聚類(lèi)分析PAM算法-精選課件

聚類(lèi)分析

——PAM算法報(bào)告時(shí)間:2019年6月日?qǐng)?bào)告人:陳曉宇王暉聚類(lèi)分析

——PAM算法報(bào)告時(shí)間:2什么是聚類(lèi)聚類(lèi)(clustering)是一個(gè)將數(shù)據(jù)集劃分為若干組(class)或類(lèi)(cluster)的過(guò)程，并使得同一個(gè)組內(nèi)的數(shù)據(jù)對(duì)象具有較高的相似度；而不同組中的數(shù)據(jù)對(duì)象是不相似的。什么是聚類(lèi)聚類(lèi)(clustering)是一個(gè)將數(shù)據(jù)集什么是聚類(lèi)過(guò)程將一組(set)物理的或抽象的對(duì)象，根據(jù)它們之間的相似程度，分為若干組(group)；其中相似的對(duì)象構(gòu)成一組，這一過(guò)程就稱(chēng)為聚類(lèi)過(guò)程(clustering)什么是聚類(lèi)過(guò)程將一組(set)物理的或抽象的對(duì)象，根什么是聚類(lèi)分析一個(gè)聚類(lèi)(cluster)就是由彼此相似的一組對(duì)象所構(gòu)成的集合；不同聚類(lèi)中對(duì)象是不相似的。就是從給定的數(shù)據(jù)集中搜索數(shù)據(jù)項(xiàng)(items)之間所存在的有價(jià)值聯(lián)系。在許多應(yīng)用，一個(gè)聚類(lèi)中所有對(duì)象常常被當(dāng)作一個(gè)對(duì)象來(lái)進(jìn)行處理或分析等操作什么是聚類(lèi)分析一個(gè)聚類(lèi)(cluster)就是由彼此相許多領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)都有聚類(lèi)研究和應(yīng)用!許多領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)都有聚類(lèi)研究和應(yīng)用!聚類(lèi)分析的典型應(yīng)用商業(yè)方面聚類(lèi)分析可以幫助市場(chǎng)人員發(fā)現(xiàn)顧客群中所存在的不同特征的組群；并可以利用購(gòu)買(mǎi)模式來(lái)描述這些不同特征的顧客組群生物方面聚類(lèi)分析可以用來(lái)獲取動(dòng)物或植物所存在的層次結(jié)構(gòu)，以及根據(jù)基因功能對(duì)其進(jìn)行分類(lèi)以獲得對(duì)人群中所固有的結(jié)構(gòu)更深入的了解。聚類(lèi)分析的典型應(yīng)用商業(yè)方面聚類(lèi)分析的典型應(yīng)用聚類(lèi)還可以從地球觀測(cè)數(shù)據(jù)庫(kù)中幫助識(shí)別具有相似的土地使用情況的區(qū)域。此外還可以幫助分類(lèi)識(shí)別互聯(lián)網(wǎng)上的文檔以便進(jìn)行信息發(fā)現(xiàn)。作為數(shù)據(jù)挖掘的一項(xiàng)功能，聚類(lèi)分析還可以作為一個(gè)單獨(dú)使用的工具，來(lái)幫助分析數(shù)據(jù)的分布、了解各數(shù)據(jù)類(lèi)的特征、確定所感興趣的數(shù)據(jù)類(lèi)以便作進(jìn)一步分析。聚類(lèi)分析也可以作為其它算法（諸如：分類(lèi)和定性歸納算法）的預(yù)處理步驟聚類(lèi)分析的典型應(yīng)用聚類(lèi)還可以從地球觀測(cè)數(shù)據(jù)庫(kù)中幫助識(shí)別具有相聚類(lèi)方法劃分類(lèi)方法分層類(lèi)方法基于密度類(lèi)方法基于網(wǎng)格類(lèi)方法基于模型類(lèi)方法聚類(lèi)方法劃分類(lèi)方法聚類(lèi)方法——?jiǎng)澐诸?lèi)方法給定一個(gè)包含n個(gè)對(duì)象或數(shù)據(jù)行，劃分方法將數(shù)據(jù)集劃分為k個(gè)子集(劃分)。其中每個(gè)子集均代表一個(gè)聚類(lèi)(k≤n)。也就是說(shuō)將數(shù)據(jù)分為k組，這些組滿足以下要求每組至少應(yīng)包含一個(gè)對(duì)象每個(gè)對(duì)象必須只能屬于某一組聚類(lèi)方法——?jiǎng)澐诸?lèi)方法給定一個(gè)包含n個(gè)對(duì)象或數(shù)據(jù)行，劃分方法聚類(lèi)方法——?jiǎng)澐诸?lèi)方法給定需要?jiǎng)澐值膫€(gè)數(shù)k，一個(gè)劃分方法創(chuàng)建一個(gè)初始劃分；然后利用循環(huán)再定位技術(shù)，即通過(guò)移動(dòng)不同劃分(組)中的對(duì)象來(lái)改變劃分內(nèi)容。一個(gè)好的劃分衡量標(biāo)準(zhǔn)通常就是同一個(gè)組中的對(duì)象“相近”或彼此相關(guān)；而不同組中的對(duì)象“較遠(yuǎn)”或彼此不同。當(dāng)然還有許多其它判斷劃分質(zhì)量的衡量標(biāo)準(zhǔn)。聚類(lèi)方法——?jiǎng)澐诸?lèi)方法給定需要?jiǎng)澐值膫€(gè)數(shù)k，一個(gè)劃分方法創(chuàng)建聚類(lèi)方法——?jiǎng)澐诸?lèi)方法為獲得基于劃分聚類(lèi)分析的全局最優(yōu)結(jié)果就需要窮舉所有可能的對(duì)象劃分。為此大多數(shù)應(yīng)用采用一至二種常用啟發(fā)方法k-means算法，該算法中的每一個(gè)聚類(lèi)均用相應(yīng)聚類(lèi)中對(duì)象的均值來(lái)表示；k-medoids算法，該算法中的每一個(gè)聚類(lèi)均用相應(yīng)聚類(lèi)中離聚類(lèi)中心最近的對(duì)象來(lái)表示。聚類(lèi)方法——?jiǎng)澐诸?lèi)方法為獲得基于劃分聚類(lèi)分析的全局最優(yōu)結(jié)果就聚類(lèi)方法——分層類(lèi)方法層次方法就是通過(guò)分解所給定的數(shù)據(jù)對(duì)象集來(lái)創(chuàng)建一個(gè)層次。根據(jù)層次分解形成的方式，可以將層次方法分為自下而上和自上而下兩種類(lèi)型。自下而上的層次方法從每個(gè)對(duì)象均為一個(gè)（單獨(dú)的）組開(kāi)始；逐步將這些（對(duì)象）組進(jìn)行合并，直到組合并在層次頂端或滿足終止條件為止。自上而下層次方法從所有均屬于一個(gè)組開(kāi)始；每一次循環(huán)將其（組）分解為更小的組；直到每個(gè)對(duì)象構(gòu)成一組或滿足終止條件為止。聚類(lèi)方法——分層類(lèi)方法層次方法就是通過(guò)分解所給定的數(shù)據(jù)對(duì)象集聚類(lèi)方法——基于密度類(lèi)方法基于密度概念的聚類(lèi)方法實(shí)際上就是不斷增長(zhǎng)所獲得的聚類(lèi)直到“鄰近”（數(shù)據(jù)對(duì)象或點(diǎn)）密度超過(guò)一定閾值（如：一個(gè)聚類(lèi)中的點(diǎn)數(shù)，或一個(gè)給定半徑內(nèi)必須包含至少的點(diǎn)數(shù)）為止。這種方法可以用于消除數(shù)據(jù)中的噪聲（異常數(shù)據(jù)），以及幫助發(fā)現(xiàn)任意形狀的聚類(lèi)。聚類(lèi)方法——基于密度類(lèi)方法基于密度概念的聚類(lèi)方法實(shí)際上就是不聚類(lèi)方法——基于網(wǎng)格類(lèi)方法基于網(wǎng)格方法將對(duì)象空間劃分為有限數(shù)目的單元以形成網(wǎng)格結(jié)構(gòu)。所有聚類(lèi)操作均是在這一網(wǎng)格結(jié)構(gòu)上進(jìn)行的。這種方法主要優(yōu)點(diǎn)就是處理時(shí)間由于與數(shù)據(jù)對(duì)象個(gè)數(shù)無(wú)關(guān)而僅與劃分對(duì)象空間的網(wǎng)格數(shù)相關(guān)，從而顯得相對(duì)較快聚類(lèi)方法——基于網(wǎng)格類(lèi)方法基于網(wǎng)格方法將對(duì)象空間劃分為有限數(shù)聚類(lèi)方法——基于模型類(lèi)方法基于模型方法就是為每個(gè)聚類(lèi)假設(shè)一個(gè)模型，然后再去發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對(duì)象。一個(gè)基于模型的算法可以通過(guò)構(gòu)造一個(gè)描述數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來(lái)確定具體聚類(lèi)。它根據(jù)標(biāo)準(zhǔn)統(tǒng)計(jì)方法并考慮到“噪聲”或異常數(shù)據(jù)，可以自動(dòng)確定聚類(lèi)個(gè)數(shù)；因而它可以產(chǎn)生很魯棒的聚類(lèi)方法聚類(lèi)方法——基于模型類(lèi)方法基于模型方法就是為每個(gè)聚類(lèi)假設(shè)一個(gè)聚類(lèi)分析聚類(lèi)分析劃分方法給定包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)和所要形成的聚類(lèi)個(gè)數(shù)k，劃分算法將對(duì)象集合劃分為k份(n≤k)，其中每個(gè)劃分均代表一個(gè)聚類(lèi)。所形成的聚類(lèi)將使得一個(gè)客觀劃分標(biāo)準(zhǔn)(常稱(chēng)為相似函數(shù)，如：距離)最優(yōu)化從而使得一個(gè)聚類(lèi)中的對(duì)象是“相似”的；而不同聚類(lèi)中的對(duì)象是“不相似”的劃分方法給定包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)和所要形成的聚類(lèi)個(gè)數(shù)k-medoids算法k-medoids聚類(lèi)算法比k-means聚類(lèi)算法在處理異常數(shù)據(jù)和噪聲數(shù)據(jù)方面更為魯棒與聚類(lèi)均值相比，一個(gè)聚類(lèi)中心的代表對(duì)象要較少受到異常數(shù)據(jù)或極端數(shù)據(jù)的影響前者的處理時(shí)間要比后者更大。兩個(gè)算法都需要用戶事先指定所需聚類(lèi)個(gè)數(shù)kk-medoids算法k-medoids聚類(lèi)算法比k-mk-medoids算法k-medoids聚類(lèi)算法的基本策略就是通過(guò)首先任意為每個(gè)聚類(lèi)找到一個(gè)代表對(duì)象medoid,而首先確定n個(gè)數(shù)據(jù)對(duì)象的k個(gè)聚類(lèi)；(也需要循環(huán)進(jìn)行)其它對(duì)象則根據(jù)它們與這些聚類(lèi)代表的距離分別將它們歸屬到各相應(yīng)聚類(lèi)中(仍然是最小距離原則)。而如果替換一個(gè)聚類(lèi)代表能夠改善所獲聚類(lèi)質(zhì)量的話，那么就可以用一個(gè)新對(duì)象替換老聚類(lèi)對(duì)象。k-medoids算法k-medoids聚類(lèi)算法的基本策略k-medoids算法這里將利用一個(gè)基于各對(duì)象與其聚類(lèi)代表間距離的成本函數(shù)來(lái)對(duì)聚類(lèi)質(zhì)量進(jìn)行評(píng)估。為了確定任一個(gè)非聚類(lèi)代表對(duì)象Orandom是否可以替換當(dāng)前一個(gè)聚類(lèi)代表Oj，需要根據(jù)以下四種情況對(duì)各非聚類(lèi)代表對(duì)象p進(jìn)行檢查k-medoids算法這里將利用一個(gè)基于各對(duì)象與其聚類(lèi)代表間第一種情況若對(duì)象p當(dāng)前屬于Oj(所代表的聚類(lèi))，且如果用Orandom

