A fast subspace partition clustering algorithm for high dimensional data streams

Data stream clustering is an important research problem in data stream mining. However, clustering arbitrary shapes over high dimensional data streams has not been well addressed. In this paper, we propose a fast subspace partition data streams clustering algorithm, which adopts two-phased clustering framework. In the online component, the extension of adjacent unit (E-unit), which has common edge or vertex with dense units, is presented. Moreover, the improved CD-tree lattice structure is introduced to store the information of non-empty units, maintain the position relationships among units, and keep the affiliation between dense units (D-units) and E-units. Outdated units which need to be faded are performed by decayed function, so that the corresponding microclusters are maintained dynamically. In the offline component, the final clusters are generated according to all the micro-clusters by searching D-units in radius range. Experimental results show that SPDStream has higher clustering quality than CluStream which can not generate clusters of arbitrary shapes. Furthermore, our approach has better scalability with different dimensionality and different partition granularity.