武汉大学计算机学院模式识别(六)

武汉大学计算机学院本科生课程

模式识别

(PatternRecognition)

武汉大学计算机学院袁志勇

Email:yuanzywhu@163.com

第4章聚类分析

4.1分类与聚类的区别

4.2系统聚类/层次聚类

4.3分解聚类

4.4动态聚类（兼顾系统聚类和分解聚类）

4.5聚类分析编程举例

按照“物以类聚、人以群分”的基本思想，对未知类

别的样本集根据样本之间的相似程度分类，相似的归

为一类，不相似的归为另一类，故这种分类称为聚类

分析(Clusteringanalysis),又常常叫做噪类”。

相似性测度、聚类准则和聚类算法称为聚类分析的

三要素。

相似性测度用于衡量同类样本的类似性和不同类样

本的差异性。常用的测度有：距离、夹角余弦、相似

系数等(详见第一讲课件)。

为了评价聚类效果的好坏，必须定义准则函数。有

了模式相似性测度和准则函数后，聚类就变成了使准

则函数取极值的优化问题了。常用的准则函数是误差

平方和准则。

4.1分类与聚类的区别

分类(Classifying)：用已知类别的样本训练集

来设计分类器(有监督学习：supervised

learning)

我们在前面设计分类器时，训练样本集中

每个样本的类别归属都是“被标记了”的

(labeled),这种利用已标记样本集的学习方法

称为有监督学习方法。

聚类/集群(Clustering)：事先不知样本的类

别,、而利用样本的先验知识来构造分类器(无监

督学习：unsupervisedlearning)

4.2系统聚类

系统聚类（又叫层次聚类/谱系聚类法：Hierarchical

ClusteringMethod）：先把每个样本（或指标）各自作为一类，

然后根据样本间的相似性和相邻性聚合。即将亲疏程度最高

的两类合并，如此重复进行，直到所有的样本都合成一类。

衡量亲疏程度的指标有两种：距离、相似系数。

相似性、相邻性一般用距离表示。

一、两类间的距离

L最短距离：两类中相距最近的两样本间的距离。

D=mind

PQxecou

1J

7rn

Xi£C0〃

为表示第i个样本与第j个样本之间的距离。

2.最长距离：两类中相距最远的两个样本间的距

离。

Dpq=maxd

X,GCOJ

Lrn

xJiecoC„1

3.中间距离：最短距离前最长距离都有片面性，

因此有时采用中间距离。假设某一步将32与33

合并为类323,需要计算323类与某类口1的距离。

设巴类和323类间的最短距离为&2,最长距离为

43，323类的长度为右3，则类口1与类323的中间

距离定义为：

212112

d。=^4口+gd]3_1423

d：——H—4?+（Bdj

2,1JIND

上式推广为一般情况：1

其中p为参数，—工40<0

4.重心距离：两类的均值（向量）之间的距离

5.类平均距离：两类中各个元素两两之间的距离平

方相加后取平均值

=」一

pqNNJ

iNpiNqxap

XJe(Oq

其中，N〃：C类的样本数，Ng：4类的样本数

rrL1C1

4为%类样本点，与q类样本点J•之间的距离

6.离差平方和：

（1）设N个样本已分为q类Gi，G2，・・.,Gg,则定

义第i类样本的类内离差平方和为：

Si=E（Xji-Xi）T（Xj「Xi）

j=l

这里：

X,表示第，类（即GJ的第7个样本；

工为第i类所有样本的均值（即G,的重心）；

N,为第z•类的样本个数。

⑵离差平方和增量：设样本已分成3p、3q两类,

若把＜%、合并为%类，则定义离差平方增量:

片=sf+J)

其中,S,分别为叼类和叼类的离差平方和；

S「为例类的离差平方和；

增量愈小，合并愈合理。

八系统聚类/层次聚类算法

系统聚类基本思想：将距离阈值作为决定聚类数目的标

准，基本思路是每个样本先自成一类，然后按距离准则逐

步合并，减少类别数，直到达到分类要求为止。

系统聚类算法步骤描述：

⑴初始分类。假设有N个样本，每个样车自成一类，则有

N类:Gi(O),G2(0),GN(O){d(k)表示第k次合并时的

第i类，此步k=0}。

(2)计算各类之间的距离,得mXm维的距离矩阵

D(k),m为类别个数(初始时m=N,k=0)。

(3)找出距离矩阵D(k)中类间距离最小的元素，如果

它对应着G4k)和G/k),则将类G/k)与G/k)合并为一

