提出基于连通图的凸聚类理论，揭示图结构对聚类效果的影响。
Affinity Graph Connectivity in Convex Clustering
- 用随机游走建模聚类中的图连通性，推导新理论边界
- 证明了在连通图下中心点恢复速率更快
- 建议调参时同时优化输入相似度权重
我们将凸聚类的有限样本界推广到亲和权重对应一般连通图的情形。这些边界及其分析深化了对数据背后不同连通结构下聚类行为的理解，并给出了新的中心点恢复收敛速率。新理论框架基于随机游走，可应用与随机图模型相关的集中不等式，形式化了聚类性能与图结构连通性之间的关系。通过边界形式与实验结果，我们主张在凸聚类问题中调参应包括对输入亲和权重的调整。
原文摘要 · Abstract (English)
We generalize finite-sample bounds for convex clustering to the setting where affinity weights appearing in the objective correspond to a general connected graph. These bounds and their analysis lead to a better understanding of clustering behavior under various implied connectivity structures behind the data and to new rates of convergence for centroid recovery. The new theoretical framework is based on random walks, which allow application of concentration inequalities related to random graph models, and formalizes the relationship between the clustering performance and the connectivity of the graph structures. Through the form of the bound and empirical results, we argue proper tuning of hyperparameters to convex clustering problems should also include tuning of input affinity weights.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。