IEEE Workshop on Nonlinear Circuit Networks
December 15-16, 2017

Parameter Setting of K-Means Clustering withModifying Firefly Algorithm
Masaki Takeuchi∗ , Thomas Ott† , Haruna Matsushita‡ , Yoko Uwate∗ and Yoshifumi Nishio∗∗ Department of Electrical and Electronic Engineering, Tokushima University

2-1 Minami-Josanjima, Tokushima, 770-8506, Japan
E-mail: {masaki, uwate, nishio}@ee.tokushima-u.ac.jp† Zurich University of Applied Sciences
Einsiedlerstrasse 31a, 8820 Waedenswil, Switzerland
E-mail: thomas.ott@zhaw.ch‡ Department of Electronics and Information Engineering, Kagawa University
2217-20 Hayashi-cho, Takamatsu, Kagawa, 761-0396, Japan
E-mail: haruna@eng.kagawa-u.ac.jp
Abstract—In 2011, Senthilnath et al. proposed to utilize theFirefly Algorithm for K-means clustering. The algorithm has
shown better results than the standard K-means algorithm orother combinations with bio-inspired optimization heuristics. In
this study, we propose a further improvement of the method,
based on an improved firefly algorithm. As a key aspect, therandomization parameter in our proposed algorithm is changed
when the assignment does not change. We compare the standard
K-means algorithm, K-means using the conventional Firefly
Algorithm and our proposed algorithm on the basis of a simple
data distribution. Numerical experiments show that our proposed
algorithm is more efficient than the other algorithms.

I. I NTRODUCTION
Clustering is a popular data analysis technique used fordata analysis, image analysis, data mining and the other fields
of science and engineering. The goal of clustering is to findhomogeneous groups of data points in a data set. Each groupis called a cluster and is characterized by the fact that objects
that belong to the same group are more similar than objects
that belong to different groups. The K-means algorithm is
one of the most famous clustering methods. It is used if
the number of clusters is known and the clusters tend to bespherical. The goal of the method is to find K cluster centers
and assign each object to the closest cluster center such thatthe sum of the squared distances between the objects and thecorresponding cluster centers is minimal. This means that theK-means clustering problem is an optimization problem.
Senthilnath et al. proposed an algorithm that used the fireflyalgorithm for K-means clustering (KMFA) [1]. Numericalexperiments have indicated that this algorithm is more efficientalgorithm than the standard algorithm or other optimization
heuristics. The Firefly Algorithm (FA) has been proposed by
Yang in 2007 and is based on the idealized behavior of theflashing characteristics of fireflies [2]. FA is an efficient optimization algorithm because it has a deterministic component
and a random component. Almost all algorithms having only
the deterministic component are local search algorithms, forwhich there is a risk of being trapped in a local optimum.

However, the random component makes it possible to escapefrom such a local optimum.
In our previous study, we proposed a new clustering
algorithm that combines K-means clustering and improved
Firefly Algorithm (KMIFA). In our proposed algorithm, one
parameter is changed when the assignment does not change[3]. We compared the conventional K-means algorithm, KMFA
and our proposed algorithm KMIFA using a 2-dimensional toy
data model. These experiments indicated that our algorithm
is more efficient than the other algorithms. However, for 3dimensional toy data model this algorithm cannot obtain abetter results than other algorithms. We improved the transition
rule of one parameter. Our proposed algorithm has new twoparameters. In the previous studies, we carried out computer
simulations with fixed parameters. Therefore, in this study, wesimulate a various patterns of this two parameters and intestate
their effects.
II. T HE C ONVENTIONAL M ETHODSIn this section, we explain the conventional K-means algorithm and the Firefly Algorithm (FA).
A. K-means algorithm
The objective function of K-means clustering is defined by
J=K ∑N∑bkn |ck − on |2 ,(1)k=1 n=1

