模式識別導論PatternRecognition

1、第七章 非監(jiān)督學習方法王文偉 Wang Wenwei, Dr.-Ing.Tel: 687-78652Email: Web: http:/ 非監(jiān)督學習方法2Table of Contents7.1 引言7.2 單峰子集的分離方法7.3 類別分離的間接方法7.4 分級聚類方法7.5 聚類中的問題電子信息學院第七章 非監(jiān)督學習方法37.1 引言u有監(jiān)督學習（supervised learning)：用已知類別的樣本訓練分類器，以求對訓練集數(shù)據(jù)達到某種最優(yōu)，并能推廣到對新數(shù)據(jù)的分類。u非監(jiān)督學習（unsupervised learning) ：樣本數(shù)據(jù)類別未知，需要根據(jù)樣本間的相似性對樣本集進行分類(

2、聚類，clustering)第七章 非監(jiān)督學習方法4監(jiān)督與非監(jiān)督學習方法比較引言第七章 非監(jiān)督學習方法5監(jiān)督與非監(jiān)督學習方法比較u監(jiān)督學習方法必須要有訓練集與測試樣本。在訓練集中找規(guī)律，而對測試樣本使用這種規(guī)律；而非監(jiān)督學習只有一組數(shù)據(jù)，在該組數(shù)據(jù)集內尋找規(guī)律。u監(jiān)督學習方法的目的是識別事物，給待識別數(shù)據(jù)加上標號(label)。因此訓練樣本集必須由帶標號的樣本組成。而非監(jiān)督學習方法只有要分析的數(shù)據(jù)集本身，沒有標號。如果發(fā)現(xiàn)數(shù)據(jù)集呈現(xiàn)某種聚集性，則可按自然的聚集性分類，但不以與某種預先的分類標號對上號為目的。引言第七章 非監(jiān)督學習方法6主要的非監(jiān)督學習方法u基于概率密度函數(shù)估計的直接方法：設法找

3、到各類別在特征空間的分布參數(shù)再進行分類。直方圖方法。 u基于樣本間相似性度量的間接聚類方法：設法定出不同類別的核心或初始類核，然后依據(jù)樣本與這些核心之間的相似性度量將樣本聚集成不同類別。引言第七章 非監(jiān)督學習方法77.2 單峰子集的分離方法u思想：把特征空間分為若干個區(qū)域，在每個區(qū)域上混合概率密度函數(shù)是單峰的，每個單峰區(qū)域對應一個類別。u一維空間中的單峰分離: 對樣本集KN=xi應用直方圖/Parzen窗方法估計概率密度函數(shù)，找到概率密度函數(shù)的峰以及峰之間的谷底，以谷底為閾值對數(shù)據(jù)進行分割。第七章 非監(jiān)督學習方法8一維空間中的單峰子集分離直接方法1argm in()Lktp k第七章 非監(jiān)督學

4、習方法9灰度圖像二值化算法示例直接方法第七章 非監(jiān)督學習方法10多維空間投影方法u多維空間y中直接劃分成單峰區(qū)域比較困難，把它投影到一維空間x中來簡化問題。u投影方法舉例：直接方法第七章 非監(jiān)督學習方法11如何確定合適的投影方向uu使投影x=uTy的方差最大：方差越大，類之間分離的程度也可能越大u樣本協(xié)方差矩陣的最大本征值對應的本征向量滿足這樣的要求u存在問題：這樣投影有時并不能產(chǎn)生多峰的邊緣密度函數(shù)直接方法第七章 非監(jiān)督學習方法12投影方法算法步驟1.計算樣本y協(xié)方差矩陣的最大本征值對應的本征向量u，把樣本數(shù)據(jù)投影到u上，得到v=uTy2.用直方圖/Parzen窗法求邊緣概率密度函數(shù)p(v)

