Data stream dynamic clustering supported by Markov chain isomorphisms

Several research fields have described phenomena that produce endless sequences of samples, referred to as data streams. These phenomena are studied using data clustering models continuously obtained throughout the endless data gathering process, whose set of dynamical properties, i.e., behavior, ev...

Full description

Saved in:
Bibliographic Details
Published in:Intelligent data analysis 2013-01, Vol.17 (3), p.439-457
Main Authors: Albertini, Marcelo Keese, de Mello, Rodrigo Fernandes
Format: Article
Language:English
Subjects:
Algorithms
Clustering
Clusters
Isomorphism
Markov chains
Mathematical models
Statistical analysis
Streams
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Several research fields have described phenomena that produce endless sequences of samples, referred to as data streams. These phenomena are studied using data clustering models continuously obtained throughout the endless data gathering process, whose set of dynamical properties, i.e., behavior, evolves over time. In order to cope with data streams characteristics, researchers have developed clustering techniques with low time-complexity requirements. However, pre-defined and static parameters (thresholds, number of clusters and learning rates) commonly found in current techniques still limit the application of clustering to data streams. These limitations to adapt clustering process to behavior changes motivated this paper to propose an on-line and adaptive approach to detect changes and modify parameters. The proposed approach is based on the traditional k-means algorithm to update cluster prototypes and the statistical model of Markov chains to represent behavior. Behavior changes are detected by testing the isomorphism of Markov chains over time under the grounds of Dynamical Systems Theory. The results have confirmed the advantages of the approach when compared with current techniques.
ISSN:1088-467X
1571-4128
DOI:10.3233/IDA-130588