# Cluster Analysis Based on Bipartite Network

Authors: Dawei Zhang; Fuding Xie; Dapeng Wang; Yong Zhang; Yan Sun
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Clustering data has a wide range of applications and has attracted considerable attention in data mining and artificial intelligence. However it is difficult to find a set of clusters that best fits natural partitions without any class information. In this paper, a method for detecting the optimal cluster number is proposed. The optimal cluster number can be obtained by the proposal, while partitioning the data into clusters by FCM (Fuzzyc-means) algorithm. It overcomes the drawback of FCM algorithm which needs to define the cluster number c in advance. The method works by converting the fuzzy cluster result into a weighted bipartite network and then the optimal cluster number can be detected by the improved bipartite modularity. The experimental results on artificial and real data sets show the validity of the proposed method.


---

## Body

## 1. Introduction

Clustering is the unsupervised classification of data points into groups or clusters, such that samples in the same group are similar to each other, while patterns in different groups are dissimilar. In past decades, a number of clustering algorithms have been proposed, attempting to classify the given data set into groups by using different similarities. Generally, these algorithms can be classified into three cases: hard (crisp) cluster, soft (fuzzy) cluster, and possibilistic clustering [1–3]. The classical clustering algorithms should be c-means and fuzzy c-means and their various improved versions. However, these algorithms require the user to specify the number c, of clusters which the user does not usually know in advance or may not want to specify. As a consequence, the clustering result often depends on the choice of parameter. Therefore a very challenging problem in cluster analysis is the cluster validity problem in the literatures, which consists of finding the optimal value for c.In fact, clustering validation is a technique to find a set of clusters that best fits natural partitions (number of clusters) without any class information. Based on FCM algorithm and bipartite network, in this paper, a method for finding the optimal cluster numberc is suggested. A weighted bipartite network is first constructed by using of membership matrix and centers of each clusters obtained by FCM algorithm. Then the bipartite modularity of the bipartite network is extended to the case of the weighted bipartite network. Last, the optimal cluster number c is obtained by optimal community structures. To validate the effectiveness of the proposed method, one has done the experiments on seven artificial data sets and seven real data sets. As a result, the optimal cluster number c has been detected for most of data sets.


## 2. Related Works

### 2.1. Some Cluster Validity Indices

