模式識(shí)別第七章 非監(jiān)督分類

第七章非監(jiān)督學(xué)習(xí)方法1主要內(nèi)容引言單峰子集分離方法類別分離的間接方法分級(jí)聚類方法聚類中的問(wèn)題27.1引言有監(jiān)督學(xué)習(xí)（supervisedlearning)：用已知類別的樣本訓(xùn)練分類器，以求對(duì)訓(xùn)練集的數(shù)據(jù)達(dá)到某種最優(yōu)，并能推廣到對(duì)新數(shù)據(jù)的分類非監(jiān)督學(xué)習(xí)（unsupervisedlearning)：樣本數(shù)據(jù)類別未知，需要根據(jù)樣本間的相似性對(duì)樣本集進(jìn)行分類(聚類，clustering)3以前討論的分類器設(shè)計(jì)方法都是在樣本集類別已知的條件下進(jìn)行的，這些樣本稱為訓(xùn)練樣本。統(tǒng)計(jì)出各類訓(xùn)練樣本不同的描述量，如概率分布等，并利用這些參數(shù)進(jìn)行分類器設(shè)計(jì)，稱為有監(jiān)督的學(xué)習(xí)方法。當(dāng)樣本的類別未知，沒(méi)有訓(xùn)練樣本，因而只能從未知樣本類別樣本集進(jìn)行分類器設(shè)計(jì)，這就是通常說(shuō)的無(wú)監(jiān)督學(xué)習(xí)方法。4方案對(duì)比5非監(jiān)督學(xué)習(xí)與有監(jiān)督學(xué)習(xí)方法的區(qū)別有監(jiān)督學(xué)習(xí)必須有訓(xùn)練集與測(cè)試樣本。在訓(xùn)練集中找規(guī)律，而對(duì)測(cè)試樣本使用這種規(guī)律；非監(jiān)督學(xué)習(xí)沒(méi)有訓(xùn)練集，只有一組數(shù)據(jù)，在該組數(shù)據(jù)集內(nèi)尋找規(guī)律。有監(jiān)督學(xué)習(xí)方法的目的是識(shí)別事物，識(shí)別的結(jié)果表現(xiàn)在給待識(shí)別數(shù)據(jù)加上了標(biāo)號(hào)。因此訓(xùn)練樣本集必須由帶標(biāo)號(hào)樣本組成；非監(jiān)督學(xué)習(xí)方法只有分析數(shù)據(jù)集本身，無(wú)標(biāo)號(hào)。如果發(fā)現(xiàn)數(shù)據(jù)集呈現(xiàn)某種聚集性，則可按自然的聚集性分類，但不以與某種預(yù)先的分類標(biāo)號(hào)為目的。6非監(jiān)督學(xué)習(xí)方法可以分成兩大類：基于概率密度函數(shù)估計(jì)的直接方法：設(shè)法找到各類別在特征空間的分布參數(shù)再進(jìn)行分類；基于樣本間相似性度量的間接聚類方法。其原理是設(shè)法定出不同類別的核心或初始類核，然后依據(jù)樣本與這些核心之間的相似性度量將樣本聚集成不同類別。7基于概率密度函數(shù)估計(jì)的直接方法前提：無(wú)類條件概率分布先驗(yàn)知識(shí)思想：把特征空間分為若干個(gè)區(qū)域，每個(gè)區(qū)域上混合概率密度函數(shù)為單峰，每個(gè)單峰區(qū)域?qū)?yīng)一個(gè)類。關(guān)鍵：找出各個(gè)峰值區(qū)。一維空間中的單峰分離:對(duì)樣本集KN={xi}應(yīng)用直方圖方法估計(jì)概率密度函數(shù)，找到概率密度函數(shù)的峰以及峰之間的谷底，以谷底為閾值對(duì)數(shù)據(jù)進(jìn)行分割。7.2單峰子集的分離方法8樣本在整個(gè)特征空間中呈現(xiàn)兩個(gè)分布高峰。如果從分布的谷點(diǎn)將此特征空間劃分為兩個(gè)區(qū)，則對(duì)應(yīng)每個(gè)區(qū)域，樣本分布就只有一個(gè)峰值，這些區(qū)域被稱為單峰區(qū)域。每個(gè)單峰區(qū)域看作一個(gè)不同的決策域。落在同一單峰區(qū)域的待分類樣本就被劃分成同一類，稱為單峰子類。9（1）多維空間投影方法多維空間y中直接劃分成單峰區(qū)域比較困難，把它投影到一維空間x中簡(jiǎn)化問(wèn)題。10對(duì)于樣本在某一種度量中的分布統(tǒng)計(jì)，一般稱為直方圖統(tǒng)計(jì)，在樣本數(shù)量很大時(shí)，又可作為概率統(tǒng)計(jì)的估計(jì)。由于這種方法基于將樣本投影到某個(gè)坐標(biāo)軸上，因而稱為投影方法。使用投影方法有兩個(gè)組成部分一是如何設(shè)計(jì)合適的坐標(biāo)系統(tǒng)。二是如何設(shè)計(jì)直方圖。（1）多維空間投影方法11在樣本屬性完全不知的情況下，如何選擇坐標(biāo)系統(tǒng)比較困難。目前還沒(méi)有一個(gè)準(zhǔn)則函數(shù)來(lái)表征這樣坐標(biāo)系統(tǒng)的性質(zhì)。一種啟發(fā)式的辦法是使待分類的樣本在某個(gè)坐標(biāo)軸方向具有最大的分散性，可采用K-L變換方法。（1）多維空間投影方法12用混合樣本協(xié)方差矩陣作為K-L變換的產(chǎn)生矩陣，找到其特征值，并按大小排序。對(duì)應(yīng)最大特征值的特征向量對(duì)此混合樣本來(lái)說(shuō)，離散程度最大，預(yù)期能發(fā)現(xiàn)明顯的峰值，但是這樣投影有時(shí)并不能產(chǎn)生多峰的邊緣密度函數(shù)，因而并不能保證分出各個(gè)聚類。（1）多維空間投影方法1314（1）投影方法算法步驟計(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è)子集；如果沒(méi)有谷點(diǎn)，則用下一個(gè)最大的特征值代替；對(duì)所得到的各個(gè)子集進(jìn)行同樣的過(guò)程，直至每個(gè)子集都是單峰為止。15（2）單峰子集分離的迭代算法把樣本集KN={xi}分成c個(gè)不相交子集Ki。每個(gè)劃分可用Parzen方法估計(jì)各類的概率密度函數(shù)：聚類準(zhǔn)則：合理的劃分應(yīng)使下式最大16迭代算法步驟對(duì)數(shù)據(jù)集進(jìn)行初始劃分：K1,K2,…,Kc用Parzen方法估計(jì)各聚類的概率密度函數(shù)按照最大似然概率逐個(gè)對(duì)樣本xk進(jìn)行分類：

