machine-learning - 是什么使得 k-medoid "better"中的距离测量值比 k-means 中的距离测量值高？

Question

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

据推测，在 k-medoid 算法中使用成对距离度量(而不是更熟悉的欧几里得距离平方和来评估我们使用 k-means 发现的方差)有一个优点。显然，这种不同的距离度量在某种程度上减少了噪音和异常值。

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

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

Answer 1

1。 K-medoid更加灵活

首先，您可以将 k-medoids 与任何相似性度量一起使用。然而，K 均值可能无法收敛 - 它实际上只能用于与均值一致的距离。所以例如绝对 Pearson 相关性不得与 k-means 一起使用，但它与 k-medoids 一起使用效果很好。

2。 medoid的鲁棒性

其次，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 .