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 -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 -means-like algorithm for clustering categorical data is introduced. The clustering performance of the algorithm is demonstrated with two well-known data sets, namely, em soybean disease and em nursery databases.
@article{bwmeta1.element.bwnjournal-article-amcv14i2p241bwm,
author = {San, Ohn and Huynh, Van-Nam and Nakamori, Yoshiteru},
title = {An alternative extension of the k-means algorithm for clustering categorical data},
journal = {International Journal of Applied Mathematics and Computer Science},
volume = {14},
year = {2004},
pages = {241-247},
zbl = {1061.62091},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-amcv14i2p241bwm}
}
San, Ohn; Huynh, Van-Nam; Nakamori, Yoshiteru. An alternative extension of the k-means algorithm for clustering categorical data. International Journal of Applied Mathematics and Computer Science, Tome 14 (2004) pp. 241-247. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-amcv14i2p241bwm/
[000] Anderberg M.R. (1973): Cluster Analysis for Applications. - New York: Academic Press. | Zbl 0299.62029
[001] Ball G.H. and Hall D.J. (1967): A clustering technique for summarizing multivariate data.- Behav. Sci., Vol. 12, No. 2, pp. 153-155.
[002] 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. | Zbl 0441.62055
[003] 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.
[004] Cox D. (1957): Note on grouping.- J. Amer. Stat. Assoc., Vol. 52, pp. 543-547. | Zbl 0088.35402
[005] Fisher D.H. (1987): Knowledge acquisition via incremental conceptual clustering.- Mach. Learn., Vol. 2, No. 2, pp. 139-172.
[006] 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.
[007] Gibson D., Kleinberg J. and Raghavan P. (1998) Clustering categorical data: An approach based on dynamic systems. Proc. 24-th Int. Conf. Very LargeDatabases, New York, pp. 311-323.
[008] Gowda K.C. and Diday E. (1991): Symbolic clustering using a new dissimilarity measure. - Pattern Recogn., Vol. 24, No. 6, pp. 567-578.
[009] 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.
[010] Han J. and Kamber M. (2001): Data Mining: Concepts and Techniques. - San Francisco: Morgan Kaufmann Publishers.
[011] Hathaway R.J. and Bezdek J.C. (1986): Local convergence of the c-means algorithms.- Pattern Recogn., Vol. 19, No. 6, pp. 477-480. | Zbl 0623.62058
[012] 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.
[013] Huang Z. (1998): Extensions to the k-means algorithm for clustering large data setswith categorical values. - Data Mining Knowl. Discov., Vol. 2, No. 2, pp. 283-304.
[014] 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.
[015] 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. | Zbl 0623.62059
[016] Jain A.K. and Dubes R.C. (1988): Algorithms for Clustering Data.- Englewood Cliffs: Prentice Hall. | Zbl 0665.62061
[017] Kaufman L. and Rousseeuw P.J. (1990): Finding Groups in Data. - New York: Wiley.
[018] 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. | Zbl 0214.46201
[019] 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.
[020] Ralambondrainy H. (1995): A conceptual version of the k-means algorithm.- Pattern Recogn. Lett., Vol. 15, No. 11, pp. 1147-1157.
[021] Ruspini E.R. (1969): A new approach to clustering. -Inf. Contr., Vol. 15, No. 1, pp. 22-32. | Zbl 0192.57101
[022] 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. | Zbl 0546.62037