Memetic Clustering Based on Particle Swarm Optimizer and K

WCCI 2012 IEEE World Congress on Computational Intelligence
June, 10-15, 2012 - Brisbane, Australia
IEEE CEC
Memetic Clustering Based on Particle Swarm
Optimizer and K-Means
Zexuan Zhu1 , Member, IEEE, Wenmin Liu1 , Shan He2 , and Zhen Ji1 , Member, IEEE
1
Shenzhen City Key Laboratory of Embedded System Design
College of Computer Science and Software Engineering
Shenzhen University, Shenzhen, China 518060
2
School of Computer Science
University of Birmingham, Edgbaston, Birmingham, B15 2TT, UK
Abstract—This paper proposes an efficient memetic clustering
algorithm (MCA) for clustering based on particle swarm optimizer (PSO) and K-means. Particularly, PSO is used as a global
search to allow fast exploration of the candidate cluster centers.
PSO has strong ability to find high quality solutions within
tractable time, but it suffers from slow-down convergence as the
swarm approaching optima. K-means, achieving fast convergence
to optimum solutions, is utilized as local search to fine-tune the
solutions of PSO in the framework of memetic algorithm. The
performance of MCA is evaluated on four synthetic datasets
and three high-dimensional gene expression datasets. Comparison
study to K-means, PSO, and PSO-KM (jointed PSO and Kmeans) indicates that MCA is capable of identifying cluster
centers more precisely and robustly than the other counterpart
algorithms by taking advantage of both PSO and K-means.
I. I NTRODUCTION
Clustering is a common unsupervised learning technique for
statistical data analysis. It aims to categorize observations into
groups (also known as clusters) based on similarities so that
the inherent property of the data can be discovered. Clustering algorithms mainly fall into two groups: hierarchical and
partitional methods. Hierarchical clustering [1] organizes data
samples in a hierarchical tree using either agglomerative or
divisive approach. Partitional clustering [2] seeks to determine
all samples into a set of non-overlapping clusters at once,
so as to optimize some evaluation of the clustering. Both
hierarchical and partitional methods have achieved promising
results on numerous clustering problems. On high-dimensional
data such as gene expression and text data, partitional methods
are shown to be better choices and they tend to obtain better
performance than hierarchical clustering [3], [4].
A key issue of partitional clustering is to optimize the evaluation of cluster partition. For example, K-means [2], the most
commonly used partitional clustering method, proceeds to
This work was supported in part by the National Natural Science Foundation
of China, under Grants 61171125, 61001185, and 61102119, in part by the
NSFC-RS joint project, in part by the Fok Ying-Tung Education Foundation,
Guangdong Natural Science Foundation, under Grant 10151806001000002, in
part by the Foundation for Distinguished Young Talents in Higher Education
of Guangdong, under Grant LYM10113, in part by Scientific Research Foundation for the Returned Overseas Chinese Scholars, Ministry of Education of
China, and in part by the Shenzhen City Foundation for Distinguished Young
Scientists. All correspondence should be addressed to Prof. Zhen Ji (Email:
[email protected], Tel.: +86 755 26557413).
U.S. Government work not protected by U.S. copyright
categorize data samples into K groups while minimizing intracluster variance. K-means is popular owning to its simplicity
and efficiency, whereas it has some drawbacks such as: 1) it
needs a predefined number of clusters k, 2) its performance
is sensitive to the choice of initial clustering centers and it
could easily be trapped in local minima, 3) it can deal only
with clusters with spherical symmetrical point distribution.
Computational intelligence techniques provide another kind
of solutions to solve the optimization problems involved in
partitional clustering. Among them, PSO is one of the most
widely used for clustering. Inspired by social interaction of
bird flocking or fish schooling, PSO was first proposed by Dr.
Eberhart and Dr. Kennedy in 1995 [5] as a population-based
stochastic optimization technique. It is easy to implement with
only few parameters and model equations. PSO has been
successfully applied on many clustering problems [6]–[12]
thanks to its key advantages. PSO is a powerful global search
method and robust to the random initialization, but it suffers
from slow-down of convergence as the swarm approaching
optima [13].
In this study, a memetic clustering algorithm (MCA) is
proposed based on PSO and K-means to take advantage of
both. Memetic algorithm (MA) [14] is commonly known
as a synergy of evolutionary population-based global search
approaches with separate lifetime learning process, where the
latter is also known as local refinement heuristic or meme. MA
is shown to converge to high-quality solutions more efficiently
than its conventional counterpart thanks to the advantage of
using both global search and local search [14]–[22]. MCA
is not designed to solve all issues of K-means and PSO
based clustering, but focuses on relieving the dependence of
the clustering performance on initialization and accelerating
the convergence to more accurate cluster centers. Particularly,
MCA is designed to evolve a particle swarm of candidate
cluster centers while minimizing the intra-cluster variance.
The dependency of the performance on initialization and the
possibility being trapped in local optimal are reduced by using
PSO based global search. A K-means based local search
is applied on each particle to refine the PSO solutions and
accelerate the convergence in local region. The performance
of MCA is evaluated on four synthetic and three gene expression datasets. MCA is observed to identify more precise
cluster centers with better clustering performance than other
counterpart algorithms.
The remainder of this paper is organized as follows. Section
II describes the details of the proposed MCA. Section IV
shows the experimental results of the new algorithm on four
synthetic and three gene expression datasets. Finally, Section
V concludes this study.
velocity of the a particle in the search space are represented as
Pi = [pi1 , pi2 , ...pij ..., piN ] and Vi = [vi1 , vi2 , ...vij ..., viN ],
respectively. CLPSO updates the velocity and position of the
ith particle based on:
II. M EMETIC C LUSTERING A LGORITHM
MA is a framework for combining global search and local
search to take the advantage of both. The main inspiration
of MA is Dawkins’ notion of “meme”, which defines a unit
of cultural evolution and represents the evolution law of
human beings. In this study, a MA based clustering method is
proposed to accelerate the search convergence of the cluster
centers and increase the chances of identifying global optima.
The procedure of MCA is outlined in Algorithm 1.
where w is the inertia weight proposed by Shi and Eberhart
[24] to balance the exploration and exploitation on the search
space, c is an acceleration constant, rij denotes a random
number in [0, 1], and pbest(fij )j represents the jth dimension
of the exemplar particle’s pbest. The index fij of the exemplar
particle is decided using Algorithm 2.
Algorithm 1 The procedure of MCA
1: Initialize the position and velocity of each particle in PSO
swarm;
2: while Stopping criteria are not satisfied do
3:
Update the velocity and position of each particle according to (2) and (3);
4:
Evaluate the fitness of each particle;
5:
Perform the K-means based local search on each
particle;
6: end while
A. Particle Encoding and Fitness Calculation
In MCA, each particle is designed to encode the candidate
positions of K centers for a cluster partition. The position of
each particle Pi = [pi1 , pi2 , ...pij ..., piN ] is denoted as a vector
of N = K × L elements, where L denotes the dimension of a
data sample. The fitness of each particle is evaluated based on
the mean square error (MSE), also known as the intra-cluster
variance:
M
∑
˜= 1
D
[d min (xi )]2
M i=1
(1)
where dmin (xi ) denotes the Euclidean distance between sample
xi to its closest center encoded in the particle and M is the
total number of samples.
B. PSO based Global Search
The global search in MCA is performed based on the comprehensive learning PSO (CLPSO) proposed by Liang et al.
[23]. CLPSO is one of PSO variants attempting to mitigate the
issue of premature convergence. Particularly, CLPSO enlarges
the search space of each particle using a novel comprehensive
learning strategy whereby all other particles’ historical best
information is used to update a particle’s velocity.
The particles of CLPSO cooperate and evolve using the
comprehensive learning strategy to search for the global optimum in the N -dimensional search space. The position and
vij = wvij + crij (pbest(fij )j − pij )
(2)
pij = pij + vij
(3)
Algorithm 2 Selection of learning exemplar
1: INPUT: pij ;
2: Calculate a learning probability based on Pl = 0.05 +
exp(
3:
4:
5:
6:
7:
8:
10(i−1)
)−1
ps−1
0.45 ∗ exp(10)−1
, where ps is the swarm size;
′
Generate a random number rij
in [0, 1];
′
if rij > Pl then
fij = i;
else
Randomly select two particles (excluding particle i)
from the swam and assign fij the one with better fitness.
end if
If ∀j ∈ {1, 2, . . . , N } fij = i, a randomly selected dimension is forced to learn from another particle’s pbest. Once
the exemplars for all dimensions of a particle are selected, the
particle keeps learning from these exemplars until a stagnation
of m generations is detected, then fij is renewed based on
Algorithm 2.
Unlike the conventional PSO which updates all dimensions
of a particle according to its own best previous position
pbest(i) and the global best position gbest, CLPSO updates
each dimension of a particle to learn from any counterpart
particle’s pbest, so that the swarm diversity is considerably
increased and the issue of premature convergence is mitigated.
For more details of CLPSO, the reader could refer to [23].
C. K-means based Local Search
In general, PSO is capable of exploring and exploiting
promising regions of the local search space, however, it
takes a relatively long time to locate the exact local optimum within the region of convergence [13]. To overcome
this problem, MCA adopts a K-means based local search
to fine-tune the cluster centers encoded in each PSO particle and accelerate the search convergence of the algorithm.
In particular, given a particle Pi , a K-means clustering is
initialized with each of the K centers encoded in position
Ck = [pi(kL−L+1) , pi(kL−L+2) , ..., pi(kL) ] and each data point
xj is assigned to the closest cluster based on Euclidean
distance measure:
√
(4)
Distance(xj , Ck ) = ∥xj − Ck ∥2

Download Report