第5章
CHAPTER 5


聚 类 分 析







俗话说“物以类聚，人以群分”，这句话实际上就反映了聚类分析的基本思想。一般来说，数据集根据其客观属性可分为若干个自然类，每个自然类中的数据的一些属性都具有较强的相似性。聚类分析是基于这种思想而建立的一种数据描述方法。在第2章中为了获取判别模型的参数，需要由带有类别标签的数据组成训练样本集，但在实际应用中，常常会遇到因条件限制无法得到训练样本集，只是要求对已获取的大量未知类别数据，根据这些数据中的特性进行分类。在模式识别系统中，我们称这种算法为聚类算法。聚类算法把彼此特征相似的数据归入同一类，而把特征不相似的数据分到不同的类中，而且在分类中不需要用训练样本进行学习，所以也称为无监督分类。





第12集
微课视频



5.1模式相似性测度

在贝叶斯判决中，为了求得后验概率，需要已知先验概率和类条件概率。由于条件概率通常也未知，就需要用训练样本去对概率密度进行估计。在实际应用中，这一过程往往非常困难。聚类分析避免了估计类概率密度的困难，每个聚类中心都是局部密度极大值位置，越靠近聚合中心，密度越高； 越远离聚合中心，密度越小。聚类算法把特征相似性的样本聚集为一个类别，在特征空间里占据着一个局部区域。每个局部区域都形成一个聚类中心，聚类中心代表相应类别。如图51所示为具有相同的平均值和协方差矩阵的数据集，无论采用参数估计，还是非参数估计，都无法取得合理的结果，而采用聚类分析，从图中可以直观看出图51(a)具有一个类别，图51(b)和图51(c)各有两个类别。



图51具有相同的平均值和协方差矩阵的数据集


特征选择是聚类分析的关键因素，选取不同的特征，聚类的结果可能不同。如图52(a)所示为混合训练样本集； 根据样本的面积大小可分成三类的情况，如图52(b)所示； 根据外形特征分成三类的情况，如图52(c)所示； 根据线型分成两类的情况，如图52(d)所示。可以想象，属于不同类别的样本，它们之间必然存在某些特征显著不同。如果在聚类分析中，未把不同类的样本区分开来，可能是因为特征选择不当，没有选取标志类别显著差别的特征，这时应当重新选择特征。特征选择不当不仅可能会使聚类性能下降，甚至会使聚类完全无效。特征较少可能会使特征向量包含的分类信息太少，特征太多又会使特征之间产生信息冗余，都会直接影响聚类的结果。因此，特征选择也成了聚类分析中最困难的环节之一。关于特征选择的方法，我们将在第6章详细介绍。



图52聚类分析的结果与特征的选取的关系示例








实际应用中，对已知样本集X(N)={X1,X2,…,XN}，是按某种相似性把X分类，衡量样本相似性的方法对聚类结果同样也有很大的影响。为了能区分样本的类别，首先需要定义模式相似性的测度。

5.1.1距离测度

若一个样本模式被表示成特征向量，则对应于特征空间的一个点。当样本特征选择恰当，也即同类样本特征相似，不同类样本的特征显著不同时，同类样本就会聚集在一个区域，不同类样本相对远离。显然，样本点在特征空间的距离直接反映了相应样本所属类别，可以作为样本相似性度量。距离越近，相似性越大，属于同一类的可能性就越大； 距离越远，相似性越小，属于同一类的可能性就越小。聚类分析中，最常用的就是距离相似性测度。实际应用中，有各种各样距离的定义，下面我们给出距离定义应满足的条件。


设已知3个样本，它们分别为Xi=(xi1,xi2,…,xid)T、Xj=(xj1,xj2,…,xjd)T和Xk=(xk1,xk2,…,xkd)T。其中，d为特征空间的维数，向量Xi和Xj的距离以及Xi和Xk的距离分别记为D(Xi,Xj)和D(Xi,Xk)，对任意两向量的距离定义应满足下面的公理： 

(1) D(Xi,Xj)≥0，当且仅当Xi=Xj时，等号成立。

(2) D(Xi,Xj)=D(Xj,Xi)。

(3) D(Xi,Xj)≤D(Xj,Xk)+D(Xi,Xk)。

需要指出，模式识别中定义的某些距离测度不满足第3个条件，只是在广义上称为距离。下面给出距离测度的几种具体算式。

1. 欧氏距离

De(Xi,Xj)=‖Xi－Xj‖=∑dk=1|xik－xjk|2(51)

根据De(X1,X2)的定义，通过选择合适的门限ds，可以判决X1和X2是否为同一类别。当De(X1,X2)小于门限ds时，表示X1和X2属于同一类别，反之，则属于不同类别。这里门限ds的选取非常关键，若ds选择过大，则全部样本被归为同一类别； 若ds选取过小，则可能造成每个样本都单独构成一个类别。必须正确选择门限值以保证正确分类。实际应用中还需注意以下两点。

(1) 模式特征向量的构成。一种物理量对应一种量纲，而一种量纲一般有不同的单位制式，每种单位制式下又有不同的单位，简单地说，就是一种物理量对应着一个具体的单位。对于各特征向量，对应的维度上应当是相同的物理量，并且要注意物理量的单位。

通常，特征向量中的每一维所表示的物理意义不尽相同，如x1表示周长，x2表示面积等。如果某些维度上的物理量采用的单位发生变化，就可能会导致相同样本集出现不同的聚类结果。如图53所示，a、b、c和d表示4个二维向量，向量的两个分量x1、x2均表示长度，当x1、x2的单位发生不同的变化时，会出现不同的聚类结果。如图53(b)所示a,b为一类，c,d为另一类，如图53(c)所示a,c为一类，b,d为另一类。由此可见，坐标轴的简单缩放就能引起样本点的重新聚类。

(2) 在实际应用中，可以采用特征数据标准化方法对原始特征进行预处理，使其与变量的单位无关。此时所描述的点是一种相对的位置关系，只要样本点间的相对位置关系不变，就不会影响聚类结果。例如，对图53(b)和图53(c)中的数据标准化后，4个点的相对位置关系总是和图53(a)相同。

需要指出的是，并不是所有的标准化都是合理的。如果数据散布恰恰是由于类别差异引起的，标准化反而会引起错误的聚类结果。因此，在聚类之前是否应进行标准化处理，建立在对数据各维度物理量充分研判的基础上。



图53特征量纲对聚类结果的影响


2. 绝对值距离(街坊距离或曼哈顿距离) 

D(Xi,Xj)=∑nk=1xik－xjk,k=1,2,…,d(52)

3. 切比雪夫(Chebyshev)距离

D(Xi,Xj)=maxxik－xjk,k=1,2,…,d(53)

4. 闵可夫斯基(Minkowski)距离

Dλ(Xi,Xj)=∑dk=1|xik－xjk|λ1λ，λ>0k=1,2,…,d(54)

它是若干距离函数的通式： 当λ=2时，等于欧氏距离； 当λ=1时，称为“街坊”(City Block)距离。

5. 马哈拉诺比斯(Mahalanobis)距离

设n维向量Xi是向量集X1,X2,…,XN中的一个向量，其马哈拉诺比斯距离的平方定义为

D2(Xi,μ)=(Xi－μ)TΣ－1(Xi－μ)(55)

式中，Σ=1N－1∑Ni=1(Xi－μ)(Xi－μ)T，μ=1N∑Ni=1Xi。


