聚類分析廣州中醫(yī)藥大學(xué)演示文稿當(dāng)前第1頁\共有139頁\編于星期三\13點(diǎn)（優(yōu)選）聚類分析廣州中醫(yī)藥大學(xué)當(dāng)前第2頁\共有139頁\編于星期三\13點(diǎn)聚類是一種無監(jiān)督分類法:沒有預(yù)先指定的類別；典型的應(yīng)用作為一個(gè)獨(dú)立的分析工具，用于了解數(shù)據(jù)的分布；作為其它算法的一個(gè)數(shù)據(jù)預(yù)處理步驟；---異常分析當(dāng)前第3頁\共有139頁\編于星期三\13點(diǎn)應(yīng)用聚類分析的例子市場銷售:

幫助市場人員發(fā)現(xiàn)客戶中的不同群體，然后用這些知識來開展一個(gè)目標(biāo)明確的市場計(jì)劃；土地使用:

在一個(gè)陸地觀察數(shù)據(jù)庫中標(biāo)識那些土地使用相似的地區(qū)；保險(xiǎn):

對購買了汽車保險(xiǎn)的客戶，標(biāo)識那些有較高平均賠償成本的客戶；城市規(guī)劃:

根據(jù)類型、價(jià)格、地理位置等來劃分不同類型的住宅；地震研究:

根據(jù)地質(zhì)斷層的特點(diǎn)把已觀察到的地震中心分成不同的類；當(dāng)前第4頁\共有139頁\編于星期三\13點(diǎn)

生物方面，聚類分析可以用來對動物或植物分類，或根據(jù)基因功能對其進(jìn)行分類以獲得對人群中所固有的結(jié)構(gòu)更深入的了解。

當(dāng)前第5頁\共有139頁\編于星期三\13點(diǎn)什么是一個(gè)好的聚類方法?一個(gè)好的聚類方法要能產(chǎn)生高質(zhì)量的聚類結(jié)果——簇，這些簇要具備以下兩個(gè)特點(diǎn)：高的簇內(nèi)相似性低的簇間相似性

聚類結(jié)果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實(shí)現(xiàn)；聚類方法的好壞還取決于該方法是能發(fā)現(xiàn)某些還是所有的隱含模式；當(dāng)前第6頁\共有139頁\編于星期三\13點(diǎn)可伸縮性能夠處理不同類型的屬性能發(fā)現(xiàn)任意形狀的簇在決定輸入?yún)?shù)的時(shí)候，盡量不需要特定的領(lǐng)域知識能夠處理噪聲和異常對輸入數(shù)據(jù)對象的順序不敏感能處理高維數(shù)據(jù)能產(chǎn)生一個(gè)好的、能滿足用戶指定約束的聚類結(jié)果結(jié)果是可解釋的、可理解的和可用的當(dāng)前第7頁\共有139頁\編于星期三\13點(diǎn)

6.2聚類分析算法分類

分裂法層次法基于密度類方法基于網(wǎng)格類方法基于模型類方法

當(dāng)前第8頁\共有139頁\編于星期三\13點(diǎn)1、分裂法（partitioningmethod）

給定一個(gè)有N個(gè)元組或者記錄的數(shù)據(jù)集，分裂法將構(gòu)造K個(gè)分組，每個(gè)分組就代表一個(gè)聚類，K<N,而且這K個(gè)分組滿足下列幾個(gè)條件

（1）每個(gè)分組至少包含一個(gè)數(shù)據(jù)記錄（2）每一個(gè)數(shù)據(jù)記錄屬于且僅屬于一個(gè)分組（在某些模糊聚類算法中可以放寬）對于一個(gè)給定的K，算法首先給出一個(gè)初始的分組方法法，以后通過反復(fù)迭代的方法改變分組，使得每一次改進(jìn)之后的分組方案都較前一次好。好的標(biāo)準(zhǔn)就是：同組記錄越來越近，不同組記錄越來越好使用這個(gè)算法的基本思想有：

K-MEANS算法、KMEDOID算法、CLARANS算法當(dāng)前第9頁\共有139頁\編于星期三\13點(diǎn)2、層次法(hierarchicalmethod)

層次方法對給定數(shù)據(jù)對象集合進(jìn)行層次的分解。

凝聚----自底向上

分裂-----自頂向下的缺點(diǎn):一旦一個(gè)步驟（合并或分裂）完成，它就不能被撤消，因此而不能更正錯(cuò)誤的決定。代表算法有：

BIRCH算法(利用層次方法的平衡迭代歸約和聚類）

、CURE算法（利用代表點(diǎn)聚類）當(dāng)前第10頁\共有139頁\編于星期三\13點(diǎn)3、基于密度的方法(density-basedmethod)

它與其他方法的根本區(qū)別：不是基于各種各樣的距離的、而是基于密度的，這樣就能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”聚類的缺點(diǎn)。其主要思想是：只要臨近區(qū)域的密度超過某個(gè)閾值，就繼續(xù)聚類。這樣的方法可以用來過濾“噪聲”孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。代表算法有：

DBSCAN算法（基于高密度連接區(qū)域的密度聚類方法）

OPTICS算法、DENCLUE算法當(dāng)前第11頁\共有139頁\編于星期三\13點(diǎn)4、基于網(wǎng)格的方法(grid-basedmethod)

基于網(wǎng)格的聚類方法采用一個(gè)網(wǎng)格數(shù)據(jù)結(jié)構(gòu)。把對象空間量化為有限數(shù)目的單元，形成了一個(gè)網(wǎng)格結(jié)構(gòu)。優(yōu)點(diǎn):處理速度很快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。代表算法有：

STING算法（統(tǒng)計(jì)信息風(fēng)格）、CLIQUE算法、WAVE-CLUSTER算法

當(dāng)前第12頁\共有139頁\編于星期三\13點(diǎn)5、基于模型的方法(model-basedmethod)

給每個(gè)聚類假設(shè)一個(gè)模型（如密度分布函數(shù)），然后去尋找能很好地滿足這個(gè)模型的數(shù)據(jù)集。它的潛在的一個(gè)假定是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。通常有兩種：統(tǒng)計(jì)的方案和神經(jīng)網(wǎng)絡(luò)方案當(dāng)前第13頁\共有139頁\編于星期三\13點(diǎn)

ex6.1:在病理分析時(shí)發(fā)現(xiàn)肺癌患者的頭發(fā)中微量元素的含量與正常人相比有無異常變化。如果以Cr，Cd及As含量的一個(gè)函數(shù)作為變量x1:x1=f(Cr，Cd,As)

以Se,Zn含量的另一個(gè)函數(shù)做為變量x2,則

x2=g(Se,Zn)

在以x1為橫坐標(biāo)，x2為縱坐標(biāo)的平面上，每個(gè)檢查者按這些微量元素的含量在該平面上占據(jù)一點(diǎn)，其分布情況如下：當(dāng)前第14頁\共有139頁\編于星期三\13點(diǎn)x1 x2健康人群初期患者后期患者當(dāng)前第15頁\共有139頁\編于星期三\13點(diǎn)6．3聚類分析中的數(shù)據(jù)類型假設(shè)一個(gè)要進(jìn)行聚類分析的數(shù)據(jù)集包含n個(gè)對象，這些對象可以是人、房屋、文件等。聚類算法通常都采用以下兩種數(shù)據(jù)結(jié)構(gòu)：

當(dāng)前第16頁\共有139頁\編于星期三\13點(diǎn)兩種數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)矩陣(twomodes)差異度矩陣(onemode)當(dāng)前第17頁\共有139頁\編于星期三\13點(diǎn)1．?dāng)?shù)據(jù)矩陣數(shù)據(jù)矩陣是一個(gè)對象—屬性結(jié)構(gòu)。它是n個(gè)對象組成，例如：人的對象是利用P個(gè)屬性來進(jìn)行描述的，如：年齡、高度、重量等。數(shù)據(jù)矩陣采用關(guān)系表形式或nP矩陣來表示，如（6.1)式當(dāng)前第18頁\共有139頁\編于星期三\13點(diǎn)