替換Oj作為新聚類(lèi)代表，而p就更接近其它Oi(i≠j)，那么就將p歸類(lèi)到Oi(所代表的聚類(lèi))中第一種情況若對(duì)象p當(dāng)前屬于Oj(所代表的聚類(lèi))第一種情況——圖第一種情況——圖第二種情況若對(duì)象p當(dāng)前屬于Oi

(所代表的聚類(lèi))，且如果用Orandom替換Oj作為新聚類(lèi)代表，而p最更接近Orandom，那么就將p歸類(lèi)到Orandom(所代表的聚類(lèi))中第二種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))，且第二種情況——圖第二種情況——圖第三種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))(

i≠j)

，且如果用Orandom替換Oj作為新聚類(lèi)代表，而p仍然最接近Oi，那么p歸類(lèi)不發(fā)生變化第三種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))(i≠第三種情況——圖第三種情況——圖第四種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))(

i≠j)

，且如果用Orandom替換Oj作為新聚類(lèi)代表，而p仍然最接近Orandom，那么就將p歸類(lèi)到Orandom(所代表的聚類(lèi))中第四種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))(i第四種情況——圖第四種情況——圖說(shuō)明上述k-medoids聚類(lèi)算法的四種主要處理情況。每次對(duì)對(duì)象進(jìn)行重新歸類(lèi)，都會(huì)使得構(gòu)成成本函數(shù)的方差E發(fā)生變化。因此成本函數(shù)能夠計(jì)算出聚類(lèi)代表替換前后的方差變化。通過(guò)替換不合適的代表來(lái)而使距離方差發(fā)生變化的累計(jì)就構(gòu)成了成本函數(shù)的輸出。若整個(gè)輸出成本為負(fù)值，那么就用Oradom

替換Oj

，以便能夠減少實(shí)際的方差E。若整個(gè)輸出成本為正值，那么就認(rèn)為當(dāng)前的Oj

是可接受的，本次循環(huán)就無(wú)需變動(dòng)。一個(gè)基本的k-medoids聚類(lèi)算法如下算法所示。說(shuō)明上述k-medoids聚類(lèi)算法的四種主要處理情況。每次對(duì)基本的聚類(lèi)算法k-medoids算法算法：根據(jù)聚類(lèi)的中心對(duì)象（聚類(lèi)代表）進(jìn)行聚類(lèi)劃分的k-medoids算法輸入：聚類(lèi)個(gè)數(shù)k，以及包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)輸出：滿足基于各聚類(lèi)中心對(duì)象的方差最小標(biāo)準(zhǔn)的k個(gè)聚類(lèi)基本的聚類(lèi)算法k-medoids算法算法：根據(jù)聚類(lèi)的中心對(duì)象基本的聚類(lèi)算法k-medoids算法處理流程：