容易证明，马哈拉诺比斯距离对一切非奇异线性变换都是不变的，即具有坐标系比例、旋转、平移不变性，并且从统计意义上尽量去掉了分量间的相关性。这说明它不受特征量纲选择的影响。另外，由于Σ的含义是这个向量集的协方差阵的统计量，所以马哈拉诺比斯距离对特征的相关性也做了考虑。当Σ为单位矩阵时，马哈拉诺比斯距离和欧氏距离是等价的。

【例5.1】已知二维正态母体G的分布为 

N00,10.90.91

求点A=［1,1］T和B=［1,－1］T至均值点μ=［0,0］T的马哈拉诺比斯距离和欧氏距离。

【解】由题设，可得

Σ=10.90.91，Σ－1=10.191－0.9－0.91

从而马哈拉诺比斯距离


D2(A,μ)=［1,1］Σ-111=0.20.19
D2(B,μ)=［1,－1］Σ－11－1=3.80.19


点B是点A的19倍，若用欧氏距离，算得的距离值相同，均为2。由分布函数知，A和B两点的概率密度分别为p(1,1)=0.2157和p(1,－1)=0.00001658。

6. 堪培拉（Canberra）距离(兰氏距离)

D(Xi,Xj)=∑nk=1xik－xjk|xik+xjk|,(xik,xjk≥0,xik+xjk≠0)(56)

该距离能克服量纲引起的问题，但不能克服分量间的相关性。


5.1.2相似测度

与距离测度不同，相似测度考虑两向量的方向是否相近，向量长度并不重要。如果两样本点在特征空间的方向越接近，则两样点划归为同一类别的可能性越大。下面给出相似测度的几种定义。

1. 角度相似系数(夹角余弦)

样本Xi与Xj之间的角度相似性度量定义为它们之间夹角的余弦，也是单位向量之间的点积(内积)即

S(Xi,Xj)=cosθ=XTiXj‖Xi‖·‖Xj‖(57)

|S(Xi,Xj)|≤1，S(Xi,Xj)越大，Xi与Xj越相似； 当Xi=Xj时，S(Xi,Xj)达到最大值。因向量长度已规格化，S(Xi,Xj)对于坐标系的旋转及放大、缩小是不变的，但对位移和一般性的线性变换不具有不变性。当Xi与Xj的各特征为(0,1)二元取值时，S(Xi,Xj)的意义如下： ①若模式样本的第i维特征取值为1，则该样本占有第i维特征； ②若模式样本的第i维特征取值为0，则该样本无此维特征。此时，XTiXj表示Xi与Xj两个样本中共有的特征数目。S(Xi,Xj)反映Xi与Xj共有的特征数目的相似性度量。S(Xi,Xj)越大，共有特征数目越多，相似性越高。

2. 相关系数

相关系数定义为数据中心化后的向量夹角余弦，即

R(X,Y)=(X－μX)T(Y－μY)［(X－μX)T(X－μX)(Y－μY)T(Y－μY)］1/2(58)

式中，X=(x1,x2,…,xd)，Y=(y1,y2,…,yd)分别为两个数据集的样本，μX和μY分别为这两个数据集的平均向量。

相关系数对于坐标系的平移、旋转和尺度缩放具有不变性。

3. 指数相似系数

已知样本Xi=(xi1,xi2,…,xid)、Xj=(xj1,xj2,…,xjd)，其指数相似系数定义为

E(Xi,Xj)=1d∑dk=1exp－3(xik－xjk)24σk(59)

式中，σ2k为相应分量的协方差，d为向量维数。

4. 其他相似测度

当样本Xi=(xi1,xi2,…,xid)、Xj=(xj1,xj2,…,xjd)各特征值非负时，还可定义下列相似系数： 


S1(Xi,Xj)=∑k=1min(xik,xjk)∑k=1max(xik,xjk)(510)
S2(Xi,Xj)=∑k=1min(xik,xjk)12∑k=1(xik+xjk)(511)
S3(Xi,Xj)=∑k=1min(xik,xjk)∑k=1xikxjk(512)


上述相似性系数，均可作为样本相似测度。当两个样本Xi与Xj越相似时，S(Xi,Xj)的值越大； 当Xi与Xj相等时，其值为1。


5.1.3匹配测度

当Xi与Xj的各特征为(0,1)二元取值时，我们称之为二值特征。对于给定的二值特征向量Xi=(xi1,xi2,…,xid)和Xj=(xj1,xj2,…,xjd)，根据它们两个相应分量xik与xjk的取值，可定义如下四种匹配关系： 若xik=1和xjk=1，则称xik与xjk是(11)匹配； 若xik=1和xjk=0，则称xik与xjk是(10)匹配； 若xik=0和xjk=1，则称xik与xjk是(01)匹配； 若xik=0和xjk=0，则称xik与xjk是(00)匹配。令

a=∑i=1xiyib=∑i=1yi(1－xi)c=∑i=1xi(1－yi)e=∑i=1(1－xi)(1－yi)


则a、b、c、e分别表示Xi与Xj的(11)、(01)、(10)和(00)的匹配特征数目。对于二值d维特征向量可定义如下相似性测度。

(1) 谷本（Tanimoto）测度：

St(Xi,Xj)=aa+b+c=XTiXjXTiXi+XTjXj－XTiXj(513)

可以看出，St(X,Y)等于X和Y共同具有的特征数目与X和Y分别具有的特征种类总数之比。这里只考虑(11)匹配而不考虑(00)匹配。

(2) Rao测度：

Sr(Xi,Xj)=aa+b+c+e=XTiXjd(514)

上式等于(11)匹配特征数目和所选用的特征数目之比。

(3) 简单匹配系数：

M(Xi,Xj)=a+ed(515)

这时，匹配系数分子为(11)匹配特征数目与(00)匹配特征数目之和，分母为所考虑的特征数目。

(4) Dice系数：

MD(Xi,Xj)=a2a+b+c=XTiXjXTiXi+XTjXj(516)

(5) Kulzinsky系数：

MK(Xi,Xj)=ab+c=XTiXjXTiXi+XTjXj－2XTiXj(517)

上式分子为(11)匹配特征数目，分母为(10)和(01)匹配特征数目之和，即不匹配特征数目之和。

【例5.2】已知两样本X1=010110T,X2=001110T，求其Tanimoto测度。

【解】XT1X2=2,XT1X1=3,XT2X2=3

StX1,X2=23+3－2=12=0.5

上面从不同角度给出了许多样本相似性测度的定义，各种相似性测度有其特点和适用的条件，在实际使用时应根据具体问题进行选择。建立了模式相似性测度之后，两个样本的相似程度就可量化了，据此便可以进行聚类分析。

5.2类间距离测度方法

在有些聚类算法中要用到类间距离，下面给出一些类间距离定义方式。

5.2.1最短距离法

如H、K是两个聚类，则两类间的最短距离定义为

DHK=minDXH,XK，XH∈H,XK∈K

式中，DXH,XK表示H类中的某个样本XH和K类中的某个样本XK之间的欧氏距离。DHK表示H类中所有样本与K类中所有样本之间的最小距离，如图54(a)所示。
如果K类由I和J两类合并而成，如图54(b)所示，则得到递推公式： 

DHK=minDHI,DHJ(518)



图54最短距离法示意图


5.2.2最长距离法

与最短距离法类似，两个聚类H和K之间的最长距离定义为 

DHK=maxDXH,XK(519)

其中，XH∈H,XK∈K。

若K类由I和J两类合并而成，则得到递推公式：

DHK=maxDHI,DHJ(520)

5.2.3中间距离法

 中间距离法介于最长与最短的距离之间。若K类由I和J两类合并而成，则H和K类之间的距离为

DHK=12D2HI+12D2HJ－14D2IJ(521)

