# A Validity Index for Fuzzy Clustering Based on Bipartite Modularity

Authors: Yongli Liu; Xiaoyang Zhang; Jingli Chen; Hao Chao
Journal: Journal of Electrical and Computer Engineering
 (2019)

---

## Abstract

Because traditional fuzzy clustering validity indices need to specify the number of clusters and are sensitive to noise data, we propose a validity index for fuzzy clustering, named CSBM (compactness separateness bipartite modularity), based on bipartite modularity. CSBM enhances the robustness by combining intraclass compactness and interclass separateness and can automatically determine the optimal number of clusters. In order to estimate the performance of CSBM, we carried out experiments on six real datasets and compared CSBM with other six prominent indices. Experimental results show that the CSBM index performs the best in terms of robustness while accurately detecting the number of clusters.


---

## Body

## 1. Introduction

Recently, in order to reveal valuable knowledge and patterns behind data, data mining has become increasingly crucial in many fields such as automatic categorization of text documents [1, 2], grouping search engine results [3, 4], analyzing time series data [5, 6], and others [7–10]. As one of the vital techniques of data mining, clustering can divide a group of samples into multiple clusters, so that elements in the same cluster are as similar as possible and elements in different clusters are as dissimilar as possible.In fuzzy clustering, represented by the FCM (fuzzy C means) [11] algorithm, the value of membership degree is fuzzy, which means that a sample is allowed to belong to multiple clusters with different probabilities. It is more consistent with the rule of sample distribution than the hard clustering logic; therefore, the fuzzy clustering research has constantly been ongoing and innovative. As yet, a large number of fuzzy clustering algorithms have been increasingly improved in accuracy, efficiency, robustness, and other aspects, which significantly boosts the development of data mining. At the same time, the validity index used to measure the clustering quality of fuzzy clustering, as an indispensable part of algorithm research, plays a growing important role in fuzzy clustering.Recently, the achievement on clustering validity index is pretty fruitful. Hu et al. [12] proposed a clustering validity index by combining intraclass compactness with intercluster separateness, which reduces the impact of noise data well. Chen and Pi [13] proposed a nondistance validity index based on fuzzy membership degree by mixing with compactness and separateness, which improves the identification of overlapping clusters while weakening the sensitivity to noise data. Although these indices enhance the robustness by combining intraclass compactness with interclass separateness, it is still necessary to manually specify the number of clusters owing to the restrictions of the FCM algorithm. Zhang et al. [14], regarding the fuzzy membership degree and the bipartite modularity as the global and local attributes, respectively, proposed a weighted global-local validity based index (WGLI). The WGLI can automatically determine the number of clusters but is vulnerable to noise data because of its higher dependency on the fuzzy membership degree of the FCM algorithm.Motivated by the above analysis, in this paper, we apply the bipartite modularity to the constructed bipartite network based on the clustering result of the FCM algorithm and evaluate the final partition result combining intraclass compactness with interclass separateness at the same time. The proposed validity index fuses the bipartite modularity with intraclass compactness and interclass separateness, which is not only able to enhance the robustness of clustering results but also able to determine the optimal number of clusters automatically.


## 2. Related Work

### 2.1. FCM Algorithm

The FCM algorithm dividesN data samples xii=1,2,…,N into C fuzzy clusters by means of the fuzzy partition method and then calculates the centre of each cluster. Its objective function shown in formula (1) is minimized through the process of iteration:(1)JmU,V=∑c=1C∑i=1Nucimxi−vc2,where vc represents the center of c-th cluster, m is the fuzzy parameter and m∈1,∞, and uci indicates the membership degree that the sample i belonging to the cluster c and(2)∑c=1Cuci=1,uci∈0,1.Then, the expressions ofuci and vc can be obtained using the Lagrange multiplier method as follows:(3)uci=1∑k=1Cdci/dki2/m−1,(4)vc=∑i=1Nucimxi∑i=1Nucim,where dci and dki, respectively, represent the Euclidean distances from the clustering centers c and k to the sample i.


### 2.2. Fuzzy Clustering Validity Index

The fuzzy clustering validity index can measure the clustering performance and is fairly significant in the fuzzy clustering research. The prevalent fuzzy clustering validity indices are shown in Table1.Table 1
The commonly used fuzzy clustering validity indices.
Indices
Definition
Description
PC (partition coefficient)
PC
=
1
/
N
∑
c
=
1
C
∑
i
=
1
N
u
c
i
2
The partition coefficient (PC) [15] measures the fuzzy degree of final divided clusters by means of the fuzzy partition matrix, and the larger its value, the better the partition result
PE (partition entropy)
PE
=
−
1
/
N
∑
c
=
1
C
∑
i
=
1
N
u
c
i
log
u
c
i
The partition entropy (PE) [16] measures the fuzzy degree of final divided clusters by means of the fuzzy partition matrix, and the smaller its value, the better the partition result
MPC (modified partition coefficient)
MPC
=
C
×
I
PC
−
1
/
C
−
1
Because the value of PC merely depends on the membership degreeuci, Dave [17] proposed the modified PC index MPC, and the larger its value, the better the partition result
MPE (modified partition entropy)
MPE
=
N
×
I
PE
/
N
−
C
Because the value of PE merely depends on the membership degreeuci, Dave [17] proposed the modified PE index MPE, and the smaller its value, the better the partition result
XB (Xie–Beni index)
XB
=
J
m
/
N
×
min
i
,
j
=
1
,
...
,
C
,
i
≠
j
v
i
−
v
j
2
Considering the membership degree and the structure of datasets, Xie and Beni [18] proposed the XB index to measure the overall average compactness and separateness, and the smaller its value, the better the partition result
FS (Fukuyama–Sugeno index)
FS
=
J
m
U
,
V
−
K
m
U
,
V
=
J
m
−
∑
i
=
1
N
∑
c
=
1
C
u
c
i
m
v
c
−
v
¯
2, where v¯=1/N∑i=1Nxi
Fukuyama and Sugeno [19] also proposed the index FS considering the compactness and separateness, and when its value reaches the minimum, the partition result is the best
PCAES (partition coefficient and exponential separation)
PCAES
=
∑
c
=
1
C
∑
i
=
1
N
u
c
i
2
/
u
M
−
∑
c
=
1
C
exp
−
min
k
≠
c
v
c
−
v
k
2
/
β
T, where uM=min1≤c≤C∑i=1Nuci2,βT=∑l=1Cvl−v¯2/C,v¯=1/N∑i=1Nxi
Wu and Yang [20] proposed the index PCAES by combining the normalized partition coefficient with the exponential separateness degree of each cluster, and the larger its value, the better the partition result
CO (compactness and overlap measures)
CO
=
C
c
,
U
−
O
c
,
U
=
1
/
n
∑
j
=
1
n
∑
i
=
1
c
C
i
j
c
,
U
−
∑
a
=
1
c
−
1
∑
b
=
a
+
1
c
O
a
b
j
c
,
U, where Cijc,U=uijifuij−uik≥Tc,k=1,…,c,k≠j0otherwiseOabjc,U=1−uaj−ubjifuaj−ubj≥To,a≠b0otherwise
Žalik [21] proposed the index CO based on the compactness and separateness, and the larger its value, the higher the compactness degree, and the lower the coverage degree between clusters, the better the partition result
WGLI (weighted global-local index)
WGLI
=
2
MMD
+
Q
B
′
/
3, where MMD=1/n∑j=1nmaxuij1≤i≤C
Zhang et al. [14], based on the membership degree obtained from the FCM algorithm, proposed the index WGLI combining the bipartite modularity; QB′ represents the bipartite modularity proposed by Murata [22], and the larger the value of WGLI, the better the partition result


