1
聚类分析
2
例 对 10位应聘者做智能检验。 3项指标 X,Y
和 Z分别表示数学推理能力，空间想象能力和语言理解能力。其得分如下，选择合适的统计方法对应聘者进行分类。
应聘者 1 2 3 4 5 6 7 8 9 10
X 28 18 11 21 26 20 16 14 24 22
Y 29 23 22 23 29 23 22 23 29 27
Z 28 18 16 22 26 22 22 24 24 24
§ 1 什么是聚类分析
3
4
我们直观地来看，这个分类是否合理？
计算 4号和 6号得分的离差平方和：
(21-20)2+(23-23)2+(22-22)2=1
计算 1号和 2号得分的离差平方和：
(28-18)2+(29-23)2+(28-18)2=236
计算 1号和 3号得分的离差平方和为 482，由此可见一般，分类可能是合理的，欧氏距离很大的应聘者没有被聚在一起。
由此，我们的问题是如何来选择样品间相似的测度指标，如何将有相似性的类连接起来？
5
聚类分析根据一批样品的许多观测指标,按照一定的数学公式具体地计算一些样品或一些参数 (指标 )的相似程度,
把相似的样品或指标归为一类 。
思考：样本点之间按什么刻画相似程度思考：样本点和小类之间按什么刻画相似程度思考：小类与小类之间按什么刻画相似程度
6
一,变量测量尺度的类型为了将样本进行分类,就需要研究样品之间的关系；而为了将变量进行分类,就需要研究变量之间的关系 。 但无论是样品之间的关系,还是变量之间的关系,都是用变量来描述的,变量的类型不同,
描述方法也就不同 。 通常,变量按照测量它们的尺度不同,可以分为三类 。
(1)间隔尺度 。 指标度量时用数量来表示,其数值由测量或计数,统计得到,如长度,重量,收入,
支出等 。 一般来说,计数得到的数量是离散数量,
测量得到的数量是连续数量 。 在间隔尺度中如果存在绝对零点,又称比例尺度 。
§ 2 相似系数和距离
7
(2)顺序尺度 。 指标度量时没有明确的数量表示,只有次序关系,或虽用数量表示,但相邻两数值之间的差距并不相等,它只表示一个有序状态序列 。 如评价酒的味道,
分成好,中,次三等,三等有次序关系,但没有数量表示 。
(3)名义尺度 。 指标度量时既没有数量表示也没有次序关系,只有一些特性状态,如眼睛的颜色,化学中催化剂的种类等 。 在名义尺度中只取两种特性状态的变量是很重要的,如电路的开和关,天气的有雨和无雨,人口性别的男和女,医疗诊断中的,十,和,一,,市场交易中的买和卖等都是此类变量 。
8
二,数据的变换处理所谓数据变换，就是将原始数据矩阵中的每个元素，
按照某种特定的运算把它变成为一个新值，而且数值的变化不依赖于原始数据集合中其它数据的新值。
1,中心化变换中心化变换是一种坐标轴平移处理方法,它是先求出每个变量的样本平均值,再从原始数据中减去该变量的均值,就得到中心化变换后的数据 。
设原始观测数据矩阵为：
npnn
p
p
xxx
xxx
xxx
21
22221
11211
X
9
jijij xxx* ),,3,2,1;,,3,2,1( pjni
中心化变换的结果是使每列数据之和均为 0,即每个变量的均值为 0,而且每列数据的平方和是该列变量样本方差的 (n—1)倍,任何不同两列数据之交叉乘积是这两列变量样本协方差的 (n—1)倍,所以这是一种很方便地计算方差与协方差的变换 。
),,3,2,1(1
1
pjxnx
n
i
ijj
10
2,极差规格化变换规格化变换是从数据矩阵的每一个变量中找出其最大值和最小值,这两者之差称为极差,然后从每个变量的每个原始数据中减去该变量中的最小值,再除以极差,就得到规格化数据 。 即有：
j
ni
ijij
ij R
xx
x,,2,1*
)m i n (
),,3,2,1;,,3,2,1( pjni
ni
ijijnij xxR
,,2,1,,2,1
)m in ()(m a x
10 * ijx
11
经过规格化变换后,数据矩阵中每列即每个变量的最大数值为 1,最小数值为 0,其余数据取值均在 0－ 1之间；
并且变换后的数据都不再具有量纲,便于不同的变量之间的比较 。
3,标准化变换标准化变换也是对变量的数值和量纲进行类似于规格化变换的一种数据处理方法 。 首先对每个变量进行中心化变换,然后用该变量的标准差进行标准化 。 即有：
j
jij
ij S
xxx* ),,3,2,1;,,3,2,1( pjni
n
i jijj
xxnS
1
2)(
1
1
12
经过标准化变换处理后,每个变量即数据矩阵中每列数据的平均值为 0,方差为 1,且也不再具有量纲,同样也便于不同变量之间的比较 。 变换后,数据短阵中任何两列数据乘积之和是两个变量相关系数的 （ n－ 1） 倍,所以这是一种很方便地计算相关矩阵的变换 。
4,对数变换对数变换是将各个原始数据取对数,将原始数据的对数值作为变换后的新值 。 即：
)l o g (* ijij xx?
13
三、样品间亲疏程度的测度研究样品或变量的亲疏程度的数量指标有两种,一种叫 相似系数,性质越接近的变量或样品,它们的相似系数越接近于 1或一 l,而彼此无关的变量或样品它们的相似系数则越接近于 0,相似的为一类,不相似的为不同类；另一种叫 距离,它是将每一个样品看作 p维空间的一个点,并用某种度量测量点与点之间的距离,距离较近的归为一类,距离较远的点应属于不同的类 。
14
变量之间的聚类即 R型聚类分析,常用相似系数来测度变量之间的亲疏程度 。 而样品之间的聚类即 Q型聚类分析,则常用距离来测度样品之间的亲疏程度 。
15
常用距离的算法设 和是第 i和 j 个样品的观测值，则二者之间的距离为：
gp
k
g
jkikij xxd
1
1 )||(
pk jkikij xxd 1 2)(
ipii xxx,,,21?ix ),,,( 21 jpjj xxx?jx
明氏距离特别，欧氏距离
(1) 明氏距离测度
16
明考夫斯基距离主要有以下两个缺点：
① 明氏距离的值与各指标的量纲有关,而各指标计量单位的选择有一定的人为性和随意性,各变量计量单位的不同不仅使此距离的实际意义难以说清,而且,任何一个变量计量单位的改变都会使此距离的数值改变从而使该距离的数值依赖于各变量计量单位的选择 。
② 明氏距离的定义没有考虑各个变量之间的相关性和重要性 。 实际上,明考夫斯基距离是把各个变量都同等看待,将两个样品在各个变量上的离差简单地进行了综合 。
17
(2)杰氏距离这是杰斐瑞和马突斯塔 (Jffreys & Matusita)
所定义的一种距离,其计算公式为：
211 2)()( pk jkikij xxJd
18
(3)兰氏距离这是兰思和维廉姆斯 (Lance & Williams)所给定的一种距离，其计算公式为：
p
k
jkik
jkik
ij xx
xxLd
1
)(
这是一个自身标准化的量，由于它对大的奇异值不敏感，这样使得它特别适合于高度偏倚的数据。虽然这个距离有助于克服明氏距离的第一个缺点，但它也没有考虑指标之间的相关性。
19
(4)马氏距离这是印度著名统计学家马哈拉诺比斯
(P,C,Mahalanobis)所定义的一种距离,其计算公式为：
)()(2 ji1ji xxxxijd
分别表示第 i个样品和第 j样品的 p指标观测值所组成的列向量,即样本数据矩阵中第 i个和第 j个行向量的转置,?表示观测变量之间的协方差短阵 。
在实践应用中,若总体协方差矩阵?未知,则可用样本协方差矩阵作为估计代替计算 。
20
马氏距离又称为广义欧氏距离 。 显然,马氏距离与上述各种距离的主要不同就是马氏距离考虑了观测变量之间的相关性 。 如果假定各变量之间相互独立,即观测变量的协方差矩阵是对角矩阵,则马氏距离就退化为用各个观测指标的标准差的倒数作为权数进行加权的欧氏距离 。 因此,
马氏距离不仅考虑了观测变量之间的相关性,而且也考虑到了各个观测指标取值的差异程度,。
21
(5) 斜交空间距离由于各变量之间往往存在着不同的相关关系，用正交空间的距离来计算样本间的距离易变形，所以可以采用斜交空间距离。
21
1 12
))((1?
p
h
p
k hkjkikjhihij
xxxxpd?
当各变量之间不相关时，斜交空间退化为欧氏距离。
22
2、相似系数的算法
（ 1）相似系数设 和是第 和 个样品的观测值，则二者之间的相似测度为,
ipii xxx,,,21?ix ),,,( 21 jpjj xxx?jx
i j
p
k
p
k jjkiik
p
k jjkiik
ij
xxxx
xxxx
1 1
22
1
])(][)([
))((
其中
23
（ 2）夹角余弦夹角余弦时从向量集合的角度所定义的一种测度变量之间亲疏程度的相似系数。设在 n维空间的向量
niiii xxx,,,21?x njjjj xxx,,,21?x
n
k
n
k kjki
n
k kjki
ijij
xx
xx
c
1 1
22
1co s?
22 1 ijij Cd
24
§ 3 系统聚类方法
正如样品之间的距离可以有不同的定义方法一样，类与类之间的距离也有各种定义。例如可以定义类与类之间的距离为两类之间最近样品的距离，或者定义为两类之间最远样品的距离，也可以定义为两类重心之间的距离等等。类与类之间用不同的方法定义距离，
就产生了不同的系统聚类方法。
25
一、常用的种类
1,最短距离法
qpijpq GGdM i nD ji xx,：定义距离：
qplDDM i nD qlplrl,，递推公式,
p q ij p qD M a x d G Gijxx定 义 距 离,,,
r l p l q lD M a x D D l p q递 推 公 式,,,
2,最 长距离 法
26
3、中间距离法
PG
qG
LG
rG
0412121 2222 〈〈，递推公式, pqkqkpkr DDDD
27
类平均法定义类间的距离是两类间样品的距离的平均数 。
4、类平均法
222
kq
r
q
kp
r
p
rk Dn
n
D
n
n
D递推公式：
pi qjGx Gx
ij
qp
pq dnnD
22 1
定义距离：
28
5,可变类平均法类平均法的递推公式中,没有反映 Gp类和 Gq类的距离有多大,进一步将其改进,加入 D2Pq,并给定系数?<1,则类平均法的递推公式改为：
用此递推公式进行聚类就是可变类平均法。递推公式由：
p类和 q类与 L类的距离的加权平均数
p类和 q类的距离两项的加权和构成,β 的大小根据哪项更重要而定 。
2222 ])[1(
pqkq
r
p
kp
r
p
kr DDn
n
D
n
n
D
29
6、离差平方和法类似于方差分析的想法，如果类分得恰当，同类内的样品之间的离差平方和应较小，而类间的离差平方和应当较大。
离差平方和法的思路是,当 k固定时,选择使
S达到最小的分类 。 先让 n个样品各自成一类,然后缩小一类,每缩小一类离差平方和就要增大,
选择使 S2增加最小的两类合并,直到所有的样品归为一类为止 。 离差平方和法定义类间的平方距离为
30
2222 qprpq SSSD的增量：定义距离为离差平方和其中 是由 Gp和 Gq合并成的 Gr类的类内离差平方和 。
可以证明离差平方和的聚类公式为
2rS
2222
pq
rk
k
qk
kr
qk
pk
kr
pk
rk Dnn
nD
nn
nnD
nn
nnD
递推公式：
31
7、可变方法如果让中间距离法的递推公式前两项的系数也依赖于?，
则递推公式为：
用上式作为递推公式的系统聚类法称为可变法 。
1)(21 2222 〈, pqkqkpkr DDDD
32
分别为 Gp和 Gq的重心,类与类之间的距离定义为两个类重心 （ 类内样品平均值 ） 间的平方距离 。
1 p
ip
n
pi
xGp
Xx
n?
1 q
iq
n
qi
xGq
Xx
n?
重心法，也称为样品的均值法。设 Gp和 Gq 为两个类
8,重心法
33
设某一步 Gp和 Gq的重心分别为 和,类内的样品数分别为和,如果要把 Gp和 Gq合并为 Gr类,则 Gr
类的样品数 nr=np+nq,Gr类的重心为 和 的加权算术平均数：
pXqX
qp
qqpp
r nn
XnXnX
pX qX
34
假设第 p类和第 q类合并成第类，第 r类与其它各旧类的距离按重心法为：
()
11
i p q i l
rl r l i i
x G G x Gp q l
D x x
n n n
xx
2 2 2
2
p q p q
p l q l p q
r r r
n n n nD D D
n n n
35
二、确定类的个数在聚类分析过程中类的个数如何来确定才合适呢？ 这是一个十分困难的问题,人们至今仍未找到令人满意的方法 。 但是这个问题又是不可回避的 。 下面我们介绍几种方法 。
1,给定阈值 —— 通过观测聚类图,给出一个合适的阈值 T。
要求类与类之间的距离不要超过 T值 。 例如我们给定 T=0.35,当聚类时,类间的距离已经超过了 0.35,则聚类结束 。
36
总离差平方和的分解（准备知识）
npnn
p
p
xxx
xxx
xxx
21
22221
11211
1x 2x px
22
1
2
11
2
111
)()(
)()
pnppp
n
xxxx
xxxx
（总离差平方和
37
如果着些样品被分成两类
pnnn
p
p
xxx
xxx
xxx
222 21
22221
11211
pnnn
p
p
xxx
xxx
xxx
111 21
22221
11211
)1(1x )1(2x )1(px )2(1x )2(2x )2(px
2)1(2)1(
1
21
11
21
111
)()(
)()
1
1
ppnpp
n
xxxx
xxxx
）（）（（一组的离差平方和
2)2(2)2(
1
22
11
22
111
)()(
)()
2
2
ppnpp
n
xxxx
xxxx
）（）（（二组的离差平方和
38
可以证明：
总离差平方和
＝组内离差平方和＋组间离差平方和令 T为总离差平方和令 PG为分为 G类的组内离差平方和。
39
2,统计量其中 T是数据的总离差平方和,是组内离差平方和。
比较大，说明分 G个类时类内的离差平方和比较小，
也就是说分 G类是合适的。但是，分类越多，每个类的类内的离差平方和就越小,也就越大；所以我们只能取合适的 G，使得 足够大，而 G本身很小，随着 G的增加,的增幅不大。比如，假定分 4类时，
=0.8； 下一次合并分 3类时,下降了许多,=0.32，
则分 4 类是合适的。
T
PR G 12
GP
2R
2R
2R
2R
2R
2R
40
3,伪 F统计量的定义为伪 F统计量用于评价聚为 G类的效果 。 如果聚类的效果好,类间的离差平方和相对于类内的离差平方和大,所以应该取伪 F统计量较大而类数较小的聚类水平 。
)(
)1()(
GnP
GPTF
G
G
41
Pseudo F Statistic
0
10
20
30
40
50
60
70
80
90
100
110
120
Number of Clusters
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
42
4,伪 统计量的定义为其中 和 分别是的类内离差平方和,
是将 K和 L合并为第 M类的离差平方和
= - -
为合并导致的类内离差平方和的增量 。 用它评价合并第 K和 L类的效果,伪 统计量大说明不应该合并这两类,应该取合并前的水平 。
2t
)2()(
2
LKLK
KL
NNWW
Bt
KW
LWKLB KWMW
LW
2t
43
三,系统聚类法的基本性质
（ 一 ） 单调性在聚类分析过程中,并类距离分别为 l k（ k=1,2，
3,…? ） 若满足,则称该聚类方法具有单调性 。 可以证明除了重心法和中间距离法之外,
其他的系统聚类法均满足单调性的条件 。
121 kk llll
（二）空间的浓缩和扩张
1,定义矩阵的大小设同阶矩阵 D（ A） 和 D（ B）,如果 D（ A） 的每一个元素不小于 D（ B） 的每一个元素,则记为 。 )()( BDAD?
44
2,空间的浓缩和扩张设有两种系统聚类法 A和 B,他们在第 i步的距离矩阵分别为 Ai和 Bi（ I=1,2,3… ）,若 Ai>Bi,
则称第一种方法 A比第二种方法 B使空间扩张,或第二种方法比第一种方法浓缩 。
3,方法的比较
D（ 短 ） D（ 平 ）,D（ 重 ） D（ 平 ） ；
D（ 长 ） D（ 平 ） ；
当,D（ 变平 ） D（ 平 ） ；
当,D（ 变平 ） D（ 平 ） 。
100
45
五、主要的步骤
1、选择变量
（ 1）和聚类分析的目的密切相关
（ 2）反映要分类变量的特征
（ 3）在不同研究对象上的值有明显的差异
（ 4）变量之间不能高度相关
2、计算相似性相似性是聚类分析中的基本概念，他反映了研究对象之间的亲疏程度，聚类分析就是根据对象之间的相似性来分类的。有很多刻画相似性的测度
46
3、聚类选定了聚类的变量，计算出样品或指标之间的相似程度后，构成了一个相似程度的矩阵。这时主要涉及两个问题：
（ 1）选择聚类的方法
（ 2）确定形成的类数
47
4、聚类结果的解释和证实
对聚类结果进行解释是希望对各个类的特征进行准确的描述，给每类起一个合适的名称。这一步可以借助各种描述性统计量进行分析，通常的做法是计算各类在各聚类变量上的均值，对均值进行比较，还可以解释各类产别的原因。
48
例 某公司下属 30个企业,公司为了考核下属企业的经济效益,设计了 8个指标 。 为了避免重复,需要对这 8个指标进行筛选,建立一个恰当的经济效益指标体系 。 通过计算 30
个企业 8个指标的相关系数距离,数据是 1-r2。 得如下表,
x1 x2 x3 x4 x5 x6 x7 x8
x1 0
0.60 0
0.43 0.46 0
0.47 0.45 0.12 0
0.57 0.45 0.23 0.22 0
0.38 0.40 0.21 0.29 0.22 0
0.31 0.79 0.65 0.70 0.80 0.66 0
0.45 0.45 0.27 0.23 0.14 0.19 0.77 0
试用将它们聚类 。
x2
x3
x4
x5
x6
x7
x8
49
50
根据美国等 20个国家和地区的信息基础设施的发展状况进行分类 。
Call— 每千人拥有的电话线数；
move l— 每千人户居民拥有的蜂窝移动电话数；
fee— 高峰时期每三分钟国际电话的成本；
comp— 每千人拥有的计算机数；
mips— 每千人计算机功率 （ 每秒百万指令 ） ；
net— 每千人互联网络户主数。
51
国家 call movel fee comp mips net
meiguo 631.6 161.9 0.36 403 26073 35.34
riben 498.4 143.2 3.57 176 10223 6.26
deguo 557.6 70.60 2.18 199 11571 9.84
ruidian 684.1 281.8 1.4 246 16660 29.39
ruishi 644 93.5 1.98 234 13621 22.68
xinjiapo 498.4 147.5 2.5 284 13578 13.49
taiwan 469.4 56.1 3.68 119 6911 1.72
hanguo 434.5 73 3.36 99 5795 1.66
baxi 81.9 16.3 3.02 19 876 0.52
zhili 138.6 8.20 1.4 31 1411 1.28
moxige 92.2 9.8 2.61 31 1751 0.35
eluosi 174.9 5 5.12 24 1101 0.48
bolan 169 6.5 3.68 40 1796 1.45
xiongyali 262.2 49.4 2.66 68 3067 3.09
malaixiya 195.5 88.4 4.19 53 2734 1.25
taiguo 78.6 27.8 4.95 22 1662 0.11
yindu 13.6 0.30 6.28 2 101 0.01
faguo 559.1 42.9 1.27 201 11702 4.76
yingguo 521.10 122.5 0.98 248 14461 11.91
52
53
Pseudo F Statistic
0
10
20
30
40
50
60
70
80
90
100
110
120
Number of Clusters
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
54
§ 4 动态聚类一,思想系统聚类法是一种比较成功的聚类方法 。 然而当样本点数量十分庞大时,则是一件非常繁重的工作,
且聚类的计算速度也比较慢 。 比如在市场抽样调查中,有 4万人就其对衣着的偏好作了回答,希望能迅速将他们分为几类 。 这时,采用系统聚类法就很困难,而动态聚类法就会显得方便,适用 。
动态聚类解决的问题是,假如有个样本点,要把它们分为类,使得每一类内的元素都是聚合的,并且类与类之间还能很好地区别开 。 动态聚类使用于大型数据 。
55
选择凝聚点分类修改分类分类是否合理分类结束
Yes
No
56
用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。 快速聚类的步骤：
1、随机选取两个点 和 作为聚核。
2、对于任何点,分别计算
3、若,则将 划为第一类，否则划给第二类。于是得图（ b）的两个类。
)1(1x )1(2x
kx ),(),(
)1(
2
)1(
1 xxdxxd kk 和
),(),( )1(2)1(1 xxdxxd kk?kx
4,分别计算两个类的重心,则得 和,以其为新的聚核,对空间中的点进行重新分类,得到新分类 。
)2(1x )2(2x
57
（ a） 空间的群点 (b) 任取两个聚核
(c) 第一次分类 (d) 求各类中心
58
(e) 第二次分类
59
二、选择凝聚点和确定初始分类凝聚点就是一批有代表性的点，是欲形成类的中心。凝聚点的 选择直接决定初始分类，对分类结果也有很大的影响，由于凝聚点 的不同选择，其最终分类结果也将出现不同。故选择时要慎重．通 常选择凝聚点的方法有：
(1) 人为选择，当人们对所欲分类的问题有一定了解时，根据经验，预先确定分类个数和初始分类，并从每一类中选择一个有代表性的样品作为凝聚点。
(2) 将数据人为地分为 A类，计算每一类的重心，
就将这些重心作为凝聚点。
60
(3) 用密度法选择凝聚点。以某个正数 d为半径，
以每个样品为球心，落在这个球内的样品数 (不包括作为球心的样品 )就叫做这个样品的密度。计算所有样品点的密度后，首先选择密度最大的样品作为第一凝聚点，并且人为地确定一个正数 D(一般 D＞ d，常取 D＝ 2d)。然后选出次大密度的样品点，若它与第一个凝 聚点的距离大于 D，则将其作为第二个凝聚点；否则舍去这点，再选密度次于它的样品。这样，按密度大小依次考查，直至全部样品考查完毕为止．此方法中,d要给的合适，
太大了使凝聚点个数太 少，太小了使凝聚点个数太多。
61
(5) 随机地选择，如果对样品的性质毫无所知，可采用随机数表来选择，打算分几类就选几个凝聚点。
或者就用前 A个样品作为凝聚点 (假设分 A类 )。这方法一般不提倡使用。
(4) 人为地选择一正数 d，首先以所有样品的均值作为第一凝聚点。然后依次考察每个样品，若某样品与已选定的凝聚点的距 离均大于 d，该样品作为新的凝聚点，否则考察下一个样品。
62
四,动态聚类步骤为：
第一,选择若干个观测值点为,凝聚点,；
第二,可选择地,通过分配每个,凝聚点,最近的类里来形成临时分类 。 每一次对一个观测值点进行归类,,凝聚点,更新为这一类目前的均值；
63
第三，可选择地，通过分配每个“凝聚点”
最近的类里来形成临时分类。所有的观测值点分配完后，这些类的“凝聚点”用临时类的均值代替。该步骤可以一直进行直到“凝聚点”的改变很小或为零时止；
第四，最终的分类有分配每一个观测到最近的“凝聚点”而形成。
64
§ 5 有序样本聚类法前面介绍的聚类方法与样品的顺序无关，但在有些实际问题中样品是有顺序的，样品按一定的要求排成序，分类不能打乱顺序．例如在地质勘探中通过钻井的岩心样品欲将地层分类，此时岩心样品是由浅到深的顺序取的．又如气象资料它是按时间排列的，其样品也是有序的。
65
系统聚类开始 n个样品各自自成一类，然后逐步并类，直至所有的样品被聚为一类为止。而有序聚类则相反，开始所有的样品为一类，然后分为二类、三类等，直到分成 n类。每次分类都要求产生的离差平方和的增量最小。
66
有序聚类的步骤
1、定义类的直径设某类 G中包含的样品有
)( ij ( j )1)(i( i ) x,,x,x?
该类的均值向量为
j
itij ( t )G
xX 11
设有序样品 x(1),x(2),…,x(n) 。他们可以是从小到达排列，也可以是按时间的先后排列。
67
用 D(i,j)表示这一类的直径，常用的直径有，欧氏距离：
j itjiD )X(x)Xx G(t)G(t)(),(
当是单变量的时，也可以定义直径为：
是中位数Gj it G( t ) XXxjiD ~|~|),(
68
2、定义分类的损失函数用 b(n,k)表示将 n个有序的样品分为 k类的某种分法：
1 1 1 2,1,,1G j j j
2 2 2 3,1,,1G j j j
,1,,k k kG j j n
定义这种分类法的损失函数为：各类的直径之和 。
kt tt iiDknbL 1 1 )1,(),(
69
由损失函数的构造可以看出，损失函数是各类的直径之和。如果分类不好，则各类的直径之和大，否则比较小。
当 n和 k固定时,L[b(n,k)]越小表示各类的离差平方和越小，分类是合理的。因此要寻找一种分法 b(n,k)，使分类损失函数 L[b(n,k)]达到最小。记该分法为 P[n,k]。
70
应用简例分析儿童的生长期。有如下的资料是 1-11
岁的男孩平均每年的增重：
问男孩的发育可分为几个阶段。
年龄 1 2 3 4 5 6 7 8 9 10 11
增加重量（公斤）
9.3 1.8 1.9 1.7 1.5 1.3 1.4 2.0 1.9 2.3 2.1
71
j 1 2 3 4 5 6 7 8 9 10
2 2 8,1 2 5
3 3 7,0 0 7 0,0 0 5
4 4 2,2 0 8 0,0 2 0,0 2
5 4 5,9 9 2 0,0 8 8 0,0 8 0,0 2
6 4 9,1 2 8 0,2 3 2 0,2 0,0 8 0,0 2
7 5 1,1 0,2 8 0,2 3 2 0,0 8 8 0,0 2 0,0 0 5
8 5 1,5 2 9 0,4 1 7 0,3 9 3 0,3 0 8 0,2 9 0,2 8 7 0,1 8
9 5 1,9 8 0,4 6 9 0,4 5 4 0,3 9 3 0,3 8 8 0,3 7 0,2 0 7 0,0 0 5 0 8
10 5 2,0 2 9 0,8 0 2 0,8 0,7 7 4 0,7 7 3 0,7 0 8 0,4 2 0,0 8 7 0,0 8
11 5 2,1 8 2 0,9 0 9 0,9 0 9 0,8 9 5 0,8 8 9 0,7 9 3 0,4 5 2 0,0 8 8 0,0 8 0,0 2
i
(,)D i j
72
n
k
2 3 4 5 6 7 8 9 10
3 0.005/2
4 0.02/2 0.005/4
5 0.088/2 0.020/5 0.005/5
6 0.232/2 0.040/5 0.02/6 0.005/6
7 0.280/2 0.040/5 0.025/6 0.010/6 0.005/6
8 0.417/2 0.280/8 0.040/8 0.025/8 0.010/8 0.005/8
9 0.469/2 0.285/8 0.045/8 0.030/8 0.015/8 0.010/8 0.005/8
10 0.802/2 0.367/8 0.127/8 0.045/10 0.030/10 0.015/10 0.010/10 0.005/10
11 0.909/2 0.368/8 0.128/8 0.065/10 0.045/11 0.030/11 0.015/11 0.010/11 0.005/11
最小损失函数 L[p(n,k)
73
损失函数L [ p ( n,k ) ] 随k 变化趋势图
0
0.2
0.4
0.6
0.8
1
1 2 3 4 5 6 7 8 9
类数损失函数
74
分类数 L[p (11,k )] 最优分割结果
2 0.909 1,2-11
3 0.368 1,2-7,8-11
4 0.128 1,2-4,5-7,8-11
5 0.065 1,2-4,5-7,8-9,10-11
6 0.045 1,2-4,5-7,8-9,10,11
7 0.03 1,2-3,4,5-7,8-9,10,11
8 0.015 1,2-3,4,5,6-7,8-9,10,11
9 0.01 1,2,3,4,5,6-7,8-9,10,11
10 0.005 1,2,3,4,5,6,7,8-9,10,11
聚类分析
2
例 对 10位应聘者做智能检验。 3项指标 X,Y
和 Z分别表示数学推理能力，空间想象能力和语言理解能力。其得分如下，选择合适的统计方法对应聘者进行分类。
应聘者 1 2 3 4 5 6 7 8 9 10
X 28 18 11 21 26 20 16 14 24 22
Y 29 23 22 23 29 23 22 23 29 27
Z 28 18 16 22 26 22 22 24 24 24
§ 1 什么是聚类分析
3
4
我们直观地来看，这个分类是否合理？
计算 4号和 6号得分的离差平方和：
(21-20)2+(23-23)2+(22-22)2=1
计算 1号和 2号得分的离差平方和：
(28-18)2+(29-23)2+(28-18)2=236
计算 1号和 3号得分的离差平方和为 482，由此可见一般，分类可能是合理的，欧氏距离很大的应聘者没有被聚在一起。
由此，我们的问题是如何来选择样品间相似的测度指标，如何将有相似性的类连接起来？
5
聚类分析根据一批样品的许多观测指标,按照一定的数学公式具体地计算一些样品或一些参数 (指标 )的相似程度,
把相似的样品或指标归为一类 。
思考：样本点之间按什么刻画相似程度思考：样本点和小类之间按什么刻画相似程度思考：小类与小类之间按什么刻画相似程度
6
一,变量测量尺度的类型为了将样本进行分类,就需要研究样品之间的关系；而为了将变量进行分类,就需要研究变量之间的关系 。 但无论是样品之间的关系,还是变量之间的关系,都是用变量来描述的,变量的类型不同,
描述方法也就不同 。 通常,变量按照测量它们的尺度不同,可以分为三类 。
(1)间隔尺度 。 指标度量时用数量来表示,其数值由测量或计数,统计得到,如长度,重量,收入,
支出等 。 一般来说,计数得到的数量是离散数量,
测量得到的数量是连续数量 。 在间隔尺度中如果存在绝对零点,又称比例尺度 。
§ 2 相似系数和距离
7
(2)顺序尺度 。 指标度量时没有明确的数量表示,只有次序关系,或虽用数量表示,但相邻两数值之间的差距并不相等,它只表示一个有序状态序列 。 如评价酒的味道,
分成好,中,次三等,三等有次序关系,但没有数量表示 。
(3)名义尺度 。 指标度量时既没有数量表示也没有次序关系,只有一些特性状态,如眼睛的颜色,化学中催化剂的种类等 。 在名义尺度中只取两种特性状态的变量是很重要的,如电路的开和关,天气的有雨和无雨,人口性别的男和女,医疗诊断中的,十,和,一,,市场交易中的买和卖等都是此类变量 。
8
二,数据的变换处理所谓数据变换，就是将原始数据矩阵中的每个元素，
按照某种特定的运算把它变成为一个新值，而且数值的变化不依赖于原始数据集合中其它数据的新值。
1,中心化变换中心化变换是一种坐标轴平移处理方法,它是先求出每个变量的样本平均值,再从原始数据中减去该变量的均值,就得到中心化变换后的数据 。
设原始观测数据矩阵为：
npnn
p
p
xxx
xxx
xxx
21
22221
11211
X
9
jijij xxx* ),,3,2,1;,,3,2,1( pjni
中心化变换的结果是使每列数据之和均为 0,即每个变量的均值为 0,而且每列数据的平方和是该列变量样本方差的 (n—1)倍,任何不同两列数据之交叉乘积是这两列变量样本协方差的 (n—1)倍,所以这是一种很方便地计算方差与协方差的变换 。
),,3,2,1(1
1
pjxnx
n
i
ijj
10
2,极差规格化变换规格化变换是从数据矩阵的每一个变量中找出其最大值和最小值,这两者之差称为极差,然后从每个变量的每个原始数据中减去该变量中的最小值,再除以极差,就得到规格化数据 。 即有：
j
ni
ijij
ij R
xx
x,,2,1*
)m i n (
),,3,2,1;,,3,2,1( pjni
ni
ijijnij xxR
,,2,1,,2,1
)m in ()(m a x
10 * ijx
11
经过规格化变换后,数据矩阵中每列即每个变量的最大数值为 1,最小数值为 0,其余数据取值均在 0－ 1之间；
并且变换后的数据都不再具有量纲,便于不同的变量之间的比较 。
3,标准化变换标准化变换也是对变量的数值和量纲进行类似于规格化变换的一种数据处理方法 。 首先对每个变量进行中心化变换,然后用该变量的标准差进行标准化 。 即有：
j
jij
ij S
xxx* ),,3,2,1;,,3,2,1( pjni
n
i jijj
xxnS
1
2)(
1
1
12
经过标准化变换处理后,每个变量即数据矩阵中每列数据的平均值为 0,方差为 1,且也不再具有量纲,同样也便于不同变量之间的比较 。 变换后,数据短阵中任何两列数据乘积之和是两个变量相关系数的 （ n－ 1） 倍,所以这是一种很方便地计算相关矩阵的变换 。
4,对数变换对数变换是将各个原始数据取对数,将原始数据的对数值作为变换后的新值 。 即：
)l o g (* ijij xx?
13
三、样品间亲疏程度的测度研究样品或变量的亲疏程度的数量指标有两种,一种叫 相似系数,性质越接近的变量或样品,它们的相似系数越接近于 1或一 l,而彼此无关的变量或样品它们的相似系数则越接近于 0,相似的为一类,不相似的为不同类；另一种叫 距离,它是将每一个样品看作 p维空间的一个点,并用某种度量测量点与点之间的距离,距离较近的归为一类,距离较远的点应属于不同的类 。
14
变量之间的聚类即 R型聚类分析,常用相似系数来测度变量之间的亲疏程度 。 而样品之间的聚类即 Q型聚类分析,则常用距离来测度样品之间的亲疏程度 。
15
常用距离的算法设 和是第 i和 j 个样品的观测值，则二者之间的距离为：
gp
k
g
jkikij xxd
1
1 )||(
pk jkikij xxd 1 2)(
ipii xxx,,,21?ix ),,,( 21 jpjj xxx?jx
明氏距离特别，欧氏距离
(1) 明氏距离测度
16
明考夫斯基距离主要有以下两个缺点：
① 明氏距离的值与各指标的量纲有关,而各指标计量单位的选择有一定的人为性和随意性,各变量计量单位的不同不仅使此距离的实际意义难以说清,而且,任何一个变量计量单位的改变都会使此距离的数值改变从而使该距离的数值依赖于各变量计量单位的选择 。
② 明氏距离的定义没有考虑各个变量之间的相关性和重要性 。 实际上,明考夫斯基距离是把各个变量都同等看待,将两个样品在各个变量上的离差简单地进行了综合 。
17
(2)杰氏距离这是杰斐瑞和马突斯塔 (Jffreys & Matusita)
所定义的一种距离,其计算公式为：
211 2)()( pk jkikij xxJd
18
(3)兰氏距离这是兰思和维廉姆斯 (Lance & Williams)所给定的一种距离，其计算公式为：
p
k
jkik
jkik
ij xx
xxLd
1
)(
这是一个自身标准化的量，由于它对大的奇异值不敏感，这样使得它特别适合于高度偏倚的数据。虽然这个距离有助于克服明氏距离的第一个缺点，但它也没有考虑指标之间的相关性。
19
(4)马氏距离这是印度著名统计学家马哈拉诺比斯
(P,C,Mahalanobis)所定义的一种距离,其计算公式为：
)()(2 ji1ji xxxxijd
分别表示第 i个样品和第 j样品的 p指标观测值所组成的列向量,即样本数据矩阵中第 i个和第 j个行向量的转置,?表示观测变量之间的协方差短阵 。
在实践应用中,若总体协方差矩阵?未知,则可用样本协方差矩阵作为估计代替计算 。
20
马氏距离又称为广义欧氏距离 。 显然,马氏距离与上述各种距离的主要不同就是马氏距离考虑了观测变量之间的相关性 。 如果假定各变量之间相互独立,即观测变量的协方差矩阵是对角矩阵,则马氏距离就退化为用各个观测指标的标准差的倒数作为权数进行加权的欧氏距离 。 因此,
马氏距离不仅考虑了观测变量之间的相关性,而且也考虑到了各个观测指标取值的差异程度,。
21
(5) 斜交空间距离由于各变量之间往往存在着不同的相关关系，用正交空间的距离来计算样本间的距离易变形，所以可以采用斜交空间距离。
21
1 12
))((1?
p
h
p
k hkjkikjhihij
xxxxpd?
当各变量之间不相关时，斜交空间退化为欧氏距离。
22
2、相似系数的算法
（ 1）相似系数设 和是第 和 个样品的观测值，则二者之间的相似测度为,
ipii xxx,,,21?ix ),,,( 21 jpjj xxx?jx
i j
p
k
p
k jjkiik
p
k jjkiik
ij
xxxx
xxxx
1 1
22
1
])(][)([
))((
其中
23
（ 2）夹角余弦夹角余弦时从向量集合的角度所定义的一种测度变量之间亲疏程度的相似系数。设在 n维空间的向量
niiii xxx,,,21?x njjjj xxx,,,21?x
n
k
n
k kjki
n
k kjki
ijij
xx
xx
c
1 1
22
1co s?
22 1 ijij Cd
24
§ 3 系统聚类方法
正如样品之间的距离可以有不同的定义方法一样，类与类之间的距离也有各种定义。例如可以定义类与类之间的距离为两类之间最近样品的距离，或者定义为两类之间最远样品的距离，也可以定义为两类重心之间的距离等等。类与类之间用不同的方法定义距离，
就产生了不同的系统聚类方法。
25
一、常用的种类
1,最短距离法
qpijpq GGdM i nD ji xx,：定义距离：
qplDDM i nD qlplrl,，递推公式,
p q ij p qD M a x d G Gijxx定 义 距 离,,,
r l p l q lD M a x D D l p q递 推 公 式,,,
2,最 长距离 法
26
3、中间距离法
PG
qG
LG
rG
0412121 2222 〈〈，递推公式, pqkqkpkr DDDD
27
类平均法定义类间的距离是两类间样品的距离的平均数 。
4、类平均法
222
kq
r
q
kp
r
p
rk Dn
n
D
n
n
D递推公式：
pi qjGx Gx
ij
qp
pq dnnD
22 1
定义距离：
28
5,可变类平均法类平均法的递推公式中,没有反映 Gp类和 Gq类的距离有多大,进一步将其改进,加入 D2Pq,并给定系数?<1,则类平均法的递推公式改为：
用此递推公式进行聚类就是可变类平均法。递推公式由：
p类和 q类与 L类的距离的加权平均数
p类和 q类的距离两项的加权和构成,β 的大小根据哪项更重要而定 。
2222 ])[1(
pqkq
r
p
kp
r
p
kr DDn
n
D
n
n
D
29
6、离差平方和法类似于方差分析的想法，如果类分得恰当，同类内的样品之间的离差平方和应较小，而类间的离差平方和应当较大。
离差平方和法的思路是,当 k固定时,选择使
S达到最小的分类 。 先让 n个样品各自成一类,然后缩小一类,每缩小一类离差平方和就要增大,
选择使 S2增加最小的两类合并,直到所有的样品归为一类为止 。 离差平方和法定义类间的平方距离为
30
2222 qprpq SSSD的增量：定义距离为离差平方和其中 是由 Gp和 Gq合并成的 Gr类的类内离差平方和 。
可以证明离差平方和的聚类公式为
2rS
2222
pq
rk
k
qk
kr
qk
pk
kr
pk
rk Dnn
nD
nn
nnD
nn
nnD
递推公式：
31
7、可变方法如果让中间距离法的递推公式前两项的系数也依赖于?，
则递推公式为：
用上式作为递推公式的系统聚类法称为可变法 。
1)(21 2222 〈, pqkqkpkr DDDD
32
分别为 Gp和 Gq的重心,类与类之间的距离定义为两个类重心 （ 类内样品平均值 ） 间的平方距离 。
1 p
ip
n
pi
xGp
Xx
n?
1 q
iq
n
qi
xGq
Xx
n?
重心法，也称为样品的均值法。设 Gp和 Gq 为两个类
8,重心法
33
设某一步 Gp和 Gq的重心分别为 和,类内的样品数分别为和,如果要把 Gp和 Gq合并为 Gr类,则 Gr
类的样品数 nr=np+nq,Gr类的重心为 和 的加权算术平均数：
pXqX
qp
qqpp
r nn
XnXnX
pX qX
34
假设第 p类和第 q类合并成第类，第 r类与其它各旧类的距离按重心法为：
()
11
i p q i l
rl r l i i
x G G x Gp q l
D x x
n n n
xx
2 2 2
2
p q p q
p l q l p q
r r r
n n n nD D D
n n n
35
二、确定类的个数在聚类分析过程中类的个数如何来确定才合适呢？ 这是一个十分困难的问题,人们至今仍未找到令人满意的方法 。 但是这个问题又是不可回避的 。 下面我们介绍几种方法 。
1,给定阈值 —— 通过观测聚类图,给出一个合适的阈值 T。
要求类与类之间的距离不要超过 T值 。 例如我们给定 T=0.35,当聚类时,类间的距离已经超过了 0.35,则聚类结束 。
36
总离差平方和的分解（准备知识）
npnn
p
p
xxx
xxx
xxx
21
22221
11211
1x 2x px
22
1
2
11
2
111
)()(
)()
pnppp
n
xxxx
xxxx
（总离差平方和
37
如果着些样品被分成两类
pnnn
p
p
xxx
xxx
xxx
222 21
22221
11211
pnnn
p
p
xxx
xxx
xxx
111 21
22221
11211
)1(1x )1(2x )1(px )2(1x )2(2x )2(px
2)1(2)1(
1
21
11
21
111
)()(
)()
1
1
ppnpp
n
xxxx
xxxx
）（）（（一组的离差平方和
2)2(2)2(
1
22
11
22
111
)()(
)()
2
2
ppnpp
n
xxxx
xxxx
）（）（（二组的离差平方和
38
可以证明：
总离差平方和
＝组内离差平方和＋组间离差平方和令 T为总离差平方和令 PG为分为 G类的组内离差平方和。
39
2,统计量其中 T是数据的总离差平方和,是组内离差平方和。
比较大，说明分 G个类时类内的离差平方和比较小，
也就是说分 G类是合适的。但是，分类越多，每个类的类内的离差平方和就越小,也就越大；所以我们只能取合适的 G，使得 足够大，而 G本身很小，随着 G的增加,的增幅不大。比如，假定分 4类时，
=0.8； 下一次合并分 3类时,下降了许多,=0.32，
则分 4 类是合适的。
T
PR G 12
GP
2R
2R
2R
2R
2R
2R
40
3,伪 F统计量的定义为伪 F统计量用于评价聚为 G类的效果 。 如果聚类的效果好,类间的离差平方和相对于类内的离差平方和大,所以应该取伪 F统计量较大而类数较小的聚类水平 。
)(
)1()(
GnP
GPTF
G
G
41
Pseudo F Statistic
0
10
20
30
40
50
60
70
80
90
100
110
120
Number of Clusters
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
42
4,伪 统计量的定义为其中 和 分别是的类内离差平方和,
是将 K和 L合并为第 M类的离差平方和
= - -
为合并导致的类内离差平方和的增量 。 用它评价合并第 K和 L类的效果,伪 统计量大说明不应该合并这两类,应该取合并前的水平 。
2t
)2()(
2
LKLK
KL
NNWW
Bt
KW
LWKLB KWMW
LW
2t
43
三,系统聚类法的基本性质
（ 一 ） 单调性在聚类分析过程中,并类距离分别为 l k（ k=1,2，
3,…? ） 若满足,则称该聚类方法具有单调性 。 可以证明除了重心法和中间距离法之外,
其他的系统聚类法均满足单调性的条件 。
121 kk llll
（二）空间的浓缩和扩张
1,定义矩阵的大小设同阶矩阵 D（ A） 和 D（ B）,如果 D（ A） 的每一个元素不小于 D（ B） 的每一个元素,则记为 。 )()( BDAD?
44
2,空间的浓缩和扩张设有两种系统聚类法 A和 B,他们在第 i步的距离矩阵分别为 Ai和 Bi（ I=1,2,3… ）,若 Ai>Bi,
则称第一种方法 A比第二种方法 B使空间扩张,或第二种方法比第一种方法浓缩 。
3,方法的比较
D（ 短 ） D（ 平 ）,D（ 重 ） D（ 平 ） ；
D（ 长 ） D（ 平 ） ；
当,D（ 变平 ） D（ 平 ） ；
当,D（ 变平 ） D（ 平 ） 。
100
45
五、主要的步骤
1、选择变量
（ 1）和聚类分析的目的密切相关
（ 2）反映要分类变量的特征
（ 3）在不同研究对象上的值有明显的差异
（ 4）变量之间不能高度相关
2、计算相似性相似性是聚类分析中的基本概念，他反映了研究对象之间的亲疏程度，聚类分析就是根据对象之间的相似性来分类的。有很多刻画相似性的测度
46
3、聚类选定了聚类的变量，计算出样品或指标之间的相似程度后，构成了一个相似程度的矩阵。这时主要涉及两个问题：
（ 1）选择聚类的方法
（ 2）确定形成的类数
47
4、聚类结果的解释和证实
对聚类结果进行解释是希望对各个类的特征进行准确的描述，给每类起一个合适的名称。这一步可以借助各种描述性统计量进行分析，通常的做法是计算各类在各聚类变量上的均值，对均值进行比较，还可以解释各类产别的原因。
48
例 某公司下属 30个企业,公司为了考核下属企业的经济效益,设计了 8个指标 。 为了避免重复,需要对这 8个指标进行筛选,建立一个恰当的经济效益指标体系 。 通过计算 30
个企业 8个指标的相关系数距离,数据是 1-r2。 得如下表,
x1 x2 x3 x4 x5 x6 x7 x8
x1 0
0.60 0
0.43 0.46 0
0.47 0.45 0.12 0
0.57 0.45 0.23 0.22 0
0.38 0.40 0.21 0.29 0.22 0
0.31 0.79 0.65 0.70 0.80 0.66 0
0.45 0.45 0.27 0.23 0.14 0.19 0.77 0
试用将它们聚类 。
x2
x3
x4
x5
x6
x7
x8
49
50
根据美国等 20个国家和地区的信息基础设施的发展状况进行分类 。
Call— 每千人拥有的电话线数；
move l— 每千人户居民拥有的蜂窝移动电话数；
fee— 高峰时期每三分钟国际电话的成本；
comp— 每千人拥有的计算机数；
mips— 每千人计算机功率 （ 每秒百万指令 ） ；
net— 每千人互联网络户主数。
51
国家 call movel fee comp mips net
meiguo 631.6 161.9 0.36 403 26073 35.34
riben 498.4 143.2 3.57 176 10223 6.26
deguo 557.6 70.60 2.18 199 11571 9.84
ruidian 684.1 281.8 1.4 246 16660 29.39
ruishi 644 93.5 1.98 234 13621 22.68
xinjiapo 498.4 147.5 2.5 284 13578 13.49
taiwan 469.4 56.1 3.68 119 6911 1.72
hanguo 434.5 73 3.36 99 5795 1.66
baxi 81.9 16.3 3.02 19 876 0.52
zhili 138.6 8.20 1.4 31 1411 1.28
moxige 92.2 9.8 2.61 31 1751 0.35
eluosi 174.9 5 5.12 24 1101 0.48
bolan 169 6.5 3.68 40 1796 1.45
xiongyali 262.2 49.4 2.66 68 3067 3.09
malaixiya 195.5 88.4 4.19 53 2734 1.25
taiguo 78.6 27.8 4.95 22 1662 0.11
yindu 13.6 0.30 6.28 2 101 0.01
faguo 559.1 42.9 1.27 201 11702 4.76
yingguo 521.10 122.5 0.98 248 14461 11.91
52
53
Pseudo F Statistic
0
10
20
30
40
50
60
70
80
90
100
110
120
Number of Clusters
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
54
§ 4 动态聚类一,思想系统聚类法是一种比较成功的聚类方法 。 然而当样本点数量十分庞大时,则是一件非常繁重的工作,
且聚类的计算速度也比较慢 。 比如在市场抽样调查中,有 4万人就其对衣着的偏好作了回答,希望能迅速将他们分为几类 。 这时,采用系统聚类法就很困难,而动态聚类法就会显得方便,适用 。
动态聚类解决的问题是,假如有个样本点,要把它们分为类,使得每一类内的元素都是聚合的,并且类与类之间还能很好地区别开 。 动态聚类使用于大型数据 。
55
选择凝聚点分类修改分类分类是否合理分类结束
Yes
No
56
用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。 快速聚类的步骤：
1、随机选取两个点 和 作为聚核。
2、对于任何点,分别计算
3、若,则将 划为第一类，否则划给第二类。于是得图（ b）的两个类。
)1(1x )1(2x
kx ),(),(
)1(
2
)1(
1 xxdxxd kk 和
),(),( )1(2)1(1 xxdxxd kk?kx
4,分别计算两个类的重心,则得 和,以其为新的聚核,对空间中的点进行重新分类,得到新分类 。
)2(1x )2(2x
57
（ a） 空间的群点 (b) 任取两个聚核
(c) 第一次分类 (d) 求各类中心
58
(e) 第二次分类
59
二、选择凝聚点和确定初始分类凝聚点就是一批有代表性的点，是欲形成类的中心。凝聚点的 选择直接决定初始分类，对分类结果也有很大的影响，由于凝聚点 的不同选择，其最终分类结果也将出现不同。故选择时要慎重．通 常选择凝聚点的方法有：
(1) 人为选择，当人们对所欲分类的问题有一定了解时，根据经验，预先确定分类个数和初始分类，并从每一类中选择一个有代表性的样品作为凝聚点。
(2) 将数据人为地分为 A类，计算每一类的重心，
就将这些重心作为凝聚点。
60
(3) 用密度法选择凝聚点。以某个正数 d为半径，
以每个样品为球心，落在这个球内的样品数 (不包括作为球心的样品 )就叫做这个样品的密度。计算所有样品点的密度后，首先选择密度最大的样品作为第一凝聚点，并且人为地确定一个正数 D(一般 D＞ d，常取 D＝ 2d)。然后选出次大密度的样品点，若它与第一个凝 聚点的距离大于 D，则将其作为第二个凝聚点；否则舍去这点，再选密度次于它的样品。这样，按密度大小依次考查，直至全部样品考查完毕为止．此方法中,d要给的合适，
太大了使凝聚点个数太 少，太小了使凝聚点个数太多。
61
(5) 随机地选择，如果对样品的性质毫无所知，可采用随机数表来选择，打算分几类就选几个凝聚点。
或者就用前 A个样品作为凝聚点 (假设分 A类 )。这方法一般不提倡使用。
(4) 人为地选择一正数 d，首先以所有样品的均值作为第一凝聚点。然后依次考察每个样品，若某样品与已选定的凝聚点的距 离均大于 d，该样品作为新的凝聚点，否则考察下一个样品。
62
四,动态聚类步骤为：
第一,选择若干个观测值点为,凝聚点,；
第二,可选择地,通过分配每个,凝聚点,最近的类里来形成临时分类 。 每一次对一个观测值点进行归类,,凝聚点,更新为这一类目前的均值；
63
第三，可选择地，通过分配每个“凝聚点”
最近的类里来形成临时分类。所有的观测值点分配完后，这些类的“凝聚点”用临时类的均值代替。该步骤可以一直进行直到“凝聚点”的改变很小或为零时止；
第四，最终的分类有分配每一个观测到最近的“凝聚点”而形成。
64
§ 5 有序样本聚类法前面介绍的聚类方法与样品的顺序无关，但在有些实际问题中样品是有顺序的，样品按一定的要求排成序，分类不能打乱顺序．例如在地质勘探中通过钻井的岩心样品欲将地层分类，此时岩心样品是由浅到深的顺序取的．又如气象资料它是按时间排列的，其样品也是有序的。
65
系统聚类开始 n个样品各自自成一类，然后逐步并类，直至所有的样品被聚为一类为止。而有序聚类则相反，开始所有的样品为一类，然后分为二类、三类等，直到分成 n类。每次分类都要求产生的离差平方和的增量最小。
66
有序聚类的步骤
1、定义类的直径设某类 G中包含的样品有
)( ij ( j )1)(i( i ) x,,x,x?
该类的均值向量为
j
itij ( t )G
xX 11
设有序样品 x(1),x(2),…,x(n) 。他们可以是从小到达排列，也可以是按时间的先后排列。
67
用 D(i,j)表示这一类的直径，常用的直径有，欧氏距离：
j itjiD )X(x)Xx G(t)G(t)(),(
当是单变量的时，也可以定义直径为：
是中位数Gj it G( t ) XXxjiD ~|~|),(
68
2、定义分类的损失函数用 b(n,k)表示将 n个有序的样品分为 k类的某种分法：
1 1 1 2,1,,1G j j j
2 2 2 3,1,,1G j j j
,1,,k k kG j j n
定义这种分类法的损失函数为：各类的直径之和 。
kt tt iiDknbL 1 1 )1,(),(
69
由损失函数的构造可以看出，损失函数是各类的直径之和。如果分类不好，则各类的直径之和大，否则比较小。
当 n和 k固定时,L[b(n,k)]越小表示各类的离差平方和越小，分类是合理的。因此要寻找一种分法 b(n,k)，使分类损失函数 L[b(n,k)]达到最小。记该分法为 P[n,k]。
70
应用简例分析儿童的生长期。有如下的资料是 1-11
岁的男孩平均每年的增重：
问男孩的发育可分为几个阶段。
年龄 1 2 3 4 5 6 7 8 9 10 11
增加重量（公斤）
9.3 1.8 1.9 1.7 1.5 1.3 1.4 2.0 1.9 2.3 2.1
71
j 1 2 3 4 5 6 7 8 9 10
2 2 8,1 2 5
3 3 7,0 0 7 0,0 0 5
4 4 2,2 0 8 0,0 2 0,0 2
5 4 5,9 9 2 0,0 8 8 0,0 8 0,0 2
6 4 9,1 2 8 0,2 3 2 0,2 0,0 8 0,0 2
7 5 1,1 0,2 8 0,2 3 2 0,0 8 8 0,0 2 0,0 0 5
8 5 1,5 2 9 0,4 1 7 0,3 9 3 0,3 0 8 0,2 9 0,2 8 7 0,1 8
9 5 1,9 8 0,4 6 9 0,4 5 4 0,3 9 3 0,3 8 8 0,3 7 0,2 0 7 0,0 0 5 0 8
10 5 2,0 2 9 0,8 0 2 0,8 0,7 7 4 0,7 7 3 0,7 0 8 0,4 2 0,0 8 7 0,0 8
11 5 2,1 8 2 0,9 0 9 0,9 0 9 0,8 9 5 0,8 8 9 0,7 9 3 0,4 5 2 0,0 8 8 0,0 8 0,0 2
i
(,)D i j
72
n
k
2 3 4 5 6 7 8 9 10
3 0.005/2
4 0.02/2 0.005/4
5 0.088/2 0.020/5 0.005/5
6 0.232/2 0.040/5 0.02/6 0.005/6
7 0.280/2 0.040/5 0.025/6 0.010/6 0.005/6
8 0.417/2 0.280/8 0.040/8 0.025/8 0.010/8 0.005/8
9 0.469/2 0.285/8 0.045/8 0.030/8 0.015/8 0.010/8 0.005/8
10 0.802/2 0.367/8 0.127/8 0.045/10 0.030/10 0.015/10 0.010/10 0.005/10
11 0.909/2 0.368/8 0.128/8 0.065/10 0.045/11 0.030/11 0.015/11 0.010/11 0.005/11
最小损失函数 L[p(n,k)
73
损失函数L [ p ( n,k ) ] 随k 变化趋势图
0
0.2
0.4
0.6
0.8
1
1 2 3 4 5 6 7 8 9
类数损失函数
74
分类数 L[p (11,k )] 最优分割结果
2 0.909 1,2-11
3 0.368 1,2-7,8-11
4 0.128 1,2-4,5-7,8-11
5 0.065 1,2-4,5-7,8-9,10-11
6 0.045 1,2-4,5-7,8-9,10,11
7 0.03 1,2-3,4,5-7,8-9,10,11
8 0.015 1,2-3,4,5,6-7,8-9,10,11
9 0.01 1,2,3,4,5,6-7,8-9,10,11
10 0.005 1,2,3,4,5,6,7,8-9,10,11