若沒(méi)有數(shù)據(jù)點(diǎn)發(fā)生類別遷移變化，則停止。否則轉(zhuǎn)2（2）單峰子集分離的迭代算法177.3類別分離的間接方法兩個(gè)要點(diǎn):相似性度量，準(zhǔn)則函數(shù)相似性度量樣本間相似性度量:特征空間的某種距離度量樣本與樣本聚類間相似性度量18準(zhǔn)則函數(shù)準(zhǔn)則函數(shù)：聚類質(zhì)量的判別標(biāo)準(zhǔn)，常用的最小誤差平方和準(zhǔn)則目標(biāo):類內(nèi)元素相似性高，類間元素相似性低19聚類方法按相似度進(jìn)行劃分的方法，原理很簡(jiǎn)單。如果把相似度表示成在特征空間中的某種距離度量,這種方法又稱為基于距離度量的方法。與前一種方法相比，它不是以計(jì)算密度為依據(jù)的，這是這兩種方法的主要區(qū)別。不通過(guò)對(duì)概率密度函數(shù)作出估計(jì)而直接按樣本間的相似性，或彼此間在特征空間中的距離長(zhǎng)短進(jìn)行分類，這種方法稱為聚類方法。20如何聚類則取決于聚類的準(zhǔn)則函數(shù)，以便某種聚類準(zhǔn)則達(dá)到極值為最佳。兩種聚類的方法：迭代的動(dòng)態(tài)聚類算法非迭代的分級(jí)聚類算法聚類方法21動(dòng)態(tài)聚類方法的任務(wù)是將數(shù)據(jù)集劃分成一定數(shù)量的子集。要解決的問(wèn)題:如何確定數(shù)據(jù)集應(yīng)該劃分的子集數(shù)目若劃分?jǐn)?shù)目已定，則又如何找到最佳劃分。聚類方法22（1）動(dòng)態(tài)聚類方法數(shù)據(jù)集可以有許多種不同的劃分方法，因此需要對(duì)不同的劃分作出評(píng)價(jià)，并找到優(yōu)化的劃分結(jié)果。由于優(yōu)化過(guò)程是從“不合理的”劃分到“最佳”劃分，是一個(gè)動(dòng)態(tài)的迭代過(guò)程，故這種方法稱為動(dòng)態(tài)聚類方法。這里討論子集數(shù)目已知條件下的聚類方法，如何確定合理的子集數(shù)目？23動(dòng)態(tài)聚類方法要點(diǎn)選定某種距離度量作為樣本間的相似性度量；確定樣本合理的初始分類，包括代表點(diǎn)的選擇，初始分類的方法選擇等；確定某種評(píng)價(jià)聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)，用以調(diào)整初始分類直至達(dá)到該準(zhǔn)則函數(shù)的極值。24K-均值算法（k-Means)對(duì)樣本集KN={xi}尚不知每個(gè)樣本的類別，但可假設(shè)所有樣本可分為c類，各類樣本在特征空間依類聚集，且近似球形分布用一代表點(diǎn)來(lái)表示一個(gè)聚類，如類內(nèi)均值mi來(lái)代表聚類Ki聚類準(zhǔn)則：誤差平方和J25K-均值算法的訓(xùn)練初始化：選擇c個(gè)代表點(diǎn)p1,p2,…,pc建立c個(gè)空聚類列表：K1,K2,…,Kc按照最小距離法則逐個(gè)對(duì)樣本x進(jìn)行分類：