### 2.3. Bipartite Modularity

Newman and Girvan [23] introduced modularity to measure the strength of community structure in a single network. However, networks in the real world not only exist in this simple form, which means, for example, in the metabolic networks [24], pathological networks [25], and the World Wide Web; there may be one-to-many and even many-to-many relationships between the vertices and the divided communities instead of the simple one-to-one relationship. For complicated networks, by extending and concretizing the matrix-based method that Newman used for bipartite network, Barber [26] defined a zero model and then proposed the bipartite modularity applied in bipartite networks with special constraints which means that the vertices of bipartite network are divided into two disjoint sets and each edge connects two vertices from these two sets, respectively. However, the disadvantages of the bipartite modularity include that the number of communities must be determined in advance, and the number of communities of the two types of vertices in the bipartite network must be equal. Guimerà et al. [27] proposed the bipartite modularity by adopting the idea of modularity maximization and transformed the module identification problem into the combinatorial optimization problem. Unfortunately, the module structure of a type of vertex should be manually specified, which will affect the accuracy of partition.Then, Murata [22] defined a modified bipartite modularity, which allows random connections between two types of vertices, and a community containing a type of vertex can correspond to one or more communities of the other type of vertex. When there is a complete one-to-one relationship between communities of different types of vertices, the bipartite modularity reaches its maximum.LetG be a bipartite network, in which M denotes the total number of edges and V is a set including all vertices. The bipartite network is divided into communities of X-vertex and Y-vertex, and the numbers of these communities are LX and LY. VX and VY are defined as sets of communities of X-vertex and Y-vertex and represented as VX=V1X,V2X,…,VLXX and VY=V1Y,V2Y,…,VLYY, respectively, in which the elements VlX and VmY represent a community of X-vertex and Y-vertex, respectively. Let A be an adjacency matrix, and one of its elements can be expressed as A (i, j). Moreover, if the vertexes i and j are connected, A (i, j) = 1, otherwise A (i, j) = 0.Assuming that the two communitiesVl and Vp are different from each other, which means Vl∈VX∧Vp∈VY∨Vl∈VY∧Vp∈VX; the number of all the edges, denoted by elp, that connect the vertices from Vl and Vp and its row sum, denoted by al, can be respectively expressed as(5)elp=12M∑i∈Vl∑j∈VpAi,j,(6)al=∑pelp=12M∑i∈Vl∑j∈VAi,j.The bipartite modularityQB is defined as(7)QB=QBXY+QBYX=∑l1∈VXel1p1−al1ap1+∑l2∈VYel2p2−al2ap2,where(8)p1=argmaxk1∈VYel1k1,(9)p2=argmaxk2∈VXel2k2.Q
B indicates the sum of bipartite modularity in two different directions, VX⟶VY and VY⟶VX, QBXY and QBYX, respectively, denote the expected values in two directions, which means the number of edges connecting the corresponding vertices from communities of X-vertex and Y-vertex minus the number of edges that are connected randomly between X-vertex and Y-vertex in the same divided communities. The larger the value of QB, the stronger the community structure of bipartite network and the better the result of community detection.


### 2.4. Constructing Bipartite Network

According to the membership degree matrix andC clusters obtained from the FCM algorithm, a weighted bipartite network can be constructed. The X-vertex is represented by all the cluster centers, the Y-vertex is denoted by all the sample points, and the weighted edges are indicated by membership degrees. Applying the bipartite modularity to the constructed bipartite network, we have LX = LY = C, M=∑i=1C∑j=1NAi,j, and the adjacency matrix A (i, j) can be defined as follows:(10)Ai,j=1.0,uci>α,uci,1−α≤uci≤α,0.0,uci<1−α,where α = 0.7, uci denotes the fuzzy membership degree of the FCM algorithm.Suppose that the FCM algorithm runs on a dataset including 10 sample points and 4 clusters. According to formula (10), a bipartite network can be constructed by cluster centers and sample points and shown as Figure 1.Figure 1
The example of bipartite network.In Figure1, the top nodes, which are also the X-vertex, represent different communities composed of cluster centers, and the bottom nodes, which are correspondingly the Y-vertex, represent different communities composed of divided datasets. Besides, the weighted values of the edges are the corresponding membership degrees, which are used to express the values of A (i, j). According to the formulas (5)–(10), the value of QB can be calculated.


## 2.1. FCM Algorithm

