两类间的距离
1、最短距离：两类中相距最近的两样品间 的距离。
Dpq
min
xi p
dij
x j q
• 2、最长距离 ：两类中相距最远的两个样本间
的距离。
Dpq
max
xi p
dij
x j q
• 3、中间距离：最短距离和最长距离都有
片面性，因此有时用中间距离。设ω1类和ω23
类间的最短距离为d12，最长距离为d13，ω 23类的
样本号 1 2 3 4 5 6 7 8 9 10
x1
0 0 2 24 4 5 6 6 7
x2
6 5 5 34 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
长度为d23，则中间距离为：
d
2 0
1 2
d122
1 2
d13
•上式推广为一般情况：
1 4
d
2 23
2 d23 d12 d0 d13
3
1
d
2 0
1 2
d122
1 2
d13
d
2 23
其中为参数，－ 1 0 4
• 4、重心距离：均值间的距离
• 5、类平均距离：两类中各个元素两两之间的 距离平方相加后取平均值
x2的值。可用以下递推
k ) xi ) /( N1(k ) 1)
x(k 1) 2
(k)
x2
(k)
(x2
xi
)
/(
N
(k 2
)
1)
x1 (k) , x2 (k)是第k步对分时两类均值,
x1(k 1) , x2(k 1)是下一次对分时把xi从G1(k )
划到G2(k)时的两类均值
N1(
k
)
,
N
(k 2
N
2、分别计算当 x1, x2 ,..., x21 划入G2 时的E值
x 把 1划入G2 时有
(0)
(1)
x x x 1
(0)
1
1 x1 N1(0) 1
0.714
(
)
(10..373134) (60)
0.75
(
),
1.333
(21 1)
1.10
(1)
0
x2
( ) 6
E 20 1 0.752 (1.10 6)2 23.40 21
样 本符合正态分布
⑥ 夹角余弦
Cij
n
XikXjk
k 1
n k 1
Xik
2
n k 1
Xjk 2
为xi xj的均值 即样本间夹角小的为一类，具有相似性
例： x1 , x2 , x3的夹角如图：
x2
x3
x1
x2
x1
因为x1 , x2 的夹角小，所以x1 , x2 最相似。
⑦ 相关系数
n
然后再把x2 , x3,..., x21 划入 G2 时对应的
E值，找出一个最大的E值。
x 把 21划为G2 的E值最大。
G G ∴
(1) 1
( x1 ,
x2
,...,
x20
),
(1) 2
( x21 )
0.9
x1
( ), 1.65
x2
(
3 ),
5
N (1) 1
20,
N
(1) 2
1
E(1)=56.6
目标函数 两类均值方差
E
N1 N 2 N
(x1
T
x2 )
(x1
x2 )
N：总样本数，N1 ：ω1类样本数
N2：ω2类样本数，x1, x2 : 两类均值
❖分解聚类框图：
初始分类
调整分类方案 N
目标函数 达到最优先？
Y
最终结果
对分算法：略 例：已知21个样本，每个样本取二个特征，原 始资料矩阵如下表：
已知两个样本
xi=(xi1, xi2 , xi3,…,xin)T xj=(xj1, xj2 , xj3,…,xjn)T
n
dij | Xik Xjk | k 1
② 欧几里德距离
dij n Xik Xjk 2 k 1
③明考夫斯基距离
| | n
q 1 q
dij(q) Xik Xjk
k 1
其 中 当 q=1 时 为 绝 对 值 距 离 ， 当q=2时为欧氏距离
④ 切比雪夫距离
dij() max | Xik Xjk | 1k n
q趋向无穷大时明氏距离的极限情况 ⑤ 马哈拉诺比斯距离
T
dij(M ) Xi Xj
1 Xi Xj
其中xi ，xj为特征向量， 为协方差。使用的条件是
G3 G1
G2 G5
x G4 G6
• 1、设全部样本分为6类， • 2、作距离矩阵D(0)
ω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、求最小元素：d31 d64 1 4、把ω1,ω3合并ω7=(1,3)
ω4,ω6合并ω8=(4,6) 5、作距离矩阵D(1)
体积与长，宽，高有关；比重与材料，纹理，颜 色有关。这里低、中、高三层特征都有了。
方法的有效性
特征选取不当 特征过少 特征过多 量纲问题
主要聚类分析技术
谱系法（系统聚类，层次聚类法） 基于目标函数的聚类法（动态聚类） 图论聚类法 模糊聚类分析法
2.2模式相似度度量
各种距离表示相似性：
① 绝对值距离
Xki Xi Xkj Xj
rij k1
n
2n
2
Xki Xi
Xkj Xj
k 1
k 1
为xi xj的均值
注意：在求相关系数之前，要将数据标准化
2.3类的定义和与类间距离
用距离进行定义类（书19）
非监督学习方法分类
1、基于概率密度函数估计的直接方法 2、基于样本间相似性度量的间接聚类方 法
0
0
11
x2 Z2 (1)
离差平方和增量：设样本已分成ωp,ωq两类， 若把ωp,ωq合为ωr类，则定义离差平方：
D
2 pq
Sr
(Sp
Sq )
其中S p , Sq分别为 p类于q类的离差平方和,
S r为 r 类的离差平方和
增量愈小，合并愈合理。
聚类准则
类内距离越小越好
Jw Min
类间距离越大越好
JB Max
一些准则函数
④ 用前k个样本点作为代表点。
三、初始分类和调整
① 选一批代表点后，代表点就是聚类中心，计算其它样本
到聚类中心的距离，把所有样本归于最近的聚类中心点，形成 初始分类，再重新计算各聚类中心，称为成批处理法。
② 选一批代表点后,依次计算其它样本的归类，当计算完第 一个样本时，把它归于最近的一类，形成新的分类。再计算新 的聚类中心，再计算第二个样本到新的聚类中心的距离，对第 二个样本归类。即每个样本的归类都改变一次聚类中心。此法 称为逐个处理法。
)为二类样品数
6
5
4
x11
3
x15
x13
x12
2
1 x14
6 5 4 3 2 1
x19 1
2
x20 3 4
5
x21
6
Xx12
x2
x3
x4
x16
12 3 x17 x18
x5
x6
x8
x7
x9 x10
456
X1
§ 动态聚类——兼顾系统聚 类和分解聚类
一、动态聚类的方法概要 ① 先选定某种距离作为样本间的相似性 的度量; ② 确定评价聚类结果的准则函数; ③ 给出某种初始分类，用迭代法找出使 准则函数取极值的最好的聚类结果。
J 准则函数
下降快
拐点 A
下降慢
0 1 2 3 4 5 67
K
最佳初始分类
四、C－平均算法
例：已知有20个样本，每个样本有2个特征，数据分布如下 图 样本序号 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
③ 直接用样本进行初始分类，先规定距离d,把第一个样品作 为第一类的聚类中心，考察第二个样本，若第二个样本距第一 个聚类中心距离小于d，就把第二个样本归于第一类，否则第 二个样本就成为第二类的聚类中心，再考虑其它样本，根据样 本到聚类中心距离大于还是小于d，决定分裂还是合并。
④ 最佳初始分类。 如图所示，随着初始分类k的增大，准则函数下降很快，经 过拐点A后，下降速度减慢。拐点A就是最佳初始分类。
D 2 pq
1 N pNq
di2j
xi p
x j q
其中:
N
p
: p样本数,
Nq
:
样本数
q
dij为 p类点i与q类点j之间的距离
6、 离差平方和：
设N个样品原分q类，则定义第i类的离差平
方和为： Siq
Ni
(xij xi )T (xij xi )
j 1
其中xi为样品xij的均值, Ni为第i类的样本数.
6
5
x9 x10 x11
4
3
2 1 x3
x5
x6 x7 x8 x4
X1
0 1 2 3 4 5 6 7 8 9 10