模式識別第9章20151019

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

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

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

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

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

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

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

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

——混合模型的估計混合高斯分布

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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