The FCM algorithm dividesN data samples xii=1,2,…,N into C fuzzy clusters by means of the fuzzy partition method and then calculates the centre of each cluster. Its objective function shown in formula (1) is minimized through the process of iteration:(1)JmU,V=∑c=1C∑i=1Nucimxi−vc2,where vc represents the center of c-th cluster, m is the fuzzy parameter and m∈1,∞, and uci indicates the membership degree that the sample i belonging to the cluster c and(2)∑c=1Cuci=1,uci∈0,1.Then, the expressions ofuci and vc can be obtained using the Lagrange multiplier method as follows:(3)uci=1∑k=1Cdci/dki2/m−1,(4)vc=∑i=1Nucimxi∑i=1Nucim,where dci and dki, respectively, represent the Euclidean distances from the clustering centers c and k to the sample i.


## 2.2. Fuzzy Clustering Validity Index

The fuzzy clustering validity index can measure the clustering performance and is fairly significant in the fuzzy clustering research. The prevalent fuzzy clustering validity indices are shown in Table1.Table 1
The commonly used fuzzy clustering validity indices.
Indices
Definition
Description
PC (partition coefficient)
PC
=
1
/
N
∑
c
=
1
C
∑
i
=
1
N
u
c
i
2
The partition coefficient (PC) [15] measures the fuzzy degree of final divided clusters by means of the fuzzy partition matrix, and the larger its value, the better the partition result
PE (partition entropy)
PE
=
−
1
/
N
∑
c
=
1
C
∑
i
=
1
N
u
c
i
log
u
c
i
The partition entropy (PE) [16] measures the fuzzy degree of final divided clusters by means of the fuzzy partition matrix, and the smaller its value, the better the partition result
MPC (modified partition coefficient)
MPC
=
C
×
I
PC
−
1
/
C
−
1
Because the value of PC merely depends on the membership degreeuci, Dave [17] proposed the modified PC index MPC, and the larger its value, the better the partition result
MPE (modified partition entropy)
MPE
=
N
×
I
PE
/
N
−
C
Because the value of PE merely depends on the membership degreeuci, Dave [17] proposed the modified PE index MPE, and the smaller its value, the better the partition result
XB (Xie–Beni index)
XB
=
J
m
/
N
×
min
i
,
j
=
1
,
...
,
C
,
i
≠
j
v
i
−
v
j
2
Considering the membership degree and the structure of datasets, Xie and Beni [18] proposed the XB index to measure the overall average compactness and separateness, and the smaller its value, the better the partition result
FS (Fukuyama–Sugeno index)
FS
=
J
m
U
,
V
−
K
m
U
,
V
=
J
m
−
∑
i
=
1
N
∑
c
=
1
C
u
c
i
m
v
c
−
v
¯
2, where v¯=1/N∑i=1Nxi
Fukuyama and Sugeno [19] also proposed the index FS considering the compactness and separateness, and when its value reaches the minimum, the partition result is the best
PCAES (partition coefficient and exponential separation)
PCAES
=
∑
c
=
1
C
∑
i
=
1
N
u
c
i
2
/
u
M
−
∑
c
=
1
C
exp
−
min
k
≠
c
v
c
−
v
k
2
/
β
T, where uM=min1≤c≤C∑i=1Nuci2,βT=∑l=1Cvl−v¯2/C,v¯=1/N∑i=1Nxi
Wu and Yang [20] proposed the index PCAES by combining the normalized partition coefficient with the exponential separateness degree of each cluster, and the larger its value, the better the partition result
CO (compactness and overlap measures)
CO
=
C
c
,
U
−
O
c
,
U
=
1
/
n
∑
j
=
1
n
∑
i
=
1
c
C
i
j
c
,
U
−
∑
a
=
1
c
−
1
∑
b
=
a
+
1
c
O
a
b
j
c
,
U, where Cijc,U=uijifuij−uik≥Tc,k=1,…,c,k≠j0otherwiseOabjc,U=1−uaj−ubjifuaj−ubj≥To,a≠b0otherwise
Žalik [21] proposed the index CO based on the compactness and separateness, and the larger its value, the higher the compactness degree, and the lower the coverage degree between clusters, the better the partition result
WGLI (weighted global-local index)
WGLI
=
2
MMD
+
Q
B
′
/
3, where MMD=1/n∑j=1nmaxuij1≤i≤C
Zhang et al. [14], based on the membership degree obtained from the FCM algorithm, proposed the index WGLI combining the bipartite modularity; QB′ represents the bipartite modularity proposed by Murata [22], and the larger the value of WGLI, the better the partition result


## 2.3. Bipartite Modularity

Newman and Girvan [23] introduced modularity to measure the strength of community structure in a single network. However, networks in the real world not only exist in this simple form, which means, for example, in the metabolic networks [24], pathological networks [25], and the World Wide Web; there may be one-to-many and even many-to-many relationships between the vertices and the divided communities instead of the simple one-to-one relationship. For complicated networks, by extending and concretizing the matrix-based method that Newman used for bipartite network, Barber [26] defined a zero model and then proposed the bipartite modularity applied in bipartite networks with special constraints which means that the vertices of bipartite network are divided into two disjoint sets and each edge connects two vertices from these two sets, respectively. However, the disadvantages of the bipartite modularity include that the number of communities must be determined in advance, and the number of communities of the two types of vertices in the bipartite network must be equal. Guimerà et al. [27] proposed the bipartite modularity by adopting the idea of modularity maximization and transformed the module identification problem into the combinatorial optimization problem. Unfortunately, the module structure of a type of vertex should be manually specified, which will affect the accuracy of partition.Then, Murata [22] defined a modified bipartite modularity, which allows random connections between two types of vertices, and a community containing a type of vertex can correspond to one or more communities of the other type of vertex. When there is a complete one-to-one relationship between communities of different types of vertices, the bipartite modularity reaches its maximum.LetG be a bipartite network, in which M denotes the total number of edges and V is a set including all vertices. The bipartite network is divided into communities of X-vertex and Y-vertex, and the numbers of these communities are LX and LY. VX and VY are defined as sets of communities of X-vertex and Y-vertex and represented as VX=V1X,V2X,…,VLXX and VY=V1Y,V2Y,…,VLYY, respectively, in which the elements VlX and VmY represent a community of X-vertex and Y-vertex, respectively. Let A be an adjacency matrix, and one of its elements can be expressed as A (i, j). Moreover, if the vertexes i and j are connected, A (i, j) = 1, otherwise A (i, j) = 0.Assuming that the two communitiesVl and Vp are different from each other, which means Vl∈VX∧Vp∈VY∨Vl∈VY∧Vp∈VX; the number of all the edges, denoted by elp, that connect the vertices from Vl and Vp and its row sum, denoted by al, can be respectively expressed as(5)elp=12M∑i∈Vl∑j∈VpAi,j,(6)al=∑pelp=12M∑i∈Vl∑j∈VAi,j.The bipartite modularityQB is defined as(7)QB=QBXY+QBYX=∑l1∈VXel1p1−al1ap1+∑l2∈VYel2p2−al2ap2,where(8)p1=argmaxk1∈VYel1k1,(9)p2=argmaxk2∈VXel2k2.Q
B indicates the sum of bipartite modularity in two different directions, VX⟶VY and VY⟶VX, QBXY and QBYX, respectively, denote the expected values in two directions, which means the number of edges connecting the corresponding vertices from communities of X-vertex and Y-vertex minus the number of edges that are connected randomly between X-vertex and Y-vertex in the same divided communities. The larger the value of QB, the stronger the community structure of bipartite network and the better the result of community detection.