类，由此得到新的聚类G[(k+1),G2(k+1),...o令

k=k+1,m=m—1,计算曲离矩阵D(k)。

(4)若D(k)中类间距离最小值大于距离阈值T,则算

法停止(这意味着所有类间距均大于要求的阈值T,

各类已经足够分开了)，所得分类即为聚类结果(或

者，如果所有的样本被聚成两类，则算法停止)；否

则，转(3)。

系统聚类法将样本逐步聚类，类别由多到少。

系统聚类算法的特点是在聚类过程中类的中心不断

地调整，但样本一旦归到某个类以后就不会再改变

三、系统聚类举例，如下图所示

G3G1G2G5G4G6

-4_i।।i।i।i-i——>%

12345678910

⑴设全部样本分为6类;

⑵作距离矩阵D(0),见下表:

G)]3Q

02<3%05

G)9

乙9

G)216

%491664

3二

5254364

3公0

66425819

R————————————卜曲

⑶求最小元素；

(4)把3合并37=(1,3)；a4,川6合并o8=(4,6)；

(5)作距离矩阵D(l)；

370238

029

084916

3525

说明：这里采用最小距离法求距离D⑴。

⑹若合并的类数没有达到要求，转(3)；

否则停止。________

(3)求最小元素。

(4)3夕35,32合并，3厂(2,5,4,6)。

“10

一①9

叫

-----树状图/系统聚类树

①6

CDO.

4.3分解聚类

分解聚类：把全部样本作为一类，然后根据相似性、相邻

性进行分解。

通俗地说，分解聚类法是首先把全部样本当作一类，

然后再分为两类，三类，…，直至所有的样本自成一类为

止。

目标函数：两类均值（重心）方差

NM————/———

£二k（Xl—%2）（由一12）

N：总样本数，No31类样本数,

N2：32类样本数。

下面介绍一分为二的方法：

设有N个样本当作一类记为3,将它分成两个子类叫和a2且

各有N1和N2个样本,记,，31，32的重心分别为五年兀。3,

31,0）2的离差平方和分别为:

s=Z（七一元）’（％-亍）

邑二£（七一弓）'（毛一币），j='，2

XjECOj«/«/

“一分为二”的思想就是要使S1+S2尽可能小,或使s-srs2

尽可能大。

可以证明（此略）：

E=S-S-S.

}JL，

=竽（石-弓），（弓-弓）

N：总样本数，N"31类样本数，

N2：32类样本数。

把上面两类均值（重心）的方差£作为目标函数,

选择某种分法使得£达到最大。

对分法(一分为二法中的一种)：

一开始所有n个样本均在:a1中，然后找一个样本把它

归入32使E达到最大，接着再找第二个样本归入32使E

达到最大，如此继续下去(某样本一旦归入,2后，该样本在

以后的划分中就不再回到31)o

令E(k)表示32中有k个样本，那么一定存在k*使得：

V(k*)=maxE(k)

1WkWn

于是将前k*次进入32的样本归为一类，其余n-k*个

样本为另一类。再将上述步骤应用于每个子类直至每个样

本都自成一类。

举例1：已知21个样本，每个样本有两个特征,

原始资料列表如下：

样本号12345678910

巧0022445667

*6553431210

1112131415161718192021

-4-2-3-3-5100-1-1-3

322021-1-2-1-3-5

解：第一次分类时计算所有样本，分别划到G2时

的E值，找出最大的。

1、开始时，6:=区，/，・・・，孙）6：=空

-（o）_（）0

0.714—°（o）（0）

,，%―1.333=（0）NA71=2i，NA7?二°

，目标函数E=—X^-2（X1-X2）r（Xl-X2）=0

N

2、分别计算当Xi22，・・・』n划入G2时的E值

把%1划入G2时有:

fflH

—(0)

一(1)—(0)Xif

=+

XiXiN?-1

0.7140

