马氏与欧氏
第五章 聚类分析
§5.1 什么是聚类分析
聚类分析又称群分析,它是研究(样品或指标)分类问题的一种多元统计方法,所谓类,通俗地说,就是指相似元素的集合。严格的数学定义是较麻烦的,在不同问题中类的定义是不同的。详见参考文献[1]。
聚类分析起源于分类学,在考古的分类学中,人们主要依靠经验和专业知识来实现分类。随着生产技术和科学的发展,人类的认识不断加深,分类越来越细,要求也越来越高,有时光凭经验和专业知识是不能进行确切分类的,往往需要定性和定量分析结合起来去分类,于是数学工具逐渐被引进分类学中,形成了数值分类学。后来随着多元分析的引进,聚类分析又逐渐从数值分类学中分离出来而形成一个相对独立的分支。
在社会经济领域中存在着大量分类问题,比如对我国30个省市自治区独立核算工业企业经济效益进行分析,一般不是逐个省市自治区去分析,而较好地做法是选取能反映企业经济效益的代表性指标,如百元固定资产实现利税、资金利税率、产值利税率、百元销售收入实现利润、全员劳动生产率等等,根据这些指标对30个省市自治区进行分类,然后根据分类结果对企业经济效益进行综合评价,就易于得出科学的分析。又比如若对某些大城市的物价指数进行考察,而物价指数很多,有农用生产物价指数、服务项目价指数、食品消费物价指数、建材零售价格指数等等。由于要考察的物价指数很多,通常先对这些物价指数进行分类。总之,需要分类的问题很多,因此聚类分析这个有用的数学工具越来越受到人们的重视,它在许多领域中都得到了广泛的应用。
值得提出的是将聚类分析和其它方法联合起来使用,如判别分析、主成分分析、回归分析等往往效果更好。
聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。本章主要介绍常用的系统聚类法。
§5.2 距离和相似系数
为了将样品(或指标)进行分类,就需要研究样品之间关系。目前用得最多的方法有两个:一种方法是用相似系数,性质越接近的样品,它们的相似系数的绝对值越接近1,而彼此无关的样品,它们的相似系数的绝对值越接近于零。比较相似的样品归为一类,不怎么相似的样品归为不同的类。另一种方法是将一个样品看作P维空间的一个点,并在空间定义距离,距离越近的点归为一类,距离较远的点归为不同的类。但相似系数和距离有各种各样的定义,而这些定义与变量的类型关系极大,因此先介绍变量的类型。
由于实际问题中,遇到的指标有的是定量的(如长度、重量等),有的是定性的(如性别、职业等),因此将变量(指标)的类型按以下三种尺度划分:
间隔尺度:变量是用连续的量来表示的,如长度、重量、压力、速度等等。在间隔尺度中,如果存在绝对零点,又称比例尺度,本书并不严格区分比例尺度和间隔尺度。
有序尺度:变量度量时没有明确的数量表示,而是划分一些等级,等级之间有次序关系,
如某产品分上、中、下三等,此三等有次序关系,但没有数量表示。
名义尺度:变量度量时、既没有数量表示,也没有次序关系,如某物体有红、黄、白三种颜色,又如医学化验中的阴性与阳性,市场供求中的“产”和“销”等。
不同类型的变量,在定义距离和相似系数时,其方法有很大差异,使用时必须注意。研究比较多的是间隔尺度,因此本章主要给出间隔尺度的距离和相似系数的定义。
设有n个样品,每个样品测得p项指标(变量),原始资料阵为
x1 x2 xp
x12x1p
x22x2p
xn2xnp
其中xij(i1,,n;j1,,p)为第i个样品的第j个指标的观测数据。第i个样品Xi为矩阵
X的第i行所描述,所以任何两个样品KK与XL之间的相似性,可以通过矩阵X中的第K行与第L行的相似程度来刻划;任何两个变量xK与xL之间的相似性,可以通过第K列与第L列的相似程度来刻划。
1 对样品分类(称为Q-型聚类分析)常用的距离和相似系数定义 (1)距离
如果把n个样品(X中的n个行)看成p维空间中n个点,则两个样品间相似程度可用p维空间中两点的距离来度量。令dij表示样品Xi与Xj的距离。常用的距离有:
i)明氏(Minkowski)距离
X1x11
X2x21X
Xnxn1
pdij(q)xiaxja
a1
q
当q=1时
dij(1)
当q=2时
x
a1
p
ia
xja 即绝对距离
2
p2dij(2)(xx)iajaa1
即欧氏距离
当q时
dij()maxxiaxja
1ap
即切比雪夫距离
当各变量的测量值相差悬殊时,要用明氏距离并不合理,常需要先对数据标准化,然
后用标准化后的数据计算距离。
明氏距离特别是其中的欧氏距离是人们较为熟悉的也是使用最多的距离。但明氏距离存在不足之处,主要表面在两个方面:第一,它与各指标的量纲有关;第二,它没有考虑指标之间的相关性,欧氏距离也不例外。除此之外,从统计的角度上看,使用欧氏距离要求一个向量的n个分量是不相关的且具有相同的方差,或者说各坐标对欧氏距离的贡献是同等的且变差大小也是相同的,这时使用欧氏距离才合适,效果也较好,否则就有可能不能如实反映情况,甚至导致错误结论。因此一个合理的做法,就是对坐标加权,这就产生了“统计距离”。比如设P(x1,x2,,xp),Q(y1,y2,,yp),且Q的坐标是固定的,点P的坐标相互独立地变化。用s11,s12,„,spp表示p个变量x1,x2,,xp的n次观测的样本方差,则可以义P到Q的统计距离为:
(xpyp)2(x1y1)2(x2y2)2
d(P,Q)
s11s22spp
所加的权是k1
111
,k2,,kp,即用样本方差除相应坐标。当取s11s22spp
y1y2yp0时,就是点P到原点O的距离。若s11s22spp时,就是欧氏距
离。
ii)马氏(Mahalanobis)距离
马氏距离是由印度统计学家马哈拉诺比斯于1936年引入的,故称为马氏距离。这一距离在多元统计分析中起着十分重要的作用,下面给出定义。
设表示指标的协差阵即:
(ij)pp
1n
其中ij(xaixi)(xajxj) i,j1,,p
n1a1
1n1n
xixai xjxaj
na1na1
如果1存在,则两个样品之间的马氏距离为
2
dij(M)(XiXj)1(XiXj)
这里Xi为样品Xi的p个指标组成的向量,即原始资料阵的第i行向量。样品Xj类似。
顺便给出样品X到总体G的马氏距离定义为
d2(X,G)(X)1(X)
其中为总体的均值向量,为协方差阵。
马氏距离既排除了各指标之间相关性的干扰,而且还不受各指标量纲的影响。除此之外,它还有一些优点,如可以证明,将原数据作一线性交换后,马氏距离仍不变等等。
iii)兰氏(Canberra)距离
它是由Lance和Williams最早提出的,故称兰氏距离。
1
dij(L)
p
x
a1
p
xiaxja
ia
xja
i,j1,,n
此距离仅适用于一切xij0的情况,这个距离有助于克服各指标之间量纲的影响,但没有考虑指标之间的相关性。
计算任何两个样品Xi与Xj之间的距离dij,其值越小表示两个样品接近程度越大,dij值越大表示两个样品接近程度越小。如果把任何两个样品的距离都算出来后,可排成距离阵D:
d11d12d1nddd21222n Ddddn2nnn1
其中d11d22dnn0。D是一个实对称阵,所以只须计算上三角形部分或下三角形部分即可。根据D可对n个点进行分类,距离近的点归为一类,距离远的点归为不同的类。
以上三种距离的定义是适用于间隔尺度变量的,如果变量是有序尺度或名义尺度时,也有一些定义距离的方法,读者可参看文献,[1]。
(2)相似系数
研究样品之间的关系,除了用距离表示外,还有相似系数,顾名思义,相似系数是描写样品之间相似程度的一个量,常用的相似系数有:
i)夹角余弦
这是受相似形的启发而来的,下图曲线AB和CD尽管长度不一,但形状相似。
当长度不是主要矛盾时,要定义一种相似系数,使AB和CD呈现出比较密切的关系,则夹角余弦就适合这个要求。它的定义是:
将任何两个样品Xi与Xj看成p维空间的两个向量,这两个向量的夹角余弦用cosij表示。则
cosij
x
a1p
2
iaa1
p
iaxja
p
1cosij1
2ja
xx
a1
当cosij1,说明两个样品Xi与Xj完全相似;cosij接近1,说明Xi与Xj相似密切;
cosij0,说明Xi与Xj完全不一样;cosij接近0,说明Xi与Xj差别大。把所有两两
样品的相似系数都算出,可排成相似系数矩阵:
cos11cos12coscos2221H○
cosn1cosn2
cos1ncos2n
cosnn
其中cos11cos22cosnn1。○H是一个实对称阵,所以只须计算上三角形部分或下三角形部分,根据○H可对n个样品进行分类,把比较相似的样品归为一类,不怎么相似的样品归为不同的类。 ii)相关系数
通常所说相关系数,一般指变量间的相关系数,作为刻划样品间的相似关系也可类似给出定义,即第i个样品与第j个样品之间的相关系数定义为:
(x
rij
a1
p
ia
xi)(xjaxj)
(x
a1
p
ia
xi)2
(x
a1
p
-1rij1
ja
xj)2
其中
1
xi
p
1
xia xj
pa1
p
x
a1
p
ja
实际上,rij就是两个向量XiXi与XjX
j
的夹角余弦,其中
Xi(xi,,xi),Xj(xj,,xj)。若将原始数据标准化,则XiXj0,这时
rijcosij。
r11r12r1nrrr21222n R(rij)rrrnnn1n2
其中r11r22rnn1,可根据R对n个样品进行分类。
名义尺度也有一些相似系数的定义,读者可参考文献[1]。
2 对指标分类(称为R-型聚类分析)常用的距离和相似系数定义
p个指标(变量)之间相似性的定义与样品相似性定义类似,但此时是在n维空间中来研究的,变量之间的相似性是通过原始资料矩阵X中p列间相似关系来研究的。
(1)距离
令dij表示变量Xi(x1i,,xni)与变量Xj(x1j,,xnj)之中距离。
i)明氏距离
n
dij(q)xaixaj
a1
q
q
ii)马氏距离
设表示样品的协差阵即
(ij)nn
1p
其中ij(xiaxi)(xjaxj) i,j1,,n p1a1
1p1p
xixia xjxja
pa1pa1
如果1存在,则马氏距离为
2dij(M)(xixj)1(xixj)
iii)兰氏距离
dij(L)
此处仅适用于一切xij0的情况。
(2)相似系数
i)夹角余弦
x
a1
n
xaixaj
ai
xaj
cosij
x
a1n
2aia1
n
aixaj
n
-1cosij1
2aj
xx
a1
把两两列间相似系数算出后,排成矩阵
cos11cos12coscos2221H=○
cosp1cosp2
cos1p
cos2p
cospp
其中cos11cos22cospp1,根据○H对p个变量进行分类。
ii)相关系数
n
(x
rij
ai
ai
xi)(xajxj)
(x
a1
n
ai
xi)2
(x
a1
n
-1rij1
aj
xj)2
把两两变量的相关系数都算出后,排成矩阵为
r11r12r1prrr21222p R(rij)rrrp1p2pp
其中r11r22rpp1,可根据R对p个变量进行分类。
在实际问题中,对样品分类常用距离,对指标分类常用相似系数。
由于样品分类和指标分类从方法上看基本上是一样的,所以两者就不严格分开说明了。
§5.3 八种系统聚类方法
正如样品之间的距离可以有不同的定义方法一样,类与类之间的距离也有各种定义。例如可以定义类与类之间的距离为两类之间最近样品的距离,或者定义为两类之间最远样品的距离,也可以定义为两类重心之间的距离等等。类与类之间用不同的方法定义距离,就产生了不同的系统聚类方法。本节介绍常用的八种系统聚类方法,即最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法、离差平方和法。系统聚类分析尽管方法很多,但归类的步骤基本上是一样的,所不同的仅是类与类之间的距离有不同的定义方法,从而得到不同的计算距离的公式。这些公式在形式上不大一样,但最后可将它们统一为一个公式,对上机计算带来很大的方便,详见后。
以下用dij表示样品Xi与Xj之间距离,用Dij表示类Gi与Gj之间的距离。
1 最短距离法
定义类Gi与Gj之间的距离为两类最近样品的距离,即
Dij
GiGi,GJGj
min
dij
dij
设类Gp与Gq合并成一个新类记为Gr,则任一类Gk与Gr的距离是:
Dkr
XiGi,XjGj
min
minmindij,mindij
XiGk,XjGq
XiGk,XjGpminDkp,Dkq
最短距离法聚类的步骤如下:
(1)定义样品之间距离,计算样品两两距离,得一距离阵记为D(0),开始每个样品自
成一类,显然这时Dijdij。
(2)找出D(0)的非对角线最小元素,设为Dpq,则将Gp和Gq合并成一个新类,记为
Gr,即GrGp,Gq。
(3)给出计算新类与其它类的距离公式:
DkrminDkp,Dkq
将D(0)中第p、q行及p、q列用上面公式并成一个新行新列,新行新列对应Gr,所得到的矩阵记为D(1)。
(4)对D(1)重复上述对D(0)的(2)、(3)两步得D(2);如此下去,直到所有的元素并成一类为止。
如果某一步D(k)中非对角线最小的元素不止一个,则对应这些最小元素的类可以同时合并。
为了便于理解最短距离法的计算步骤,现在举一个最简单的数字例子。
例1 设抽取五个样品,每个样品只测一个指标,它们是1,2,3.5,7,9,试用最短距离法对五个样品进行分类。
(1)定义样品间距离采用绝对距离,计算样品两两距离,得距离阵D(0)如下:
表1
(2)找出D(0)中非对角线最小元素是1,即D12d121,
则将G1与G2并成一个新类,记为G6X1,X2。
(3)计算新类G6与其它类的距离,按公式:
Gi6min(Di1,Di2) i3,4,5
即将表D(0)的前两例取较小的一列得表D(1)如下:
表2
(4)找出D(1)中非对角线最小元素是1.5,则将相应的两类G3和G6合并为
G7X1,X2,X3,然后再按公式计算各类与G7的距离,即将G3, G6相应的两行两列归并一行一列,新的行列由原来的两行(列)中较小的一个组成,计算结果得表D(2)如下:
(5)找出D(2)中非对角线最小元素是2,则将G4与G5合并成G8X4,X5,最后再按公式计算G7与G8的距离,即将G4,G5相应的两行两列归并成一行一列,新的行列由原来的两行(列)中较小的一个组成,得表D(3)如下:
表4
最后将G7 和G8合并成G9,上述并类过程可用下图表达。横坐标的刻度是并类的距离。
X1 X2 X3 X4 X5
由上图看到分布两类X1,X2,X3及X4,X5比较合适,在实际问题中有时给出一个阈值T,要求类与类之间的距离小于T,因此有些样品可能归不了类。
最短距离法也可用于指标(变量)分类,分类时可以用距离,也可以用相似系数。但用相似系数时应找最大的元素并类,也就是把公式Dikmin(Dip,Diq)中的min换成max。
2 最长距离法
定义类Gi与类Gj之间距离为两类最远样品的距离,即
Dpq
XiGp,XjGq
max
dij
最长距离法与最短距离法的并类步骤完全一样,也是将各样品先自成一类,然后将非对角线上最小元素对应的两类合并。设某一步将类Gp与Gq合并为Gr,则任一类Gk与Gr的距离用最长距离公式为
Dkrmax
XiGk,XjGr
dij
maxmaxdij,maxdij
XiGk,XjGq
XiGk,XjGp=maxDkp,Dkq
再找非对角线最小元素的两类并类,直至所有的样品全归为一类为止。 易见最长距离法与最短距离法只有两点不同:一是类与类之间的距离定义不同;另一是计算新类与其它类的距离所用的公式不同。下面将要介绍的其它系统聚类法之间的不同点也表现在这两个方面,而并类步骤完全一样,所以下面介绍其它系统聚类方法时,主要指出这两个方面:定义和公式。
举例1应用最长距离法按聚类步骤(1)—(3)可得下表:
D(0)为
表5
D(1)为
表6
D(2)为
表7
D(3)为
表8
最后将G6和G8合并成G9。其聚类图如下,与最短距离法分类情况一致,只是并类的距离不同。
X
X
X
X4
X5
3 中间距离法
定义类与类之间的距离既不采用两类之间最近的距离,也不采用有两类之间最远的距离,而是采用介于两者之间的距离,故称为中间距离法。
如果在某一步将类Gp与类Gq合并为Gr,任一类Gk和Gr的距离公式为:
2Dkr
12122
DkpDkqDpq22
1
0 4
1
时,由初等几何知Dkr就是上面三角形的中线。 4
如果用最短距离法,则DkrDkp;如果用最长距离法,则DkrDkp;如果取夹在这两
当
121212
DkpDkqDpq,由于距离公式中的量都是距离的平224
方,为了上机计算的方便,可将表D(0)、D(1)、D(2)、„„中的元素,都用相应元素的平方
边的中线作为Dkr,则Dkr
2
代替而得表D(20)、D(21)、D(2)、„。
1
。 4
(1)将每个样品看作自成一类,因此Dijdij,得表D(0),然后将D(0)中元素平方得
将例1用中间距离法分类,取表D(20)为
表9
(2)找出D(20)中非对角线最小元素是1,则将G1
、G2合并成一个新类G6。 (3)按中间距离公式计算新类G6与其它类的平方距离得D(21)表为
表10
如:
121212
D31D32D12 224111
6.252.25 224 4
(4)找出D(2则将G3和G6合并成G7,将G4和1)中非对角线最小元素是D36D454,
2
D36
G5合并成G8。
(5)最后计算G7和G8的平方距离,得D(22)表为:
表11
XXXX4 X
不难看出此聚类图的形状和前面两种聚类图一致,只是并类距离不同。而且可以发现中间距离法的并类距离大致处于它们的中间。
4 重心法
定义类与类之间距离时,为了体现出每类包含的样品个数给出重心法。
重心法定义两类之间的距离就是两类重心之间的距离。设Gp和Gq的重心(即该类样品的均值)分别是Xp和Xq(注意一般它们是p维向量),则Gp和Gq之间的距离是
DpqdXpXq。
设聚类到某一步,Gp和Gq分别有样品np,nq个,将Gp和Gq合并为Gr,则Gr内样品个数为nrnpnq,它的重心是Xr
1
(npXnr
p
nqXq),某一类Gk的重心是Xk,它
与新类Gr的距离(如果最初样品之间的距离采用欧氏距离)为
22DkrdX(XkXr)(XkXr) kXr
11
(npXpnqXq)Xk(npXpnqXq) Xknrnr
npnq
XkXk2XkXp2XkXq
nrnr12
2(n2XX2nnXXnXkkpqqXq) ppqpnr
1利用XkXknpXkXknqXkXk代入上式得
nr
np'nq
DXkXk2XpXqXPXqXkXk2XkXqXqXq
nrnr
2
kr
npnqnr2
(X
p
X
p
2X
p
XqX
2 Dpq
q
Xq)
np
nrnrnrnr
显然,当npnq时即为中间距离法的公式。
2Dkp
nq
2
Dkq
npnq
如果样品之间的距离不是欧氏距离,可根据不同情况给出不同的距离公式。
重心法的归类步骤与以上三种方法基本上一样,所不同的是每合并一次类,就要重新计算新类的重心及各类与新类的距离。
将例1用重心法分类。
重心法的初始距离阵D(20)与中间距离法相同(即表9),D(20)表为:
首先将G1与G2并成新类G6,其重心为X61.5,计算G6与其它各类重心之间的平方距离得D(21)阵如下:
其中 如D46
2
2
Dk6
n12n22nn2
Dk1Dk2122D12n6n6n6
k3,4,5
111
3625130.25 224
非对角线最小元素为4,可将G3与G6并成G7,G4与G5并成G8,计算新类与其它重心间的平方距离得D(22)如下:
最后将G7与G8合并成G9,其聚类图如下:
X1 X2 X3 X4 X5 0
5 类平均法
重心法虽有很好的代表性,但并未充分利用各样品的信息,因此给出类平均法,它定义两类之间的距离平方为这两类元素两两之间距离平方的平均,即
2Dpq
1
npnq
XiGpXjGj
d
2ij
设聚类到某一步将Gp和Gq合并为Gr,则任一类Gk与Gr的距离为
2 Dkr
1
nknr
XiGkXjGr
d
2ij
122dijdij
nknrXiGkXjGp
XiGkXjGq
np2nq2
DkpDkq
nrnr
类平均法的聚类步骤与上述方法完全类似,就不详述了。 将例1用类平均法分类,同前D(20)表如下:
将G1与G2合并为G6,按类平均法的距离公式计算G6与D(20)中非对角线最小元素是1,其它类的距离得D(21)表如下:
2
Dk6
其中
1212
k =3,4,5 Dk1Dk2
22112
如 D366.252
.254.25
22
2
将G4与G5合并为G7,计算G7与其它各类的距离得D(22)D(1)中非对角线最小元素是4,
表如下:
最后将G8与G7合并成G9,其聚类图如下
6 可变类平均法
由于类平均法公式中没有反映Gp与Gq之间距离Dpq的影响,所以给出可变类平均法,此法定义两类之间的距离同上,只是将任一类Gk与新类Gr的距离改为如下形式:
nrnr
其中是可变的且1。
仍取例1的数据用可变类平均法分类。
2Dkr
np
(1
2)Dkp
np
22
(1)DkqDpq
D(20)表如下:
D(20)中非对角线最小元素是1,将G1与G2合并成G6,并按照上述公式计算G6与其它
各类的距离,取
1
,求得D(21)表如下: 4
将G4与G5合并为G7,计算G7与其它各类的距离得D(22)D(21)中非对角线最小元素是4,表如下:
将G3
与G6合并成G8,计算G8与G7的距离得D(22)表如下:
最后将G7与G8合并成G9,其聚类图如下:
7 可变法
此法定义两类之间的距离仍同上,而新类Gr与任一类的Gk的距离公式为:
2Dkr
1222
(DkpDkq)Dpq
2nq
其中是可变的,且1。
1
,即为上式。
nrnr2
可变类平均法与可变法的分类效果与的选择关系极大,如果接近1,一般分类效果
1
不好,在实际应用中常取负值。下面用例1数据用可变法分类,取
,D(20)表如下:
显然在可变类平均法中取
np
将G1与G2合并成G6,按上述公式计算G6与任一类的距离得D(21)表如下: 再将G4与G5合并成G7,计算G7与其它类距离得D(22)表如下:
G4{X4,X5}
66.66 25.56 0
再将G3与G6合并成G8,计算G8与G7的距离得D(23)表如下:
最后将G7与G8合并成G9,其聚类图如下:
8 离差平方和法
这个方法是Ward提出来的,故又称为Ward法。
设将n个样品分成k类:G1, G2, „, Gk, 用Xi(t)表示Gt中的第i个样品(注意Xi(t)是p维向量),nt表示Gt中的样品个数,X
(t)
是Gt的重心,则Gt中样品的离差平方和为:
St
i1
nt
(Xi(t)X
(t)
)(Xi(t)X
(t)
)
k个类的类内离差平方和为
S
t1
k
St
t1i1
knt
(Xi(t)X
(t)
)(Xi(t)X
(t)
)
Ward法的基本思想是来自于方差分析,如果分类正确,同类样品的离差平方和应当较小,类与类的离差平方和应当较大。具体做法是先将n个样品各自成一类,然后每次缩小一类,每缩小一类离差平方和就要增大,选择使S增加最小的两类合并(因为如果分类正确,同类样品的离差平方和应当较小)直到所有的样品归为一类为止。
粗看Ward法与前七种方法有较大的差异,但是如果将Gp与Gq的距离定义为
2DpqSrSpSq
其中GrGp
G
q
,就可使Ward法和前七种系统聚类方法统一起来,且可以证明Ward法
合并类的距离公式为:
nrnknrnk
将例1用Ward法分类:
(1)将五个样品各自分成一类,显然这时类内离差平方和S=0。
(2)将一切可能的任意两列合并,计算所增加的离差平方和,取其中较小的S所对应的类合并,例如将G1X1、G2X2合并成一类,它的离差平方和
2Dkr
nknp
2
Dkp
nknq
2
Dkq
nk2
Dpq
nrnk
S(11.5)2(21.5)20.5,如果将G1X1、G3X3合并,它的离差平方和S(12.25)2(3.52.25)23.125,将一切可能的两类合并的离差平方和都算出,列表如下:
表13
表中非对角线最小元素是0.5,说明将G1、G2合并为G6增加的S最少,计算G6与其它 类的距离得D(21)表如下:
2
其中 Dk6
nkn12nkn22nk2
Dk1Dk2D12
n6nkn6nkn6nk
k3,4,5
这里n1
n2n3n4n51,n62
上表非对角线最小元素是2,将G4、G5合并为G7,计算G7与其它类的距离得D(22)表如k42k52k22DDD45其中 Dk7k4k5n7nkn7nkn7nk
这里n3n4n51,n6n72
k3,6
上表非对角线最小元素是2.667,将G3、G6合并为G8,计算G8与G7的距离得D(23)表如下:
2
其中 D78
n7n32n7n62n72
D73D76D36
n7n8n7n8n7n8
342
13.542.252.66740.83 5
55
最后将G7、G8合并G9,将全部分类过程列表如下:
用增加最小的离差平方和代替合并的平方距离也可画出聚类图如下:
上面介绍了八种系统聚类方法,这些方法聚类的步骤是完全一样的,所不同的是类与类之间的距离有不同的定义法。依法所给出的新类与任一类的距离公式不同。但这些公式在1967年由兰斯(Lance)和威廉姆斯(Williams)统一起来(参考文献[1])。当采用欧氏距离时,八种方法有统一形式的递推公式。
222222DKRpDkpqDkqDpq|DkpDkq|
如果不采用欧氏距离时,除重心法、中间距离法、离差平方和法之外,统一形式的递推公式
仍成立。上式中参数p、q、、对不同的方法有不同的取值。表15列出上述八种方法中参数的取值。八种方法公式的统一,对于编制程序提供了很在的方便。
对指标进行分类时,常用的是相似系数,统一记为Cij(如夹角余弦,相关系数等)。若用相关系数时应找最大的元素并类,也可将相关系数转化为距离,以便维护距离越小则关系
22越密切的含义,例如可取dij1Cij或者dij。 1Cij
表15
上述例1给出的数字例子,用八种系统聚类法并类的结果都是一致的,只是并类的距离不同。然而在一般情况下,用不同的方法聚类的结果是不完全一致的。自然会问哪一种方法好呢?这就需要提出一个标准作为衡量的依据,但至今还没有一个合适的标准。各种方法的比较目前仍是值得研究的一个课题,在实际应用中,一般采用以下两种处理方法:一种办法是根据分类问题本身的专业知识结合实际需要来选择分类方法,并确定分类个数。另一种办法是多用几种分类方法去作,把结果中的共性取出来,如果用几种方法的某些结果都一样,则说明这样的聚类确实反映了事物的本质,而将有争议的样品暂放一边或用其它办法如判别
分析去归类。下面再看两个实例。
例1 为了更深入了解我国人口的文化程度状况,现利用1990年全国人口普查数据对全国30个省、直辖市、自治区进行聚类分析。分析选用了三个指标:(1)大学以上文化程度的人口占全部人口的比例(DXBZ);(2)初中文化程度的人口占全部人口的比例(CZBZ);(3)文盲半文盲人口占全部人口的比例(WMBZ)、分别用来反映较高、中等、较低文化程度人口的状况,原始数据如下表:
1990年全国人口普查文化程度人口比例(%)
数据来源:《中国计划生育全书》第886页。
计算样品之间的相似系数,使用最长距离法、重心法和Ward法,将上机计算结果按样品号画出聚类图如下:
根据聚类图把30个样品分为四类能更好地反映我国实际情况。
第一类:北京、天津、山西、辽宁、吉林、黑龙江、上海。其中大多是东部经济、文化较发达的地区。
第二类:安徽、宁夏、青海、甘肃、云南、贵州。其中大多是西部经济、文化发展较慢的地区。
第三类:西藏。经济、文化较落后的地区。
第四类:其它省、直辖市、自治区。经济、文化在全国处于中等水平。 例2 根据信息基础设施的发展状况,对世界20个国家和地区进行分类。
这里选取了发达国家、新兴工业化国家、拉美国家、亚洲发展中国家、转型国家等不同类型的20个国家作Q型聚类分析。描述信息基础设施的变量主要有六个:(1)Call—每千人拥有电话线数,(2)movecall—每千房居民蜂窝移动电话数,(3)fee—高峰时期每三分钟国际电话的成本,(4)Computer—每千人拥有的计算机数,(5)mips—每千人中计算机功率《每秒百万指令》,(6)net—每千人互联网络户主数。数据摘自《世界竞争力报告—1997》。
由于数据存在量纲和数量级的差别,在聚类之前先进行标准化处理,计算样品之间的距离采用欧氏距离。下面分别用最长距离法、重心法、离差平方和法进行计算,其结果如下表:
最长距离法
Brazil Mexico
Porland
Hungary
Malasia Chile
Russian
Tailand
Indian Taiwan
Korea
Japan
German France
Singapo
British
Switzer
重心法
Brazil Mexico
Porland Hungary Chile Malasia Russian Tailand Indian German France Singapo British Switzer British Switzer Taiwan Korea Japan Sweden Denmark
10
离差平方和法见下页图。 从聚类图看,本例用三种方法聚类结果基本一致,而最长距离法和重心法所得结果更接近一致,结合实际情况分析采用离差平方和法把20个国家分为两类:
第Ⅰ类:巴西、墨西哥、波兰、匈牙利、智利、俄罗斯、泰国、印度、马来西亚。 第Ⅱ类:瑞典、丹麦、美国、中国台湾、韩国、日本、德国、法国、新加坡、英国、瑞士。
其中第Ⅰ类中的国家为转型国家和亚洲、拉美发展中国家,这些国家经济较不发达,基础设施薄弱,属于信息基础设施比较落后的国家;第Ⅱ类中的国家是美、日、欧洲发达国家与新兴工业化国家中国台湾、新加坡、韩国。新兴工业化国家这几十年来发展迅速,努力赶超发达国家,在信息基础设施的发展上已非常接近发达国家,而发达国家中美国、瑞典、丹麦的信息基础设施发展最为良好。
§5.4 系统聚类法的基本性质
1 单调性
设Dk是系统聚类法中第k次并类时的距离,如果D1D2,则称并类距离具有单调性。可以证明最短距离法、最长距离法、类平均法、离差平方和法、可变法和可变类平均法都具有单调性,只有重心法和中间距离法不具有单调性。
有单调性画出的聚类图符合系统聚类的思想,先结合的类关系较近,后结合的类关系较远。
2 空间的浓缩或扩张
设两个同阶矩阵D(A)和D(B),如果D(A)的每一个元素不小于D(B)相应的元素,则记为D(A)≥D(B)。特别地如果矩阵D的元素是非负的,则有D≥0。(提醒注意,此处D≥0的含义与非负定阵的含义不同,这个记号仅在本章使用)。
2
如果D(A) ≥0,D(B) ≥0,D(A)表示将D(A)的每个元素平方,则
D(A)D(B)D2(B)。
令D(A,B)D2(A)D2(B) 则D(A,B)0D(A)D(B)
若有两个系统聚类法A, B,在第k步距离阵记为D(Ak)D(Bk)(k0,1,,n1),若
D(Ak,Bk)0即D(Ak)D(Bk)(k1,,n1),则称A比B使空间扩张或B比A使空间浓缩。用下例距离阵D(0)来说明最长距离法比最短距离法扩张)(或张说最短距离法比最长
距离法浓缩)。
D(1)
G6 G1 G4 G5
D(2) D*(2)
G7G1G5
G7034
G1G5010
G7G1G5
G7067
G1G5010
D(3) D*(3)
G8G5
G804
G5
G8
G5
G8G5
100
左边是用最短距离法的并类过程所算出的距离阵D(1)、D(2)、D(3)。右边是用最长距离法的
**
并类过程所算的距离阵D(1)、D(2)、D(3)。显然D(1)D(*1)、D(2)D(2)、D(3)D(3),所
以说最短距离法比最长距离法浓缩。
今用短、长、重、平、变平、可变、离,分别表示八种方法,它们的平方距离记为D2
(短)、D2(长)、D2(中),„。然后以类平均法为基准,其它方法都与它来比较,则不难得出:
(1)D(短,平)≤0 (2)D(长,平)≥0 (3)D(重,平)≤0
0,0
(4)D(变平,平)
0,10
(5)D(离,平)≤0
(6)中间距离法与类平均法的比较没有统一的结论,它可能≥0,也可能≤0。
一般作聚类图时横坐标(并类距离)的范围太小时对区别类的灵敏度就差些,也就是说太浓缩的方法不够灵敏,但太扩张的方法对分类不利。和类平均法相比最短距离法、重心法使空间浓缩。最长距离法、可变类平均法、最差平方和法使空间扩散,而类平均法比较适中,与其它方法相比,既不太浓缩也不太扩张。
还有一些性质,如单调变换不变性、类重复不变性等,就不再介绍了。
§5.5 附 注
1 选代表性指标
用聚类方法分类完之后,如果各类中指标较多,又不想把类分得太多,这时要想从每类中选一个代表性指标该怎么办?一个简单的办法就是计算每类中相关指数的平均值R,取其中较大者对应的指数做为该类的代表性指标。
计算公式:
2
R
2
r
j1
2ij
k1
i,j1,,k
2
其中k为某一类中变量的个数,rij为该类内变量xi对类中其它变量的相关系数的平方。
例如:体重、胸围、大腿围是一类的三个指标,其相关系数表如下:
2
计算体重对胸围及大腿围的R1
(0.8233)2(0.7403)20.6121
31
胸围对体重及大腿围的R2
2
(0.8233)2(0.6413)20.5445
31
大腿围对体重及胸围的R3
2
(0.7403)2(0.6413)20.4331
31
由于R1值最大,所以这一类代表性指标取为体重。在身高一定的前提下,一般说来体重重的人其胸围和大腿围的指标都较大些,这是符合常规的。
2. 在本章§5.1中,曾提到聚类分析的内容是很丰富的,本章只介绍国内外常用的八种系统聚类法,除此而外,还有有序样品聚类法、模糊聚类法、动态聚类法等等。为便于读者使用这些方法,这里简单介绍一下这些方法所能解决的是哪类问题。
系统聚类法,被分类的样品是相互独立的,分类时彼此是平等的。而有序样品分类法要求样品按一定的顺序排列的,分类时是不能打乱次序的,即同一类样品必须是互相邻接的。比如要将建国以来国民收入的情况划分几个阶段,此阶段的划分必须依年份的顺序为依据;又如研究天气演变的历史时,样品是按从古到今的年代排列的,年代的次序也是不能打乱的,研究这类样品的分类问题就用有序样品聚类法。
有序样品的分类实质上是找一些分点,将有序样品划分为几个分段,每个分段看作一个类,所以分类也称为分割。显然分点取在不同的位置就可以得到不同的分割。通常寻找最好分割的一个依据就是使各段内部样品之间的差异最小,而各段样品之间的差异较大。有序样品聚类法就是研究这种最优分割法。
模糊聚类法是将模糊集的概念用到聚类分析中所产生的一种聚类方法,它是根据研究对象本身的属性而构造一个模糊矩阵,在此基础上根据一定的隶属度来确定其分类关系。
动态聚类法又称为逐步聚类法,它是先粗糙的进行预分类,然后再逐步调整,直到满意为止。整个聚类过程如下图:
框图的每一部分,均有许多种处理方法,这些方法按框图组合,就得到各种动态聚类方法。
选作题参考
5.1 对世界15个国家社会发展水平作聚类分析。
5.2 对世界16个国家8项经济指标作聚类分析。 5.3 对北京市区县保险公司分类的探讨。 5.4 中国房地产经济分区初步探讨。 5.5 分析我国农村消费区域类型。
2
5.6 按照城乡居民消费水平,对我国30个省市自治区分类。 5.7 横向比较30个省市自治区工业的经济效益和科技水平。 5.8 对各地区社会总产值的部门构成进行聚类分析。
5.9 对30个省市自治区根据农林牧副渔各生产值的大小进行分类。 5.10 从科研与发展状况这一角度对全国29个省市进行行发类。
5.11 某行政系统所属独立核算工业企业16个行业经济实力强弱的聚类分析。 5.12 聚类分析在行业经济效益分析中的应用。 5.13 对1991年工业总产值进行分类研究。
5.14 对世界各国国民生产总值部门构成进行研究。 5.15 聚类分析在研究各国国际竞争力中的应用。
5.16 运用聚类分析对世界各国财富来源构成的研究(财富来源包括:人力资源、生产资产、自然资本)。
5.17 对全国部分省份的城市设施水平的各项指标作聚类分析。
上述选作题的数据可来自各个方面,为节省篇幅,皆略去,如果读者在作题时遇到数据的困难,建议查阅历年《中国统计年鉴》,它可以帮助读者解决一部分数据的来源。以下各章的选作题数据都可如此处理。