(1)從m個(gè)數(shù)據(jù)對(duì)象任意選擇k個(gè)對(duì)象作為初始聚類(lèi)(中心)代表 (2)循環(huán)(3)到(5)到每個(gè)聚類(lèi)不再發(fā)生變化為止 (3)依據(jù)每個(gè)聚類(lèi)的中心代表對(duì)象，以及各對(duì)象與這些中心對(duì)象間距離；并根據(jù)最小距離重新對(duì)相應(yīng)對(duì)象進(jìn)行劃分 (4)任意選擇一個(gè)非中心對(duì)象Orandom

；計(jì)算其與中心對(duì)象Oj交換的整個(gè)成本S (5)若S為負(fù)值則交換Orandom與Oj以構(gòu)成新聚類(lèi)的k個(gè)中心對(duì)象基本的聚類(lèi)算法k-medoids算法處理流程：PAM算法PAM(圍繞中心對(duì)象進(jìn)行劃分)方法是最初提出的k-medoids聚類(lèi)算法之一它在初始選擇k個(gè)聚類(lèi)中心對(duì)象之后，不斷循環(huán)對(duì)每?jī)蓚€(gè)對(duì)象(一個(gè)為非中心對(duì)象，一個(gè)為中心對(duì)象)進(jìn)行分析，以便選擇出更好的聚類(lèi)中心代表對(duì)象。并根據(jù)每組對(duì)象分析計(jì)算所獲得的聚類(lèi)質(zhì)量。若一個(gè)中心對(duì)象Oj

