|Title||HE-Tree: a Framework for Detecting Changes in Clustering Structure for Categorical Data Streams|
|Publication Type||Journal Article|
|Year of Publication||2009|
|Authors||Keke Chen, Ling Liu|
|Keywords||Categorical Data Clustering, Change Detection, Data Stream Mining|
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