On the Optimal Clustering of Sequential Data.
Journal
Proceedings of the Second SIAM International Conference on Data Mining, Arlington, VA, USA, April 11-13, 2002
Pages
141-157
Date Issued
2002
Author(s)
Lin, Cheng-Ru
Abstract
Data clustering has attracted a lot of attention in the field of computational statistics and data mining. Notice, however, that in many applications not only the attributes but also the sequence of the objects has to be considered for clustering. Specifically, in some applications, a set of sequential data has to be partitioned into clusters in such a way that all the data points in each cluster form a continous region. This clustering capability, termed sequential clustering in this paper, can be applied to analyze the moving pattern of an object or the status log of a running machine. Due to its continuous constraint, prior results on data clustering cannot be applied to solve this problem, thus calling for the design of new algorithms. To remedy this, we shall explore the problem of optimal sequential clustering in this paper. Specifically, we first prove that this optimal sequential clustering problem addressed in this paper possesses the optimal substructure property which means that an optimal solution to this problem is composed of the optimal solutions to its subproblems. In light of this property, we devise algorithm SCOPT to obtain the optimal solution of the problem. The time complexity of algorithm SCOPT is O (kn2), where n is the size of the dataset and k is the number of clusters. To further reduce its complexity, we devise a greedy algorithm, SCGD, which solves the problem in linear time. Extensive experimental studies are conducted to evaluate the performance and the effectiveness of these two algorithms. It is shown that algorithm SCGD is able to obtain the solution clustering of very high quality which is in fact very close to that obtained by algorithm SCOPT.
Type
conference paper