Density-based clustering of data streams at multiple resolutions

Abstract

In data stream clustering, it is desirable to have algorithms that are able to detect clusters of arbitrary shapes, changing clusters that evolve over time, and clusters with noise. In recent years, stream data clustering algorithms are based on an online-offline approach: The online component captures synopsis information from the data stream (thus, overcoming the real-time and memory constraint issues) and the offline component generates clusters using the stored synopsis. The online-offline approach affects the overall performance of stream data clustering in various ways: (1) How easily is the synopsis information derived from stream data? (2) The complexity of data structure used to store and man age the synopsis information. (3) The frequency with which the offline component is used to generate clusters. In this project we propose an algorithm that (1) computes and updates synopsis information in constant time; (2) allows users to discover clusters at multiple resolutions; (3) determines the right time for users to generate clusters from the synopsis information; (4) generates clusters of higher purity than existing algorithms; and (5) determines the right threshold function for density-based clustering based on the fading model of stream data. To the best of our knowledge, no existing data stream algorithm has all of these features. Experimental results show that our algorithm is able to detect arbitrarily shaped evolving clusters of high quality. [3rd Award]