# A Global-Relationship Dissimilarity Measure for thek-Modes Clustering Algorithm

Authors: Hongfang Zhou; Yihui Zhang; Yibin Liu
Journal: Computational Intelligence and Neuroscience
 (2017)

---

## Abstract

Thek-modes clustering algorithm has been widely used to cluster categorical data. In this paper, we firstly analyzed thek-modes algorithm and its dissimilarity measure. Based on this, we then proposed a novel dissimilarity measure, which is named as GRD. GRD considers not only the relationships between the object and all cluster modes but also the differences of different attributes. Finally the experiments were made on four real data sets from UCI. And the corresponding results show that GRD achieves better performance than two existing dissimilarity measures used ink-modes and Cao’s algorithms.


---

## Body

## 1. Introduction

Clustering is an important technique in data mining, and its main task is to group the given data based on some similarity/dissimilarity measures [1]. Most clustering techniques use distances largely to measure the dissimilarity between different objects [2–4]. However, these methods work only on the data sets with numeric attributes, which limits their uses in solving categorical data clustering problems [5].Some researchers have made great efforts to quantize relationships among different categorical attributes. Guha et al. [6] proposed a hierarchical clustering method termed ROCK, which can measure the similarity between a pair of objects [7]. In ROCK, the number ofLink is computed as the number of common neighbors between two objects [8]. However, the following two deficiencies still exist: (1) two involved parameters (θ,k) must be assigned in advance and (2) the mass calculation is involved [9]. For these reasons, some researchers have generated some new algorithms like QROCK [10], DNNS [11], and GE-ROCK [12] to modify or improve the ROCK algorithm. To remove the numeric-only limitation ofk-means algorithm, Huang et al. [13, 14] proposed thek-modes algorithm, which extends thek-means algorithm by using (1) a simple matching dissimilarity measure for categorical attributes; (2) modes in place of means for clustering; and (3) a frequency-related strategy to update modes to minimize the clustering costs [15]. In fact, the idea of simple matching has been used in many clustering algorithms, such as fuzzyk-modes algorithm [16], fuzzyk-modes algorithm with fuzzy centroid [17], andk-prototype algorithm [14]. However, simple matching often results in some low intradissimilarity clusters [18] and disregards of the dissimilarity hidden between the categorical values [19].In this paper, a Global-Relationship Dissimilarity (GRD) measure for thek-modes clustering algorithm is proposed. This dissimilarity measure considers not only the relationships between the object and all cluster modes but also the differences of various attributes instead of simple matching. The clustering effectiveness ofk-modes based on GRD (KBGRD) is demonstrated on four standard data sets from the UCI Machine Learning Repository [20].The remainder of this paper is organized as follows: a detailed review of the dissimilarity measure used ink-modes is presented and analyzed in Section 2. In Section 3, the new dissimilarity measure GRD is proposed. Section 4 describes the details of KBGRD algorithm. Section 5 illustrates the performance and stability of KBGRD. Finally, a concluding remark is given in Section 6.


## 2. Related Works

### 2.1. Categorical Data

As is known to all, the structural data can be stored in a table, where each row represents a fact about an object. And the practical data usually contains categorical attributes [21]. We firstly define the term “data set” [22].Definition 1 (data set).
A data set information system can be expressed as a quadrupleIS={U,A,V,f}, which is satisfied with(1)
U={x1,x2,…,xn} is a nonempty set of n data objects, which is named as a universe;(2)
A={a1,a2,…,am} is a nonempty set of m categorical attributes;(3)
V is the union of all attribute domains, that is, V=⋃j=1mVaj, where Vaj={aj(1),aj(2),…,aj(nj)} is the value domain of attribute aj, and it is finite and unordered; nj is the number of categories of attribute aj for 1≤j≤m;(4)
f is a mapping function U×A→V which can be formally expressed as (∀x)(∀y)((x∈U)∧(y∈A)→f(x,y)∈Vaj)(j=1,2,…,m).


### 2.2.k-Modes Dissimilarity Measure