5.2.4重心法

以上定义的类间距离中并未考虑每一类所包含的样本数目，重心法在这一方面有所改进。从物理的观点看，一个类的空间位置若要用一个点表示，那么用它的重心代表较合理。将每类中包含的样本数考虑进去。若I类中有NI个样本，J类中有NJ个样本，则类与类之间的距离递推式为 

DHK=NINI+NJD2HI+NJNI+NJD2HJ－NINJ(NI+NJ)2D2IJ(522)

5.2.5平均距离法(类平均距离法)

设H、K是两个聚类，则H类和K类间的距离定义为

DHK=1NHNK∑i∈Hj∈KD2ij(523)

式中，D2ij是H类任一样本XH和K类任一样本XK之间的欧氏距离的平方，NH和NK分别表示H和K类中的样本数目。

如果K类由I类和J类合并产生，则可以得到H和K类之间距离的递推式为

DHK=NINI+NJD2HI+NJNI+NJD2HJ(524)

定义类间距离的方法不同，会使分类结果不太一致。实际问题中常用几种不同的方法，比较其分类结果，从而选择一个比较切合实际的分类。

【例5.3】已知6个五维模式样本X1、X2、X3、X4、X5和X6，试按最短距离法进行聚类分类。


X1=0,3,1,2,0TX2=1,3,0,1,0TX3=3,3,0,0,1T
X4=1,1,0,2,0TX5=3,2,1,2,1TX6=4,1,1,1,0T


【解】对每一样本可表示为


X1=x11,x12,x13,x14,x15T，X2=x21,x22,x23,x24,x25T,…,
X6=x61,x62,x63,x64,x65T


(1) 将每一样本看成单独一类，得


G1(0)=X1G2(0)=X2G3(0)=X3
G4(0)=X4G5(0)=X5G6(0)=X6


计算各类间欧氏距离： 


D12(0)=‖X1－X2‖=x11－x212+x12－x222+x13－x232
+x14－x242+x15－x25212
=1+0+1+1+012=3


同理可求得 

D13(0),D14(0),D15(0),D16(0);D21(0),D22(0),D23(0),D24(0),D25(0),D26(0),…

距离矩阵D(0)可由表格表示，见表51。


表51距离矩阵D(0)的表格形式




D(0)
G1(0)
G2(0)
G3(0)
G4(0)
G5(0)
G6(0)



G1(0)
0





G2(0)
3*
0




G3(0)
15
6
0



G4(0)
6
5
13
0


G5(0)
11
8
6
7
0

G6(0)
21
14
8
11
4
0


(2) 将最小距离3对应的类G1(0)和G2(0)合并为一类，得到新的分类


G12(1)=G1(0),G2(0)G3(1)=G3(0)
G4(1)=G4(0)G5(1)=G5(0)G6(1)=G6(0)


按最小距离准则计算类间距离，由D(0)矩阵递推得到聚类后的距离矩阵D(1)也可由表格表示，见表52。


表52第1次合并后的距离矩阵D（1）的表格形式




D(1)
G12(1)
G3(1)
G4(1)
G5(1)
G6(1)



G12(1) 
0




G3(1)
6
0



G4(1)
5
13
0


G5(1)
8
6
7
0

G6(1)
14
8
11
4*
0


(3) 将D(1)中最小值4对应的类合并为一类，得D(2),其可由表格表示，见表53。


表53第2次合并后的距离矩阵D(2)的表格形式




D(2)
G12(2)
G3(2)
G4(2)
G56(2)



G12(2)0

G3(2)
60

G4(2)
5*
13
0

G56(2)
8
6
7
0

(4) 将D(2)中最小值5对应的类合并为一类，得D(3)，其可由表格表示，见表54。


表54第3次合并后的距离矩阵D（3）的表格形式




D(3)
G124(3)
G3(3)
G56(2)



G124(3)
0

G3(3)
6
0

G56(2)
7
6
0



若给定的阈值为T=5，D(3)中的最小元素6>T，聚类结束，结果为

G1=X1,X2,X4G2=X2G3=X5,X6

若无阈值，继续聚类下去，最终全部样本归为一类，这时给出聚类过程的树状表示，如图55所示。类间距离阈值增大，分类变粗。



图55分级聚类法的树状表示 


5.3聚类准则函数

样本相似性度量是聚类分析的基础，针对具体问题，选择适当的相似性度量是保证聚类效果的基础。但有了相似性度量还不够，还必须有适当的聚类准则函数，才能把真正属于同一类的样本聚合成一个类别的子集，把不同类的样本分离开来。因此，聚类准则函数对聚类质量也有重要影响。相似性度量用于解决集合与集合的相似性问题； 相似性准则用于来评价分类效果的好坏。如果聚类准则函数选得好，聚类质量就会高。同时，聚类准则函数还可以用来评价一种聚类结果的质量，如果聚类质量不满足要求，就要重复执行聚类过程，以优化结果。在重复优化中，可以改变相似性度量的方法，也可以选用新的聚类准则。

5.3.1误差平方和准则

给定样本集X1,X2,…,XN依据某种相似性测度划分为c类ω1,ω2,…,ωc，定义误差平方和准则函数为

J=∑ci=1∑Xi∈ωi‖Xi－Mi‖2

式中，Mi=1Ni∑Xi∈ωiXi为属于ωi集的样本的均值向量，Ni为ωi中样本数目。

J代表了分属于c个聚类类别的全部模式样本与其相应类别模式均值之间的误差平方和。在此准则函数下，聚类的目标转化为使J取最小值，即聚类的结果应使全部样本与其相应模式均值之间的误差平方和最小。该准则适用于各类样本密集且数目相差不多，而不同类间的样本又明显分开的情况； 当类别样本数相差较大，且类间距离又不足够大时，并不适宜采用该准则函数。因为可能会由于样本数较多造成类中的边缘处样本距离另一类的类心更近，从而产生错误的划分。

如图56(a)所示，类内误差平方和很小，类间距离很远，可得到较好的结果。图56(b)中类长轴两端距离中心很远，J值较大，结果不易令人满意。在该准则下，有时可能把样本数目多的一类分拆为二，造成错误聚类。如图57(a)和(b)的正确分类与错误分类情况所示，ω1中的某些样本被错分到ω2中，因为这样分类，J值会更小。



图56样本分布




图57正确分类与错误分类示例


5.3.2加权平均平方距离和准则

误差平方和准则只是考虑了各样本到判定类心的距离，并没有考虑样本周围空间其他样本对聚类的影响，当综合考虑这些因素时，误差平方和准则可改进为加权平均平方距离和准则。加权平均平方距离和准则函数定义为

J=∑ci=1NiN2i(525)

式中,

2i=2NiNi－1∑xik∈ωixij∈ωi‖xik－xij‖2(526)

∑xik∈ωixij∈ωi‖xik－xij‖2表示ωi类中任意两个不同样本距离平方和，由于ωi中包含样本的个数为Ni，因此共有NiNi－12个组合，由此可见，2i的含义是类内任意两样本的平均平方距离。N为样本总数，NiN为ωi类的先验概率，因此J被称为加权平均平方距离和准则。

5.3.3类间距离和准则

给定待分样本X1,X2,…,XN，将它们分成c类ω1,ω2,…,ωc，定义ωi类的样本均值向量Mi和总体样本均值向量M为


Mi=1Ni∑Xi∈ωiXi(527)
M=1N∑Ni=1Mi(528)


则类间距离和准则定义为

J=∑ci=1Mi－MTMi－M(529)

聚类的目标是最大化式(529)，J越大表示各类之间的可分离性越好，聚类效果越好。

