A Fast Adaptive k-means with No Bounds
A Fast Adaptive k-means with No Bounds
复制标题
无界限的快速自适应 k 均值
DOI：
10.1109/tpami.2020.3008694
复制
发表时间：
2020
影响因子：
23.6
通讯作者：
Zizhong Chen
中科院分区：
文献类型：
--
作者：
Shuyin Xia;Daowan Peng;Deyu Meng;Changqing Zhang;Guoyin Wang;Elisabeth Giem;Wei;Zizhong Chen
本文提出了一种新的加速精确平均算法“球平均法”，它用球来描述每个簇，以减少点-质心距离的计算量。球面平均法可以准确地为每个簇找到它的邻居簇，从而只计算一个点和它的邻居簇的质心之间的距离，而不是所有质心。此外，每个星系团又可分为“稳定区”和“活动区”，而“活动区”又被进一步划分为一些确切的“环状区”。“稳定区域”中的点的分配不变，而每个“环形区域”中的点将在几个相邻簇内进行调整。整个过程没有上下限。此外，Ball-Means算法使用球簇和邻域搜索以及多种新策略来减少质心距离计算。与目前最先进的加速精确有界法、银阳算法和Exponion算法以及其他基于树的有界方法相比，球平均法具有更高的性能和更少的距离计算，特别是对于大k问题。更快的速度，不需要额外的参数，更简单的设计，使其成为幼稚手段的全方位替代。
This paper presents a novel accelerated exact-means called as “Ball-means” by using the ball to describe each cluster, which focus on reducing the point-centroid distance computation. The “Ball-means” can exactly find its neighbor clusters for each cluster, resulting distance computations only between a point and its neighbor clusters’ centroids instead of all centroids. What’s more, each cluster can be divided into “stable area” and “active area”, and the latter one is further divided into some exact “annular area”. The assignment of the points in the “stable area” is not changed while the points in each “annular area” will be adjusted within a few neighbor clusters. There are no upper or lower bounds in the whole process. Moreover, ball-means uses ball clusters and neighbor searching along with multiple novel stratagems for reducing centroid distance computations. In comparison with the current state-of-the art accelerated exact bounded methods, the Yinyang algorithm and the Exponion algorithm, as well as other top-of-the-line tree-based and bounded methods, the ball-means attains both higher performance and performs fewer distance calculations, especially for large-k problems. The faster speed, no extra parameters and simpler design of “Ball-means” make it an all-around replacement of the naive-means.