是什么使k-medoid中的距离度量比k-means更好?
cluster-analysis
data-mining
k-means
machine-learning
5
0

我正在阅读有关k-均值聚类和k-medoid聚类之间的区别。

假设在k-medoid算法中使用成对距离度量,而不是更熟悉的平方欧几里得距离类型度量之和来评估我们用k-均值求出的方差,是有优势的。显然,这种不同的距离度量可以以某种方式减少噪声和离群值。

我已经看过这种说法,但是对于这种说法背后的数学,我还没有看到任何很好的推理。

是什么使k-medoid中常用的成对距离度量更好?更确切地讲,缺少平方项如何使k-medoids具有与取中位数概念相关的理想属性?

参考资料:
Stack Overflow
收藏
评论
共 3 个回答
高赞 时间 活跃

我认为这与选择集群中心有关。 k均值将选择群集的“中心”,而k均值将选择群集的“最中心”成员。在具有离群值(即,远离该聚类的其他成员的点)的聚类中,k均值会将聚类的中心朝向离群值,而k-medoid将选择更多聚类成员之一(该medoid)作为中央。

现在,这取决于您将群集用于什么目的。如果您只想对一堆对象进行分类,那么您就不必在乎中心在哪里;但是,如果使用聚类来训练决策者,该决策者现在将基于这些中心点对新对象进行分类,则k-medoid将为您提供一个更靠近人类放置中心的中心。

用维基百科的话来说:

“与k-means相比,它(k-medoid)对噪声和离群值更鲁棒,因为它使成对的相异之和最小化而不是平方的欧几里德距离之和。”

这是一个例子:

假设您想在k = 2的一维上聚类。一个集群的大多数成员约为1000,而另一个集群的成员约为-1000。但是在100000处有一个离群值(或噪声)。它显然属于1000左右的簇,但k均值会使中心点远离1000并朝向100000。这甚至可能使1000簇的某些成员(例如值500的成员)分配给-1000集群。 k-medoid将选择大约1000个成员之一作为medoid,它可能会选择一个大于1000的成员,但不会选择离群值。

收藏
评论

1. K-medoid更灵活

首先,您可以将k-medoids用于任何相似性度量。但是,K均值可能无法收敛-实际上,它只能用于与均值一致的距离。因此,例如绝对绝对皮尔逊相关不能与k-means一起使用,但是它与k-medoids一起很好地工作。

2.类固醇的健壮性

其次,k-medoids使用的medoid与中位数大致相当(实际上,也存在k个中值,类似于K-means,但曼哈顿距离)。如果您查阅有关中位数的文献,您会看到很多解释和示例,为什么中位数比算术平均值更能抵抗异常值 。本质上,这些解释和示例也将适用于类固醇。与k均值中使用的平均值相比,它是对代表点的更可靠的估计。

考虑以下一维示例:

[1, 2, 3, 4, 100000]

该组的中位数和中值都为3 。平均值是20002。

您认为哪个更能代表数据集?均值具有较低的平方误差,但假设此数据集中可能存在测量误差...

从技术上讲, 故障点的概念用于统计。中位数的分解点为50%(即,一半的数据点可能不正确,结果仍然不受影响),而平均值的分解点为0(即,单个大观察值可能产生错误的估计)。

我没有证据,但我认为该类药物的分解点与中位数相似。

3. k-medoids要贵得多

那是主要的缺点。通常,PAM的运行时间比k均值要长得多。由于涉及计算所有成对距离,因此为O(n^2*k*i) ;而k-means在O(n*k*i) ,通常,k倍的迭代次数是k*i << n

收藏
评论

只是在@Eli答案中添加了一个小注释,K-medoid在噪声和离群值方面比k-means更健壮,因为后者选择了聚类中心,而簇中心通常只是一个“虚拟点”,而前者选择了聚类中心。群集中的“实际对象”。

假设您在一个群集中有五个2D点,其坐标分别为(1,1),(1,2),(2,1),(2,2)和(100,100)。如果我们不考虑聚类之间的对象交换,则使用k均值,您将获得聚类的中心(21.2,21.2),该聚类的中心被点(100,100)分散了。但是,对于k-medoid,将根据其算法在(1,1),(1,2),(2,1)和(2,2)中选择中心。

这是一个有趣的applet( EM Mirkes,K-means和K-medoids applet。莱斯特大学,2011年 ),您可以在2D平面中随机生成数据集并比较k-medoid和k-means学习过程。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号