对于二分类问题，类间距离常用式(530)表示类间距离。

J=M1－M2TM1－M2(530)

5.3.4离散度矩阵

给定待分样本X1,X2,…,XN，将它们分成c类ω1,ω2,…,ωc。定义ωi类的离散度矩阵为

Si=∑Xi∈ωiXi－MiXi－MiT(531)

定义类内离散度矩阵为

Sw=∑ci=1Si(532)

定义类间离散度矩阵为

Sb=∑ci=1NiMi－MMi－MT(533)

定义总体离散度矩阵为

St=∑Ni=1Xi－MXi－MT(534)

可以证明St=Sw+Sb，聚类的目标是极大化Sb和极小化Sw，即使不同类的样本尽可能分开，而同一类的样本尽可能聚集，由此可定义如下基于离散度矩阵的4个聚类准则。


J1=trS－1wSb(535)
J2=S－1wSb(536)
J3=trS－1wSt(537)
J4=S－1wSt(538)


式中，tr（·）为求矩阵的迹，即方阵主对角线上各元素之和，也就是矩阵的特征值的总和。

聚类的目标是极大化Ji(i=1,2,3,4)，Ji越大表示各类之间的可分离性越好，聚类质量越好。当待分样本特征向量的维数为d时，S－1wSb则为d×d的对称矩阵，其对应的特征值为λi(i=1,2,…,d)，易知


J1=∑di=1λi(539)
J2=∏di=1λi(540)
J3=∑di=1(1+λi)(541)
J4=∏di=1(1+λi)(542)


因此，在实际运算中，只要求出S－1wSb的特征值，即可求得Ji(i=1,2,3,4)。

5.4基于距离阈值的聚类算法

当确定了相似性测度和准则函数后，聚类的过程是依靠聚类算法来实现的。因此，聚类算法是一个试图识别数据集合聚类的特殊性质的学习过程。本节介绍两种简单的聚类分析方法，它通过对某些关键性的元素进行试探性的选取，使某种聚类准则达到最优，又称为基于试探的聚类算法。





第13集
微课视频




第14集
微课视频



5.4.1最近邻规则的聚类算法

最近邻规则聚类分析问题描述为： 假设已有混合样本集X(N)=X1,X2,…,XN，给定类内距离门限阈值T，将X(N)=X1,X2,…,XN划分为ω1,ω2,…,ωc个类别。

最近邻规则聚类算法的基本思想是： 计算样本的特征向量到聚类中心的距离，将该距离与门限阈值T比较，决定该样本属于哪一类别或作为新一类别的中心。

按照最近邻原则进行聚类，算法步骤如下。

(1) 选取距离阈值T，并且任取一个样本作为第一个聚合中心Z1，如Z1=X1。

(2) 计算样本X2到Z1的距离D21： 

若D21≤T，则X2∈Z1，否则令X2为第二个聚合中心，即Z2=X2。

设Z2=X2，计算X3到Z1和Z2的距离D31和D32，若D31>T和D32>T，则建立第三个聚合中心Z3。否则把X3归于最近邻的聚合中心。依此类推，直到把所有的N个样本都进行分类。

(3) 按照某种聚类准则考查聚类结果，若不满意，则重新选取距离阈值T和第一个聚合中心Z1，返回(2)，直到满意，算法结束。

该算法的优点是简单，如果有样本分布的先验知识用于指导阈值和起始点的选取，则可较快得到合理结果。其缺点是聚类过程中类别的中心一经选定，在聚类过程中将不再改变。同样，样本一经判定类别归属后也不再改变。因此，在样本分布一定时，该算法的结果在很大程度上取决于第一个聚合中心的选取和距离阈值的大小的确定。对于高维的样本集来说，只有经过多次试探，并对聚类结果进行检验，才能选择最优的聚类结果。

5.4.2最大最小距离聚类算法

最大最小距离聚类算法的问题描述为： 假设已有混合样本集X(N)=X1,X2,…,XN，给比例系数θ，将X(N)=X1,X2,…,XN划分为ω1,ω2,…,ωc个类别。该算法的基本思想是： 样本的特征向量以最大距离原则选取新的聚类中心，以最小距离原则进行类别归属。如果使用欧氏距离，除首先辨识最远的聚类中心外，其余步骤与最近邻规则算法相似。用一个例子说明该算法。



【例5.4】已知二类共10个样本，分布如图58所示。




图58例5.4样本分布


其中，X1=0,0T，X2=3,8T，X3=2,2T，X4=1,1T，X5=5,3T，X6=4,8T，X7=6,3T，X8=5,4T，X9=6,4T，X10=7,5T，采用最大最小距离聚类算法求出分类结果。

【解】采用最大最小距离聚类算法求解的步骤如下。 

(1) 给定θ，0<θ<1，并且任取一个样本作为第一个聚合中心，Z1=X1。

(2) 寻找新的集合中心。

计算其他所有样本到Z1的距离Di1，若Dk1=maxi{Di1}，则取Xk为第二个聚合中心Z2，如本例中Z2=X6。计算所有样本到Z1和Z2的距离Di1和Di2，若Dl=max{min(Di1,Di2)}，i=1,2,…,n，并且Dl>θ·D12，D12为Z1和Z2间距离，则取Xl为第三个集合中心Z3，本例中Z3=X7。如果Z3存在，则计算Dj=max{min(Di1,Di2,Di3)}，i=1,2,…,n，若Dj>θ·D12，则建立第四个聚合中心。以此类推，直到最大最小距离不大于θ·D12时，结束寻找聚合中心的计算。

观察表55，当取θ=0.5时，29在min(Di1,Di2)中为最大的，而且Dl=29>θ·80。所以，Z3=X7。


表55判断第三个聚类中心样本距离计算表





距离
样本


X1
X2
X3
X4
X5
X6
X7
X8
X9
X10


到Z1的距离
0
73
8
2
34
80
45
41
52
74
到Z2的距离
80
1
40
58
26
0
29
17
20
18
min(Di1,Di2)
0
1
8
2
26
0
29
17
20
18



观察表56，计算Dj=max{min(Di1,Di2,Di3)},i=1,2,…,n，得Dj=8<θ·80，结束寻找聚合中心。则图58中只有三个集合中心，Z1=X1，Z2=X6，Z3=X7。



表56判断第四个聚类中心样本距离计算表





距离
样本


X1
X2
X3
X4
X5
X6
X7
X8
X9
X10


到Z1的距离
0
73
8
2
34
80
45
41
52
74
到Z2的距离
80
1
40
58
26
0
29
17
20
18
到Z3的距离
45
34
17
29
1
29
0
2
1
5
min(Di1,Di2,Di3)
0
1
8
2
1
0
0
2
1
5



(3) 按最近邻原则把所有样本归属于距离最近的聚合中心，有

{x1,x3,x4}∈Z1，{x2,x6}∈Z2，{x5,x7,x8,x9,x10}∈Z3

(4) 按照某聚类准则考查聚类结果，若不满意，则重选θ和第一个聚合中心Z1，返回(2)，直到满意，算法结束。

从上述步骤可以看出，该算法的聚类结果与参数θ和起始点Z1的选取密切相关。若无先验样本分布知识，则只有用试探法通过多次试探优化，选择最合理的一种参数选择方案和聚类结果。若有先验知识用于指导θ和Z1选取，则算法可以很快收敛。





第15集
微课视频



5.5动态聚类算法

