代价

「K-中心点算法」（K-medoids）是一种距离计算聚类。选取有代表性的样本来表示整个簇，即选取最靠近「中心点」的那个样本来代表整个簇。可以降低聚类算法对离群点的敏感度。

如果代表样本能被非代表样本所替代，则替代产生的总代价 是所有样本产生的代价之和

其中， 是数据集中样本的个数， 表示中心点 被非中心点 代替后，样本点 的代价。

当非代表样本 替代代表样本 后，对于数据集中每个样本 ，它所属的簇的类别将有以下四种可能的变化

  • 原本属于 ，被分配给了另一个簇的代表点 。此时代价为
  • 原本属于 ，被分配给了 。此时代价为
  • 分配不变，此时代价为
  • 原本属于 ，被分配给了 ，此时代价为

算法

输入：聚类簇数 ，数据集

输出： 个簇

过程：

  • 随机选取 个对象作为最初每个簇的「代表点」
  • 循环：
    • 为每个剩余的对象分配到一个最近的代表点所对应的簇
    • 随机选择一个非代表性对象
    • 计算将某一个代表点 换成 的过程中的总代价
    • if
      • 将 和 交换，让 作为新的代表点
  • 直到代表点不再发生变化

例题

假设空间中的五个点 ，其距离矩阵如下

样本点 A B C D E
A 0 1 2 2 3
B 1 0 2 4 3
C 2 2 0 1 5
D 2 4 1 0 3
E 3 3 5 3 0

用 中心点算法实现聚类

解：

第一步，建立节点，假设初始抽取的中心点为 ，则得到的初始簇可以为

第二步，开始交换。现以

Interactive Graph
Table Of Contents
代价
算法
例题