Clustering over uncertain data stream

摘要

Most existing clustering algorithms on uncertain data stream cannot discover the arbitrary shapes since they are based on k-means. To address this issue, this paper proposes a density grid-based clustering algorithm (DG-UStream) over uncertain data stream. DG-UStream uses the grid structure to store the summary information of data tuples in the stream which could be easily updated periodically. Clusters are formed by merging the adjacent grids. Furthermore, an efficient technique is developed to detect and delete the isolated grids which could greatly reduce the time and space costs. The experimental results show that DG-UStream has superior clustering performance in terms of clustering quality and time efficiency.