The purpose of clustering algorithm is to divide the given data setX
=
{
x
1
,
x
2
,
…
,
x
n
} into groups X
1
,
X
2
,
…
,
X
c. The partition matrix U of size c
×
n may be represented as U
=
[
u
i
j
], i
=
1,2
,
…
,
c and j
=
1,2
,
…
,
n, where u
i
j is the membership of sample x
j to cluster X
i. In the case of crisp partitioning, the following condition should be satisfied: u
i
j
=
1 if x
j
∈
X
i; otherwise, u
i
j
=
0 [4].Formally, the goal of clustering analysis can be represented as follows:(1)
⋃
i
=
1
c
X
i
=
X
,
X
i
≠
∅
,
i
=
1,2
,
…
,
c
,
X
i
∩
X
j
=
0
,
i
=
1,2
,
…
,
c
,
j
=
1,2
,
…
,
n
.In the case of fuzzy clustering, the membershipu
i
j is in interval [
0,1
]. The crisp clustering may be viewed as a special case of fuzzy clustering.No matter what, we take crisp partitioning method or fuzzy clustering algorithm to separate data set into groups, the generated partitions may not reflect the desired clustering of the data because of inappropriate choice of algorithmic parameters. Thus, it is a key problem how to determine the cluster numberc, especially for real data sets. Clustering is an unsupervised classification process and therefore it has no a priori information of a data set. That is to say that user has no prior knowledge about the number of classes. For two-dimensional data or data set with small size, it is possible to visually verify the validity of the results. However, the visualization of the data set in high dimensional space or with huge size would be difficult. Thus it is difficult to partition the given data set into clusters which best fit the natural distribution of the data set.To find the optimal cluster numberc, the researchers proposed some validity indices based on fuzzy cluster result obtained by FCM algorithm. Once the partition is obtained by a clustering method, the validity function can help us to validate whether it accurately presents the structure of the data set or not. In Table 1, some popular validity indices are listed. The earliest proposed fuzzy cluster validity functions associated with FCM are the partition coefficient (PC) and partition entropy (PE) [5, 6]. NPC and NPE, modification of the PC and PE, proposed by Dunn and Roubens [7, 8] in succession. These indices only use the membership values and have the advantage of being easy to compute. Considering the compactness and separation of data set, Fukuyama and Sugeno [9] and Xie and Beni [10] proposed FS and XB indices, respectively. Kwon extended Xie and Beni’s index to eliminate its tendency to monotonically decrease by introducing a punishing function in Xie and Benis original validity index [11]. Based on the concepts of hypervolume and density, Gath and Geva [12] put forward the fuzzy hypervolume validity FHV. The introduction of the concepts of fuzzy compactness and fuzzy separation to the traditional validity indices allows Zahid et al. to propose a novel index to evaluate the fitness of partitions produced by fuzzy clustering algorithms [13]. Wu and Yang use the factors from a normalized partition coefficient and an exponential separation measure for each cluster and then pool these two factors to create the PCAES validity index [14]. They also discussed the problem that the validity indexes face in a noisy environment. By solving the maximum value of PBMF index, Pakhira et al. [15] measured the goodness of clustering on different partitions of a data set.Table 1
Some validity indices based on FCM algorithm.
Name and reference
Index
Bezdek [5]
PC
=
1
n
∑
j
=
1
n
∑
i
=
1
C
u
i
j
2
Bezdek [6]
PE
=
-
1
n
∑
j
=
1
n
∑
i
=
1
C
u
i
j
log
⁡
⁡
(
u
i
j
)
Dunn [7]
NPC
=
C
×
PC
-
1
C
-
1
=
(
c
/
n
)
∑
j
=
1
n
‍
∑
i
=
1
C
‍
u
i
j
2
-
1
C
-
1
Roubens [8]
NPE
=
n
×
PE
n
-
C
=
-
∑
j
=
1
n
‍
∑
i
=
1
C
‍
u
i
j
log
⁡
⁡
(
u
i
j
)
n
-
C
Fukuyama and Sugeno [9]
FS
=
J
m
-
∑
j
=
1
n
∑
i
=
1
C
u
i
j
m
∥
c
i
-
c
-
∥
2
Gath and Geva [12]
FHV
=
∑
i
=
1
C
det
⁡
(
∑
j
=
1
n
‍
u
i
j
m
(
x
j
-
c
i
)
(
x
j
-
c
i
)
T
∑
j
=
1
n
‍
u
i
j
m
)
Xie and Beni [10]
XB
=
J
m
n
min
⁡
i
≠
j
∥
c
i
-
c
j
∥
2
Bensaid et al. [24]
BSC
=
∑
i
=
1
C
(
∑
j
=
1
n
‍
u
i
j
∥
x
j
-
c
i
∥
2
∑
j
=
1
n
‍
u
i
j
∑
k
=
1
C
‍
∥
c
i
-
c
k
∥
2
)
Kwon [11]
K
=
J
m
+
(
1
/
c
)
∑
i
=
1
C
‍
∥
c
i
-
c
-
∥
2
min
⁡
i
≠
j
∥
c
i
-
c
j
∥
2
Wu and Yang [14]
PCAES
=
∑
i
=
1
C
(
∑
j
=
1
n
‍
u
i
j
2
min
⁡
1
≤
i
≤
C
∑
j
=
1
n
‍
u
i
j
2
-
exp
⁡
(
-
C
min
⁡
k
≠
i
∥
c
i
-
c
k
∥
2
∑
l
=
1
C
‍
∥
c
l
-
c
-
∥
2
)
)
Zahid et al. [13]
ZSC
=
∑
i
=
1
C
‍
∥
c
i
-
c
-
∥
2
/
C
∑
i
=
1
C
‍
(
∑
j
=
1
n
‍
u
i
j
m
∥
x
j
-
c
i
∥
2
/
∑
j
=
1
n
‍
u
i
j
)
-
∑
i
=
1
C
-
1
‍
∑
l
=
i
+
1
C
‍
(
∑
j
=
1
n
‍
(
min
⁡
(
u
i
j
,
u
l
j
)
)
2
/
∑
j
-
1
n
‍
min
⁡
(
u
i
j
,
u
l
j
)
)
∑
j
=
1
n
‍
(
max
⁡
1
≤
i
≤
C
u
i
j
)
2
/
∑
j
=
1
n
‍
max
⁡
1
≤
i
≤
C
u
i
j
Pakhira et al. [15]
PBMF
=
(
1
C
×
∑
j
=
1
n
‍
u
i
j
∥
x
j
-
c
-
∥
∑
j
=
1
n
‍
∑
i
=
1
C
‍
(
u
i
j
)
m
∥
x
j
-
c
i
∥
×
C
max
i
,
j
=
1
⁡
⁡
∥
c
i
-
c
j
∥
)
2
Chen and Linkens [25]
P
=
1
n
∑
j
=
1
n
max
⁡
i
⁡
(
u
i
j
)
-
∑
i
=
1
C
-
1
‍
∑
k
=
i
+
1
C
‍
(
(
1
/
n
)
∑
j
=
1
n
‍
min
⁡
(
u
i
j
,
u
k
j
)
)
∑
i
=
1
C
-
1
‍
i
Bouguessa and Wang [26]
SCG
=
trace
(
∑
i
=
1
C
‍
∑
j
=
1
n
‍
u
i
j
m
(
c
i
-
c
-
)
(
c
i
-
c
-
)
T
)
∑
i
=
1
C
‍
trace
(
∑
j
=
1
n
‍
u
i
j
m
(
x
j
-
c
i
)
(
x
j
-
c
i
)
T
/
∑
j
=
1
n
‍
u
i
j
m
)
wherec
-
=
(
1
/
n
)
∑
j
=
1
n
x
j in above indices.In general, an optimal cluster numberc can be found by solving maximum or minimum of theses indices, respectively, to produce the best clustering performance for the data set X.


