前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >沃德的方法分析

沃德的方法分析

原创
作者头像
罗大琦
发布2019-07-18 17:38:09
1.1K0
发布2019-07-18 17:38:09
举报
文章被收录于专栏:算法和应用

作者: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

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档