机器学习：K-中心点聚类算法

K-means 的弊端

K-means 算法对于离群点也是敏感的，因为一个具有很大的极端值的对象可能显著地扭曲数据的分布。

而且 K-means 准则函数中使用的平方误差函数更是严重地恶化了这一影响。

K-中心聚类的改进

不采用簇中对象的均值作为参照点，而是在每个簇中选出一个实际的对象来代替质心，称作代表对象

算法描述

K-中心点聚类算法中需要计算所有 非代表对象 和 代表对象 之间的相异度作为分组的依据，针对不同的数据类型有不同的相异度作为分组的依据，针对不同的数据类型有不同的相异度或距离函数。

若数据对象为数值型，选用曼哈顿距离。

$$d(i,j) = |x_{i1}-x_{j1}|+|x_{i2}-x_{j2}|+...+|x_{in}-x_{jn}|$$

K-中心聚类算法不断地用随机的非代表对象尝试去替换当前的代表对象，并使用 代价 来评价本次替换的好坏。

替换中心点后，某一个数据对象 p 的代价为：

$$代价 = d(O_{new}-p)-d(O_{old}, p)$$

将所有数据对象的代价计算后相加，即可以得到其代价总和。

• 代价小于 0，则代表这一替换是好的
• 代价总和越小越好

算法流程

1. 任意选择 K 个对象作为初始化中心点
2. 对所有对象指派为离他最近的中心点所在的簇
3. 在每个聚簇中按照顺序依次选取数据对象，计算用该数据对象替换原代表对象的代价，选择代价最小且小于 0 的数据对象进行替换
4. 重复2和3直到没有再发生代表对象的重新分配。