(…，一(，

0.7141.33360.75

二()+-一（1.10），

1.333(21-1)

一（i）0

%2=(6)

E=型迎[O.752+(1.10—6)2]=23,40

21

然后再把%233,…321划入G2时对应的E值,找出一

个最大的E值。

把％21划为G2的E值最大。

'GT二(X1，X2，・・・，X2O)，G「=(X21)

O3

(\

\XN(N/!

X-.912-1-202-

1175

A.65

E(l)=56.6

此时，将Qi固定在G(；)中，再继续进行第2、第

3次迭代，…;计算出E(2),E(3),…。

迭代次数(k)G1-G2E值

1X2156.6

2X2079.16

3X1890.90

4%14102.61

5X15120.11

6X19137.15

7孙154.10

8X13176.15

9X12195.26

10X17213.07

11%16212.01

第10次迭代工17划入G2时，E最大。于是分成

以下两类:一=（再,12,…，石0,石6）

G?—（玉］,X］2,%13,114,占5，％17,%18，%19,%20,121）

每次分类后要重新计算工1，12的值。可用以

下递推公式£_

k

x，+D=%「）+（x:）一xj/（N\）—1）

铲）=针）_（兀出一］）/（N*+1）

君

第

类

步

均

值

分

时

对

是

E7\两

KK/1左

7•

次

时

k分

是

k1对

下

X+AX+巴X

1夕2

左

左

类

均

值

戈

时

的

从

\到\

/r(两

G\|71MG71

U2

A1

左

类

本

样

数

(为

NN二

2

1

举例2：运用分解聚类法对经济差距进行分类统计与决策（

一篇小型论文）。

论文来源：

万树平「甚用分解聚类法对经济差距的分类统计与决策，

统计与决策，2007年第5期，P139o

（可在学校图书馆网站进“中国期刊网”或“重庆维普”

检索“运用分解聚类法对经济差距的分类”，然后下载

文件即可）

具体内容详见“运用分解聚类法对经济差距的分类

.PDF”文档。

4.4动态聚类（兼顾系统聚类和分解聚类）

、动态聚类法概要

（DynamicClusteringAlgorithm）

动态聚类法首先选择若干个样本作为聚类中心，

再按照事先确定的聚类准则进行聚类。在聚类过程中，

根据聚类准则对聚类中心进行反复修改，直到分类合理

为止。

动态聚类有如下三个要点：

1）先选定某种距离作为样本间的相似性度量；

2）确定评价聚类结果的准则函数；

3）给出某种初始分类，用迭代法找出使准则函数取极值

的最好的聚类结果。

动态聚类法基本思想如下图所示。“动态”即指聚类过

程中，聚类中心不断被修改的变化状态。

图动态聚类基本思路框图

二、代表点的选取方法：代表点就是初始分

类的聚类中心数k

1.凭经验选代表点，根据问题的性质、数据分布，

从直观上看来较合理的代表点k；

2.将全部样本随机分成k类，计算每类重心，把这

些重心作为每类的代表点；

3.按密度大小选代表点

以每个样本作为球心，以d为半径做球形；落在球

内的样本数称为该点的密度，并按密度大小排序。首先

选密度最大的作为第一个代表点，即第一个聚类中心。

再考虑第二大密度点，若第二大密度点距第一代表点的

距离大于6（人为规定的正数），则把第二大密度点作为

第二代表点，否则不能作为代表点，这样按密度大小考

察下去，所选代表点间的距离都大于6。di太小，代表

点太多，d]太大,代表点太小，一般选d]=2d。对代表

点内的密度一般要求大于T。T>0为规定蚓一个正数。这

样选择k个样本（即k个代表点）作为初始聚类中心。

4.用前k个样本点作为代表点。J（最简捷常用）

三、初始分类和调整

1.选一批代表点后，代表点就是聚类中心，计算其

他样本到聚类中心的距离，把所有样本归于最近

的聚类中心点，形成初始分类，再重新计算各聚

类中心，称为成批处理法。

2.选一批代表点后，依次计算其他样本的归类，当

计算完第一个样本时，把它归于最近的一类，形

成新的分类。再计算新的聚类中心，并计算第二

个样本到新的聚类中心的距离，对第二个样本归

类。即每个样本的归类都改变一次聚类中心。此

法称为逐个处理法。

3,直接用样本进行初始分类，先规定距离d,把

第一个样本作为第一类的聚类中心，考察第二个

样本，若第二个样本距第一个聚类中心距离小于

d,就把第二个样本归于第一类，否则第二个样

本就成为第二类的聚类中心，再考虑其他样本，

根据样本到聚类中心距离大于还是小于d,决定

分裂还是合并。

4.最佳初始分类

K均值算法，其聚类中心数目（初始分类数目）

假定已知为K个。如下图所示，随着初始分类K的

增大，准则函数下降很快，经过拐点A后，下降

"逮飕减慢:拐酒才就是最佳初始分类。

J.准则函数

下降快

拐点

下降慢

，K

°1234567

最佳初始分类

四、K次平均算法/K均值算法:成批处理法

(K/C-means)

K均值算法也称。均值算法，是根据函数准则进行分类

的聚类算法，基于使聚类准则函数最小化。这里所用的聚类

准则函数是聚类中每一个样本点到类聚类中心的平方和。对

于第/个聚类集，准则函数定义为

Nj

i=\

式中,G/表示第/个聚类集,也称为聚类域,其聚类中心为RM为

第/个聚类域G,所包含的样本个数.

对所有K个模式类有准则函数：

K*2

「EE卜-Z』四『

j=li=l

K均值算法的聚类准则是:聚类中心z,的选择应使准则函数/极小,

也就是使乙的值极小，要满足这一点,应有：

dJj

­二0

3Lri

oN：a%

即：…卜

可解得：

]Nj

4卞中,X3Gj

上式表明,G/类的聚类中心应选为该类样本的均值.

K均值算法使用的聚类准则函数是误差平方和准

则，通过反复迭代优化聚类结果，使所有样本到各

自所属类别的中心的距离平方和达到最小。

条件：设待分类的模式向量集为{X"".”XN},

类的数目K是事先取定的。

应。均值算法步骤描述：

⑴任选K个初始聚类中心：句(0),句(0),…,加0)；

其中，圆括号中的数字表示聚类过程中的迭代运算

次数，用r表示，令初值r=0。

⑵将待分类的模式特征集{%}中的模式逐个按最

小距离原则划分给K类中的某一类，即：

如果d〃(r)=mjn{&.(r)}=mjnxz.-zy(^)||(i=l,2,...,N)

则判定x;.GGj(r+1)(j=1,2,K)

式中分⑺表示%和G/C)的聚类中心z«)的距离，

