A coarse-grain grid-based subspace clustering method for online multi-dimensional data streams

ABSTRACT

This paper proposes a subspace clustering algorithm which combines grid-based clustering with frequent itemset mining. Given a d-dimensional data stream, the on-going distribution statistics of its data elements in every one-dimensional data space is monitored by a list of fine-grain grid-cells called a sibling list, so that all the one-dimensional clusters are accurately identified. By tracing a set of frequently co-occurred one-dimensional clusters, it is possible to find a coarse-grain dense rectangular space in a higher dimensional subspace. An ST-tree is introduced to continuously monitor dense rectangular spaces in all the subspaces of the d dimensions. Among the spaces, those ones whose densities are greater than or equal to a user defined minimum support threshold S_min are corresponding to final clusters.

REFERENCES

• 1: Nam Hun Park , Won Suk Lee, Cell trees: An adaptive synopsis structure for clustering multi-dimensional on-line data streams, Data & Knowledge Engineering, v.63 n.2, p.528-549, November, 2007 [doi>10.1016/j.datak.2007.04.003]
• 2: Ramesh C. Agarwal , Charu C. Aggarwal , V. V. V. Prasad, A tree projection algorithm for generation of frequent item sets, Journal of Parallel and Distributed Computing, v.61 n.3, p.350-371, March 1, 2001 [doi>10.1006/jpdc.2000.1693]
• 3: Joong Hyuk Chang , Won Suk Lee, Finding recent frequent itemsets adaptively over online data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956807]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
data mining, data streams, grid-based clustering, st-tree, subspace clustering