### 2.2. The Bipartite Network

Networks have attracted a burst of attention in the last decade, with applications to natural, social, and technological networks. To understand the nature of a complex system, a common approach is to map the interconnected objects in the complex system to a complex network and study the structure of the complex network. Many real-world networks display natural bipartite structure. Examples include the actors-films network and the papers-scientists network [16, 17]. Because one-mode projection of bipartite networks will bring some drawbacks and affect the properties of the networks, it is an important problem to directly analyze the original bipartite networks. In bipartite networks, there are two nonoverlapping sets of nodes called top nodes and bottom nodes. The edges only connect a pair of vertices which belong to different sets.One of the common characteristics of many bipartite networks is their community structures which are seen as groups of nodes within which connections are dense and between which connections are sparse. Although the notion of community structure is straightforward, construction of an efficient algorithm for identification of the community structure in a bipartite network is highly nontrivial. A number of algorithms for detecting the communities have been developed, each of them attempts to uncover a reasonable good partition of the network. To measure the division quality of a network, various modularity functions have been suggested. Using the modularity, the quality of any assignment of vertices to modules can be assessed. Guimerà et al. [18] proposed a projection based method. It transforms the bipartite network into an one-mode network and uses method for one-mode network to discover communities. They strikingly demonstrated that the analysis of a projection can give incorrect results in a model network. It will affect the properties including the community structures of the networks. Barber [19] extended the Newmans modularity to bipartite network and proposed a method searching communities by minimizing the modularity. The algorithm is based on the idea that the modules in the two parts of the network are dependent, with each part mutually being used to induce the vertices for the other part into the modules. To resolve communities in bipartite networks, Xu et al. [20] proposed an MDL 21 criterion for identifying a good partition of a bipartite network. Recently, a new measurement for community extraction from bipartite networks is proposed which is a straightforward generalization of Newman’s modularity [21].


## 2.1. Some Cluster Validity Indices

