1、IPL第七章 非監(jiān)督學(xué)習(xí)方法模式識(shí)別理論及應(yīng)用Pattern Recognition - Methods and Application內(nèi)容目錄IPL第七章 非監(jiān)督學(xué)習(xí)方法 7.1 引言3245 7.2 單峰子集的分離方法7.3 類別分離的間接方法7.4 分級(jí)聚類方法7.5 聚類中的問題1模式識(shí)別與神經(jīng)網(wǎng)絡(luò)第七章 非監(jiān)督學(xué)習(xí)方法37.1 引言有監(jiān)督學(xué)習(xí)（supervised learning)：用已知類別的樣本訓(xùn)練分類器，以求對(duì)訓(xùn)練集的數(shù)據(jù)達(dá)到某種最優(yōu)，并能推廣到對(duì)新數(shù)據(jù)的分類非監(jiān)督學(xué)習(xí)（unsupervised learning) ：樣本數(shù)據(jù)類別未知，需要根據(jù)樣本間的相似性對(duì)樣本集進(jìn)行分類(

2、聚類，clustering)非監(jiān)督學(xué)習(xí)方法大致分為兩大類：基于概率密度函數(shù)估計(jì)的方法基于樣本間相似性度量的方法第七章 非監(jiān)督學(xué)習(xí)方法4方案對(duì)比 第七章 非監(jiān)督學(xué)習(xí)方法57.2 單峰子集的分離方法思想：把特征空間分為若干個(gè)區(qū)域，在每個(gè)區(qū)域上混合概率密度函數(shù)是單峰的，每個(gè)單峰區(qū)域?qū)?yīng)一個(gè)類一維空間中的單峰分離: 對(duì)樣本集KN=xi應(yīng)用直方圖方法估計(jì)概率密度函數(shù)，找到概率密度函數(shù)的峰以及峰之間的谷底，以谷底為閾值對(duì)數(shù)據(jù)進(jìn)行分割第七章 非監(jiān)督學(xué)習(xí)方法6一維空間中的單峰子集分離概率密度分析第七章 非監(jiān)督學(xué)習(xí)方法7多維空間投影方法多維空間y中直接劃分成單峰區(qū)域比較困難，把它投影到一維空間x中簡(jiǎn)化問題。確定

3、合適的投影方向u：使投影x=uTy的方差最大，方差越大，類之間分離的程度也可能越大樣本協(xié)方差矩陣的最大特征值對(duì)應(yīng)的特征向量滿足這樣的要求存在問題：這樣投影有時(shí)并不能產(chǎn)生多峰的邊緣密度函數(shù)概率密度分析第七章 非監(jiān)督學(xué)習(xí)方法8投影方法舉例第七章 非監(jiān)督學(xué)習(xí)方法9投影方法算法步驟計(jì)算樣本y協(xié)方差矩陣的最大特征值對(duì)應(yīng)的特征向量u，把樣本數(shù)據(jù)投影到u上，得到v=uTy用直方圖法求邊緣概率密度函數(shù)p(v)找到邊緣概率密度函數(shù)的各個(gè)谷點(diǎn)，在這些谷點(diǎn)上作垂直于u的超平面把數(shù)據(jù)劃分成幾個(gè)子集如果沒有谷點(diǎn)，則用下一個(gè)最大的特征值代替對(duì)所得到的各個(gè)子集進(jìn)行同樣的過程，直至每個(gè)子集都是單峰為止概率密度分析第七章 非監(jiān)

4、督學(xué)習(xí)方法10灰度圖像二值化算法灰度圖像閾值:概率密度分析第七章 非監(jiān)督學(xué)習(xí)方法11單峰子集分離的迭代算法概率密度分析把樣本集KN=xi分成c個(gè)不相交子集Ki。用這樣的一個(gè)劃分可用Parzon方法估計(jì)各類的概率密度函數(shù)：聚類準(zhǔn)則：即理想的劃分應(yīng)使下式最大第七章 非監(jiān)督學(xué)習(xí)方法12迭代算法步驟概率密度分析對(duì)數(shù)據(jù)集進(jìn)行初始劃分：K1, K2, ,Kc用Parzon方法估計(jì)各聚類的概率密度函數(shù)按照最大似然概率逐個(gè)對(duì)樣本xk進(jìn)行分類：若沒有數(shù)據(jù)點(diǎn)發(fā)生類別遷移變化，則停止。否則轉(zhuǎn)2第七章 非監(jiān)督學(xué)習(xí)方法137.3 類別分離的間接方法兩個(gè)要點(diǎn):相似性度量，準(zhǔn)則函數(shù)相似性度量樣本間相似性度量: 特征空間的某

5、種距離度量樣本與樣本聚類間相似性度量第七章 非監(jiān)督學(xué)習(xí)方法14準(zhǔn)則函數(shù)準(zhǔn)則函數(shù)：聚類質(zhì)量的判別標(biāo)準(zhǔn)，常用的最小誤差平方和準(zhǔn)則目標(biāo): 類內(nèi)元素相似性高，類間元素相似性低第七章 非監(jiān)督學(xué)習(xí)方法15C-均值算法（k-Means, k-均值)對(duì)樣本集KN=xi尚不知每個(gè)樣本的類別，但可假設(shè)所有樣本可分為c類，各類樣本在特征空間依類聚集，且近似球形分布用一代表點(diǎn)(prototype)來表示一個(gè)聚類，如類內(nèi)均值mi來代表聚類Ki聚類準(zhǔn)則：誤差平方和J相似性分析第七章 非監(jiān)督學(xué)習(xí)方法16C-均值算法的訓(xùn)練初始化：選擇c個(gè)代表點(diǎn)p1, p2, ,pc建立c個(gè)空聚類列表： K1, K2, ,Kc按照最小距離法則