(6.1)

常稱為樣本數(shù)據(jù)矩陣。其中第i個(gè)樣品p個(gè)變量的觀測值可以記為向量：

xi=(xi1,xi2,…xip)Tx11…x1f….x1p…………xi1…xif…xip…………xn1…xnf….xnp當(dāng)前第19頁\共有139頁\編于星期三\13點(diǎn)

由于各變量表示樣品的各種性質(zhì)，往往使用不同的度量單位，其觀測值也可能相差十分懸殊。這樣，絕對值大的變量其影響可能會湮沒絕對值小的變量，使后者應(yīng)有的作用得不到反映。為了確保各變量在分析中的地位相同，往往需要對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化變換。當(dāng)前第20頁\共有139頁\編于星期三\13點(diǎn)

標(biāo)準(zhǔn)化測量------給所有屬性相同的權(quán)值而在一些應(yīng)用中，用戶會有意識地賦予某些屬性更大權(quán)值以突出其重要性。例如：在對候選籃球選手進(jìn)行聚類分析時(shí)，可能就會給身高屬性賦予更大的權(quán)值。

當(dāng)前第21頁\共有139頁\編于星期三\13點(diǎn)常用的標(biāo)準(zhǔn)化手段有:標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化極差標(biāo)準(zhǔn)化極差正軌化如標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化分兩步當(dāng)前第22頁\共有139頁\編于星期三\13點(diǎn)（1）計(jì)算絕對偏差均值sj

sj=其中，xlj，X2j，…，xnj是變量j的n個(gè)測量值，為變量j的均值；也就是:

＝當(dāng)前第23頁\共有139頁\編于星期三\13點(diǎn)（2）計(jì)算標(biāo)準(zhǔn)化測量值（z-分量）

zij=

其中，絕對偏差均值sj要比標(biāo)準(zhǔn)偏差j更為魯棒(對含有噪聲數(shù)據(jù)而言)。

當(dāng)前第24頁\共有139頁\編于星期三\13點(diǎn)2、差異矩陣差異矩陣是一個(gè)對象-對象結(jié)構(gòu)。它存放n個(gè)對象彼此之間所形成的差異。一般采用nn矩陣表示

(6.2)

0d(2,1)0對稱d(3,1)d(3,2)0

…………d(n,1)d(n,2)…….0當(dāng)前第25頁\共有139頁\編于星期三\13點(diǎn)

其中，d(i，j)表示對象i和對象j之間的差異(或不相似程度)。通常d(i，j)為一個(gè)非負(fù)數(shù)，當(dāng)對象i和對象j非常相似或彼此“接近”時(shí)，該數(shù)值接近0，該數(shù)值越大，就表示對象i和對象j越不相似。

當(dāng)前第26頁\共有139頁\編于星期三\13點(diǎn)許多聚類算法都是基于差異矩陣進(jìn)行聚類分析的。如果數(shù)據(jù)是以數(shù)據(jù)矩陣形式給出的，就需要先轉(zhuǎn)換為差異矩陣，才能利用聚類算法進(jìn)行處理。當(dāng)前第27頁\共有139頁\編于星期三\13點(diǎn)3、基于數(shù)值型數(shù)據(jù)的差異矩陣計(jì)算在標(biāo)準(zhǔn)化之后，或在無需標(biāo)準(zhǔn)化的特定應(yīng)用中，由數(shù)值所描述對象之間的差異(或相似)程度可以通過計(jì)算相應(yīng)兩個(gè)對象之間距離來確定。最常用的距離計(jì)算公式就是歐氏距離具體公式內(nèi)容如下：

當(dāng)前第28頁\共有139頁\編于星期三\13點(diǎn)

d(i,j)=[(|xi1-xj1|2+|xi2-xj2|2+…+|xip-xjp|2]1/2(6.3)-----------歐氏距離其中，i=(xi1,xi2,….xip)

j=(xj1,xj2,….xjp)

分別表示一個(gè)P維數(shù)據(jù)對象另一個(gè)常用的距離計(jì)算方法就是Manhattan距離，它的具體計(jì)算公式定義如下：當(dāng)前第29頁\共有139頁\編于星期三\13點(diǎn)

d(i，,j)＝|xi1-xj1|+|xi2-xj2|+…+|xip-xjp|(6.4)---------------Manhattan距離歐氏距離和Manhattan距離均滿足距離函數(shù)的有關(guān)數(shù)學(xué)性質(zhì)(要求)：d(i，j)≥0，表示對象之間距離為非負(fù)數(shù)的一個(gè)數(shù)值?！(i，j)＝0，表示對象自身之間距離為零。，d(i，j)＝d(j，i)，表示對象之間距離是對稱函數(shù)。d(i，j)≤d(i，h)+d(h，j)，表示對象自身之間距離滿足“兩邊之和不小于第三邊”的性質(zhì)當(dāng)前第30頁\共有139頁\編于星期三\13點(diǎn)相似性度量

例：對于一個(gè)4維向量

X1＝｛1,0,1,0｝

X2＝｛2,1,-3,-1｝，這些距離的度量標(biāo)準(zhǔn)L1（X1，X2）＝1+1+4+1＝7，L2（X1，X2）＝（1+1+16+1）1/2＝4.36L3（X1，X2）＝（1+1+64+1）1/3＝4.06。Lk（Xi，Xj）＝（k）1/k當(dāng)前第31頁\共有139頁\編于星期三\13點(diǎn)

Minkowski距離:

是歐式距離和Manhattan距離的一個(gè)推廣；計(jì)算公式如下：d(i，j)＝[(|xi1-xj1|q+|xi2-xj2|q+…+|xip-xjp|q]1/q(6.5)

其中，q為一個(gè)正整數(shù)，當(dāng)q＝1時(shí)，它代表Manhattan距離計(jì)算公式；當(dāng)q二2時(shí)，它代表歐氏距離計(jì)算公式?？梢詾槊總€(gè)變量賦予一個(gè)權(quán)值，以表示其所代表屬性的重要性還有契比雪夫距離、馬氏距離等當(dāng)前第32頁\共有139頁\編于星期三\13點(diǎn)兩個(gè)對象間的相似系數(shù)也可有多種定義形式如：

夾角余弦法相關(guān)系數(shù)法等

cov(x,y)))/D(x)D(y)=E(x-E(x))(y-E(y))/D(x)D(y)

