Data stream clustering algorithm based on spatial directed graph

Recently, the grid-density based clustering has become one of the major issues among all of the clustering approaches, it has special advantages over other clustering algorithms, such as less computation and the ability of clustering with arbitrarily shape, which are particularly useful for the data stream clustering. This paper defines a spatial directed graph named Grid-Based Graph (GBG) to store the non-empty grids in data space, and proposes a data stream clustering algorithm based on spatial directed graph GBGSClu (Grid-Based Graph Stream Clustering). GBG graph composes of vertices and directed edges, if a vertex A has a neighboring dense vertex B, and then there is a directed edge from vertex B to A in GBG. The algorithm maps the data stream into the non-empty vertices online, updates the vertices' feature vectors with the arriving of data stream, deletes the sparse vertices every gap time, generates GBG graph when the clustering quest coming and finally clusters on the current structure. The eventual clustering results can be obtained by only checking the vertices' in-degree which can reduce the computation needed in clustering. The validity and efficiency of GBGSClu algorithm have been tested and verified by clustering on real and synthetic datasets.