什么使得k-medoid中的距离度量“优于”k-means？

Question

我正在阅读关于k-means聚类和k-medoid聚类之间的差异。

据说在k-medoid算法中使用成对距离测量有优势，而不是我们在k-means中找到的更为熟悉的平方欧几里得距离类型度量来评估方差。显然，这种不同的距离度量方式可以降低噪声和异常值。

我看到了这个说法，但我还没有看到任何关于这个说法背后数学原理的好的推理。

成对距离在k-medoid中为什么更常用？更确切地说，缺少平方项如何使k-medoids具有与取中值概念相关联的理想属性？

- tumultous_rooster

---

统计学堆栈交换网站（http://stats.stackexchange.com/）可以是一个更好的地方，以获得更深入和理论化的答案。 - berkay

看看我的更新答案，关于鲁棒统计中的破坏点概念。中值很可能是一种鲁棒统计量，而均值则完全不具备鲁棒性。 - Has QUIT--Anony-Mousse

Answer 1

1. K-medoid更加灵活

首先，你可以使用k-medoid与任何相似性度量。但是，k-means可能无法收敛 - 它必须仅与与平均数一致的距离一起使用。例如，不能使用绝对皮尔逊相关性与k-means一起使用，但它与k-medoid很好地配合。

2. medoid的鲁棒性

其次，由k-medoids使用的medoid大致相当于中位数（事实上，也有k-中位数，它类似于曼哈顿距离下的k-means）。如果您查阅关于中位数的文献，您将看到许多解释和例子，说明中位数比算术平均数更具有鲁棒性。本质上，这些解释和例子也适用于medoid。它是一个比k-means中使用的平均值更加鲁棒的代表点估计。

考虑这个一维示例：

[1, 2, 3, 4, 100000]

这组数据的中位数和中心点（medoid）都是3。平均值为20002。

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

在统计学中，技术上使用“破坏点”（breakdown point）概念。中位数的破坏点为50%（即一半数据点可能不正确，结果仍不受影响），而平均值的破坏点为0（即单个大观察值可能导致错误估计）。

我没有证明，但我认为中心点与中位数具有类似的破坏点。

3. k-medoids要昂贵得多

这是主要缺点。通常，PAM的运行时间比k-means长得多。因为它涉及计算所有成对距离，所以复杂度是O(n^2*k*i)；而k-means的运行时间为O(n*k*i)，通常情况下，k乘以迭代次数为k*i << n。

- Has QUIT--Anony-Mousse

---

谢谢您的评论。但我仍然没有看到相似度测量中缺少平方项和中位数概念之间的相关性。 - tumultous_rooster

不是二次项本身的问题，而是总和的问题，这对异常值不具有鲁棒性。将一个极端值放入您的数据中。比如说，你的数据是0,1,2,3,100000000。比较均值和中位数，哪个更具有鲁棒性？ - Has QUIT--Anony-Mousse

关于k-medoids和中位数之间的类比部分有点含糊不清？ - tumultous_rooster

显然它们不是一样的。但是如果你通过“delta”使一个离群值更极端，这不会对中心点产生太大影响，就像中位数一样；因为所有其他候选项都受到相同的影响。 - Has QUIT--Anony-Mousse

Answer 2

我认为这与对聚类中心的选择有关。k-means将选择聚类的“中心”，而k-medoid将选择聚类的“最中心”的成员。 在一个有异常值（即远离聚类其他成员的点）的聚类中，k-means会将聚类中心放置在异常值附近，而k-medoid将选择更密集的成员（介质点）作为中心。

现在取决于您使用聚类的目的。如果你只是想分类一堆对象，那么你不需要真正关心中心在哪里；但如果聚类被用来训练一个分析器，现在基于这些中心点分类新对象，那么k-medoid将给你一个中心点更接近人类放置的中心。

用维基百科的话来说：

“与k-means相比，它[k-medoid]对噪声和异常值更加稳健，因为它最小化成对差异而不是平方欧几里得距离之和。”

下面是一个例子：

假设您要在一维上进行k=2的聚类。一个聚类大部分成员在1000附近，另一个在-1000附近；但是有一个异常值（或噪声）在100000。 它显然属于1000附近的聚类，但k-means会将中心点放在1000附近，而向100000方向移动。这甚至可能导致一些1000聚类成员（例如值为500的成员）被分配给-1000聚类。 k-medoid将选择1000附近的一个成员作为介质点，它可能会选择一个大于1000的成员，但不会选择异常值。

- Eli Algranti

Answer 3

只是在@Eli的回答中添加了一个细节，K-medoid比k-means更能处理噪点和异常值，因为后者选择的聚类中心大多只是"虚拟点"，而前者则从集群中选择"实际对象"。

假设您有一个包含（1,1），（1,2），（2,1），（2,2）和（100,100）坐标的二维点集。如果我们不考虑集群之间的对象交换，使用k-means您将得到集群中心（21.2,21.2），这个结果很受（100,100）点的干扰。然而，使用k-medoid将根据其算法在（1,1），（1,2），（2,1）和（2,2）之间选择中心。

这里有一个有趣的应用程序 ( E.M. Mirkes, K-means and K-medoids applet. University of Leicester, 2011 ) ，您可以在二维平面上随机生成数据集并比较k-medoid和k-means的学习过程。

- lennon310