當(dāng)前第33頁\共有139頁\編于星期三\13點(diǎn)4、其它類型的變量相似性值（1）二值變量一個(gè)二值變量僅取0或1值，其中0代表(變量所表示的)狀態(tài)不存在；1代表相應(yīng)的狀態(tài)存在。給定變量smoker，它描述了一個(gè)病人是否吸煙情況。如：smoker為1表示病人吸煙，若smoker為0，表示病人不吸煙。如果按照數(shù)值變量對二值變量進(jìn)行處理，常會導(dǎo)致錯(cuò)誤的聚類分析結(jié)果產(chǎn)生。因此需要采用特定方法計(jì)算二值變量所描述對象間的差異(程度)當(dāng)前第34頁\共有139頁\編于星期三\13點(diǎn)計(jì)算方法:

根據(jù)二值數(shù)據(jù)計(jì)算差異矩陣；如果認(rèn)為所有的二值變量的權(quán)值均相同，那么就能得到一個(gè)22條件表，如下圖6．1所示。當(dāng)前第35頁\共有139頁\編于星期三\13點(diǎn)對象j

對象i

1

0合計(jì)

1

q

r

q+r

0

s

t

S+t合計(jì)

q+s

r+t

p圖6.1當(dāng)前第36頁\共有139頁\編于星期三\13點(diǎn)表中q表示在對象i和對象j中均取1的二值變量個(gè)數(shù)，r表示在對象i取1而在對象j中取0的二值變量個(gè)數(shù)，s表示在對象i中取0而在對象j中取1的二值變量個(gè)數(shù),t表示在對象i中取i取0而在對象j中取0的二值變量個(gè)數(shù)二值變量的總個(gè)數(shù)為p，那么就有p＝q+r+s+t當(dāng)前第37頁\共有139頁\編于星期三\13點(diǎn)

如果一個(gè)二值變量取0或1所表示的內(nèi)容同樣重要，那么該二值變量就是對稱的。如“性別”就是對稱變量，因?yàn)樗烤故怯?還是用1來(編碼)表示“男”，“女”并不重要。同樣的基于對稱二值變量所計(jì)算相應(yīng)的相似(或差異)性稱為不變相似性（invariantsimilarity)，因?yàn)闊o論如何對相應(yīng)二值變量進(jìn)行編碼并不影響到它們相似(或差異)性的計(jì)算結(jié)果。當(dāng)前第38頁\共有139頁\編于星期三\13點(diǎn)對于不變相似性(計(jì)算)，最常用的描述對象i和對象j之間差異(程度)參數(shù)是簡單匹配關(guān)系數(shù)，定義:d(i,j)=(r+s)/(q+r+s+t)(7-9)當(dāng)前第39頁\共有139頁\編于星期三\13點(diǎn)

如果一個(gè)二值變量取0或1所表示內(nèi)容的重要性是不一樣的，那么該二值變量就是非對稱的。例如，一個(gè)疾病disease-的測試結(jié)果可描述為positive或negative。顯然這兩個(gè)(輸出)結(jié)果的重要性是不一樣的、通常將少見的情況用l來表示

(如：HIVpositive)，而將其它情況用0來表示(HIVnegative)當(dāng)前第40頁\共有139頁\編于星期三\13點(diǎn)給定兩個(gè)非對稱二值變量，如果它們認(rèn)為取1值比取0值所表示的情況更重要，那么，這樣的二值變量就稱為是單性的（好象一個(gè)狀態(tài)），最常用的描述對象i和j的差異(程度)參數(shù)就是Jaccard相關(guān)系數(shù)，具體定義:d(i,j)=(r+s)/(q+r+s)(7-10)Sim(i,j)=1-d(i,j)=q/(q+r+s)(Jaccard)當(dāng)前第41頁\共有139頁\編于星期三\13點(diǎn)

ex7．2二值變量的差異性。假設(shè)一個(gè)病人記錄表如表7-2所示，表中所描述的屬性(變量)分別為:name，gender，fever，cough，test-1，test-2，test-3和test-4

其中，name作為(病人)對象的標(biāo)識，gender(性別)是一個(gè)對稱二值變量。其它變量則均為非對稱變量。當(dāng)前第42頁\共有139頁\編于星期三\13點(diǎn)

表6.1包含許多二值屬性的關(guān)系數(shù)據(jù)表示意描述namegenderfevercoughtest-1test-2test-3test-4Jack

MY(1)N(0)P(1)N(0)N(0)N(0)Mary

FY(1)N(0)P(1)N(0)P(1)N(0)Jim

MY(1)P(1)N(0)N(0)N(0)N(0)…..……….………….當(dāng)前第43頁\共有139頁\編于星期三\13點(diǎn)對于非對稱屬性（變量）值，將Y和P設(shè)為1，N設(shè)為0。根據(jù)非對稱屬性（變量）計(jì)算不同對象（病人）之間的距離（差異性），就可利用Jaccard相關(guān)系數(shù)計(jì)算公式（Jaccard）進(jìn)行當(dāng)前第44頁\共有139頁\編于星期三\13點(diǎn)

d(Jack,Mary)=(0+1)/(2+0+1)=0.33d(Jack,Jim)=(1+1)/(1+1+1)=0.67d(Jim,Mary)=(1+2)/(1+1+2)=0.75

