A weighted k -modes clustering using new weighting method based on within-cluster and between-cluster impurity measures

Abstract

Partitioning a set of objects into groups or clusters is a fundamental task in data mining, and clustering is a popular approach to implementing partitioning. Among several clustering algorithms, the k-means algorithm is well-known and widely applied in several areas that only handle numerical attributes. The k-modes algorithm is an extension of the k-means algorithm that deals with categorical variables, which has several variations such as fuzzy methods. This paper presents a new attribute weighting method for the k-modes algorithm that utilizes impurity measures such as entropy and Gini impurity. The proposed algorithm considers both the distribution of categories of attributes within the same cluster and between different clusters. By doing this, categorical variables defined as more important that others by the new algorithm have a significant influence on the similarity calculation, and this results in improved clustering performance, which was confirmed by experiments.

1 Introduction

Clustering is an unsupervised learning method that identifies groups of objects similar to each other in such a way that generated groups are distinct from other groups. Clustering is one way to gain insight from data distribution and has been applied to many real-world applications such as marketing, psychology, and bioinformatics. Because of the usefulness of clustering, various clustering algorithms have been developed such as k-means algorithm [29, 30], spectral clustering algorithm [35], hierarchical clustering algorithm [26], density-based spatial clustering algorithm of applications with noise [14, 33],two-stage genetic clustering algorithm [21] and others. However, clustering of categorical data has been less extensively studied compared with clustering of numerical data. Recently, clustering of categorical data has gained increasing attention considering practical requirements from fields such as statistics and psychology.

Studies on the clustering of categorical data are limited because of certain problems that need to be solved [7, 9]. Categorical attributes are lacking in inherent order of categories in each attribute, which prevents the definition of similarity or dissimilarity measures. The difficulty on defining distance measures is critical in evaluating the clustering quality during the clustering process, which does not occur when dealing with only numerical attributes. Several dissimilarity measures for categorical data have been proposed to overcome this problem and utilize similar clustering techniques for numerical data [12].

Based on dissimilarity measures for categorical data instead of distance metrics such as Euclidean distance, k-modes clustering algorithm [22, 23], which similar to the k-means clustering algorithm for numerical data was proposed and became one of the most efficient clustering methods for datasets including categorical features [3 , 20]. Like the k-means clustering algorithms, which have been widely used in real-world applications because of its simplicity and strength in high-dimensional space, the k-modes clustering algorithm groups a given dataset with k clusters to minimize dissimilarities between a data point and the centroid of the cluster to which the data point belongs for all data points. The simplest way to do this is to count the number of mismatching attributes for dissimilarity calculation.

Furthermore, a fuzzy version of the k-modes clustering algorithm was also proposed in [24], in which each data point has membership degrees for k clusters instead of being delegated to one of the k clusters. Similar to the way in which the performance of the k-means clustering was improved by introducing fuzziness, the fuzzy k-modes clustering algorithm has achieved improved clustering results [19, 24].

In addition, attribute weighting has been introduced in clustering algorithms to overcome the problems in high-dimensional spaces. In such spaces, data sparseness, skewness, and irrelevancy or redundancy of some attributes can degrade the clustering performance because of small differences between similar and dissimilar pairs of objects. Similar to other clustering algorithms for categorical data, attribute weighting techniques were tested first for numerical data. For numerical data, attribute weighted clustering has been intensively studied by utilizing common weights for the entire dataset [11 , 32] and extended versions of conventional algorithms, which provide different feature weights for each cluster, also called as subspace in such algorithms, have been newly developed [8, 15]. Although these weighting algorithms have been successfully applied to different areas, the application areas are limited to numerical data. Therefore, the clustering algorithms proposed in [22, 23] were modified for datasets with categorical attributes; their effectiveness has been confirmed in calculation of the feature weights of datasets with categorical attributes.

Because of the enhancement induced by weighting in early researches, new weighting algorithms have been continuously proposed. In [1], each categorical variable calculates a similarity measure in a weighted manner, which means that a weighting scheme is embedded in the similarity calculation. This method presents nonzero dissimilarity value, 1 - w_kl when x_il = x_jl where k represents the specific cluster, l denotes one of the categorical variables and i and j represent data points. This is opposite to the Gower similarity [18], which gives zero when x_il = x_jl. w_kl is generally proportional to the number of objects with the certain category of the lth attribute in the kth cluster if _xi and _xj belong to the kth cluster. This forces a certain category of the lth attribute to have a larger weight when objects with this value are concentrated in the specific cluster. In other studies, the weights of features were calculated based on complementary entropy for the k-modes algorithm [6]. Both [1] and [6] consider distributions of values of categorical attributes to count different effects of features during clustering. However, these works only focus on the individual cluster.

In the present paper, the new attribute weighting method using impurity measures has been proposed in different views to consider the relations among cluster. The main characteristics of the proposed algorithm are as follows:

A new weighting method uses impurity measures such as entropy and Gini impurity to determine which attributes are more relevant to separate clusters.

A new weighting method considers the distinct number of values of each attribute to calculate weights. Because of the existence of the upper bound of entropy and Gini impurity, a large weight might be applied on categorical attributes with large categories. To remove this effect on weights, the proposed method applies relative entropy and Gini impurity to the upperbound.