VLJJ

r表示迭代次数。于是产生新的聚类G/r+1)(j=l,2,…,K)

(3)计算重新分类后的各聚类中心，即:

Z(r+l)=Z为1=1,2,…,K)

si%U十Rx,eGy(r+1)

式中%(r+1)为x£G/C+1)类中所含模式样本的个数。

IIIIII「

因为这一步采用取平均的方法计算调整后各类的中心,

且定为K类，故称为K均值法。

II

性曲山二曲山二曲山二曲山二曲山二曲山二曲山二曲山会

(4)如果4(r+l)=Zj(r)(j=l,2,…,K),则结束;

否则，r=r+L转至(2)。

K均值算法讨论:

K均值算法是否有效主要受以下几个因素的影响：

⑴选取的聚类中心数(代表点)是否符合模式的实际分布；

⑵所选聚类中心的初始位置；

(3)模式样本分布的几何性质；

(4)样本读入的次序。

实际应用中，需要试探不同的K值和选择不同的聚类

中心初始值。如果模式样本形成几个距离较远的孤立分布

的小块区域，一般结果都收敛。

五、K均值算法举例

已知有20个样本，每个样本有2个特征，数据

分布如下图，K=2,试用K均值法进行聚类。

样本序号X1X2X3X4X5X6X7X8X9X10

特征X]0101212367

特征工20011122266

xnX12X13X14X15X16X17X18X19X20

8678978989

6777788899

A

111111LIMmJlLU1111111L-fflU1111111LIMMmiU1111111LUiLLMfflU11111

；第一步：K=2,选初始聚类中心为

Z/0)=玉=(0,0y;Z2(0)=x2=(1,0)

二田二曲山二曲山二曲山二曲山二曲山二曲山二曲山二曲山二曲山二曲山二曲山二曲曲由M

(0、。

第二步:卜]—Z](0)||=⑼=0

[1、

X]_Z2(0)=「°、=1

O

因为演―Z[(0)|<k-Z2(0)||

所以国wG](l)

rnroA

%—4(0)=1

h-z(o)二0

2⑼⑼

因为房二乙⑼>

所以“G2⑴

同理

I|x3-Z\(O)||=l<||x3-Z2(0)||=2,.•.x3eG】(1)

旧—Z\(0)||=2>||X4-Z2(0)||=1,/eG2(l)

同样把所有%,4,…，％o与第二个聚类中心的距离

计算出来，判断匕居，…，/。都属于G2⑴

因此分为两类：

1、G1(1)=(X1,X3),

2、G2(1)=(x2,X4,X5，・・・，*20)

M=2应=18

第三步：计算新的聚类中心

i1i「@@

Z"l)=wZX=5(⑼+(1

7V1M(l)J

1代、

=(0,0.5/

5匕

z2(1)=—£x=

N2舄

二(5.67,5.33)7

第四步:因4⑴wZ/(0)(j=l,2),故Lr+1=1,转第二步’。

第二步'：由新的聚类中心，得

W—Z](l)||<||x/-Z2(l)||/=1,2,…,8

"―Z](l“〉卜/—Z2(l)||Z=9,10,...,20

故得：

G[(2)=(X],%2,…,％8)，N[=8

G2⑵—(X9，"io,…,，20)，N2—12

第三步、计算聚类中心

]]

2j(2)=——EX=G(X]+々+工3+…+/)

N1XGG,(2)8

=(1.25,1.13/

Z2(2)=­ZX=不(/+%0+…+%0)

N2xeG2(2)1/

二(7.67,7.33)

第四步，：因242)。2/1)"=1,2/=r+1=2,转第二步〃。