Thek-modes clustering algorithm is an improvement of thek-means algorithm [4] by using a simple dissimilarity measure for categorical data. And it adopts a frequency-related strategy to update modes in the clustering to minimize the clustering costs. These extensions have excluded the numeric-only limitation existed ink-means algorithm and enable the clustering process to be used on large-size categorical data sets from real world database [22].Definition 2.
LetIS={U,A,V,f} be a categorical data set information system which is defined in Definition 1 and aj∈A. For any object xi∈U and cluster mode zl for 1≤l≤k, Dis0(zl,xi) is the simple matching dissimilarity measure between object xi and the mode zl of the lth cluster which is defined as follows:(1)Dis0zl,xi=∑j=1mδajzl,xiIn (1), δaj(zl,xi) can be expressed as δajzl,xi={1,f(zl,aj)≠f(xi,aj);0,f(zl,aj)=f(xi,aj)}.There are nine objects{x1,x2,…,x9} with four attributes {A1,A2,A3,A4} and three initial cluster modes as shown in Table 1. For determining the appropriate cluster of x1, it is required to compute the dissimilarity of x1 and the three cluster modes. According to (1), Dis0(c1,x1)=Dis0(c2,x1)=Dis0(c3,x1)=1. Therefore, it is impossible to determine exactly to which cluster the object x1 should be assigned.Table 1
An artificial data set.
Objects
A
1
A
2
A
3
A
4
x
1
A
B
A
E
x
2
A
A
B
D
x
3
C
A
A
E
Cluster 1 (c1)
A
A
A
E
x
4
A
B
B
E
x
5
B
A
C
E
x
6
A
B
C
E
Cluster 2 (c2)
A
B
C
E
x
7
A
A
A
E
x
8
D
C
B
E
x
9
C
C
A
E
Cluster 3 (c3)
A
C
A
EThe dissimilarity between an object and a cluster mode should consider the relationships between the object and all cluster modes as well as the differences of various attributes. When thek-modes dissimilarity measure is computing dissimilarity of a certain attribute, it only simply matches this object with this mode and ignores the differences of various attributes. Such as attribute “A4” in Table 1, almost all of objects and cluster modes is “E”; “A4” should contribute more to dissimilarity than other attributes. However, thek-modes dissimilarity treats all attributes equally.


## 2.1. Categorical Data

As is known to all, the structural data can be stored in a table, where each row represents a fact about an object. And the practical data usually contains categorical attributes [21]. We firstly define the term “data set” [22].Definition 1 (data set).
A data set information system can be expressed as a quadrupleIS={U,A,V,f}, which is satisfied with(1)
U={x1,x2,…,xn} is a nonempty set of n data objects, which is named as a universe;(2)
A={a1,a2,…,am} is a nonempty set of m categorical attributes;(3)
V is the union of all attribute domains, that is, V=⋃j=1mVaj, where Vaj={aj(1),aj(2),…,aj(nj)} is the value domain of attribute aj, and it is finite and unordered; nj is the number of categories of attribute aj for 1≤j≤m;(4)
f is a mapping function U×A→V which can be formally expressed as (∀x)(∀y)((x∈U)∧(y∈A)→f(x,y)∈Vaj)(j=1,2,…,m).


## 2.2.k-Modes Dissimilarity Measure

Thek-modes clustering algorithm is an improvement of thek-means algorithm [4] by using a simple dissimilarity measure for categorical data. And it adopts a frequency-related strategy to update modes in the clustering to minimize the clustering costs. These extensions have excluded the numeric-only limitation existed ink-means algorithm and enable the clustering process to be used on large-size categorical data sets from real world database [22].Definition 2.
LetIS={U,A,V,f} be a categorical data set information system which is defined in Definition 1 and aj∈A. For any object xi∈U and cluster mode zl for 1≤l≤k, Dis0(zl,xi) is the simple matching dissimilarity measure between object xi and the mode zl of the lth cluster which is defined as follows:(1)Dis0zl,xi=∑j=1mδajzl,xiIn (1), δaj(zl,xi) can be expressed as δajzl,xi={1,f(zl,aj)≠f(xi,aj);0,f(zl,aj)=f(xi,aj)}.There are nine objects{x1,x2,…,x9} with four attributes {A1,A2,A3,A4} and three initial cluster modes as shown in Table 1. For determining the appropriate cluster of x1, it is required to compute the dissimilarity of x1 and the three cluster modes. According to (1), Dis0(c1,x1)=Dis0(c2,x1)=Dis0(c3,x1)=1. Therefore, it is impossible to determine exactly to which cluster the object x1 should be assigned.Table 1
An artificial data set.
Objects
A
1
A
2
A
3
A
4
x
1
A
B
A
E
x
2
A
A
B
D
x
3
C
A
A
E
Cluster 1 (c1)
A
A
A
E
x
4
A
B
B
E
x
5
B
A
C
E
x
6
A
B
C
E
Cluster 2 (c2)
A
B
C
E
x
7
A
A
A
E
x
8
D
C
B
E
x
9
C
C
A
E
Cluster 3 (c3)
A
C
A
EThe dissimilarity between an object and a cluster mode should consider the relationships between the object and all cluster modes as well as the differences of various attributes. When thek-modes dissimilarity measure is computing dissimilarity of a certain attribute, it only simply matches this object with this mode and ignores the differences of various attributes. Such as attribute “A4” in Table 1, almost all of objects and cluster modes is “E”; “A4” should contribute more to dissimilarity than other attributes. However, thek-modes dissimilarity treats all attributes equally.


## 3. Global-Relationship Dissimilarity Measure

