DENGRIS-Stream: A Density-Grid based Clustering Algorithm for Evolving Data Streams over Sliding Window
Amineh Amini, Teh Ying Wah · 2012
Evolving data streams are ubiquitous. Various clustering algorithms have been developed to extract useful knowledge from evolving data streams in real time. Density-based clustering method has the ability to handle outliers and discover arbitrary shape clusters whereas grid-based clustering has high speed processing time. Sliding window is a widely used model for data stream mining due to its emphasis on recent data and its limited memory requirement. In this paper, we propose a new framework for density grid-based clustering algorithm using sliding window model. The algorithm is called DENGRIS-Stream (a DENsity GRId-based algorithm for clustering data streams over Sliding window). It discovers the arbitrary shape clusters in limited time and memory. The DENGRIS-Stream algorithm has an online component which maps each data record to a density grid in each sliding window. The offline component adjusts the clusters by removing sparse grids and merging the neighboring dense grids. shape clusters and is useful for identifying the noise. Some typical examples of density-based algorithms include DBSCAN (13), OPTICS (7) and DENCLUE (18). The main idea in these algorithms is to consider the dense area of points in the data space as clusters, which are separated by low density area (noise). Another method of clustering is grid-based clustering and its remarkable feature is that it has fast processing time which is independent from the number of data points. Well-known algorithms of grid-based clustering include STING (29), CLIQUE (5), WaveCluster (26). The grid-based clustering approach uses a multi-resolution grid data structure. It divides the object space into a finite number of cells that form a grid structure on which all of the operations for clustering are performed.