模式識別中的常見聚類算法.ppt

《模式識別中的常見聚類算法.ppt》由會員分享，可在線閱讀，更多相關《模式識別中的常見聚類算法.ppt（27頁珍藏版）》請在裝配圖網上搜索。

模式識別中的常見聚類算法,趙英剛整理,聚類問題的描述（1）,聚類問題的描述（2）,聚類問題：根據給定的數據集，要求尋找T上的一個“好”的劃分(劃分成m個類；m可以是已知的，也可以是未知的），滿足約束條件：,,,,,,,,,,聚類問題的描述（3）,模糊聚類問題：根據給定的數據集，要求尋找T上的一個“好”的模糊劃分(劃分成m個模糊集），滿足約束條件：,,,,,,,,,,模糊聚類問題可以看成是前面聚類問題（硬聚類）的一個推廣，當uj的值域限制為{0,1}時，模糊聚類就是硬聚類.,聚類問題的要點,樣本間的接近度（ProximityMeasures）聚類評價準則：“好”的聚類指什么？聚類算法聚類有效性檢驗（統計假設檢驗）聚類結果解釋（結合專家知識）聚類的泛化能力或一致性或抗擾動能力,樣本間的接近度度量,差異性度量（DissimilarityMeasure,DM）對稱性自己與自己的差異性最小例子：距離差異性度量相似性度量（SimilarityMeasure，SM）對稱性自己與自己的相似性最大例子：高斯徑向基函數,常用的接近度度量,點與點之間點與集合之間集合與集合之間,點與點之間——DM,點與點之間——SM,點與集合之間,集合與集合之間,聚類評價準則,類內樣本間的接近度大，類間樣本間的接近度小…………,主要聚類算法(1),N個樣本聚為m類的可能聚類數S(N,m):,S(15,3)=2375101;S(20,4)=45232115901S(25,8)=690223721118368580;S(100,5)≈1068枚舉聚類是行不通的！,主要聚類算法(2),順序聚類（SequentialCluteringAlgorithms）分層聚類（HierachicalCluteringAlgorithms）模型聚類（basedoncostfunctionoptimization)其他,順序聚類,最基本的順序聚類算法（1）第1個樣本歸為第1類；（2）計算下一個樣本到己有類的最短距離，若其距離小于給定的域值，則將該樣本歸為其對應的類，否則增加一個新類，并將該樣本歸為新類。（3）重復（2），直到所有樣本都被歸類。特點聚類結果與樣本的順序和給定的域值有關；聚類速度快,分層聚類,將數據對象按層次進行分解，形成一個分層的嵌套聚類(聚類譜系圖或聚類樹狀圖)，可分為凝聚算法（AgglomerativeAlgorithms）開始將每個對象作為一個類，然后相繼地合并上輪中最相近的兩個類，直到所有的類合并為一個類或者達到某個終止條件。分裂算法（DivisiveAlgorithms）開始將所有對象置于一個類中；然后將上輪的每個類按某個準則分裂為兩類，在從中選擇其中最好的一個分裂，作為該輪的類分裂；直到每個對象都在單獨的一個類中或達到某個終止條件。缺點在于一旦一個合并或分裂完成，就不能撤銷，導致分層聚類方法不能更正錯誤的決定。,分層（凝聚）聚類的一些結論,聚類結果和樣本點間距離函數以及類間距離函數的關系：一般來講，最短距離法使用于長條狀或S形的類，最長距離法，重心法，類平均法，離差平方和法適用于橢球型的類。我們用Dk表示第k次并類操作時的距離，如果一個系統聚類法能夠保證{Di}是單調上升的，那么我們稱之為具有單調性?？梢宰C明，最短距離法，最長距離法，類平均法，離差平方和法具有單調性，重心法和中間距離法不具有單調性。從聚類譜系圖中可以看出，不具有單調性表現為出現一個凹陷，并且不容易劃分類。,分層（凝聚）聚類的一些結論,有人從極端距離矩陣的觀點出發(fā)，認為相比于其他方法，類平均法既不太濃縮，也不太擴張，比較適中；因而從空間的濃縮和擴張的角度，他們推薦類平均法。有人證明與初始距離矩陣A最接近的極端距離矩陣，恰好是使用最短距離法得到的極端距離矩陣，而其他的凝聚型分層聚類法都不具有這個最優(yōu)性質。從這個角度出發(fā)，最短距離法比較受到推崇。,模型聚類,K-meansClusteringK-中心點聚類模糊K-均值聚類或ISODATA………,K-meansClustering—模型,將N個樣本{x1,…,xN}劃分到m個類{C1,…,Cm}中，最小化評分函數,,,這里c1,…,cm是C1,…,Cm的質心，是劃分到類Cj的樣本,K-meansClustering—實現,隨機選擇m個樣本點作為m個初始質心c1,…,cm；按距離最近原則，將所有樣本劃分到以質心c1,…,cm為代表的m個類中；重新計算m個類的質心c1,…,cm；重復（2）和（3）直到質心c1,…,cm無改變或目標函數J(c1,…,cm)不減小。,K-meansClustering—特點,優(yōu)點：當類密集，且類與類之間區(qū)別明顯（比如球型聚集）時，聚類效果很好；強的一致性算法的復雜度是O(Nmt)(t為迭代次數)，對處理大數據集是高效的。缺點：結果與初始質心有關；必須預先給出聚類的類別數m；對“噪聲”和孤立點數據敏感，少量的這些數據對平均值產生較大的影響；不適合發(fā)現非凸面形狀的聚類,K-中心點聚類,避開k-均值聚類對“噪聲”和少數孤立點的敏感性，將類中各個對象的平均值（質心）更改為類中各個對象的中心點。但運算代價比k-均值聚類大。,模糊k-均值聚類（ISODATA）,譜聚類,譜聚類,可以看成是特征空間中的聚類問題原空間不具備球型（或橢球型）的聚類問題，可通過映射將其轉化為特征空間中的球型（或橢球型）聚類問題,基于密度的方法,Step1:尋找數據集中的核心對象(即其?-鄰域包含較多對象的對象)p1,…,pm，形成以這些核心對象為代表的類；Step2:反復尋找從這些核心對象直接密度可達的對象（在核心對象的?-鄰域中），這期間可能涉及一些密度可達類的合并，該過程直到沒有新的點可加入到任何類中時結束。,