由于Jim和Mary之間的距離最大，因此不大可能得的是相似病，而Jack,Mary之間的距離最小，因此可能得的是相似病當(dāng)前第45頁\共有139頁\編于星期三\13點(diǎn)（2）分類變量（符號變量）符號變量是二值變量的一個(gè)推廣。符號變量可以對兩個(gè)以上的狀態(tài)進(jìn)行描述。例如：地圖顏色map_color變量就是一個(gè)符號變量，它可以表示五種狀態(tài)，即紅、綠、籃、粉紅和黃色。設(shè)一個(gè)符號變量所取狀態(tài)個(gè)數(shù)為M，其中的狀態(tài)可以用字母、符號，或一個(gè)整數(shù)集合來表示，如：1，2，…，M。這里整數(shù)僅僅是為了方便數(shù)據(jù)處理而采用的，并不表示任何順序關(guān)系。當(dāng)前第46頁\共有139頁\編于星期三\13點(diǎn)

對于分類變量，最常用的計(jì)算對象i和對象j之間差異(程度)的方法就是簡單匹配方法。它的具體定義描述如公式(7-12)所示

d(i,j)=(p-m)/p（7-12)

其中，m表示對象i和對象j中取同樣狀態(tài)的符號變量個(gè)數(shù)(匹配數(shù))，p為所有的符號變量個(gè)數(shù),為增強(qiáng)m的作用，可以給它賦予一定的權(quán)值．

當(dāng)前第47頁\共有139頁\編于星期三\13點(diǎn)(3)序數(shù)變量（順序變量）一個(gè)離散順序變量與一個(gè)符號變量相似，不同的是(對應(yīng)M個(gè)狀態(tài)的)M個(gè)順序值是具有按照一定順序含義的。例如：專業(yè)等級(描述)就是順序變量，它是按照助教、講師、副教授和教授的順序進(jìn)行排列的。一個(gè)連續(xù)順序變量看上去就像一組未知范圍的連續(xù)數(shù)據(jù)，但它的相對位置要比它的實(shí)際數(shù)值有意義得多。例如，在足球比賽中，一個(gè)球隊(duì)排列名次常常要比它的實(shí)際得分更為重要。當(dāng)前第48頁\共有139頁\編于星期三\13點(diǎn)順序變量的數(shù)值常常是通過對數(shù)值(變量)的離散化而獲得的，也就是通過將取值范圍分為有限個(gè)組而得到的。一個(gè)順序變量可以映射到一個(gè)等級(rank)集合上。如：若一個(gè)順序變量f包含Mf個(gè)狀態(tài)，那么這些有序的狀態(tài)就映射為1，2，…，Mf的等級。當(dāng)前第49頁\共有139頁\編于星期三\13點(diǎn)

假設(shè)變量f為一組描述n個(gè)對象順序變量中的一個(gè)。涉及變量f的差異程度計(jì)算:(1)第i個(gè)對象的f變量值標(biāo)記為xif，變量f有Mf個(gè)有序狀態(tài)，可以利用等級1，2，…，Mf分別替換相應(yīng)的xif，得到相應(yīng)的rif，rif

屬于{1，2，…，Mf}。

(2)將每個(gè)順序變量的取值范圍映射到[0，1]區(qū)間，以便使每個(gè)變量的權(quán)值相同。當(dāng)前第50頁\共有139頁\編于星期三\13點(diǎn)可以通過將第i個(gè)對象中的第f個(gè)變量的rif

用以下所計(jì)算得到的值來替換：

zif=(rif–1)/(Mf-1)(7-13)

這時(shí)可以利用所介紹有關(guān)間隔數(shù)值變量的任一個(gè)距離計(jì)算公式，來計(jì)算用順序變量描述的對象間距離，其中用zif來替換第i個(gè)對象中的變量f值。當(dāng)前第51頁\共有139頁\編于星期三\13點(diǎn)(4)比例標(biāo)度變量

P258當(dāng)前第52頁\共有139頁\編于星期三\13點(diǎn)(5)混合類型變量

P259當(dāng)前第53頁\共有139頁\編于星期三\13點(diǎn)(6)向量對象

P260當(dāng)前第54頁\共有139頁\編于星期三\13點(diǎn)6．4主要聚類方法需要根據(jù)應(yīng)用所涉及的數(shù)據(jù)類型、聚類的目的以及具體應(yīng)用要求來選擇合適的聚類算法。如果利用聚類分析作為描述性或探索性的工具，那么就可以使用若干聚類算法對同一個(gè)數(shù)據(jù)集進(jìn)行處理以觀察可能獲得的有關(guān)(數(shù)據(jù)特征)描述。

當(dāng)前第55頁\共有139頁\編于星期三\13點(diǎn)一.聚類的特征與聚類間的距離聚類的數(shù)學(xué)含義:

設(shè)G為元素的集合，共有m個(gè)元素，記為gi，i=1,2…m,

另外給定一個(gè)閾值T>0,則若G中任意兩個(gè)元素gi和gj之間的距離不大于閾值，即有dij<=T,則稱G為類當(dāng)前第56頁\共有139頁\編于星期三\13點(diǎn)若將類G的元素gi視為隨機(jī)向量Xi,則可用以下特征來描述類：1、類的重心----各元素的均向量2、類的直徑DG=也可定義為類中各元素至類中心的歐氏距離之和當(dāng)前第57頁\共有139頁\編于星期三\13點(diǎn)二、分層聚類法

聚集法

先將所有研究對象都各自算作一類，將最“靠近”的首先進(jìn)行聚類，再將這個(gè)類和其他類中最“靠近”的結(jié)合，繼續(xù)合并直到所有對象都綜合成一類或滿足一個(gè)閾值條件為止分割法先將所有研究對象看成一大類，然后割成兩類，使一類中的對象盡可能“遠(yuǎn)離”另一類的對象；再將每一類繼續(xù)這樣分割，直到每個(gè)對象自成一類或滿足一個(gè)閾值條件為止

當(dāng)前第58頁\共有139頁\編于星期三\13點(diǎn)1、最短距離法又稱單連接法或最近鄰連接法基本思想：類之間的距離用從兩個(gè)類中抽取的每對樣本的最小距離作為距離度量，一旦最近的兩個(gè)類的距離超過某個(gè)任意給定的閾值，算法就自動結(jié)束。

當(dāng)前第59頁\共有139頁\編于星期三\13點(diǎn)類間的距離:D{1,2,3,4}{5,6,7}=min{d15,d16,d17,d25,d26,d27,d35,d36,d37,d45,d46,d47}=d37.1.2.4.3

.5.7.6當(dāng)前第60頁\共有139頁\編于星期三\13點(diǎn)假定5個(gè)對象間的距離如下表所示，試用最短距離法聚類并畫出樹形圖編號1234512345004045471550當(dāng)前第61頁\共有139頁\編于星期三\13點(diǎn)解：先將五個(gè)對象都分別看成一個(gè)類，由表看出最靠近的兩個(gè)類是2和5

將2和5合并成一個(gè)新類{2，5}

再求{2，5}和1，3，4之間的距離

