第六章 聚类分析
§ 6－ 1 分类与聚类的区别
– 分类：用已知类别的样本训练集来设计分类器（监督学习）
– 聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）
§ 6-2 系统聚类
系统聚类：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。
相似性、相邻性一般用距离表示
（ 1）两类间的距离
– 1、最短距离：两类中相距最近的两样品间的距离。
ij
x
xpq
dD
qj
pi
m in
2、最长距离,两类中相距最远的两个样本间的距离。
3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。 设 ω1类和 ω23
类间的最短距离为 d12，最长距离为 d13,ω 23类的长度为 d23，则中间距离为：
上式推广为一般情况：
ij
x
xpq
dD
qj
pi
m ax
2
2313
2
12
2
0 4
1
2
1
2
1 dddd
1
2 3
12d
0d
23d
13d
0
4
1
2
1
2
1 2
2313
2
12
2
0
为参数，－其中
dddd
4、重心距离：均值间的距离
5、类平均距离：两类中各个元素两两之间的距离平方相加后取平均值
qj
pi
pq
x
x
ij
qp
d
NN
D
22 1
之间的距离类点与类点为样本数样本数其中
jid
NN
qpij
qqpp
,,::
6,离差平方和：
– 设 N个样品原分 q类，则定义第 i类的离差平方和为：
– 离差平方和增量：设样本已分成 ωp,ωq两类，
若把 ωp,ωq合为 ωr类，则定义离差平方：
.
,
)()(
1
类的样本数为第的均值为样品其中
iN
xx
xxxxS
i
ij
i
i
ij
T
i
N
j
ij
q
i
i
。增量愈小，合并愈合理类的离差平方和为类的离差平方和类于分别为其中
rr
qpqp
qprpq
S
SS
SSSD
,,
)(
2
（ 2）系统聚类的算法（略）
例：如下图所示
1、设全部样本分为 6类，
2、作距离矩阵 D(0)
3G 1G 2G 5G 4G 6G
x
ω1 ω2 ω3 ω4 ω5
ω2 9
ω3 1 16
ω4 49 16 64
ω5 25 4 36 4
ω6 64 25 81 1 9
3、求最小元素：
4、把 ω1,ω3合并 ω7=(1,3)
ω4,ω6合并 ω8=(4,6)
5、作距离矩阵 D(1)
16431 dd
ω7 ω2 ω8
ω2 9
ω8 49 16
ω5 25 4 4
6、若合并的类数没有达到要求，转 3。
否则停止。
3、求最小元素：
4,ω8,ω5,ω2合并,ω9=（ 2,5,4,6）
45852 dd
枝状图
1?
5?
2?
3?
4?
6?
7?
8?
9?
10?
§ 6-2 分解聚类
分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。
目标函数 两类均值方差
)()( 212121 xxxx TNNNE
N：总样本数,,ω1类样本数
,ω2类样本数,两类均值:,21 xx
1N
2N
分解聚类框图：
初始分类调整分类方案 最终结果目标函数达到最优先？N Y
对分算法：略例：已知 21个样本，每个样本取二个特征，原始资料矩阵如下表：
样本号 1 2 3 4 5 6 7 8 9 10
x1 0 0 2 2 4 4 5 6 6 7
x2 6 5 5 3 4 3 1 2 1 0
11 12 13 14 15 16 17 18 19 20 21
-4 -2 -3 -3 -5 1 0 0 -1 -1 -3
3 2 2 0 2 1 -1 -2 -1 -3 -5
∴ 目标函数
0)()( 212121 xxxxNNNE T
∴ )
333.1
714.0()0(
1?x
)
0
0
(
)0(
2?x
0,21 )0(2)0(1 NN
解：第一次分类时计算所有样本，分别划到时的 E值，找出最大的。
1、开始时，
G2
),...,,( 2121)0(1 xxxG? 空?G )0(2
2、分别计算当 划入 G2 时的 E值把 划入 G2 时有
2121,...,,xxx
1x
40.23)610.1(75.0
21
120
)
6
0
(
),
10.1
75.0
(
)121(
)
6
0
()
333.1
714.0
(
)
333.1
714.0
(
1
22
)1(
2
)0(
1
1
)0(
1
)0(
1
)1(
1
E
N
x
x
x
xx
然后再把 划入 时对应的 E
值，找出一个最大的 E值。
把 划为 的 E值最大。
∴
2132,.,,,,xxx
G2
G2x21
),,..,,,( 2021)1(1 xxxG? )( 21)1(2 xG?
),
65.1
9.0
(1?x 1,20),5
3
( )1(2)1(12
NNx
E(1)=56.6
再继续进行第二，第三次迭代 …
计算出 E(2),E(3),…
次数 E值
1 56.6
2 79.16
3 90.90
4 102.61
5 120.11
6 137.15
7 154.10
8 176.15
9 195.26
10 213.07
11 212.01
G2G1
x21
x20
x18
x14
x15
x19
x11
x13
x12
x17
x16
第 10次迭代 划入 时,E最大。于是分成以下两类：
∴
G2x17
),,...,,( 1610211 xxxxG?
),,,,,,,,( 212019181715,141312112 xxxxxxxxxxG?
每次分类后要重新计算 的值。可用以下递推公式,21,xx
)1/()(
)1/()(
)(
2
)(
2
)(
2
)1(
2
)(
1
)(
1
)(
1
)1(
1
k
i
kkk
k
i
kkk
Nxxxx
Nxxxx
为二类样品数时的两类均值划到从是下一次对分时把步对分时两类均值是第
)(
2
)(
1
)(
2
)(
1
)1(
2
)1(
1
)(
2
)(
1
,
,
,,
kk
k
k
i
kk
kk
NN
G
Gxxx
kxx
10x
2x
3x
4x
15x
11x
12x
13x
14x
16x
17x
18x
19x
7x
8x
9x
20x
21x
6x
1x
5x
6
5
4
3
2
1
1
2
3
4
5
6
1X
2X
4321 5 66? 5? 4? 3? 2? 1?
作业：
样本 1 2 3 4 5 6 7 8
0 2 1 5 6 5 6 7
0 2 1 3 3 4 4 5
用对分法编程上机，分成两类画出图形。
1x
2x
§ 6-3 动态聚类 ——兼顾系统聚类和分解聚类一、动态聚类的方法概要
① 先选定某种距离作为样本间的相似性的度量 ;
② 确定评价聚类结果的准则函数 ;
③ 给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。
选代表点 初始分类 分类合理否 最终分类修改分类
Y
N
动态聚类框图二、代表点的选取方法：代表点就是初始分类的聚类中心数 k
① 凭经验选代表点，根据问题的性质、数据分布，
从直观上看来较合理的代表点 k;
② 将全部样本随机分成 k类，计算每类重心，把这些重心作为每类的代表点 ;
③ 按密度大小选代表点：
以每个样本作为球心，以 d为半径做球形 ;落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于 d1（人为规定的正数）则把第二大密度点作为第二代表点，，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于 d1。 d1太小，代表点太多,d1太大，代表点太小，一般选 d1＝ 2d。对代表点内的密度一般要求大于 T。 T>0为规定的一个正数。
④ 用前 k个样本点作为代表点。
三、初始分类和调整
① 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。
② 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。
③ 直接用样本进行初始分类，先规定距离 d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于 d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于 d，决定分裂还是合并。
④ 最佳初始分类。
如图所示，随着初始分类 k的增大，准则函数下降很快，经过拐点 A后，下降速度减慢。拐点 A就是最佳初始分类。
准则函数J
K
最佳初始分类
A
拐点
0 321 7654
下降快下降慢
四,K次平均算法：成批处理法（ 算法略）
例：已知有 20个样本，每个样本有 2个特征，数据分布如下图第一步：令 K=2，选初始聚类中心为
TT xZxZ )0,1()1(;)0,0()1( 2211
样本序号 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
特征 x1 0 1 0 1 2 1 2 3 6 7
特征 x2 0 0 1 1 1 2 2 2 6 6
x11 x12 x13 x14 x15 x16 x17 x18 x19 x20
8 6 7 8 9 7 8 9 8 9
6 7 7 7 7 8 8 8 9 9
1
5
4
3
1
2
6
6
5432
1X
10
10
9
9
8
8
7
70
2X
1x 2x
3x
4x 5 x
6x 7x 8x
9x 10x 11x
12x 13x 14x 15x
16x 17x 18x
19x 20x
1
0
0
0
1
)1(
)1(
)1()1(
1
0
1
0
0
)1(
0
0
0
0
0
)1(
12
11
2111
21
11
＝））－（（＝
所以因为
＝））－（（＝
＝））－（（＝第二步：
Zx
Zx
ZxZx
Zx
Zx
18,2
),.,.,,()1(
),,()1(
)1(..,
..,
)1(,1)1(2)1(
)1(,2)1(1)1(
)1(
,)1()1(
0)
0
1
()
0
1
()1(
21
205421
311
22065
2065
242414
132313
22
2212
22
NN
xxxxG
xxG
Zxxx
xxx
ZxZxZx
ZxZxZx
Zx
ZxZx
Zx
二、
一、
因此分为两类：
都属于、、离计算出来，判断与第二个聚类中心的距、、同样把所有
＝
＝
同理所以因为
第三步：根据新分成的两类建立新的聚类中心
T
Gx
xxX
N
Z
)5.0,0()
1
0
(
2
1
)
1
0
()
0
0
(
2
1
)(
2
11
)2(
31
)1(1
1
1
T
Gx
xxxxX
N
Z
)33.5,67.5(
)...(
18
11)2(
20542
)1(2
2
2
第四步：
∵
转第二步。
第二步：重新计算 到 z1(2),z2(2) 的距离，把它们归为最近聚类中心，重新分为两类，
)(2,1),1()2( 新旧聚类中心不等 JZZ JJ
2021,.,,,,xxx
第三步，更新聚类中心
T
Gx
xxxxX
N
Z
)13.1,25.1(
)...(
8
11
)3( 8321
)2(1
1
1
T
Gx
xxxX
N
Z
)33.7,67.7(
)...(
12
11
)3( 20109
)2(2
2
2
8),,.,,,,()2( 18211 NxxxG
12),,.,,,,()2( 2201092 NxxxG
第四步，
第二步，
第三步，更新聚类中心转第二步因,2,1),2()3( jZZ jj
12,8),,.,.,,()4(
),.,.,,()4(
,.,.,,
)3(),3(,.,.,,
21201092
8211
2021
212021
NNxxxG
xxxG
xxx
ZZxxx
重新分为二类心，归于最近的那个聚类中分别把的距离，到重新计算计算结束。
T
T
ZZ
ZZ
)33.7,67.7()3()4(
)13.1,25.1()3()4(
22
11
上机作业
已知十个样本，每个样本 2个特征，数据如下：
用 K次平均算法和 ISODATA算法分成 3类，
编程上机，并画出分类图。
样本序号 1 2 3 4 5 6 7 8 9 10
x1 0 1 2 4 5 5 6 1 1 1
x2 0 1 1 3 3 4 5 4 5 6
§ 6－ 1 分类与聚类的区别
– 分类：用已知类别的样本训练集来设计分类器（监督学习）
– 聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）
§ 6-2 系统聚类
系统聚类：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。
相似性、相邻性一般用距离表示
（ 1）两类间的距离
– 1、最短距离：两类中相距最近的两样品间的距离。
ij
x
xpq
dD
qj
pi
m in
2、最长距离,两类中相距最远的两个样本间的距离。
3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。 设 ω1类和 ω23
类间的最短距离为 d12，最长距离为 d13,ω 23类的长度为 d23，则中间距离为：
上式推广为一般情况：
ij
x
xpq
dD
qj
pi
m ax
2
2313
2
12
2
0 4
1
2
1
2
1 dddd
1
2 3
12d
0d
23d
13d
0
4
1
2
1
2
1 2
2313
2
12
2
0
为参数，－其中
dddd
4、重心距离：均值间的距离
5、类平均距离：两类中各个元素两两之间的距离平方相加后取平均值
qj
pi
pq
x
x
ij
qp
d
NN
D
22 1
之间的距离类点与类点为样本数样本数其中
jid
NN
qpij
qqpp
,,::
6,离差平方和：
– 设 N个样品原分 q类，则定义第 i类的离差平方和为：
– 离差平方和增量：设样本已分成 ωp,ωq两类，
若把 ωp,ωq合为 ωr类，则定义离差平方：
.
,
)()(
1
类的样本数为第的均值为样品其中
iN
xx
xxxxS
i
ij
i
i
ij
T
i
N
j
ij
q
i
i
。增量愈小，合并愈合理类的离差平方和为类的离差平方和类于分别为其中
rr
qpqp
qprpq
S
SS
SSSD
,,
)(
2
（ 2）系统聚类的算法（略）
例：如下图所示
1、设全部样本分为 6类，
2、作距离矩阵 D(0)
3G 1G 2G 5G 4G 6G
x
ω1 ω2 ω3 ω4 ω5
ω2 9
ω3 1 16
ω4 49 16 64
ω5 25 4 36 4
ω6 64 25 81 1 9
3、求最小元素：
4、把 ω1,ω3合并 ω7=(1,3)
ω4,ω6合并 ω8=(4,6)
5、作距离矩阵 D(1)
16431 dd
ω7 ω2 ω8
ω2 9
ω8 49 16
ω5 25 4 4
6、若合并的类数没有达到要求，转 3。
否则停止。
3、求最小元素：
4,ω8,ω5,ω2合并,ω9=（ 2,5,4,6）
45852 dd
枝状图
1?
5?
2?
3?
4?
6?
7?
8?
9?
10?
§ 6-2 分解聚类
分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。
目标函数 两类均值方差
)()( 212121 xxxx TNNNE
N：总样本数,,ω1类样本数
,ω2类样本数,两类均值:,21 xx
1N
2N
分解聚类框图：
初始分类调整分类方案 最终结果目标函数达到最优先？N Y
对分算法：略例：已知 21个样本，每个样本取二个特征，原始资料矩阵如下表：
样本号 1 2 3 4 5 6 7 8 9 10
x1 0 0 2 2 4 4 5 6 6 7
x2 6 5 5 3 4 3 1 2 1 0
11 12 13 14 15 16 17 18 19 20 21
-4 -2 -3 -3 -5 1 0 0 -1 -1 -3
3 2 2 0 2 1 -1 -2 -1 -3 -5
∴ 目标函数
0)()( 212121 xxxxNNNE T
∴ )
333.1
714.0()0(
1?x
)
0
0
(
)0(
2?x
0,21 )0(2)0(1 NN
解：第一次分类时计算所有样本，分别划到时的 E值，找出最大的。
1、开始时，
G2
),...,,( 2121)0(1 xxxG? 空?G )0(2
2、分别计算当 划入 G2 时的 E值把 划入 G2 时有
2121,...,,xxx
1x
40.23)610.1(75.0
21
120
)
6
0
(
),
10.1
75.0
(
)121(
)
6
0
()
333.1
714.0
(
)
333.1
714.0
(
1
22
)1(
2
)0(
1
1
)0(
1
)0(
1
)1(
1
E
N
x
x
x
xx
然后再把 划入 时对应的 E
值，找出一个最大的 E值。
把 划为 的 E值最大。
∴
2132,.,,,,xxx
G2
G2x21
),,..,,,( 2021)1(1 xxxG? )( 21)1(2 xG?
),
65.1
9.0
(1?x 1,20),5
3
( )1(2)1(12
NNx
E(1)=56.6
再继续进行第二，第三次迭代 …
计算出 E(2),E(3),…
次数 E值
1 56.6
2 79.16
3 90.90
4 102.61
5 120.11
6 137.15
7 154.10
8 176.15
9 195.26
10 213.07
11 212.01
G2G1
x21
x20
x18
x14
x15
x19
x11
x13
x12
x17
x16
第 10次迭代 划入 时,E最大。于是分成以下两类：
∴
G2x17
),,...,,( 1610211 xxxxG?
),,,,,,,,( 212019181715,141312112 xxxxxxxxxxG?
每次分类后要重新计算 的值。可用以下递推公式,21,xx
)1/()(
)1/()(
)(
2
)(
2
)(
2
)1(
2
)(
1
)(
1
)(
1
)1(
1
k
i
kkk
k
i
kkk
Nxxxx
Nxxxx
为二类样品数时的两类均值划到从是下一次对分时把步对分时两类均值是第
)(
2
)(
1
)(
2
)(
1
)1(
2
)1(
1
)(
2
)(
1
,
,
,,
kk
k
k
i
kk
kk
NN
G
Gxxx
kxx
10x
2x
3x
4x
15x
11x
12x
13x
14x
16x
17x
18x
19x
7x
8x
9x
20x
21x
6x
1x
5x
6
5
4
3
2
1
1
2
3
4
5
6
1X
2X
4321 5 66? 5? 4? 3? 2? 1?
作业：
样本 1 2 3 4 5 6 7 8
0 2 1 5 6 5 6 7
0 2 1 3 3 4 4 5
用对分法编程上机，分成两类画出图形。
1x
2x
§ 6-3 动态聚类 ——兼顾系统聚类和分解聚类一、动态聚类的方法概要
① 先选定某种距离作为样本间的相似性的度量 ;
② 确定评价聚类结果的准则函数 ;
③ 给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。
选代表点 初始分类 分类合理否 最终分类修改分类
Y
N
动态聚类框图二、代表点的选取方法：代表点就是初始分类的聚类中心数 k
① 凭经验选代表点，根据问题的性质、数据分布，
从直观上看来较合理的代表点 k;
② 将全部样本随机分成 k类，计算每类重心，把这些重心作为每类的代表点 ;
③ 按密度大小选代表点：
以每个样本作为球心，以 d为半径做球形 ;落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于 d1（人为规定的正数）则把第二大密度点作为第二代表点，，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于 d1。 d1太小，代表点太多,d1太大，代表点太小，一般选 d1＝ 2d。对代表点内的密度一般要求大于 T。 T>0为规定的一个正数。
④ 用前 k个样本点作为代表点。
三、初始分类和调整
① 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。
② 选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。
③ 直接用样本进行初始分类，先规定距离 d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于 d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于 d，决定分裂还是合并。
④ 最佳初始分类。
如图所示，随着初始分类 k的增大，准则函数下降很快，经过拐点 A后，下降速度减慢。拐点 A就是最佳初始分类。
准则函数J
K
最佳初始分类
A
拐点
0 321 7654
下降快下降慢
四,K次平均算法：成批处理法（ 算法略）
例：已知有 20个样本，每个样本有 2个特征，数据分布如下图第一步：令 K=2，选初始聚类中心为
TT xZxZ )0,1()1(;)0,0()1( 2211
样本序号 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
特征 x1 0 1 0 1 2 1 2 3 6 7
特征 x2 0 0 1 1 1 2 2 2 6 6
x11 x12 x13 x14 x15 x16 x17 x18 x19 x20
8 6 7 8 9 7 8 9 8 9
6 7 7 7 7 8 8 8 9 9
1
5
4
3
1
2
6
6
5432
1X
10
10
9
9
8
8
7
70
2X
1x 2x
3x
4x 5 x
6x 7x 8x
9x 10x 11x
12x 13x 14x 15x
16x 17x 18x
19x 20x
1
0
0
0
1
)1(
)1(
)1()1(
1
0
1
0
0
)1(
0
0
0
0
0
)1(
12
11
2111
21
11
＝））－（（＝
所以因为
＝））－（（＝
＝））－（（＝第二步：
Zx
Zx
ZxZx
Zx
Zx
18,2
),.,.,,()1(
),,()1(
)1(..,
..,
)1(,1)1(2)1(
)1(,2)1(1)1(
)1(
,)1()1(
0)
0
1
()
0
1
()1(
21
205421
311
22065
2065
242414
132313
22
2212
22
NN
xxxxG
xxG
Zxxx
xxx
ZxZxZx
ZxZxZx
Zx
ZxZx
Zx
二、
一、
因此分为两类：
都属于、、离计算出来，判断与第二个聚类中心的距、、同样把所有
＝
＝
同理所以因为
第三步：根据新分成的两类建立新的聚类中心
T
Gx
xxX
N
Z
)5.0,0()
1
0
(
2
1
)
1
0
()
0
0
(
2
1
)(
2
11
)2(
31
)1(1
1
1
T
Gx
xxxxX
N
Z
)33.5,67.5(
)...(
18
11)2(
20542
)1(2
2
2
第四步：
∵
转第二步。
第二步：重新计算 到 z1(2),z2(2) 的距离，把它们归为最近聚类中心，重新分为两类，
)(2,1),1()2( 新旧聚类中心不等 JZZ JJ
2021,.,,,,xxx
第三步，更新聚类中心
T
Gx
xxxxX
N
Z
)13.1,25.1(
)...(
8
11
)3( 8321
)2(1
1
1
T
Gx
xxxX
N
Z
)33.7,67.7(
)...(
12
11
)3( 20109
)2(2
2
2
8),,.,,,,()2( 18211 NxxxG
12),,.,,,,()2( 2201092 NxxxG
第四步，
第二步，
第三步，更新聚类中心转第二步因,2,1),2()3( jZZ jj
12,8),,.,.,,()4(
),.,.,,()4(
,.,.,,
)3(),3(,.,.,,
21201092
8211
2021
212021
NNxxxG
xxxG
xxx
ZZxxx
重新分为二类心，归于最近的那个聚类中分别把的距离，到重新计算计算结束。
T
T
ZZ
ZZ
)33.7,67.7()3()4(
)13.1,25.1()3()4(
22
11
上机作业
已知十个样本，每个样本 2个特征，数据如下：
用 K次平均算法和 ISODATA算法分成 3类，
编程上机，并画出分类图。
样本序号 1 2 3 4 5 6 7 8 9 10
x1 0 1 2 4 5 5 6 1 1 1
x2 0 1 1 3 3 4 5 4 5 6
