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

模式識(shí)別中的常見聚類算法第一頁(yè)，共二十七頁(yè)，2022年，8月28日聚類問題的描述（1）第二頁(yè)，共二十七頁(yè)，2022年，8月28日聚類問題的描述（2）聚類問題：根據(jù)給定的數(shù)據(jù)集，要求尋找T上的一個(gè)“好”的劃分(劃分成m個(gè)類；m可以是已知的，也可以是未知的），滿足約束條件：第三頁(yè)，共二十七頁(yè)，2022年，8月28日聚類問題的描述（3）模糊聚類問題：根據(jù)給定的數(shù)據(jù)集，要求尋找T上的一個(gè)“好”的模糊劃分(劃分成m個(gè)模糊集），滿足約束條件：模糊聚類問題可以看成是前面聚類問題（硬聚類）的一個(gè)推廣，當(dāng)uj的值域限制為{0,1}時(shí)，模糊聚類就是硬聚類.第四頁(yè)，共二十七頁(yè)，2022年，8月28日聚類問題的要點(diǎn)樣本間的接近度（ProximityMeasures）聚類評(píng)價(jià)準(zhǔn)則：“好”的聚類指什么？聚類算法聚類有效性檢驗(yàn)（統(tǒng)計(jì)假設(shè)檢驗(yàn)）聚類結(jié)果解釋（結(jié)合專家知識(shí)）聚類的泛化能力或一致性或抗擾動(dòng)能力第五頁(yè)，共二十七頁(yè)，2022年，8月28日樣本間的接近度度量差異性度量（DissimilarityMeasure,DM）對(duì)稱性自己與自己的差異性最小例子：距離差異性度量相似性度量（SimilarityMeasure，SM）對(duì)稱性自己與自己的相似性最大例子：高斯徑向基函數(shù)第六頁(yè)，共二十七頁(yè)，2022年，8月28日常用的接近度度量點(diǎn)與點(diǎn)之間點(diǎn)與集合之間集合與集合之間第七頁(yè)，共二十七頁(yè)，2022年，8月28日點(diǎn)與點(diǎn)之間——DM第八頁(yè)，共二十七頁(yè)，2022年，8月28日點(diǎn)與點(diǎn)之間——SM第九頁(yè)，共二十七頁(yè)，2022年，8月28日點(diǎn)與集合之間第十頁(yè)，共二十七頁(yè)，2022年，8月28日集合與集合之間第十一頁(yè)，共二十七頁(yè)，2022年，8月28日聚類評(píng)價(jià)準(zhǔn)則類內(nèi)樣本間的接近度大，類間樣本間的接近度小…………第十二頁(yè)，共二十七頁(yè)，2022年，8月28日主要聚類算法(1)N個(gè)樣本聚為m類的可能聚類數(shù)S(N,m):S(15,3)=2375101;S(20,4)=45232115901S(25,8)=690223721118368580;S(100,5)≈1068枚舉聚類是行不通的！第十三頁(yè)，共二十七頁(yè)，2022年，8月28日主要聚類算法(2)順序聚類（SequentialCluteringAlgorithms）分層聚類（HierachicalCluteringAlgorithms）模型聚類（basedoncostfunctionoptimization)其他第十四頁(yè)，共二十七頁(yè)，2022年，8月28日順序聚類最基本的順序聚類算法（1）第1個(gè)樣本歸為第1類；（2）計(jì)算下一個(gè)樣本到己有類的最短距離，若其距離小于給定的域值，則將該樣本歸為其對(duì)應(yīng)的類，否則增加一個(gè)新類，并將該樣本歸為新類。（3）重復(fù)（2），直到所有樣本都被歸類。特點(diǎn)聚類結(jié)果與樣本的順序和給定的域值有關(guān)；聚類速度快第十五頁(yè)，共二十七頁(yè)，2022年，8月28日分層聚類將數(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ò)誤的決定。第十六頁(yè)，共二十七頁(yè)，2022年，8月28日分層（凝聚）聚類的一些結(jié)論聚類結(jié)果和樣本點(diǎn)間距離函數(shù)以及類間距離函數(shù)的關(guān)系：一般來講，最短距離法使用于長(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è)凹陷，并且不容易劃分類。第十七頁(yè)，共二十七頁(yè)，2022年，8月28日分層（凝聚）聚類的一些結(jié)論有人從極端距離矩陣的觀點(diǎn)出發(fā)，認(rèn)為相比于其他方法，類平均法既不太濃縮，也不太擴(kuò)張，比較適中；因而從空間的濃縮和擴(kuò)張的角度，他們推薦類平均法。有人證明與初始距離矩陣A最接近的極端距離矩陣，恰好是使用最短距離法得到的極端距離矩陣，而其他的凝聚型分層聚類法都不具有這個(gè)最優(yōu)性質(zhì)。從這個(gè)角度出發(fā)，最短距離法比較受到推崇。第十八頁(yè)，共二十七頁(yè)，2022年，8月28日模型聚類K-meansClusteringK-中心點(diǎn)聚類模糊K-均值聚類或ISODATA………第十九頁(yè)，共二十七頁(yè)，2022年，8月28日K-meansClustering—模型將N個(gè)樣本{x1,…,xN}劃分到m個(gè)類{C1,…,Cm}中，最小化評(píng)分函數(shù)

這里c1,…,cm是C1,…,Cm的質(zhì)心，是劃分到類Cj的樣本第二十頁(yè)，共二十七頁(yè)，2022年，8月28日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無改變或目標(biāo)函數(shù)J(c1,…,cm)不減小。第二十一頁(yè)，共二十七頁(yè)，2022年，8月28日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)非凸面形狀的聚類第二十二頁(yè)，共二十七頁(yè)，2022年，8月28日K-中心點(diǎn)聚類避開k-均值聚類對(duì)“噪聲”和少數(shù)孤立點(diǎn)的敏感性，將類中各個(gè)對(duì)象的平均值（質(zhì)心）更改為類中各個(gè)對(duì)象的中心點(diǎn)。但運(yùn)算代價(jià)比k-均值聚類大。第二十三頁(yè)，共二十七頁(yè)，2022年，8月28日模糊k-均值聚類（ISODATA）第二十四頁(yè)，共二十七頁(yè)，2022年，8月28日譜聚類第二十五頁(yè)，共二十七頁(yè)，2022年，8月28日譜聚類可以看成是特征空間中的聚類問題原空間不具備球型（或橢球型）的聚類問題，可通過映射將其轉(zhuǎn)化為特征空間中的球型（或橢球型）聚類問題第二十六頁(yè)，共二十七頁(yè)，2022年，8月28日基于密度的方法Step1:尋找數(shù)據(jù)集中的