Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2014:2014:564829.
doi: 10.1155/2014/564829. Epub 2014 Aug 18.

Towards enhancement of performance of K-means clustering using nature-inspired optimization algorithms

Simon Fong  1 , Suash Deb  2 , Xin-She Yang  3 , Yan Zhuang  1
Affiliations

Towards enhancement of performance of K-means clustering using nature-inspired optimization algorithms

Simon Fong et al. ScientificWorldJournal. 2014.

Abstract

Traditional K-means clustering algorithms have the drawback of getting stuck at local optima that depend on the random values of initial centroids. Optimization algorithms have their advantages in guiding iterative computation to search for global optima while avoiding local optima. The algorithms help speed up the clustering process by converging into a global optimum early with multiple search agents in action. Inspired by nature, some contemporary optimization algorithms which include Ant, Bat, Cuckoo, Firefly, and Wolf search algorithms mimic the swarming behavior allowing them to cooperatively steer towards an optimal objective within a reasonable time. It is known that these so-called nature-inspired optimization algorithms have their own characteristics as well as pros and cons in different applications. When these algorithms are combined with K-means clustering mechanism for the sake of enhancing its clustering quality by avoiding local optima and finding global optima, the new hybrids are anticipated to produce unprecedented performance. In this paper, we report the results of our evaluation experiments on the integration of nature-inspired optimization methods into K-means algorithms. In addition to the standard evaluation metrics in evaluating clustering quality, the extended K-means algorithms that are empowered by nature-inspired optimization methods are applied on image segmentation as a case study of application scenario.

PubMed Disclaimer

Figures

Figure 1
Figure 1
Examples of clustering results by random centroids of K-means where k = 3.
Figure 2
Figure 2
Workflow of C-Cuckoo algorithm.
Figure 3
Figure 3
Workflow of C-Bat algorithm.
Figure 4
Figure 4
Snapshots of clustering operations.
Figure 5
Figure 5
Computation time (in secs.) for C-Firefly, C-Cuckoo, and C-Bat algorithms.
Figure 6
Figure 6
Computation time (in secs.) for C-ACO algorithm.
Figure 7
Figure 7
Number of iterations required for C-Firefly, C-Cuckoo, and C-Bat algorithms to converge.
Figure 8
Figure 8
Number of iterations required for C-ACO to converge.
Figure 9
Figure 9
Results of image segmentation by using different nature-inspired clustering algorithms, on a photo called “Tower Bridge.”
Figure 10
Figure 10
Results of image segmentation by using different nature-inspired clustering algorithms, on a photo called “Cambridge University.”
Figure 11
Figure 11
Results of image segmentation by using different nature-inspired clustering algorithms, on a photo called “Le Mont-Saint-Michel.”
Figure 12
Figure 12
Results of image segmentation by using different nature-inspired clustering algorithms, on a photo called “Château de Chenonceau.”
See this image and copyright information in PMC

References

    1. MacQueen JB. Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability; 1967; University of California Press; pp. 281–297.
    1. Fong S. Swarm Intelligence and Bioinspired Computation. Elsevier; 2013. Opportunities and challenges of integrating bio-inspired optimization and data mining algorithms; pp. 385–401.
    1. Tang R, Fong S, Yang X-S, Deb S. Integrating nature-inspired optimization algorithms to K-means clustering. Proceedings of the 7th International Conference on Digital Information Management (ICDIM '12); August 2012; Macau, China. pp. 116–123.
    1. Senthilnath J, Omkar SN, Mani V. Clustering using firefly algorithm: performance study. Swarm and Evolutionary Computation. 2011;1(3):164–171.
    1. Karaboga D. TR06. Computer Engineering Department, Engineering Faculty, Erciyes University; 2005. An idea based on honey bee swarm for numerical optimization.

Publication types

LinkOut - more resources