2017 International Symposium on Nonlinear Theory and Its Applications,NOLTA2017, Cancun, Mexico, December 4-7, 2017

K-Means Clustering with Modifying 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‡Zurich University of Applied Sciences
Einsiedlerstrasse 31a, 8820 Waedenswil, Switzerland§Department of Electronics and Information Engineering, Kagawa University
2217-20 Hayashi-cho, Takamatsu, Kagawa, 761–0396, Japan
Email: masaki@ee.tokushima-u.ac.jp, thomas.ott@zhaw.ch,haruna@eng.kagawa-u.ac.jp, {uwate, nishio}@ee.tokushima-u.ac.jp
Abstract— In 2011, Senthilnath et al. proposed to utilize the Firefly Algorithm for K-means clustering. Thealgorithm has shown better results than the standard Kmeans algorithm or other combinations with bio-inspired
optimization heuristics. In this study, we propose a furtherimprovement of the method, based on an improved firefly algorithm. As a key aspect, the randomization 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 ourproposed algorithm is more eﬃcient than the other algorithms.
1. Introduction
Clustering is a popular data analysis technique used fordata analysis, image analysis, data mining and the otherfields of science and engineering. The goal of clustering
is to find homogeneous groups of data points in a data set.
Each group is called a cluster and is characterized by thefact that objects that belong to the same group are moresimilar than objects that belong to diﬀerent groups. TheK-means algorithm is one of the most famous clustering
methods. It is used if the number of clusters is known andthe clusters tend to be spherical. The goal of the method is
to find K cluster centers and assign each object to the closest cluster center such that the sum of the squared distances
between the objects and the corresponding cluster centers
is minimal. This means that the K-means clustering problem is an optimization problem.
Senthilnath et al. proposed an algorithm that used thefirefly algorithm for K-means clustering (KMFA) [1]. Numerical experiments have indicated that this algorithm ismore eﬃcient algorithm than the standard algorithm orother optimization heuristics. The Firefly Algorithm (FA)has been proposed by Yang in 2007 and is based on theidealized behavior of the flashing characteristics of fireflies [2]. FA is an eﬃcient optimization algorithm because
it has a deterministic component and a random component.

Almost all algorithms having only the deterministic component are local search algorithms, for which there is a riskof being trapped in a local optimum. However, the random
component makes it possible to escape from such a localoptimum.
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 notchange [4]. 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 eﬃcient than the otheralgorithms. However, for 3-dimensional toy data model
this algorithm cannot obtain a better results than other algorithms. We improved the transition rule of one parameter [5]. Our proposed algorithm has new two parameters. In
the previous studies, we carried out computer simulations
with fixed parameters. Therefore, in this study, we simulate
a various patterns of this two parameters and intestate theireﬀects.

2. The Conventional Methods
In this section, we explain the conventional K-means algorithm and the Firefly Algorithm (FA).
2.1. K-means algorithm
The objective function of K-means clustering is defined
byJ=K ∑N∑bkn |ck − on |2 ,(1)k=1 n=1

where K is the number of cluster centers, N is the numberof objects, c k is the position vector of cluster center k andon is the position vector of object n. Each object is assigned
to its nearest center. Hence bkn = 1 if object n is assigned- 576 -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 < MaxGeneration 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 > I j 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 for j
end fori
Rank the fireflies and find the current best
end while
Postprocess results and visualization
to center k and bkn = 0 otherwise:
1, ob ject n is assigned to center kbkn = 0, otherwise.

(2)• The brightness or light intensity of a firefly is aﬀected
or determined by the landscape of the objective function to be optimized.
The attractiveness of a firefly β is defined by
β=γ=L

=

(β0 − βmin )e−γri j + βmin ,1√ ,L|Xmax − Xmin |,22(3)(4)(5)

