K-Medoids算法

引入

K-Means算法高效, 使用广泛, 但对样本中的异常值十分敏感, 异常点的存在会使聚类的结果发生严重的偏离.

K-Medoids算法则消除了这种不足之处. 利用代表对象(即用样本中的一个点, 代表多个点)这种形式. 在消除噪声和异常值显著的背后, 是很高的算法复杂度, 计算效率很低, 只能再中小数据集中使用.

算法原理

在K-means算法的迭代中, 每次计算新的中心点时, 使用该簇的所有点计算平均值, 以这个平均值作为新的中心. K-Medoids算法不选用平均值, 而是采用簇中位置最中心的对象, 即中心点(medoids)作为参照点.

K-Medoids的重点, 在于中心点的选取. 选取簇中心点的原则为: 当前簇中所有其他点到该中心点的距离之和最小, 需要遍历簇中所有点. 其他的步骤与K-Means算法中的相同.

K-Medoids的使用绝对差值和(Sum of Absolute Differences, SAD)来的度量来衡量聚类结果的优劣, SAD的公式如下:

$\text{SAD}=\sum\limits_{m=1}^{k}\sum\limits_{p_i\in{C_m}}\sqrt{\sum\limits_{j=1}^{|C_m|}(p_{ij}-o_{ij})^2}$

PAM

PAM, Partitioning Around Medoids. PAM算法是K-Medoids算法的衍生算法. 基本流程如下:

• 首先随机选择k个对象作为中心, 把每个对象分配给离它最近的中心

• 然后随机地选择一个非中心对象替换中心对象, 每次交换一个中心点和非中心点, 然后执行将非中心点指派到最近的中心点, 计算得到的SAD值越小, 则聚类质量越好

• 如果总的损失减少, 则交换中心对象和非中心对象; 如果总的损失增加, 则不进行交换

• 聚类的过程就是不断迭代, 进行中心对象和非中心对象的反复替换过程, 直到目标函数不再有改进为止

在交换中心点和非中心点时, 应当遍历当前所有的中心点和非中心点, 选取最优的交换组合, 但这样的效率很低, 使用随机的方法代替遍历.

这种算法通常适用于聚类比较小的点的集合, 因为如果能够迭代所有情况, 那么最终得到的划分一定是最优的划分, 得到最好的聚类效果. 但是如果待聚类的点的集合比较大, 则需要通过限制迭代次数来终止迭代计算, 从而得到一个能够满足实际精度需要的聚类结果.

CLARA

CLARA, Clustering LARge Applications, 也是K-Medoids的一种衍生算法. 由于PAM在面对大样本时很慢, CLARA从数据集中抽取多个样本集, 对每个样本集使用PAM, 并以最好的聚类作为输出. 具体步骤如下:

• 设定从数据集中抽取子样本集的次数, 进行循环

  • 从整体数据集中抽取$N$个对象的样本子集, 调用PAM算法, 得到K个中心点
  • 将整个数据集中的所有样本点根据最近距离匹配到这K个样本点上

  • 计算SAD值, 如果当前的K个中心点对应的聚类结果计算得到的SAD值小于之前的模型, 则用现在的这K个中心点对应的模型作为最优模型

• 得到最优的聚类模型

参考资料

• 数据挖掘入门笔记——K-Medoids