6、逐個(gè)對(duì)樣本x進(jìn)行分類：計(jì)算J及用各聚類列表計(jì)算聚類均值，并用來作為各聚類新的代表點(diǎn)（更新代表點(diǎn)）若J不變或代表點(diǎn)未發(fā)生變化，則停止。否則轉(zhuǎn)2。相似性分析第七章 非監(jiān)督學(xué)習(xí)方法18C-均值算法舉例彩色圖像分割：第七章 非監(jiān)督學(xué)習(xí)方法19C-均值算法的其他考慮按照與c個(gè)代表點(diǎn)的最小距離法對(duì)新樣本y進(jìn)行分類，即：初始劃分的方法更新均值的時(shí)機(jī)：逐個(gè)樣本修正法與成批樣本修正法聚類數(shù)目的動(dòng)態(tài)決定相似性分析第七章 非監(jiān)督學(xué)習(xí)方法20樣本與聚類間相似性度量樣本x與聚類Ki間相似性度量:聚類的表示：樣本集Ki =xj(i)用一個(gè)所謂的“核函數(shù)”Ki，如樣本集的某種統(tǒng)計(jì)量相似性分析第七章 非監(jiān)督學(xué)習(xí)方法21樣本與

7、聚類間相似性度量基于樣本與聚類間相似性度量的動(dòng)態(tài)聚類算法初始化：選擇c個(gè)初始聚類K1, K2, , Kc建立c個(gè)空聚類列表： L1, L2, , Lc按照最相似法則逐個(gè)對(duì)樣本進(jìn)行分類：計(jì)算J并用Li 更新各聚類核函數(shù)Ki 若J不變則停止。否則轉(zhuǎn)2相似性分析第七章 非監(jiān)督學(xué)習(xí)方法22正態(tài)核函數(shù)的聚類算法正態(tài)核函數(shù)，適用于各類為正態(tài)分布相似性分析參數(shù)集Vi=mi,i為各類樣本統(tǒng)計(jì)參數(shù)相似性度量：第七章 非監(jiān)督學(xué)習(xí)方法23近鄰函數(shù)準(zhǔn)則算法近鄰函數(shù)：樣本間相似性的度量如果yi是yj的第I個(gè)近鄰， yj是yi的第K個(gè)近鄰 aij = I + K 2 , ij近鄰函數(shù)使得密度相近的點(diǎn)容易聚成一類同一類中的

8、點(diǎn)之間存在“連接”。連接損失就定義為兩點(diǎn)之間的近鄰函數(shù)aij一個(gè)點(diǎn)和其自身的連接損失aii=2N，以懲罰只有一個(gè)點(diǎn)的聚類不同類的點(diǎn)不存在連接，連接損失aii=0總類內(nèi)損失：相似性分析第七章 非監(jiān)督學(xué)習(xí)方法24兩類間最小近鄰函數(shù)值第i類和第j類間最小近鄰函數(shù)值定義為：相似性分析第i類內(nèi)最大連接損失記為： aimax第i類與第j類之間的連接損失定義為bij，它的設(shè)計(jì)目標(biāo)是：如果兩類間的最小近鄰值大于任何一方的類內(nèi)的最大連接損失時(shí)，損失代價(jià)就是正的，從而應(yīng)該考慮把這兩類合并第七章 非監(jiān)督學(xué)習(xí)方法25近鄰函數(shù)準(zhǔn)則總類間損失：相似性分析準(zhǔn)則函數(shù)：算法步驟：計(jì)算距離矩陣用距離矩陣計(jì)算近鄰矩陣計(jì)算近鄰函數(shù)矩

9、陣在L 中，每個(gè)點(diǎn)與其最近鄰連接，形成初始的劃分對(duì)每兩個(gè)類計(jì)算rij 和aimax，ajmax ，只要rij 小于aimax、ajmax中的任何一個(gè)，就合并兩類（建立連接）。重復(fù)至沒有新的連接發(fā)生為止第七章 非監(jiān)督學(xué)習(xí)方法267.4 分級(jí)聚類方法劃分序列：N個(gè)樣本自底向上逐步合并一類：每個(gè)樣本自成一類（劃分水平1）K水平劃分的進(jìn)行：計(jì)算已有的c=N-K+2個(gè)類的類間距離矩陣D(K-1)=dij(K-1)，其最小元素記作d(K-1)，相應(yīng)的兩個(gè)類合并成一類重復(fù)第2步，直至形成包含所有樣本的類（劃分水平N）劃分處于K水平時(shí)，類數(shù)c=N-K+1，類間距離矩陣D(K)=dij(K)，其最小元素記作d(K)如果d(K) 閾值dT，則說明此水平上的聚類是適宜的第七章 非監(jiān)督學(xué)習(xí)方法27分級(jí)聚類樹表示方法y1y2y3y4y5y61009080706050401-水平 -2-水平 -3-水平 -4-水平 -5-水平 -6-水平 -分級(jí)聚類第七章 非監(jiān)督學(xué)習(xí)方法28兩聚類間的距離度量聚類Ki與Kj間的距離度量最近距離：最遠(yuǎn)距離：均值距離：分級(jí)聚類第七章 非監(jiān)督學(xué)習(xí)方法297.5 聚類中的問題非監(jiān)督模式識(shí)別問題存在更大的不確定性: 可利用信息少相似性度量一般對(duì)數(shù)據(jù)尺度(scale)較敏感影響聚類結(jié)果的因素：樣本的分布，樣