Attribute Value Weighting in K-Modes Clustering

Categorical data clustering is an important research problem in pattern recognition and data mining. The k -modes algorithm [1] extends the k -means paradigm to cluster categorical data by using (1) a simple matching dissimilarity measure for categorical objects, (2) modes instead of means for clusters, and (3) a frequency-based method to update modes in the k -means fashion to minimize the cost function of clustering. The k -modes algorithm is widely used in real world applications due to its efficiency in dealing with large categorical database. In standard k -modes algorithm, a simple matching similarity measure is used, in which the distance is either 0 or 1. Such simple matching dissimilarity measure doesn't consider the implicit similarity relationship embedded in categorical values, which will result in a weaker intra-cluster similarity by allocating less similar objects to the cluster. To illustrate this fact, let's consider the following example shown in Fig.1. Example 1: In this artificial example, the dataset is described with 3 categorical attributes A1, A2,and A3, and there are two clusters with their modes. Assuming that we have to allocate a data object Y = [a, p, w] to either cluster 1 or cluster 2. According to the k -modes algorithm, we can assign Y to either cluster 1 or cluster 2 since these two clusters have the same mode. However, from the viewpoint of intra-cluster simila rity, it is more desirable to allocate Y to cluster 1.