模式識(shí)別第9章20151019

模式識(shí)別：非監(jiān)督模式識(shí)別PatternRecognition主講人：胡雪梅導(dǎo)師：黃嵐指導(dǎo)老師：王巖時(shí)間：2015/10/19非監(jiān)督模式識(shí)別引言基于模型的方法混合模型的估計(jì)動(dòng)態(tài)聚類算法模糊聚類方法分級(jí)聚類方法SOM自組織神經(jīng)映射網(wǎng)絡(luò)

非監(jiān)督模式識(shí)別——引言非監(jiān)督學(xué)習(xí)識(shí)別/聚類通過(guò)某種算法把一組未知類別的樣本劃分為若干類別。事先不知道類別的定義，不知道有幾類或者是否存在分類，無(wú)可參考的分類目標(biāo)。分監(jiān)督模式識(shí)別的分類基于樣本的規(guī)律分布模型進(jìn)行聚類劃分。

例如：基于模型的方法根據(jù)樣本間的距離或相似度進(jìn)行聚類。例如：3引言2023/2/5非監(jiān)督模式識(shí)別

——基于模型的方法前提條件：已經(jīng)知道或者可以估計(jì)樣本在特征空間的概率分布。單峰子集分離法/單峰子類分離法基本思想：假設(shè)每一個(gè)聚類的樣本在特征空間里是集中在一起的，在分布的密度上形成了了一個(gè)局部的峰值。特征高維：投影。把樣本按照某種準(zhǔn)則投影到某個(gè)一維坐標(biāo)上估計(jì)樣本的概率密度，尋找單峰值進(jìn)行聚類劃分。關(guān)鍵問(wèn)題：如何設(shè)計(jì)合適的坐標(biāo)系？

一種可行答案：使待分類的樣本在某個(gè)坐標(biāo)軸方向具有最大的分散性。/樣本分布方差最大的方向。

但不是所有的情況都適合用這種方法。

算法步驟1）主成分分析。選取投影方向。2）估計(jì)概率函數(shù)密度。如：直方圖3）尋找局部極小值點(diǎn)。若無(wú)則1）4）對(duì)劃分出來(lái)的子集重復(fù)以上步驟，直至終止條件滿足4基于模型的方法2023/2/5非監(jiān)督模式識(shí)別

——混合模型的估計(jì)最大似然函數(shù)：非監(jiān)督的最大似然估計(jì)基本思想：當(dāng)從模型總體隨機(jī)抽取n組樣本觀測(cè)值后，最合理的參數(shù)估計(jì)量應(yīng)該使得從模型中抽取該n組樣本觀測(cè)值的概率最大。假設(shè)條件：5混合模型的估計(jì)2023/2/5非監(jiān)督模式識(shí)別

——混合模型的估計(jì)混合高斯分布

高斯混合模型是單一高斯機(jī)率密度函數(shù)的延伸，任意形狀的概率分布

都可以用多個(gè)高斯分布函數(shù)去近似。

62023/2/5非監(jiān)督模式識(shí)別

——?jiǎng)討B(tài)聚類算法基于相似度度量的聚類方法。動(dòng)態(tài)聚類算法的要點(diǎn)：1）選定某種距離度量作為樣本間的相似性度量。2）確定某種評(píng)價(jià)聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)。3）給定某個(gè)初始分類，迭代，找出使準(zhǔn)則函數(shù)取極值的最好聚類結(jié)果。常用的聚類算法：C均值算法、ISODATA、基于樣本與核的相似性度量的動(dòng)態(tài)聚類算法。C均值算法基本思想：最小方差劃分

通過(guò)迭代尋找c個(gè)聚類的一種劃分方案，使得c個(gè)聚類的均值來(lái)代表相應(yīng)的各類樣本時(shí)得到的總體誤差最小。準(zhǔn)則函數(shù)Je含義是各類樣本與其所屬樣本均值間誤差平方之總和。7動(dòng)態(tài)聚類算法2023/2/5非監(jiān)督模式識(shí)別