## 2.4. Constructing Bipartite Network

According to the membership degree matrix andC clusters obtained from the FCM algorithm, a weighted bipartite network can be constructed. The X-vertex is represented by all the cluster centers, the Y-vertex is denoted by all the sample points, and the weighted edges are indicated by membership degrees. Applying the bipartite modularity to the constructed bipartite network, we have LX = LY = C, M=∑i=1C∑j=1NAi,j, and the adjacency matrix A (i, j) can be defined as follows:(10)Ai,j=1.0,uci>α,uci,1−α≤uci≤α,0.0,uci<1−α,where α = 0.7, uci denotes the fuzzy membership degree of the FCM algorithm.Suppose that the FCM algorithm runs on a dataset including 10 sample points and 4 clusters. According to formula (10), a bipartite network can be constructed by cluster centers and sample points and shown as Figure 1.Figure 1
The example of bipartite network.In Figure1, the top nodes, which are also the X-vertex, represent different communities composed of cluster centers, and the bottom nodes, which are correspondingly the Y-vertex, represent different communities composed of divided datasets. Besides, the weighted values of the edges are the corresponding membership degrees, which are used to express the values of A (i, j). According to the formulas (5)–(10), the value of QB can be calculated.


## 3. Fuzzy Clustering Validity Index CSBM

In this paper, we proposed a fuzzy clustering validity index named CSBM. This index combines three components: (1) bipartite modularity, (2) intraclass compactness, and (3) interclass separateness. First, CSBM builds a bipartite network based on the clustering results of FCM and applies the bipartite modularity to this bipartite network. Second, CSBM evaluates the clustering results by combining intraclass compactness and interclass separation.Compared with the conventional validity indices, the index CSBM can enhance the robustness on the one hand and automatically determine the optimal number of clusters on the other hand.


### 3.1. Intraclass Compactness

The intraclass compactness of the index CSBM is defined as(11)NC=∑i=1N∑c=1Cuci2umax,where(12)umax=max1≤i≤N∑c=1Cuci2.NC (novel compactness) improves the performance of the partition coefficient PC, where the compactness of the clusterc is expressed as uci2/umax. The larger the value of NC, the higher the intraclass compactness, and the better the result of fuzzy partition.


### 3.2. Interclass Separateness

In order to reduce the impact of noise data on the clustering result, the interclass separateness is measured by the distance between different fuzzy clusters, which is defined as follows:(13)SEP=1N∑i=1N∑a=1C−1∑b=a+1COabiC,U,where(14)OabiC,U=1−uai−ubi,ifuai−ubi≥To,a≠b,0,otherwise.The thresholdTo is used to eliminate the noise points on the cluster boundary and represents the separateness between samples of two clusters a and b. uai and ubi indicate the membership degrees that sample point i belonging to cluster a and b, respectively. The smaller the value of Oabi (C, U), the lower the coverage degree between clusters a and b, and the higher the separation degree between the two clusters, whereas SEP (separateness) indicates the sum of the cluster separation degrees of all sample points in the fuzzy membership matrix, and the smaller the value of SEP, the better the result of fuzzy partition.


### 3.3. Index CSBM

The objective function used to calculate the index CSBM is defined as(15)CSBM=C−11/C×NC−SEP+QB2.The introduction ofC−11/C is to adjust the value of CSBM. The larger the value of NC, the smaller the value of SEP and the better the clustering result. At the same time, the larger the value of NC-SEP and QB, the larger the value of CSBM. The better the clustering quality of FCM algorithm, the more accurate the optimal number of clusters.The calculation process of the fuzzy clustering validity index (CSBM) is as follows:(1)
Input: the datasetS and threshold ε used in the FCM algorithm(2)
Output: the clustering result.(3)
Running the FCM algorithm on the given dataset(4)
Constructing the weighted bipartite network according to the membership degreeuci and the cluster centre vc obtained from formulas (3) and (4) and the adjacency matrix A (i, j) from formula (10).(5)
Calculating the bipartite modularityQB according to formulas (5)–(10)(6)
Calculating CSBM according to formulas (11)–(15)


## 3.1. Intraclass Compactness

The intraclass compactness of the index CSBM is defined as(11)NC=∑i=1N∑c=1Cuci2umax,where(12)umax=max1≤i≤N∑c=1Cuci2.NC (novel compactness) improves the performance of the partition coefficient PC, where the compactness of the clusterc is expressed as uci2/umax. The larger the value of NC, the higher the intraclass compactness, and the better the result of fuzzy partition.


## 3.2. Interclass Separateness

In order to reduce the impact of noise data on the clustering result, the interclass separateness is measured by the distance between different fuzzy clusters, which is defined as follows:(13)SEP=1N∑i=1N∑a=1C−1∑b=a+1COabiC,U,where(14)OabiC,U=1−uai−ubi,ifuai−ubi≥To,a≠b,0,otherwise.The thresholdTo is used to eliminate the noise points on the cluster boundary and represents the separateness between samples of two clusters a and b. uai and ubi indicate the membership degrees that sample point i belonging to cluster a and b, respectively. The smaller the value of Oabi (C, U), the lower the coverage degree between clusters a and b, and the higher the separation degree between the two clusters, whereas SEP (separateness) indicates the sum of the cluster separation degrees of all sample points in the fuzzy membership matrix, and the smaller the value of SEP, the better the result of fuzzy partition.


