Recovering Trees with Convex Clustering
Recovering Trees with Convex Clustering
复制标题
DOI：
10.1137/18m121099x
复制
发表时间：
2019-01-01
影响因子：
3.6
通讯作者：
Steinerberger, Stefan
中科院分区：
文献类型：
--
作者：
Chi, Eric C.;Steinerberger, Stefan
层次聚类是一项基本的无监督学习任务，其目标是将一组点组织成一棵嵌套聚类树。凸聚类是最近提出的一种新的构造数据树组织的方法，与标准的层次聚类算法相比，这种方法对输入数据的扰动具有更强的鲁棒性。本文给出了保证凸聚类解路径恢复树的条件，并明确了凸聚类公式中的亲和力参数如何调整恢复树的结构。我们主要结果的证明依赖于在Hilbert空间中建立点云的一个新的性质，这是潜在的独立兴趣。
Hierarchical clustering is a fundamental unsupervised learning task, whose aim is to organize a collection of points into a tree of nested clusters. Convex clustering has been proposed recently as a new way to construct tree organizations of data that are more robust to perturbations in the input data than standard hierarchical clustering algorithms. In this paper, we present conditions that guarantee when the convex clustering solution path recovers a tree and also make explicit how affinity parameters in the convex clustering formulation modulate the structure of the recovered tree. The proof of our main result relies on establishing a novel property of point clouds in a Hilbert space, which is potentially of independent interest.