被替換后導(dǎo)致方差迅速減少，那么就進(jìn)行替換。對(duì)于較大的n

與k

值這樣的計(jì)算開(kāi)銷(xiāo)也非常大PAM算法PAM(圍繞中心對(duì)象進(jìn)行劃分)方法是最初提出的kPAM算法像PAM方法這樣典型的k-medoids聚類(lèi)算法，在小數(shù)據(jù)集上可以工作的很好但是對(duì)于大數(shù)據(jù)庫(kù)則處理效果并不理想?？梢岳靡粋€(gè)基于采樣的聚類(lèi)方法，稱(chēng)為CLARA(ClusteringLARgeApplication),來(lái)有效處理大規(guī)模數(shù)據(jù)PAM算法像PAM方法這樣典型的k-medoids聚類(lèi)算參考文獻(xiàn)(加)JiaweiHan[韓家煒],MichelineKamber[坎伯]著范明…[等]譯數(shù)據(jù)挖掘概念與技術(shù)機(jī)械工業(yè)出版社2019陳京民.數(shù)據(jù)倉(cāng)庫(kù)與數(shù)據(jù)挖掘技術(shù)[M].電子工業(yè)出版社,2019.(美)MehmedKantardzic著閃四清,陳茵,程雁等譯數(shù)據(jù)挖掘概念、模型、方法和算法清華大學(xué)出版社2019