where γ is the light absorption coeﬃcient, βmin is the minimum value of β, β0 is the attractiveness at ri j = 0, and ri jis the Euclidian distance between any two fireflies i and j
at xi and x j . 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 byxi=xi + β(x j − xi ) + αϵ i ,(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(This optimization problem is solved using the K-means
algorithm which is composed of the following four steps:

α(t) =

10−4α(0)0.9)t/tmax,(8)1. Initialize all cluster centers and objects: The numberof cluster centers and all objects are predefined. Allcluster centers are randomly initialized in the searchspace.

where t is the number of iteration.
Algorithm 1 shows the pseudo code of the conventional
FA for minimum optimization problems.

2. Assignments: Each object is assigned to only the closest cluster center.

3. K-Means Clustering with FA (KMFA)

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 longer
change.
2.2. The Conventional Firefly Algorithm (FA)
FA has been developed by Yang and it was based on
the idealized behavior of the flashing characteristics of fireflies [2]. 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.

For KMFA, the position vector xi of a firefly i corresponds to (c1 , c2 , ..., cK ). That is, each firefly contains thepositions of all cluster centers. The attractiveness of eachfirefly is defined by the objective function (Eq. (7)). Numerical experiments have indicated that this algorithm ismore eﬃcient than the K-means algorithm and other algorithms for typical benchmark data sets [1].
4. K-means Clustering using the Improved FA(KMIFA)The K-means algorithm and KMFA sometimes converge
to a local minimum. Therefore, the purpose of this study
is to remove this disadvantage. In our proposed algorithm,
each firefly has its own value of α(t):
(α(t)

= λi

10−40.9)t/tmax,(9)where λ is a new parameter. We set all value of λ to thesame certain value λ0 when initializing the population offireflies and define the minimum value of λ is 0. We do not- 577 -Table 1: Information about data toy model usedcluter ideal center object number ball of radius
1(50, 50, 70)50152(20, 20, 40)30103(20, 80, 40)30104(80, 20, 40)30
105(80, 80, 40)30
106(50, 50, 40)
205(a) x vs y

define the maximum value of λ, which means λ could increase to infinity. The value of λ changes if the assignmentchanges or not.

λi − θ1 , the assignment doesn′ t change
newλ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 thecase of λ >> 0, a firefly moves with a relatively strong
random influence. This makes the firefly easier to escapefrom a local minimum. In the case of λ = 0.0, a firefly does
not move randomly, which leads to a faster convergence.
Therefore, the concept of our proposed algorithm is at thebeginning of the search, fireflies easily escape from local
optima. Then, as the number of iteration increases, fireflies
tend to converge.

(b) x vs z(c) y vs z

Figure 1: Data toy model used.
5. Numerical Experiments
We compare the conventional K-means algorithm,
KMFA and two transition patterns our KMIFA using a simple data toy model. Information about that model is summarized in Tab. 1 and that model 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 each ball of radius. We used
all the same data set in each numerical experiment. Eachnumerical experiment was run 500 times and we compared
the success rate of each algorithm, where the success rateis defined as the fraction of objects that are assigned to thecorrect cluster:
S uccess Rate[%]=S uccess T imes[times]× 100.
(11)500

Figure 2 shows the numerical experiment results in thecase of θ1 = 0.1 and θ2 = 0.1. We assume that our proposed algorithm is more eﬃcient algorithm than the othertwo algorithms. For our proposed algorithm, the successrates are almost same as those of KMFA when λ0 is morethan 1.5. As λ0 decreasing from 1.5, the success rates ofour proposed algorithm are gradually increasing. On theother hand, As λ0 decreasing from 1.5, the success rates of
KMFA remind flat to 0.5, then, those rapidly decrease.
Figure 3 shows the transition of λ when λ0 is 0.0. Eachline means the value of λ of each firefly. The transition islike a mountain. Until the number of iterations is about 30,
λ of all fireflies increase. From the number of iterations isabout 60, λ of all fireflies decrease.
Next, we focus on the rule of changing λ. Figure 4 shows
the numerical experiment results in the case θ1 is fixed at0.1 and θ2 is 0 and 0.1. We assume the algorithm having
only decrease operation cannot obtain good result.
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. 5).
Figure 5 shows the value of θ2 is suitable for our proposedalgorithm. 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. 6). We assume that the success rate does
not depend on the value of θ2 .

- 578 -

Figure 5: Numerical experiment result changing θ2 .

Figure 2: Numerical experiment result.

Figure 6: Numerical experiment result changing θ1 .
Figure 3: The tradition of λ0 = 0.0.
Acknowledgment
6. Conclusion
In this study, we have proposed a new clustering algorithm that utilizes an improved firefly algorithm for Kmeans clustering. Our algorithm is based on the idea thatthe randomization parameter is changed when the assignment changes or not. In our proposed algorithm, at thebeginning of the search, all fireflies move with a relatively
strong random influence. Hence they can more easily escape from a local minimum. As the number of iterations
increases, the firefly tend to converge. Numerical experiments have indicated that our proposed algorithm is moreeﬃcient 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.

This work was partly supported by JSPS Grant-in-Aidfor Scientific Research 16K06357.
References[1] J. Senthilnath, S.N. Omkar and V. Mani, “Clustering
using Firefly Algorithm: Performance Study”, Swarmand Evolutionary Computation 1, pp. 164–171, 2011.
[2] X.S. Yang, Nature–Inspired Metaheuristic Algorithms Second Edition, Luniver Press, 2010.
[3] J. Kennedy and R. Eberhart, “Particle Swarm Optimization”, Proceedings of the International Conference on Neural Networks, pp. 1942–1948, 1995.
[4] 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, Communication and Signal Processing (NCSP’17), pp. 225–228,
2017.
[5] M. Takeuchi, T. Ott, H. Matsushita, Y. Uwate and Y.
Nishio , “Investigation of K-Means Clustering Used
Firefly Algorithm Modified Random Component”,
Asia Pacific Conference on Postgraduate Research in
Microelectronics and Electronics, 2017 (will appear).

Figure 4: Numerical experiment result only decrease operation.

- 579 -