d{2,5}1=min{d21,d51}=min{6,7}=6d{2,5)3=min{d23,d53}=min{4,5}=4d{2,5)4=min{d24,d54}=min{4,5}=4編號{2,5}134{2,5}134004204350當(dāng)前第62頁\共有139頁\編于星期三\13點(diǎn)在這4個(gè)類中，最靠近的兩個(gè)類是1和3，合并成{1，3}，再求{1，3}到{2，5}和4的距離d{1,3}{2,5}=min{d1{2,5},d3{2,5}}=4d{1,3}4=min{d14,d34}=3編號{2,5}{1,3}4{2,5}{1,3}4040430當(dāng)前第63頁\共有139頁\編于星期三\13點(diǎn)編號{2,5}{1,3,4}{2,5}{1,3,4}040當(dāng)前第64頁\共有139頁\編于星期三\13點(diǎn)

最短距離的樹形圖

123425134當(dāng)前第65頁\共有139頁\編于星期三\13點(diǎn)

先將五個(gè)樣本都分別看成是一個(gè)簇，最靠近的兩個(gè)簇是3和4，因?yàn)樗麄兙哂凶钚〉拇亻g距離

D（3，4）=5.0。第一步：合并簇3和4，得到新簇集合1,2,（34）,5

練習(xí)一單連接算法(最短距離)當(dāng)前第66頁\共有139頁\編于星期三\13點(diǎn)

更新距離矩陣：

D(1,(34))=min(D(1,3),D(1,4))=min(20.6,22.4)=20.6;D(2,(34))=min(D(2,3),D(2,4))=min(14.1,11.2)=11.2;D(5,(34))=min(D(3,5),D(4,5))=min(25.0,25.5)=25.0.

原有簇1,2,5間的距離不變，修改后的距離矩陣如圖所示，在四個(gè)簇1,2,(34),5中，最靠近的兩個(gè)簇是1和5，它們具有最小簇間距離D（1,5）＝7.07。單連接算法當(dāng)前第67頁\共有139頁\編于星期三\13點(diǎn)

單連接算法當(dāng)前第68頁\共有139頁\編于星期三\13點(diǎn)

單連接算法單連接樹當(dāng)前第69頁\共有139頁\編于星期三\13點(diǎn)

2、最長距離法又稱完全連接法或最遠(yuǎn)緊鄰連接法與最短距離的聚類方法相同區(qū)別:類間的距離定義為兩類中元素之間距離最大者

當(dāng)前第70頁\共有139頁\編于星期三\13點(diǎn)類間的距離:D{1,2,3,4}{5,6,7}=max{d15,d16,d17,d25,d26,d27,d35,d36,d37,d45,d46,d47}=d16.1.2.4.3

.5.7.6當(dāng)前第71頁\共有139頁\編于星期三\13點(diǎn)例6.4

假定5個(gè)對象間的距離如下表所示，試用最長距離法聚類并畫出樹形圖編號1234512345004045471550當(dāng)前第72頁\共有139頁\編于星期三\13點(diǎn)解：先將五個(gè)對象都分別看成一個(gè)類，由表看出最靠近的兩個(gè)類是2和5

也是將2和5合并成一個(gè)新類{2，5}

再求{2，5}和1，3，4之間的距離

d{2,5}1=max{d21,d51}=max{6,7}=7d{2,5)3=min{d23,d53}=max{4,5}=5d{2,5)4=min{d24,d54}=max{4,5}=5編號{2,5}134{2,5}1340705

205350當(dāng)前第73頁\共有139頁\編于星期三\13點(diǎn)在這4個(gè)類中，最靠近的兩個(gè)類是1和3，合并成{1，3}，編號{2,5}134{2,5}1340705

205350當(dāng)前第74頁\共有139頁\編于星期三\13點(diǎn)再求{1，3}到{2，5}和4的距離d{1,3}{2,5}=max{d1{2,5},d3{2,5}}=7d{1,3}4=max{d14,d34}=5編號{2,5}{1,3}4{2,5}{1,3}4070550此時(shí):由于兩個(gè)距離都為5d{1,3}4=5d{2,5}4=5可合并{1,3}和4為{1,3,4}也可合并{2,5}和4為{2,5,4}當(dāng)前第75頁\共有139頁\編于星期三\13點(diǎn)編號{2,5}{1,3,4}{2,5}{1,3,4}070編號{2,5,4}{1,3}{2,5,4}{1,3}070當(dāng)前第76頁\共有139頁\編于星期三\13點(diǎn)

最長距離的樹形圖(a)

123425134當(dāng)前第77頁\共有139頁\編于星期三\13點(diǎn)

最長距離的樹形圖(b)

123425413當(dāng)前第78頁\共有139頁\編于星期三\13點(diǎn)3、中間距離法如假定在聚類的過程中兩個(gè)類G1和G2合并成一個(gè)新類

GN=(G1,G2).則GN和其它任一類G3的距離可定義為G1G2G3三角形中線的平方G3G1G2GN類間距離dG3Gn=d2=1/2[dG3G12+dG3G22

-

(1/2)

dG1G22]注意:中間距離進(jìn)行聚類時(shí),一般都采用距離的平方當(dāng)前第79頁\共有139頁\編于星期三\13點(diǎn)例6.5

假定5個(gè)對象間的距離如下表所示，試用中間距離法聚類并畫出樹形圖編號1234512345004045471550當(dāng)前第80頁\共有139頁\編于星期三\13點(diǎn)編號12345123450360416091625049125250<1>先把原距離平方當(dāng)前第81頁\共有139頁\編于星期三\13點(diǎn)解:還是先將{2,5}合并,然后計(jì)算{2,5}和1,3,4的距離d{2,5}12=1/2[d212+d512

-

(1/2)

d252]=42.25d{2,5}32=20.25d{2,5}42=20.25編號{2,5}134{2,5}134042.25020.254020.259250<2>當(dāng)前第82頁\共有139頁\編于星期三\13點(diǎn)編號{2,5}{1,3}4{2,5}{1,3}4030.25

020.25160<3>當(dāng)前第83頁\共有139頁\編于星期三\13點(diǎn)編號{2,5}{1,3,4}{2,5}{1,3,4}021.250<4>當(dāng)前第84頁\共有139頁\編于星期三\13點(diǎn)4、重心法兩個(gè)類之間的距離定義為兩類重心間的距離

5、類平均法