5、3.找到邊緣概率密度函數(shù)的各個谷點，在這些谷點上作垂直于u的超平面把數(shù)據(jù)劃分成幾個子集4.如果沒有谷點，則用下一個最大的本征值代替5.對所得到的各個子集進行同樣的過程，直至每個子集都是單峰為止直接方法第七章 非監(jiān)督學習方法13單峰子集分離的迭代算法u把樣本集KN=xi分成c個不相交子集Ki。對這樣的一個劃分可用Parzen方法估計各類的概率密度函數(shù)：1(|)(,)iiiKfKKNxxx x211(|)(|)()ccijijJfKfKpd xxxx直接方法第七章 非監(jiān)督學習方法14迭代算法步驟1.對數(shù)據(jù)集進行初始劃分，得到：K1, K2, ,Kc2.用Parzen方法估計各聚類的概率密度函數(shù)3.

6、按照最大似然概率逐個對樣本xk進行分類：4.若沒有數(shù)據(jù)點發(fā)生類別遷移變化，則停止。否則轉2argm ax(|)kikjijfKKxx直接方法(|)ifKx第七章 非監(jiān)督學習方法157.3 類別分離的間接方法u目標: 類內元素相似性高，類間元素相似性低u該類方法的兩個要點:相似性度量準則函數(shù)u相似性度量：(,)ijKx(,)() ()Tijijijx xxxxx樣本間相似性度量: 特征空間的某種距離度量樣本與樣本聚類間相似性度量第七章 非監(jiān)督學習方法16準則函數(shù)u準則函數(shù)：聚類質量的判別標準。1(,)iciiKJ yx mu常用的最小誤差平方和準則：間接方法第七章 非監(jiān)督學習方法171. C-均

7、值(k-Means, k-均值)算法u對樣本集KN=xi尚不知每個樣本的類別，但可假設所有樣本可分為C類，各類樣本在特征空間依類聚集，且近似球形分布。u用一代表點(prototype)來表示一個聚類，如類內均值mi來代表聚類Kiu聚類準則：誤差平方和J11(,)()()iiccTiiiiKiKJ xxx mxmym間接方法argm inljKlKJ第七章 非監(jiān)督學習方法18C-均值算法的步驟1.初始化：選擇c個代表點p1, p2, ,pc2.建立c個空聚類列表： K1, K2, ,Kc3.按照最小距離法則逐個對樣本x進行分類：4.計算J及用各聚類列表(Ki)計算聚類均值(pi) ，作為各聚類新

8、的代表點（更新代表點）5.若J不變或代表點未發(fā)生變化，則停止。否則轉2。argm in(,), add(,)ijijKx px1(,)iciiKJ xx p間接方法第七章 非監(jiān)督學習方法19C-均值算法舉例u彩色圖像分割：間接方法第七章 非監(jiān)督學習方法20C-均值算法的其他考慮u完成聚類后，可以用結果來分類,即按照與c個代表點的最小距離法對新樣本y進行分類，即：argm in(,),ijijy pyu初始劃分的方法u更新均值的時機：逐個樣本修正法成批樣本修正法u聚類數(shù)目的動態(tài)決定間接方法第七章 非監(jiān)督學習方法212. 樣本與聚類間相似性度量u樣本x與聚類Ki間相似性度量:u聚類的表示：樣本集K

9、i =xj(i)用一個所謂的“核函數(shù)”Ki，如樣本集的某種統(tǒng)計量(,)iKx間接方法第七章 非監(jiān)督學習方法22基于樣本與聚類間相似性度量的動態(tài)聚類算法1. 初始化：選擇c個初始聚類K1, K2, , Kc2. 建立c個空聚類列表： L1, L2, , Lc3. 按照最相似法則逐個對樣本進行分類：4. 計算J并用Li 更新各聚類核函數(shù)Ki 5. 若J不變則停止。否則轉2argm in(,), add(,)ijijKLxx1(,)iciiKJK yx間接方法第七章 非監(jiān)督學習方法23正態(tài)核函數(shù)的聚類算法u正態(tài)核函數(shù)：適用于各類為正態(tài)分布11 / 2/ 211()exp()()2(2)Tiiiidj