where K is the number of cluster centers, N is the number ofobjects, ck is the position vector of cluster center k and on
is the position vector of object n. Each object is assigned toits nearest center. Hence bkn = 1 if object n is assigned tocenter k and bkn = 0 otherwise:{
1, object n is assigned to center k(2)bkn =0, otherwise
This optimization problem is solved using the K-means
algorithm which is composed of the following four steps:- 19 -Algorithm 1 The conventional Firefly Algorithm
Objective function f (x), x = (x1 , ..., xd )T
Initialize a population of fireflies xi (i = 1, 2, ..., n)while t < M axGeneration dofor i = 1 to n, all n fireflies dofor j = 1 to n, all n fireflies doLight intensity Ii at xi is determined by f (xi )if Ii > Ij thenMove firefly i towards j in all d dimensions
end ifAttractiveness varies with distance r via exp[−γr]Evaluate new solutions and update light intensity
end forj
end fori
Rank the fireflies and find the current best
end while
Postprocess results and visualization

1) Initialize all cluster centers and objects: The number ofcluster centers and all objects are predefined. All cluster
centers are randomly initialized in the search space.
2) Assignments: Each object is assigned to only the closest
cluster center.
3) Calculates cluster centers: The places of each cluster
center move to the mean of each group object.
4) Iterate steps 2 and 3 until the assignments no longerchange.
B. The Conventional Firefly Algorithm (FA)
FA has been developed by Yang and it was based on theidealized behavior of the flashing characteristics of fireflies[2]. Many researchers have paid attention to FA [4], [5]. The
conventional FA idealizes these flashing characteristics using
the following three rules:• All fireflies are unisex so that one firefly is attracted toother fireflies regardless of their sex.
•Attractiveness is proportional to brightness; thus, for
any two flashing fireflies, the less brighter one will
move towards the brighter one. Both the attractivenessand brightness stared above decrease as their distanceincreases. If no one is brighter than a particular firefly, it
moves randomly.

The brightness or light intensity of a firefly is affected ordetermined by the landscape of the objective function tobe optimized.
The attractiveness of a firefly β is defined by

Algorithm 2 KMFA
Initialize a population of fireflies xi (i = 1, 2, ..., Nf )Initialize a cluster centers ck (k = 1, 2, ..., Nc )Initialize a objects on (n = 1, 2, ..., No )while t < M axGeneration do
Each object is assigned the closest cluster center
calculate Ji (i = 1, 2, ..., N f )Light intensity Ii is determined by Ji
if Ii > Ij thenMove firefly i towards j
end ifFind the current best
end while
Postprocess results and visualization|Xmax − Xmin |,(5)2where γ is the light absorption coefficient, βmin is the minimum value of β, β0 is the attractiveness at rij = 0, and rij
is the Euclidian distance between any two fireflies i and j atxi and xj . L means the average scale for the problem. The
movement of the firefly i is attracted to another more attractive
firefly j, and is determined by
L=2(3)(4)(6)ϵi = (random() − 0.5)L,(7)

where xi is the position vector of firefly i, random() is a
uniform random number distributed in [0, 1] and α(t) is therandomization parameter. The parameter α(t) is defined by( −4 )t/tmax
10,(8)
α(t) = α(0)0.9where t is the number of iteration.
Algorithm 1 shows the pseudo code of the conventional FA
for minimum optimization problems.
III. K-M EANS C LUSTERING WITH FA (KMFA)For KMFA, the position vector xi of a firefly i correspondsto (c1 , c2 , ..., cK ). That is, each firefly contains the positionsof all cluster centers. The attractiveness of each firefly isdefined by the objective function (Eq. (7)). Numerical experiments have indicated that this algorithm is more efficientthan the K-means algorithm and other algorithms for typicalbenchmark data sets [1].
Algorithm 2 shows the pseudo code of KMFA.
IV. K- MEANS C LUSTERING USING THE I MPROVED FA(KMIFA)•β = (β0 − βmin )e−γrij + βmin ,1γ=√ ,
Lxi = xi + β(xj − xi ) + αϵi ,The K-means algorithm and KMFA sometimes converge
to a local minimum. Therefore, the purpose of this study isto remove this disadvantage. In our proposed algorithm, eachfirefly has its own value of α(t):( −4 )t/tmax
10,(9)
α(t) = λi0.9- 20 -TABLE I
I NFORMATION ABOUT DATA TOY MODEL USEDcluster
123456ideal center(50, 50, 70)(20, 20, 40)(20, 80, 40)(80, 20, 40)(80, 80, 40)(50, 50, 40)

object number
50
3030
30
30
20

ball of radius
15
1010
10
10
5(a) x vs y.

