当前位置:   article > 正文

聚类篇——(三)K-Medoids聚类

k-medoids聚类

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

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

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 ( t k ( n − k ) 2 ) O(tk(n-k)^2) O(tk(nk)2) ,不能很好的扩展到大型数据库上去。

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/812992
推荐阅读
相关标签
  

闽ICP备14008679号