用覆盖树加速k均值聚类，减少距离计算量。
Accelerating k-Means Clustering with Cover Trees
- 引入覆盖树索引结构，利用邻近点同簇特性优化搜索
- 在多种参数下性能优于基于k-d树的方法，计算开销低
- 结合上下界过滤，适合大规模数据聚类场景
k均值聚类算法是一种广泛使用的数据分组方法。现有加速方法多依赖点到聚类中心距离的上下界和三角不等式来减少距离计算，但仅使用数组作为底层数据结构，无法利用邻近点常被分配至同一聚类的特性。本文提出一种基于覆盖树索引的新k均值算法，具有较低的额外开销，在更广泛的参数范围内表现优于基于k-d树的现有方法。通过结合上下界过滤机制，进一步构建混合算法，同时发挥树结构聚合与边界剪枝的优势。
原文摘要 · Abstract (English)
The k-means clustering algorithm is a popular algorithm that partitions data into k clusters. There are many improvements to accelerate the standard algorithm. Most current research employs upper and lower bounds on point-to-cluster distances and the triangle inequality to reduce the number of distance computations, with only arrays as underlying data structures. These approaches cannot exploit that nearby points are likely assigned to the same cluster. We propose a new k-means algorithm based on the cover tree index, that has relatively low overhead and performs well, for a wider parameter range, than previous approaches based on the k-d tree. By combining this with upper and lower bounds, as in state-of-the-art approaches, we obtain a hybrid algorithm that combines the benefits of tree aggregation and bounds-based filtering.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。