計(jì)算J及用各聚類列表計(jì)算聚類均值，并用來(lái)作為各聚類新的代表點(diǎn)（更新代表點(diǎn)）若J不變或代表點(diǎn)未發(fā)生變化，則停止。否則轉(zhuǎn)2。2627K-均值算法舉例彩色圖像分割：28K-均值算法的其他考慮按照與c個(gè)代表點(diǎn)的最小距離法對(duì)新樣本y進(jìn)行分類，即：初始劃分的方法更新均值的時(shí)機(jī)：逐個(gè)樣本修正法與成批樣本修正法聚類數(shù)目的動(dòng)態(tài)決定29ISODATA算法ISODATA算法的功能與k-均值算法相比，在下列幾方面有改進(jìn)?？紤]了類別的合并與分裂，因而有了自我調(diào)整類別數(shù)的能力。合并主要發(fā)生在某一類內(nèi)樣本個(gè)數(shù)太少的情況，或兩類聚類中心之間距離太小的情況。算法有自我調(diào)整的能力.30ISODATA算法(迭代自組織數(shù)據(jù)分析算法）ISODATA算法與K均值算法有相似之處，即聚類中心根據(jù)樣本的均值來(lái)修改。不同的是，這種算法進(jìn)行的過(guò)程中聚類中心的數(shù)目不是固定不變而是反復(fù)進(jìn)行修改。聚類既有合并也有分裂，合并與分裂是在一組預(yù)先選定的參數(shù)指導(dǎo)下進(jìn)行的。此外，一些經(jīng)驗(yàn)結(jié)果也包含在算法中。

ISODATA算法共分十四步。其中第一步到第六步是預(yù)選參數(shù)、進(jìn)行初始分類，并為合并和分裂準(zhǔn)備必要的數(shù)據(jù)；第七步?jīng)Q定下一步是進(jìn)行合并還是進(jìn)行分裂；第八步到第十步是分裂算法，第十一步到第十三步是合并算法，第十四步?jīng)Q定算法是否結(jié)束。算法的具體步驟如下：31ISODATA算法設(shè)有N個(gè)樣本模式X1，X2，……XN.第一步：預(yù)選NC個(gè)聚類中心Z1，Z2，……ZNC,NC不要求等于希望的聚類數(shù)目。NC個(gè)聚類中心也可在N個(gè)樣本中選擇。然后預(yù)選下列指標(biāo)：K：K是希望的聚類中心的數(shù)目。θN

