An efficient approximation to the K-means clustering for massive data
An efficient approximation to the K-means clustering for massive data
复制标题
DOI：
10.1016/j.knosys.2016.06.031
复制
发表时间：
2017-02-01
影响因子：
8.8
通讯作者：
Lozano, Jose A.
中科院分区：
文献类型：
--
作者：
Capo, Marco;Perez, Aritz;Lozano, Jose A.
由于在各种科学领域中可获得的数据量的逐渐增长，操纵和分析这些信息变得更加困难。尽管K-means算法依赖于初始设置和收敛所需的大量距离计算，但它仍然是大规模数据集最流行的聚类方法之一。在这项工作中，我们提出了一个有效的近似K-means问题的海量数据。我们的方法将整个数据集递归地划分为少量子集，每个子集的特征在于其代表性（质量中心）和权重（基数），然后将加权版本的K均值算法应用于这种局部表示，这可以大大减少计算距离的数量。除了一些理论性质，实验结果表明，我们的方法优于众所周知的方法，如K-meansi-+和minibatch K-means，在距离计算的数量和近似的质量之间的关系。(C)2016爱思唯尔B. V.保留所有权利。
Due to the progressive growth of the amount of data available in a wide variety of scientific fields, it has become more difficult to manipulate and analyze such information. In spite of its dependency on the initial settings and the large number of distance computations that it can require to converge, the K-means algorithm remains as one of the most popular clustering methods for massive datasets. In this work, we propose an efficient approximation to the K-means problem intended for massive data. Our approach recursively partitions the entire dataset into a small number of subsets, each of which is characterized by its representative (center of mass) and weight (cardinality), afterwards a weighted version of the K-means algorithm is applied over such local representation, which can drastically reduce the number of distances computed. In addition to some theoretical properties, experimental results indicate that our method outperforms well-known approaches, such as the K-meansi-+ and the minibatch K-means, in terms of the relation between number of distance computations and the quality of the approximation. (C) 2016 Elsevier B.V. All rights reserved.