模式識(shí)別中的常見聚類算法.ppt

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