最近邻规则和最大、最小距离聚类算法的共同缺点是： 一个样本的归属一旦判定后，在后继的迭代过程中就不会改变，因此，这类算法在实际应用中有较大的局限性。与上述算法相对，动态聚类法是聚类分析中较普遍采用的方法。该算法首先选择某种样本相似性度量和适当的聚类准则函数，在对样本进行初始划分的基础上，使用迭代算法逐步优化聚类结果，当准则函数达到极值时，取得在该准则函数下的最优聚类结果。

该算法有以下两个关键问题。

(1) 首先选择有代表性的点作为起始聚合中心。若类别数目已知，则选择代表点的数目等于类别数目； 若类别数未知，那么聚类过程如何形成的类别数目是一个值得研究的问题。

(2) 代表点选择好之后，如何形成初始划分是算法的另一个关键问题。


5.5.1C均值聚类算法

给定模式样本集X(N)=X1,X2,…,XN，假设已知样本的类别数为c。C均值聚类算法的基本思想是： 先选定c个初始聚类中心，按最短距离原则将各样本归属到c个类别中，然后重新计算各类别中心，调整各样本的类别归属，算法不断迭代，最终使各样本到其类别中心的距离平方和最小。

C均值聚类算法使用的聚类准则函数是误差平方和准则Jc，即

Jc=∑cj=1∑Njk=1‖Xk－mj‖2(543)

式中，Nj为第j类的样本数，mj为第j类ωj的均值。

为了使聚类结果优化，应该使准则Jc最小化。下面给出C均值算法的具体步骤。

(1) 已知混合样本X(N)=X1,X2,…,XN，令I表示迭代运算次数，任选c个样本作为初始聚合中心Zj(I),j=1,2,…,c。

(2) 计算每个样本与聚合中心的距离DXk,Zj(I)，k=1，2，…,n,j=1,2,…,c。若

DXk,Zj(I)=minj=1,2,…,cDXk,Zj(I),k=1,2,…,n(544)

则Xk∈ωj。

(3) 重新计算c个新的集合的聚类中心，即

Zj(I+1)=1Nj∑Njk=1X(j)k,j=1,2,…,c(545)

式中，Nj为第I+1次迭代时归属于ωj类的样本数，X(j)k为第I+1次迭代时归属于ωj类的样本，上标表示类别。

(4) 若Zj(I+1)≠Zj(I)，j=1,2,…,c，则I=I+1，返回(2)，否则算法结束。

C均值聚类算法特点是： ①每次迭代中都要重新计算聚类中心，并考查每个样本类别归属是否正确，若不正确，就要调整，在全部样本调整完之后，进入下一次迭代。如果在某一个迭代运算中，所有的样本都被正确分类，则样本不会调整，聚合中心也不会有变化，算法达到收敛。②算法需要首先确定类别数和初始聚类中心，显然，类别数c和初始聚合中心的选择对聚类结果有较大影响，所以结果不是全局最优。③算法简单便于实现，当样本分布为类内团状时，一般可以达到比较好的聚类效果。

从算法的步骤可以看出，算法在迭代中没有计算Jc值，也就是说Jc不是算法结束的明显依据。算法通过对样本分类的不断调整去逐步减少Jc的值，当没有样本调整时，此时Jc不再变化，聚类达到最优。事实上，可以通过样本移动对Jc的影响来修改上述算法。假定I+1次迭代时，Xk由样本子集X(i)移入另一个子集X(j)，那么这次移动只影响两个类型ωi和ωj的聚类中心Zi和Zj，以及两类的类内误差平方和Jci、Jcj。移动后，ωi和ωj的聚类中心


Zi(I+1)=1Ni－1NiZi(I)－Xk=Zi(I)+1Ni－1Zi(I)－Xk(546)
Zj(I+1)=1Nj+1NjZj(I)+Xk=Zj(I)－1Nj+1Zj(I)－Xk(547)


因此，有


Jci(I+1)=Jc1(I)－NiNi－1‖Xk－Zi(I)‖2(548)
Jcj(I+1)=Jcj(I)+NiNi+1‖Xk－Zj(I)‖2(549)


由于样本Xk从X(i)移入X(j)，显然Xk距Zj(I)比Zi(I)更近，因此有

NiNi+1‖Xk－Zj(I)‖2<NiNi－1‖Xk－Zi(I)‖2(550)

那么，Jc的值会减小为

Jc(I+1)=Jc(I)－NiNi－1‖Xk－Zi(I)‖2－NiNi+1‖Xk－Zj(I)‖2(551)

根据上述分析，可对C均值算法做如下改进：

(1) 已知混合样本X(N)=X1,X2,…,XN，令I表示迭代运算次数，任选c个样本作为初始聚合中心Zj(I),j=1,2,…,c； 

(2) 计算每个样本与聚合中心的距离DXk,Zj(I)，k=1，2，…,N，j=1,2,…,c。若

DXk,Zj(I)=minj=1,2,…,cDXk,Zj(I),k=1,2,…,N

则Xk∈ωi。

(3) 令I=I+1=2，计算新的类别中心

Zj(2)=1Nj∑Njk=1X(j)k,j=1,2,…,c(552)

计算本次迭代的误差平方和Jc，即

Jc=∑cj=1∑Njk=1‖X(j)k－Zj(2)‖2(553)

(4) 对每个类别中的每个样本，计算ρii(Jc减少的部分)和ρij(Jc增加的部分)。


ρii=NiNi－1‖X(i)k－Zi(I)‖2，i=1,2,…,c(554)
ρij=NjNj+1‖X(i)k－Zj(I)‖2，i=1,2,…,ci≠j(555)


令

ρil=mini≠jρij(556)

若ρil<ρii，则把样本X(i)k移到聚合中心ωl中，并修改聚合中心和Jc值，即有


Zi(I+1)=Zi(I)－1Ni－1Zi(I)－X(i)k(557)
Zl(I+1)=Zl(I)+1Nl+1Zl(I)－X(i)k(558)
Jc(I+1)=Jc(I)－ρii－ρil(559)


(5) 若Jc(I+1)<Jc(I)，则I=I+1，返回(4)。否则，算法结束。

【例5.5】现有混合样本集X(N)=X1,X2,…,X20，共有样本20个，样本分布如图59所示，类型数目c=2。试用C均值聚类算法进行聚类分析。

【解】(1) c=2，任选2个集合中心，不妨取Z1(1)=X1，Z2(1)=X2，即Z1(1)=0，0T，Z2(1)=1，0T。



图59例5.5 样本分布


(2) 选用欧氏距离作为相似性度量，计算各样本到Z1(1)=X1，Z2(1)=X2的距离，并把各样本归属于距离最小的聚类范围内，有


‖X1－Z1(1)‖<‖X1－Z2(1)‖，因此X1∈ω1
‖X2－Z2(1)‖<‖X2－Z1(1)‖，因此X2∈ω2
‖X3－Z1(1)‖<‖X3－Z2(1)‖，因此X3∈ω1


…


可得


ω1： X1,X3，N1=2
ω2： X2,X4,X5,…,X20，N2=18


(3) 计算新的聚类中心： 


Z1(2)=12X1+X3=0,0.5T
Z2(2)=118X2+X4+X5+…+X20=5.67,5.33T


(4) Zj(2)≠Zj(1)，j=1,2。令I=I+1=2，返回(2)。

计算各样本到Zj(2)，j=1,2的欧氏距离，有


‖Xk－Z1(2)‖<‖Xk－Z2(2)‖，k=1，2，…，8
‖Xk－Z2(2)‖<‖Xk－Z1(2)‖，k=9,10，…,20


得到新的聚类：


ω1： X1,X2，…,X8，N1=8
ω2： X9,X10,…,X20，N2=12


