An effective and efficient hierarchical K-means clustering algorithm. (August 2017)

• Record Type: Journal Article
• Authors: Qi, Jianpeng; Yu, Yanwei; Wang, Lihong; Liu, Jinglei; Wang, Yingjie
• Is Part Of: International journal of distributed sensor networks. Volume 13:Number 8(2017)
• Publication Date: 2017-08
• Subjects: Data mining -- clustering -- k-means -- top-n merging -- cluster pruning; Sensor networks -- Periodicals; Intelligent agents (Computer software) -- Periodicals; Multisensor data fusion -- Periodicals; 681.2
• DOI: 10.1177/1550147717728627
• Languages: English
• ISSNs: 1550-1329

Abstract

K -means plays an important role in different fields of data mining. However, k -means often becomes sensitive due to its random seeds selecting. Motivated by this, this article proposes an optimized k -means clustering method, named k* -means, along with three optimization principles. First, we propose a hierarchical optimization principle initialized by k * seeds (k * > k ) to reduce the risk of random seeds selecting, and then use the proposed "top- n nearest clusters merging" to merge the nearest clusters in each round until the number of clusters reaches atk . Second, we propose an "optimized update principle" that leverages moved points updating incrementally instead of recalculating mean andSSE of cluster in k -means iteration to minimize computation cost. Third, we propose a strategy named "cluster pruning strategy" to improve efficiency of k -means. This strategy omits the farther clusters to shrink the adjustable space in each iteration. Experiments performed on real UCI and synthetic datasets verify the efficiency and effectiveness of our proposed algorithm.