10、Kxxmxmu參數(shù)集Vi=mi,i為各類樣本統(tǒng)計參數(shù)u相似性度量：111(,)()()log22TiiiijK xxmxm間接方法第七章 非監(jiān)督學習方法24近鄰函數(shù)準則算法u近鄰函數(shù)：樣本間相似性的度量如果yi是yj的第I個近鄰， yj是yi的第K個近鄰 aij = I + K 2 , iju近鄰函數(shù)使得密度相近的點容易聚成一類u同一類中的點之間存在“連接”。連接損失就定義為兩點之間的近鄰函數(shù)aiju一個點和其自身的連接損失aii=2N，以懲罰只有一個點的聚類u不同類的點不存在連接，連接損失aii=0u總類內損失：11NNwijijLa 間接方法第七章 非監(jiān)督學習方法25兩類間最小近鄰函數(shù)值u

11、第i類和第j類間最小近鄰函數(shù)值定義為：,m in()kiljijklKKayym axm axm axm axm axm axm axm axm axm axm axm axm axm ax()(),ijiijjijiijjijiijiijjijijjijiijjijijijiijjaaifaaaifaabaifaaaaifaa間接方法第七章 非監(jiān)督學習方法26近鄰函數(shù)準則u總類間損失：bijijLb1.計算距離矩陣2.用距離矩陣計算近鄰矩陣3.計算近鄰函數(shù)矩陣4.在L 中，每個點與其最近鄰連接，形成初始的劃分5.對每兩個類計算rij 和aimax，ajmax ，只要rij 小于aimax、a

12、jmax中的任何一個，就合并兩類（建立連接）。重復至沒有新的連接發(fā)生為止wbJLL間接方法第七章 非監(jiān)督學習方法277.4 分級聚類方法u聚類劃分序列：N個樣本自底向上逐步合并成一類：1.每個樣本自成一類（劃分水平1）2.K水平劃分的進行：計算已有的c=N-K+2個類的類間距離矩陣D(K-1)=dij(K-1)，其最小元素記作d(K-1)，相應的兩個類合并成一類3.重復第2步，直至形成包含所有樣本的類（劃分水平N）u劃分處于K水平時，類數(shù)c=N-K+1，類間距離矩陣D(K)=dij(K)，其最小元素記作d(K)u如果d(K) 閾值dT，則說明此水平上的聚類是適宜的第七章 非監(jiān)督學習方法28分級

13、聚類樹表示方法y1y2y3y4y5y61009080706050401-水平 -2-水平 -3-水平 -4-水平 -5-水平 -6-水平 -分級聚類第七章 非監(jiān)督學習方法29兩聚類間的距離度量u聚類Ki與Kj間的距離度量最近距離：(,)m in(,)ijijKKKKxyx y最遠距離：(,)m ax(,)ijijKKKKxyx y均值距離：(,)(,)ijijKKmm分級聚類第七章 非監(jiān)督學習方法307.5 聚類中的問題u非監(jiān)督模式識別問題存在更大的不確定性: 可利用信息少相似性度量一般對數(shù)據(jù)尺度(scale)較敏感u影響聚類結果的因素：樣本的分布，樣本數(shù)量，聚類準則，相似性度量，預分類數(shù)等u

14、針對不同數(shù)據(jù)，不同目標選擇不同的聚類算法u動態(tài)聚類算法計算效率高，實際應用多第七章 非監(jiān)督學習方法31習題1.習題10.22.如果四個數(shù)據(jù)分別為：現(xiàn)有兩種聚類劃分：(1) (2) 若用最小平方誤差和準則，哪一種劃分更好？3.試用流程圖描述C-Means算法4.試小結下列相似性度量： 樣本x與樣本y間的相似性度量 樣本x與聚類K間的相似性度量 聚類Ki與聚類Kj間的相似性度量5.試說明以下問題求解是基于監(jiān)督學習或是非監(jiān)督學習。 圖像分割：圖像中道路區(qū)域與非道路區(qū)域的劃分。112234 ,KKx xx x112324 ,KKx x xx第七章 非監(jiān)督學習方法32例題解答u對于第一種劃分，有：112234551111()