## 3.3. Index CSBM

The objective function used to calculate the index CSBM is defined as(15)CSBM=C−11/C×NC−SEP+QB2.The introduction ofC−11/C is to adjust the value of CSBM. The larger the value of NC, the smaller the value of SEP and the better the clustering result. At the same time, the larger the value of NC-SEP and QB, the larger the value of CSBM. The better the clustering quality of FCM algorithm, the more accurate the optimal number of clusters.The calculation process of the fuzzy clustering validity index (CSBM) is as follows:(1)
Input: the datasetS and threshold ε used in the FCM algorithm(2)
Output: the clustering result.(3)
Running the FCM algorithm on the given dataset(4)
Constructing the weighted bipartite network according to the membership degreeuci and the cluster centre vc obtained from formulas (3) and (4) and the adjacency matrix A (i, j) from formula (10).(5)
Calculating the bipartite modularityQB according to formulas (5)–(10)(6)
Calculating CSBM according to formulas (11)–(15)


## 4. Experiments

### 4.1. Datasets

In order to verify the effectiveness and validity of the index CSBM, we select six datasets from UCI database. The detailed information of these six datasets is shown in Table2.Table 2
The detailed information of datasets.
Datasets
Samples
Attributes
Clusters
Description
Iris
150
4
3
The dataset is the most famous database in the pattern recognition literatures, including 150 samples, 4 attributes, and 3 classes containing 50 instances each, and each class refers to a type of iris.
Wine
178
13
3
The dataset is the result of chemical analysis on three different kinds of wines from the same region of Italy. It contains 178 results. The analysis determines the number of 13 components found in each wine. The dataset is divided into three categories.
Wpbc
194
33
2
The dataset is a Wisconsin breast cancer dataset with 194 samples and 33 attributes, and each sample represents a subsequent data of breast cancer case. The dataset is divided into two categories.
Hayesroth
132
5
3
The dataset describes the evidence of behaviour classification, confidence degree, and recognition behaviour that are closely related to human behaviour. It contains 132 samples and 5 attributes using numerical values instead of actual values. The dataset is divided into three classes.
Zoo
101
16
7
The dataset describes the classification of animals, including 101 samples and 17 attributes. The dataset is divided into 7 classes.
Glass
214
9
6
The study of glass classification is motivated by criminological investigations. If the identification is correct, the remaining glass can act as evidence. The dataset consists of 214 samples and 9 attributes, which is divided into 6 classes.


### 4.2. Evaluation Criteria for Clustering Result

F-measure (FM) and entropy (EN) are used to evaluate the clustering result of the FCM algorithm. F-measure is often used to evaluate the partition result of clustering algorithms and can be defined as(16)F=2PRP+R,where P represents the accuracy rate, which means the proportion of the related files retrieved by the system to the total number of all the related files in the system and R represents the recall rate, which indicates the proportion of the related files retrieved by the system to the total number of all the files retrieved by the system. In general, the accuracy rate and recall rate interact on each other. Considering these two factors, the index F-measure can be calculated and reveals the overall performance. The value range of F-measure is [0, 1], and the larger its value, the better the clustering result.Entropy, also known as Shannon entropy [28], is represented by a set of discrete probabilities pi, which, in the case of sending a message, are the ones that a particular message is actually sent. The entropy of message system is used to measure the average amount of information in a message and can be defined as follows:(17)E=∑i=1Npilog2pi.The value range of entropy is [0, 1], and the smaller its value, the better the clustering result.


### 4.3. Experimental Results