：每個(gè)聚類中最少的樣本數(shù)。若某聚類中的樣本少θN

，則該聚類不能作為一個(gè)獨(dú)立的聚類，應(yīng)刪去。θS

：一個(gè)聚類中樣本的標(biāo)準(zhǔn)偏差參數(shù)。要求每一個(gè)聚類內(nèi)標(biāo)準(zhǔn)偏差向量的所有分量中的最大分量小于θS

，否則該類應(yīng)分裂為兩類。標(biāo)準(zhǔn)偏差向量的每一分量等于每個(gè)樣本的分量與聚類中心對(duì)應(yīng)分量差的平方和平均值。θC

：兩聚類中心之間的最小距離。若兩類中心之間距離小于θC

，則這兩類合并為一類。L：在一次迭代中允許合并的聚類中心的最大對(duì)數(shù)。I：允許迭代的次數(shù)。32第二步：把N個(gè)樣本按最近鄰規(guī)則分配到Nc個(gè)聚類中。第三步：若Sj中的樣本數(shù)Nj<θN

，則取消該類，并且NC－1。第四步：修正各聚類中心。第五步：計(jì)算聚類Sj中各樣本到該類聚類中心的平均距離，用表示：ISODATA算法33第六步：計(jì)算全部樣本到其所在類聚類中心距離的平均距離。即計(jì)算全部樣本的總體平均距離，用表示。第七步：判決是進(jìn)行分裂還是進(jìn)行合并，決定迭代步驟等。(1)如迭代已達(dá)I次，即最后一次迭代，置QC＝0，跳到第十一步。ISODATA算法34(2)若NC≤K/2(聚類中心小于或等于希望數(shù)的一半)，進(jìn)入第八步，將已有的聚類分裂。(3)如果迭代的次數(shù)是偶數(shù)，或NC≥2K(聚類中心數(shù)目大于或等于希望數(shù)的兩倍)，則跳到第十一步，進(jìn)行合并。否則進(jìn)入第八步進(jìn)行分裂。第八步：計(jì)算每個(gè)聚類的標(biāo)準(zhǔn)偏差向量，第Sj類的標(biāo)準(zhǔn)偏差向量為：

式中，xij是Sj類樣本X的第i個(gè)分量，zij是Zj的第i個(gè)分量。所以σij是X的第i個(gè)分量的標(biāo)準(zhǔn)差，X是n維模式向量。ISODATA算法35第九步：求每個(gè)標(biāo)準(zhǔn)差向量的最大分量，σj的最大分量記為σjmax

