聚类篇——（三）K-Medoids聚类

上一篇博文介绍了常用聚类算法之一K-means聚类，对其基本思想、优缺点、逻辑计算过程以及初始中心点的确定有了一定认识。本篇博文详细介绍另外一种常用聚类算法K-Medoids聚类。

K-Medoids算法的基本思想为： 对于给定聚类数目k，首先随机选择k个代表对象作为初始聚类中心，计算各剩余对象与代表对象的距离并将其分配给最近的一个簇，产生相应的聚类结果。然后开始迭代过程：对于每一次迭代，将随机选择的一个非中心点替代原始中心点中的一个，重新计算聚类结果。若聚类效果有所提高，保留此次替换，否则恢复原中心点。当替换对聚类效果不再有所提高，迭代停止。用代价函数来衡量聚类结果的质量，该函数用来度量对象与中心点之间的平均相异度，具体定义如下：
$E=\sum _{i=1}^k\sum _{p\in C_i}{\left|p-o_i\right|}^2$
其中，$p$是空间中的点，即为给定对象，$o_i$代表簇$C_i$的中心点，$E$则表示数据集中所有对象的离差平方和。
在进行新一轮中心替换后，以${}_{new}{C}_i,i=1,2,\cdots ,k$表示新中心集划分的簇，以${}_{old}{C}_i,i=1,2,\cdots ,k$代表原来的簇，它们的聚类评价函数分别为$E_{new},E_{old}$，则
$E_{new}=\sum _{i=1}^k\sum _{p{\in }_{new}{C}_i}{\left|p-o_i\right|}^2$
$E_{old}=\sum _{i=1}^k\sum _{p{\in }_{old}{C}_i}{\left|p-o_i\right|}^2$
由$E_{new},E_{old}$定义中心替换的代价函数为：$Cost=E_{new}-E_{old}$
聚类所要达到的目标是使得簇内各个对象之间的差异尽可能小，因此，若要判定一个非代表对象$o_{random}$是否是对当前中心点$o_i$的更优替换点，对于每一个非中心点对象$p$，每当重新分配时，平方-误差$E=\sum _{i=1}^k\sum _{p\in C_i}{\left|p-o_i\right|}^2$所产生的差别会对代价函数产生影响，替换所产生的总代价是所有非中心点对象的代价之和。若总代价的值小于零，即实际平方-误差减小，表明经过替换后，簇内对象之间的差异变得更小了，此时，可用$o_{random}$替换$o_i$作为新的中心点对象。反之，若替换所产生的总代价一直大于或等于零，则未能产生一个有效的替换，此时算法收敛。

K-Medoids聚类算法的具体步骤为：

输入：期望聚类数目k，包含n个数据对象的数据集。
输出：k个簇，使得所有点与其最近中心点的相异度总和最小。
步骤：
（1） 在n个数据对象中随机选择k个点，作为初始中心集；
（2） 计算每个非代表对象到各中心点的距离，将其分配给离其最近的簇中；
（3） 对于每个非中心对象，依次执行以下过程：用当前点替换其中一个中心点，并计算替换所产生的代价函数，若为负，则替换，否则不替换且还原中心点；
（4） 得到一个最终的较优k个中心点集合，根据最小距离原则重新将所有对象划分到离其最近的簇中。
说明：K-Medoids聚类初始中心的选择仍可采用最大距离法、最大最小距离法和Huffman树。

下面举一个实例，说明K-Medoids聚类的逻辑过程。 为研究不同地区的经济发展特点，根据各地区GDP、GDP指数、人均GDP指标数据，将北京市、天津市、江苏省等10个地区按照其经济水平分成3类。

• 采用正向/极差化法对数据进行标准化，并计算样本间的欧式距离；
  正向/极差化法
  
  欧式距离
  
  

• 采用最大距离法得到3个初始聚类中心；
  

• 按照距离最近原则将各对象划分到3个聚类中心所代表的簇中，此时离差平方和 E=2.4808，替换中心候选集为
  {北京市，河北省，黑龙江，吉林省，辽宁省，上海市，内蒙古}
  

• 聚类中心的迭代替换；
  （1）内蒙古替换天津市，则以内蒙古、山西省、江苏省为聚类中心进行分类得，离差平方和Enew=5.0114> Eold=2.4808，则用内蒙古替换天津市后，代价函数大于零，因此仍以天津市、山西省、江苏省为中心。此时替换中心候选集为 {北京市，河北省，黑龙江，吉林省，辽宁省，上海市}。
  
  （2）辽宁省替换天津市，则以辽宁省、山西省、江苏省为聚类中心进行分类得，离差平方和Enew=4.7274> Eold=2.4808，则用辽宁省替换天津市后，代价函数大于零，因此仍以天津市、山西省、江苏省为中心。此时替换中心候选集为 {北京市，河北省，黑龙江，吉林省，上海市}。
  
  （3）吉林省替换天津市，则以吉林省、山西省、江苏省为聚类中心进行分类得，离差平方和Enew=3.6267> Eold=2.4808，则用吉林省替换天津市后，代价函数大于零，因此仍以天津市、山西省、江苏省为中心。此时替换中心候选集为{北京市，河北省，黑龙江，上海市}。
  
  （4）北京市替换天津市，则以北京市、山西省、江苏省为聚类中心进行分类得，离差平方和Enew=1.6461< Eold=2.4808，则用北京市替换天津市后，代价函数小于零，因此以北京市、山西省、江苏省为中心。此时Eold=1.6461，替换中心候选集为 {河北省，黑龙江，上海市}。
  
  （5）上海市替换北京市，则以上海市、山西省、江苏省为聚类中心进行分类得，离差平方和 Enew=1.6861> Eold=1.6461，则用上海市替换北京市后，代价函数大于零，因此仍以北京市、山西省、江苏省为中心。此时替换中心候选集为 {河北省，黑龙江}。
  
  （6）黑龙江替换山西省，则以北京市、黑龙江、江苏省为聚类中心进行分类得，离差平方和Enew=1.6700> Eold=1.6461 ，则用黑龙江替换山西省后，代价函数大于零，因此以北京市、山西省、江苏省为中心。此时替换中心候选集为 {河北省}。
  
  （7）河北省替换山西省，则以北京市、河北省、江苏省为聚类中心进行分类得，离差平方和Enew=2.0172> Eold=1.6461，则用河北省替换山西省后，代价函数大于零，因此仍以北京市、山西省、江苏省为中心。此时所有对象都已经替换一次，迭代终止。

• 最终聚类结果
  

K-Medoids算法在抗噪声和孤立点的能力方面有了很大的提高，但是K-Medoids算法在处理起来花费时间比较长，算法的时间复杂度为$O(tk(n-k{)}^2)$ ，不能很好的扩展到大型数据库上去。

ps：初衷是通过撰写博文记录自己所学所用，实现知识的梳理与积累；将其分享，希望能够帮到面临同样困惑的小伙伴儿。如发现博文中存在问题，欢迎随时交流~~