8.2 基于划分的聚类（二）在线视频

k -中心点算法

不采用簇中对象的平均值作为参照点

而是选用簇中位置最中心的对象

即中心点作为簇的代表对象

以降低k-均值算法

对离群点数据敏感性

PAM算法是

最早提出的k-中心点算法之一

该算法首先为每个簇

随意选择一个代表对象

剩余的对象根据其与代表对象的距离

分配给最近的一个簇

然后反复地

用非代表对象来替代代表对象

以改进聚类的质量

为了判定一个非代表对象oˇj

是否是当前一个代表对象mˇi的好的替代

对于每一个非代表对象p

考虑下面的四种情况

①p当前隶属于代表对象mˇi

所代表的聚类

如果mˇi被oˇj所代替

且p离oˇi最近

i与j不等

那么p被重新分配给oˇi所在的聚簇

②p当前隶属于代表对象

mˇi所代表的聚类

如果mˇi被oˇj所代替

且p离oˇj最近

那么p被重新分配给oˇj

③p当前隶属于代表对象

mˇj所代表的聚类

且i与j不等

如果mˇi被oˇj所代替

且p离oˇi最近

那么对象的隶属不发生变化

④p当前隶属于代表对象

mˇj所代表的聚类

且i与j不等

如果mˇi被oˇj所代替

且p离oˇj最近

那么p被重新分配给oˇj

k -中心点算法的基本过程

分为以下几步

①从n个数据对象任意选择k个对象

作为初始聚类中心代表

②计算其余各对象

与这些中心对象间的距离

并根据最小距离原则

将各对象分配到离它最近的聚类中心

所在的簇中

③任意选择一个非中心对象oˇj

计算其与中心对象mˇi

交换的总代价TCˇij

④若TCˇij为负值

则交换oˇj与mˇi

以构成新聚类的k个中心对象

⑤循环②到④

直到每个聚类不再发生变化为止

TCˇij表示中心点mˇi

被非中心点oˇj替换后的总代价

由每一个对象的替换代价组成

计算公式如下所示

其中

Sˇijk为中心点mˇi

被非中心点oˇj替换后

对象oˇk的替换代价

假设对象oˇk原先属于

中心点mˇs所代表的簇

替换中心点后

属于中心点mˇt所代表的簇

则替换成本Sˇijk

计算公式如下所示

例 使用PAM算法进行聚类

数据对象集合D使用前例数据

作为一个聚类分析的二维样本

要求的簇的数量k=2

数据分布如前例

解

①样本点间欧几里得距离

计算结果如表所示

②建立初始聚簇中心

随机选择oˇ3 (1.5,0)

oˇ5 (5,2)

为簇Cˇ1和Cˇ2初始的聚簇中心

即mˇ1=oˇ3=(1.5,0)

mˇ2=oˇ5=(5,2)

③对剩余的每个对象

根据其与各个簇质心的距离

将它赋给最近的簇

根据表中的数据

对象oˇ1距mˇ1的距离

近于距mˇ2的距离

故将oˇ1分配给Cˇ1

对象oˇ2距mˇ1的距离

近于距mˇ2的距离

故将oˇ2分配给Cˇ1

对象oˇ4距mˇ2的距离

近于距mˇ1的距离

故将oˇ4分配给Cˇ2

于是得到两个簇

Cˇ1=包括oˇ1 oˇ2 oˇ3

Cˇ2包括oˇ4 oˇ5

聚类结果如图所示

其中红色点为簇中心点

④交换聚簇中心

用非聚簇中心点

oˇ1、oˇ2和oˇ4

分别代替中心点

oˇ3和oˇ5

分别计算替换后的代价

TCˇ31、TCˇ32、TCˇ34

和TCˇ51、TCˇ52、TCˇ54

用非中心点oˇ1

代替中心点oˇ3

计算TCˇ31

替换后的中心点为

oˇ1和oˇ5

计算每个对象

与中心对象之间的距离

按距离最小原则划对象

对象oˇ1距oˇ1的距离