兩個(gè)類之間的距離定義為兩類中元素兩兩之間的平均距離當(dāng)前第85頁\共有139頁\編于星期三\13點(diǎn)前面是基于距離在對變量進(jìn)行聚類時(shí),一般先求出變量間的相似系數(shù),按照相似系數(shù)越大,兩個(gè)變量越相似的原則聚類,根據(jù)分層聚類的思想,聚類過程完全相似當(dāng)前第86頁\共有139頁\編于星期三\13點(diǎn)下表是24名優(yōu)秀運(yùn)動員的七項(xiàng)全能項(xiàng)目得分間的相關(guān)系數(shù).對這7項(xiàng)指標(biāo)進(jìn)行聚類分析編號x1x2x3x4x5x6x7x1x2x3x4x5x6x71.000.44981.000.6838.46661.000.8466.3296.56751.000.8113.5420.5943.81121.000.3214.2154.6896.3143.32761.000.5706.1498.3726.6790.4957.05561.000當(dāng)前第87頁\共有139頁\編于星期三\13點(diǎn)改進(jìn)的層次聚類BIRCH是一個(gè)綜合的層次聚類方法，它引入了兩個(gè)概念：聚類特征和聚類特征樹（CF樹）CURE方法采用了一種新穎的層次聚類算法，該算法選擇基于重心和基于代表對象方法之間的中間策略。ROCK方法是一個(gè)可選的凝聚的層次聚類算法，適用于分類屬性。Chameleon（變色龍）方法是一個(gè)在層次聚類中采用動態(tài)模型的層次聚類算法當(dāng)前第88頁\共有139頁\編于星期三\13點(diǎn)三、劃分方法（動態(tài)聚類法）

最常用也是最知名的劃分方法就是k-means算法和k-medoids算法，

1、k-means算法

算法7．1根據(jù)聚類中的均值進(jìn)行聚類劃分的k-means算法。輸入：聚類個(gè)數(shù)k，以及包含n個(gè)數(shù)據(jù)對象的數(shù)據(jù)庫。輸出：滿足方差最小標(biāo)準(zhǔn)的k個(gè)聚類。

當(dāng)前第89頁\共有139頁\編于星期三\13點(diǎn)處理流程：

(1)從n個(gè)數(shù)據(jù)對象任意選擇k個(gè)對象作為初始聚類中心。

(2)使用歐氏距離將剩余實(shí)例賦給距離它們最近的簇中心

(3)使用每簇中的實(shí)例計(jì)算每個(gè)簇對象的均值(中心對象)，計(jì)算每個(gè)對象與這些中心對象的距離，并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行分類。

(4)重新計(jì)算每個(gè)(有變化)聚類的均值(中心對象)，直至新平均值等于上次迭代的平均值，算法結(jié)束。

當(dāng)前第90頁\共有139頁\編于星期三\13點(diǎn)

如

:

假設(shè)空間數(shù)據(jù)對象分布如圖(a)所示，設(shè)是k＝3，也就是需要將數(shù)據(jù)集劃分為3份(聚類)。

當(dāng)前第91頁\共有139頁\編于星期三\13點(diǎn)根據(jù)算法6．1，從數(shù)據(jù)集中任意選擇三個(gè)對象作為初始聚類中心(圖(a)中這些對象被標(biāo)上了“+”)，其余對象則根據(jù)與這三個(gè)聚類中心(對象)的距離，根據(jù)最近距離原則，逐個(gè)分別聚類到這三個(gè)聚類中心所代表的(3個(gè))聚類中，由此獲得了如圖(a)所示的三個(gè)聚類(以虛線圈出)當(dāng)前第92頁\共有139頁\編于星期三\13點(diǎn)

在完成第一輪聚類之后，各聚類中心發(fā)生了變化。繼而更新3個(gè)聚類的聚類中心(圖(b)中這些對象被標(biāo)上了“十”)，也就是分別根據(jù)各聚類中的對象重新計(jì)算相應(yīng)聚類的(對象)均值。根據(jù)所獲得的3個(gè)新聚類中心，以及各對象與這三個(gè)聚類中心的距離，(根據(jù)最近距離原則)對所有對象進(jìn)行重新歸類。有關(guān)變化情況如圖(b)所示(已用粗虛線圈出)。當(dāng)前第93頁\共有139頁\編于星期三\13點(diǎn)圖6.2當(dāng)前第94頁\共有139頁\編于星期三\13點(diǎn)

再次重復(fù)上述過程就可獲得如圖(c)所示的聚類結(jié)果(已用實(shí)線圈出)，這時(shí)由于各聚類中的對象(歸屬)已不再變化，整個(gè)聚類結(jié)束。

當(dāng)前第95頁\共有139頁\編于星期三\13點(diǎn)例6.6k-means算法舉例實(shí)例xy1234561.01.02.02.03.05.01.54.51.53.52.56.0當(dāng)前第96頁\共有139頁\編于星期三\13點(diǎn)Step1:設(shè)Ｋ＝2,算法任意選擇兩個(gè)點(diǎn)作為初始簇中心，假設(shè)算法選擇實(shí)例１作為第一個(gè)簇的中心，即Ｃ１＝（1.0,1.5)實(shí)例（２.0,1.5)作為第二個(gè)簇的中心，即Ｃ２＝（2.0,1.5)第二步，第一次迭代，分別計(jì)算樣本實(shí)例到C1，C2的歐氏距離：Distance(C1,1)=0.00Distance(C2,1)=1.00Distance(C1,2)=3.00Distance(C2,2)=3.16Distance(C1,3)=1.00Distance(C2,3)=0.08Distance(C1,4)=2.24Distance(C2,4)=2.00Distance(C1,5)=2..24Distance(C2,5)=1.41Distance(C1,6)=6.02Distance(C2,6)=5.41當(dāng)前第97頁\共有139頁\編于星期三\13點(diǎn)確定C1，C2C1包含實(shí)例1(1.0,1.5)和2(1.0，4.5)C2包含實(shí)例3，4，5，6Step3：重新計(jì)算每個(gè)簇的中心對于簇C1：x=(1.0+1.0)/2=1.0y=(1.5+4.5)/2=3.0對于簇C2：x=(2.0+2.0+3.0+5.0)/4=3.0Y=(1.5+3.5+2.5+6.0)/4=3.375因此新的簇中心為：C1=(1.0,3.0)C2=(3.0,3.375)Step4:進(jìn)行第二次迭代：當(dāng)前第98頁\共有139頁\編于星期三\13點(diǎn)Distance(C1,1)=1.50Distance(C2,1)=2.74Distance(C1,2)=1.50Distance(C2,2)=2.29Distance(C1,3)=1.80Distance(C2,3)=2.125Distance(C1,4)=1.12Distance(C2,4)=1.01Distance(C1,5)=2..06Distance(C2,5)=0.875Distance(C1,6)=5.00Distance(C2,6)=3.30此時(shí)C1包含實(shí)例1,2,3C2包含實(shí)例4,5,6Step5:對每個(gè)簇重新計(jì)算新的中心，可得到：