參考文獻(xiàn)(加)JiaweiHan[韓家煒],Michel謝謝大家!謝謝大家!聚類(lèi)分析

——PAM算法報(bào)告時(shí)間:2019年6月日?qǐng)?bào)告人:陳曉宇王暉聚類(lèi)分析

——PAM算法報(bào)告時(shí)間:2什么是聚類(lèi)聚類(lèi)(clustering)是一個(gè)將數(shù)據(jù)集劃分為若干組(class)或類(lèi)(cluster)的過(guò)程，并使得同一個(gè)組內(nèi)的數(shù)據(jù)對(duì)象具有較高的相似度；而不同組中的數(shù)據(jù)對(duì)象是不相似的。什么是聚類(lèi)聚類(lèi)(clustering)是一個(gè)將數(shù)據(jù)集什么是聚類(lèi)過(guò)程將一組(set)物理的或抽象的對(duì)象，根據(jù)它們之間的相似程度，分為若干組(group)；其中相似的對(duì)象構(gòu)成一組，這一過(guò)程就稱(chēng)為聚類(lèi)過(guò)程(clustering)什么是聚類(lèi)過(guò)程將一組(set)物理的或抽象的對(duì)象，根什么是聚類(lèi)分析一個(gè)聚類(lèi)(cluster)就是由彼此相似的一組對(duì)象所構(gòu)成的集合；不同聚類(lèi)中對(duì)象是不相似的。就是從給定的數(shù)據(jù)集中搜索數(shù)據(jù)項(xiàng)(items)之間所存在的有價(jià)值聯(lián)系。在許多應(yīng)用，一個(gè)聚類(lèi)中所有對(duì)象常常被當(dāng)作一個(gè)對(duì)象來(lái)進(jìn)行處理或分析等操作什么是聚類(lèi)分析一個(gè)聚類(lèi)(cluster)就是由彼此相許多領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)都有聚類(lèi)研究和應(yīng)用!許多領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)都有聚類(lèi)研究和應(yīng)用!聚類(lèi)分析的典型應(yīng)用商業(yè)方面聚類(lèi)分析可以幫助市場(chǎng)人員發(fā)現(xiàn)顧客群中所存在的不同特征的組群；并可以利用購(gòu)買(mǎi)模式來(lái)描述這些不同特征的顧客組群生物方面聚類(lèi)分析可以用來(lái)獲取動(dòng)物或植物所存在的層次結(jié)構(gòu)，以及根據(jù)基因功能對(duì)其進(jìn)行分類(lèi)以獲得對(duì)人群中所固有的結(jié)構(gòu)更深入的了解。聚類(lèi)分析的典型應(yīng)用商業(yè)方面聚類(lèi)分析的典型應(yīng)用聚類(lèi)還可以從地球觀測(cè)數(shù)據(jù)庫(kù)中幫助識(shí)別具有相似的土地使用情況的區(qū)域。此外還可以幫助分類(lèi)識(shí)別互聯(lián)網(wǎng)上的文檔以便進(jìn)行信息發(fā)現(xiàn)。作為數(shù)據(jù)挖掘的一項(xiàng)功能，聚類(lèi)分析還可以作為一個(gè)單獨(dú)使用的工具，來(lái)幫助分析數(shù)據(jù)的分布、了解各數(shù)據(jù)類(lèi)的特征、確定所感興趣的數(shù)據(jù)類(lèi)以便作進(jìn)一步分析。聚類(lèi)分析也可以作為其它算法（諸如：分類(lèi)和定性歸納算法）的預(yù)處理步驟聚類(lèi)分析的典型應(yīng)用聚類(lèi)還可以從地球觀測(cè)數(shù)據(jù)庫(kù)中幫助識(shí)別具有相聚類(lèi)方法劃分類(lèi)方法分層類(lèi)方法基于密度類(lèi)方法基于網(wǎng)格類(lèi)方法基于模型類(lèi)方法聚類(lèi)方法劃分類(lèi)方法聚類(lèi)方法——?jiǎng)澐诸?lèi)方法給定一個(gè)包含n個(gè)對(duì)象或數(shù)據(jù)行，劃分方法將數(shù)據(jù)集劃分為k個(gè)子集(劃分)。其中每個(gè)子集均代表一個(gè)聚類(lèi)(k≤n)。也就是說(shuō)將數(shù)據(jù)分為k組，這些組滿足以下要求每組至少應(yīng)包含一個(gè)對(duì)象每個(gè)對(duì)象必須只能屬于某一組聚類(lèi)方法——?jiǎng)澐诸?lèi)方法給定一個(gè)包含n個(gè)對(duì)象或數(shù)據(jù)行，劃分方法聚類(lèi)方法——?jiǎng)澐诸?lèi)方法給定需要?jiǎng)澐值膫€(gè)數(shù)k，一個(gè)劃分方法創(chuàng)建一個(gè)初始劃分；然后利用循環(huán)再定位技術(shù)，即通過(guò)移動(dòng)不同劃分(組)中的對(duì)象來(lái)改變劃分內(nèi)容。一個(gè)好的劃分衡量標(biāo)準(zhǔn)通常就是同一個(gè)組中的對(duì)象“相近”或彼此相關(guān)；而不同組中的對(duì)象“較遠(yuǎn)”或彼此不同。當(dāng)然還有許多其它判斷劃分質(zhì)量的衡量標(biāo)準(zhǔn)。聚類(lèi)方法——?jiǎng)澐诸?lèi)方法給定需要?jiǎng)澐值膫€(gè)數(shù)k，一個(gè)劃分方法創(chuàng)建聚類(lèi)方法——?jiǎng)澐诸?lèi)方法為獲得基于劃分聚類(lèi)分析的全局最優(yōu)結(jié)果就需要窮舉所有可能的對(duì)象劃分。為此大多數(shù)應(yīng)用采用一至二種常用啟發(fā)方法k-means算法，該算法中的每一個(gè)聚類(lèi)均用相應(yīng)聚類(lèi)中對(duì)象的均值來(lái)表示；k-medoids算法，該算法中的每一個(gè)聚類(lèi)均用相應(yīng)聚類(lèi)中離聚類(lèi)中心最近的對(duì)象來(lái)表示。聚類(lèi)方法——?jiǎng)澐诸?lèi)方法為獲得基于劃分聚類(lèi)分析的全局最優(yōu)結(jié)果就聚類(lèi)方法——分層類(lèi)方法層次方法就是通過(guò)分解所給定的數(shù)據(jù)對(duì)象集來(lái)創(chuàng)建一個(gè)層次。根據(jù)層次分解形成的方式，可以將層次方法分為自下而上和自上而下兩種類(lèi)型。自下而上的層次方法從每個(gè)對(duì)象均為一個(gè)（單獨(dú)的）組開(kāi)始；逐步將這些（對(duì)象）組進(jìn)行合并，直到組合并在層次頂端或滿足終止條件為止。自上而下層次方法從所有均屬于一個(gè)組開(kāi)始；每一次循環(huán)將其（組）分解為更小的組；直到每個(gè)對(duì)象構(gòu)成一組或滿足終止條件為止。聚類(lèi)方法——分層類(lèi)方法層次方法就是通過(guò)分解所給定的數(shù)據(jù)對(duì)象集聚類(lèi)方法——基于密度類(lèi)方法基于密度概念的聚類(lèi)方法實(shí)際上就是不斷增長(zhǎng)所獲得的聚類(lèi)直到“鄰近”（數(shù)據(jù)對(duì)象或點(diǎn)）密度超過(guò)一定閾值（如：一個(gè)聚類(lèi)中的點(diǎn)數(shù)，或一個(gè)給定半徑內(nèi)必須包含至少的點(diǎn)數(shù)）為止。這種方法可以用于消除數(shù)據(jù)中的噪聲（異常數(shù)據(jù)），以及幫助發(fā)現(xiàn)任意形狀的聚類(lèi)。聚類(lèi)方法——基于密度類(lèi)方法基于密度概念的聚類(lèi)方法實(shí)際上就是不聚類(lèi)方法——基于網(wǎng)格類(lèi)方法基于網(wǎng)格方法將對(duì)象空間劃分為有限數(shù)目的單元以形成網(wǎng)格結(jié)構(gòu)。所有聚類(lèi)操作均是在這一網(wǎng)格結(jié)構(gòu)上進(jìn)行的。這種方法主要優(yōu)點(diǎn)就是處理時(shí)間由于與數(shù)據(jù)對(duì)象個(gè)數(shù)無(wú)關(guān)而僅與劃分對(duì)象空間的網(wǎng)格數(shù)相關(guān)，從而顯得相對(duì)較快聚類(lèi)方法——基于網(wǎng)格類(lèi)方法基于網(wǎng)格方法將對(duì)象空間劃分為有限數(shù)聚類(lèi)方法——基于模型類(lèi)方法基于模型方法就是為每個(gè)聚類(lèi)假設(shè)一個(gè)模型，然后再去發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對(duì)象。一個(gè)基于模型的算法可以通過(guò)構(gòu)造一個(gè)描述數(shù)據(jù)點(diǎn)空間分布的密度函數(shù)來(lái)確定具體聚類(lèi)。它根據(jù)標(biāo)準(zhǔn)統(tǒng)計(jì)方法并考慮到“噪聲”或異常數(shù)據(jù)，可以自動(dòng)確定聚類(lèi)個(gè)數(shù)；因而它可以產(chǎn)生很魯棒的聚類(lèi)方法聚類(lèi)方法——基于模型類(lèi)方法基于模型方法就是為每個(gè)聚類(lèi)假設(shè)一個(gè)聚類(lèi)分析聚類(lèi)分析劃分方法給定包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)和所要形成的聚類(lèi)個(gè)數(shù)k，劃分算法將對(duì)象集合劃分為k份(n≤k)，其中每個(gè)劃分均代表一個(gè)聚類(lèi)。所形成的聚類(lèi)將使得一個(gè)客觀劃分標(biāo)準(zhǔn)(常稱(chēng)為相似函數(shù)，如：距離)最優(yōu)化從而使得一個(gè)聚類(lèi)中的對(duì)象是“相似”的；而不同聚類(lèi)中的對(duì)象是“不相似”的劃分方法給定包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)庫(kù)和所要形成的聚類(lèi)個(gè)數(shù)k-medoids算法k-medoids聚類(lèi)算法比k-means聚類(lèi)算法在處理異常數(shù)據(jù)和噪聲數(shù)據(jù)方面更為魯棒與聚類(lèi)均值相比，一個(gè)聚類(lèi)中心的代表對(duì)象要較少受到異常數(shù)據(jù)或極端數(shù)據(jù)的影響前者的處理時(shí)間要比后者更大。兩個(gè)算法都需要用戶事先指定所需聚類(lèi)個(gè)數(shù)kk-medoids算法k-medoids聚類(lèi)算法比k-mk-medoids算法k-medoids聚類(lèi)算法的基本策略就是通過(guò)首先任意為每個(gè)聚類(lèi)找到一個(gè)代表對(duì)象medoid,而首先確定n個(gè)數(shù)據(jù)對(duì)象的k個(gè)聚類(lèi)；(也需要循環(huán)進(jìn)行)其它對(duì)象則根據(jù)它們與這些聚類(lèi)代表的距離分別將它們歸屬到各相應(yīng)聚類(lèi)中(仍然是最小距離原則)。而如果替換一個(gè)聚類(lèi)代表能夠改善所獲聚類(lèi)質(zhì)量的話，那么就可以用一個(gè)新對(duì)象替換老聚類(lèi)對(duì)象。k-medoids算法k-medoids聚類(lèi)算法的基本策略k-medoids算法這里將利用一個(gè)基于各對(duì)象與其聚類(lèi)代表間距離的成本函數(shù)來(lái)對(duì)聚類(lèi)質(zhì)量進(jìn)行評(píng)估。為了確定任一個(gè)非聚類(lèi)代表對(duì)象Orandom是否可以替換當(dāng)前一個(gè)聚類(lèi)代表Oj，需要根據(jù)以下四種情況對(duì)各非聚類(lèi)代表對(duì)象p進(jìn)行檢查k-medoids算法這里將利用一個(gè)基于各對(duì)象與其聚類(lèi)代表間第一種情況若對(duì)象p當(dāng)前屬于Oj(所代表的聚類(lèi))，且如果用Orandom