In order to evaluate the accuracy of CSBM in terms of predicting the optimal number of clusters, we compare it with six prevalent fuzzy clustering validity indices, including PC, PE, MPC, MPE, CO, and WGLI. Tables3–8 show the values of the index CSBM and other comparative indices obtained from running the FCM algorithm on six datasets, in which the values of F-measure and entropy are also included, so the practicability and effectiveness of the FCM algorithm can be confirmed. The bold values in the tables denote the values of indices corresponding to the optimal number of clusters.Table 3
Values of each index on the iris dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7582
0.7966
0.8724
0.0833
0.7668
0.0844
0.8840
0.8399
0.2507
3
0.7744
0.7427
0.7660
0.1682
0.6599
0.1716
0.8129
0.9815
0.1338
4
0.7625
0.6926
0.6699
0.2468
0.5672
0.2536
0.7130
0.8652
0.1304
5
0.7593
0.6824
0.6508
0.2871
0.5690
0.2970
0.7072
0.8458
0.0888
6
0.7646
0.6472
0.5931
0.3474
0.5161
0.3618
0.6035
0.7968
0.0825
7
0.7647
0.6248
0.5447
0.3856
0.4725
0.4045
0.5832
0.7232
0.0446Table 4
Values of each index on the wine dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7436
0.7760
0.8518
0.0912
0.7313
0.0922
0.8515
0.8533
0.3846
3
0.7564
0.7427
0.7690
0.1606
0.6674
0.1634
0.8294
0.8383
0.3304
4
0.7488
0.7314
0.7613
0.1767
0.6910
0.1807
0.8322
0.7379
0.3382
5
0.7483
0.7146
0.7235
0.2152
0.6613
0.2214
0.7933
0.7587
0.2875
6
0.7475
0.7192
0.7258
0.2204
0.6765
0.2280
0.8005
0.6555
0.282
7
0.7411
0.7208
0.7368
0.2134
0.6976
0.2221
0.7973
0.6425
0.2743Table 5
Values of each index on the wpbc dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7187
0.7460
0.7640
0.1180
0.5997
0.1192
0.7407
0.7833
0.2788
3
0.7109
0.7098
0.7132
0.1686
0.6057
0.1713
0.7654
0.6914
0.2723
4
0.7142
0.7003
0.6786
0.2079
0.5954
0.2122
0.7526
0.5835
0.2778
5
0.7158
0.6726
0.6341
0.2527
0.5605
0.2594
0.6769
0.5362
0.2781
6
0.7106
0.6635
0.6013
0.2889
0.5359
0.2981
0.6703
0.4124
0.2758
7
0.7175
0.6547
0.5922
0.3045
0.5362
0.3159
0.6621
0.4014
0.2729Table 6
Values of each index on the Hayesroth dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7429
0.7697
0.8141
0.1022
0.6749
0.1038
0.7985
0.4485
0.4618
3
0.7439
0.7419
0.7616
0.1529
0.6657
0.1564
0.8072
0.4328
0.4544
4
0.7404
0.7252
0.7318
0.1856
0.6579
0.1914
0.773
0.3603
0.4574
5
0.7368
0.7125
0.711
0.2099
0.6504
0.2182
0.7778
0.3369
0.4562
6
0.7355
0.7041
0.6945
0.2301
0.6428
0.241
0.7625
0.3269
0.4437
7
0.7343
0.6958
0.6786
0.2493
0.6329
0.2633
0.7405
0.2997
0.4427Table 7
Values of each index on the zoo dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
3
0.7853
0.6493
0.6147
0.2940
0.4248
0.3030
0.5777
0.6000
0.3421
4
0.7891
0.6711
0.6196
0.3219
0.4946
0.3352
0.6767
0.6825
0.2475
5
0.7885
0.622
0.5326
0.4117
0.4171
0.4332
0.5685
0.6652
0.2183
6
0.7778
0.5996
0.4917
0.4697
0.3911
0.4993
0.5662
0.7103
0.1625
7
0.8149
0.5542
0.4496
0.5117
0.3588
0.5498
0.4215
0.5737
0.1800
8
0.7969
0.556
0.4476
0.5342
0.3695
0.5802
0.4691
0.6003
0.1248Table 8
Values of each index on the glass dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7252
0.7296
0.7702
0.1314
0.5864
0.1326
0.7498
0.6782
0.6697
3
0.7036
0.6958
0.7215
0.1909
0.6054
0.1936
0.7392
0.7240
0.6119
4
0.7350
0.6421
0.6051
0.2859
0.4889
0.2913
0.6576
0.7038
0.5901
5
0.7852
0.5568
0.4763
0.3925
0.3569
0.4019
0.3512
0.6558
0.5753
6
0.7746
0.5541
0.4703
0.4127
0.3736
0.4246
0.5503
0.6776
0.5364
7
0.7845
0.5307
0.4193
0.4799
0.3302
0.4961
0.4578
0.6967
0.5378The experimental results can be clearly interpretive from the following three aspects:(1)
On the iris, wine, and zoo datasets (Tables3, 4 and 7, respectively), the index CSBM outperforms other indices, which means its matching classification number indicates the best partition result. On the iris and wine datasets shown in Tables 3 and 4, respectively, other indices could produce their own best index values when the cluster number equals 2. And actually, these two datasets have both 3 classes. Table 7 lists the results on the zoo dataset which has 7 classes. However, WGLI, PC, MPC, and CO all generate their own best index values when there are 4 clusters, and PE and MPE think the best number of clusters is 3.(2)
On the wpbc and Hayesroth datasets shown in Tables5 and 6, respectively, some indices including CSBM all gain their own optimal values, while others are not as satisfactory. On the wpbc dataset, there are 5 indices that could find the realistic number of classes accurately, including CSBM, WGLI, PC, PE, and MPE. Other two indices, MPC and CO, find more clusters. On the Hayesroth dataset, only the CSBM and CO generate accurate number of clusters and the other 5 indices generate less clusters.(3)
On the glass dataset as in Table8, all the indices cannot achieve the desired results. But compared with the other indices, the predicted value, 5, of the index CSBM is closest to the standard value, 6. The second best is the index MPC, whose predicted number of clusters is 3. The rest indices, including WGLI, PC, PE, MPE, and CO, all generate their own best values when the number of clusters is 2.According to the above experimental results, the index CSBM performs better than these comparative indices in terms of predicting the optimal number of clusters.In order to verify the robustness of the index CSBM, we add some noisy data to each dataset at a rate of 10% and then run the FCM algorithm again. The change trend of values of all the indices with the number of clusters is shown as Figure2. At the same time, the OC (original clusters) is the original classification number of each dataset, and the optimal numbers of clusters of each dataset determined by all the indices before and after adding noise data are shown in Table 9.Figure 2
The variation trend of each index with the number of cluster (C) after adding noise data. (a) Iris. (b) Wine. (c) Wpbc. (d) Hayesroth. (e) Zoo. (f) Glass.
(a)
(b)
(c)
(d)
(e)
(f)Table 9
The original classification number of each dataset and the optimal number of clusters determined by each index before and after adding noise data.
Datasets
OC
CSBM
WGLI
PC
PE
MPC
MPE
CO
Iris
3
3(3)
2(2)
2(2)
2(2)
2(2)
2(2)
2(2)
Wine
3
3(3)
2(2)
2(2)
2(2)
2(5)
2(2)
2(3)
Wpbc
2
2(2)
2(2)
2(2)
2(2)
3(4)
2(2)
3(3)
Hayesroth
3
3(3)
2(2)
2(2)
2(2)
2(4)
2(2)
3(4)
Zoo
7
7(7)
4(4)
4(4)
3(3)
4(4)
3(3)
4(4)
Glass
6
5(6)
2(2)
2(3)
2(3)
3(3)
2(3)
2(3)The numbers outside and within parentheses, respectively, represent the optimal number of clusters determined by the corresponding indices before and after the addition of noise data, and the coarser values indicate that the number of clusters matches the standard valuesIt can be seen from Figure2 and Table 9 that the index CSBM is less vulnerable to the added noise data than other comparative indices and can still determine the optimal number of clusters accurately. Meanwhile, due to the noise data, the results of indices WGLI, PC, PE, and MPE on zoo and glass datasets, index MPC on wine, wpbc and Hayesroth datasets and index CO on wine, and Hayesroth and glass datasets are all changed in different degrees. According to Figure 2, after adding noise data, the values of some indices remain unchanged, such as the results of WGLI on iris dataset, and the values of some indices are slightly closer to standard values, such as the results of CO on wine dataset. However, some indices differ from standard values to a greater extent, such as the results of MPC on wine dataset. The overall change shows that there is a big difference between the value of each index and the standard values in theory after adding noise data, but the actual results are relatively random and lack of the corresponding rules, which furthermore verifies the excellent performance of the index CSBM in terms of robustness.


