模式識(shí)別中的常見(jiàn)聚類(lèi)算法

模式識(shí)別中的常見(jiàn)聚類(lèi)算法第一頁(yè)，共二十七頁(yè)，編輯于2023年，星期六聚類(lèi)問(wèn)題的描述（1）第二頁(yè)，共二十七頁(yè)，編輯于2023年，星期六聚類(lèi)問(wèn)題的描述（2）聚類(lèi)問(wèn)題：根據(jù)給定的數(shù)據(jù)集，要求尋找T上的一個(gè)“好”的劃分(劃分成m個(gè)類(lèi)；m可以是已知的，也可以是未知的），滿(mǎn)足約束條件：第三頁(yè)，共二十七頁(yè)，編輯于2023年，星期六聚類(lèi)問(wèn)題的描述（3）模糊聚類(lèi)問(wèn)題：根據(jù)給定的數(shù)據(jù)集，要求尋找T上的一個(gè)“好”的模糊劃分(劃分成m個(gè)模糊集），滿(mǎn)足約束條件：模糊聚類(lèi)問(wèn)題可以看成是前面聚類(lèi)問(wèn)題（硬聚類(lèi)）的一個(gè)推廣，當(dāng)uj的值域限制為{0,1}時(shí)，模糊聚類(lèi)就是硬聚類(lèi).第四頁(yè)，共二十七頁(yè)，編輯于2023年，星期六聚類(lèi)問(wèn)題的要點(diǎn)樣本間的接近度（ProximityMeasures）聚類(lèi)評(píng)價(jià)準(zhǔn)則：“好”的聚類(lèi)指什么？聚類(lèi)算法聚類(lèi)有效性檢驗(yàn)（統(tǒng)計(jì)假設(shè)檢驗(yàn)）聚類(lèi)結(jié)果解釋?zhuān)ńY(jié)合專(zhuān)家知識(shí)）聚類(lèi)的泛化能力或一致性或抗擾動(dòng)能力第五頁(yè)，共二十七頁(yè)，編輯于2023年，星期六樣本間的接近度度量差異性度量（DissimilarityMeasure,DM）對(duì)稱(chēng)性自己與自己的差異性最小例子：距離差異性度量相似性度量（SimilarityMeasure，SM）對(duì)稱(chēng)性自己與自己的相似性最大例子：高斯徑向基函數(shù)第六頁(yè)，共二十七頁(yè)，編輯于2023年，星期六常用的接近度度量點(diǎn)與點(diǎn)之間點(diǎn)與集合之間集合與集合之間第七頁(yè)，共二十七頁(yè)，編輯于2023年，星期六點(diǎn)與點(diǎn)之間——DM第八頁(yè)，共二十七頁(yè)，編輯于2023年，星期六點(diǎn)與點(diǎn)之間——SM第九頁(yè)，共二十七頁(yè)，編輯于2023年，星期六點(diǎn)與集合之間第十頁(yè)，共二十七頁(yè)，編輯于2023年，星期六集合與集合之間第十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期六聚類(lèi)評(píng)價(jià)準(zhǔn)則類(lèi)內(nèi)樣本間的接近度大，類(lèi)間樣本間的接近度小…………第十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期六主要聚類(lèi)算法(1)N個(gè)樣本聚為m類(lèi)的可能聚類(lèi)數(shù)S(N,m):S(15,3)=2375101;S(20,4)=45232115901S(25,8)=690223721118368580;S(100,5)≈1068枚舉聚類(lèi)是行不通的！第十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期六主要聚類(lèi)算法(2)順序聚類(lèi)（SequentialCluteringAlgorithms）分層聚類(lèi)（HierachicalCluteringAlgorithms）模型聚類(lèi)（basedoncostfunctionoptimization)其他第十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期六順序聚類(lèi)最基本的順序聚類(lèi)算法（1）第1個(gè)樣本歸為第1類(lèi)；（2）計(jì)算下一個(gè)樣本到己有類(lèi)的最短距離，若其距離小于給定的域值，則將該樣本歸為其對(duì)應(yīng)的類(lèi)，否則增加一個(gè)新類(lèi)，并將該樣本歸為新類(lèi)。（3）重復(fù)（2），直到所有樣本都被歸類(lèi)。特點(diǎn)聚類(lèi)結(jié)果與樣本的順序和給定的域值有關(guān)；聚類(lèi)速度快第十五頁(yè)，共二十七頁(yè)，編輯于2023年，星期六分層聚類(lèi)將數(shù)據(jù)對(duì)象按層次進(jìn)行分解，形成一個(gè)分層的嵌套聚類(lèi)(聚類(lèi)譜系圖或聚類(lèi)樹(shù)狀圖)，可分為凝聚算法（AgglomerativeAlgorithms）開(kāi)始將每個(gè)對(duì)象作為一個(gè)類(lèi)，然后相繼地合并上輪中最相近的兩個(gè)類(lèi)，直到所有的類(lèi)合并為一個(gè)類(lèi)或者達(dá)到某個(gè)終止條件。分裂算法（DivisiveAlgorithms）開(kāi)始將所有對(duì)象置于一個(gè)類(lèi)中；然后將上輪的每個(gè)類(lèi)按某個(gè)準(zhǔn)則分裂為兩類(lèi)，在從中選擇其中最好的一個(gè)分裂，作為該輪的類(lèi)分裂；直到每個(gè)對(duì)象都在單獨(dú)的一個(gè)類(lèi)中或達(dá)到某個(gè)終止條件。缺點(diǎn)在于一旦一個(gè)合并或分裂完成，就不能撤銷(xiāo)，導(dǎo)致分層聚類(lèi)方法不能更正錯(cuò)誤的決定。第十六頁(yè)，共二十七頁(yè)，編輯于2023年，星期六分層（凝聚）聚類(lèi)的一些結(jié)論聚類(lèi)結(jié)果和樣本點(diǎn)間距離函數(shù)以及類(lèi)間距離函數(shù)的關(guān)系：一般來(lái)講，最短距離法使用于長(zhǎng)條狀或S形的類(lèi)，最長(zhǎng)距離法，重心法，類(lèi)平均法，離差平方和法適用于橢球型的類(lèi)。我們用Dk表示第k次并類(lèi)操作時(shí)的距離，如果一個(gè)系統(tǒng)聚類(lèi)法能夠保證{Di}是單調(diào)上升的，那么我們稱(chēng)之為具有單調(diào)性?？梢宰C明，最短距離法，最長(zhǎng)距離法，類(lèi)平均法，離差平方和法具有單調(diào)性，重心法和中間距離法不具有單調(diào)性。從聚類(lèi)譜系圖中可以看出，不具有單調(diào)性表現(xiàn)為出現(xiàn)一個(gè)凹陷，并且不容易劃分類(lèi)。第十七頁(yè)，共二十七頁(yè)，編輯于2023年，星期六分層（凝聚）聚類(lèi)的一些結(jié)論有人從極端距離矩陣的觀點(diǎn)出發(fā)，認(rèn)為相比于其他方法，類(lèi)平均法既不太濃縮，也不太擴(kuò)張，比較適中；因而從空間的濃縮和擴(kuò)張的角度，他們推薦類(lèi)平均法。有人證明與初始距離矩陣A最接近的極端距離矩陣，恰好是使用最短距離法得到的極端距離矩陣，而其他的凝聚型分層聚類(lèi)法都不具有這個(gè)最優(yōu)性質(zhì)。從這個(gè)角度出發(fā)，最短距離法比較受到推崇。第十八頁(yè)，共二十七頁(yè)，編輯于2023年，星期六模型聚類(lèi)K-meansClusteringK-中心點(diǎn)聚類(lèi)模糊K-均值聚類(lèi)或ISODATA………第十九頁(yè)，共二十七頁(yè)，編輯于2023年，星期六K-meansClustering—模型將N個(gè)樣本{x1,…,xN}劃分到m個(gè)類(lèi){C1,…,Cm}中，最小化評(píng)分函數(shù)

