.png){kind=icon}
返回
Efficient k-Means plus plus Approximation with MapReduce
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2014.2306193.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
k-means is undoubtedly one of the most popular clustering algorithms owing to its simplicity and efficiency. However, this algorithm is highly sensitive to the chosen initial centers and thus a proper initialization is crucial for obtaining an ideal solution. To address this problem, k-means++ is proposed to sequentially choose the centers so as to achieve a solution that is provably close to the optimal one. However, due to its weak scalability, k-means++ becomes inefficient as the size of data increases. To improve its scalability and efficiency, this paper presents MapReduce k-means++ method which can drastically reduce the number of MapReduce jobs by using only one MapReduce job to obtain k centers. The k-means++ initialization algorithm is executed in the Mapper phase and the weighted k-means++ initialization algorithm is run in the Reducer phase. As this new MapReduce k-means++ method replaces the iterations among multiple machines with a single machine, it can reduce the communication and I/O costs significantly. We also prove that the proposed MapReduce k-means++ method obtains O(alpha(2)) approximation to the optimal solution of k-means. To reduce the expensive distance computation of the proposed method, we further propose a pruning strategy that can greatly avoid a large number of redundant distance computations. Extensive experiments on real and synthetic data are conducted and the performance results indicate that the proposed MapReduce k-means++ method is much more efficient and can achieve a good approximation.
Keyword:
Clustering algorithms
k-means
k-means plus
MapReduce
approximation
scalability
期刊
IF:
6
论文数:
5.2K
被引数:
1.1W
机构
引用论文
.png){kind=icon}
分享收藏A comparative study of efficient initialization methods for the k-means clustering algorithmK-means聚类算法高效初始化方法的比较研究
PREAI
分享收藏
查看更多内容