模式識(shí)別-聚類分析(集群)

模式識(shí)別

PatternClassification

第七章:聚類分析（集群）基本概念有師識(shí)別：由學(xué)習(xí)過程和識(shí)別過程兩部分組成，且用于學(xué)習(xí)的樣本類別是已知的。無師識(shí)別：缺少樣本類別的先驗(yàn)知識(shí)，在樣本類別未知的情況下進(jìn)行分類（非監(jiān)督學(xué)習(xí)方法）應(yīng)用：語音識(shí)別、圖像分割、遙感圖像分類、數(shù)據(jù)挖掘3AppliedPatternRecognitionCSE616基本概念聚類（集群）：根據(jù)模式之間的相似度（相似程度）對(duì)模式進(jìn)行無師識(shí)別的方法相似度：衡量模式之間相似程度的尺度。聚類準(zhǔn)則：聚類分析的同一類模式相似程度的標(biāo)準(zhǔn)或不同類模式差異程度的標(biāo)準(zhǔn)。聚類效果取決于模式的特征空間中的分布！4AppliedPatternRecognitionCSE616相似度測(cè)量相似度測(cè)量歐氏距離（衡量兩個(gè)樣本之間的距離）設(shè)x１,x２為d維特征空間的模式向量，則歐氏距離直觀地反映了兩個(gè)樣本的相似程度5AppliedPatternRecognitionCSE616相似度測(cè)量馬氏距離（衡量單個(gè)樣本與某類樣本，或兩類樣本之間的距離）

6AppliedPatternRecognitionCSE616相似度測(cè)量設(shè)x為某樣本，則該樣本與均值向量為μ，協(xié)方差矩陣Σ為的模式類的馬氏距離為：

7AppliedPatternRecognitionCSE616相似度測(cè)量Ｄ１Ｄ２馬氏距離與樣本與均值向量之間的距離成正比8AppliedPatternRecognitionCSE616相似度測(cè)量馬氏距離與協(xié)方差成反比9AppliedPatternRecognitionCSE616相似度測(cè)量而均值分別為μ1和μ2，協(xié)方差為Σ的兩模式類的馬氏距離為：

10AppliedPatternRecognitionCSE616聚類準(zhǔn)則聚類準(zhǔn)則的類型聚類準(zhǔn)則閥值準(zhǔn)則函數(shù)準(zhǔn)則11AppliedPatternRecognitionCSE616聚類準(zhǔn)則閥值準(zhǔn)則根據(jù)規(guī)定的距離閥值或類別數(shù)進(jìn)行分類函數(shù)準(zhǔn)則定義一個(gè)準(zhǔn)則函數(shù)，把聚類分析問題轉(zhuǎn)化為準(zhǔn)則函數(shù)求極值的問題12AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法合并聚類法定義樣本間的距離：歐氏距離定義類與類之間的距離：近點(diǎn)距離（最短距離）遠(yuǎn)點(diǎn)距離（最長距離）均值距離馬氏距離13AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法最近距離14AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法最遠(yuǎn)距離15AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法均值距離16AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法合并聚類法首先假設(shè)每個(gè)樣本自成一類，并計(jì)算各類之間的距離。然后將具有最近距離的兩類樣本合并成一類重復(fù)上述過程，直至合并的類別數(shù)等于給定的數(shù)目，或各類別間的距離大于某規(guī)定的距離閥值為止

17AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法合并聚類法18AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法合并聚類法-聚為3類19AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法合并聚類法-聚為2類基于閥值準(zhǔn)則的聚類方法

C-均值算法（動(dòng)態(tài)聚類法）指定群數(shù)C，選取C個(gè)代表點(diǎn)作為群的聚類中心。（可選各類的均值位置為聚類中心）遍歷所有的樣本，將每個(gè)樣本歸入與之最近的聚類中心所的代表的群（成批樣本修正法）重新計(jì)算C個(gè)群的中心，將其作為各群新的聚類中心，重復(fù)第2步，直至分類結(jié)果不變逐個(gè)樣本修正法21AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法

C-均值算法22AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法C-均值算法的局限性最終的聚類結(jié)果依賴于初始類中心的選擇需要事先指定聚類的類別數(shù)23AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法問題：如何確定聚類群數(shù)，初始聚類重心？改進(jìn)的C-均值算法①首先計(jì)算各樣本的密度，并將樣本按密度順序排列②給定距離閥值T，挑選出可能的樣本作為初始聚類中心應(yīng)用：1、語音識(shí)別

2、圖像分類

24AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法改進(jìn)的C-均值算法25AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法理論上可以證明，不論初始類中心如何選擇，動(dòng)態(tài)聚類算法總是可以收斂的。26AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法核函數(shù)的聚類算法樣本x與聚類Ki間相似性度量:樣本集Ki

={xj(i)}用一個(gè)所謂的“核函數(shù)”Ki，如樣本集的某種統(tǒng)計(jì)量27AppliedPatternRecognitionCSE616基于閥值準(zhǔn)則的聚類方法核函數(shù)的聚類算法28AppliedPatternRecognitionCSE616基于準(zhǔn)則函數(shù)的聚類方法

誤差平方和準(zhǔn)則

定義誤差平方和準(zhǔn)則函數(shù)為：其中C為類別數(shù)，為第i類樣本，為第i類樣本的均值向量,即：

29AppliedPatternRecognitionCSE616基于準(zhǔn)則函數(shù)的聚類方法為第i類樣本總數(shù)表示樣本聚為C個(gè)類別（群）后，所有樣本到各類中心之間誤差的平方和。當(dāng)最小時(shí)，即是希望的聚類結(jié)果。30AppliedPatternRecognitionCSE616基于準(zhǔn)則函數(shù)的聚類方法上述準(zhǔn)則函數(shù)的值，只有在知道聚類群數(shù)，及各樣本屬于那一群后，才能計(jì)算欲求極小值，用窮舉法是行不通的通常是應(yīng)用迭代的方法來實(shí)現(xiàn)

31AppliedPatternRecognitionCSE616基于準(zhǔn)則函數(shù)的聚類方法基本思想：根據(jù)一定的先驗(yàn)知識(shí)確定聚類的群數(shù)，并粗略找到一個(gè)初始劃分結(jié)果，再由迭代算法得到最優(yōu)聚類結(jié)果。

32AppliedPatternRecognitionCSE616基于準(zhǔn)則函數(shù)的聚類方法原理：采用誤差平方和準(zhǔn)則函數(shù)

33AppliedPatternRecognitionCSE616基于準(zhǔn)則函數(shù)的聚類方法現(xiàn)假定在初始劃分后，將中的樣本搬到中去則變?yōu)椋?/p>

34AppliedPatternRecognitionCSE616基于準(zhǔn)則函數(shù)的聚類方法則增加到35AppliedPatternRecognitionCSE616基于準(zhǔn)則函數(shù)的聚類方法同理，則減小到36AppliedPatternRecognitionCSE616基于準(zhǔn)則函數(shù)的聚類方法若減小的大于增加的，即則這次搬動(dòng)改進(jìn)了準(zhǔn)則函數(shù)。37AppliedPatternRecognitionCSE616其它聚類方