第二步”：重新计算用,%,…,超0到Zi(2),Zz(2)的距离，

分别把玉,Z，…，/o归于最近的那个聚类中心，

重新分为二类G]⑶=—,%，•・・，/)

G)⑶二(元9,国0,…，/。)，N[=8,N2=\2

第三步”：更新聚类中心

Z43)=ZI(2)=(1.25,1.13)7

r

Z2(3)=Z2(2)=(7.67,7.33)

第四步”：

因Z/3)=Zj(2)(j=l,2),不再出现新的类别划分，故分类过程结束。

4.5聚类分析编程举例

一.MATLAB中常用的计算距离的函数

MATLAB软件包中主要使用系统聚类法。

设有用X几阶的数据矩阵X=区,X2,xjr,每一行是一个样本数据

(即X矩阵有用个模式样本,每个模式样本有几个特征)。

MATLAB中常用计算样本点间距离的函数如下：

y=pdist(x)%计算样本点之间的欧氏距离

55

y=pdist(x3mahal)%计算样本点之间的马氏距离

55

y=pdist(x5minkowski3p)%计算样本点之间的明考夫斯基距离

y=pdist(x；cosine')%计算样本点之间的余弦距离

另外，函数yy=sqareform(y)表示将样本点之间的距离用矩阵的形

式输出。

二.创建系统聚类树

「锯巨型看蓟辉不威芝荷的距离y,可以用linkage函数创建

系统聚类树，格式为：

z=linkage(y)%用最短距离法创建系统聚类树

其中：Z为一个包含聚类树信息的(m-1)x3的矩阵，前两列为索引标

识，表示哪两个序号的样本可以聚为同一类；第三列为这两个样本之间的

距离；另外除了m个样本以外，对于每次新产生的类，依次用m+1、

m+2、…来标识。如：

z=

2.0005.0000.2

3.0004.0001.28

贝!Jz的第一行表示第2、第5个样本点连接为一个类，它们的距离为

0.2;z的第二行表示第3、第4个样本点连接为一个类，它们的距离为1.28。

二.创建系统聚类树(Cont.)

MATLAB创建聚类树的函数linkage：

z=linkage(y)%表示用最短距离法创建系统聚类树

z=linkage(y,Single9)%表示用最短距离法创建系统聚类树

z=linkage(y/complete,)%表示用最长距离法创建系统聚类树

z=linkage(y,Average9)%表示用平均距离法创建系统聚类树

z=linkage(y/centroid，)%表示用重心距离法创建系统聚类树

z=linkage(y/ward,)%表示用离差平方和递增法创建系统聚类树

为了表示z矩阵，我们可以用更直观的聚类树状图来展示，方法为

使用dendrogram(z)产生的聚类树状图，图的最下边表示样本，然后一

级一级往上聚类，最终成为最顶端的一类；纵轴高度代表距离列。

三.聚类分析程序举例

例1：在MATLAB中编辑名为ex6_Lm的程序文件。

%Filename:ex6_l.m

%创建系统聚类树

x=[31.7;11;23;22.5;1.21;1.11.5;31];

y=pdist(x,,mahar);

yy=squareform(y)

z=linkage(y,Centroid*)%用重心距离法创建系统聚类树

h=dendrogram(z)%生成树状图(这里即为聚类树状图)

yy=

02.38792.19831.69462.16842.22840.8895

2.387902.60972.06160.23780.62552.3778

2.19832.609700.63532.55222.01532.9890

1.69462.06160.635301.97501.51062.4172

2.16840.23782.55221.975000.66662.1400

2.22840.62552.01531.51060.666602.4517

0.88952.37782.98902.41722.14002.45170

z=

2.00005.00000.2378

6.00008.00000.6353

3.00004.00000.6353

1.00007.00000.8895

9.000010.00002.1063

11.000012.00002.0117

按重心距离法得到的系统聚类树如下:

Figure1□00

EileEditViewInsertloolsDesktopWindowHelp

口田口昌4阪0等与南口目□D

2

1.8

1.6

1

0.8

0.6

0.2

2563417

MATLAB聚类分析方法：

L根据系统聚类树创建聚类

根据已求出的系统聚类树z,使用cluster函数构造聚类。

例2：根据系统聚类树创建聚类。

%Filename:ex6_2.m

x=[31.7;11;23;22.5;1.21;1.11.5;31];

y=pdist(x/mahar);

yy=squareform(y)

z=linkage(y,4single5)%用最近距离法创建系统聚类树

h=dendrogram(z)%生成树状图(这里即为聚类树状图)

t=cluster(z,3)%分成三个聚类

输出结果:

t=

3

1

左边输出结果的含义：第、第

21

样本点为第类，第、第、

27325

第样本点为第类，第、第

16134

样本点为第类。

12

3

2.根据原始数据创建聚类

在MATLAB中，可使用clusterdata函数对原始数据

进行聚类，格式有两种：

(l)clusterdata(x,a),其中Ovavl,表示在系统聚类树中距离

小于a的样本点归结为一类；

(2)clusterdata(x,b),其中b>l且为整数，表示将原始数据x

分为b类。

说明：利用chisterdata函数对数据样本进行一次聚

类的方法简洁方便，但使用范围较窄(不能由用户根据自

身需要设定参数以及不能更改距离的计算方法)。

例3：由原始数据创建聚类。

%Filename:ex6_3.m

%根据原始数据创建聚类

x=[31.7;11;23;22.5;1.21;1.11.5;31];

t=clusterdata(x,0.5)%距离小于0.5的样本点归为一类

z=clusterdata(x,3)%将原始数据x分为3类

42

t的输出结果共有四z的结果约定将原始数

33

类，第类：样本点据分为三类。Z的输出

211

6；第2类：样本点3结果为，第1类：样本

21

和4；第3类：样本点3和4；第2类：样本

33

点2和5；第4类：样点1和7；第3类：样本

13

本点1和7。点2、5和6。

42

3.分步聚类法

设有样本数据矩阵x:

Step1:对于不同的距离，禾佣pdist函数计算样本点之间的距离。

yl=pdist(x)%欧氏距离

y2=pdist(x/mahaP)

y3=pdist(x,Minkowski9,1)%p=l为绝对距离/城市距离

Step2:计算系统聚类树及相关信息。

zl=linkage(yl)

z2=linkage(y2)

z3=linkage(y3)

Step3:利用cophenet函数计算聚类树信息与原始数据的距离

之间的相关性，该值越大越好(利用cophenet函数评价聚类信

息)。

tl=cophenet(zl,yl)

t2=cophenet(z2,y2)

t3=cophenet(z3,y3)

注意：z在前y在后，顺序不能颠倒。

Step4:选择具有最大的cophenet值的距离进行聚类。

利用函数chisterdata(x,a)对数据进行聚类，其中OvavL

表示系统聚类树距离小于a的样本点归为一类。

例4：分步聚类法示例。

x=[31.7;11;23;22.5;1.21;1.11.5;31];

yl=pdist(x);%欧氏距蔺

y2=pdist(x,1mahal1);

%y3=pdist(x/minkowski\l);%p=l为绝对距离/城市距离

y3=pdist(x,*cityblock1);

zl=linkage(yl);

z2=linkage(y2);

z3=linkage(y3);

tl=cophenet(zl,yl)

t2=cophenet(zl,y2)

t3=cophenet(zl,y3)

tl=

0.9291

t2=

0.9103

t3=

0.9161

由于”的值最大，可见此例利用欧氏距离最合适。于

是，可编写另一个文件名为ex6_4a.m的文件。

%Filename:ex6_4a.m

x=[31.7;11;23;22.5;1.21;1.11.5;31];

yl=pdist(x);%欧氏距离

zl=linkage(yl)

zl=

2.00005.00000.2000

3.00004.00000.5000

6.00008.00000.5099

1.00007.00000.7000

9.000011.00001.2806

10.000012.00001.3454

矩阵zl的第1行表示样本点2、5为一类，在系统聚类树

上的距离为0.2,其他类推。考察矩阵的第3列，系统聚类

树上的6个距离，可以选择0.5作为聚类分界阈值。于是，

可编写另一个文件名为ex6_4b.m的文件。

%Filename:ex6_4b.m

x=[3L7;l1;23;22.5;121®1.5;31];

yl二pdist(x);切欧是距离

zl=linkage(yl)

t=cluster(zl,0.5)

%h=dendrogram(zl)

输出结果：

t=

4

3-------------------------------------

2即分为四类，第1类：样本

2点6;第2类样本点3和4；第

33类：样本点2和5；第4类：

]|样本点1和7。

