2017 IEEE Workshop on Nonlinear Signal Processing, Feb. 10, 2017

K-means Algorithm Using an Improved Firefly
Algorithm Applied Simple Toy Model
Masaki TakeuchiThomas Ott

Haruna Matsushita

Yoko Uwate and Yoshifumi Nishio

Dept. Electrical
Zurich University
Dept. Electronics
Dept. Electricaland Electronic Eng.,of Applied Sciences
and Info. Eng.,and Electronic Eng.,
Tokushima University
thomas.ott@zhaw.ch
Kagawa University
Tokushima University
masaki@ee.tokushima-u.ac.jp
haruna@eng.kagawa-u.ac.jp {uwate, nishio}@ee.tokushima-u.ac.jp

I. I NTRODUCTION
100
Success rate [%]Senthilnath et. al. [1] proposed an algorithm that used thefirefly algorithm for K-means clustering (KMFA). Numericalexperiments have indicated that this algorithm is more efficientalgorithm than the standard algorithm or other optimization
heuristics. In this paper, we introduce a new clustering algorithm that combines K-means clustering with improved
firefly algorithm (KMIFA). In our algorithm, one parameter ischanged when the assignment does not change. We compare
the conventional K-means algorithm, KMFA and KMIFA
using a toy data model. 1 These experiments indicate that ouralgorithm is more efficient than the other algorithms.

7550250K-means algorithm
KMFAKMIFA
100200300

400500Maximum number of iterations of algorithm

II. KMIFAFig. 1. Comparison of the three algorithms

The K-means algorithm sometimes converges to a local
minimum. Therefore, the purpose of this study is to remove
this disadvantage. In our algorithm, each firefly has its own
value of α(0) and we set all values of α(0) to 1.0 when
initializing the population of fireflies. In the case of a fireflyi, if the assignment of all objects does not change, the valueof α(0) of firefly i decreases. We define the minimum valueof α(0) is 0.0.
{α(0)i, the assignment changesnew(1)α(0)i=α(0)i − V , otherwise
The parameter V is a predefined value. In the case of α(0) =1.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.0, a firefly does not move randomly,
which leads to a faster convergence.
III. N UMERICAL E XPERIMENTS
We compare the conventional K-means algorithm, KMFAand KMIFA using a simple data toy model. The number ofdimensions is 2, the range of each dimension is [0, 100], thenumber of clusters is 6 and the number of objects is 120(20 objects per cluster). For the data generation, the ideal
cluster centers were placed at (30, 30), (70, 70), (10, 80),
(90, 20), (50, 90) and (70, 70). Then, the data objects weregenerated randomly around the ideal centers within a ball
1 The extended version of this study is being reviewed for NCSP2017 [2].

of radius 10. Each numerical experiment was run 300 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.
Figure 1 shows the numerical results for the parameter V =0.1 and 20 fireflies. We assume that our algorithm is more
efficient algorithm than the other two algorithms.
IV. C ONCLUSION
In this study, we have introduced 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 does not change.
In our algorithm, at the beginning of the search, all fireflies
move with a relatively strong random influence. Hence they
can more easily escape from a local minimum. As the numberof iterations increases, the firefly tend to converge. Numericalexperiments have indicated that our algorithm is more efficientthan K-means algorithm and KMFA.
R EFERENCES[1] J. Senthilnath, S.N. Omkar and V. Mani, “Clustering using FireflyAlgorithm: Performance Study”, Swarm and Evolutionary Computation
1, pp. 164–171, 2011.
[2] M. Takeuchi, T. Ott, H. Matsushita, Y. Uwate and Y. Nishio, ”Kmeans Algorithm using Improved Firefly Algorithm“, RISP International
Workshop on Nonlinear Circuits, Communications and Signal Processing,2017. (being submitted)-5-