C1=（1.33,2.50)C2=(3.33,4.00)繼續(xù)直到類中心不再發(fā)生變化當(dāng)前第99頁\共有139頁\編于星期三\13點(diǎn)

對于初始中心的每種選擇，最后都會得到不同的簇配置。這是K-means算法的通病，也就是說：盡管算法能確保實(shí)例聚類到一個(gè)穩(wěn)定的狀態(tài)，但不能保證最佳穩(wěn)定性。

K-means算法的最優(yōu)聚類：實(shí)例到它們對應(yīng)簇中心的誤差平方和最小。對于給定K值，要找到一個(gè)最優(yōu)聚類，必須根據(jù)初始中心的不同選擇來重復(fù)執(zhí)行算法。

當(dāng)前第100頁\共有139頁\編于星期三\13點(diǎn)例如，對上表重復(fù)應(yīng)用K-means算法而獲得的三類聚類結(jié)果：輸出結(jié)果簇中心簇點(diǎn)均方差

1(2.67,4.67)

2,4,614.50(2.00,1.83)

1,3,5

2(1.5,1.5)

1,315.94(2.75,4.125)2,4,5,6

3(1.8,2.7)1,2,3,4,59.60(5,6)6當(dāng)前第101頁\共有139頁\編于星期三\13點(diǎn)k－means聚類算法練習(xí)坐標(biāo)表示5個(gè)點(diǎn)｛X1,X2,X3,X4,X5｝作為一個(gè)聚類分析的二維樣本：X1＝（0,2），X2＝（0,0），X3＝（1.5,0），X4＝（5,0），X5＝（5,2）。假設(shè)要求的簇的數(shù)量k=2。第1步：由樣本的隨機(jī)分布形成兩個(gè)簇：C1＝｛X1,X2,X4｝和C2＝｛X3,X5｝。這兩個(gè)簇的質(zhì)心M1和M2是：M1＝｛(0+0+5)/3,(2+0+0)/3｝＝｛1.66，0.66｝；M2＝｛（1.5+5）/2，（0+2）/2｝＝｛3.25，1.00｝；當(dāng)前第102頁\共有139頁\編于星期三\13點(diǎn)基于質(zhì)心的k－means聚類算法樣本初始隨機(jī)分布之后，方差是：

e12=[(0-1.66)2+(2-0.66)2]+[(0-1.66)2+(0-0.66)2]+[(5-1.66)2+(0-0.66)2]=19.36；

e22=8.12；總體平方誤差是：E2＝e12+e22＝19.36+8.12＝27.48（公式）當(dāng)前第103頁\共有139頁\編于星期三\13點(diǎn)基于質(zhì)心的k－means聚類算法第2步：取距離其中一個(gè)質(zhì)心（M1或M2）最小的距離分配所有樣本，簇內(nèi)樣本的重新分布如下：d(M1,X1)=(1.662+1.342)1/2=2.14d(M2,X1)=3.40==>X1∈C1；d(M1,X2)=1.79和d(M2,X2)=3.40==>X2∈C1d(M1,X3)=0.83和d(M2,X3)=2.01==>X3∈C1d(M1,X4)=3.41和d(M2,X4)=2.01==>X4∈C2d(M1,X5)=3.60和d(M2,X5)=2.01==>X5∈C2新簇C1＝｛X1,X2,X3｝和C2＝｛X4,X5｝當(dāng)前第104頁\共有139頁\編于星期三\13點(diǎn)基于質(zhì)心的k－means聚類算法第3步：計(jì)算新的質(zhì)心：M1＝｛0.5，0.67｝；M2＝｛5.0，1.0｝。相應(yīng)的方差及總體平方誤差分別是：e12＝4.17；e22＝2.00；E＝6.17；可以看出第一次迭代后，總體誤差顯著減?。◤闹?7.48到6.17）。在這個(gè)簡單的例子中，第一次迭代同時(shí)也是最后一次迭代，因?yàn)槿绻^續(xù)分析新中心和樣本間的距離，樣本將會全部分給同樣的簇，不將重新分配，算法停止。當(dāng)前第105頁\共有139頁\編于星期三\13點(diǎn)

k-means算法復(fù)雜度為O(nkt),因而它在處理大數(shù)據(jù)庫時(shí)也是相對有效的(具有可擴(kuò)展性)。這里n為對象個(gè)數(shù)，k為聚類個(gè)數(shù)，t為循環(huán)次數(shù)。當(dāng)前第106頁\共有139頁\編于星期三\13點(diǎn)

但是k-means算法只適用于聚類均值有意義的情況。因此在某些應(yīng)用中，諸如：數(shù)據(jù)集包含符號屬性時(shí)，直接應(yīng)用k-means算法就有困難了。

k-means算法另一個(gè)缺點(diǎn)就是用戶須事先指定聚類個(gè)數(shù)k。此外，k-means算法對噪聲和異常數(shù)據(jù)也很敏感，因?yàn)檫@類數(shù)據(jù)可能會影響到類的均值(計(jì)算結(jié)果)。當(dāng)前第107頁\共有139頁\編于星期三\13點(diǎn)

k-means算法還有一些變化(版本)。它們主要在初始k個(gè)聚類中心的選擇、差異程度計(jì)算和聚類中心均值的計(jì)算方法等方面有所不同。

當(dāng)前第108頁\共有139頁\編于星期三\13點(diǎn)

數(shù)據(jù)挖掘的內(nèi)容經(jīng)常含有離散數(shù)據(jù)，傳統(tǒng)的方法是轉(zhuǎn)換離散數(shù)據(jù)為數(shù)值值，經(jīng)常得不出有意義的結(jié)果

k-modes算法去除了這個(gè)限制，并在保留k-means算法效率的同時(shí)將應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)。與k-means算法相比，k-modes算法使用了不同的非相似性度量以及一個(gè)基于頻率的方式對模式更新

當(dāng)前第109頁\共有139頁\編于星期三\13點(diǎn)

非相似性度量：設(shè)X，Y是由m個(gè)離散屬性描述的兩個(gè)離散對象，X，Y之間的非相似性度量可用兩個(gè)對象的對應(yīng)的屬性離散值的總不匹配量來定義。

d(X,Y)=（xj,yj)（xj,yj)=0xi=yj1xiyj當(dāng)前第110頁\共有139頁\編于星期三\13點(diǎn)

將k-means算法和k-modes算法結(jié)合到一起，就可以對采用數(shù)值量和符號量描述對象進(jìn)行聚類分析，從而構(gòu)成了k-prototypes算法。當(dāng)前第111頁\共有139頁\編于星期三\13點(diǎn)

2．k-medoids算法

k-means算法對異常數(shù)據(jù)很敏感。