4

4.K均值聚类法的MATLAB实现

在MATLAB中直接调用如下语句即可实现胺值聚类:

[IDX,C,SUMD,D]=kmeans(data,K);

其中，data:要聚类的数据集合，每一行为一个样本;

IDX:聚类结果；C:聚类中心；SUMD:每个样本到该中

心的距离和；D:每个样本到各聚类中心的距离；K:分类

的数目。

!■■■■■■■■■■■■!

!■■■■■■■■■■■■!

例：已知有59个样本，每个样本有3个特征值，数据分布见

下表所示（表中只列出部分，其余见程序中的data数据矩阵）

,K=4,试写出K均值聚类法对其进行聚类的程序。（K均

值聚类MATLAB程序名：kmns.m）

表样本数据

序号ABc所属类别

11739.941675.152395.96未知

2373.33087.052429.47未知

ooooooooooooooo

581817.361927.42328.79未知

591860.451782.881875.13未知

分析：

若使用命令[IDX,C,SUMD,D]=kmeans(data,4)进行

聚类，IDX列向量返回的是聚类结果(向量中第i个元素

值表示第i个模式样本所对应的类别号)。若想画出4个聚

类的图形,可采用如下程序片段：

D=D，%得到每个样本至1)4个聚类中心的距离

minD=min(D);%找到每个样本至1)4个聚类中心的最小距离

