是什么让k-medoid中的距离测量"比k-means更好"？

Question

我正在阅读k-means聚类和k-medoid聚类之间的区别.

据推测,在k-medoid算法中使用成对距离度量有一个优点,而不是更熟悉的欧几里德距离型度量平方和来评估我们用k均值找到的方差.显然,这种不同的距离度量会以某种方式降低噪音和异常值.

我已经看到了这个说法,但我还没有看到任何关于这一主张背后的数学的理由.

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

Answer 1

1. K-medoid更灵活

首先,您可以使用任何相似性度量的k-medoids .然而,K-means可能无法收敛 - 它实际上只能用于与均值一致的距离.因此,例如Absolute Pearson Correlation不能与k-means一起使用,但它适用于k-medoids.

2.类固体的稳健性

其次,k-medoids使用的medoid与中位数大致相当(事实上​​,还有k-medians,就像K-means,但对于曼哈顿距离).如果你查看关于中位数的文献,你会看到大量的解释和例子,为什么中值对异常值比算术平均值更强.从本质上讲,这些解释和例子也适用于medoid.对于代表点而言,它是比k均值中使用的平均值更稳健的估计.

考虑这个一维示例:

1 2 3 4 100000

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

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

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

我没有证据,但我认为medoid将具有与中位数类似的分解点.

3. k-medoids要贵得多

这是主要的缺点.通常,PAM比k-means需要更长的运行时间.因为它涉及计算所有成对距离,它是O(n^2*k*i); 而k-means O(n*k*i)通常在迭代次数为k次的情况下运行k*i << n.

Answer 2

我认为这与选择集群中心有关.k-means将选择群集的"中心",而k-medoid将选择群集的"最中心"成员.在具有异常值的群集中(即远离群集的其他成员的点),k-means将群集的中心置于异常值,而k-medoid将选择一个更集群的成员(medoid)作为中央.

它现在取决于你使用什么聚类.如果你只想对一堆物体进行分类,那么你并不关心中心的位置; 但如果聚类用于训练一个决定者,现在将根据这些中心点对新物体进行分类,那么k-medoid将为你提供一个靠近人类放置中心位置的中心.

用维基百科的话说:

"与k-means相比,它[k-medoid]对噪声和异常值更具鲁棒性,因为它最大限度地减少了成对差异的总和,而不是欧几里德距离的平方和."

这是一个例子:

假设您想要在k = 2的一个维度上进行聚类.一个集群的大部分成员大约1000个,另一个集团大约-1000个; 但是有一个异常值(或噪音)在100000.它显然属于1000左右的集群,但k-means将使中心点远离1000并朝向100000.这甚至可能使1000集群中的一些成员(比如说)值为500的成员将分配给-1000群集.k-medoid将选择1000左右的一个成员作为medoid,它可能会选择一个大于1000的成员,但它不会选择异常值.

Answer 3

只是在 @Eli 的答案中添加了一个小注释，K-medoid 对噪声和异常值比 k-means 更稳健，因为后者选择聚类中心，这主要只是一个“德性点”，另一方面，前者选择聚类中心来自集群的“实际对象”。

假设一个簇中有 5 个 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) 之间选择中心。

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