## 4.1. Datasets

In order to verify the effectiveness and validity of the index CSBM, we select six datasets from UCI database. The detailed information of these six datasets is shown in Table2.Table 2
The detailed information of datasets.
Datasets
Samples
Attributes
Clusters
Description
Iris
150
4
3
The dataset is the most famous database in the pattern recognition literatures, including 150 samples, 4 attributes, and 3 classes containing 50 instances each, and each class refers to a type of iris.
Wine
178
13
3
The dataset is the result of chemical analysis on three different kinds of wines from the same region of Italy. It contains 178 results. The analysis determines the number of 13 components found in each wine. The dataset is divided into three categories.
Wpbc
194
33
2
The dataset is a Wisconsin breast cancer dataset with 194 samples and 33 attributes, and each sample represents a subsequent data of breast cancer case. The dataset is divided into two categories.
Hayesroth
132
5
3
The dataset describes the evidence of behaviour classification, confidence degree, and recognition behaviour that are closely related to human behaviour. It contains 132 samples and 5 attributes using numerical values instead of actual values. The dataset is divided into three classes.
Zoo
101
16
7
The dataset describes the classification of animals, including 101 samples and 17 attributes. The dataset is divided into 7 classes.
Glass
214
9
6
The study of glass classification is motivated by criminological investigations. If the identification is correct, the remaining glass can act as evidence. The dataset consists of 214 samples and 9 attributes, which is divided into 6 classes.


## 4.2. Evaluation Criteria for Clustering Result

F-measure (FM) and entropy (EN) are used to evaluate the clustering result of the FCM algorithm. F-measure is often used to evaluate the partition result of clustering algorithms and can be defined as(16)F=2PRP+R,where P represents the accuracy rate, which means the proportion of the related files retrieved by the system to the total number of all the related files in the system and R represents the recall rate, which indicates the proportion of the related files retrieved by the system to the total number of all the files retrieved by the system. In general, the accuracy rate and recall rate interact on each other. Considering these two factors, the index F-measure can be calculated and reveals the overall performance. The value range of F-measure is [0, 1], and the larger its value, the better the clustering result.Entropy, also known as Shannon entropy [28], is represented by a set of discrete probabilities pi, which, in the case of sending a message, are the ones that a particular message is actually sent. The entropy of message system is used to measure the average amount of information in a message and can be defined as follows:(17)E=∑i=1Npilog2pi.The value range of entropy is [0, 1], and the smaller its value, the better the clustering result.


## 4.3. Experimental Results

