An alternative extension of the k-means algorithm for clustering categorical data

San, O. M. ; Huynh, V. N. ; Nakamori, Y.

International Journal of Applied Mathematics and Computer Science, Tome 14 (2004) no. 2, pp. 241-247.

Résumé

Most of the earlier work on clustering has mainly been focused on numerical data whose inherent geometric properties can be exploited to naturally define distance functions between data points. Recently, the problem of clustering categorical data has started drawing interest. However, the computational cost makes most of the previous algorithms unacceptable for clustering very large databases. The k-means algorithm is well known for its efficiency in this respect. At the same time, working only on numerical data prohibits them from being used for clustering categorical data. The main contribution of this paper is to show how to apply the notion of "cluster centers” on a dataset of categorical objects and how to use this notion for formulating the clustering problem of categorical objects as a partitioning problem. Finally, a k-means-like algorithm for clustering categorical data is introduced. The clustering performance of the algorithm is demonstrated with two well-known data sets, namely, soybean disease and nursery databases.

Détail

Keywords: cluster analysis, categorical data, data mining
Mots-clés : analiza skupień, dane kategoryczne, eksploracja danych

Bibliographie

[1] Anderberg M.R. (1973): Cluster Analysis for Applications. — New York: Academic Press.

[2] Ball G.H. and Hall D.J. (1967): A clustering technique for summarizing multivariate data.—Behav. Sci., Vol. 12, No. 2, pp. 153–155.

[3] Bezdek J.C. (1980): A convergence theorem for the fuzzy ISODATA clustering algorithms.—IEEE Trans. Pattern Anal. Mach. Intell., Vol. 2, No. 1, pp. 1–8.

[4] Blake C.L. and Merz C.J. (1998): UCI Repository of machine learning databases. — Available at: http://www.ics.uci.edu/~mlearn/MLRepository.html, Irvine, CA: University of California, Department of Information and Computer Science.

[5] Cox D. (1957): Note on grouping. — J. Amer. Stat. Assoc., Vol. 52, pp. 543–547.

[6] Fisher D.H. (1987): Knowledge acquisition via incremental conceptual clustering. — Mach. Learn., Vol. 2, No. 2, pp. 139–172.

[7] Ganti V., Gehrke J. and Ramakrishnan R. (1999): CATUS - Clustering categorical data using summaries.—Proc. Int. Conf. Knowledge Discovery and Data Mining, San Diego, USA, pp. 73–83.

[8] Gibson D., Kleinberg J. and Raghavan P. (1998) Clustering categorical data: An approach based on dynamic systems. Proc. 24-th Int. Conf. Very Large Databases, New York, pp. 311–323.

[9] Gowda K.C. and Diday E. (1991): Symbolic clustering using a new dissimilarity measure. — Pattern Recogn., Vol. 24, No. 6, pp. 567–578.

[10] Guha S., Rastogi R. and Shim K. (2000): ROCK: A robust clustering algorithm for categorical attributes. — Inf. Syst., Vol. 25, No. 5, pp. 345–366.

[11] Han J. and Kamber M. (2001): Data Mining: Concepts and Techniques. — San Francisco: Morgan Kaufmann Publishers.

[12] Hathaway R.J. and Bezdek J.C. (1986): Local convergence of the c-means algorithms. — Pattern Recogn., Vol. 19, No. 6, pp. 477–480.

[13] Huang Z. (1997): Clustering large data sets with mixed numeric and categorical values, In: KDD: Techniques and Applications (H. Lu, H. Motoda and H. Luu, Eds.). — Singapore: World Scientific, pp. 21–34.

[14] Huang Z. (1998): Extensions to the k-means algorithm for clustering large data sets with categorical values. — Data Mining Knowl. Discov., Vol. 2, No. 2, pp. 283–304.

[15] Huang Z. and Ng M.K. (1999): A fuzzy k-modes algorithm for clustering categorical data. — IEEE Trans. Fuzzy Syst., Vol. 7, No. 4, pp. 446–452.

[16] Ismail M.A. and Selim S.Z. (1986): Fuzzy c-means: Optimality of solutions and effective termination of the problem. — Pattern Recogn., Vol. 19, No. 6, pp. 481–485.

[17] Jain A.K. and Dubes R.C. (1988): Algorithms for Clustering Data.—Englewood Cliffs: Prentice Hall.

[18] Kaufman L. and Rousseeuw P.J. (1990): Finding Groups in Data.—New York: Wiley.

[19] MacQueen J.B. (1967): Some methods for classification and analysis of multivariate observations.—Proc. 5-th Symp. Mathematical Statistics and Probability, Berkelely, CA, Vol. 1, pp. 281–297.

[20] Michalski R.S. and Stepp R.E. (1983): Automated construction of classifications: Conceptual clustering versus numerical taxonomy. — IEEE Trans. Pattern Anal. Mach. Intell., Vol. PAMI-5, No. 4, pp. 396–410.

[21] Ralambondrainy H. (1995): A conceptual version of the k-means algorithm. — Pattern Recogn. Lett., Vol. 15, No. 11, pp. 1147–1157.

[22] Ruspini E.R. (1969): A new approach to clustering. — Inf. Contr., Vol. 15, No. 1, pp. 22–32.

[23] Selim S.Z. and Ismail M.A. (1984): k-Means-type algorithms: A generalized convergence theorem and characterization of local optimality. — IEEE Trans. Pattern Anal. Mach. Intell., Vol. PAMI-6, No. 1, pp. 81–87.