Definition 3.
LetIS={U,A,V,f} be a categorical data set information system which is defined in Definition 1 and aj∈A. For any object xi∈U and cluster mode zl for 1≤l≤k, Dis(zl,xi) is the new dissimilarity measure between object xi and the mode zl of the lth cluster which is defined as (2)Diszl,xi=1-Simzl,xim.In (2), m is the dimension number of data set and the similarity function Sim(zl,xi) is defined as follows:(3)Simzl,xi=∑j=1mφajzl,xi,subject to(4)φajzl,xi=1-S-1k,fzl,aj=fxi,aj0,fzl,aj≠fxi,aj,where k is the number of cluster modes, and(5)S=∑l=1ksajzl,xi;here saj(zl,xi) is satisfied with(6)sajzl,xi=1,fzl,aj=fxi,aj0,fzl,aj≠fxi,aj.As shown in Table1, it is required to compute the dissimilarity of x1 with three cluster modes for determining which cluster x1 should be assigned to. According to (2)–(6), the following three ones can be got:(1)
Dis(c1,x1)=1-1/4(1-3-1/3+0+1-2-1/3+1-3-1/3)=8/12.(2)
Dis(c2,x1)=1-1/4(1-3-1/3+1-1-1/3+0+1-3-1/3)=7/12.(3)
Dis(c3,x1)=1-1/4(1-3-1/3+0+1-2-1/3+1-3-1/3)=8/12.Hence, x1 can be assigned to cluster “2” definitely.


## 4. KBGRD Algorithm

In this section, we give the concrete procedure of thek-modes based on GRD (KBGRD) algorithm. In addition, the computational complexity of KBGRD is analyzed.


### 4.1. KBGRD Algorithm Description

Definition 4.
LetIS={U,A,V,f} be a categorical data set information system which is defined in Definition 1 and aj∈A. Thek-modes algorithm uses thek-means paradigm to cluster categorical data. The objective function of thek-modes algorithm is defined as follows:(7)FW,Z=∑l=1k∑i=1nwliDiszl,xi.In (7), wli∈0,1,1≤l≤k,1≤i≤n;∑l=1kwli=1,1≤i≤n;0<∑i=1nwli<n,1≤l≤k. Here k(≤n) is a known cluster number; W=[wli] is ak-by-n{0,1} matrix; wli is a binary variable and indicates whether object xi belongs to the lth cluster; wli=1 if xi belongs to the lth cluster and 0 otherwise; Z=[z1,z2,…,zk]; and zl is the lth cluster mode with categorical attributes a1,a2,…,am.


### 4.2. Update and Convergence Analysis

The steps of the KBGRD algorithm are presented below. HereZ(t) and W(t) denote cluster modes and membership matrix at tth iteration, respectively.(1)
Randomly selectk distinct objects from U as initial mode Z(1)=[z1,z2,…,zk]. Determine W(1) such that F(W(1),Z(1)) is minimized according to (8). Set t=1.(2)
DetermineZ(t+1) such that F(W(t),Z(t+1)) is minimized according to (9). If F(W(t),Z(t+1))==F(W(t),Z(t)), then stop; otherwise, go to step (3).(3)
DetermineW(t+1) such that F(W(t+1),Z(t+1)) is minimized according to (8). If F(W(t+1),Z(t+1))==F(W(t),Z(t+1)), then stop; otherwise, set t=t+1 and go to step (2).In each iteration,W and Z are updated by the following formulae.WhenZ is given, W is updated by (8) for 1≤i≤n and 1≤l≤k.(8)wli=1,Disz^l,xi≤Disz^h,xi,1≤h≤k0,otherwise.And whenW is given, Z is updated as follows:(9)fzl,aj=ajr∈Vaj,where ∑i=1,xij=aj(r)nwliφaj(zl,xi)≥∑i=1,xij=aj(h)nwliφaj(zl,xi), 1≤h≤nj. Here, Vaj={aj1,aj2,…,aj(nj)}; nj is the number of categorical of attribute aj for 1≤j≤m.Now we consider the convergence of the KBGRD algorithm.Theorem 5.
F
(
W
,
Z
^
) is minimized when Z=Z^ and W is updated by (8).Proof.
For a givenZ, we have F(W,Z^)=∑l=1k∑i=1nwliDis(zl,xi). The updating method of W is computing the minimized dissimilarity between objects and modes according to (8), and the dissimilarities of objects and modes are independent. So W is updated by (8) such that F(W,Z^) is minimized.Theorem 6.
F
(
W
^
,
Z
) is minimized when W=W^ and Z is updated by (9).Proof.
For a givenW, we have(10)FW^,Z=∑l=1k∑i=1nwliDiszl,xi=∑l=1k∑i=1nwli1-1mSimzl,xi=∑l=1k∑i=1nwli-1m∑l=1k∑i=1nwliSimzl,xi=∑l=1k∑i=1nwli-1m∑l=1k∑i=1n∑j=1mwliφajzl,xi=∑l=1k∑i=1nwli-1m∑l=1k∑j=1m∑i=1nwliφajzl,xi=∑l=1k∑i=1nwli-1m∑l=1k∑j=1mϕli,where ϕli=∑i=1nwliφaj(zl,xi). Note that all inner sums ϕli are nonnegative and independent. Then minimizing F(W^,Z) is equivalent to maximizing each inner sum. When zl=aj(r), according to (9), ϕli is maximized. So Z is updated by (9) such that F(W^,Z) is minimized.Theorem 7.
The KBGRD algorithm converges in a finite number of iterations.Proof.
Firstly, we note that there are only a finite number (N=∏j=1mnj) of potential cluster mode. There are kNpossible kinds for k cluster modes; it is a finite number too.
Secondly, each possible mode appears at most once in the iteration process of KBGRD algorithm. If not, there existt1,t2 (t1<t2) such that Z(t1)=Z(t2). According to Theorem 6, a given Z can obtain a certain W, that is, Z(t1)⇒W(t1), Z(t2)⇒W(t2). When Z(t1)=Z(t2), we have W(t1)=W(t2), that is, in the iteration of algorithm, occurring F(W(t1),Z(t1))=F(W(t1),Z(t2))=F(W(t2),Z(t2)) at t1<t2. However, if F(W(t),Z(t+1))=F(W(t),Z(t)) or (W(t+1),Z(t+1))=F(W(t),Z(t+1)), algorithm is stopped according to steps (2) and (3) of the KBGRD algorithm, that is, F(W(t1),Z(t1))=F(W(t1),Z(t2))=F(W(t2),Z(t2)) never occurs.
So the KBGRD algorithm converges in a finite number of iterations.


