1 、 K-mediods 算法介绍

a) 话说，聚类算法可以被分为那么几种，比如基于划分方法的、基于层次方法的、基于密度方法的、基于网格方法的、基于模型方法的； K-mediods 算法就是基于划分方法的一种聚类算法，确切的说，是对 K-means 算法的一种改进算法。

2 、 K-mediods 算法优缺点

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

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

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

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

a) 首先随机选取一组聚类样本作为中心点集

b) 每个中心点对应一个簇

c) 计算各样本点到各个中心点的距离（如欧几里德距离），将样本点放入距离中心点最短的那个簇中

d) 计算各簇中，距簇内各样本点距离的绝度误差最小的点，作为新的中心点

e) 如果新的中心点集与原中心点集相同，算法终止；如果新的中心点集与原中心点集不完全相同，返回 b)

a) 设有 (A,B,C,D,E,F) 一组样本

b) 随机选择 B 、 E 为中心点

c) 计算 D 和 F 到 B 的距离最近， A 和 C 到 E 的距离最近，则 B,D,F 为簇 X1 ， A,C,E 为簇 X2

d) 计算 X1 发现， D 作为中心点的绝对误差最小， X2 中依然是 E 作为中心点绝对误差最小

e) 重新以 D 、 E 作为中心点，重复 c) 、 d) 步骤后，不再变换，则簇划分确定。