北京大学：《模式识别》课程教学资源（课件讲稿）非监督学习方法（第二部分）

第八章 非监督学习方法 2010.12.20

第八章 非监督学习方法 2010.12.20

2 近邻函数准则算法 近邻函数：如y:是y的第I个近邻，则y:对y 的近邻系数为I;如y是y:的第K个近邻，则y 对y的近邻系数为K;y,和y;之间的近邻函数： a=I+K-2,i≠；&m=2N; 口连接：如y,和y,被分到同一类，则相互连接； 连接损失：两点之间的近邻函数a 如两点不 同类，则损失为0： NN 总类内损失：Lmn=∑∑a, i=1 i=l

2 近邻函数准则算法  近邻函数：如 yi是 yj的第 I 个近邻，则 yi对 yj 的近邻系数为 I；如 yj 是 yi 的第 K 个近邻，则 yj 对 yi 的近邻系数为 K；yi和 yj之间的近邻函数：  连接：如 yi 和 yj 被分到同一类，则相互连接；  连接损失：两点之间的近邻函数αij ；如两点不 同类，则损失为 0； 2, ; 2 ; ij ii   I    K i j  N 1 1 . N N within ij i j L    总类内损失：   

3 近邻函数准则算法 y为 损失 `w"W w2 w1 Vi yk 损失：0k=1+6-2=5,0x=2+1-2=1

3 近邻函数准则算法 损失： ik     ij     ;1212,5261

4 近邻函数准则算法 两类间的最小近邻函数：方m (a)月 口w与其余各类的最小近邻函数：=in': j≠1 ▣类间损失 -[(y:-aims)-(:-agmas)if 总类间损失： Yi>akimax if Y,≤1max,Y>Ck ma Yi+akmax ifY,>C1max,Y,≤k max =∑A； Yi+aimax +ak max ifY≤amax,Y1≤0 max i=1 其中Cmax、Ckmax是同一类中样本间的最大连接损失

4 近邻函数准则算法  两类间的最小近邻函数：  ωi 与其余各类的最小近邻函数：  类间损失   , min ; k il j ij ij      y y 1, , min ; i ij j c j i       =1 ; c between i i L    总类间损失：

5 近邻函数准则算法 口算法步骤 1.计算距离矩阵△，其元素△=△(yy,)月 2.用距离矩阵计算近邻矩阵M,M表示y:是y的 第几个近邻； 3计算近邻函数矩阵L,L,M,+M-2L,L2N: 4.搜索L,连接每个点与其最近邻形成初始划分； 5.对每两个类计算Y和imax? jmax' 只要Y,小 于imax' a: imax 中的任何一个，就合并两类（建 立连接)。重复至没有新的连接为止

5 近邻函数准则算法  算法步骤 1. 计算距离矩阵 ∆，其元素 2. 用距离矩阵计算近邻矩阵 M ， Mij 表示 yi 是 yj 的 第几个近邻； 3. 计算近邻函数矩阵 L ， Lij = Mij + Mji –2 I ， Lii =2 N； 4. 搜索 L，连接每个点与其最近邻形成初始划分； 5. 对每两个类计算γij 和αimax，αjmax，只要γij 小 于αimax，αjmax中的任何一个，就合并两类（建 立连接）。重复至没有新的连接为止。 );,( ij   yy ji

分级聚类方法

分级聚类方法

7 两种策略 y2 Ya y1 yo ys ya 1-水平- 100 2-水平- 3-水平- 90 4-水平- 80 5-水平- 70 性 y1,y2,y3,y4y5 6-水平 y1,y2,y3 y4,y5 y1,y2 ys y

7 两种策略

8 类间相似性度量 口最近距离(single--link): A(T,「y)=min8(x,y), yerj 口最远距离(complete--link): A(rir)=max6(x,y), yerj 口均值距离(average-link): △(T,Tj)=6(m,mj)

8 类间相似性度量  最近距离（single-link）：  最远距离（complete-link）：  均值距离（average-link）： ( , ) min ( , ), i j i j       x y x y ( , ) max ( , ), i j i j       x y x y ( , ) ( , ). ij i j     m m

9 类间相似性度量对结果的影响 Single-Link Single-Link Method ab C d Euclidean Distance (1) (2) (3) b d b d d d a 2 6 5 6 a,bi 3) a,b,c 4 3 b 4 c 4 c Distance Matrix Complete-Link Method Complete-Link Euclidean Distance ab ca (1) (2) (3) b d b d C d c.d 3 5 654 a 53 65 a,b 56 a,b6 4 4 c y Distance Matrix

9 类间相似性度量对结果的影响

10 类间相似性度量对结果的影响 0 0 0 0 0 0 00 0 (a) 。0 0 0 00 0 0 0 0 0 00 0 0 (b) (6) 0 0 0 000 0 (c) (c) (c) 三种数据分布的例子 采用最近距离作为相似性度量 采用最远距离作为相似性度量

10 类间相似性度量对结果的影响