### 4.3. Pseudocodes and Complexity Analysis

The pseudocodes of KBGRD algorithm are presented in Pseudocode1.Pseudocode 1:Pseudocodes of KBGRD algorithm.
Input: data set U and initial cluster number k;
Output: clusters.
Sub function Cluster(U, modes)
Begin:
(1)for  l = 0 to k//k is the number of clusters.
(2)for  i = 1 to n//n is the number of objects.
(3)  CalculatingDis(cl,xi) according to Eqs. (2)–(6);
(4)end for
(5)end for
(6)if (Dis(cl,xi)≤Dis(ch,xi)(0≤h≤k))
(7)   Classifyith object xi into into lth cluster;
End
Sub function Fun()
Begin:
(1)for  l = 0 to k//k is the number of clusters.
(2)for  i = 1 to n//n is the number of objects.
(3)    Calculating SumDissimilarity according to Eq. (7);
(4)return SumDissimilarity;
end
Main function
Begin:
(1) Randomly choosek distinct objects x1,x2,…,xk as initial modes from U;
(2) Cluster(U, modes);
(3) newDissimilarity = Fun();// calculating the value of F(W,Z).
(4)Do
(5)  oldDissimilarity = newDissimilarity;
(6)  Update modes according to Eq. (9);
(7)  Cluster(U, modes);
(8)  newDissimilarity = Fun();
(9)whilenewDissimilarity != oldDissimilarity;
EndThe major function of subfunction Cluster() is computing the dissimilarity between object and cluster mode and classifying the objects into the clusters whose dissimilarity is the minimum. The function of subfunction Fun() is computing the value of objective function.In fact, main function is a controller, which controls the iterations of algorithm. We first choosek distinct objects as initial modes. Line 2 is the initialization of cluster; Line 3 computes original cluster result and “new Dissimilarity.” Lines 4–9 are to iteratively update modes and clusters. And when “new Dissimilarity” is invariant, the iteration stops.Referring to the pseudocodes as shown in Pseudocode1, the computational complexity of KBGRD algorithm is analyzed as follows. We only consider the major computational steps.We firstly consider the computational complexity of two subfunctions. The computational complexity for computing the dissimilarity isO(k·n·m), where k is the number of modes,n is the number of objects in data set, and m is the dimension of data set. The computational complexity for assigning the ith object into thelth cluster is O(k·n). So the computational complexity for updating all clusters is O(k·n·(m+1)), that is, O(k·n·m). The computational complexity of computing objective function is O(k·n·m).Suppose that the iteration time ist and the whole computational cost of KBGRD algorithm is t(O(k·n·m)+O(k·n·m))=2O(t·k·n·m), that is, O(t·k·n·m). This shows that the computational cost is linearly scalable with the number of objects, the number of attributes, and the number of clusters.


## 4.1. KBGRD Algorithm Description