——?jiǎng)討B(tài)聚類算法C均值算法的基本步驟C均值算法的特點(diǎn)局部搜索算法，不能保證收斂到全局最優(yōu)解。結(jié)果受初始劃分和樣本調(diào)整順序的影響。樣本初始劃分方法：一般選擇一些代表樣點(diǎn)作為初始聚類的核心。82023/2/5非監(jiān)督模式識(shí)別

——?jiǎng)討B(tài)聚類算法代表點(diǎn)的選擇方法憑經(jīng)驗(yàn)選擇代表點(diǎn)。將全部數(shù)據(jù)隨機(jī)分成c類，計(jì)算每類的重心。將樣本排序后用前c個(gè)點(diǎn)作為代表點(diǎn)。從（c-1）聚類劃分問(wèn)題中產(chǎn)生c聚類劃分問(wèn)題的代表點(diǎn)。初始分類方法選擇一批代表點(diǎn)后，其余的點(diǎn)離那個(gè)代表點(diǎn)進(jìn)就歸入哪一類。同上，但是會(huì)立即重新計(jì)算中心代替原來(lái)的代表點(diǎn)。首先選擇一個(gè)正數(shù)，選擇，計(jì)算與間的距離如果小于，則將歸于，否則建立新類，以此類推……現(xiàn)將數(shù)據(jù)標(biāo)準(zhǔn)化，用表示標(biāo)準(zhǔn)化后的第i個(gè)樣本的第j個(gè)坐標(biāo)。令

9如果計(jì)算的值最接近整數(shù)k，則將歸入第k類計(jì)算關(guān)于聚類數(shù)目c拐點(diǎn)A處對(duì)應(yīng)的類別數(shù)最優(yōu)2023/2/510非監(jiān)督模式識(shí)別

——?jiǎng)討B(tài)聚類算法ISODATA方法（改進(jìn)的C均值算法）與C均值算法的不同不是調(diào)整一個(gè)樣本的類別就更新一次各類的均值，而是把全部樣本調(diào)整完后才重新計(jì)算各類的均值。引入了對(duì)類別的評(píng)判準(zhǔn)則，根據(jù)這些準(zhǔn)則對(duì)某些類合并或者分裂。ISODTADA基本步驟

2023/2/511非監(jiān)督模式識(shí)別

——?jiǎng)討B(tài)聚類算法基于樣本與核的相似性度量的動(dòng)態(tài)算法問(wèn)題引入當(dāng)樣本的分布偏離超球形，用均值就不能很好的代表一個(gè)類。解決辦法構(gòu)造基于樣本與核的相似性度量的動(dòng)態(tài)聚類算法。類別的核表示、類的距離度量準(zhǔn)則函數(shù)：

算法步驟1）選擇初始劃分，c類，確定每一類的初始核Kj；2）若

如果樣本y到核Kj的距離是y到所有核Kk中的最小者。則將y劃分到第j類中；3）重新修正核Kj,若Kj保持不變，算法終止，否則轉(zhuǎn)到2）；

比較C均值是基于樣本與核的相似性度量的動(dòng)態(tài)算法的一個(gè)特例。2023/2/512非監(jiān)督模式識(shí)別

——模糊聚類方法基本知識(shí)模糊聚類基本知識(shí)Zadeh提出模糊集理論：每一個(gè)元素是以一定的程度屬于某個(gè)集合，也可以以不同的程度屬于幾個(gè)集合。隸屬度函數(shù)：一個(gè)對(duì)象x隸屬于集合A的程度的函數(shù)，。支持集、支持點(diǎn)重要函數(shù)模糊C均值算法聚類損失函數(shù)（準(zhǔn)則函數(shù)）：歸一化條件：計(jì)算隸屬度函數(shù)：更新聚類中心函數(shù)：2023/2/513算法步驟非監(jiān)督模式識(shí)別

——模糊聚類方法改進(jìn)的模糊C均值算法問(wèn)題引入如果某個(gè)野值樣本遠(yuǎn)離各類的聚類中心，原本屬于各類的隸屬度都很小，但歸一化條件會(huì)使得它對(duì)各類都有較大的隸屬度，影響迭代結(jié)果。改進(jìn)策略：放松歸一化條件，使得樣本對(duì)各類的隸屬度總和為n，即評(píng)價(jià)優(yōu)點(diǎn)：更好的魯棒性、對(duì)初始聚類數(shù)目不敏感；缺點(diǎn)：1）同C均值、模糊C均值一樣，對(duì)聚類中心的初值十分敏感；2）若果某個(gè)聚類中心距離某個(gè)樣本非常近，可能會(huì)得到只包含這一個(gè)樣本的類別。2023/2/514非監(jiān)督模式識(shí)別

——分級(jí)聚類方法引入生物學(xué)上物種的分類。分級(jí)聚類：自底向上的方法算法步驟1）初始化，每個(gè)樣本形成一類；2）合并：把距離最?。ɑ蛳嗨菩宰畲蟮膬深惡喜ⅲ?）重復(fù)2），直到所有的樣本合并到兩個(gè)類中。樹(shù)枝的長(zhǎng)度反應(yīng)兩個(gè)節(jié)點(diǎn)之間的距離（相似性）算法特點(diǎn)局部搜索、噪音敏感；聚類數(shù)樹(shù)畫(huà)法不唯一；分級(jí)聚類方法2023/2/515非監(jiān)督模式識(shí)別

——自組織映射神經(jīng)網(wǎng)絡(luò)SOM算法和自組織特性SOM的生物依據(jù)由芬蘭人Kohonen于1981年開(kāi)始研究。高等動(dòng)物大腦皮層對(duì)外界的信號(hào)有規(guī)律的相應(yīng)，很大部分是在不斷接受外界信號(hào)刺激的的過(guò)程中形成的。特定神經(jīng)元參數(shù)組織對(duì)特定外界刺激敏感，形成局部功能區(qū)域。SOM的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)SOM算法思想某個(gè)輸出結(jié)點(diǎn)能對(duì)某一類刺激作出特別的反應(yīng)以代表該類別；輸出層上相鄰的結(jié)點(diǎn)能對(duì)實(shí)際模式分布中相近的類別作出特別的反映；當(dāng)某類數(shù)據(jù)輸入時(shí)，對(duì)某一輸出結(jié)點(diǎn)產(chǎn)生最大刺激的獲勝結(jié)點(diǎn)，同時(shí)對(duì)獲勝結(jié)點(diǎn)周圍的一些結(jié)點(diǎn)產(chǎn)生較大刺激；2023/2/516非監(jiān)督模式識(shí)別

——自組織映射神經(jīng)網(wǎng)絡(luò)算法步驟2023/2/517非監(jiān)督模式識(shí)別

——自組織映射神經(jīng)網(wǎng)絡(luò)SOM算法圖例真實(shí)聚類規(guī)則訓(xùn)練樣本點(diǎn)神經(jīng)元初始位置第一個(gè)訓(xùn)練樣本獲勝神經(jīng)元9，鄰域：5，6，8第二個(gè)訓(xùn)練樣本獲勝神經(jīng)元4鄰域：1，5，7第三個(gè)訓(xùn)練樣本獲勝神經(jīng)元3鄰域：2，5，6第一個(gè)訓(xùn)練樣本獲勝神經(jīng)元9，鄰域：5，6，8第二個(gè)訓(xùn)練樣本獲勝神經(jīng)元4鄰域：1，5，7第三個(gè)訓(xùn)練樣本獲勝神經(jīng)元3鄰域：2，5，6SOM的自組織現(xiàn)象

SOM完成的是從原樣本空間到二維平面上神經(jīng)元網(wǎng)格的映射，這種映射是拓?fù)浔３值?，即在原空間