北京邮电大学信息工程学院：《模式识别导论》课程教学资源（PPT课件讲稿）第六章 聚类分析

第六章聚类分析 §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

6、若合并的类数没有达到要求,转3。 否则停止 ·3、求最小元素: d =d 52 58 4 4、O3,O502合并,O9=(2,5,4,6) 7 10 枝状图

• 6、若合并的类数没有达到要求，转3。 否则停止。 • 3、求最小元素： • 4、ω8 ,ω5 ,ω2合并, ω9 =（2,5,4,6） d52 = d58 = 4 枝状图 1 5 2 3 4 6 7 8 9 10

§6-2分解聚类 分解聚类:把全部样本作为一类,然后 根据相似性、相邻性分解 目标函数两类均值方差 E NNi( 2 x 1-2 N:总样本数,N1:o1类样本数 N2:02类样本数,x12x2:两类均值

§6-2 分解聚类 • 分解聚类：把全部样本作为一类，然后 根据相似性、相邻性分解。 • 目标函数 两类均值方差 ( ) ( ) 1 2 1 2 1 2 x x x x T N N N E = − − N：总样本数， ：ω1类样本数 ：ω2类样本数， x1, x2 :两类均值 N1 N2