Definition 4.
LetIS={U,A,V,f} be a categorical data set information system which is defined in Definition 1 and aj∈A. Thek-modes algorithm uses thek-means paradigm to cluster categorical data. The objective function of thek-modes algorithm is defined as follows:(7)FW,Z=∑l=1k∑i=1nwliDiszl,xi.In (7), wli∈0,1,1≤l≤k,1≤i≤n;∑l=1kwli=1,1≤i≤n;0<∑i=1nwli<n,1≤l≤k. Here k(≤n) is a known cluster number; W=[wli] is ak-by-n{0,1} matrix; wli is a binary variable and indicates whether object xi belongs to the lth cluster; wli=1 if xi belongs to the lth cluster and 0 otherwise; Z=[z1,z2,…,zk]; and zl is the lth cluster mode with categorical attributes a1,a2,…,am.


## 4.2. Update and Convergence Analysis

The steps of the KBGRD algorithm are presented below. HereZ(t) and W(t) denote cluster modes and membership matrix at tth iteration, respectively.(1)
Randomly selectk distinct objects from U as initial mode Z(1)=[z1,z2,…,zk]. Determine W(1) such that F(W(1),Z(1)) is minimized according to (8). Set t=1.(2)
DetermineZ(t+1) such that F(W(t),Z(t+1)) is minimized according to (9). If F(W(t),Z(t+1))==F(W(t),Z(t)), then stop; otherwise, go to step (3).(3)
DetermineW(t+1) such that F(W(t+1),Z(t+1)) is minimized according to (8). If F(W(t+1),Z(t+1))==F(W(t),Z(t+1)), then stop; otherwise, set t=t+1 and go to step (2).In each iteration,W and Z are updated by the following formulae.WhenZ is given, W is updated by (8) for 1≤i≤n and 1≤l≤k.(8)wli=1,Disz^l,xi≤Disz^h,xi,1≤h≤k0,otherwise.And whenW is given, Z is updated as follows:(9)fzl,aj=ajr∈Vaj,where ∑i=1,xij=aj(r)nwliφaj(zl,xi)≥∑i=1,xij=aj(h)nwliφaj(zl,xi), 1≤h≤nj. Here, Vaj={aj1,aj2,…,aj(nj)}; nj is the number of categorical of attribute aj for 1≤j≤m.Now we consider the convergence of the KBGRD algorithm.Theorem 5.
F
(
W
,
Z
^
) is minimized when Z=Z^ and W is updated by (8).Proof.
For a givenZ, we have F(W,Z^)=∑l=1k∑i=1nwliDis(zl,xi). The updating method of W is computing the minimized dissimilarity between objects and modes according to (8), and the dissimilarities of objects and modes are independent. So W is updated by (8) such that F(W,Z^) is minimized.Theorem 6.
F
(
W
^
,
Z
) is minimized when W=W^ and Z is updated by (9).Proof.
For a givenW, we have(10)FW^,Z=∑l=1k∑i=1nwliDiszl,xi=∑l=1k∑i=1nwli1-1mSimzl,xi=∑l=1k∑i=1nwli-1m∑l=1k∑i=1nwliSimzl,xi=∑l=1k∑i=1nwli-1m∑l=1k∑i=1n∑j=1mwliφajzl,xi=∑l=1k∑i=1nwli-1m∑l=1k∑j=1m∑i=1nwliφajzl,xi=∑l=1k∑i=1nwli-1m∑l=1k∑j=1mϕli,where ϕli=∑i=1nwliφaj(zl,xi). Note that all inner sums ϕli are nonnegative and independent. Then minimizing F(W^,Z) is equivalent to maximizing each inner sum. When zl=aj(r), according to (9), ϕli is maximized. So Z is updated by (9) such that F(W^,Z) is minimized.Theorem 7.
The KBGRD algorithm converges in a finite number of iterations.Proof.
Firstly, we note that there are only a finite number (N=∏j=1mnj) of potential cluster mode. There are kNpossible kinds for k cluster modes; it is a finite number too.
Secondly, each possible mode appears at most once in the iteration process of KBGRD algorithm. If not, there existt1,t2 (t1<t2) such that Z(t1)=Z(t2). According to Theorem 6, a given Z can obtain a certain W, that is, Z(t1)⇒W(t1), Z(t2)⇒W(t2). When Z(t1)=Z(t2), we have W(t1)=W(t2), that is, in the iteration of algorithm, occurring F(W(t1),Z(t1))=F(W(t1),Z(t2))=F(W(t2),Z(t2)) at t1<t2. However, if F(W(t),Z(t+1))=F(W(t),Z(t)) or (W(t+1),Z(t+1))=F(W(t),Z(t+1)), algorithm is stopped according to steps (2) and (3) of the KBGRD algorithm, that is, F(W(t1),Z(t1))=F(W(t1),Z(t2))=F(W(t2),Z(t2)) never occurs.
So the KBGRD algorithm converges in a finite number of iterations.


## 4.3. Pseudocodes and Complexity Analysis

