Investigation of K-means Algorithm
Using an Improved Firefly Algorithm
M. Takeuchi1 , T. Ott2 , H. Matsushita3 , Y. Uwate1 and Y. Nishio1
1: Tokushima Univ., 2: Zurich Univ. of Applied Sciences, 3: Kagawa Univ.
1: {masaki, uwate, nishio}@ee.tokushima-u.ac.jp, 2: thomas.ott@zhaw.ch,
3: haruna@eng.kagawa-u.ac.jp
Clustering is a popular data analysis technique used for data analysis, image analysis,
data mining and the other ﬁelds of science and engineering. The goal of clustering is toﬁnd homogeneous groups of data points in a data set. Each group is called a cluster andis characterized by the fact that objects belonging to the same group are more similar
than objects belonging to diﬀerent 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 be spherical. The goal of the method is to ﬁnd 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 thatthe K-means clustering problem is an optimization problem.
Senthilnath et al. [1] proposed an algorithm that used the ﬁreﬂy algorithm for Kmeans clustering (KMFA). Numerical experiments have indicated that this algorithm
is more eﬃcient algorithm than the standard algorithm or other optimization heuristics. The ﬁreﬂy algorithm (FA) has been proposed by Yang in 2007 and is based on
the idealized behavior of the ﬂashing characteristics of ﬁreﬂies [2–4]. 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 searchalgorithms, for which there is a risk of being trapped in a local optimum. However, therandom component makes it possible to escape from such a local optimum.
In this paper, we propose a new clustering algorithm that combines K-means clustering and improved ﬁreﬂy algorithm (KMIFA). In our proposed algorithm, each ﬁreﬂy
has its own value of α(t):α(t)i = λi(10−40.953)t/tmax.

(1)

In the case of ﬁreﬂy i, if the assignment of all objects does not change, the value of λi
decreases. We set all initial values of λ to 1.0 when initializing the population of ﬁreﬂies
anddeﬁneminimumof λ is 0. of all objects does not change, the value of λIn thecasetheof ﬁreﬂyi, if value
the assignmentidecreases. We set all 
initialvalues, ofthe
λ to
1.0 when does
initializing
the population of ﬁreﬂies
λoldassignment
not changei −V
λi =(2)and deﬁne the minimum
value of λ is 0.
λold, otherwiseiλoldi −V, the assignment does not change
The parameter Vλ is=a predeﬁned value. At the beginning of the search, all ﬁreﬂies move(2)i
 oldλ, otherwise
with a relatively strong
randominﬂuence.
Hence, they can more easily escape from locali

optima.
As the numberof iterations
increases,ﬁreﬂy tends
converge.
We compare
The parameter
V is a predeﬁnedvalue.
At thethe
beginningof thetosearch,
all ﬁreﬂies
movetheK-means
algorithm,
KMFA
and ourKMIFA
withconventionala relatively strong
randominﬂuence.
Hence,
theyproposed
can morealgorithm
easily escapefromusing
local
severalmodels
thatofhave
severalincreases,spherical theclusters.
that
optima.dataAs thenumberiterations
ﬁreﬂyThesetends experiments
to converge. indicate
We compare
ouris more
eﬃcient
than theotherandalgorithms.
the algorithm
conventional
K-meansalgorithm,KMFA
our proposed algorithm KMIFA using
several data models that have several spherical clusters. These experiments indicate that
our algorithm is more eﬃcient than the other algorithms.
References[1] J. Senthilnath, S.N. Omkar and V. Mani, “Clustering using Firefly Algorithm: Per-References
formance Study", Swarm and Evolutionary Computation 1, pp. 164–171, 2011.

[1] X.S.
J. Senthilnath,
S.N. OmkarMetaheuristic
and V. Mani, Algorithms“ClusteringSecondusing Firefly
Per[2]
Yang, Nature-Inspired
Edition,Algorithm:
Luniver Press,formance Study", Swarm and Evolutionary Computation 1, pp. 164–171, 2011.
2010.
[2] S.
X.S.
Yang, andNature-Inspired
Metaheuristic
SecondEdition, LuniverPress,[3]
LukasikS. Zak, “Firefly
Algorithm Algorithms
for ContinuousConstrainedOptimization
2010. Computational Collective Intelligence, Semantic Web, Social Networks andTasks",
Systems,Vol.
5796 ofthe Seriesfor
LectureNotes Constrainedin ComputerOptimization
Science, pp.
[3] Multiagent
S. Lukasik andS. Zak,
“Firefly
Algorithm
Continuous
97–106,
Tasks", 2009.
Computational Collective Intelligence, Semantic Web, Social Networks andMultiagent
Systems,
Vol.Algorithm5796 of theSeries
Lecture Notes
in ComputerScience,Propp.
[4] H.
Matsushita,“FireflywithDynamicallyChangingConnections",
97–106, 2009.
ceedingsof International Symposium on Nonlinear Theory and its Applica(NOLTA’14),
pp. 906–909,
2014.
[4] tion
H. Matsushita,“FireflyAlgorithmwith Dynamically Changing Connections", Proceedings of International Symposium on Nonlinear Theory and its Application (NOLTA’14), pp. 906–909, 2014.
The preliminary version of this study is presented at NCSP2017.

The preliminary version of this study is presented at NCSP2017.

54