A new weighting method considers distributions of categories within clusters and between clusters. Conventional weighting methods usually reflect distributions of categories within clusters. They put additional weight on attributes such that values of attributes in each cluster are highly imbalanced. However, the proposed method incorporates the distribution of each value of categorical attributes across clusters.

The rest of the paper is organized as follows. In Sections 2 and 3, detailed reviews of the k-modes and fuzzy k-modes clustering algorithms are provided. In Section 4, the proposed weighting method is described in detail. In Section 5, the experiment results obtained from the proposed algorithm and other comparative algorithms are presented. Finally, conclusion of the paper is given in Section 6.

2 The k-modes clustering algorithm

The k-modes clustering algorithm, proposed in [23], is an extension of the k-means clustering algorithm that cat be applied for categorical data. The objective of clustering a dataset of n observations with d categorical variables into k clusters, C₁, …, C_k is to minimize the following objective function F. $F (W, Z) = \sum_{j = 1}^{k} \sum_{i = 1}^{n} w_{ji} d (z_{j}, x_{i})$ (1) subject to ${\begin{matrix} w_{ji} \in {0, 1}, & 1 \leq j \leq k, 1 \leq i \leq n, \\ \sum_{j = 1}^{k} w_{ji} = 1, & 1 \leq i \leq n, \\ 0 < \sum_{i = 1}^{n} w_{ji} < n, & 1 \leq j \leq k \end{matrix}$ (2) where

W = [w_ji] is a k-by-n matrix and w_ji is a binary variable that indicates whether object x_i belongs to the jth cluster. w_ji is 1 if x_i belongs to the jth cluster and 0 otherwise

z_j is the centroid of the jth cluster with d categorical attributes

d (z_j, x_i) is a dissimilarity measure between x_i and z_j which is defined as $d (z_{j}, x_{i}) = \sum_{l = 1}^{d} δ (z_{jl}, x_{il})$ and δ (z_jl, x_il) is a dissimilarity measure defined on a categorical variable. There are several different ways to calculate dissimilarity of categorical variables

Similar to k-means clustering, k-modes clustering also minimizes the objective function in such a way as to use partial optimization for Z and W. In the k-modes clustering, two steps of finding the best Z and W are repeated until convergence.

Problem P₁: Fix $Z = \hat{Z}$ , solve the reduced problem $F (W, \hat{Z})$

Problem P₂: Fix $W = \hat{W}$ , solve the reduced problem $F (\hat{W}, Z)$

The solution of problem P₁ is given by ${\hat{w}}_{ji} = {\begin{matrix} 1 & if d (z_{j}, x_{i}) \leq d (z_{h}, x_{i}), 1 \leq h \leq k \\ 0 & otherwise \end{matrix}$ (3)

The solution of problem P₂ is given by $z_{jl} = a_{l}^{(r)}$ (4) where $r = {argmax}^{t} | {x_{i} | w_{ji} = 1, x_{il} = a_{l}^{(t)}} |$ . Here, |X| denotes the number of elements in the set X and $a_{l}^{(t)}$ represent one of the categories of the lth attribute and the number of categories in the lth attribute is m_l. It means that value of the lth attribute of z_j is determined by finding the majority value of the lth attributed in the jth cluster.

3 The fuzzy k-modes clustering algorithm

The fuzzy k-modes clustering algorithm is a fuzzy version of the k-modes clustering [24]. In this algorithm, the objective function is not different from that of the k-modes clustering algorithm, but w_ji is not a binary variable. In the original k-modes clustering, an object belongs to one of k clusters. However, the fuzzy k-modes clustering algorithm calculates the probability that an object belongs to a cluster. The probability is computed based on dissimilarity between objects and centroids. If an object is close to the specific centroid, it is more probable that this object belongs the cluster represented by the centroid. To reflect this assumption, the probability to belong to certain cluster increases as the dissimilarity between an object and a cluster’s centroiddecreases.

In [24], the objective function of the k-modes clustering algorithm is modified slightly to introduce the fuzzy concept. $F (W, Z) = \sum_{j = 1}^{k} \sum_{i = 1}^{n} w_{ji}^{e} d (z_{j}, x_{i})$ (5) subject to ${\begin{matrix} 0 \leq w_{ji} \leq 1, & 1 \leq i \leq n, 1 \leq j \leq k \\ \sum_{j = 1}^{k} w_{ji} = 1, & 1 \leq i \leq n \\ 0 < \sum_{i = 1}^{n} w_{ji} < n, & 1 \leq j \leq k \end{matrix}$ (6) where newly introduced parameter e controls the fuzziness of membership degree, w_ji of each datum and w_ji is computed by $w_{ji} = {(\sum_{h = 1}^{k} {(\frac{d (z_{j}, x_{i})}{d (z_{h}, x_{i})})}^{\frac{1}{e - 1}})}^{- 1}$ (7)

If d (z_j, _xi) =0 and d (z_h, _xi) =0 for any h, 1 ≤ h ≤ k, w_ji is set to 0. In the case that d (z_j, _xi) =0 and d (z_h, _xi) ≠0 for all h, w_ji is 1.

At first, the fuzzy k-modes clustering algorithm only modified the method to calculate w_ji and each attribute of the cluster’s centroid was set to the specific category if the summation of the membership degree of the objects with the category for that attribute was higher than that of the other categories within the clusters. $z_{jl} = a_{l}^{(r)} where \sum_{x_{il} = a_{l}^{(r)}} w_{ji}^{e} \geq \sum_{x_{il} = a_{l}^{(t)}} w_{ji}^{e}, 1 \leq t \leq m_{l}$ (8)

In [27], an improved version of the fuzzy k-modes clustering was proposed by introducing fuzzy centroids. The proposed k-modes clustering algorithm calculates the centroids of clusters in a fuzzy way in addition to w_ji. Instead of hard assignment of the value on z_jl, fuzzy centroids also calculate the probability that z_jl is $a_{l}^{(r)}$ . Similar to the membership degree, the probability, $ω_{jl}^{(r)}$ that z_jl is $a_{l}^{(r)}$ is proportional to the sum of the jth membership degree of objects whose lth attribute’s value is $a_{l}^{(r)}$ . $ω_{jl}^{(r)} = P (z_{jl} = a_{l}^{(r)}) \propto \sum_{x_{il} = a_{l}^{(r)}} w_{ji}^{e}$ (9) In the step to calculate centroids of cluster, this algorithm calculates (9) and keeps them to use dissimilarity between data samples and centroids. In other words, a value of each attribute of centroid, z_jl is defined as $z_{jl} = {(a_{l}^{(1)}, ω_{jl}^{(1)}), \dots, (a_{l}^{(m_{l})}, ω_{jl}^{(m_{l})})}$ (10) where $0 \leq ω_{jl}^{(r)} \leq 1$ for 1 ≤ r ≤ m_l and $\sum_{t = 1}^{m_{l}} ω_{jl}^{(t)} = 1$ .

Dissimilarity calculation should be tuned when the fuzzy concept is used for centroids, because it is impossible to determine whether a value of a categorical attribute of an object matches with that of a centroid or not. Therefore, dissimilarity is calculated by averaging dissimilarity of every possible pairs in weighted manner and weights is set to $ω_{jl}^{(r)}$ . By doing this, dissimilarity can be obtained as followingway. $d (z_{jl}, x_{il}) = \sum_{t = 1}^{m_{l}} ω_{jl}^{(t)} d (a_{l}^{(t)}, x_{il})$ (11)

4 Weighted dissimilarity measure for categorical variables

4.1 Weighting method using within-cluster information

Generally, in the k-modes clustering algorithm, each categorical attribute has an equal effect on the dissimilarity calculation because the dissimilarity of two objects with categorical variables is computed by summation of the dissimilarity of each categorical variable. However, certain attributes are more relevant to separate objects into different clusters. To reflect this situation into k-modes clustering, a weighting scheme should be introduced.

The proposed weighting algorithm is based on the entropy [34] or the Gini impurity [5]. Both the entropy and the Gini impurity are measures of impurity and are widely used measurements in decision tree algorithms; they can be used to obtain the best split at each node of decision trees. These two measures have the maximum value when every outcome have equal probabilities and produce zero when only one outcome exists, which is the reason that they are called impurity measures.

The entropy is defined as $I_{E} (f) = - \sum_{i = 1}^{m} f_{i} {log}_{b} f_{i}$ (12) and the Gini impurity is defined as $I_{G} (f) = \sum_{i = 1}^{m} f_{i} (1 - f_{i}) = 1 - \sum_{i = 1}^{m} f_{i}^{2}$ (13) where f_i is the frequency ratio of the ith category in a set and the number of categories in a set is m. Base of log, b is usually set as 2 for entropy.

Compared with the entropy, the Gini impurity tends to locate a larger group in a set to minimize misclassification errors (misclassification error is defined as $1 - max_{i} f_{i}$ ). In addition, calculating the Gini impurity is slightly faster than calculating the entropy because computing the log requires more computation power. Otherwise, the entropy tends to find groups of classes that make up 50% of data samples.

The main concept of the proposed algorithm is to give a large weight to the variable with the low entropy or the low Gini impurity because if categories of a categorical variable are homogeneously distributed in a cluster, this categorical variable is meaningless when objects are divided into clusters, and the two measures become zero when only one category exists for a categorical attribute in a cluster.

To compute weights for categorical variables, first, calculate the entropy, I_E,w (f_lj) or the Gini impurity, I_G,w (f_lj) of each categorical variable based on the distribution of categories within the clusters. $I_{E, w} (f_{lj}) = - \sum_{r = 1}^{m_{l}} f_{lj}^{(r)} {log}_{2} f_{lj}^{(r)}$ (14) $I_{G, w} (f_{lj}) = 1 - \sum_{r = 1}^{m_{l}} {(f_{lj}^{(r)})}^{2}$ (15) where

f_lj represents a distribution of categories of the lth categorical attribute in the jth cluster

$f_{lj}^{(r)}$ , frequency ratio of the rth category of the lth categorical attribute in the jth cluster is defined as $f_{lj}^{(r)} = \frac{n_{lj}^{(r)}}{n_{\cdot j}}$ where $n_{lj}^{(r)} = | {x_{i} | x_{i} \in C_{j}, x_{il} = a_{l}^{(r)}} |$ and n_·j is the number of objects in the cluster C_j

From I_E,w (f_lj) or I_G,w (f_lj), the weights, λ_l,w for categorical variables are computed using the weighted average. For clarity, both I_E,w (f_lj) and I_G,w (f_lj) are represented by I_w (f_lj) in common equations because the scheme of calculating weights is the same for both the entropy and the Gini impurity. $λ_{l, w} \propto \sum_{j = 1}^{k} α_{j} (1 - I_{w} (f_{lj}))$ (16) where α_j is a weight for categorical attributes proportional to the number of data samples that belong to the jth cluster and that is defined as $α_{j} = \frac{n_{\cdot j}}{n}$ . I_w (f_lj) is subtracted from one to account for the negative relationship between I_w (f_lj) and weight of a variable. Weights are normalized to ensure $\sum_{l = 1}^{d} λ_{l, w} = 1$ and final weights are computed by $λ_{l, w} = \frac{\sum_{j = 1}^{k} α_{j} (1 - I_{w} (f_{lj}))}{\sum_{l = 1}^{d} \sum_{j = 1}^{k} α_{j} (1 - I_{w} (f_{lj}))}$ (17)

In addition, we further modified the Equation (17) to consider the number of categories in a categorical variable. In cases in which the number of categories in a categorical variable is large, I_w (f_lj) has a greater probability of being large. Therefore, the possible maximum I_w (f_lj) of normalized I_w (f_lj) is defined as the function of the number of categories in a categorical variable. $I_{w}^{'} (f_{l j}) = (\frac{I_{w, \max} (f_{l}) - I_{w} (f_{l j})}{I_{w, \max} (f_{l})})$ (18) where I_w,max (f_l) is the possible maximum entropy or Gini impurity of the lth categorical variable and defined as $I_{E, w, max} (f_{l}) = - \sum_{r = 1}^{m_{l}} \frac{1}{m_{l}} {log}_{2} \frac{1}{m_{l}} = {log}_{2} m_{l}$ (19) $I_{G, w, max} (f_{l}) = 1 - \sum_{r = 1}^{m_{l}} {(\frac{1}{m_{l}})}^{2} = 1 - \frac{1}{m_{l}}$ (20) where m_l is the number of categories in the lth categorical attribute. $λ_{l, w}^{'} = \frac{\sum_{j = 1}^{k} α_{j} (1 - I_{w}^{'} (f_{lj}))}{\sum_{l = 1}^{d} \sum_{j = 1}^{k} α_{j} (1 - I_{w}^{'} (f_{lj}))}$ (21)

4.2 Weighting method using between-cluster information

Distributions of categories within clusters are only considered to obtain appropriate weights for categorical variables in many k-modes clustering algorithms. However, in cases where original categories are already inhomogeneously distributed, I_w (f_lj) is more likely to be high. For example, when the portion of zero in a binary categorical variable is 90%, Gini impurity is 0.18; the same value is obtained even though every cluster has the same distribution, which means that this categorical variable is not significant for the separation of clusters.

To avoid this drawback in weighting variables, distributions of values of categorical variables across clusters must be considered. $I_{b} (g_{l}) = \sum_{r = 1}^{m_{l}} β_{lr} I_{b} (g_{l}^{(r)})$ (22) In Equation (22), g_l represent the distribution of categories of the lth attribute across clusters. It also contains frequency ratios, but they are computed within a set with the same category value. Because of this, the notation is changed from f to g for clarity. Difference between f and g is illustrated in Table 1. In addition, the entropy or the Gini impurity of a collection of assigned clusters for objects with $x_{il} = a_{l}^{(r)}$ , $I_{E, b} (g_{l}^{(r)})$ and $I_{G, b} (g_{l}^{(r)})$ are defined as following $I_{E, b} (g_{l}^{(r)}) = - \sum_{j = 1}^{k} g_{lj}^{(r)} {log}_{2} g_{lj}^{(r)}$ (23) $I_{G, b} (g_{l}^{(r)}) = 1 - \sum_{j = 1}^{k} {(g_{lj}^{(r)})}^{2}$ (24) where

$g_{lj}^{(r)}$ is the frequency ratio of objects whose category value of the lth categorical attribute is $a_{l}^{(r)}$ in the jth cluster and computed by $g_{lj}^{(r)} = \frac{n_{lj}^{(r)}}{n_{l \cdot}^{(r)}}$ where $n_{lj}^{(r)} = | {x_{i} : x_{i} \in C_{j}, x_{il} = a_{l}^{(r)}} |$ and $n_{l \cdot}^{(r)} = \sum_{j = 1}^{k} n_{lj}^{(r)} = | {x_{i} : x_{il} = a_{l}^{(r)}} |$

β_lr is a weight for each category in the lth variable to account for the number of objects with a certain category value and is calculated by $β_{lr} = \frac{n_{l \cdot}^{(r)}}{n}$

Similar to the weighting method using within-cluster information, an upper bound of I_b (g_l) is set on the basis of the number of clusters k and the number of categories m_l for the lth categorical variable. $I_{b}^{'} (g_{l}^{(r)}) = (\frac{I_{b, max} (g_{l}) - I_{b} (g_{l}^{(r)})}{I_{b, max} (g_{l})})$ (25) where I_E,b,max (g_l) is defined as k · log ₂m_l and I_G,b,max (g_l) is defined as $1 - \frac{1}{k \cdot {log}_{2} m_{l}}$ . The reason to consider k in setting an upper bound of I_b (g_l) is that I_b,max (g_l) may have a higher value with increasing of the number of categories because the number of objects with the certain category value for variables decreases as the number of categories increases and the probability that objects are grouped together in some clusters increases when a small number of objects are separated into k clusters.

Weights from $I_{b}^{'} (g_{l}^{(r)})$ are obtained in the same way as weights obtained from $I_{w}^{'} (f_{lj})$ . $λ_{l, b} \propto (1 - I_{b}^{'} (g_{l}^{(r)}))$ (26)

Overall weights of attributes are obtained by the weighted summation of two different weights λ_l,w(or $λ_{l, w}^{'}$ ) and λ_l,b (or $λ_{l, b}^{'}$ ); the amount of contribution of each weight on the total weight is adjusted by parameter c (0 ≤ c ≤ 1). $λ_{l} = c λ_{l, w} + (1 - c) λ_{l, b}$ (27)

4.3 Fuzzy weighting method

In the previously introduced weighting method, $f_{lj}^{(r)}$ and $g_{lj}^{(r)}$ are computed based on objects that belong to the jth cluster. However, $f_{lj}^{(r)}$ and $g_{lj}^{(r)}$ can be interpreted as the probability that $x_{il} = a_{l}^{(r)}$ in the jth cluster and the probability that an object with $x_{il} = a_{l}^{(r)}$ belongs to the jth cluster respectively. Therefore, $f_{lj}^{(r)}$ and $g_{lj}^{(r)}$ can be computed using membership degree. In fuzzy weighting method, $f_{lj}^{(r)}$ is defined as

$f_{lj}^{(r)} = \frac{\sum_{x_{il} = a_{l}^{(r)}} w_{ji}}{\sum_{i = 1}^{n} w_{ji}}$ (28) and $g_{lj}^{(r)}$ is defined as

$g_{lj}^{(r)} = \frac{\sum_{x_{il} = a_{l}^{(r)}} w_{ji}}{\sum_{x_{il} = a_{l}^{(r)}} \sum_{j = 1}^{k} w_{ji}}$ (29) In both cases, w_ji is the membership degree computed in the fuzzy k-modes clustering algorithm.

4.4 Summary of the proposed algorithm

The proposed k-modes or fuzzy k-modes clustering algorithm considers the different significance of each categorical attribute on clustering. Thus, the purpose of the proposed algorithm is to optimize the objective functions, which include attribute weights. The objective function of the proposed k-modes algorithm is defined as $F (W, Z, Λ) = \sum_{j = 1}^{k} \sum_{i = 1}^{n} w_{ji} \sum_{l = 1}^{d} λ_{l} d (z_{jl}, x_{il})$ (30) and that of the proposed fuzzy k-modes algorithm is defined as $F (W, Z, Λ) = \sum_{j = 1}^{k} \sum_{i = 1}^{n} w_{ji}^{e} \sum_{l = 1}^{d} λ_{l} d (z_{jl}, x_{il})$ (31) The clustering procedure is similar to that of the conventional k-modes or fuzzy k-modes clustering algorithms. In addition to the traditional procedures, the clustering procedure requires one more step to calculate the weights of the attributes. In this step, the proposed algorithm considers the distribution of categories of categorical variables within clusters and between clusters, which is a novel point of this algorithm. Finally, the proposed algorithm can be simplified in the following three steps.

Step 1: Fix $Z = \hat{Z} and Λ = \hat{Λ}$ , update W

Step 2: Fix $W = \hat{W} and Λ = \hat{Λ}$ , update Z

Step 3: Fix $W = \hat{W} and Z = \hat{Z}$ , update Λ

These steps are repeated until any terminal condition is fulfilled; terminal conditions generally include the convergence of Z, W, and Λ, or the reaching of the maximum iteration defined by a user in advance.

5 Experiments

5.1 Datasets

For experiments to evaluate the proposed algorithm, the six standard datasets obtained from the UCI Machine Learning Repository [28] were used. These datasets are introduced as follows.

Soybean data: This dataset has 47 data samples and 35 attributes. The class output is labeled as one of the four diseases, Diaporthe Stem Canker, Charcoal Rot, Phizoctonia Root Rot, and Phytophthora Rot.

Zoo data: This datasets consists of 101 instances and 15 categorical variables. The purpose of this dataset is to classify the type of animal based on characteristics. Each animal is classified into 7 different categories.

Horse colic data: Original dataset has 368 samples and 22 attributes; it is a binary classification problem that tries to determine whether a lesion of colic of a horse is surgical. However, some attributes have too many missing values and the 7 features are not categorical. Therefore, attributes with more than 100 missing values and numerical attributes are removed. In addition, rows with any missing values are also eliminated after removing certain features. Finally, 215 samples remain with 9 categorical attributes. Among them, the number of samples that requires surgical treatment is 134.

Heart disease data: This dataset has 303 instances with eight categorical and five numerical attributes generated at the Cleveland Clinic. It is a binary classification dataset with normal patients (164 objects) and heart patients (139 objects).

Credit approval data: It consists of 690 customers divided into two classes, negative (383 objects) and positive (307 objects), collected from credit card organizations. It has eight categorical and six numeric features. In this paper, only categorical attributes are selected for experiments.

Breast cancer data: It consists of 699 data objects and 9 categorical attributes. It has two clusters, benign (458 objects) and malignant (241 objects). This dataset was obtained from the University Medical Center, Institute of Oncology, Ljubljana, Yugoslavia.

The number of objects, categorical features, and clusters for the datasets are summarized in Table 2.

5.2 Similarity measure

Unlike numerical variables, the values of categorical variables represent different categories; thus, difference or distance in values is irrelevant. Therefore, dissimilarity measures for categorical variables are based on matching. If the number of matched categorical attributes of two objects increases, the two objects are more likely to be similar.

Dissimilarity is the opposite of similarity. This value increases when two objects are less similar. Usually, dissimilarity is defined as d (_xi, _xj) =1 - sim (_xi, _xj), which justifies the concept of complementarity in similarity and dissimilarity measures. Through this relation, the decision to one of the measures determines the remaining measure.

To improve the clustering performance, several studies have investigated new similarity measures to reflect the characteristics of categorical variables, such as Gower similarity [18], Eskin similarity [13], inverse occurrence frequency similarity [10], occurrence frequency similarity [4], Goodall similarity [17], and so on.

In the present paper, the similarity measure to calculate the dissimilarity between two objects is determined as Gower similarity. It is the most popular similarity measure for categorical variables. It has only a binary output, 0 or 1, depending on matching of an attribute [18]. $sim (x_{il}, x_{jl}) = {\begin{matrix} 1 & if x_{il} = x_{jl} \\ 0 & if x_{il} \neq x_{jl} \end{matrix}$ (32) In Gower similarity, when the attribute values of two objects are the same, dissimilarity is zero; otherwise, it is one. This similarity appears to be extremely simple; however, some studies reported that Gower similarity works effectively for real data and is sufficient in capturing relations among categorical features [4, 12].

5.3 Experimental setting

To ensure a fair comparison, the parameter setting for the experiments is determined in the following steps:

The number of clusters, k is set to the number of classes for each dataset.

Because clustering performance depends on the initial centroids of the clusters, initial centroids are randomly selected and the same procedures are repeated 100 times. In each iteration, the same initial centroids are used in the different clustering algorithms.

For fuzzy k-modes clustering, parameter e, controlling the fuzziness, should be set in advance; it also affects the performance of the clustering results. In several papers related to fuzzy k-modes clustering with categorical attributes [2 , 27], the clustering performance for categorical data with smaller e is usually better than that with larger e. Generally, the best clustering performance has been reported when e is 1.1. For this reason, e is set at 1.1.

Λ is initialized as (1, 1,. . . , 1).

To control the balance between within-cluster information and between-cluster information in the calculation of the weights, parameter c is changed. The effectiveness of c is tested during experiments.

5.4 Evaluation metrics

In the performance analysis, four widely used metrics were adopted to evaluate the results of the proposed clustering algorithm.

category utility function: The category utility (CU) function is a measure of the probability that two objects in the same cluster have the same attribute values and the probability that objects from different clusters have different attribute values. CU function is defined as $CU = \sum_{j = 1}^{k} \frac{n_{\cdot j}}{n} \sum_{l = 1}^{d} \sum_{r = 1}^{m_{l}} [P (a_{l}^{(r)} | C_{j})^{2} - P (a_{l}^{(r)})^{2}]$ (33) where $P (a_{l}^{(r)} | C_{j}) = n_{lj}^{(r)} / n_{\cdot j}$ and $P (a_{l}^{(r)}) = \sum_{j = 1}^{k} n_{lj}^{(r)} / n$ . The CU has larger value when $P (a_{l}^{(r)} | C_{j})^{2}$ much deviates from $P (a_{l}^{(r)})$ , which means that attributes’ values are inhomogenously distributed across clusters.

accuracy: The accuracy (AC) is an external criterion that takes advantage of true class labels to evaluate the performance of clustering. AC is defined as follows $AC = \frac{\sum_{i = 1}^{n} a_{i}}{n}$ (34) where a_i denotes the correctness of cluster assignment. The label of clusters is determined by the major class of objects in the cluster. If true output label of the object _xi is the same as the major class in the cluster to which _xi belongs, a_i is set to 1. Otherwise, a_i is set to 0.

adjusted Rand index: The adjusted Rand index (ARI) is an external performance measure, which means that it requires knowledge of the ground truth cluster assignments [25]. ARI is a function that measures the similarity of the two assignments, ignoring chances of normalization and permutation. To obtain ARI, the raw Rand index should be computed first; it is given by $RI = \frac{a + b}{C_{2}^{n}}$ (35) where $C_{2}^{n} = (\begin{matrix} n \\ k \end{matrix}) = \frac{n!}{k! (n - k)!}$ is the total number of possible pairs in the dataset without ordering, a is the number of pairs of elements that are in the same cluster in the ground truth assignment and the assignment from clustering and b is the number of pairs of elements that are in different sets in the ground truth assignment and the assignment from clustering. ARI accounts for the effect in which random label assignments cause a value close zero for RI and discount the expected RI, $𝔼 [RI]$ of random labeling. The ARI is defined as $ARI = \frac{RI - 𝔼 [RI]}{max RI - 𝔼 [RI]}$ (36)

partition entropy coefficient: The partition entropy (PE) coefficient is a validity index for fuzzy clustering. PE measures the fuzziness of the clustering results, and has a smaller value when the clustering result has less uncertainty. This metric is only computed for fuzzy algorithms. $PC = - \frac{1}{n} \sum_{j = 1}^{k} \sum_{i = 1}^{n} w_{ji} {log}_{2} w_{ji}$ (37)

5.5 Experimental results

In this paper, to prove the value of the proposed method, the k-modes clustering and fuzzy k-modes clustering algorithms are compared with the k-modes clustering algorithm combined with the proposed weighting method. The same experimental procedures with the same parameter setting are applied to the different clustering algorithms, with weights calculated using the entropy and the Gini impurity. The effectiveness of fuzziness in the calculation of weights is verified through experiments. For clarity, the clustering algorithms tested in this paper are denoted as follows: k-modes clustering as KM, k-modes clustering with the non-fuzzy weighting method as WKM, fuzzy k-modes clustering as FKM, fuzzy k-modes clustering with the non-fuzzy weighting method as WFKM, and fuzzy k-modes clustering with the fuzzy weighting method as FWFKM. All five clustering algorithms calculate the centroids of clusters in a fuzzy method reported in [27]. In the case of non-fuzzy k-modes clustering, the centroids of the clusters are represented by ratios of the categories of each attribute within the cluster.

In addition, the balancing parameter c is changed in the range of [0,1] with interval 0.1. Clustering performance is evaluated using four different metrics.

In Tables 3–4, the clustering results for the datasets are summarized. In each cell, the first number represents the average value for 100 runs; the second number is the standard deviation. Results from the clustering algorithms with the feature weighting are reported separately with respect to weightingmethods.

Based on the experimental results, in can be seen that fuzzy k-modes clustering generally outperforms k-modes clustering in all datasets and for all evaluation metrics except PE. In addition, common k-modes and fuzzy k-modes clustering algorithms can be improved to utilize the proposed methods, which calculate weights of categorical variables in terms of CU, AC, and ARI. After introducing weights for calculation of similarity, PE increases in some datasets depending on the weighting methods, which means that the membership degrees of objects become less certain. However, the membership degrees do not have a large effect on the final clustering results because each object is assigned to one of the clusters by calculating the maximum member degrees in actual situations. Between entropy and the Gini impurity, entropy usually provides a smaller PE, possibly because the same measure, entropy, is used to obtain weights.

In terms of standard deviation, the proposed algorithm reduces the standard deviation compared with original methods, which means that the proposed algorithm groups objects into stable clusters regardless of random initial centroids. This fact is an advantage in real-world applications because users do not need to apply algorithms to the same data several times to obtain improved clustering results.

In Tables 4, the best balancing parameter c, the average, and the standard deviation of the four evaluation metrics regardless of c are summarized. The average and standard deviation are calculated from 1,100 clustering results (11 different c × 100). The optimal value of c is different according to datasets and weighting methods. However, the average values of the evaluation metrics regardless of c degraded slightly from the optimum; the deviations are also not significant. In addition, the best c usually is not located in the center in the range of [0,1]; for most cases, it is close to 0 or 1. Therefore, selecting small c and large c, and selecting c based on CU or PE instead of applying several values of c within [0,1] is a good approach to save time. Moreover, for fuzzy k-modes clustering, PE is usually more correlated with AC and ARI with CU; thus, PE may need to be considered further to determine the appropriate c.

6 Conclusion

This paper proposed a new weighting method for categorical attributes to improve k-modes clustering results in both ordinal and fuzzy algorithms. The key concept of the proposed algorithm is to increase the certainty of the values of categorical attributes within the cluster. To measure this certainty, the entropy and the Gini impurity were introduced to weighting features. These two metrics have high values when attributes are not very useful to separate clusters; thus, weights are proportional to the subtraction of the entropy or the Gini impurity from 1. This method is simple and easy to implement as well as universal for categorical variables.

Experiments were systematically conducted to evaluate the performance of the proposed method with k-modes and fuzzy k-modes clustering algorithms. To this end, experiments were conducted over six different datasets; and four different evaluation metrics were used for comparison. The results of the experiments confirmed that the performance of the k-modes and fuzzy k-modes clustering algorithms was enhanced overall by introducing the proposed weighting method. For some datasets, PE increased with the introduction of weights, although the final clustering assignment was not much affected by PE. Other metrics, such as AC and ARI, related to cluster assignment, showed improved results in the proposed method. In addition, the best performance of the proposed algorithm was achieved when c > 0 for all the datasets, which proves that between-cluster information is helpful to calculate appropriate weights.

Even though the k-modes clustering algorithm with the proposed weighting method provides improved clustering results, selection of a balancing parameter c is important; however, in this paper, a rough guideline to select c was presented. Therefore, a more detailed analysis of c and the construction of guidelines to choose the optimal value of c should be performed in the future. In addition, the proposed algorithm can be extended to numerical attributes by introducing inhomogeneous measure for numerical features and can be applied to data with mixed attributes.

Footnotes

Acknowledgments

This study was financially supported by Seoul National University of Science & Technology.

References

Aranganayagi

and Thangavel

, Improved K-modes for categorical clustering using weighted dissimilarity measure, International Journal of Computer, Electrical, Automation, Control and Information Engineering 3(3) (2009), 182–188.

Bai

, Liang

, Dang

and Cao

, A novel fuzzy clustering algorithm with between-cluster information for categorical data, Fuzzy Sets and Systems 215 (2013), 55–73.

Barbara

, Li

and Couto

, COOLCAT: An Entropy-Based Algorithm for Categorical Clustering. International Conference on Information and Knowledge Management (CIKM’02), 2002, pp. 582–589.

Boriah

, Chandola

and Kumar

, Similarity measures for categorical data: A comparative evaluation. In Proceedings of the SIAM International Conference on Data Mining, SDM 2008, Atlanta, Georgia, USA, 2008, pp. 243–254.

Breiman

, Friedman

, Ohlsen

and Stone

, Classification and regression trees, Wadsworth International Group, Belmont, CA, 1984.

Cao

, Liang

, Li

and Zhao

, A weighting k-modes algorithm for subspace clustering of categorical data, Neurocomputing 108 (2013), 23–30.

Cesario

, Manco

and Ortale

, Top-down parameter-free clustering of high-dimensional categorical data, IEEE Transactions on Knowledge and Data Engineering 19(12) (2007), 1607–1624.

Chan

E.Y.

, Ching

W.K.

, Ng

M.K.

and Huang

J.Z.

, An optimization algorithm for clustering using weighted dissimilarity measures, Pattern Recognition 375 (2004), 943–952.

Chen

H.-L.

, Chuang

K.-T.

and Chen

M.-S.

, On data labeling for clustering categorical data, IEEE Transactions on Knowledge and Data Engineering 20(11) (2008), 1458–1472.

10.

Church

and Gale

, Inverse document frequency (idf): A measure of deviations from poisson. Natural Language Processing Using Very Large Corpora, 1999, pp. 121–130.

11.

De Soete

, Optimal variable weighting for ultrametric and additive tree clustering, Quality and Quantity 20(2-3) (1986), 169–180.

12.

dos Santos

T.R.

and Zárate

L.E.

, Categorical data clustering: What similarity measure to recommend? Expert Systems with Applications 42(3) (2015), 1247–1260.

13.

Eskin

, Arnold

, Prerau

, Portnoy

and Stolfo

, A geometric framework for unsupervised anomaly detection, Applications of Data Mining in Computer Security 3(40) (2002), 77–101.

14.

Ester

, Kriegel

H.P.

, Sander

and Xu

, A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Second International Conference on Knowledge Discovery and Data Mining, 1996, pp. 226–231.

15.

Frigui

and Nasraoui

, Unsupervised learning of prototypes and attribute weights, Pattern Recognition 37(3) (2004), 567–581.

16.

Ganti

, Gehrke

and Ramakrishnan

, CACTUS clustering categorical data using summaries. Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’99, 1999, pp. 73–83.

17.

Goodall

D.W.

, A new similarity index based on probability, Biometrics 22(4) (1966), 882–907.

18.

Gower

J.C.

, A general coefficient of similarity and some of its properties, Biometrics 27(4) (1971), 857–871.

19.

Graves

and Pedrycz

, Kernel-based fuzzy clustering and fuzzy clustering: A comparative experimental study, Fuzzy Sets and Systems 161(4) (2010), 522–543.

20.

Guha

, Rastogi

and Shim

, ROCK: A robust clustering algorithm for categorical attributes, Icde 512 (1999).

21.

and Tan

, A two-stage genetic algorithm for automatic clustering, Neurocomputing 81 (2012), 49–59.

22.

Huang

, A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining. Research Issues on Data Mining and Knowledge Discovery, 1997, pp. 1–8.

23.

Huang

, Extensions to the k-means algorithm for clustering large datasets with categorical values, Data Mining and Knowledge Discovery 2(3) (1998), 283–304.

24.

Huang

and Ng

M.K.

, A fuzzy k-modes algorithm for clustering categorical data, IEEE Transactions on Fuzzy Systems 7(4) (1999), 446–452.

25.

Hubert

and Arabie

, Comparing partitions, Journal of Classification 2(1) (1985), 193–218.

26.

J.H.

Jr.

Hierarchical grouping to optimize an objective function, Journal of the American Statistical Association 58(301) (1963), 236–244.

27.

Kim

D.W.

, Lee

K.H.

and Lee

, Fuzzy clustering of categorical data using fuzzy centroids, Pattern Recognition Letters 25(11) (2004), 1263–1271.

28.

Lichman

, UCI machine learning repository, 2013.

29.

Lloyd

, Least squares quantization in PCM, IEEE Transactions on Information Theory 28(2) (1982), 129–137.

30.

MacQueen

J.B.

, Some methods for classification and analysis of multivariate observations. 5th Berkeley Symposium on Mathematical Statistics and Probability 1967 1(233) (1967), 281–297.

31.

Makarenkov

and Legendre

, Optimal variable weighting for ultrametric and additive trees and K-means partitioning: Methods and software, Journal of Classification 18(2) (2001), 245–271.

32.

Road

and Jose

, Automatic Subspace Clustering Mining of High Dimensional Applications for Data, Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, 27, 1998, pp. 94–105.

33.

Sander

, Ester

, Kriegel

H.P.P.

and Xu

, Density-based clustering in spatial databases: The algorithm GDBSCAN and its applications, Data Mining and Knowledge 194 (1998) 169–194.

34.

Shannon

C.E.

, A mathematical theory of communication, Bell System Technical Journal 27(3) (1948), 379–423.

35.

Shi

and Malik

, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence 22(8) (2000), 888–905.