indexl=find(D(l,:)==min(D))%找到属于第1类的样本点

index2=find(D(2,:)==min(D))%找到属于第2类的样本点

index3=find(D(3,:)==min(D))%找到属于第3类的样本点

index4=find(D(4,:)==min(D))%找到属于第4类的样本点

为了提高所显示图形的区分度，添加如下程序片段:

line(data(index1,l),data(indexl,2),data(index1,3),'linestyle','none','marker',1*','color','g')；

Iine(data(index2,l),data(index2,2),data(index2,3),'linestyle','none','marker',1*','color','r');

Iine(data(index3,l),data(index3,2),data(index3,3),'linestyle','none','marker','color','b');

Iine(data(index4,l),data(index4,2),data(index4,3),'linestyle','none','marker','color','y');

初始分类的选取与调整：

K均值算法的分类数目假设已知为K。当K未知时，

可以令K逐渐增加；使用K均值算法，误差平方和J随K增

加而单调减少。最初，由于K较小，类的分裂会使人迅速

减少，但当K增加到一定的数值时，人的减少速度会放慢

,即随着初始分类K的增大，准则函数下降很快，经过拐

点后，下降速度减慢。拐点处的K值就是最佳分类数目。

M寸阳寸阳寸阳寸加寸阳寸木忖；忖；忖；忖；忖；忖；忖；忖；忖；忖；忖；忖；忖；忖寸木

⑴当分类数目K=2时，调用[10*,(3,311]\«>2]41加2115((1212,2)实现长均

值聚类：

SUMD=

1.0e+007*

1.4810

1.0599

J=25.409*106

44二田二曲山二曲山二曲山二曲山二曲山二曲山二曲山二曲曲由4s

⑵当分类数目K=3时，调用[10*,(3,311]\«>2]41加2115((1212,3)实现长均

值聚类：

SUMD=

1.0e+006*

1.4058

0.3332

7.3544

J=9.0934*106

卜RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR田■田■田■田M

⑶当分类数目K=4时，调用［10*«,31；］\1»必411^115（（^即4）实现长均

值聚类：

SUMD=

1.0e+006*

1.1820

1.5262

0.3332

1.4058

J=4.4472*106

44二田二曲山二曲山二曲山二曲山二曲山二曲山二曲山二曲曲由4s

(4)当分类数目K=5时，调用[10*,(3,311]\«>2]41加2115((1212,5)实现长均

值聚类：

SUMD=

1.0e+006*

0.3332

0.0437

0.8008

0.9260

1.4058

J=3.5095*106

1slsmgrngk由二由j・田smsHsism二由

⑸当分类数目K=6时，调用[1口弘（：,511]\«）2]=：1«11©4115（（121%6）实现长均

值聚类：

SUMD=

1.0e+006*

0.4764

1.2492

0.3223

0.2014

0.5362

0.3332

J=3.1187*106

⑹当分类数目K=7时，调用［2*,（3,511］\«>4）］：=1«1^115（（1212,7）实现长均

值聚类：

SUMD=

1.0e+006*

3.2850

2.0138

2.7520

3.1015

5.3616

3.7949

3.3317

J=3.1187*106

如下图所示，随着初始分类数目K的增大，准则函

数下降很快，经过拐点A后，下降速度减慢。拐点就是

最佳初始分类，即阵4是最佳初始分类。

K=4时，K均值聚类程序清单：

%kmns.m:K均值聚类程序

clearall;

clc;

data=[1739.941675.152395.96%模式样本空间，每行所对应的模式为3维

373.33087.052429.47

1756.7716521514.98

864.451647.312665.9

222.853059.542002.33

877.882031.663071.18

1803.581583.122163.05

2352.122557.041411.53

401.33259.942150.98

363.343477.952462.86

1571.171731.041735.33

104.83389.832421.83

499.853305.752196.22

2297.283340.14535.62

2092.623177.21584.32

1418.791775.892772.9

1845.591918.812226.49

2205.363243.741202.69

2949.163244.44662.42

1692.621867.52108.97

1680.671575.781725.1

2802.883017.111984.98

172.783084.492328.65

2063.543199.761257.21

1449.581641.583405.12

1651.521713.281570.38

341.593076.622438.63

291.023095.682088.95

237.633077.782251.96

1702.81639.792068.74

1877.931860.961975.3

867.812334.682535.1

1831.491713.111604.68

460.693274.772172.99

2374.983346.98975.31

2271.893482.97946.7

1783.641597.992261.31

198.833250.452445.08

1494.632072.592550.51

1597.031921.522126.76

1598.931921.081623.33

1243.131814.073441.07

2336.312640.261599.63

3543300.122373.61

2144.472501.62591.51

426.313105.292057.8

1507.131556.891954.51

343.073271.722036.94

2201.943196.22935.53

2232.433077.871298.87

1580.11752.072463.04

1962.41594.971835.95

1495.181957.443498.02

1125.171594.392937.73

24.223447.312145.01

1269.071910.722701.97

1802.071725.811966.35

1817.361927.42328.79

1860.451782.881875.13];

[IDX,C,SUMD,D]=kmeans(data,4);

D=D*

minD=min(D);

indexl=find(D(l,:)==min(D))

index2=find(D(2,:)==min(D))

index3=find(D(3,:)==min(D))

index4=find(D(4,:)==min(D))

plot3(data(:,l),data(:,2),data(:,3),'*');

grid;

line(data(mdexl,l)»data(indexl,2),data(indexl,3)/linestyle,,,none*,,marker*,**,,,coloryg,);

,,,,,,,,,,,

Iine(data(mdex2,l)?data(index2,2),data(mdex2,3),linestyle,none,marker,*,color,*r);

Iine(data(index3,l),data(index3,2),data(index3,3),'liiiestyle\'iione\'marker\'+\'color?b');

Iine(data(mdex4,l),data(index4,2),data(index4,3)/linestyle,,,none,,,marker*,,+*,,color,,*y,);

titleCK均值聚类分析图》

xlabelC第1特征坐标1);

ylabelC第2薄征坐标，)；

zlabelC第3特征坐标，)；

运行结果：

D=D为每个样本与聚

1.0e+007*类中心的最小距离

Columns1through8

0.44870.00560.51270.29720.00940.24260.49540.5354

0.40640.56720.25600.67330.53100.71940.36990.0385

0.06370.24420.24320.02580.32850.01470.10710.4156

0.01800.38810.02200.12380.40350.20180.00630.1377

Columns9through16

0.00210.01140.41040.00960.00490.69390.59870.3616

0.49190.59610.28310.68720.46660.03610.03090.5413

0.32160.35230.16460.37960.31240.91860.81000.0088

0.41280.51490.00840.55870.40350.49680.41450.0735

!

Columns17through24

0.40870.47240.95340.37930.48920.63720.00420.4093

0.29070.00590.05780.29440.31060.10510.62350.0120

0.09400.59361.01590.09530.18320.47800.29290.5367

0.01090.30960.54810.00370.00910.27870.43790.2770

Columns25through32

0.51530.45650.00590.00420.00250.45040.44170.1191

0.82710.25730.58220.51950.57720.34540.24990.4829

0.03130.21470.24610.30830.28840.10900.14110.0505

0.21310.01720.39490.39420.41140.00190.00370.1420

Columns33through40

0.50380.00340.59420.56510.48380.00490.28380.3388

0.23960.47460.00840.01840.39000.64580.38900.2985

0.22440.31290.74450.77470.08920.31700.02850.0842

0.01480.40270.40100.44040.01030.48690.05000.0076

Columns41through48

Illi!it1111it11ITITIT11illiitITIT11IT11ill11111iiHiliiit11ITITHiliiill111itin

0.37720.42900.49050.00240.66700.00670.43170.0050

0.21790.83810.04670.56480.06030.45990.37700.4919

0.19340.02390.36930.30970.68610.29310.11980.3543

0.01770.23920.13240.45080.26730.35910.00830.4296

Columns49through56

0.53430.46570.38440.55820.45840.38040.01380.2863

0.00510.00600.42510.29170.78260.71280.66080.5140

0.68110.52360.03970.19040.03790.00880.45310.0070

0.34360.25100.02610.00920.24220.13140.58790.0773

Columns57through59

0.45750.39840.4646

0.29050.31610.2541

0.13560.07660.1604

0.00050.01680.0029

indexl=

Columns1through14

2591012132327282934384446

Columns15through16

4855

index!=

8141518192224353643454950

index3=

461625323942535456

index4=

Columns1thr