前一篇我们了解了一个最基本的 clustering 办法 k-means ，这次要说的 k-medoids 算法，其实从名字上就可以看出来，和 k-means 肯定是非常相似的。事实也确实如此，k-medoids 可以算是 k-means 的一个变种。

      k-medoids 和 k-means 不一样的地方在于中心点的选取，在 k-means 中，我们将中心点取为当前 cluster 中所有数据点的平均值：

并且我们已经证明在固定了各个数据点的 assignment 的情况下，这样选取的中心点能够把目标函数 J 最小化。然而在 k-medoids 中，我们将中心点的选取限制在当前 cluster 所包含的数据点的集合中。换句话说，在 k-medoids 算法中，我们将从当前 cluster 中选取这样一个点——它到其他所有（当前 cluster 中的）点的距离之和最小——作为中心点。k-means 和 k-medoids 之间的差异就类似于一个数据样本的均值 (mean) 和中位数 (median) 之间的差异：前者的取值范围可以是连续空间中的任意值，而后者只能在给样本给定的那些点里面选。那么，这样做的好处是什么呢？
一个最直接的理由就是 k-means 对数据的要求太高了，它使用欧氏距离描述数据点之间的差异 (dissimilarity) ，从而可以直接通过求均值来计算中心点。这要求数据点处在一个欧氏空间之中。

然而并不是所有的数据都能满足这样的要求，对于数值类型的特征，比如身高，可以很自然地用这样的方式来处理，但是类别 (categorical) 类型的特征就不行了。举一个简单的例子，如果我现在要对犬进行聚类，并且希望直接在所有犬组成的空间中进行，k-means 就无能为力了，因为欧氏距离 \|x_i-x_j\|^2 在这里不能用了：一只 Samoyed 减去一只 Rough Collie 然后在平方一下？天知道那是什么！再加上一只 German Shepherd Dog 然后求一下平均值？根本没法算，k-means 在这里寸步难行！

在 k-medoids 中，我们把原来的目标函数 J 中的欧氏距离改为一个任意的 dissimilarity measure 函数 ：

最常见的方式是构造一个 dissimilarity matrix \mathbf{D} 来代表 \mathcal{V}，其中的元素 \mathbf{D}_{ij} 表示第 i 只狗和第 j 只狗之间的差异程度，例如，两只 Samoyed 之间的差异可以设为 0 ，一只 German Shepherd Dog 和一只 Rough Collie 之间的差异是 0.7，和一只 Miniature Schnauzer 之间的差异是 1 ，等等。

除此之外，由于中心点是在已有的数据点里面选取的，因此相对于 k-means 来说，不容易受到那些由于误差之类的原因产生的 Outlier 的影响，更加 robust 一些。

扯了这么多，还是直接来看看 k-medoids 的效果好了，由于 k-medoids 对数据的要求比 k-means 要低，所以 k-means 能处理的情况自然 k-medoids 也能处理，为了能先睹为快，我们偷一下懒，直接在上一篇文章中的 k-means 代码的基础上稍作一点修改，还用同样的例子。将代码的 45 到 47 行改成下面这样：

 for j in range(k):            idx_j = (labels == j).nonzero()            distj = distmat(X[idx_j], X[idx_j])            distsum = ml.sum(distj, axis=1)            icenter = distsum.argmin()            centers[j] = X[idx_j[0][icenter]]

　　可以看到 k-medoids 在这个例子上也能得到很好的结果：

而且，同 k-means 一样，运气不好的时候也会陷入局部最优解中：

如果仔细看上面那段代码的话，就会发现，从 k-means 变到 k-medoids ，时间复杂度陡然增加了许多：在 k-means 中只要求一个平均值  即可，而在 k-medoids 中则需要枚举每个点，并求出它到所有其他点的距离之和，复杂度为  。