這里c1,…,cm是C1,…,Cm的質(zhì)心，是劃分到類(lèi)Cj的樣本第二十頁(yè)，共二十七頁(yè)，編輯于2023年，星期六K-meansClustering—實(shí)現(xiàn)隨機(jī)選擇m個(gè)樣本點(diǎn)作為m個(gè)初始質(zhì)心c1,…,cm

；按距離最近原則，將所有樣本劃分到以質(zhì)心c1,…,cm為代表的m個(gè)類(lèi)中；重新計(jì)算m個(gè)類(lèi)的質(zhì)心c1,…,cm；重復(fù)（2）和（3）直到質(zhì)心c1,…,cm無(wú)改變或目標(biāo)函數(shù)J(c1,…,cm)不減小。第二十一頁(yè)，共二十七頁(yè)，編輯于2023年，星期六K-meansClustering—特點(diǎn)優(yōu)點(diǎn)：當(dāng)類(lèi)密集，且類(lèi)與類(lèi)之間區(qū)別明顯（比如球型聚集）時(shí)，聚類(lèi)效果很好；強(qiáng)的一致性算法的復(fù)雜度是O(Nmt)(t為迭代次數(shù))，對(duì)處理大數(shù)據(jù)集是高效的。缺點(diǎn)：結(jié)果與初始質(zhì)心有關(guān)；必須預(yù)先給出聚類(lèi)的類(lèi)別數(shù)m；對(duì)“噪聲”和孤立點(diǎn)數(shù)據(jù)敏感，少量的這些數(shù)據(jù)對(duì)平均值產(chǎn)生較大的影響；不適合發(fā)現(xiàn)非凸面形狀的聚類(lèi)第二十二頁(yè)，共二十七頁(yè)，編輯于2023年，星期六K-中心點(diǎn)聚類(lèi)避開(kāi)k-均值聚類(lèi)對(duì)“噪聲”和少數(shù)孤立點(diǎn)的敏感性，將類(lèi)中各個(gè)對(duì)象的平均值（質(zhì)心）更改為類(lèi)中各個(gè)對(duì)象的中心點(diǎn)。但運(yùn)算代價(jià)比k-均值聚類(lèi)大。第二十三頁(yè)，共二十七頁(yè)，編輯于2023年，星期六模糊k-均值聚類(lèi)（ISODATA）第二十四頁(yè)，共二十七頁(yè)，編輯于2023年，星期六譜聚類(lèi)第二十五頁(yè)，共二十七頁(yè)，編輯于2023年，星期六譜聚類(lèi)可以看成是特征空間中的聚類(lèi)問(wèn)題原空間不具備球型（或橢球型）的聚類(lèi)問(wèn)題，可通過(guò)映射將其轉(zhuǎn)化為特征空間中的球型（或橢球型）聚類(lèi)問(wèn)題第二十六頁(yè)，共二十七頁(yè)，編輯于2023年，星期六基于密度的方法Step1:尋找數(shù)據(jù)集中