计算聚类中心：


Z1(3)=18X1+X2+…+X8=1.25,1.13T
Z2(2)=112X9+X10+…+X20=7.67,7.33T


因为Zj(3)≠Zj(2)，j=1,2。令I=I+1=3，返回(2)。判断： Zj(4)=Zj(3)，j=1,2，聚类结果无变化，聚类中心无变化，算法结束，聚类结果如图59所示。


(5) Jc与c的关系曲线。上述C均值算法，其类别数假定已知为c。对于类别数未知时，可以令c逐渐增加，如c=1，2，…，分别使用C均值算法，显然误差平方和Jc随c的增加而单调减少。最初，由于c较小，类别的分裂会使Jc迅速减小，但当c增加到一定数值时，相当于将本来就比较密集的类别再行分开，因此Jc的减小速度会减慢，直到c增加到总类别数目N时，Jc=0，Jc与c的关系曲线如图510所示。




图510Jc与c的关系曲线



在图510中，曲线的拐点A对应着接近最优的c值。但是并非所有的情况都容易找到Jc与c的关系曲线的拐点，此时c值将无法确定。下面介绍一种确定类型数目c的方法。

5.5.2ISODATA聚类算法

C均值聚类算法的一个缺点是必须事先指定聚类的个数，在实际应用中有时并不可行，而是希望这个类别的个数也可以自动改变，于是形成了迭代自组织数据分析算法(Iterative SelfOrganizing Data Analysis Techniques Algorithm，ISODATA)。ISODATA是在C均值聚类算法基础上，通过增加对聚类结果的“合并”和“分裂”两个操作，并设置算法运行控制参数的一种聚类算法。ISODATA可以通过类的自动合并(两类合一)与分裂(一类分为二)，得到较合理的类型数目，因此是目前应用比较广的一种聚类算法。

算法的基本思想： 通过设定初始参数，并使用合并与分裂的机制，当某两类聚类中心距离小于某一阈值时，将它们合并为一类； 当某类标准差大于某一阈值或其样本数目超过某一阈值时，将其分为两类。在某类样本数目少于某阈值时，需将其取消。如此，根据初始聚类中心和设定的类别数目等参数迭代，最终得到一个比较理想的分类结果。

具体算法步骤如下。

(1) 给定控制参数。

K： 预期的聚类中心数目。

θn： 每一聚类中最少的样本数目，如果少于此数就不能作为一个独立的聚类。

θs： 一个聚类域中样本距离分布的标准差(阈值)。

θc： 两个聚类中心之间的最小距离，如果小于此数，两个聚类合并。

L： 每次迭代允许合并的最大聚类对数目。

I： 允许的最多迭代次数。

给定N个混合样本X(N)=X1,X2,…,XN，令迭代次数J=1，任选c个样本作为初始聚合中心Zj(1),j=1,2,…,c。

(2) 计算每个样本与聚类中心距离DXk,Zj(1)，k=1，2，…,N，j=1,2,…,c。若

DXk,Zj(1)=minj=1,2,…,cDXk,Zj(1),k=1,2,…,N(560)

则Xk∈ωj。把所有样本都归属到c个聚类中去，Nj表示类别ωj中的样本数目。

(3) 若Nj<θn，j=1,2,…，c,则舍去子集ωj，c=c－1，返回(2)。

(4) 计算修改聚合中心： 

Zj(J)=1Nj∑njk=1X(j)k,j=1,2,…,c(561)

(5) 计算类内距离平均值： 

j=1Nj∑Njk=1DX(j)k,Zj(J),j=1,2,…,c(562)

(6) 计算类内总平均距离(全部样本对其相应聚类中心的总平均距离)： 

=1N∑Njj=1Njj(563)

(7) 判别分裂、合并及迭代运算等步骤。

① 如果迭代运算次数已达I次，即最后一次迭代，置θc=0，跳到(11)。

② 如果c≤K2，即聚类中心的数目等于或不到规定值的一半，则进入(8)，将已有的聚类分裂。

③ 如果迭代运算的次数是偶数，或c>2K，则不进行分裂，跳到(11)，若不符合上述两个条件，则进入(8)进行分裂处理。

(8) 计算每个聚类的标准偏差向量σj=σj1,σj2,…,σjd。

每个分量为

σji=1Nj∑xji∈ωjxji－zji(J)2,i=1,2,…,d,j=1,2,…,c(564)

式中，xji表示Xj的第i个分量，zji表示Zj的第i个分量，d为样本特征向量维数。

(9) 求出每个聚类的最大分量： 

σjmax=maxj=1,2,…,cσji，j=1,2,…,c(565)

(10) 考查σjmax(j=1,2,…,c)若有σjmax>θs，并同时满足以下两条件之一： 

① j>及Nj>2(θn+1) (类内平均距离大于总类内平均距离，样本数目超过规定值一倍以上)。

② c≤K2。

则该聚类分裂成两个新的聚类，聚类中心分别为

Z+j(J)=Zj(J)+rj
Z－j(J)=Zj(J)－rj(566)

式中，rj=ασj或rj=α0,0,…,σjmax,…,0,0T,0<α≤1。

令c=c+1，J=J+1返回(2)。这里α的选择很重要，应使Xj中的样本到Z+j(J)和Z－j(J)的距离不同，但又使样本全部在这两个集合中。

(11) 计算任意两聚类中心间的距离： 

Dij=DZi(J),Zj(J)，i=1,2,…,c-1,j=1,2,…,c(567)

(12) 将Dij与θc比较，并把小于θc的Dij按递增次序排列，取前L个

Di1j1<Di2j2<…<DiLjL(568)

(13) 考查式(568)，对每一个Diljl(l=1,2,…,L)，相应有两个聚类中心Zil(J)和Zjl(J)，则把两类合并，合并后的聚类中心为

Zl(J)=1Nil+NjlNilZil(J)+NjlZjl(J),l=1,2,…,L

c=c已并掉的类数。

(14) 若J<I，则J=J+1，如果修改给定参数则返回(1)，不修改参数返回(2)，否则J=I，算法结束。

在上述算法步骤中，第(8)~(10)步为分裂，第(11)~(13)步为合并，算法的合并与分裂条件可归纳如下。

(1) 合并条件： (类内样数<θn)‖(类的数目≥2K)&&(两类间中心距离<θc)。

(2) 分裂条件： 类的数目≤K2&&(类的最大分量的标准差＞θs)，即

(σjmax>θs)&&(j>)&&Nj>2(θn+1)‖c≤K2



图511例5.6 样本分布


这里，‖表示“或”的关系，&&表示“与”的关系。当类的数目满足K2<c<2K时，迭代运算的次数是偶数时合并，迭代运算的次数是奇次时分裂。

【例5.6】有一混合样本集，其样本分布如图511所示，试用ISODATA算法进行聚类分析。

【解】如图511所示，样本数目N1=8，取类型数目初始值c=1，执行ISODATA算法。


(1) 给定参数K=2,θn=2,θs=1,θc=4,L=0,I=4，预选X1为聚类中心，即Z1=0,0T，令迭代次数J=1。参数可任意选取，然后在迭代过程中加以调整。

(2) 因只有一个聚合中心Z1=0,0T，故ω1： X1,X2,…,X8，N1=8。

(3) 因N1=8>θn，故没有子集舍弃。

(4) 计算新聚合中心： 


Z1=18∑Xi∈ωiXi=1+2+4+4+5+5+68,1+2+3+3+4+4+58T
=3.38，2.75T


(5) 计算类内距离平均值： 


