K-medoids聚类算法在重新犯罪预测中的应用

1.K-medoids算法原理分析

上一节我们详细讲解了K-means算法，而K-medoids算法，从名字上就可以看出来，这两个算法应该有些相似的地方。其实，K-medoids可以算是K-means的一个变种。K-medoids和K-means不一样的地方在于中心点的选取，在K-means中，我们将中心点取为当前簇中所有数据点的平均值；然而在K-medoids中，我们将中心点的选取限制在当前簇所包含的数据点的集合中。换句话说，在K-medoids算法中，我们将从当前簇中选取这样一个点——它到其他所有（当前簇中的）点的距离之和最小——作为中心点。K-means和K-medoids之间的差异就类似于一个数据样本的均值（Mean）和中位数（Median）之间的差异：前者的取值范围可以是连续空间中的任意值，而后者只能在样本给定的那些点里面选。

那么，这样做的好处是什么呢？一个最直接的理由就是K-means对数据的要求太高了，它使用欧氏距离描述数据点之间的差异，从而可以直接通过求均值来计算中心点。这要求数据点处在一个欧氏空间之中。然而并不是所有的数据都能满足这样的要求，对于数值类型的特征，比如身高，可以很自然地用这样的方式来处理，但是对类别类型的特征就不行了。举一个简单的例子，如果我现在要对犬进行聚类，并且希望直接在所有犬组成的空间中进行，K-means就无能为力了，因为欧氏距离在这里不能用了：不同的类型显然无法进行数学运算，K-means在这里寸步难行。由于中心点是在已有的数据点里面选取的，因此相对于K-means来说，K-means不容易受到那些由于误差之类的原因产生的异常点的影响，更加鲁棒些。

2.K-medoids算法流程

算法流程如下：

（1）确定聚类的个数K；

（2）在所有数据集合中选择K个点作为各个聚簇的中心点；

（3）计算其余所有点到K个中心点的距离，并把每个点到K个中心点最短的聚簇作为自己所属的聚簇；

（4）在每个聚簇中按照顺序依次选取点，计算该点到当前聚簇中所有点距离之和，最终距离之和最小的点，则视为新的中心点；

（5）重复（2）（3）步骤，直到各个聚簇的中心点不再改变。

3.K-medoids算法优缺点(www.xing528.com)

（1）K-medoids算法具有能够处理大型数据集，结果簇相当紧凑，并且簇与簇之间明显分明的优点，这一点和K-means算法相同。

（2）同时，该算法也有K-means同样的缺点，如：必须事先确定类簇数和中心点，簇数和中心点的选择对结果影响很大；一般在获得一个局部最优的解后就停止了；对于除数值型以外的数据不适合；只适用于聚类结果为凸形的数据集等。

（3）与K-means相比，K-medoids算法对于噪声不那么敏感，这样离群点就不会造成划分的结果偏差过大，少数数据不会造成重大影响。

（4）K-medoids由于上述原因被认为是对K-means的改进，但由于按照中心点选择的方式进行计算，算法的时间复杂度也比K-means上升了O（n）。

4.K-medoids算法举例

（1）假设有（A，B，C，D，E，F）一组样本。

（2）随机选择B、E为中心点。

（3）计算D和F到B的距离最近，A和C到E的距离最近，则B、D、F为簇x1，A、C、E为簇x2。

（4）计算x1发现，D作为中心点的绝对误差最小，x2中依然是E作为中心点的绝对误差最小。

（5）重新以D、E作为中心点，重复（3）、（4）步骤后，不再变换，则簇划分确定。