The purpose of clustering algorithm is to divide the given data setX
=
{
x
1
,
x
2
,
…
,
x
n
} into groups X
1
,
X
2
,
…
,
X
c. The partition matrix U of size c
×
n may be represented as U
=
[
u
i
j
], i
=
1,2
,
…
,
c and j
=
1,2
,
…
,
n, where u
i
j is the membership of sample x
j to cluster X
i. In the case of crisp partitioning, the following condition should be satisfied: u
i
j
=
1 if x
j
∈
X
i; otherwise, u
i
j
=
0 [4].Formally, the goal of clustering analysis can be represented as follows:(1)
⋃
i
=
1
c
X
i
=
X
,
X
i
≠
∅
,
i
=
1,2
,
…
,
c
,
X
i
∩
X
j
=
0
,
i
=
1,2
,
…
,
c
,
j
=
1,2
,
…
,
n
.In the case of fuzzy clustering, the membershipu
i
j is in interval [
0,1
]. The crisp clustering may be viewed as a special case of fuzzy clustering.No matter what, we take crisp partitioning method or fuzzy clustering algorithm to separate data set into groups, the generated partitions may not reflect the desired clustering of the data because of inappropriate choice of algorithmic parameters. Thus, it is a key problem how to determine the cluster numberc, especially for real data sets. Clustering is an unsupervised classification process and therefore it has no a priori information of a data set. That is to say that user has no prior knowledge about the number of classes. For two-dimensional data or data set with small size, it is possible to visually verify the validity of the results. However, the visualization of the data set in high dimensional space or with huge size would be difficult. Thus it is difficult to partition the given data set into clusters which best fit the natural distribution of the data set.To find the optimal cluster numberc, the researchers proposed some validity indices based on fuzzy cluster result obtained by FCM algorithm. Once the partition is obtained by a clustering method, the validity function can help us to validate whether it accurately presents the structure of the data set or not. In Table 1, some popular validity indices are listed. The earliest proposed fuzzy cluster validity functions associated with FCM are the partition coefficient (PC) and partition entropy (PE) [5, 6]. NPC and NPE, modification of the PC and PE, proposed by Dunn and Roubens [7, 8] in succession. These indices only use the membership values and have the advantage of being easy to compute. Considering the compactness and separation of data set, Fukuyama and Sugeno [9] and Xie and Beni [10] proposed FS and XB indices, respectively. Kwon extended Xie and Beni’s index to eliminate its tendency to monotonically decrease by introducing a punishing function in Xie and Benis original validity index [11]. Based on the concepts of hypervolume and density, Gath and Geva [12] put forward the fuzzy hypervolume validity FHV. The introduction of the concepts of fuzzy compactness and fuzzy separation to the traditional validity indices allows Zahid et al. to propose a novel index to evaluate the fitness of partitions produced by fuzzy clustering algorithms [13]. Wu and Yang use the factors from a normalized partition coefficient and an exponential separation measure for each cluster and then pool these two factors to create the PCAES validity index [14]. They also discussed the problem that the validity indexes face in a noisy environment. By solving the maximum value of PBMF index, Pakhira et al. [15] measured the goodness of clustering on different partitions of a data set.Table 1
Some validity indices based on FCM algorithm.
Name and reference
Index
Bezdek [5]
PC
=
1
n
∑
j
=
1
n
∑
i
=
1
C
u
i
j
2
Bezdek [6]
PE
=
-
1
n
∑
j
=
1
n
∑
i
=
1
C
u
i
j
log
⁡
⁡
(
u
i
j
)
Dunn [7]
NPC
=
C
×
PC
-
1
C
-
1
=
(
c
/
n
)
∑
j
=
1
n
‍
∑
i
=
1
C
‍
u
i
j
2
-
1
C
-
1
Roubens [8]
NPE
=
n
×
PE
n
-
C
=
-
∑
j
=
1
n
‍
∑
i
=
1
C
‍
u
i
j
log
⁡
⁡
(
u
i
j
)
n
-
C
Fukuyama and Sugeno [9]
FS
=
J
m
-
∑
j
=
1
n
∑
i
=
1
C
u
i
j
m
∥
c
i
-
c
-
∥
2
Gath and Geva [12]
FHV
=
∑
i
=
1
C
det
⁡
(
∑
j
=
1
n
‍
u
i
j
m
(
x
j
-
c
i
)
(
x
j
-
c
i
)
T
∑
j
=
1
n
‍
u
i
j
m
)
Xie and Beni [10]
XB
=
J
m
n
min
⁡
i
≠
j
∥
c
i
-
c
j
∥
2
Bensaid et al. [24]
BSC
=
∑
i
=
1
C
(
∑
j
=
1
n
‍
u
i
j
∥
x
j
-
c
i
∥
2
∑
j
=
1
n
‍
u
i
j
∑
k
=
1
C
‍
∥
c
i
-
c
k
∥
2
)
Kwon [11]
K
=
J
m
+
(
1
/
c
)
∑
i
=
1
C
‍
∥
c
i
-
c
-
∥
2
min
⁡
i
≠
j
∥
c
i
-
c
j
∥
2
Wu and Yang [14]
PCAES
=
∑
i
=
1
C
(
∑
j
=
1
n
‍
u
i
j
2
min
⁡
1
≤
i
≤
C
∑
j
=
1
n
‍
u
i
j
2
-
exp
⁡
(
-
C
min
⁡
k
≠
i
∥
c
i
-
c
k
∥
2
∑
l
=
1
C
‍
∥
c
l
-
c
-
∥
2
)
)
Zahid et al. [13]
ZSC
=
∑
i
=
1
C
‍
∥
c
i
-
c
-
∥
2
/
C
∑
i
=
1
C
‍
(
∑
j
=
1
n
‍
u
i
j
m
∥
x
j
-
c
i
∥
2
/
∑
j
=
1
n
‍
u
i
j
)
-
∑
i
=
1
C
-
1
‍
∑
l
=
i
+
1
C
‍
(
∑
j
=
1
n
‍
(
min
⁡
(
u
i
j
,
u
l
j
)
)
2
/
∑
j
-
1
n
‍
min
⁡
(
u
i
j
,
u
l
j
)
)
∑
j
=
1
n
‍
(
max
⁡
1
≤
i
≤
C
u
i
j
)
2
/
∑
j
=
1
n
‍
max
⁡
1
≤
i
≤
C
u
i
j
Pakhira et al. [15]
PBMF
=
(
1
C
×
∑
j
=
1
n
‍
u
i
j
∥
x
j
-
c
-
∥
∑
j
=
1
n
‍
∑
i
=
1
C
‍
(
u
i
j
)
m
∥
x
j
-
c
i
∥
×
C
max
i
,
j
=
1
⁡
⁡
∥
c
i
-
c
j
∥
)
2
Chen and Linkens [25]
P
=
1
n
∑
j
=
1
n
max
⁡
i
⁡
(
u
i
j
)
-
∑
i
=
1
C
-
1
‍
∑
k
=
i
+
1
C
‍
(
(
1
/
n
)
∑
j
=
1
n
‍
min
⁡
(
u
i
j
,
u
k
j
)
)
∑
i
=
1
C
-
1
‍
i
Bouguessa and Wang [26]
SCG
=
trace
(
∑
i
=
1
C
‍
∑
j
=
1
n
‍
u
i
j
m
(
c
i
-
c
-
)
(
c
i
-
c
-
)
T
)
∑
i
=
1
C
‍
trace
(
∑
j
=
1
n
‍
u
i
j
m
(
x
j
-
c
i
)
(
x
j
-
c
i
)
T
/
∑
j
=
1
n
‍
u
i
j
m
)
wherec
-
=
(
1
/
n
)
∑
j
=
1
n
x
j in above indices.In general, an optimal cluster numberc can be found by solving maximum or minimum of theses indices, respectively, to produce the best clustering performance for the data set X.