The pseudocodes of KBGRD algorithm are presented in Pseudocode1.Pseudocode 1:Pseudocodes of KBGRD algorithm.
Input: data set U and initial cluster number k;
Output: clusters.
Sub function Cluster(U, modes)
Begin:
(1)for  l = 0 to k//k is the number of clusters.
(2)for  i = 1 to n//n is the number of objects.
(3)  CalculatingDis(cl,xi) according to Eqs. (2)–(6);
(4)end for
(5)end for
(6)if (Dis(cl,xi)≤Dis(ch,xi)(0≤h≤k))
(7)   Classifyith object xi into into lth cluster;
End
Sub function Fun()
Begin:
(1)for  l = 0 to k//k is the number of clusters.
(2)for  i = 1 to n//n is the number of objects.
(3)    Calculating SumDissimilarity according to Eq. (7);
(4)return SumDissimilarity;
end
Main function
Begin:
(1) Randomly choosek distinct objects x1,x2,…,xk as initial modes from U;
(2) Cluster(U, modes);
(3) newDissimilarity = Fun();// calculating the value of F(W,Z).
(4)Do
(5)  oldDissimilarity = newDissimilarity;
(6)  Update modes according to Eq. (9);
(7)  Cluster(U, modes);
(8)  newDissimilarity = Fun();
(9)whilenewDissimilarity != oldDissimilarity;
EndThe major function of subfunction Cluster() is computing the dissimilarity between object and cluster mode and classifying the objects into the clusters whose dissimilarity is the minimum. The function of subfunction Fun() is computing the value of objective function.In fact, main function is a controller, which controls the iterations of algorithm. We first choosek distinct objects as initial modes. Line 2 is the initialization of cluster; Line 3 computes original cluster result and “new Dissimilarity.” Lines 4–9 are to iteratively update modes and clusters. And when “new Dissimilarity” is invariant, the iteration stops.Referring to the pseudocodes as shown in Pseudocode1, the computational complexity of KBGRD algorithm is analyzed as follows. We only consider the major computational steps.We firstly consider the computational complexity of two subfunctions. The computational complexity for computing the dissimilarity isO(k·n·m), where k is the number of modes,n is the number of objects in data set, and m is the dimension of data set. The computational complexity for assigning the ith object into thelth cluster is O(k·n). So the computational complexity for updating all clusters is O(k·n·(m+1)), that is, O(k·n·m). The computational complexity of computing objective function is O(k·n·m).Suppose that the iteration time ist and the whole computational cost of KBGRD algorithm is t(O(k·n·m)+O(k·n·m))=2O(t·k·n·m), that is, O(t·k·n·m). This shows that the computational cost is linearly scalable with the number of objects, the number of attributes, and the number of clusters.


## 5. Experimental Analysis

### 5.1. Experimental Environment and Evaluation Indexes

The experiments are conducted on a PC with an Intel i3 processor and 4 G byte memory running the Windows 7 operating system. All algorithms are coded by JAVA on Eclipse.To evaluate the efficiency of clustering algorithm, the evaluation indexesAccuracy (AC) andRandIndex are employed in the experiments.LetC={C1,C2,C3} be the set of three classes in the data set and C′={C1′,C2′,C3′} be the set of three clusters generated by the clustering algorithm. Given a pair of objects (Xi,Xj) in the data set, we refer to it as(1)
a if both objects belong to the same cluster in C and the same cluster in C′;(2)
b if the two objects belong to the same cluster in C and two different clusters in C′;(3)
c if the two objects belong to two different clusters in C and to the same cluster in C′;(4)
d if both objects belong to two different clusters in C and two different clusters in C′.Let S1, S2, S3, and S4 be the number ofa,b,c, andd,RandIndex [23] is defined as follows:(11)RandIndex=S1+S4S1+S2+S3+S4.Accuracy (AC) is defined as follows:(12)AC=∑i=1kain,where k is the number of clusters,n is the number of objects, and ai is the number of objects that are correctly assigned to the cluster Ci (1≤i≤k).Four categorical data sets from the UCI Machine Learning Repository are used to evaluate the clustering performance, including QSAR Biodegradation (QSAR), Chess, Mushroom, and Nursery. The relative information about the data sets is tabulated in Table2.Table 2
Data sets.
Data set
Attribute characteristics
#of data objects
# of attributes
# of class
Missing values
QSAR
Integer/real
1055
41
2
No
Chess
Categorical
3196
36
2
No
Mushroom
Categorical
8142
22
2
Yes (very few)
Nursery
Categorical
12960
8
5
No


### 5.2. Experimental Results and Analysis