In order to evaluate the accuracy of CSBM in terms of predicting the optimal number of clusters, we compare it with six prevalent fuzzy clustering validity indices, including PC, PE, MPC, MPE, CO, and WGLI. Tables3–8 show the values of the index CSBM and other comparative indices obtained from running the FCM algorithm on six datasets, in which the values of F-measure and entropy are also included, so the practicability and effectiveness of the FCM algorithm can be confirmed. The bold values in the tables denote the values of indices corresponding to the optimal number of clusters.Table 3
Values of each index on the iris dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7582
0.7966
0.8724
0.0833
0.7668
0.0844
0.8840
0.8399
0.2507
3
0.7744
0.7427
0.7660
0.1682
0.6599
0.1716
0.8129
0.9815
0.1338
4
0.7625
0.6926
0.6699
0.2468
0.5672
0.2536
0.7130
0.8652
0.1304
5
0.7593
0.6824
0.6508
0.2871
0.5690
0.2970
0.7072
0.8458
0.0888
6
0.7646
0.6472
0.5931
0.3474
0.5161
0.3618
0.6035
0.7968
0.0825
7
0.7647
0.6248
0.5447
0.3856
0.4725
0.4045
0.5832
0.7232
0.0446Table 4
Values of each index on the wine dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7436
0.7760
0.8518
0.0912
0.7313
0.0922
0.8515
0.8533
0.3846
3
0.7564
0.7427
0.7690
0.1606
0.6674
0.1634
0.8294
0.8383
0.3304
4
0.7488
0.7314
0.7613
0.1767
0.6910
0.1807
0.8322
0.7379
0.3382
5
0.7483
0.7146
0.7235
0.2152
0.6613
0.2214
0.7933
0.7587
0.2875
6
0.7475
0.7192
0.7258
0.2204
0.6765
0.2280
0.8005
0.6555
0.282
7
0.7411
0.7208
0.7368
0.2134
0.6976
0.2221
0.7973
0.6425
0.2743Table 5
Values of each index on the wpbc dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7187
0.7460
0.7640
0.1180
0.5997
0.1192
0.7407
0.7833
0.2788
3
0.7109
0.7098
0.7132
0.1686
0.6057
0.1713
0.7654
0.6914
0.2723
4
0.7142
0.7003
0.6786
0.2079
0.5954
0.2122
0.7526
0.5835
0.2778
5
0.7158
0.6726
0.6341
0.2527
0.5605
0.2594
0.6769
0.5362
0.2781
6
0.7106
0.6635
0.6013
0.2889
0.5359
0.2981
0.6703
0.4124
0.2758
7
0.7175
0.6547
0.5922
0.3045
0.5362
0.3159
0.6621
0.4014
0.2729Table 6
Values of each index on the Hayesroth dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7429
0.7697
0.8141
0.1022
0.6749
0.1038
0.7985
0.4485
0.4618
3
0.7439
0.7419
0.7616
0.1529
0.6657
0.1564
0.8072
0.4328
0.4544
4
0.7404
0.7252
0.7318
0.1856
0.6579
0.1914
0.773
0.3603
0.4574
5
0.7368
0.7125
0.711
0.2099
0.6504
0.2182
0.7778
0.3369
0.4562
6
0.7355
0.7041
0.6945
0.2301
0.6428
0.241
0.7625
0.3269
0.4437
7
0.7343
0.6958
0.6786
0.2493
0.6329
0.2633
0.7405
0.2997
0.4427Table 7
Values of each index on the zoo dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
3
0.7853
0.6493
0.6147
0.2940
0.4248
0.3030
0.5777
0.6000
0.3421
4
0.7891
0.6711
0.6196
0.3219
0.4946
0.3352
0.6767
0.6825
0.2475
5
0.7885
0.622
0.5326
0.4117
0.4171
0.4332
0.5685
0.6652
0.2183
6
0.7778
0.5996
0.4917
0.4697
0.3911
0.4993
0.5662
0.7103
0.1625
7
0.8149
0.5542
0.4496
0.5117
0.3588
0.5498
0.4215
0.5737
0.1800
8
0.7969
0.556
0.4476
0.5342
0.3695
0.5802
0.4691
0.6003
0.1248Table 8
Values of each index on the glass dataset.
Clusters
CSBM
WGLI
PC
PE
MPC
MPE
CO
FM
EN
2
0.7252
0.7296
0.7702
0.1314
0.5864
0.1326
0.7498
0.6782
0.6697
3
0.7036
0.6958
0.7215
0.1909
0.6054
0.1936
0.7392
0.7240
0.6119
4
0.7350
0.6421
0.6051
0.2859
0.4889
0.2913
0.6576
0.7038
0.5901
5
0.7852
0.5568
0.4763
0.3925
0.3569
0.4019
0.3512
0.6558
0.5753
6
0.7746
0.5541
0.4703
0.4127
0.3736
0.4246
0.5503
0.6776
0.5364
7
0.7845
0.5307
0.4193
0.4799
0.3302
0.4961
0.4578
0.6967
0.5378The experimental results can be clearly interpretive from the following three aspects:(1)
On the iris, wine, and zoo datasets (Tables3, 4 and 7, respectively), the index CSBM outperforms other indices, which means its matching classification number indicates the best partition result. On the iris and wine datasets shown in Tables 3 and 4, respectively, other indices could produce their own best index values when the cluster number equals 2. And actually, these two datasets have both 3 classes. Table 7 lists the results on the zoo dataset which has 7 classes. However, WGLI, PC, MPC, and CO all generate their own best index values when there are 4 clusters, and PE and MPE think the best number of clusters is 3.(2)
On the wpbc and Hayesroth datasets shown in Tables5 and 6, respectively, some indices including CSBM all gain their own optimal values, while others are not as satisfactory. On the wpbc dataset, there are 5 indices that could find the realistic number of classes accurately, including CSBM, WGLI, PC, PE, and MPE. Other two indices, MPC and CO, find more clusters. On the Hayesroth dataset, only the CSBM and CO generate accurate number of clusters and the other 5 indices generate less clusters.(3)
On the glass dataset as in Table8, all the indices cannot achieve the desired results. But compared with the other indices, the predicted value, 5, of the index CSBM is closest to the standard value, 6. The second best is the index MPC, whose predicted number of clusters is 3. The rest indices, including WGLI, PC, PE, MPE, and CO, all generate their own best values when the number of clusters is 2.According to the above experimental results, the index CSBM performs better than these comparative indices in terms of predicting the optimal number of clusters.In order to verify the robustness of the index CSBM, we add some noisy data to each dataset at a rate of 10% and then run the FCM algorithm again. The change trend of values of all the indices with the number of clusters is shown as Figure2. At the same time, the OC (original clusters) is the original classification number of each dataset, and the optimal numbers of clusters of each dataset determined by all the indices before and after adding noise data are shown in Table 9.Figure 2
The variation trend of each index with the number of cluster (C) after adding noise data. (a) Iris. (b) Wine. (c) Wpbc. (d) Hayesroth. (e) Zoo. (f) Glass.
(a)
(b)
(c)
(d)
(e)
(f)Table 9
The original classification number of each dataset and the optimal number of clusters determined by each index before and after adding noise data.
Datasets
OC
CSBM
WGLI
PC
PE
MPC
MPE
CO
Iris
3
3(3)
2(2)
2(2)
2(2)
2(2)
2(2)
2(2)
Wine
3
3(3)
2(2)
2(2)
2(2)
2(5)
2(2)
2(3)
Wpbc
2
2(2)
2(2)
2(2)
2(2)
3(4)
2(2)
3(3)
Hayesroth
3
3(3)
2(2)
2(2)
2(2)
2(4)
2(2)
3(4)
Zoo
7
7(7)
4(4)
4(4)
3(3)
4(4)
3(3)
4(4)
Glass
6
5(6)
2(2)
2(3)
2(3)
3(3)
2(3)
2(3)The numbers outside and within parentheses, respectively, represent the optimal number of clusters determined by the corresponding indices before and after the addition of noise data, and the coarser values indicate that the number of clusters matches the standard valuesIt can be seen from Figure2 and Table 9 that the index CSBM is less vulnerable to the added noise data than other comparative indices and can still determine the optimal number of clusters accurately. Meanwhile, due to the noise data, the results of indices WGLI, PC, PE, and MPE on zoo and glass datasets, index MPC on wine, wpbc and Hayesroth datasets and index CO on wine, and Hayesroth and glass datasets are all changed in different degrees. According to Figure 2, after adding noise data, the values of some indices remain unchanged, such as the results of WGLI on iris dataset, and the values of some indices are slightly closer to standard values, such as the results of CO on wine dataset. However, some indices differ from standard values to a greater extent, such as the results of MPC on wine dataset. The overall change shows that there is a big difference between the value of each index and the standard values in theory after adding noise data, but the actual results are relatively random and lack of the corresponding rules, which furthermore verifies the excellent performance of the index CSBM in terms of robustness.


## 5. Conclusions

In this paper, a new fuzzy clustering validity index named CSBM is proposed. This index modifies the intraclass compactness and interclass separateness on the basis of conventional indices, which means that it enhances the robustness and weakens the impact of noise data. At the same time, the optimal cluster number of fuzzy clustering can be predicted more accurately by integrating with bipartite modularity. Six datasets from the UCI database are selected for the sake of validating the feasibility and validity of the index CSBM. The results show that the index CSBM performs better than other comparative indices in terms of clustering accuracy and robustness and predicts the optimal number of clusters more precisely.



---

*Source: 2719617-2019-08-08.xml*