## 2.2. The Bipartite Network

Networks have attracted a burst of attention in the last decade, with applications to natural, social, and technological networks. To understand the nature of a complex system, a common approach is to map the interconnected objects in the complex system to a complex network and study the structure of the complex network. Many real-world networks display natural bipartite structure. Examples include the actors-films network and the papers-scientists network [16, 17]. Because one-mode projection of bipartite networks will bring some drawbacks and affect the properties of the networks, it is an important problem to directly analyze the original bipartite networks. In bipartite networks, there are two nonoverlapping sets of nodes called top nodes and bottom nodes. The edges only connect a pair of vertices which belong to different sets.One of the common characteristics of many bipartite networks is their community structures which are seen as groups of nodes within which connections are dense and between which connections are sparse. Although the notion of community structure is straightforward, construction of an efficient algorithm for identification of the community structure in a bipartite network is highly nontrivial. A number of algorithms for detecting the communities have been developed, each of them attempts to uncover a reasonable good partition of the network. To measure the division quality of a network, various modularity functions have been suggested. Using the modularity, the quality of any assignment of vertices to modules can be assessed. Guimerà et al. [18] proposed a projection based method. It transforms the bipartite network into an one-mode network and uses method for one-mode network to discover communities. They strikingly demonstrated that the analysis of a projection can give incorrect results in a model network. It will affect the properties including the community structures of the networks. Barber [19] extended the Newmans modularity to bipartite network and proposed a method searching communities by minimizing the modularity. The algorithm is based on the idea that the modules in the two parts of the network are dependent, with each part mutually being used to induce the vertices for the other part into the modules. To resolve communities in bipartite networks, Xu et al. [20] proposed an MDL 21 criterion for identifying a good partition of a bipartite network. Recently, a new measurement for community extraction from bipartite networks is proposed which is a straightforward generalization of Newman’s modularity [21].


## 3. The Fuzzyc-Means Clustering Algorithm

The most commonly used fuzzy clustering method should be fuzzyc-means algorithm. The purpose of fuzzy clustering is to divide the data set into c distinct clusters. The fuzzy c-means (FCM) algorithm is proposed by Dunn [22] and then extended by Bezdek [23]. Formally, the FCM algorithm can be expressed as follows.LetX
=
{
x
1
,
…
,
x
n
} be a data set with n points in P-dimensional feature space R
P, X
⊂
R
P. The FCM clustering algorithm partitions X into 1
<
c
<
n fuzzy groups by minimizing objective function J
m which is the weighted sum of squared errors within groups and is defined as follows:
(2)
J
m
(
U
,
X
)
=
∑
j
=
1
n
∑
i
=
1
c
u
i
j
m
∥
x
j
-
v
i
∥
A
2
,
1
<
m
<
∞
,
and subject to
(3)
u
i
j
∈
[
0,1
]
,
∑
i
=
1
c
u
i
j
=
1
,
where U
=
[
u
i
j
]
c
×
n is a fuzzy partition matrix composed of the degree of membership of data point x
j to ith cluster; (
v
1
,
v
2
,
…
,
v
c
) is a vector of unknown cluster prototype (centers), v
i
∈
R
P. A norm matrix A defines a measure of similarity between a data point and the cluster prototypes. The parameter m controls the fuzziness of membership of each datum. The cluster centroids and the respective membership functions, which are solutions of the constrained optimization problem in (2) are given by the following equations:
(4)
u
i
j
=
1
∑
k
=
1
c
(
∥
x
j
-
v
i
∥
A
/
∥
x
j
-
v
k
∥
A
)
2
/
(
m
-
1
)
,
1
≤
i
≤
c
,
1
≤
j
≤
n
,
(5)
v
i
=
∑
j
=
1
n
u
i
j
m
x
j
∑
j
=
1
n
u
i
j
m
,
1
≤
i
≤
c
.
Equations (4) and (5) constitute an iterative optimization procedure.The FCM algorithm is executed in the following stepsStep 1.
Given a preselectedc clustering centroids (
v
1
,
v
2
,
…
,
v
c
) and fuzzy factor m
(
m
>
1
), initialize the fuzzy partition matrix U.Step 2.
Calculate the fuzzy clustering centroidv
i using (5).Step 3.
Use (4) to update the fuzzy membership matrix U.Step 4.
If the improvement inJ
m
(
U
,
X
) is less than a certain threshold (
ε
), then stop; otherwise, go to Step 2.


