模式識別中的常見聚類算法.ppt
《模式識別中的常見聚類算法.ppt》由會員分享,可在線閱讀,更多相關(guān)《模式識別中的常見聚類算法.ppt(27頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
模式識別中的常見聚類算法,趙英剛整理,聚類問題的描述(1),聚類問題的描述(2),聚類問題:根據(jù)給定的數(shù)據(jù)集,要求尋找T上的一個“好”的劃分(劃分成m個類;m可以是已知的,也可以是未知的),滿足約束條件:,,,,,,,,,,聚類問題的描述(3),模糊聚類問題:根據(jù)給定的數(shù)據(jù)集,要求尋找T上的一個“好”的模糊劃分(劃分成m個模糊集),滿足約束條件:,,,,,,,,,,模糊聚類問題可以看成是前面聚類問題(硬聚類)的一個推廣,當(dāng)uj的值域限制為{0,1}時,模糊聚類就是硬聚類.,聚類問題的要點(diǎn),樣本間的接近度(ProximityMeasures)聚類評價準(zhǔn)則:“好”的聚類指什么?聚類算法聚類有效性檢驗(yàn)(統(tǒng)計(jì)假設(shè)檢驗(yàn))聚類結(jié)果解釋(結(jié)合專家知識)聚類的泛化能力或一致性或抗擾動能力,樣本間的接近度度量,差異性度量(DissimilarityMeasure,DM)對稱性自己與自己的差異性最小例子:距離差異性度量相似性度量(SimilarityMeasure,SM)對稱性自己與自己的相似性最大例子:高斯徑向基函數(shù),常用的接近度度量,點(diǎn)與點(diǎn)之間點(diǎn)與集合之間集合與集合之間,點(diǎn)與點(diǎn)之間——DM,點(diǎn)與點(diǎn)之間——SM,點(diǎn)與集合之間,集合與集合之間,聚類評價準(zhǔn)則,類內(nèi)樣本間的接近度大,類間樣本間的接近度小…………,主要聚類算法(1),N個樣本聚為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個樣本歸為第1類;(2)計(jì)算下一個樣本到己有類的最短距離,若其距離小于給定的域值,則將該樣本歸為其對應(yīng)的類,否則增加一個新類,并將該樣本歸為新類。(3)重復(fù)(2),直到所有樣本都被歸類。特點(diǎn)聚類結(jié)果與樣本的順序和給定的域值有關(guān);聚類速度快,分層聚類,將數(shù)據(jù)對象按層次進(jìn)行分解,形成一個分層的嵌套聚類(聚類譜系圖或聚類樹狀圖),可分為凝聚算法(AgglomerativeAlgorithms)開始將每個對象作為一個類,然后相繼地合并上輪中最相近的兩個類,直到所有的類合并為一個類或者達(dá)到某個終止條件。分裂算法(DivisiveAlgorithms)開始將所有對象置于一個類中;然后將上輪的每個類按某個準(zhǔn)則分裂為兩類,在從中選擇其中最好的一個分裂,作為該輪的類分裂;直到每個對象都在單獨(dú)的一個類中或達(dá)到某個終止條件。缺點(diǎn)在于一旦一個合并或分裂完成,就不能撤銷,導(dǎo)致分層聚類方法不能更正錯誤的決定。,分層(凝聚)聚類的一些結(jié)論,聚類結(jié)果和樣本點(diǎn)間距離函數(shù)以及類間距離函數(shù)的關(guān)系:一般來講,最短距離法使用于長條狀或S形的類,最長距離法,重心法,類平均法,離差平方和法適用于橢球型的類。我們用Dk表示第k次并類操作時的距離,如果一個系統(tǒng)聚類法能夠保證{Di}是單調(diào)上升的,那么我們稱之為具有單調(diào)性??梢宰C明,最短距離法,最長距離法,類平均法,離差平方和法具有單調(diào)性,重心法和中間距離法不具有單調(diào)性。從聚類譜系圖中可以看出,不具有單調(diào)性表現(xiàn)為出現(xiàn)一個凹陷,并且不容易劃分類。,分層(凝聚)聚類的一些結(jié)論,有人從極端距離矩陣的觀點(diǎn)出發(fā),認(rèn)為相比于其他方法,類平均法既不太濃縮,也不太擴(kuò)張,比較適中;因而從空間的濃縮和擴(kuò)張的角度,他們推薦類平均法。有人證明與初始距離矩陣A最接近的極端距離矩陣,恰好是使用最短距離法得到的極端距離矩陣,而其他的凝聚型分層聚類法都不具有這個最優(yōu)性質(zhì)。從這個角度出發(fā),最短距離法比較受到推崇。,模型聚類,K-meansClusteringK-中心點(diǎn)聚類模糊K-均值聚類或ISODATA………,K-meansClustering—模型,將N個樣本{x1,…,xN}劃分到m個類{C1,…,Cm}中,最小化評分函數(shù),,,這里c1,…,cm是C1,…,Cm的質(zhì)心,是劃分到類Cj的樣本,K-meansClustering—實(shí)現(xiàn),隨機(jī)選擇m個樣本點(diǎn)作為m個初始質(zhì)心c1,…,cm;按距離最近原則,將所有樣本劃分到以質(zhì)心c1,…,cm為代表的m個類中;重新計(jì)算m個類的質(zhì)心c1,…,cm;重復(fù)(2)和(3)直到質(zhì)心c1,…,cm無改變或目標(biāo)函數(shù)J(c1,…,cm)不減小。,K-meansClustering—特點(diǎn),優(yōu)點(diǎn):當(dāng)類密集,且類與類之間區(qū)別明顯(比如球型聚集)時,聚類效果很好;強(qiáng)的一致性算法的復(fù)雜度是O(Nmt)(t為迭代次數(shù)),對處理大數(shù)據(jù)集是高效的。缺點(diǎn):結(jié)果與初始質(zhì)心有關(guān);必須預(yù)先給出聚類的類別數(shù)m;對“噪聲”和孤立點(diǎn)數(shù)據(jù)敏感,少量的這些數(shù)據(jù)對平均值產(chǎn)生較大的影響;不適合發(fā)現(xiàn)非凸面形狀的聚類,K-中心點(diǎn)聚類,避開k-均值聚類對“噪聲”和少數(shù)孤立點(diǎn)的敏感性,將類中各個對象的平均值(質(zhì)心)更改為類中各個對象的中心點(diǎn)。但運(yùn)算代價比k-均值聚類大。,模糊k-均值聚類(ISODATA),譜聚類,譜聚類,可以看成是特征空間中的聚類問題原空間不具備球型(或橢球型)的聚類問題,可通過映射將其轉(zhuǎn)化為特征空間中的球型(或橢球型)聚類問題,基于密度的方法,Step1:尋找數(shù)據(jù)集中的核心對象(即其?-鄰域包含較多對象的對象)p1,…,pm,形成以這些核心對象為代表的類;Step2:反復(fù)尋找從這些核心對象直接密度可達(dá)的對象(在核心對象的?-鄰域中),這期間可能涉及一些密度可達(dá)類的合并,該過程直到?jīng)]有新的點(diǎn)可加入到任何類中時結(jié)束。,- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 模式識別 中的 常見 算法
鏈接地址:http://m.zhongcaozhi.com.cn/p-3193851.html