我正在阅读有关k均值聚类和k-中心聚类之间的区别。
假设在 k-medoid 算法中使用成对距离度量有一个优势，而不是更熟悉的欧几里得距离类型度量的平方和来评估我们在 k 均值中发现的方差。 显然，这种不同的距离指标以某种方式减少了噪声和异常值。
我已经看到了这种说法，但我还没有看到任何关于这种说法背后的数学的好推理。
是什么让 k-中心点中常用的成对距离测量更好？ 更确切地说，缺少平方项如何使 k-中心点具有与取中位数概念相关的理想性质？
1.K-中心点更灵活
首先，您可以将 k 中心点与任何相似性度量一起使用。但是，K 均值可能无法收敛 - 它实际上只能与与均值一致的距离一起使用。因此，例如，绝对皮尔逊相关不能与 k 均值一起使用，但它适用于 k 中心点。
2. 中心体的鲁棒性
其次，k-中心点使用的中位数与中位数大致相当(事实上，也有k-中位数，这类似于K-均值，但对于曼哈顿距离)。如果你查找关于中位数的文献，你会看到大量的解释和例子，为什么中位数对异常值比算术平均值更健壮。从本质上讲，这些解释和示例也适用于中心点。它是比 k 均值中使用的均值更可靠的代表性点估计值。
考虑这个一维示例：
[1, 2, 3, 4, 100000]
该集合的中位数和中心点均为3。平均值为 20002。
您认为哪个数据集更能代表？平均值具有较低的平方误差，但假设此数据集中可能存在测量误差......
从技术上讲，统计中使用了击穿点的概念。中位数的细分点为 50%(即一半的数据点可能不正确，结果仍然不受影响)，而平均值的细分点为 0(即单个大型观测值可能会产生错误的估计值)。
我没有证据，但我认为中心点将具有与中位数相似的分解点。
3. K-中心点要贵得多
这是主要缺点。通常，PAM 的运行时间比 k 均值长得多。由于它涉及计算所有成对距离，因此O(n^2*k*i);而 k 均值在O(n*k*i)中运行，通常k*i << n迭代次数的 k 倍数。
，而K-Medoid将选择聚类的"最中心"成员。 在具有异常值(即远离集群其他成员的点)的聚类中，k 均值会将聚类的中心朝向异常值，而 k 中心点将选择一个聚类较多的成员(中心点)作为中心。
现在，这取决于您使用群集的目的。如果你只是想对一堆物体进行分类，那么你并不真正关心中心在哪里;但是，如果聚类用于训练决策器，该决策程序现在将根据这些中心点对新对象进行分类，那么 K-Medoid 将为您提供一个更接近人类放置中心位置的中心。
用维基百科的话说：
"与k-means相比，它[k-medoid]对噪声和异常值更可靠，因为它最小化了成对差异的总和，而不是欧几里得距离的平方和。
下面是一个示例：
假设您要在 k=2 的一个维度上聚类。一个集群的大多数成员在 1000 左右，另一个集群在 -1000 左右;但是在 100000 处有一个异常值(或噪声)。 它显然属于 1000 左右的集群，但 k 均值将使中心点远离 1000 并朝向 100000。这甚至可能使 1000 集群的某些成员(例如值为 500 的成员)分配给 -1000 集群。 K-Medoid 将选择一个大约 1000 的成员作为中心点，它可能会选择一个大于 1000 的成员，但它不会选择异常值。
只是在@Eli的答案中添加了一个很小的注释，K-medoid 比 k 均值对噪声和异常值更鲁棒，因为后者选择聚类中心，这主要只是一个"美德点"，另一方面前者从聚类中选择"实际对象"。
假设一个聚类中有五个 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) 中选择中心。
这是一个有趣的小程序(E.M. Mirkes，K-means和K-medoids小程序。莱斯特大学，2011 年)，您可以在 2D 平面中随机生成数据集并比较 k 中心点和 k 均值学习过程。