## 4. The Improved Bipartite Modularity and the Proposed Method

### 4.1. The Bipartite Modularity

Very recently, Murata [21] introduced a bipartite modularity to assess the partitioning quality of a given bipartite network. Murata’s bipartite modularity can be depicted as follows.SupposeG is an unweighted bipartite network, whose vertices V is divided into two disjoint sets, V
t and V
b, such that every edge in the network connects a node from one set from the other. Here, a bipartite network is denoted as G
=
(
V
t
,
V
b
,
E
) and top nodes and bottom nodes are called as V
t and V
b, respectively. Conveniently, we denote the top nodes by X-vertices {
x
1
,
…
,
x
n
}, and Y-vertices the bottom nodes {
y
1
,
…
,
y
p
}.Let us suppose thatM is the number of edges in a bipartite network. Consider a particular division of the bipartite network into X-vertex communities and Y-vertex communities, and the numbers of the communities are L
t and L
b, respectively. V
i
t and V
j
b are the individual community that belong to the sets V
t
=
{
V
1
t
,
V
2
t
,
…
,
V
L
t
t
} and V
b
=
{
V
1
b
,
V
2
b
,
…
,
V
L
b
b
}, respectively. A
(
i
,
j
) is an adjacency matrix of the network whose element (
i
,
j
) is equal to 1 if vertices i and j are connected and is equal to 0 otherwise.Under the condition that the vertices ofV
l and V
s are different types (which means (V
l
∈
V
t
∧
V
s
∈
V
b
)
∨
(
V
l
∈
V
b
∧
V
s
∈
V
t
)), e
l
m (the fraction of all edges that connect vertices in V
l to vertices in V
s) and a
i (its row sums) are defined as follows:
(6)
e
l
m
=
1
2
M
∑
i
∈
V
l
∑
j
∈
V
s
A
(
i
,
j
)
,
a
i
=
∑
j
e
i
j
=
1
2
M
∑
i
∈
V
l
∑
j
∈
V
s
A
(
i
,
j
)
.
The bipartite modularity Q
B is defined as
(7)
Q
B
=
∑
i
(
e
i
j
-
a
i
a
j
)
,
j
=
max
⁡
k
(
e
i
k
)
.HighQ
B value indicates strong community structure in a bipartite network.


### 4.2. The Proposed Method

For the given data set, the FCM algorithm with a proper distance norm is employed to partition it into clusters. After we have obtained the membership degree matrix, one can construct a weighted bipartite network whose top nodes consist of all clustering centers and bottom nodes are made up of all samples. The membership degrees can be thought as its weighted edges. Obviously, it will produce a fully connected bipartite network.Example 1.
If one partitions the given data set described in Figure1(a) by FCM algorithm for c
=
3, a membership degree matrix is obtained. In terms of the idea mentioned above, a weighted bipartite network will easily be constructed. The top nodes consist of three clustering centers and bottom nodes are made up of ten samples. The numbers in Figure 1(b) stands for the weights on each edge in network.The data set and a weighted bipartite network.
(a)
(b)In this case, the bipartite modularity defined in (7) can not be used to measure the quality of partitioning network because the Q
B in (7) is only useful to the unweighted bipartite network. Therefore, it is necessary to improve Q
B so as to deal with weighted bipartite network.If we define(8)
L
t
=
L
b
=
C
,
V
i
t
=
{
v
i
}
,
V
j
b
=
{
x
i
∣
u
j
i
=
max
⁡
k
(
u
k
i
)
}
,
M
=
∑
i
=
1
C
‍
∑
j
=
1
n
‍
u
j
i
,
one can successfully extend the bipartite modularity Q
B to the weighted bipartite network which is constructed by FCM algorithm.In what follows, an algorithm on how to partition a given data into ideal groups is described.Input: data setS; threshold ε (used in FCM algorithm);
Output: the optimal clustering result.
Step 1: execute FCM algorithm for the given data set;
Step 2: construct a weighted bipartite network by matrix of membership degreeU and clustering centroids v
i according to (8).
Step 3: calculate the improved bipartite modularityQ
B.Fromc
=
2 to c
max
⁡, repeat the above process. Among these values, it is easy to find the maximum value of Q
B. Generally, C
max
⁡ is unknown. Conventionally, one can take C
max
⁡
=
n which is widely used in clustering analysis.


## 4.1. The Bipartite Modularity