1=1N1∑Xi∈ω1‖Xi－Z1‖
=182782+2282+1982+1482+1182+682+582+282+

1382+282+582+1082+1382+1082+2182+1882
=2.26


(6) 计算类内总平均距离： 

=1=2.26

(7) 因不是最后一次迭代，且满足c=K2，进入(8)。

(8) 计算聚类ω1中的标准偏差： 


σ11=18∑Xi∈ω1xi1－z112
=180－2782+1－2782+2－2782+4－2782+
5－2782+4－2782+5－2782+6－2782
=3.98=1.99
σ12=182282+1482+682+282+2282+1082+1082+1882=1.56
σ1=σ11,σ12T=1.99，1.56T


(9) σ1中的最大偏差分量为σ11=1.99，即σ1max=1.99。

(10) 因为σ1max>θs，且c=K2。所以把ω1分裂成两个子类，取α=0.5，则0.5σ1max≈1，故新的聚类中心分别为


Z+1=3.38+1,2.75T=4.38,2.75T
Z－1=3.38－1,2.75T=2.38,2.75T


将Z+1和Z－1改写为Z1和Z2，令c=c+1，J=J+1=2，返回(2)。

(2)′ 按最小距离原则，重新聚类，得


ω1： X4,X5,X6,X7,X8，N1=5
ω2： X1,X2,X3，N2=3


(3)′ 因Nj>θn，故无合并。

(4)′ 重新计算聚类中心： 


Z1=1N1∑Xi∈ω1Xi=4.8,3.8T
Z2=1N2∑Xi∈ω2Xi=1.00,1.00T


(5)′ 计算类内距离平均值： 


1=1N1∑Xi∈ω1‖Xi－Z1‖=1.06
2=1N2∑Xi∈ω2‖Xi－Z2‖=0.94



(6)′ 计算类内总平均距离： 

=1N∑2j=1Nj·j=18(5×1.06+3×0.94)=1.02

(7)′ 因是偶次迭代，故跳到(11)。

(11) 计算两个聚类中心之间的距离： 

D12=‖Z1－Z2‖=4.72

(12)~(13)： 因D12>θc，故聚类中心不合并。

(14) 因为不是最后一次迭代，令J=J+1=3，考虑是否修改参数。由上面结果可知，已获得合理的类别数目，两类别中心间距离大于类内总平均距离，每个类别都有足够比例的样本数目，且两类样本数相差不大，因此不必修改控制参数，返回(2)。

第(2)″~(6)″步与上次迭代相同。

(7)″ 所列情况均不满足，继续执行。

(8)″ 计算两个聚合的标准偏差。

σ1=0.75，0.75T，σ1=0.82，0.82T

(9)″ σ1max=0.75，σ2max=0.82。

(10)″ 因为c=K2，且N1和N2均小于2θn+1，分裂条件不满足。继续执行(11)。

第(11)′~(13)′步与前一次迭代结果相同。

(14)′ 因J<I，令J=J+1=4，故无须修改控制参数，返回(2)。

第(2)~(6)步与前一次迭代相同。

(7) 因为J=I，是最后一次迭代，所以令θc=0，跳到(11)。

第(11)″~(13)″步与前一次迭代相同。

(14)″ 因J=I，故聚类过程结束。

在ISODATA算法中，起始聚合中心的选取对聚类过程和结果都有较大影响，如果选择得好，则算法收敛快，聚类质量高。

注意： ISODATA与C均值算法的以下异同点。

(1) 都是动态聚类算法。

(2) C均值算法较简单，ISODATA算法较复杂。

(3) 在C均值算法中，类型数目固定； 在ISODATA算法中，类型数目可变。

5.6Python示例

【例5.7】使用Python对最大最小距离算法进行仿真，并通过该算法对二维模式样本x=［0 3 2 1 5 4 6 5 6 7;0 8 2 1 3 8 3 4 4 5］进行聚类，样本共有10个点，设置合适的阈值，最后将其分为3类。


import math

import numpy as np

import matplotlib.pyplot as plt

import matplotlib as mpl



mpl.rcParams［'font.sans-serif'］ = ［u'SimHei'］# 设置字体为SimHei显示中文

mpl.rcParams［'axes.unicode_minus'］ = False# 设置正常显示字符



def calcuDistance(data1, data2):

"""计算两个模式样本之间的欧氏距离 """





distance = 0

for i in range(len(data1)):

distance += pow((data1［i］ - data2［i］), 2)

return math.sqrt(distance)



def maxmin_distance_cluster(data, Theta):

"""

:param data: 输入样本数据,每行一个特征

:param Theta:阈值，一般设置为0.5，阈值越小聚类中心越多

:return:样本分类，聚类中心

"""

maxDistance = 0

start = 0# 初始选一个中心点

index = start# 相当于指针指示新中心点的位置

k = 0# 中心点计数，也即是类别



dataNum = len(data) # 样本数

distance = np.zeros((dataNum,))

minDistance = np.zeros((dataNum,))

classes = np.zeros((dataNum,))

centerIndex = ［index］



ptrCen = data［0］ # 初始选择第一个为聚类中心点

# 寻找第二个聚类中心，即与第一个聚类中心最大距离的样本点

for i in range(dataNum):

ptr1 = data［i］

d = calcuDistance(ptr1, ptrCen)

distance［i］ = d

classes［i］ = k + 1

if (maxDistance < d):

maxDistance = d

index = i# 与第一个聚类中心距离最大的样本

print("与第一个聚类中心的距离为：{}，索引为：{}".format(distance［i］, index))

# 打印欧氏距离及新的聚类中心

minDistance = distance.copy()

maxVal = maxDistance

while maxVal  (maxDistance * Theta):

k = k + 1

centerIndex += ［index］# 新的聚类中心

for i in range(dataNum):

ptr1 = data［i］

ptrCen = data［centerIndex［k］］

d = calcuDistance(ptr1, ptrCen)

distance［i］ = d

# 按照当前最近邻方式分类，哪个近就分哪个类别

if minDistance［i］  distance［i］:

minDistance［i］ = distance［i］

classes［i］ = k + 1

# 寻找minDistance中的最大距离，若maxVal  (maxDistance * Theta)，则说明存在下一

# 个聚类中心

index = np.argmax(minDistance)

print("最小值中的最大值：{},索引为：{}".format(minDistance［i］, index))

maxVal = minDistance［index］





return classes, centerIndex



data = ［［0, 0］, ［3, 8］, ［2, 2］, ［1, 1］, ［5, 3］, ［4, 8］, ［6, 3］, ［5, 4］, ［6, 4］, ［7, 5］］

Theta = 0.5

classes, centerIndex = maxmin_distance_cluster(data, Theta)

print("样本所属类别：",classes)



marker = ［'o', '*', 's'］

color = ［'r', 'b', 'g'］

data = np.array(data)



plt.figure(figsize=(10,6),dpi=120)

plt.xlim(-1, 8)

plt.ylim(-1, 9)# 设置坐标范围



# 画出样本数据

for idc in np.unique(classes):

tag = classes == idc

index = int(idc - 1)

plt.scatter(data［tag,:］［:, 0］, data［tag,:］［:,1］, c=color［index］, 

marker=marker［index］, label=f"第{int(idc)}类", s=120)

# 画出中心点

for i in range(len(centerIndex)):

plt.scatter(data［centerIndex［i］］［0］, data［centerIndex［i］］［1］, c=color［i］, marker='x', s=500)

plt.legend(loc="lower right",fontsize=16)

plt.grid(True, alpha=0.6)

plt.show()




运行结果：


与第一个聚类中心的距离为：0.0，索引为：0