，j＝1,2,…,NC.第十步：在最大分量集{σjmax,j=1,2,…NC}中,如有σjmax>θS，(即Sj類樣本在σjmax對(duì)應(yīng)方向上的標(biāo)準(zhǔn)偏差大于允許的值），同時(shí)又滿足以下兩條之一：(1)和Nj>2(θN

＋1)，即類內(nèi)平均距離大于總體平均距離，并且Sj類中樣本數(shù)很大。(2)NC≤K/2,即聚類數(shù)小于或等于希望數(shù)目的一半。本步完成后，跳回第二步，且迭代次數(shù)加1。ISODATA算法36第十一步：計(jì)算所有聚類中心之間的距離。Si類和Sj類中心間的距離為第十二步：比較所有Dij與θC的值，將小于θC的Dij按升序排列：{Di1j1,Di2j2

,…,DiLjL}其中，Di1j1<Di2j2

<…<DiLjL

，L為允許每次合并的聚類中心的最大對(duì)數(shù)。第十三步：如將距離為Diljl的兩類合并，得到新的聚類中心為：每合并一對(duì)，NC減1。ISODATA算法37第十四步：若是最后一次迭代，即迭代次數(shù)為I，算法結(jié)束；若需修改參數(shù)，則跳到第一步，然后重復(fù)上述算法。否則,跳到第二步，繼續(xù)進(jìn)行迭代運(yùn)算。在本步運(yùn)算里，迭代運(yùn)算的次數(shù)加1。ISODATA算法38例：設(shè)有N=8個(gè)樣本模式，它們分別為X1=[0,0]t X2=[1,1]t X3=[2,2]tX4=[3,4]t X5=[3,5]t X6=[4,4]tX7=[4,5]t X8=[5,6]t

用ISODATA算法對(duì)這些樣本進(jìn)行分類。第一步：選NC=1,Z1=X1=[0,0]t。各參數(shù)預(yù)選為：K＝2，θN

＝1，θS

＝1，θC

＝4，L=0,I=4.第二步：只有一個(gè)聚類中心Z1，故

S1={X1,X2,…,X8}N1=8第三步：因N1>θN故無(wú)聚類可刪除。ISODATA算法39第四步：修改聚類中心，第五步：計(jì)算第六步：計(jì)算。因只有一類，故第七步：因不是最后一次迭代，且NC＝K/2，故進(jìn)入第八步進(jìn)行分裂運(yùn)算。40第八步：求S1的標(biāo)準(zhǔn)偏差向量σ1，得

σ1=[1.99,1.56]t第九步：σ1的最大分量是1.99，因此，

σ1max＝

1.99第十步：因σ1max>

θS且NC＝K/2，可將Z1分裂為兩個(gè)新的聚類中心。因σ1max是σ1的第一個(gè)分量，即S1中樣本分布在X的第一個(gè)分量方向上較分散，故分裂應(yīng)在Z1的第一個(gè)分量方向上進(jìn)行。分裂系數(shù)k選為0.5，得41為了方便，令。這一步之后，NC加1，迭代次數(shù)加1，即下面進(jìn)行第2次迭代運(yùn)算。跳回到第二步。第二步：按最近鄰規(guī)則對(duì)所有樣本聚類，得到兩個(gè)聚類分別為S1={X4,X5,X6,X7,X8}S2={X1,X2,X3}N1=5，N2=3第三步：因N1和N2都大于θN

，無(wú)聚類可以刪除。第四步：修改聚類中心，得42第五步：計(jì)算和，得第六步：計(jì)算，得第七步：因這是偶數(shù)次迭代，符合第七步的第(3)條，故進(jìn)入第十一步。第十一步：計(jì)算聚類之間距離，得43第十二步：比較D12與θC

，這里D12>

θC

。第十三步：根據(jù)第十二步的結(jié)果，聚類中心不能發(fā)生合并。第十四步：因?yàn)椴皇亲詈笠淮蔚枰袛嗍欠褚薷慕o定的參數(shù)。但前面的迭代運(yùn)算結(jié)果已得到希望的聚類數(shù)目；聚類之間分散程度大于類內(nèi)樣本的標(biāo)準(zhǔn)差；每一聚類中樣本數(shù)目都具有樣本總數(shù)的足夠大的百分比，且兩類樣本數(shù)相差不大，故可不必修改參數(shù)。因此，回到第二步，且迭代次數(shù)加1。第二步到第六步：與前一次迭代運(yùn)算的結(jié)果相同。第七步：沒(méi)有一種情況被滿足，繼續(xù)執(zhí)行第八步。44第八步：計(jì)算S1和S2的標(biāo)準(zhǔn)偏差向量σ1和σ2