where λ is a new parameter. We set all value of λ to the samecertain value λ0 when initializing the population of firefliesand define the minimum value of λ is 0. We do not define
the maximum value of λ, which means λ could increase toinfinity. The value of λ changes if the assignment changes ornot.
{
λi − θ1 , the assignment doesn′ t changenewλi=(10)λi + θ2 , the assignment changes
where θ1 and θ2 are a predefined parameter. In the case of a
firefly i, if the assignment of all objects does not change, thevalue of λi decreases. On the other hand, if the assignmentof all objects changes, the value of λi increases. In the caseof λ >> 0, a firefly moves with a relatively strong random
influence. This makes the firefly easier to escape from a local
minimum. In the case of λ = 0.0, a firefly does not move
randomly, which leads to a faster convergence. Therefore, theconcept of our proposed algorithm is at the beginning of thesearch, fireflies easily escape from local optima. Then, as thenumber of iteration increases, fireflies tend to converge.

(b) x vs z.

V. N UMERICAL E XPERIMENTS(c) y vs z.

We compare the conventional K-means algorithm, KMFA
our proposed method KMIFA using a simple data toy model.
Information about that model is summarized in Tab. I and thatmodel is depicted in Fig. 1. The number of dimensions is 3,
the range of each dimension is [0, 100], the number of clusters
is 6 and the number of total objects is 190. The data objects
were generated randomly around the ideal centers within eachball of radius. We used all the same data set in each numericalexperiment. Each numerical experiment was run 500 times
and we compared the success rate of each algorithm, where
the success rate is defined as the fraction of objects that areassigned to the correct cluster:Fig. 1. Toy data model.

Success[times]× 100.
(11)500
Figure 2 shows the numerical experiment results in thecase of θ1 = 0.1 and θ2 = 0.1. We assume that ourproposed algorithm is more efficient algorithm than the othertwo algorithms. For our proposed algorithm, the success rates
are almost same as those of KMFA when λ0 is more than 1.5.
As λ0 decreasing from 1.5, the success rates of our proposedalgorithm are gradually increasing. On the other hand, As λ0
decreasing from 1.5, the success rates of KMFA remind flat
to 0.5, then, those rapidly decrease.

Fig. 2. Numerical experiment result.

Success Rate[%] =Next, we change the value of θ1 and θ2 . First, we fix thevalue of θ1 at 0.1 and change θ2 from 0.1 to 0.3 (see Fig. 3).
Figure 3 shows the value of θ2 is suitable for our proposed
algorithm. The graph of our proposed algorithms gradually
increase with the same slope. However, as the value of θ2
increasing, the success rate decreases.
Then, we fix the value of θ2 at 0.1 and change θ1 from 0.1
to 0.3 (see Fig. 4). We assume that the success rate does not- 21 -

they can more easily escape from a local minimum. As thenumber of iterations increases, the firefly tend to converge.
Numerical experiments have indicated that our proposed algorithm is more efficient than the other algorithms.
The study is based on a relatively simple toy data set. In
our future work, we will study more complex problems. In
addition, we will study more various transition.

Fig. 3. Numerical experiment result changing θ2 .

Fig. 5. The tradition of λ when λ0 = 0.3.

Fig. 4. Numerical experiment result changing θ1 .

depend on the value of θ2 .
Figure 5 shows the transition of λ when λ0 is 0.3. Each line
means the value of λ of each firefly. The transition is like amountain. Until the number of iterations is about 30, λ of allfireflies increase. From the number of iterations is about 60,
λ of all fireflies decrease. Between 30 and 60, each firefly hasa different λ value.
Figure 6 shows the transition of α when λ0 is 0.3. Eachsolid line means the value of α of each firefly on KMIFA
and broken line means the value of α of fireflies on KMFA.
There are two difference points of the transition of α between
KMFA and KMIFA. One is that the value of α increases fromthe beginning of the search. Another is that the value of α ofeach firefly is different in the middle of searching.
VI. C ONCLUSION
In this study, we have proposed a new clustering algorithm
that utilizes an improved firefly algorithm for K-means clustering. Our algorithm is based on the idea that the randomization
parameter is changed when the assignment changes or not.
In our proposed algorithm, at the beginning of the search, allfireflies move with a relatively strong random influence. Hence

Fig. 6. The tradition of α when λ0 = 0.3.

R EFERENCES[1] J. Senthilnath, S.N. Omkar and V. Mani, “Clustering using Firefly
Algorithm: Performance Study”, Swarm and Evolutionary Computation
1, pp. 164–171, 2011.
[2] X.S. Yang, Nature–Inspired Metaheuristic Algorithms Second Edition,
Luniver Press, 2010.
[3] M. Takeuchi, T. Ott, H. Matsushita, Y. Uwate and Y. Nishio, “K-Means
Algorithm using Improved Firefly Algorithm”, Proceedings of 2017
RISP International Workshop on Nonlinear Circuits, Communicationand Signal Processing (NCSP’17), pp. 225–228, 2017.
[4] S. Lukasik and S. Zak, “Firefly Algorithm for Continuous Constrained
Optimization Tasks”, Computational Collective Intelligence. SemanticWeb, Social Networks and Multiagent Systems, Vol. 5796 of the Series
Lecture Notes in Computer Science, pp. 97–106, 2009.
[5] H. Matsushita, “Firefly Algorithm with Dynamically Changing Connections”, Proceedings of International Symposium on Nonlinear Theoryand its Application (NOLTA’14), pp. 906–909, 2014.

- 22 -