Constrained Clustering for the Evolving Data Stream

Abstract

In order to import the domain knowledge or application dependent parameters into the data mining systems, constraint-based mining has attracted a lot of research attention recently. However, most of the constraint-based mining algorithms are designed for static data sets, and are not investigated in the data stream environment. In this paper, we devise a framework of Constrained Clustering for the Evolving Data Stream, abbreviated as CCDS framework, to cluster the data stream under the pairwise range constraint. The CCDS framework proposed consists of two phases, namely the statistics reserving phase and the clustering responding phase. The statistics reserving phase provides an efficient algorithm to process and maintain the data points in a compact structure named constraint tree. The clustering responding phase generates clusters whenever a clustering request is submitted by the user. As shown in our analyses, the time complexity of the statistics reserving phase, which is the time complexity of constructing the constraint tree, is linear in the number of data points. In addition, the clustering time is also reduced by applying the statistics maintained to the clustering algorithm. Therefore, framework CCDS is very suitable for the data stream environment. It is empirically shown that the proposed framework is very efficient for dealing with multiple constrained clustering requests in the data stream environment while producing clustering results of very high quality