Tom Chiu
ABSTRACT
Clustering is a widely used technique in data mining applications to discover patterns in the underlying data. Most traditional clustering algorithms are limited to handling datasets that contain either continuous or categorical attributes. However, datasets with mixed types of attributes are common in real life data mining problems. In this paper, we propose a distance measure that enables clustering data with both continuous and categorical attributes. This distance measure is derived from a probabilistic model that the distance between two clusters is equivalent to the decrease in log-likelihood function as a result of merging. Calculation of this measure is memory efficient as it depends only on the merging cluster pair and not on all the other clusters. Zhang et al [8] proposed a clustering method named BIRCH that is especially suitable for very large datasets. We develop a clustering algorithm using our distance measure based on the framework of BIRCH. Similar to BIRCH, our algorithm first performs a pre-clustering step by scanning the entire dataset and storing the dense regions of data records in terms of summary statistics. A hierarchical clustering algorithm is then applied to cluster the dense regions. Apart from the ability of handling mixed type of attributes, our algorithm differs from BIRCH in that we add a procedure that enables the algorithm to automatically determine the appropriate number of clusters and a new strategy of assigning cluster membership to noisy data. For data with mixed type of attributes, our experimental results confirm that the algorithm not only generates better quality clusters than the traditional k-means algorithms, but also exhibits good scalability properties and is able to identify the underlying number of clusters in the data correctly. The algorithm is implemented in the commercial data mining tool Clementine 6.0 which supports the PMML standard of data mining model deployment.
- 1.Banfield, J. D. and Raftery, A. E. (1993). Model-based Gaussian and Non-Gaussian Clustering. Biometrics, 49, p. 803-821.Google Scholar
- 2.Fraley, C., and Raftery, A. E. (1998). How Many Clusters? Which Clustering Method? Answers via Model-based Cluster Analysis. Computer Journal, 4, p. 578-588.Google ScholarCross Ref
- 3.Ganti, V., Gehrke, J., and Ramakrishnan, R. (1999). CACTUS - Clustering Categorical Data Using Summaries. In Proceedings of 1999 SIGKDD Conference. p. 73-82. Google ScholarDigital Library
- 4.Guha, S., Rastogi, R., and Shim, K. (1999). ROCK: A Robust Clustering Algorithm for Categorical Attributes. URL: http://www.bell-labs.com/proiect/serendip/.Google Scholar
- 5.Huang, Z. (1998). Extensions to the K-means Algorithm for Clustering Large Datasets with Categorical Values. Data Mining and Knowledge Discovery, 2, p. 283-304. Google ScholarDigital Library
- 6.MacQueen, J. B. (1967). Some Methods for Classification and Analysis of Multivariate Observations. In Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, p. 281-297.Google Scholar
- 7.Schwarz, G. (1978). Estimating the dimension of a model. The Annual of Statistics, 6, p. 461-464.Google ScholarCross Ref
- 8.Zhang, T., Ramakrishnan, R., and Livny M. (1997). BIRCH: A New Data Clustering Algorithm and its Applications. Data Mining and Knowledge Discovery 1 (2). Google ScholarDigital Library
Index Terms
- A robust and scalable clustering algorithm for mixed type attributes in large database environment
Recommendations
K-Harmonic means type clustering algorithm for mixed datasets
Display Omitted A K-Harmonic clustering algorithm for mixed data has been presented to reduce random initialization problem for partitional algorithms.The proposed clustering algorithm uses a distance measure developed for mixed datasets.The experiment ...
Determining the number of clusters using information entropy for mixed data
In cluster analysis, one of the most challenging and difficult problems is the determination of the number of clusters in a data set, which is a basic input parameter for most clustering algorithms. To solve this problem, many algorithms have been ...
A k-means type clustering algorithm for subspace clustering of mixed numeric and categorical datasets
Almost all subspace clustering algorithms proposed so far are designed for numeric datasets. In this paper, we present a k-means type clustering algorithm that finds clusters in data subspaces in mixed numeric and categorical datasets. In this method, ...
Comments