medoid設(shè)置一個(gè)參考點(diǎn)代替k-means算法中的各聚類的均值(作為聚類中心--medoid)。從而可以根據(jù)各對象與各參考點(diǎn)之間的距離(差異性)之和最小化的原則，繼續(xù)應(yīng)用劃分方法。當(dāng)前第112頁\共有139頁\編于星期三\13點(diǎn)

基本策略：首先任意為每個(gè)聚類找到一個(gè)代表對象(medoid)而確定n個(gè)數(shù)據(jù)對象的k個(gè)聚類，(也需要循環(huán)進(jìn)行)其它對象則根據(jù)它們與這些聚類代表的距離分別歸屬到各相應(yīng)聚類中(仍然是最小距離原則)。如果替換一個(gè)聚類代表能夠改善所獲聚類質(zhì)量的話，用一個(gè)新對象替換老聚類對象。

當(dāng)前第113頁\共有139頁\編于星期三\13點(diǎn)

基于：各對象與其聚類代表間距離的成本函數(shù)來對聚類質(zhì)量進(jìn)行評估。為了確定任一個(gè)非聚類代表對象orandom是否可以替換當(dāng)前一個(gè)聚類代表oj需要根據(jù)以下四種情況對各非聚類代表對象p進(jìn)行檢查。當(dāng)前第114頁\共有139頁\編于星期三\13點(diǎn)

(1)如圖7-4(a)所示，若對象p當(dāng)前屬于oj(所代表的聚類)，且如果用orandom

替換oj

作為新聚類代表，而p更接近其它oi，則將p歸類到oi(所代表的聚類)中。

(2)如圖7-4(b)所示，若對象P當(dāng)前屬于oj(所代表的聚類)，且如果用orandom

替換oj

作為新聚類代表，而p就更接近orandom

，那么就將p歸類到orandom(所代表的聚類)中。當(dāng)前第115頁\共有139頁\編于星期三\13點(diǎn)6-3當(dāng)前第116頁\共有139頁\編于星期三\13點(diǎn)

(3)如圖7-4(a)所示，若對象p當(dāng)前屬于oi(所代表的聚類)(ij)，且如果用orandom

替換oj

作為新聚類代表，而p仍最接近oi，那么p的歸類不發(fā)生變化。

(4)如圖7-4(b)所示，若對象p當(dāng)前屬于oi(所代表的聚類)(ij)，且如果用orandom

替換oj

作為新聚類代表，而p就更接近orandom

，那么就將p歸類到orandom(所代表的聚類)中。當(dāng)前第117頁\共有139頁\編于星期三\13點(diǎn)6.4當(dāng)前第118頁\共有139頁\編于星期三\13點(diǎn)

圖7-3和圖7-4分別示意描述了上述k-medoids聚類算法的四種主要處理情況。每次對對象進(jìn)行重新歸類，都會使得構(gòu)成成本函數(shù)的方差發(fā)生變化。因此，成本函數(shù)能夠計(jì)算出聚類代表替換前后的方差變化。通過替換不合適的代表來使距離方差發(fā)生變化的累計(jì)就構(gòu)成了成本函數(shù)的輸出值。當(dāng)前第119頁\共有139頁\編于星期三\13點(diǎn)替換規(guī)則

(1)若整個(gè)輸出成本為負(fù)值，那么就用Orandom替換oj，以便能夠減少實(shí)際的方差E。(2)若整個(gè)輸出成本為正值，那么就認(rèn)為當(dāng)前的oj是可接受的，本次循環(huán)就無需變動。當(dāng)前第120頁\共有139頁\編于星期三\13點(diǎn)

算法7．2

根據(jù)聚類的中心對象(聚類代表)進(jìn)行聚類劃分的k-medoids算法。

輸入：聚類個(gè)數(shù)k，以及包含n個(gè)數(shù)據(jù)對象的數(shù)據(jù)庫。輸出：滿足基于各聚類中心對象的方差最小標(biāo)準(zhǔn)的k個(gè)聚類。

當(dāng)前第121頁\共有139頁\編于星期三\13點(diǎn)處理流程：

(1)從n個(gè)數(shù)據(jù)對象任意選擇k個(gè)對象作為初始聚類(中心)代表。

(2)循環(huán)(3)到(5)直到每個(gè)聚類不再發(fā)生變化為止。

(3)依據(jù)每個(gè)聚類的中心代表對象，以及最小距離重新對相應(yīng)對象進(jìn)行劃分。

(4)任意選擇一個(gè)非中心對象Orandom；計(jì)算其與中心對象oj交換的整個(gè)成本S。

(5)若S為負(fù)值則交換Orandom與oj以構(gòu)成新聚類的k個(gè)中心對象。當(dāng)前第122頁\共有139頁\編于星期三\13點(diǎn)

k-medoids聚類算法比k-means聚類算法在處理異常數(shù)據(jù)和噪聲數(shù)據(jù)方面更為魯棒，因?yàn)榕c聚類均值相比，一個(gè)聚類中心的代表對象要較少受到異常數(shù)據(jù)或極端數(shù)據(jù)的影響。但是前者的處理時(shí)間要比后者更大。兩個(gè)算法都需要用戶事先指定所需聚類個(gè)數(shù)k。當(dāng)前第123頁\共有139頁\編于星期三\13點(diǎn)

PAM(PartitioningAroundMedoids--圍繞中心對象進(jìn)行劃分)方法是最初提出的k-medoids聚類算法之一。它在初始選擇k個(gè)聚類中心對象之后，不斷循環(huán)對每兩個(gè)對象(一個(gè)為非中心對象，一個(gè)為中心對象)進(jìn)行分析，以便選擇出更好的聚類中心代表對象。并根據(jù)每組對象分析計(jì)算所獲得的聚類質(zhì)量。若一個(gè)中心對象oj被替換后導(dǎo)致方差迅速減少，那么就進(jìn)行替換。對于較大的n與k值這樣的計(jì)算開銷也非常大。

PAM算法的計(jì)算復(fù)雜性為O(k(n-k)2)

當(dāng)前第124頁\共有139頁\編于星期三\13點(diǎn)像PAM方法這樣典型的k-medoids聚類算法，在小數(shù)據(jù)集上可以工作得很好；但是對于大數(shù)據(jù)庫則處理效果并不理想。為此.當(dāng)前第125頁\共有139頁\編于星期三\13點(diǎn)四.大數(shù)據(jù)庫的劃分方法

CLARA是由Kaufman和Rousseeuw為處理大數(shù)據(jù)量而開發(fā)的。CLARA(Cluste—ringLARgeApplication)不是在整個(gè)數(shù)據(jù)集上發(fā)現(xiàn)代表對象，而是從數(shù)據(jù)集的樣本中發(fā)