Very recently, Murata [21] introduced a bipartite modularity to assess the partitioning quality of a given bipartite network. Murata’s bipartite modularity can be depicted as follows.SupposeG is an unweighted bipartite network, whose vertices V is divided into two disjoint sets, V
t and V
b, such that every edge in the network connects a node from one set from the other. Here, a bipartite network is denoted as G
=
(
V
t
,
V
b
,
E
) and top nodes and bottom nodes are called as V
t and V
b, respectively. Conveniently, we denote the top nodes by X-vertices {
x
1
,
…
,
x
n
}, and Y-vertices the bottom nodes {
y
1
,
…
,
y
p
}.Let us suppose thatM is the number of edges in a bipartite network. Consider a particular division of the bipartite network into X-vertex communities and Y-vertex communities, and the numbers of the communities are L
t and L
b, respectively. V
i
t and V
j
b are the individual community that belong to the sets V
t
=
{
V
1
t
,
V
2
t
,
…
,
V
L
t
t
} and V
b
=
{
V
1
b
,
V
2
b
,
…
,
V
L
b
b
}, respectively. A
(
i
,
j
) is an adjacency matrix of the network whose element (
i
,
j
) is equal to 1 if vertices i and j are connected and is equal to 0 otherwise.Under the condition that the vertices ofV
l and V
s are different types (which means (V
l
∈
V
t
∧
V
s
∈
V
b
)
∨
(
V
l
∈
V
b
∧
V
s
∈
V
t
)), e
l
m (the fraction of all edges that connect vertices in V
l to vertices in V
s) and a
i (its row sums) are defined as follows:
(6)
e
l
m
=
1
2
M
∑
i
∈
V
l
∑
j
∈
V
s
A
(
i
,
j
)
,
a
i
=
∑
j
e
i
j
=
1
2
M
∑
i
∈
V
l
∑
j
∈
V
s
A
(
i
,
j
)
.
The bipartite modularity Q
B is defined as
(7)
Q
B
=
∑
i
(
e
i
j
-
a
i
a
j
)
,
j
=
max
⁡
k
(
e
i
k
)
.HighQ
B value indicates strong community structure in a bipartite network.


## 4.2. The Proposed Method

For the given data set, the FCM algorithm with a proper distance norm is employed to partition it into clusters. After we have obtained the membership degree matrix, one can construct a weighted bipartite network whose top nodes consist of all clustering centers and bottom nodes are made up of all samples. The membership degrees can be thought as its weighted edges. Obviously, it will produce a fully connected bipartite network.Example 1.
If one partitions the given data set described in Figure1(a) by FCM algorithm for c
=
3, a membership degree matrix is obtained. In terms of the idea mentioned above, a weighted bipartite network will easily be constructed. The top nodes consist of three clustering centers and bottom nodes are made up of ten samples. The numbers in Figure 1(b) stands for the weights on each edge in network.The data set and a weighted bipartite network.
(a)
(b)In this case, the bipartite modularity defined in (7) can not be used to measure the quality of partitioning network because the Q
B in (7) is only useful to the unweighted bipartite network. Therefore, it is necessary to improve Q
B so as to deal with weighted bipartite network.If we define(8)
L
t
=
L
b
=
C
,
V
i
t
=
{
v
i
}
,
V
j
b
=
{
x
i
∣
u
j
i
=
max
⁡
k
(
u
k
i
)
}
,
M
=
∑
i
=
1
C
‍
∑
j
=
1
n
‍
u
j
i
,
one can successfully extend the bipartite modularity Q
B to the weighted bipartite network which is constructed by FCM algorithm.In what follows, an algorithm on how to partition a given data into ideal groups is described.Input: data setS; threshold ε (used in FCM algorithm);
Output: the optimal clustering result.
Step 1: execute FCM algorithm for the given data set;
Step 2: construct a weighted bipartite network by matrix of membership degreeU and clustering centroids v
i according to (8).
Step 3: calculate the improved bipartite modularityQ
B.Fromc
=
2 to c
max
⁡, repeat the above process. Among these values, it is easy to find the maximum value of Q
B. Generally, C
max
⁡ is unknown. Conventionally, one can take C
max
⁡
=
n which is widely used in clustering analysis.


## 5. Experiments