替換Oj作為新聚類(lèi)代表，而p就更接近其它Oi(i≠j)，那么就將p歸類(lèi)到Oi(所代表的聚類(lèi))中第一種情況若對(duì)象p當(dāng)前屬于Oj(所代表的聚類(lèi))第一種情況——圖第一種情況——圖第二種情況若對(duì)象p當(dāng)前屬于Oi

(所代表的聚類(lèi))，且如果用Orandom替換Oj作為新聚類(lèi)代表，而p最更接近Orandom，那么就將p歸類(lèi)到Orandom(所代表的聚類(lèi))中第二種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))，且第二種情況——圖第二種情況——圖第三種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))(

i≠j)

，且如果用Orandom替換Oj作為新聚類(lèi)代表，而p仍然最接近Oi，那么p歸類(lèi)不發(fā)生變化第三種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))(i≠第三種情況——圖第三種情況——圖第四種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))(

i≠j)

，且如果用Orandom替換Oj作為新聚類(lèi)代表，而p仍然最接近Orandom，那么就將p歸類(lèi)到Orandom(所代表的聚類(lèi))中第四種情況若對(duì)象p當(dāng)前屬于Oi(所代表的聚類(lèi))(i第四種情況——圖第四種情況——圖說(shuō)明上述k-medoids聚類(lèi)算法的四種主要處理情況。每次對(duì)對(duì)象進(jìn)行重新歸類(lèi)，都會(huì)使得構(gòu)成成本函數(shù)的方差E發(fā)生變化。因此成本函數(shù)能夠計(jì)算出聚類(lèi)代表替換前后的方差變化。通過(guò)替換不合適的代表來(lái)而使距離方差發(fā)生變化的累計(jì)就構(gòu)成了成本函數(shù)的輸出。若整個(gè)輸出成本為負(fù)值，那么就用Oradom

替換Oj

，以便能夠減少實(shí)際的方差E。若整個(gè)輸出成本為正值，那么就認(rèn)為當(dāng)前的Oj

是可接受的，本次循環(huán)就無(wú)需變動(dòng)。一個(gè)基本的k-medoids聚類(lèi)算法如下算法所示。說(shuō)明上述k-medoids聚類(lèi)算法的四種主要處理情況。每次對(duì)基本的聚類(lèi)算法k-medoids算法算法：根據(jù)聚類(lèi)的中心對(duì)象（聚類(lèi)代表）進(jìn)行聚類(lèi)劃分的k-medoids算法輸入：聚類(lèi)個(gè)數(shù)k，以及包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)