The impact of cluster representatives on the convergence of the K-modes type clustering

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

30 Scopus Citations
View graph of relations



Original languageEnglish
Pages (from-to)1509-1522
Journal / PublicationIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number6
Online published12 Oct 2012
Publication statusPublished - Jun 2013


As a leading partitional clustering technique, k-modes is one of the most computationally efficient clustering methods for categorical data. In the k-modes, a cluster is represented by a "mode," which is composed of the attribute value that occurs most frequently in each attribute domain of the cluster, whereas, in real applications, using only one attribute value in each attribute to represent a cluster may not be adequate as it could in turn affect the accuracy of data analysis. To get rid of this deficiency, several modified clustering algorithms were developed by assigning appropriate weights to several attribute values in each attribute. Although these modified algorithms are quite effective, their convergence proofs are lacking. In this paper, we analyze their convergence property and prove that they cannot guarantee to converge under their optimization frameworks unless they degrade to the original k-modes type algorithms. Furthermore, we propose two different modified algorithms with weighted cluster prototypes to overcome the shortcomings of these existing algorithms. We rigorously derive updating formulas for the proposed algorithms and prove the convergence of the proposed algorithms. The experimental studies show that the proposed algorithms are effective and efficient for large categorical datasets. © 2013 IEEE.

Research Area(s)

  • Categorical data, Clustering, Convergence, K-modes type clustering algorithms, Weighted cluster prototype