与第一个聚类中心的距离为：8.54400374531753，索引为：1

与第一个聚类中心的距离为：2.8284271247461903，索引为：1

与第一个聚类中心的距离为：1.4142135623730951，索引为：1

与第一个聚类中心的距离为：5.830951894845301，索引为：1

与第一个聚类中心的距离为：8.94427190999916，索引为：5

与第一个聚类中心的距离为：6.708203932499369，索引为：5

与第一个聚类中心的距离为：6.4031242374328485，索引为：5

与第一个聚类中心的距离为：7.211102550927978，索引为：5

与第一个聚类中心的距离为：8.602325267042627，索引为：5

最小值中的最大值：4.242640687119285,索引为：6

最小值中的最大值：2.23606797749979,索引为：2

样本所属类别： ［1. 2. 1. 1. 3. 2. 3. 3. 3. 3.］




运行结果如图512所示。



图512运行结果







第16集
微课视频



【例5.8】使用Python对基于函数准则的C均值算法进行仿真，并实现对样本的聚类。选择的样本X为二维模式样本，设置两个聚类中心，画出样本聚类情况，并判断［2, 3］和［6, 9］分别属于哪一类。


import numpy as np

from matplotlib import pyplot

from pprint import pprint





import matplotlib as mpl



class K_Means(object):

def __init__(self, k=2, tolerance=0.0001, max_iter=300):

"""

:param k:分组数

:param tolerance:中心点误差

:param max_iter:迭代次数

"""

self.k_ = k

self.tolerance_ = tolerance

self.max_iter_ = max_iter



def fit(self, data):

"""k均值计算 """

self.centers_ = {}# 中心点

for i in range(self.k_):

self.centers_［i］ = data［i］



for i in range(self.max_iter_):

self.clf_ = {}# 分组情况

for j in range(self.k_):

self.clf_［j］ = ［］# 每次迭代清空分组结果

for feature in data:

distances = ［］

for center in self.centers_:

distances.append(np.linalg.norm(feature - self.centers_［center］))
# 欧氏距离

classification = distances.index(min(distances))
# 单个数据的分组结果

self.clf_［classification］.append(feature)
# 将单个数据添加到不同组中



print(f"第{i+1}次迭代")

print("中心点:",end=' ')

pprint(self.centers_)






print("分组情况:",)

pprint(self.clf_, width=120, indent=4, compact=True)

print("-------------------------------------")



prev_centers = dict(self.centers_)

for c in self.clf_:

self.centers_［c］ = np.average(self.clf_［c］, axis=0)

# 重新计算中心点坐标



# 中心点是否在误差范围

optimized = True

for center in self.centers_:

org_centers = prev_centers［center］# 上一次的中心点坐标

cur_centers = self.centers_［center］# 这一次的中心点坐标

if np.sum((cur_centers - org_centers) / (org_centers * 100.0 + 1e-6))  self.tolerance_:

optimized = False

if optimized:

break# 两次中心点坐标比较相差无几后，结束循环



def predict(self, p_data):

"""k均值预测数据"""

distances = ［np.linalg.norm(p_data - self.centers_［center］) for center in self.centers_］# 欧氏距离

index = distances.index(min(distances)) # 单个数据的分组结果

return index



x = np.array(［［0, 0］, ［1, 0］, ［0, 1］, ［1, 1］, ［2, 1］, ［1, 2］, ［2, 2］, ［3, 2］, ［6, 6］, ［7, 6］, ［8, 6］, ［6, 7］, ［7, 7］, ［8, 7］, ［9, 7］, ［7, 8］, ［8, 8］, ［9, 8］, ［8, 9］, ［9, 9］］)

k_means = K_Means(k=2)# 分成2类

k_means.fit(x)



# 开始绘图

pyplot.figure(figsize=(10, 8), dpi=120)

for i, center in enumerate(k_means.centers_):

# 画出中心点

pyplot.scatter(k_means.centers_［center］［0］, k_means.centers_［center］［1］,marker='*', s=150, label=f"第{i}类中心")



for i, cat in enumerate(k_means.clf_):

point = np.array(k_means.clf_［cat］)

pyplot.scatter(point［:, 0］, point［:, 1］, c=('r' if cat == 0 else 'b'),  label=f"第{i}类")  # 画出样本数据



predict = ［［2, 3］, ［6, 9］］

for feature in predict:

cat = k_means.predict(feature)

pyplot.scatter(feature［0］, feature［1］, c=(

'r' if cat == 0 else 'b'), marker='x',

   label = "待检测样本")  # 画出预测数据



pyplot.legend(loc="lower right", fontsize=16)

pyplot.grid(True, alpha=0.6)

pyplot.show()




运行结果： 


第1次迭代

中心点: {0: array(［0, 0］), 1: array(［1, 0］)}

-------------------------------------------------------------

第2次迭代

中心点: {0: array(［0. , 0.5］), 1: array(［5.66666667, 5.33333333］)}

-------------------------------------------------------------

第3次迭代

中心点: {0: array(［1.25 , 1.125］), 1: array(［7.66666667, 7.33333333］)}




聚类结果如图513所示。



图513聚类结果


对获取的数据具有随机性的样本可采用Bayes理论进行分类，其前提是各类别总体的概率分布已知，要决策的分类的类别数一定。对于确定性的模式，如果类别已知(训练样本属性也已知)，则可以通过第2章介绍的方法进行分类。然而在实际应用中，不少情况下无法预先知道样本的标签，也就是说没有训练样本，因而只能从原先没有样本标签的样本集开始进行分类器设计，这就是通常说的无监督学习方法，这就是本章介绍的聚类分析方法。聚类分析无训练过程，训练与识别混合在一起完成。

习题及思考题


5.1证明马哈拉诺比斯距离是平移不变的、非奇异线性变换不变的。

5.2简述有监督学习方法和无监督学习方法的异同。

5.3请聚类下列数据(其中(x,y)代表坐标)，将其分为三个簇。

A1(2,10)，A2(2,5)，A3(8,4)，B1(5,8)，B2(7,5)，B3(6,4)，C1(1,2)，C2(4,9)

其距离为欧氏(欧几里得)距离。起初假设A1、B1、C1为每个簇的聚类中心。用C均值算法给出： 在第一次循环后的三个簇中心和最终的三个簇中心。

5.4ISODATA算法较之于C均值算法的优势何在？

5.5(1) 设有M类模式ωj，j=1,2,…,M，试证明总体离散度矩阵St是总的类内离散度矩阵Sw与类间离散度矩阵Sb之和，即St=Sw+Sb。

(2) 设有二维样本： x1=－1,0T，x2=0，－1T，x3=0,0T，x4=2,0T和x5=0,2T。试选用一种合适的方法进行一维特征提取yi=WTxi。要求求出变换矩阵W，并求出变换结果yi(i=1,2,3,4,5)。

(3) 根据(2)特征提取后的一维特征，选用一种合适的聚类算法将这些样本分为两类，要求每类样本个数不少于两个，并写出聚类过程。

5.6(1) 试给出C均值算法的算法流程。

(2) 试证明C均值算法可使误差平方和准则J(k)=∑cj=1∑xi∈ω(k)jxi－z(k)jTxi－z(k)j最小。其中，k是迭代次数； z(k)j是ω(k)j的样本均值。

5.7证明： 

(1) 如果s是类x上的距离相似性测度，x,y>0,s(x,y)>0，那么对于a>0,s(x,y)+a也是类x上的距离相似性测度。

(2) 如果d是类x上的距离差异性测度，那么对于a>0,d+a也是类x上的距离差异性测度。