聚类分析新
聚类分析
一、 二、 三、 四、 五、
聚类产生的背景
聚类分析中常用的一些方法 产生聚类的依据
聚类常用的八种距离及简单对比
例题
第一节 聚类分析产生的背景、方法及聚类依据
聚类分析起源于分类学,在考古的分类学中,人们主要依靠经验和专业知识来实现分类。随着生产技术和科学的发展,人类的认识不断加深,分类越来越细,要求也越来越高,有时光凭经验和专业知识是不能进行确切分类的,往往需要定性和定量分析结合起来去分类,于是数学工具逐渐被引进分类学中,形成了数值分类学。后来随着多元分析的引进,聚类分析又逐渐从数值分类学中分离出来而形成一个相对独立的分支。
在社会经济领域中存在着大量分类问题,比如对我国30个省市自治区独立核算工业企业经济效益进行分析,一般不是逐个省市自治区去分析,而较好的做法是选取能反映企业经济效益 的代表性指标,如百元固定资产实现利税、资金利税率、产值利税率、百元销售收入实现利润、全员劳动生产率等等,根据这些指标对30个省市自治区进行分类,然后根据分类结果对企业经济效益进行综合评价,就易于得出科学的分析。又比如若对某些大城市的物价指数进行考察,而物价指数很多,有农用生产物价指数、服务项目物价指数、食品消费物价指数、建材零售价指数等等。由于要考察的物价指数很多,通常先对这些物价指数进行分类。总之,需要分类的问题很多,因此聚类分析这个用用的数学工具越来越受到人们的重视,它在学的领域中都得到了广泛的应用。 1.1什么是聚类分析
聚类分析又称群分析,它是研究(样品或指标)分类问题的一种多元统计方法,所谓类,通俗的说,就是指相似元素的集合。 1.2 聚类分析常用方法
聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法。本节主要介绍常用的系统聚类法。其它方法用法参见第三节。 1.3聚类分析的依据
为了将样品(或指标)进行分类,就需要研究样品之间关系。目前用的最多的方法有两个:一种方法是用相似系数,性质越接近的样品,它们的相似系数的绝对值越接近于1,而彼此无关的样品,它们的相似系数的绝对值越接近于0.比较相似的样品归为一类,不怎么相似的样品归为不同的类。另一种方法是将一个样品看做P维空间的一个点,并在空间定义距离,距离越近的点归为一类,距离较远的点归为不同的类。
1 对样品分类(称为Q-型聚类分析)常用的距离和相似系数定义 1.1距离
设有n个样品X1,X2,,Xn,每个样品有p个变量的测试数据,用矩阵表示为
X1x11
X2x21
X
Xnxn1
x12x22xn2
x1p
x2p
xnp
称为样品观测值矩阵。其中xij((i1,,n;j1,,p))为第i个样品的第j个指标的观测数据。
由于每个样品各个变量的观测值具有不同的数量级和不同的测量单位,所以有必要进行变换,或者说用下列方法之一进行调整,得到无量纲数据,以消除其中的不合理现象,提高分类效果。常用的数据变换方法如下: (1)标准化法 做数据 x
*ij
xijXi
Si
n
(i1,,n;j1,,p)
其中 Xi
1n
j1
xij;Si
(2)正规化法 做数据 xij
*
xijmin(xij)
1jn
max(xij)min(xij)
1jn
1jn
(i1,,n;j1,,p)
(3)极差标准化法 做数据 x
*ij
xijXi
max(xij)min(xij)
1jn
1jn
(i1,,n;j1,,p)
(4)极大值正规化法 做数据 x
*ij
xijmax(xij)
1jn
(i1,,n;j1,,p)
(5)均值正规化法 做数据 x
*ij
xijXi
(i1,,n;j1,,p)
第i个与第j个样品之间的距离用dij表示,dij一般应满足下面的条件:
dij0
当第i个样品与第j个样品相等;
;
dij0 对一切i,j
dijdikdki
对 一切i,j,k。,
最常用的距离有欧氏距离、闵可夫斯基距离和马氏距离。 (1)绝对值距离
m
dij
(2)欧氏距离:
k1
xkixkj
1
22
dij(xikxjk)
k1
p
(3)闵可夫斯基(Minkowski)距离:
1
dijxikxjk
k1
p
g
g
g一般为1或2,如果g=1时也称之为绝对值距离,g=2时也称之为欧几里德距离。
闵可夫斯基(Minkowski)距离特别是其中的欧氏距离是人们较为熟悉的也是使用最多的距离。但闵可夫斯基(Minkowski)距离残在不足之处,主要表现在两个方面:第一,他与各指标的量纲有关;第二,它没有考虑指标之间的相关性,欧氏距离也不例外。除此之外,从统计的角度上看,使用欧氏距离要求一个向量的n个分量是不相关的且具有相同的方差,或者说各坐标对欧氏距离的贡献是同等的且变差大小也是相同的,这时使用欧氏距离才合适,效果也较好,否则就有可能不能如实反映情况,甚至导致错误结论。因此一个合理的做法,就是对坐标加权,这就产生了“统计距离”。比如设P(x1,x2,,xp)T,
Q(y1,y2,,yp),且Q的坐标是固定的,点P的坐标相互独立地变化。用
T
11,22,,
pp
,表示p个变量x1,x2,,xp的n次观测的样本方差,则可定义P到
Q的统计距离为:
d(P,Q)
即用样本方差除相应坐标。
(4)马氏(Mathalanobis)距离:
马氏距离是由印度统计学家马哈拉比斯于1936年引入的,故称为马氏距离。
dij2(xixj)T
1
(xixj)
马氏距离既排除了各指标之间相关性的干扰,而且还不守各指标量纲的影响。除此之外,它还有一些优点,如可以证明,将元数据作一线性交换后,马氏距离仍不变等等。
(5)契比雪夫(Chebishov)距离
maxxkixkj dij1
km
其中,xi为第i组样品的p个元素组成的向量,xj为第j组样品的p个元素组成的向量,
1
为p个变量的pp的协方差矩阵的逆矩阵。
计算任何两个样品Xi与Xj之间的距离dij,其值越小表示两个样品接近程度越大,dij值越大表示两个样品接近程度越小。如果把任何两个样品的距离都算出来后,可排成距离阵D:
d11
d21
D
dn1
d12d22dn2
d1n
d2n
dnn
其中d11d22dnn0。D是一个是对称阵,所以只须计算上三角形部分或下三角形部分即可。 1.2相似系数
研究样品之间的关系,除了用距离表示外,还有相似系数,顾名思义,相似系数是描写样品之间相似程度的一个量,常用的相似系数有: i)夹角余弦
记变量Xi与Xj的夹角余弦为
p
xx
i
j
cosij
1
1
n2n22
xikxjk
k1k1
1cosij1
当cosij1,说明两个样品Xi与Xj完全相似;cosij接近1,说明Xi与X
j
相似密切;cosij0,说明Xi与Xj完全不一样;cosij接近0,说明Xi与Xj差别大。可排成相似系数矩阵:
cos11
cos21 E
cosn1
cos12cos22
cosn2
cos1n
cos2n
cosnn
其中cos11cos22cosnn1。E是一个是对称阵,所以只须计算上三
角形部分或下三角形部分,根据E可对n个样品进行分类,把比较相似的样品归为一类,不怎么相似的样品对位不同的类。 ii)相关系数
通常所说相关系数,一般指变量间的相关系数,作为刻画样品间的相似关系也可类似给出定义,即第i个样品与第j个样品之间的相关系数定义为:
p
(x
i
xi)(xjxj)
rij
1rij1
p
p
i
其中 xi
1p
x x
1
j
1p
x
j
1
实际上,rij就是两个向量XiXi与XjXj的夹角余弦,其中
Xi(Xi,Xi)
'
,Xj(xj,xj)'。若将原始数据标准化,则XiXj0,这时
rijcosij
。把两两样品的相关系数都算出来,可排成样品相关系数矩阵:
r12r22rn2
r1nr2n
rnn
r11r21
R
rn1
其中r11r22rpp1,可根据R对n 个样品进行分类。 问题:相似系数也距离有什么关系。
2.对指标分类(称为R-型聚类分析)常用的距离和相似系数定义 距离与相似系数的定义与前面所讲的一样,这里不再介绍。 在实际问题中,对样品分类常用距离,对指标分类常用相似系数。
第二节 常用距离聚类方法
类与类之间用不同的方法定义距离,就产生了不同的系统聚类方法。本节介绍常用的八种系统聚类方法,即最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法、离差平方和法。系统聚类分析尽管发那个发很多,当归类的步骤基本上是一样的,所不同的仅是类与类之间的距离用不同的定义方法,从而得到不同的计算距离攻势。这些公式在形式上不大一样,但最后可将它们统一为一个公式,对上机计算带来很大的方便,详见后。
以下用dij表示样品Xi与Xj之间的距离,用Dij表示类Gi与Gj之间的距离。 1.1最短距离法(或单连接)
定义类Gi与Gj之间的距离为两类最近样品的距离,即
Dij
XiGi,XjGj
min
dij
设类Gp与Gq合并成一个新类记为Gr,则任一类Gk与Gr的距离是:
Dij
XiGi,XjGj
min
dijmin
XiGk,XjGp
min
dij,
XiGk,XjGq
min
dijminDkp,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)
如下:
(2)找出D(0)中非对角线最小元素是1,即D12d12,则将G1与G2并成一个新类,记为G6X1,X2。
(3)计算新类G6与其它类的距离,按公式:
Di6
min(Di1,Di2) i=3,4,5
即将表D(0)的前两列取较小的一列得表D(1)如下
(4)找出D(1)中非对角线最小元素是1.5,则将相应的两类G3和G6合并为
G7X1,X2,X3,然后再按公式计算各类与G7的距离,即将G3,G6相应的两
行两列归并一行一列,新的行列由原来的两行(列)中较小的一个组成,计算结果得表D(2)如下:
表3
(5) 找出D(2)中非对角线最小元素是2, 则将G4和G5合并为
G8X4,X5,最后再按公式计算G7与G8的距离,即将G4,G5相应的两行两
列归并一行一列,新的行列由原来的两行(列)中较小的一个组成,计算结果得表D(3)如下:
最后将G7和G8合并成G9,上述并类过程可用下图表达。和坐标的刻度是并类的距离。
用spss操作实现可得下图
由上图看到分成两类X1,X2,X3及X4,X5比较合适,在实际问题中有时给出一个阈值T,要求类与类之间的距离小于T,因此有些样品可能归不了类。
最短距离法也可用于指标(变量)分类,分类时可以用距离,也可用相似系数。但用相似系数时应找最大的元素并类,也就是把公式DkrminDkp,Dkq中的min换成max。
由于单连接方法用聚类之间的最短连接来合并聚类,所以这种方法不能识别分离的很差的聚类。
1.2 最长距离法(或完全连接)
定义类Gi与Gj之间的距离为两类最远样品的距离,即
Dij
max
XiGi,XjGj
dij
最长距离法与最短距离法的并类步骤完全一样,也是将各样品先自成一类,然后将非对角线上最小元素对应的两类合并。设某一步将类Gp与Gq合并成一个新类记为Gr,则任一类Gk与Gr的距离是:
Dkr
XiGk,XjGr
max
dijmaxmaxdij,maxdijmaxDkp,DkqXiGk,XjGq
XiGk,XjGp
再找非对角线最小元素的两类并类,直至所有的样品全归为一类为止。 易见最长距离法与最短距离法只有两点不同:一是类与类之间的距离定义不
同;另一是计算新类与其他类的距离所用的公式不同。下面将要介绍的其他系统聚类法之间的不同点也表现在这两个方面,而并类步骤完全一样,所以下面介绍其它系统聚类方法时,主要指出这两个方面:定义和公式。
举例说明最长距离法与最短距离法的不同: 根据最长距离法由表1可得D(1):
同理再进行合并。 利用spss操作实现。
其聚类与最短距离法分类情况一致,只是并类的距离不同。
完全连接聚类方式与单连接聚类方式在许多方面都相同,但有一个重要区别:在每个阶段,聚类之间的距离(相似性)由两个聚类中相聚最远的两个元素之间的距离确定。这样,完全连接就能保证:对一个聚类中的所有项目,彼此间的距离均不超过某个最大距离(或最小相似性)。
1.3中间距离法
定义类与类之间的距离既不采用两类之间最短距离,也不采用两类之间最远的距离,而是采用介于两者之间的距离,故称中间距离法。
如果在某一步将类Gp与Gq合并成一个新类记为Gr,则任一类Gk与Gr的距离公式是:
Dkr
2
12
Dkp14
2
12
DkqDpq
2
2
14
0
当
时,由初等几何知Dkr就是上面三角形的中线。
由于距离公式中的量都是距离的平方,为了上机计算上的方便,可将表D(0)、
D(1)、D(2)、、、中元素都用相应元素的平方代替而得表D(0)
2
,D(21),D(22)、、、
将例1用中间距离法,取
14
。
(1) 将每个样品看做自成一类,由表D(0)可得D(20)
其它归类与最短距离法归类相同。 利用spss操作实现。
不难看出此据类图的形状与前面两种聚类图一致,只是并类距离不同。而且可以发现中间距离法的并类距离大致处于它们的中间。
1.4重心法
定义类与类之间距离时,为了体现出每类包含的样品个数给出重心法。 重心法定义两类之间的距离就是两类重心之间的距离。设Gp与Gq的重心(即该类样品的均值)分别是Xp和Xq,则Gp与Gq之间的距离时DpqdXpXq。
设聚类到某一步,Gp与Gq分别有样品np,nq个,将类Gp与Gq合并成一个新类记为Gr,则Gr内样品个数为nrnpnq,它的重心是
Xr
1nr
(npX
nqXq),某一类Gk的重心是Xk
p
,它与新类Gr的距离为:
DkrdX
22
kXr
(XkXr)(XkXr)
1
nqXq)Xk(npX
nr
T
p
T
T
1Xk(npX
nr
XkXk21nr
2T
pp
nqXq)
npnrX
p
XkX
2
Tp
nqnr
XkXq
2
T
T
(npX
2Tp
2npnqXXqnqXqXq)
利用XkTXk
1nr
(npXkXknqXkXk)代入上式得
TT
Dkrnpnqnnpnr
2r
2
npnr
(XkXk2XkX
T
T
TT
p
XpXp)
T
T
nqnr
(XkXk2XkXqXqXq)
TTT
(XpX
2
p
2XpXqXqXq)Dkq
2
Dkp
nqnr
npnqnr
2
Dpq
2
重心法的归类步骤与以上三种方法基本一样,所不同的是每合并一次类,就要重新计算新类的重心及各类与新类的距离。 1.5类平均法
重心法虽有很好的代表性,但并未充分利用各样品的信息,因此给出类平均
法,它定义两类之间的距离平方为这两类元素两两之间距离平方的平均,即
Dpq
2
1npnq
dij
2
XiGpXjGq
设聚类到某一步将类Gp与Gq合并成一个新类记为Gr,则任一类Gk与Gr的距离公式是:
Dkrnpnr
2
1nknrD
2kp
nqnr
D
2kq
dij
2
1nknr
(
dij
2
dij)
2
XiGkXjGrXiGkXjGpXiGkXjGq
类平均法的聚类步骤与上述方法完全类似,就不详述了。 1.6可变类平均法
由于类平均法公式中没有反映Gp与Gq之间距离Gpq的影响,所以给出可变类平均法,此法定义两类之间的距离同上,只是将任一类Gk与新类Gr的距离改为如下形式:
2kr
D
npnr
(1)D
2kp
nqnr
(1)DkqDpq
22
其中是可变的且1。 1.7可变法
此法定义两类之间的距离仍同上,而任一类Gk与新类Gr的距离公式为:
Dkr
2
12
(1)(DkpDkq)Dpq
222
其中是可变的且1。
显然在可变类平均法中取
npnr
nqnr
12
,即为上式。
可变类平均法与可变法的分类效果与的选择关系极大,如果接近1,一般分类效果不好,在实际应用中常取负值。一般的可选1.8离差平方和法
这个方法是Ward提出来的,故又称为Ward法。
设将n个样品分成k类:G1,G2,、、、,Gk,用Xi(t)表示Gt中的第i个样品(Xi(t)是p维向量),nt表示Gt中的样品个数,X(t)是Gt的重心,则Gt中样品的离差平方和为:
nt
T
(t)
i
14
。
St
(X
i1
X
(t)
)(Xi
(t)
X
(t)
)
K个类的类内离差平方和为
k
k
t
nt
(t)i
T
S
S
t1
(X
t1i1
X
(t)
)(Xi
(t)
X
(t)
)
Ward法的基本思想是来自于方差分析,如果分类正确,同类样品的离差平方和应当较小,类与类的离差平方和应当较大。具体做法是先将n个样品各自成一类,然后每次缩小一类,每缩小一类离差平方和就要增大,选择使S增加最小的两类合并(因为如果分类正确,同类样品的离差平方和应当较小)直到所有的样品归为一类为止。
粗看Ward法与前七种方法有较大的差异,但是如果将Gp与Gq的距离定义为
DpqSrSpSq
2
其中GrGpGq,就可使Ward法与前七种系统聚类方法统一起来,且可以证明Ward法合并类的距离公式为:
D
2kr
npnknrnk
D
2kp
nqnknrnk
D
2kq
nknrnk
Dpq
2
对例1用Ward法分类。
(1) 将五个样品各自分成一类,显然这时类内离差平方和S0。 (2) 将一切可能的任意两列合并,计算所增加的离差平方和,取其中较
小的S所对应的类合并,例如将G1{x1}、G2{x2}合并成一类,它的离差平方和S(11.5)2(21.5)20.5,如果将G1{x1}、
G3{x3}合并,它的离差平方和S(12.25)(3.52.25)3.125,
2
2
将一切可能的两类合并的离差平方和都算出,列表如下:
表中非对角线最小元素是0.5,说明将G1、G2合并为G6增加的S最少,计
2
算G6与其它类的距离得D(1)表如下:
其中Dk26
nkn1nkn6
Dk1
2
nkn2nkn6
Dk2
2
nknkn6
D12
2
k3,4,5
这里n1n2n3n4n51,n62
上表非对角线最小元素是2,将G4、G5合并为G7,计算G7与其它类的距离得D(22)表如下:
其中Dk27
nkn4nkn7
Dk4
2
nkn5nkn7
Dk5
2
nknkn7
D45 k3,6
2
这里n3n4n51,n6n72
上表非对角线最小元素是2.667,将G3、G6合并为
G8,计算G8与G7的距离得D(23)表如下:
D78
2
n7n8n8n7
45
D73
2
n7n6n8n7
25
D76
2
n7n8n7
D36
2
其中
35
13.542.252.66740.83
最后将G7、G8合并为G9,将全部分类过程列表如下:
用增加最小的离差平方和代替合并的平方距离也可画出聚类图如下:
上面介绍了八种系统聚类方法,这些方法聚类的步骤是完全一样的,所不同的是类与类之间的距离有不同的定义法。依次所给出的新类与任一类的距离公式不同。但这些公式在1967年由兰斯(Lance)和威廉姆斯(Williams)统一起来。当采用欧氏距离时,八种方法有统一形式的递推公式:
DkrpDkpqDkqDpqDkpDkq
如果不采用欧氏距离时,除重心法、中间距离法、离差平方和法之外,统一形式的递推公式仍成了。上式中参数p,q,,对不同的方法有不同的取值。表8列出上式八种方法中参数的取值。八种方法公式的统一,对于编制程序提供了很大的方便。
对指标进行分类时,常用的是相似系数,统一记为Cij(如夹角余弦,相关系数等)。若用相关系数时应找最大的元素并类,也可将相关系数转化为距离,以便维持距离越小则关系越密切的含义,例如可取dij1Cij或者dij21Cij2。
表13
222222
上式例1给出的数字例子,用八种系统聚类法并类的结果是一致的,只是并类的距离不同。然而在一般情况下,用不同的方法聚类的结果是不会完全一致的。自然会问那一种方法好呢?这就需要提出一个标准作为衡量的依据,但至今还没有一个合适的标准。各种方法的比较目前仍是值得研究的一个课题,在实际应用中,一般采用以下两种处理方法:
一种方法是根据分类问题本身的专业知识结合实际需要来选择分类方法,并确定分类个数。另一种方法是多用几种分类方法去作,把结果中的共性取出来,如果用几种方法的某些结果都一样,则说明这样的聚类却是反映了食物的本质,而将有争议的样品暂放一边或用其他方法如判别分析去归类。
第三节 系统聚类法的基本性质
1单调性
设Dk是系统聚类法中第k次并类时的距离,如果D1D2,则称并类距离具有单调性。可以证明最短距离法、最长距离法、类平均法、离差平方和法、
可变法、可变平均法都具有单调性,只有重心法和中间距离法不具有单调性。 有单调性画出的据类图符合系统聚类的思想,先结合的泪关系较近,后结合的类关系较远。
2空间的浓缩或扩张
设两个同阶矩阵D(A)和D(B),如果D(A)的每一个元素不小于D(B)相应的元素,则记为D(A)D(B)。特别地如果矩阵D的元素是非负的,则有D0。(提醒,此处D0的含义与非负定阵的含义不同,这个记号仅在本章使用)
如果D(A)0,D(B)0,D2(A)表示将D(A)的每个元素平方,则
D(A)D(B)D(A)D(B)。
2
2
令D(A,B)D2(A)D2(B)
则D(A,B)0D2(A)D2(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使空间浓缩。由例1可知最短距离法比最长距离法浓缩。
今用短、长、重、平、变平、可变、离,表示八种方法,它们的平方距离记为D2(短)、D2(长)、、、、。然后以类平均法为基准,其它方法都与它比较,则不难得出:
(1)D(短,平)0
(2)D(长,平)0
(3)D(重,平)0
0,0(4)D(变平,平)
0,10
(5)D(离,平)0
(6)中间距离法与类平均法的比较没有统一的结论,它可能0,也可能0。 一般作聚类图时横坐标(并类距离)的范围太小时对区别类的灵敏度就差些,也就是说太浓缩的方法不够灵敏,但太扩张的方法对分类不利。和类平均法相比最短距离法、重心法使空间浓缩。最长距离法、可变类平均法、离差平方和法使空间扩散,而类平均法比较适中,与其它方法相比,既不太浓缩也不太扩张。
3.附注 1选代表性指标
用聚类方法分类完之后,如果各类中指标较多,又不想把类分得太多,这时要想从每一类中选一个代表性指标该怎么办?一个简单的方法是计算每类中相关指数的平均值R2,取其中较大者对应的指数作为该类的代表性指标。
计算公式:
r
Ri
2
ji
2ij
k1
i,j1,,k
2
其中k为某一类中变量的个数,rij为该类内变量xi对类中其它变量的相关系
数的平均值。
2在5.1节中,曾提到聚类分析的内容是很丰富的,本章只介绍国内外常用的八种系统聚类法,除此之外还有有无样品聚类法、模糊聚类法、动态聚类法等。下面介绍使用这些方法所能解决的是那类问题。
系统聚类法,被分类的样品是相互独立的,分类时彼此是平等的。有序样品分类法要求样品按一定的顺序排列的,分类时是不能打乱次序的,即同一类样品必须是相互邻接的。比如要将建国以来国民收入的情况划分为几个阶段,此阶段的划分必须依年份的顺序为依据。
有序样品的分类实质上是找一些分点,将有序样品划分为几个分段,每个分段看做一个类,所以分类也称为分割。显然分点取在不同的位置就可以得到不同的分割。通常寻找最好分割的一个依据是使各段内部样品之间的差异最小,而各段样品之间的差异较大。有序样品聚类法就是研究这种最优分割法。
模糊聚类法是将模糊集的概念用到聚类分析中所产生的一种聚类方法,它是根据研究对象本身的属性而构造一个模糊矩阵,在此基础上根据一定隶属度来确定其分类关系。
动态聚类法又称逐步聚类法,它是先粗糙的进行分类,然后再逐步调整,直到满意为止。整个聚类过程如下图:
当项目不能由有意义的p维亮度来表示时,常根据某些特征的存在与否将各项目对进行比较。相似项目比不相似项目有更多的共同特征。一个特征是否存在,可以从数学上引进一个二值变量来表示,当特征存在时令这个变量取值1,特征不存在时则令它取值0.举例说,对于有p=5个二值变量的情形,两个项目i与k
设
xij
为第j个二值变量在第i个项目上的得分(1或0),
xkj
为第j个二
2,1,p.因此 值变量在第k个项目上的得分(1或0),j,
(xijxkj)2
p
01
若xijxkj1或xijxkj0
若xijxkj
(12—6)
故欧氏距离平方(xijxkj)2为错配的个数。大距离对应有许多错配的情形,
j1
也就是说与相异项目相对应。对前面所举的例子,项目i与k之间的距离平方为
5
(xijxkj)2(11)2(01)2(00)2(11)2(10)22
j1
虽然基于式(12—6)的距离可用来量度相似性,它却为1—1
配对和0—0
配对提供相同的权。然而在某些情形下,1—1配对是比0—0配对更强的相似性指标。例如,在人的分组中,两个人都能阅读古希腊文同两人都没有这种能力相比是一种更强的相似性证据。因此,将0—0配对降权甚至完全不予考虑,也许是一种合理的做法。为允许对1—1配对和0—
0配对有不同处理,曾提出过几种定义相似性系数的方案。
问了引进这些方案,让我们将项目i和k的配对与错配的频数以列联
义之后附有对该定义基本依据的简单说明。
K均值法
麦奎因(MacQueen)将他所提出的一种算法命名为K均值法。这种算法的基本思想是将每一个项目分给具有最近中心(均值)的聚类。最简单形式中的算法包括一下三个步骤:
1. 将所有项目分成K个初始聚类。
2. 将项目表中的某个项目划入中心离他最近的聚类。(这里的距离通常是用标准化或非标准化数据算出的欧氏距离)对得到项目和失去项目的两个聚类重新计算它们的中心坐标。
3. 重复步骤2,直至所有的点都不能再分配时为止。
在上述过程中,步骤1也可以不从分割出K个初始聚类,而从规定K个初始中心(种子点)开始,然后进入步骤2.
最终的分类结果在,偶中程度上依赖于初始分组或初始种子点的选择。经验显示,聚类过程中的绝大多数重要变化均发生在第一次再分配中。
例题:假定我们对A,B,C,D四个项目分别测量两个变量x1和x2,得到如下数据
我们的目标是将这些项目分成K=2个聚类,使每个聚类内部的项目之间的距离比与分别属于不同项目之间的距离小。为了实施K=2均值法,我们将这些项目先随意分成两个聚类,比如说(AB)和(CD),然后计算这两个聚类的中心(均值)的坐标(1,2)。这样,在步骤1中我们有:
在第二步中,我们计算每一项到组中心的欧氏距离,并将其重新归入最近的组,如果某一项从原来的结构中移动了,则类中心必须更新。中心的第i个坐标,
i1,,p,可用以下公式更新:
ni
w
i,
n
e
xj
n1
i
, 若第j项加入到组i,
i,
n
e
ni
w
xj
n1
i, 若第j项从组i中移除
其中n是旧组中项目的数目,其中心为。 (1,,p)
考虑初始类(AB)和(CD)。中心坐标分别为(2,2)和(-1,-2)。假设项目A被移到组(CD)中,则新的组为(B)和(ACD),更新的中心为:
组(B) 1,new组(ACD) 1,new
225212(1)5
21
1 2,new1 2,new
223
1 即B的坐标 21
2(2)30.33
21
回到步骤1中的初始分组,我们计算距离平方
d(A,(AB))(52)(32)10d(A,(CD))(51)(32)61
2
2
2
2
2
2
若A不移动
d(A,(B))(51)(31)40d(A,(CD))(51)(30.33)27.09
2
2
2
2
2
2
若A移动到组(CD)
由于A到组(AB)中心的距离小于到组(ACD)中心的距离,因此A不更换组。
我们继续考虑B是否更滑组的问题,我们有:
d(B,(AB))d(B,(CD))
22
(((
2
22
12)11)
2
22
(1(1(1
2
若B不移动
2)3)
940
2)10
d(B,(A))
2
2
15)(
2
若B移动到组(CD)
(1
1)
4
d(B,(BCD))11)
由于B到组(BCD)中心的距离小于到组(AB)中心的距离,因此B更换到组(CD)。于是我们得到类(A)和(BCD),中心分别是(5,3)和(-1,-1)。
我们考虑C的更换问题。(在新的分类(A)和(BCD)下)
d(C,(A))(15)(23)41d(C,(BCD))(11)(21)5
2
2
2
222
若C不移动
d(C,(AC))(13)(20.5)10.25d(C,(BD))(12)(20.5)11.25
2
2
2
222
若C移动到组(A)
由于C到组(BCD)中心的距离小于到组(AC)中心的距离,因此C不移动。如此继续,我们发现:没有更换再发生,最终的K=2类为(A)和(BCD)。
对最终的两类,我们有
A
(BCD)
0 52
40 4
41 5
89 5
组内平方和(到中心的距离平方和)为
类(A): 0 类(BCD): 4+5+5=14 等价地,我们可以用准则 miEn
d
2
i,
c(
i)
确定K=2个类,其中最小化是对所有K=2个类的聚类,di2,c(i)是从项目i到期所在类的中心的距离平方。
在此例中,总共有7个可能的K=2个类的聚类: A,(BCD) B,(ACD) C,(ABD) D,(ABC) (AB),(CD) (AC),(BD) (AD),(BC) 对于聚类{A,(BCD)}:
2
A: dA0 ,c(A)
222 (BCD): dBdC,c(C)dD,c(D)45514 ,c(B)
因此di2,c(i)01414。
为检查聚类结果的稳定性,应该以新的初始分割重新启动算法。一旦聚类被确定,就可通过对项目表中诸项目的重新排列来对聚类作直观解释:使处于第一个聚类中的项目排在最前面,处于第二个聚类中的项目排在下一个位置,等等。一份列有各聚类中心坐标和每个聚类内部方差的表同样有助于刻画组与组之间的差别。
对k均值法的最后评注:
1. 若两个或更多个种子点碰巧处于同一聚类之中,所得到的最终聚类会难以区分。
2. 当存在某个离群值时,至少会产生一个所含项目非常分散的聚类。 3. 即使知道总体由k个组组成,抽样过程也有可能长生这样的结果:来自最稀疏的那一组的数据未出现在样本之中。这种情况下,强行将数据分成k组会造成某些毫无意义的聚类。
例题:为了更深入了叫我国人口的文化程度状况,现利用1990年全国人口普查数据对全国30个省市进行了聚类分析,现分析选用了三个指标:(1)大学以上文化程度的人口占全国比例(DXBZ),(2)初中以上文化程度的人口占全国比例(CZBZ);(3)文盲半文盲人口占全国比例(WMBZ)、分别反映较高、中等、较低文化程度人口的状况,原始数据如下表: