通过几何条件数分析，揭示低目标值为何能反映真实聚类结构。
The Condition-Number Principle for Prototype Clustering
- 提出聚类条件数，衡量簇内尺度与跨边界损失增量的比值。
- 条件数小时，小误差解对应低误分类率，保证结构可恢复。
- 适用于多种损失函数，适合研究聚类鲁棒性与不平衡问题者。
我们构建了一个几何框架，将目标精度与原型聚类中的结构恢复相联系。该分析不依赖具体算法，适用于一大类可接受的损失函数。定义了聚类条件数，用于比较簇内尺度与移动点跨越簇边界的最小损失增加量。当该值较小时，任意具有小次优间隙的解，其相对于基准划分的误分类误差也必然很小。该框架还阐明了鲁棒性与对簇不平衡敏感性之间的根本权衡，导致不同目标下精确恢复的清晰相变现象。保证为确定性且非渐近，区分了算法精度与实例内在几何难度的作用。进一步证明误差集中在簇边界附近，且在加强局部边缘条件下，足够深的簇核心可被精确恢复。这些结果共同提供了一个几何原则，用以解释低目标值是可信的有意义聚类结构证据。
原文摘要 · Abstract (English)
We develop a geometric framework that links objective accuracy to structural recovery in prototype-based clustering. The analysis is algorithm-agnostic and applies to a broad class of admissible loss functions. We define a clustering condition number that compares within-cluster scale to the minimum loss increase required to move a point across a cluster boundary. When this quantity is small, any solution with a small suboptimality gap must also have a small misclassification error relative to a benchmark partition. The framework also clarifies a fundamental trade-off between robustness and sensitivity to cluster imbalance, leading to sharp phase transitions for exact recovery under different objectives. The guarantees are deterministic and non-asymptotic, and they separate the role of algorithmic accuracy from the intrinsic geometric difficulty of the instance. We further show that errors concentrate near cluster boundaries and that sufficiently deep cluster cores are recovered exactly under strengthened local margins. Together, these results provide a geometric principle for interpreting low objective values as reliable evidence of meaningful clustering structure.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。