近于距oˇ5的距离

故将oˇ1分配给oˇ1所代表的簇

对象oˇ1

原先属于中心点oˇ3所代表的簇

现在属于中心点oˇ1所代表的簇

则替换代价为

Sˇ311=

d(oˇ1,oˇ1 )-d(oˇ1,oˇ3 )

即oˇ1距oˇ1的距离

减去oˇ1距oˇ3的距离

结果为-2.5

对象oˇ2距oˇ1的距离

近于距oˇ5的距离

故将oˇ2分配给oˇ1所代表的簇

对象oˇ2

原先属于中心点oˇ3所代表的簇

现在属于中心点oˇ1所代表的簇

则替换代价为

Sˇ312=

d(oˇ2,oˇ1 )-d(oˇ2,oˇ3 )

=0.5

对象oˇ3距oˇ1的距离

近于距oˇ5的距离

故将oˇ3分配给oˇ1所代表的簇

对象oˇ3原先属于

中心点oˇ3所代表的簇

现在属于中心点oˇ1所代表的簇

则替换代价为

Sˇ313=

d(oˇ3,oˇ1 )-d(oˇ3,oˇ3 )

结果为2.5

对象oˇ4距oˇ5的距离

近于距oˇ1的距离

故将oˇ4分配给oˇ5所代表的簇

对象oˇ4原先属于

中心点oˇ5所代表的簇

现在仍属于

中心点oˇ5所代表的簇

则替换代价为

Sˇ314=0

对象oˇ5距oˇ5的距离

近于距oˇ1的距离

故将oˇ5分配给oˇ5所代表的簇

对象oˇ5原先属于

中心点oˇ5所代表的簇

现在仍属于中心点oˇ5所代表的簇

则替换代价为

Sˇ315=0

因此

用非中心点oˇ1

代替中心点oˇ3的替换总代价为

TCˇ31=

Sˇ311+Sˇ312

+Sˇ313+Sˇ314+Sˇ315

等于0.5

同理

可求得如下替换代价

用非中心点oˇ2

代替中心点oˇ3的替换总代价为

TCˇ32=-0.5

用非中心点oˇ4

代替中心点oˇ3的替换总代价为

TC34 = 7.5

用非中心点oˇ1

代替中心点oˇ5的替换总代价为

TCˇ51 = 3

用非中心点oˇ2

代替中心点oˇ5的替换总代价为

TCˇ52 =3.5

用非中心点oˇ4

代替中心点oˇ5的替换总代价为

TCˇ54=0

这样就完成了PAM的第一次迭代

发现若将中心点oˇ3

由非中心点oˇ2替换时

TCˇ32= -0.5

此时有替换代价小于0的替换

则使用此替换方案

替换后的中心点为

mˇ1=oˇ2=(0,0)

mˇ2=oˇ5=(5,2)

⑤重复④

用非聚簇中心点

oˇ1、oˇ3和oˇ4

分别代替中心点oˇ2和oˇ5

分别计算下列替换代价

TCˇ21、TCˇ23、TCˇ24

和TCˇ51、TCˇ53、TCˇ54

TCˇ21=1

TCˇ23 = 0.5

TCˇ24 = 8

TCˇ51 = 6.4

TCˇ53 = 4

TCˇ54 = 0

这样就完成了PAM的第二次迭代

发现没有代价小于0的替换

停止迭代

聚类结果如图所示

其中红色点为簇中心点

形成的两个聚类为

Cˇ1={oˇ1,oˇ2 ,oˇ3 }

Cˇ2={oˇ4,oˇ5}

此时的聚簇中心点为

mˇ1=oˇ2=(0,0)

mˇ2=oˇ5=(5,2)

PAM方法消除了

k-平均算法对于孤立点的敏感性

因为它最小化相异点对的和

而不是欧氏距离的平方和

但PAM算法的计算量较大

对小的数据集非常有效

对大数据集效率不高

特别是n和k都很大的时候

另外

k的取值对聚类质量有较大影响