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

据说在k-medoid算法中使用成对距离度量比使用我们常见的欧几里得距离平方和类型的度量来评估k-means中的方差有优势。显然，这种不同的距离度量可以减少噪声和异常值。

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

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

回答：

1. K-medoid更灵活

首先，你可以将k-medoids与任何相似度度量一起使用。然而，k-means可能无法收敛——它真的只能与与均值一致的距离一起使用。因此，例如，绝对皮尔逊相关系数不能与k-means一起使用，但它与k-medoids配合得很好。

2. 中位数的鲁棒性

其次，k-medoids使用的中位数大致相当于中位数（实际上，还有k-medians，它类似于K-means，但用于曼哈顿距离）。如果你查阅关于中位数的文献，你会看到很多解释和例子，说明为什么中位数对异常值比算术平均值更鲁棒。这些解释和例子基本上也适用于中位数。它是比k-means中使用的均值更鲁棒的代表点估计。

考虑这个一维的例子：

[1, 2, 3, 4, 100000]

这个集合的中位数和中位数都是3。均值是20002。

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

从技术上讲，统计学中使用了崩溃点的概念。中位数的崩溃点为50%（即一半的数据点可以是错误的，结果仍然不受影响），而均值的崩溃点为0（即一个大的观测值可以导致一个糟糕的估计）。

我没有证明，但我假设中位数将具有与中位数相似的崩溃点。

3. k-medoids的成本更高

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