通过半径合并优化k均值聚类，自动识别非凸形状并提升可扩展性
Radius-Guided Post-Clustering for Shape-Aware, Scalable Refinement of k-Means Results
- 用每个簇最远点距离作为半径，重叠簇自动合并
- 即使k值略大也能准确恢复非凸形状，准确率高且计算开销小
- 支持分块并行处理，适合分布式系统与大规模数据
传统k均值聚类在非凸形状上表现不佳，且需预先指定聚类数k。本文提出一种简单几何增强：在标准k均值后，为每个簇中心分配半径（到其最远归属点的距离），若半径重叠则合并簇。该后处理步骤放宽了对精确k的要求——只要k被适度高估，就能通过有意义的合并重建非凸结构。此外，该方法支持递归分割：可在特征空间的分块区域独立聚类，再全局合并，具备可扩展性，适合分布式系统。作为轻量级后处理步骤集成于scikit-learn k-means，该算法在基准数据集上表现优异，以极少额外计算获得高精度。
原文摘要 · Abstract (English)
Traditional k-means clustering underperforms on non-convex shapes and requires the number of clusters k to be specified in advance. We propose a simple geometric enhancement: after standard k-means, each cluster center is assigned a radius (the distance to its farthest assigned point), and clusters whose radii overlap are merged. This post-processing step loosens the requirement for exact k: as long as k is overestimated (but not excessively), the method can often reconstruct non-convex shapes through meaningful merges. We also show that this approach supports recursive partitioning: clustering can be performed independently on tiled regions of the feature space, then globally merged, making the method scalable and suitable for distributed systems. Implemented as a lightweight post-processing step atop scikit-learn's k-means, the algorithm performs well on benchmark datasets, achieving high accuracy with minimal additional computation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。