In the experiments, we compare KBGRD algorithm with the originalk-modes and Cao’s algorithm [24]. Three algorithms are sequentially run on all data sets. Each algorithm requires the number of modes(ClusterNum) as an input parameter. We randomly select distinctClusterNum objects as initial cluster modes. The number of iteration of all algorithms is no more than 500.Note that there are very few missing values in the Mushroom data set; we use optimal completion strategy to deal with missing values. In the optimal completion strategy, the missing values in data set are viewed as additional variables [25, 26].Firstly, we setClusterNum as the classes’ number of the data set. The averageRandIndex of ten times’ experiments on four data sets for three algorithms is summarized in Table 3. The averageAC of ten times’ experiments on four data sets for three algorithms is summarized in Table 4. As shown in Tables 3 and 4, KBGRD achieves the highestRandIndex andAC. That is, it performs better than other algorithms under the same conditions.Table 3
AverageRandIndex on four data sets for three algorithms.
QSAR
Chess
Mushroom
Nursery
k-modes
0.513
0.5102
0.5101
0.6908
Cao’s
0.5106
0.5136
0.5251
0.7895
KBGRD
0.5153
0.5229
0.5543
0.7933Table 4
Average AC on four data sets for three algorithms.
QSAR
Chess
Mushroom
Nursery
k-modes
0.5820
0.5720
0.5701
0.4786
Cao’s
0.5944
0.5432
0.5895
0.5897
KBGRD
0.6042
0.6073
0.6634
0.5938In real world applications, the number of initial cluster modes is unknown. We evaluated clustering stability by setting differentClusterNum (10, 15, 20, 25, 30, and 35) for each data set and usedRandIndex to evaluate clustering results. The averageRandIndex of ten times’ experiments on four data sets for three algorithms is summarized in Tables 5–8. And the last column shows the average clusteringRandIndex of each algorithm on sixClusterNum. As shown in Tables 5–8, KBGRD achieves the highestRandIndex. That is to say, it performs better than other algorithms on four data sets. Additionally, KBGRD has the highest stability compared with other algorithms.Table 5
AverageRandIndex of three algorithms on QSAR data set.
10
15
20
25
30
35
Average
k-modes
0.4613
0.4608
0.4611
0.4596
0.4603
0.4584
0.4603
Cao’s
0.4650
0.4610
0.4625
0.4608
0.4611
0.4593
0.4616
KBGRD
0.4658
0.4634
0.4628
0.4612
0.4620
0.4605
0.4626Table 6
AverageRandIndex of three algorithms on Chess data set.
10
15
20
25
30
35
Average
k-modes
0.5016
0.5011
0.5008
0.5024
0.5032
0.5027
0.5020
Cao’s
0.5041
0.5023
0.5014
0.5064
0.5045
0.5044
0.5039
KBGRD
0.5060
0.5090
0.5073
0.5072
0.5070
0.5075
0.5074Table 7
AverageRandIndex of three algorithms on Mushroom data set.
10
15
20
25
30
35
Average
k-modes
0.5771
0.5641
0.5611
0.5622
0.5443
0.5404
0.5582
Cao’s
0.5925
0.5644
0.5679
0.5790
0.5558
0.5638
0.5706
KBGRD
0.5932
0.5648
0.5731
0.5834
0.5678
0.5730
0.5759Table 8
AverageRandIndex of three algorithms on Nursery data set.
10
15
20
25
30
35
Average
k-modes
0.6839
0.7061
0.6963
0.6875
0.6815
0.6942
0.6916
Cao’s
0.7188
0.7071
0.6956
0.6989
0.6847
0.6982
0.7006
KBGRD
0.7195
0.7073
0.6967
0.7022
0.6957
0.6988
0.7034


## 5.1. Experimental Environment and Evaluation Indexes

The experiments are conducted on a PC with an Intel i3 processor and 4 G byte memory running the Windows 7 operating system. All algorithms are coded by JAVA on Eclipse.To evaluate the efficiency of clustering algorithm, the evaluation indexesAccuracy (AC) andRandIndex are employed in the experiments.LetC={C1,C2,C3} be the set of three classes in the data set and C′={C1′,C2′,C3′} be the set of three clusters generated by the clustering algorithm. Given a pair of objects (Xi,Xj) in the data set, we refer to it as(1)
a if both objects belong to the same cluster in C and the same cluster in C′;(2)
b if the two objects belong to the same cluster in C and two different clusters in C′;(3)
c if the two objects belong to two different clusters in C and to the same cluster in C′;(4)
d if both objects belong to two different clusters in C and two different clusters in C′.Let S1, S2, S3, and S4 be the number ofa,b,c, andd,RandIndex [23] is defined as follows:(11)RandIndex=S1+S4S1+S2+S3+S4.Accuracy (AC) is defined as follows:(12)AC=∑i=1kain,where k is the number of clusters,n is the number of objects, and ai is the number of objects that are correctly assigned to the cluster Ci (1≤i≤k).Four categorical data sets from the UCI Machine Learning Repository are used to evaluate the clustering performance, including QSAR Biodegradation (QSAR), Chess, Mushroom, and Nursery. The relative information about the data sets is tabulated in Table2.Table 2
Data sets.
Data set
Attribute characteristics
#of data objects
# of attributes
# of class
Missing values
QSAR
Integer/real
1055
41
2
No
Chess
Categorical
3196
36
2
No
Mushroom
Categorical
8142
22
2
Yes (very few)
Nursery
Categorical
12960
8
5
No