。這時(shí)S1和S2仍為S1={X4,X5,X6,X7,X8}S2={X1,X2,X3}計(jì)算結(jié)果為：σ1=[0.75,0.75]tσ2=[0.82,0.82]t第九步：σ1max

＝0.75，σ2max

＝0.82第十步：分裂條件不滿足，故繼續(xù)執(zhí)行第十一步。45第十一步：計(jì)算聚類中心之間的距離，結(jié)果與前次迭代計(jì)算結(jié)果相同。第十二步、十三步：與前一次迭代結(jié)果相同。第十四步：因不是最后一次迭代，且不需修改參數(shù)，故返回第二步。迭代次數(shù)加1。第二到第六步：與前一次迭代結(jié)果相同。第七步：因?yàn)槭亲詈笠淮蔚?，置θC

＝0，跳到第十一步。第十一步：第十二步：與前一次迭代結(jié)果相同。第十三步：沒(méi)有合并發(fā)生。第十四步：最后一次迭代，故算法結(jié)束。46樣本與聚類間相似性度量樣本x與聚類Ki間相似性度量:聚類的表示：樣本集Ki

={xj(i)}用一個(gè)所謂的“核函數(shù)”Ki，如樣本集的某種統(tǒng)計(jì)量47樣本與聚類間相似性度量基于樣本與聚類間相似性度量的動(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)248正態(tài)核函數(shù)，適用于各類為正態(tài)分布參數(shù)集Vi={mi,Σi}為各類樣本統(tǒng)計(jì)參數(shù)相似性度量：樣本與聚類間相似性度量49主軸核函數(shù)：適合于各類樣本集中在各自的主軸方向上的子空間里的情況。樣本協(xié)方差矩陣的前dj個(gè)最大特征值對(duì)應(yīng)的特征向量基樣本到主軸子空間的距離：樣本與聚類間相似性度量50樣本和核相似性度量的聚類方法特點(diǎn)：可以擬合各種形狀的分布；需要預(yù)先知道數(shù)據(jù)的分布形狀當(dāng)不能預(yù)先知道數(shù)據(jù)的分布形狀時(shí)，如何處理？51（2）近鄰函數(shù)準(zhǔn)則算法近鄰函數(shù)：樣本間相似性的度量

如果yi是yj的第I個(gè)近鄰，yj是yi的第K個(gè)近鄰，記aij=I+K?2,i≠j近鄰函數(shù)使得密度相近的點(diǎn)容易聚成一類同一類中的點(diǎn)之間存在“連接”。連接損失就定義為兩點(diǎn)之間的近鄰函數(shù)aij一個(gè)點(diǎn)和其自身的連接損失aii=2N，以懲罰只有一個(gè)點(diǎn)的聚類不同類的點(diǎn)不存在連接，連接損失aij=0總類內(nèi)損失：52兩類間最小近鄰函數(shù)值第i類和第j類間最小近鄰函數(shù)值定義為：第i類內(nèi)最大連接損失記為：aimax第i類與第j類之間的連接損失定義為bij，它的設(shè)計(jì)目標(biāo)是：如果兩類間的最小近鄰值小于或等于任何一方的類內(nèi)的最大連接損失時(shí)，損失代價(jià)就是正的，從而應(yīng)該考慮把這兩類合并。53近鄰函數(shù)準(zhǔn)則總類間損失：準(zhǔn)則函數(shù)：算法步驟：計(jì)算距離矩陣用距離矩陣計(jì)算近鄰矩陣M計(jì)算近鄰函數(shù)矩陣L在L中，每個(gè)點(diǎn)與其最近鄰連接，形成初始的劃分對(duì)每?jī)蓚€(gè)類計(jì)算rij

和aimax，ajmax

，只要rij

小于aimax、ajmax中的任何一個(gè)，就合并兩類（建立連接）。重復(fù)至沒(méi)有新的連接發(fā)生為止。547.4分級(jí)聚類方法劃分序列：N個(gè)樣本自底向上逐步合并一類：每個(gè)樣本自成一類（劃分水平1）K水平劃分的進(jìn)行