我正在阅读k-means聚类和k-medoid聚类之间的区别。
据推测，在k-medoid算法中使用成对距离度量有一个优点，而不是更熟悉的欧几里德距离型度量平方和来评估我们用k均值找到的方差。显然，这种不同的距离度量以某种方式减少了噪音和异常值。
我已经看到了这个说法，但我还没有看到任何关于这一主张背后的数学的理由。
是什么使k-medoid中常用的成对距离测量更好？更准确地说，缺乏平方项如何使k-medoids具有与取中位数概念相关的理想属性？
首先，您可以使用任何相似性度量的k-medoids。然而，K-means可能无法收敛 - 它实际上只能用于与均值一致的距离。所以例如Absolute Pearson Correlation不能与k-means一起使用，但它适用于k-medoids。
其次，k-medoids使用的medoid与中位数大致相当（事实上，还有k-medians，就像K-means，但对于曼哈顿距离）。如果你查看关于中位数的文献，你会看到大量的解释和例子，为什么中值对异常值比算术平均值更强。从本质上讲，这些解释和例子也适用于medoid。对于代表点而言，它是比k均值中使用的平均值更稳健的估计。
考虑这个一维示例：
[1, 2, 3, 4, 100000]
该组的中位数和中位数均为3.平均值为20002。
您认为哪个更能代表数据集？均值具有较低的平方误差，但假设此数据集中可能存在测量误差...
从技术上讲，故障点的概念用于统计。中值具有50％的击穿点（即，数据点的一半可能是不正确的，并且结果仍未受影响），而平均值具有0的击穿点（即，单个大的观察可以产生不良估计）。
我没有证据，但我认为medoid将具有与中位数类似的分解点。
这是主要的缺点。通常，PAM比k-means需要更长的运行时间。因为它涉及计算所有成对距离，它是O(n^2*k*i);而k-means在O(n*k*i)中运行，通常，k次迭代次数是k*i << n。
我认为这与选择集群中心有关。 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的成员，但它不会选择异常值。
只有一个小小的音符添加到@ Eli的答案中，K-medoid对于噪声和异常值比k-means更强大，因为后者选择聚类中心，这主要是一个“美德点”，另一方面前者选择了集群中的“实际对象”。
假设您在一个簇中有五个2D点，坐标为（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），您可以在2D平面中随机生成数据集，并比较k-medoid和k-means学习过程。