HE-Tree: a Framework for Detecting Changes in Clustering Structure for Categorical Data Streams

TitleHE-Tree: a Framework for Detecting Changes in Clustering Structure for Categorical Data Streams
Publication TypeJournal Article
Year of Publication2009
AuthorsKeke Chen, Ling Liu
KeywordsCategorical Data Clustering, Change Detection, Data Stream Mining
Abstract

Analyzing clustering structures in data streams can provide critical information for real-time decisionmaking. Most research in this area has focused on clustering algorithms for numerical data streams, andvery few have proposed to monitor the change of clustering structure. Most surprisingly, to our knowledge,no work has been proposed on monitoring clustering structure for categorical data streams. In this paper,we present a framework for detecting the change of primary clustering structure in categorical data streams,which is indicated by the change of the best number of clusters (Best K) in the data stream. The frameworkuses a Hierarchical Entropy Tree structure (HE-Tree) to capture the entropy characteristics of clusters in adata stream, and detects the change of Best K by combining our previously developed BKPlot method. TheHE-Tree can efficiently summarize the entropy property of a categorical data stream and allow us to drawprecise clustering information from the data stream for generating high-quality BKPlots. We also developthe time-decaying HE-Tree structure to make the monitoring more sensitive to recent changes of clusteringstructure. The experimental result shows that with the combination of the HE-Tree and the BKPlot methodwe are able to promptly and precisely detect the change of clustering structure in categorical data streams.

Full Text

Keke Chen and Ling Liu, "HE-Tree: a Framework for Detecting Changes in Clustering Structure for Categorical Data Streams", VLDB Journal, Christian S. Jensen, Philip A. Bernstein and Kian-Lee Tan (Eds.), 18, 2009
research center: Kno.e.sis Center
pages: TBA
publisher: Springer Verlag
year: 2009
hasEditor: Christian S. Jensen, Philip A. Bernstein And Kian-Lee Tan
hasBookTitle: VLDB Journal