## 5.2. Experimental Results and Analysis

In the experiments, we compare KBGRD algorithm with the originalk-modes and Cao’s algorithm [24]. Three algorithms are sequentially run on all data sets. Each algorithm requires the number of modes(ClusterNum) as an input parameter. We randomly select distinctClusterNum objects as initial cluster modes. The number of iteration of all algorithms is no more than 500.Note that there are very few missing values in the Mushroom data set; we use optimal completion strategy to deal with missing values. In the optimal completion strategy, the missing values in data set are viewed as additional variables [25, 26].Firstly, we setClusterNum as the classes’ number of the data set. The averageRandIndex of ten times’ experiments on four data sets for three algorithms is summarized in Table 3. The averageAC of ten times’ experiments on four data sets for three algorithms is summarized in Table 4. As shown in Tables 3 and 4, KBGRD achieves the highestRandIndex andAC. That is, it performs better than other algorithms under the same conditions.Table 3
AverageRandIndex on four data sets for three algorithms.
QSAR
Chess
Mushroom
Nursery
k-modes
0.513
0.5102
0.5101
0.6908
Cao’s
0.5106
0.5136
0.5251
0.7895
KBGRD
0.5153
0.5229
0.5543
0.7933Table 4
Average AC on four data sets for three algorithms.
QSAR
Chess
Mushroom
Nursery
k-modes
0.5820
0.5720
0.5701
0.4786
Cao’s
0.5944
0.5432
0.5895
0.5897
KBGRD
0.6042
0.6073
0.6634
0.5938In real world applications, the number of initial cluster modes is unknown. We evaluated clustering stability by setting differentClusterNum (10, 15, 20, 25, 30, and 35) for each data set and usedRandIndex to evaluate clustering results. The averageRandIndex of ten times’ experiments on four data sets for three algorithms is summarized in Tables 5–8. And the last column shows the average clusteringRandIndex of each algorithm on sixClusterNum. As shown in Tables 5–8, KBGRD achieves the highestRandIndex. That is to say, it performs better than other algorithms on four data sets. Additionally, KBGRD has the highest stability compared with other algorithms.Table 5
AverageRandIndex of three algorithms on QSAR data set.
10
15
20
25
30
35
Average
k-modes
0.4613
0.4608
0.4611
0.4596
0.4603
0.4584
0.4603
Cao’s
0.4650
0.4610
0.4625
0.4608
0.4611
0.4593
0.4616
KBGRD
0.4658
0.4634
0.4628
0.4612
0.4620
0.4605
0.4626Table 6
AverageRandIndex of three algorithms on Chess data set.
10
15
20
25
30
35
Average
k-modes
0.5016
0.5011
0.5008
0.5024
0.5032
0.5027
0.5020
Cao’s
0.5041
0.5023
0.5014
0.5064
0.5045
0.5044
0.5039
KBGRD
0.5060
0.5090
0.5073
0.5072
0.5070
0.5075
0.5074Table 7
AverageRandIndex of three algorithms on Mushroom data set.
10
15
20
25
30
35
Average
k-modes
0.5771
0.5641
0.5611
0.5622
0.5443
0.5404
0.5582
Cao’s
0.5925
0.5644
0.5679
0.5790
0.5558
0.5638
0.5706
KBGRD
0.5932
0.5648
0.5731
0.5834
0.5678
0.5730
0.5759Table 8
AverageRandIndex of three algorithms on Nursery data set.
10
15
20
25
30
35
Average
k-modes
0.6839
0.7061
0.6963
0.6875
0.6815
0.6942
0.6916
Cao’s
0.7188
0.7071
0.6956
0.6989
0.6847
0.6982
0.7006
KBGRD
0.7195
0.7073
0.6967
0.7022
0.6957
0.6988
0.7034


## 6. Conclusion

This paper analyzes the advantages and disadvantages ofk-modes algorithms for categorical data. Based on this, we propose a novel dissimilarity measure (GRD) for clustering categorical data. This measure is used to improve the performance of the existingk-modes algorithm. The computational complexity of KBGRD algorithm has been analyzed which is linear with the number of data objects, attributes, and clusters. We have tested KBGRD algorithm on four real data sets from UCI. Experimental results have shown that KBGRD algorithm is effective and stable in clustering categorical data sets.



---

*Source: 3691316-2017-03-28.xml*