沃德的方法分析

作者：Anna Großwendt,Heiko Röglin,Melanie Schmidt

摘要：我们研究沃德的分层k均值问题的方法。这种流行的贪婪启发式基于\ emph {完整链接}范例：从所有数据点开始作为单例集群，它连续合并两个集群以形成一个集群，其中一个集群少。选择该对簇以（局部地）最小化下一步骤中的聚类的k均值成本。

完整的链接算法在层次聚类问题中非常流行，但它们的理论性质研究相对较少。对于欧几里德k中心问题，Ackermann等人。表明通过完全链接计算的层次结构中的k-聚类具有最差情况下的近似比率Θ（logk）。如果数据位于Rd中，对于常数维d，则保证提高到O（1），但O符号隐藏了对d的线性依赖性。到目前为止尚未分析k-中值或k-均值的完全连锁。

在本文中，我们表明，如果最佳k-聚类很好地分离，Ward的方法就k-均值目标函数计算2近似。如果另外最优聚类也满足平衡条件，则Ward的方法完全恢复最优解。这些结果具有任意维度。对于Rd中的数据集，我们的正结果伴随着Ω（（3/2）d）的下限，如果没有保证分离则保持，并且当保证分离不够强时具有下限。最后，我们展示Ward为一维数据集生成O（1） - 近似聚类。

原文标题：Analysis of Ward's Method

原文摘要：

地址：https://arxiv.org/abs/1907.05094