第六章聚类分析 §6-1分类与聚类的区别 分类:用已知类别的样本训练集来设计分类 器(监督学习) 聚类(集群):用事先不知样本的类别,而 利用样本的先验知识来构造分类器(无监督 学习)
第六章 聚类分析 • §6-1 分类与聚类的区别 – 分类:用已知类别的样本训练集来设计分类 器(监督学习) – 聚类(集群):用事先不知样本的类别,而 利用样本的先验知识来构造分类器(无监督 学习)
§6-2系统聚类 系统聚类:先把每个样本作为一类,然 后根据它们间的相似性和相邻性聚合 相似性、相邻性一般用距离表示 (1)两类间的距离 1、最短距离:两类中相距最近的两样品间 的距离。 D min ∈O eOg
§6-2 系统聚类 • 系统聚类:先把每个样本作为一类,然 后根据它们间的相似性和相邻性聚合。 • 相似性、相邻性一般用距离表示 • (1)两类间的距离 – 1、最短距离:两类中相距最近的两样品间 的距离。 ij x x Dp q d j q i p = min
2、最长距离:两类中相距最远的两个样本间 的距离。 Dpa= max d, 3、中间距离:最短距离和最长距离都有 片面性,因此有时用中间距离。设01类和o23 类间的最短距离为d12,最长距离为d13,02类的 长度为d23,则中间距离为: 23 12 13 4 上式推广为一般情况: 13
• 2、最长距离 :两类中相距最远的两个样本间 的距离。 • 3、中间距离:最短距离和最长距离都有 片面性,因此有时用中间距离。设ω1类和ω23 类间的最短距离为d12,最长距离为d13,ω 23类的 长度为d23,则中间距离为: •上式推广为一般情况: ij x x Dpq d j q i p = max 2 1 3 2 3 2 1 2 2 0 4 1 2 1 2 1 d = d + d − d 1 2 3 12 d 0 d 23 d 13 d
4=2“2+243+B 其中β为参数, β≤0 重心距离:均值间的距离 5、类平均距离:两类中各个元素两两之间的 距离平方相加后取平均值 D pq P x;∈O q 其中:Nn,样本数,N:样本数 为m,类点;与a类点之间的距离
0 4 1 2 1 2 1 2 1 3 2 3 2 1 2 2 0 = + + 其中 为参数,- d d d d • 4、重心距离:均值间的距离 • 5、类平均距离:两类中各个元素两两之间的 距离平方相加后取平均值 = j q i p p q x x i j p q d N N D 2 1 2 为 类点 与 类点 之间的距离 其中 样本数 样本数 d i j N N i j p q p p q q : : , :
·6、离差平方和: 设N个样品原分q类,则定义第谈类的离差平 方和为: ∑(x1-x)(x-x) 其中x为样品x的均值 N为第类的样本数 离差平方和增量:设样本已分成pO2两类, 若把On0合为o类,则定义离差平方
• 6、 离差平方和: – 设N个样品原分q类,则定义第i类的离差平 方和为: – 离差平方和增量:设样本已分成ωp ,ωq两类, 若把ωp ,ωq合为ωr类,则定义离差平方: ( ) . , ( ) ( ) 1 为第 类的样本数 其中 为样品 的均值 N i x x S x x x x i i j i i i j T i N j i j q i i = − − =
DDa=S-s,+sa) 其中S,S分别为,类于m类的离差平方和 S为类的离差平方和 增量愈小,合并愈合理。 ·(2)系统聚类的算法(略) 例:如下图所示 G6 12345678910 设全部样本分为6类, 2、作距离矩阵D(O)
增量愈小,合并愈合理。 为 类的离差平方和 其中 分别为 类于 类的离差平方和 r r p q p q p q r p q S S S D S S S , , ( ) 2 = − + • (2)系统聚类的算法(略) • 例:如下图所示 • 1、设全部样本分为6类, • 2、作距离矩阵D(0) G3 G1 G2 G5 G4 G6 x
16 491664 254 364 6425811
ω 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、求最小元素:31=d64=1 4、把ω1,O3合并O7=(1,3) O406合并o3=(46) 5、作距离矩阵D(1) 7 2 49 16 25 4
• 3、求最小元素: • 4、把ω1 ,ω3合并ω7=(1,3) • ω4 ,ω6合并ω8=(4,6) • 5、作距离矩阵D(1) d31 = d64 =1 ω7 ω2 ω8 ω2 9 ω8 49 16 ω5 25 4 4