To validate the introduced method, we would like to test it on seven artificial data sets [27–29] and seven well-known real data sets [30, 31] which are widely used to test the validity of various indices and clustering algorithm. Meanwhile, we also compare the results obtained by the proposal with those achieved by a number of popular validation indices on these data sets. The experimental platform is based on Windows 7 with Intel Core 2 Duo CPU T9550 @ 2.66 GHz 2.67 GHz and 4.00 GB memory. The clustering parameters m and the default minimum amount of improvement in FCM are taken 2.0 and e
-
5, respectively.The names of seven artificial data sets imply the dimension of the samples and the actual cluster numbers in the data sets. For example, in the elliptical_2_10 data set, the samples with 10 classes are in 2-dimensional space. The information about seven artificial data sets and seven well-known real data sets are listed in Table2. The authors can also browse the web page http://www.isical.ac.in/~sanghami/data.html and http://archive.igbmc.fr/projets/fcm/#datasets to see them in detail.Table 2
Fourteen artificial and real data sets.
(a)
Seven artificial data sets
Dataset
Clusters
Attributes
Nodes
elliptical_2_10
10
2
500
spherical_2_5
5
2
250
spherical_2_6
6
2
300
spherical_3_4
4
3
400
st900_2_9
9
2
900
y_10_14
14
10
480
y_2_3
3
2
300
(b)
Seven real data sets
Dataset
Clusters
Attributes
Nodes
bupa_7_2
2
7
345
glass_9_6
6
9
214
ionosphere_32_2
2
32
351
iris_4_3
3
4
150
pima_8_2
2
8
768
wall-following_4_4
4
4
5456
wbcd_8_2
2
8
699The optimal cluster numbers detected by our method and the other four indices are listed in Table3. As it can be seen that 11 ideal optimal cluster numbers on 14 data sets can be found. The data set spherical_2_6 and spherical_3_4 are well separated so that the practical class numbers 6 and 4 can be found by all indices. The fact that there are no apparent borders among clusters for the rest of the artificial data sets leads to produce the improper cluster numbers, especially for y_2_3 and spherical_2_5. From Figure 2, one can find that the distinct change of values of five indices occur when c
=
6. This case exactly corresponds to the natural distribution of samples in spherical_2_6. The scatter diagram of y_2_3 in Figure 3(a) shows that three clusters overlap each other. That is to say that there is no clear borderline among these three classes. Thus it is difficult to partition them into three clusters. The correct cluster number 3 is discovered by our method and index NPC.Table 3
Indices comparable for data sets.
DataSet
Clusters
Q
B
PC
NPC
PE
NPE
elliptical_2_10
10
10
2
10
2
2
spherical_2_5
5
5
2
4
2
2
spherical_2_6
6
6
6
6
6
6
spherical_3_4
4
4
4
4
4
4
st900_2_9
9
9
2
9
2
2
y_10_14
14
15
12
12
15
15
y_2_3
3
3
2
3
2
2
bupa_6_2
2
2
2
2
2
2
glass_9_6
6
4
2
2
2
2
ionosphere_32_2
2
2
2
2
2
2
iris_4_3
3
3
2
2
2
2
pima_8_2
2
3
2
2
2
3
wall-following_4_4
4
4
2
4
2
2
wbcd_8_2
2
2
2
2
2
2The scatter diagram of spherical_2_6 and the comparison of the proposal with the other four indices.
(a)
Spherical_2_6
(b)
The line charts of five indices on spherical_2_6The scatter diagram of y_2_3 and the comparison of the proposal with the other four indices.
(a)
y_2_3
(b)
The change of values of five indices with cluster number for y_2_3The selected seven real data sets are typical data sets which are usually employed to test the validity of clustering/classifying algorithms or cluster index. The dimensions of these data sets range from 4 to 32. That is to say that it is impossible to estimate whether the obtained cluster results are good or not by visualizing method. Furthermore, the clusters of some data sets are heavily overlapped. Therefore, it is difficult to detect the optimal cluster number of these seven data sets by the validity index. More information about these data sets can be found in [31].In Figure4, the comparison results are obtained by the proposed method and other four indices on these real data sets. It is easily to see that there exists the distinct difference of Q
B value between the maximum value and others on bupa_6_2, ionosphere_32_2, wbcd_8_2, and wall-following_4_4. Thus the optimal cluster numbers are unanimously detected by the proposed method. This is also true for the other four indices except wall-following_4_4. The Q
B value on iris_4_3, glass_9_6, and pima_8_2 are close to each other when c
=
2, c
=
3, and c
=
4. This implies that it is reasonable, while one partitions these three data sets into 2 or 3 or 4 clusters. Iris data set is a typical example where there are three classes, but looking at the data without the class information, one could also argue that there are two and not three clusters. Fortunately, the optimal cluster number 3 is found for Iris data set. These examples also show that the proposal is superior to other four indices.The comparison of the proposal with the other four indices on real data sets.
(a)
bupa_6_2
(b)
glass_9_6
(c)
ionosphere_32_2
(d)
iris_4_3
(e)
pima_8_2
(f)
wall-following_4_4
(g)
wbcd_8_2


## 6. Conclusions

In this paper, a method is proposed to detect an optimal cluster number for a given data set without any class information. The key idea of this paper is to convert the problem of detecting the optimal cluster number on a data set into the one of finding the optimum community structure in a weighted bipartite network. One of the advantage of the introduced method is to implement the automatic learning process of un-supervised classifying algorithm. The experimental results show the validity of the proposed method. The comparison results indicate that our proposal is superior to the other four indices which are only related to membership obtained by FCM algorithm. However, nonspherical cluster of data set and overlap structure will still affect the cluster results. Therefore it is worthwhile to try to construct or propose new method or index to find the optimal class structure of data set.



---

*Source: 676427-2014-02-10.xml*