Chapter5.聚類分析聚類分析概述聚類分析的數據類型主要聚類分析方法分類劃分方法（PartitioningMethods）分層方法基于密度的方法基于網格的方法基于模型（Model-Based）的聚類方法5.1聚類分析概述簇（Cluster）:一個數據對象的集合在同一個類中，對象之間具有相似性；不同類的對象之間是相異的。聚類分析(群分析、簇群分析)把一個給定的數據對象集合分成不同的簇；所謂聚類就是按照事物的某些屬性,把事物聚集成類,使類間的相似性盡可能的小,類內相似性盡量大的過程聚類是一種無監督分類法:沒有預先指定的類別；聚類分析中“類”的特征：聚類所說的類不是事先給定的，而是根據數據的相似性和距離來劃分聚類的數目和結構都沒有事先假定典型的應用作為一個獨立的分析工具，用于了解數據的分布；作為其它算法的一個數據預處理步驟；---異常分析聚類的常規應用模式識別空間數據分析在GIS中，通過聚類發現特征空間來建立主題索引；在空間數據挖掘中，檢測并解釋空間中的簇；圖象處理經濟學(尤其是市場研究方面)WWW文檔分類分析WEB日志數據來發現相似的訪問模式應用聚類分析的例子市場銷售:幫助市場人員發現客戶中的不同群體，然后用這些知識來開展一個目標明確的市場計劃；土地使用:在一個陸地觀察數據庫中標識那些土地使用相似的地區；保險:對購買了汽車保險的客戶，標識那些有較高平均賠償成本的客戶；城市規劃:根據類型、價格、地理位置等來劃分不同類型的住宅；地震研究:根據地質斷層的特點把已觀察到的地震中心分成不同的類；聚類分析原理介紹聚類方法的目的是尋找數據中：潛在的自然分組結構astructureof“natural”grouping感興趣的關系relationship聚類分析原理介紹什么是自然分組結構Naturalgrouping?我們看看以下的例子：有16張牌如何將他們分為一組一組的牌呢？AKQJ聚類分析原理介紹分成四組每組里花色相同組與組之間花色相異AKQJ花色相同的牌為一副Individualsuits聚類分析原理介紹分成四組符號相同的牌為一組AKQJ符號相同的的牌Likefacecards聚類分析原理介紹分成兩組顏色相同的牌為一組AKQJ顏色相同的配對Blackandredsuits聚類分析原理介紹這個例子告訴我們，分組的意義在于我們怎么定義并度量“相似性”Similar因此衍生出一系列度量相似性的算法AKQJ大配對和小配對Majorandminorsuits什么是一個好的聚類方法?一個好的聚類方法要能產生高質量的聚類結果——簇，這些簇要具備以下兩個特點：高的簇內相似性低的簇間相似性

聚類結果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實現；可伸縮性能夠處理不同類型的屬性能發現任意形狀的簇在決定輸入參數的時候，盡量不需要特定的領域知識能夠處理噪聲和異常對輸入數據對象的順序不敏感能處理高維數據能產生一個好的、能滿足用戶指定約束的聚類結果結果是可解釋的、可理解的和可用的5.2聚類分析算法分類

層次法

化分法基于密度類方法基于網格類方法基于模型類方法

1.層次的方法（系統聚類法）（hierarchicalmethod）（1）定義：對給定的數據進行層次的分解可分為：凝聚（agglomerative）方法（自底向上）

思想：一開始將每個對象作為單獨的一組，然后根據同類相近，異類相異的原則，合并對象，直到所有的組合并成一個，或達到一個終止條件為止。分裂方法（divisive）（自頂向下）

思想：一開始將所有的對象置于一類，在迭代的每一步中，一個類不斷地分為更小的類，直到每個對象在單獨的一個類中，或達到一個終止條件。

（2）特點類的個數不需事先定好需確定距離矩陣運算量大，適用于處理小樣本數據

缺點:一旦一個步驟（合并或分裂）完成，它就不能被撤消，因此而不能更正錯誤的決定。代表算法有：BIRCH算法(利用層次方法的平衡迭代歸約和聚類）CURE算法（利用代表點聚類）2、分裂法（partitioningmethod）

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

（1）每個分組至少包含一個數據記錄（2）每一個數據記錄屬于且僅屬于一個分組（在某些模糊聚類算法中可以放寬）對于一個給定的K，算法首先給出一個初始的分組方法，以后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案都較前一次好。好的標準就是：同組記錄越來越近，不同組記錄越來越好使用這個算法的基本思想有：K-MEANS算法、KMEDOID算法、CLARANS算法3、基于密度的方法(density-basedmethod)它與其他方法的根本區別：不是基于各種各樣的距離的、而是基于密度的，這樣就能克服基于距離的算法只能發現“類圓形”聚類的缺點。其主要思想是：只要臨近區域的密度超過某個閾值，就繼續聚類。這樣的方法可以用來過濾“噪聲”孤立點數據，發現任意形狀的簇。代表算法有：DBSCAN算法（基于高密度連接區域的密度聚類方法）OPTICS算法、DENCLUE算法4、基于網格的方法(grid-basedmethod)

基于網格的聚類方法采用一個網格數據結構。把對象空間量化為有限數目的單元，形成了一個網格結構。優點:處理速度很快

代表算法有：STING算法（統計信息風格）、CLIQUE算法、WAVE-CLUSTER算法

5、基于模型的方法(model-basedmethod)

給每個聚類假設一個模型（如密度分布函數），然后去尋找能很好地滿足這個模型的數據集。它的潛在的一個假定是：目標數據集是由一系列的概率分布所決定的。通常有兩種：統計方案和神經網絡方案

ex5.1:在病理分析時發現肺癌患者的頭發中微量元素的含量與正常人相比有無異常變化。如果以Cr，Cd及As含量的一個函數作為變量x1:x1=f(Cr，Cd,As)以Se,Zn含量的另一個函數做為變量x2,則x2=g(Se,Zn)在以x1為橫坐標，x2為縱坐標的平面上，每個檢查者按這些微量元素的含量在該平面上占據一點，其分布情況如下：x1

x2健康人群初期患者后期患者5．3聚類分析中的數據類型假設一個要進行聚類分析的數據集包含n個對象，這些對象可以是人、房屋、文件等。聚類算法通常都采用以下兩種數據結構：

兩種數據結構數據矩陣(twomodes)差異度矩陣(onemode)1．數據矩陣數據矩陣是一個對象—屬性結構。它是n個對象組成，例如：人的對象是利用P個屬性來進行描述的，如：年齡、高度、重量等。數據矩陣采用關系表形式或nP矩陣來表示，如（5.1)式圖(5.1)

常稱為樣本數據矩陣。其中第i個樣品p個變量的觀測值可以記為向量：xi=(xi1,xi2,…xip)Tx11…x1f….x1p…………xi1…xif…xip…………xn1…xnf….xnp

由于各變量表示樣品的各種性質，往往使用不同的度量單位，其觀測值也可能相差十分懸殊。這樣，絕對值大的變量其影響可能會湮沒絕對值小的變量，使后者應有的作用得不到反映。為了確保各變量在分析中的地位相同，往往需要對數據進行標準化變換。

標準化測量------給所有屬性相同的權值而在一些應用中，用戶會有意識地賦予某些屬性更大權值以突出其重要性。例如：在對候選籃球選手進行聚類分析時，可能就會給身高屬性賦予更大的權值。

常用的標準化手段有:標準差標準化極差標準化極差正軌化

標準差標準化分兩步:（1）計算絕對偏差均值sj

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

＝（2）計算標準化測量值（z-分量）

zij=

----變換后，變量的均值為0，標準差為1極差標準化Rj=max(xij)-min(xij)(1=<i<=n)(2)----變換后，變量的均值為0，極差為1極差正規化Rj=max(xij)-min(xij)(1=<i<=n)(2)----變換后，變量的極小值為0，極差為12、差異矩陣差異矩陣是一個對象-對象結構。它存放n個對象彼此之間所形成的差異。一般采用nn矩陣表示

圖(5.2)

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

…………d(n,1)d(n,2)…….0

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

許多聚類算法都是基于差異矩陣進行聚類分析的。如果數據是以數據矩陣形式給出的，就需要先轉換為差異矩陣，才能利用聚類算法進行處理。3、基于數值型數據的差異矩陣計算在標準化之后，或在無需標準化的特定應用中，由數值所描述對象之間的差異(或相似)程度可以通過計算相應兩個對象之間距離來確定。最常用的距離計算公式就是歐氏距離具體公式內容如下：

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

j=(xj1,xj2,….xjp)分別表示一個P維數據對象另一個常用的距離計算方法就是Manhattan距離，它的具體計算公式定義如下：d(i，,j)＝|xi1-xj1|+|xi2-xj2|+…+|xip-xjp|(5.4)---------------Manhattan距離歐氏距離和Manhattan距離均滿足距離函數的有關數學性質(要求)：d(i，j)≥0，表示對象之間距離為非負數的一個數值。·d(i，j)＝0，表示對象自身之間距離為零。，d(i，j)＝d(j，i)，表示對象之間距離是對稱函數。d(i，j)≤d(i，h)+d(h，j)，表示對象自身之間距離滿足“兩邊之和不小于第三邊”的性質

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

其中，q為一個正整數，當q＝1時，它代表Manhattan距離計算公式；當q二2時，它代表歐氏距離計算公式。可以為每個變量賦予一個權值，以表示其所代表屬性的重要性還有契比雪夫距離、馬氏距離等相似性度量

例：對于一個4維向量X1＝｛1,0,1,0｝X2＝｛2,1,-3,-1｝，這些距離的度量標準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除距離外，還有相似系數法：兩個對象間的相似系數也可有多種定義形式如：

夾角余弦法相關系數法等

①夾角余弦兩變量的夾角余弦定義為：

變量xi與xj的夾角余弦定義為

它是Rn中變量xi的觀測向量(x1i,x2i,?,xni)′與變量xj的觀測向量(x1j,x2j,?,xnj)′之間夾角θij的余弦函數，即cij(1)=cosθij。②相關系數兩變量的相關系數定義為：

如果變量xi與xj是已標準化了的，則它們間的夾角余弦就是相關系數4、其它類型的變量相似性值（1）二值變量一個二值變量僅取0或1值，其中0代表(變量所表示的)狀態不存在；1代表相應的狀態存在。給定變量smoker，它描述一個病人是否吸煙情況。如：smoker為1表示病人吸煙，若smoker為0，表示病人不吸煙。

計算方法:根據二值數據計算差異矩陣；如果認為所有的二值變量的權值均相同，那么就能得到一個22條件表，如下圖5．3所示。對象j對象i

10合計

1

qrq+r0stS+t合計q+sr+tp圖5.3表中q表示在對象i和對象j中均取1的二值變量個數，r表示在對象i取1而在對象j中取0的二值變量個數，s表示在對象i中取0而在對象j中取1的二值變量個數,t表示在對象i中取i取0而在對象j中取0的二值變量個數二值變量的總個數為p，那么就有p＝q+r+s+t對稱變量:

如果一個二值變量取0或1所表示的內容同樣重要，那么該二值變量就是對稱的。如“性別”就是對稱變量，因為它究竟是用0還是用1來(編碼)表示“男”，“女”并不重要。同樣的基于對稱二值變量所計算相應的相似(或差異)性稱為不變相似性（invariantsimilarity)，因為無論如何對相應二值變量進行編碼并不影響到它們相似(或差異)性的計算結果。對于不變相似性(計算)，最常用的描述對象i和對象j之間差異(程度)參數是簡單匹配關系數，定義:

d(i,j)=(r+s)/(q+r+s+t)(5.6)非對稱變量:

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

給定兩個非對稱二值變量，如果它們認為取1值比取0值所表示的情況更重要，那么，這樣的二值變量就稱為是單性的（好象一個狀態），最常用的描述對象i和j的差異(程度)參數就是Jaccard相關系數，具體定義:

d(i,j)=(r+s)/(q+r+s)(5.7)

ex5．2二值變量的差異性。假設一個病人記錄表如表5．1所示，表中所描述的屬性(變量)分別為:name，gender，fever，cough，test-1，test-2，test-3和test-4其中，name作為(病人)對象的標識，gender(性別)是一個對稱二值變量。其它變量則均為非對稱變量。

表5.1包含許多二值屬性的關系數據表示意描述namegenderfevercoughtest-1test-2test-3test-4JackMY(1)N(0)P(1)N(0)N(0)N(0)MaryFY(1)N(0)P(1)N(0)P(1)N(0)JimMY(1)Y(1)N(0)N(0)N(0)N(0)…..……….………….對于非對稱屬性（變量）值，將Y和P設為1，N設為0。根據非對稱屬性（變量）計算不同對象（病人）之間的距離（差異性），就可利用Jaccard相關系數計算公式（5.7）進行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之間的距離最小，因此可能得的是相似病（2）符號變量

符號變量是二值變量的一個推廣。符號變量可以對兩個以上的狀態進行描述。例如：地圖顏色map_color變量就是一個符號變量，它可以表示五種狀態，即紅、綠、籃、粉紅和黃色。設一個符號變量所取狀態個數為M，其中的狀態可以用字母、符號，或一個整數集合來表示，如：1，2，…，M。

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

d(i,j)=(p-m)/p（5.8)m表示對象i和對象j中取同樣狀態的符號變量個數(匹配數)，p為所有的符號變量個數.有時,為增強m的作用，可以給它賦予一定的權值．如：color1={紅，綠，藍，粉，黃｝color2={紅，黑，藍，白，黃｝則m=3p=7

(3)順序變量一個離散順序變量與一個符號變量相似，不同的是(對應M個狀態的)M個順序值是具有按照一定順序含義的。例如：專業等級(描述)就是順序變量，它是按照助教、講師、副教授和教授的順序進行排列的。

順序變量的數值常常是通過對數值(變量)的離散化而獲得的，也就是通過將取值范圍分為有限個組而得到的。一個順序變量可以映射到一個等級(rank)集合上。如：若一個順序變量f包含Mf個狀態，那么這些有序的狀態就映射為1，2，…，Mf的等級。

假設變量f為一組描述n個對象順序變量中的一個。涉及變量f的差異程度計算:(1)第i個對象的f變量值標記為xif，變量f有Mf個有序狀態，可以利用等級1，2，…，Mf分別替換相應的xif，得到相應的rif，rif屬于{1，2，…，Mf}。(2)將每個順序變量的取值范圍映射到[0，1]區間，以便使每個變量的權值相同。如可以通過將第i個對象中的第f個變量的rif用以下所計算得到的值來替換：

zif=(rif–1)/(Mf-1)(5.9)

這時可以利用所介紹有關間隔數值變量的任一個距離計算公式，來計算用順序變量描述的對象間距離，其中用zif來替換第i個對象中的變量f值。(4)混合類型屬性在實際數據庫中，數據對象往往是用復合(混合)數據類型來描述，而且常常它們(同時)包含上述多種數據類型。

此時,應將所有類型的變量放在一起進行處理，一次(性)完成整個聚類分析。這就需要將不同類型變量(值)組合到一個差異矩陣中，并將它們所有有意義的值全部映射到[0，1]區間內。

假設一個數據集包含p個組合類型變量，則對象i和對象j之間距離d(i，j)可以定義為：

其中，如果（1）xif或xjf數據不存在（對象i對象j的變量無f測量值）或（2）xif=xjf=0，且變量f為非對稱二值變量，則標記ij(f)=0，否則ij(f)=1。ij(f)表示變量f對對象i和對象j之間差異程度（距離）的貢獻

dij(f)可以根據其具體變量類型進行相應計算：(1)若變量f為二值變量或符號變量，則：如果xif=xjf，那么dij(f)＝0，否則dij(f)=1(2)若變量f為數值變量，則dij(f)=|xif-xjf|/（max(xhf)–min(xhf)),其中，h為變量f的所有可能對象。（3）若變量f為順序變量，則計算順序rif和zif=(rif–1)/Mf-1并將zif當作間隔數值變量來進行計算處理。5．4主要聚類方法的實現需要根據應用所涉及的數據類型、聚類的目的以及具體應用要求來選擇合適的聚類算法。如果利用聚類分析作為描述性或探索性的工具，那么就可以使用若干聚類算法對同一個數據集進行處理以觀察可能獲得的有關(數據特征)描述。

若將類G的元素gi視為隨機向量Xi,則可用以下特征來描述類：1、類的重心(中心，質心）----各元素的均向量2、類的直徑DG=也可定義為類中各元素至類中心的歐氏距離之和一.有關概念二、分層聚類法

聚集法

先將所有研究對象都各自算作一類，將最“靠近”的首先進行聚類，再將這個類和其他類中最“靠近”的結合，繼續合并直到所有對象都綜合成一類或滿足一個閾值條件為止

分割法先將所有研究對象看成一大類，然后割成兩類，使一類中的對象盡可能“遠離”另一類的對象；再將每一類繼續這樣分割，直到每個對象自成一類或滿足一個閾值條件為止

圖5-4凝聚聚類和分裂聚類

通過層次聚類算法，將把數據集組成一個聚類樹，大大的縮短了聚類分析所需要的時間。但是，分裂/凝聚的過程不可逆，使得聚類結果有時不準確。1、最短距離法

又稱單連接法或最近鄰連接法

定義類與類之間的距離為兩類最近樣品間的距離，即圖6.3.1最短距離法：DKL=d23例5.3假定5個對象間的距離如下表所示，試用最短距離法聚類并畫出樹形圖編號1234512345004045471550解：先將五個對象都分別看成一個類，由表看出最靠近的兩個類是2和5將2和5合并成一個新類{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在這4個類中，最靠近的兩個類是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編號{2,5}{1,3,4}{2,5}{1,3,4}040

最短距離的樹形圖1234251342、最長距離法

又稱完全連接法或最遠緊鄰連接法

類與類之間的距離定義為兩類最遠樣品間的距離，即圖6.3.3最長距離法：DKL=d15最長距離最短距離ABCDEF異常值的影響最長距離法容易被異常值嚴重地扭曲，一個有效的方法是將這些異常值單獨拿出來后再進行聚類。例5.4假定5個對象間的距離如下表所示，試用最長距離法聚類并畫出樹形圖編號1234512345004045471550解：先將五個對象都分別看成一個類，由表看出最靠近的兩個類是2和5也是將2和5合并成一個新類{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在這4個類中，最靠近的兩個類是1和3，合并成{1，3}，編號{2,5}134{2,5}1340705

205350再求{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此時:由于兩個距離都為5d{1,3}4=5d{2,5}4=5可合并{1,3}和4為{1,3,4}也可合并{2,5}和4為{2,5,4}編號{2,5}{1,3,4}{2,5}{1,3,4}070編號{2,5,4}{1,3}{2,5,4}{1,3}070

最長距離的樹形圖(a)123425134

最長距離的樹形圖(b)123425413例為了研究遼寧等5省1991年城鎮居民生活消費情況的分布規律，根據調查資料做類型分類，用最短距離做類間分類。數據如下：x1x2x3x4x5x6x7x8遼寧17.9039.778.4912.9419.2711.052.0413.29浙江27.6850.3711.3513.3019.2514.592.7514.87河南39.4227.938.208.1416.179.421.559.76甘肅49.1627.989.019.3215.999.101.8211.35青海510.0628.6410.5210.0516.188.391.9610.81將每一個省區視為一個樣本，先計算5個省區之間的歐式距離，用D0表示距離矩陣（對稱陣，故給出下三角陣）因此將3.4合并為一類，為類6，替代了3、4兩類類6與剩余的1、2、5之間的距離分別為：

d(3,4)1=min(d31,d41)=min(13.80,13.12)=13.12d(3,4)2=min(d32,d42)=min(24.63,24.06)=24.06d(3,4)5=min(d35,d45)=min(3.51,2.21)=2.21得到新矩陣合并類6和類5，得到新類7類7與剩余的1、2之間的距離分別為：

d(5,6)1=min(d51,d61)=min(12.80,13.12)=12.80d(5,6)2=min(d52,d62)=min(23.54,24.06)=23.54得到新矩陣合并類1和類2，得到新類8此時，我們有兩個不同的類：類7和類8。它們的最近距離d(7,8)

=min(d71,d72)=min(12.80,23.54)=12.80得到矩陣最后合并為一個大類。這就是按最短距離定義類間距離的系統聚類方法。最長距離法類似！3、中間距離法如假定在聚類的過程中兩個類G1和G2合并成一個新類GN=(G1,G2).則GN和其它任一類G3的距離可定義為G1G2G3三角形中線的平方G3G1G2GN類間距離dG3Gn=d2=1/2[dG3G12+dG3G22

-

(1/2)

dG1G22]注意:中間距離進行聚類時,一般都采用距離的平方例5.5假定5個對象間的距離如下表所示，試用中間距離法聚類并畫出樹形圖編號1234512345004045471550編號12345123450360416091625049125250<1>先把原距離平方解:還是先將{2,5}合并,然后計算{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>

1,3最近,把它門合成一類,并計算到{2,5}和4的距離編號{2,5}{1,3}4{2,5}{1,3}4030.25

020.25160<3>

再把1,3,4合并成一類,計算它們到{2,5}類的距離編號{2,5}{1,3,4}{2,5}{1,3,4}021.250<4>4.類平均距離法（averagelinkagemethod）類間所有樣本點的平均距離該法利用了所有樣本的信息，被認為是較好的系統聚類法

類平均法：DKL=(d13+d14+d15+d23+d24+d25)/65.重心法（centroidhierarchicalmethod）類的重心之間的距離對異常值不敏感，結果更穩定

6.離差平方和法（wardmethod）D2=WM－WK－WL即對異常值很敏感；對較大的類傾向產生較大的距離，從而不易合并，較符合實際需要。ClusterKClusterLClusterM前面是基于距離在對變量進行聚類時,一般先求出變量間的相似系數,按照相似系數越大,兩個變量越相似的原則聚類,根據分層聚類的思想,聚類過程完全相似也可以先轉為距離d=1-c2例5.6:下表是24名優秀運動員的七項全能項目得分間的相關系數.對這7項指標進行聚類分析編號x1x2x3x4x5x6x7x1x2x3x4x5x6x71.000.44981.000.6838.46661.000.8466.3296.56751.000.8113.5420.5943.81121.000.3214.2154.6896.3143.32761.000.5706.1498.3762.6790.4957.05561.000其中{x1,x2…x7}分別代表百米欄,跳高,鉛球,200米,跳遠,標槍,800米解:上表中x1和x4的相關系數0.8466為最大,先將1,4聚成一個新類{1,4}再求變量2,3,5,6,7和{1,4}的相關系數,取這些變量中和1,4相關系數最大的作為它們與{1,4}的相關系數如:r2{1,4}=max[r12,r24]=max[.4498,.3298]=.4498編號{x1,x4}x2x3x5x6x7{x1,x4}x2x3x5x6x71.000.44981.000.6838.46661.000.8113.5420.5943.81121.000.3214.2154.6896.3276.32761.000.6790.1498.3762.6790.4957.05561.000編號{x1,x4,x5}x2x3x6x7{x1,x4,x5}x2x3x6x71.000.54201.000.6838.46661.000.3276.2154.68961.000.6790.1498.3762.05561.000編號{x1,x4,x5}{x3,x6}x2x7{x1,x4,x5}{x3,x6)x2x71.000.68381.000.5420.46661.000.6790.3762.14981.000層次的方法缺陷：

一旦一個步驟（合并或分裂）完成，就不能被撤銷或修正，因此產生了改進的層次聚類方法，如BRICH,BURE,ROCK,Chameleon。改進的層次聚類BIRCH是一個綜合的層次聚類方法，它引入了兩個概念：聚類特征和聚類特征樹（CF樹）CURE方法采用了一種新穎的層次聚類算法，該算法選擇基于重心和基于代表對象方法之間的中間策略。ROCK方法是一個可選的凝聚的層次聚類算法，適用于分類屬性。Chameleon（變色龍）方法是一個在層次聚類中采用動態模型的層次聚類算法

三、劃分方法（動態聚類法）

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

1、k-means算法K-means聚類是MacQueen提出的一種無監督的聚類算法，它在最小化誤差函數的基礎上將樣本集劃分為預定的類數k。

算法5．1根據聚類中的均值進行聚類劃分的k-means算法。輸入：聚類個數k，以及包含n個數據對象的數據庫。輸出：滿足方差最小標準的k個聚類。

處理流程：(1)從n個數據對象任意選擇k個對象作為初始聚類中心。(2)使用歐氏距離將剩余實例賦給距離它們最近的簇中心(3)使用每簇中的實例計算每個簇對象的均值(中心對象)，計算每個對象與這些中心對象的距離，并根據最小距離重新對相應對象進行分類。(4)重新計算每個(有變化)聚類的均值(中心對象)，直至新平均值等于上次迭代的平均值，算法結束。

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

根據算法5．1，從數據集中任意選擇三個對象作為初始聚類中心(圖(a)中這些對象被標上了“+”)，其余對象則根據與這三個聚類中心(對象)的距離，根據最近距離原則，逐個分別聚類到這三個聚類中心所代表的(3個)聚類中，由此獲得了如圖(a)所示的三個聚類(以虛線圈出)

在完成第一輪聚類之后，各聚類中心發生了變化。繼而更新3個聚類的聚類中心(圖(b)中這些對象被標上了“十”)，也就是分別根據各聚類中的對象重新計算相應聚類的(對象)均值。根據所獲得的3個新聚類中心，以及各對象與這三個聚類中心的距離，(根據最近距離原則)對所有對象進行重新歸類。有關變化情況如圖(b)所示(已用粗虛線圈出)。圖5.2

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

例5.7k-means算法舉例實例xy1234561.01.02.02.03.05.0Step1:設Ｋ＝2,算法任意選擇兩個點作為初始簇中心，假設算法選擇實例１作為第一個簇的中心，即Ｃ１＝（1.0,1.5)實例（２.0,1.5)作為第二個簇的中心，即Ｃ２＝（2.0,1.5)第二步，第一次迭代，分別計算樣本實例到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.00Distance(C1,4)=2.24Distance(C2,4)=2.00Distance(C1,5)=2.24Distance(C2,5)=1.41Distance(C1,6)=6.02Distance(C2,6)=5.41確定C1，C2C1包含實例1(1.0,1.5)和2(1.0，4.5)C2包含實例3，4，5，6Step3：重新計算每個簇的中心對于簇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:進行第二次迭代：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此時C1包含實例1,2,3C2包含實例4,5,6Step5:對每個簇重新計算新的中心，可得到：C1=（1.33,2.50)C2=(3.33,4.00)繼續直到類中心不再發生變化

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

K-means算法的最優聚類：實例到它們對應簇中心的誤差平方和最小。

對于給定K值，要找到一個最優聚類，必須根據初始中心的不同選擇來重復執行算法。

例如，對上表重復應用K-means算法而獲得的三類聚類結果：輸出結果簇中心簇點均方差1(2.67,4.67)2,4,614.50(2.00,1.83)1,3,52(1.5,1.5)1,315.94(2.75,4.125)2,4,5,63(1.8,2.7)1,2,3,4,59.60(5,6)6k－means聚類算法練習坐標表示5個點｛X1,X2,X3,X4,X5｝作為一個聚類分析的二維樣本X1＝（0,2），X2＝（0,0），X3＝（1.5,0），X4＝（5,0），X5＝（5,2）。假設要求的簇的數量k=2。第1步：由樣本的隨機分布形成兩個簇：C1＝｛X1,X2,X4｝和C2＝｛X3,X5｝。這兩個簇的質心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）；樣本初始隨機分布之后，方差是：由于：c1類包含｛X1＝（0,2），X2＝（0,0），X4＝（5,0）｝中心M1：（1.66，0.66）所以：

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；同樣：c2類包含：｛X3＝（1.5,0），X5＝（5,2）｝中心M2：（3.25，1.00）；

e22=[(1.5-3.25)2+(0-1.00)2]+[(6-3.25)2+(0-1.00）2]=8.12；總體平方誤差是：E2＝e12+e22＝19.36+8.12＝27.48第2步：取距離其中一個質心（M1或M2）最小的距離分配所有樣本，簇內樣本的重新分布如下：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｝第3步：計算新的質心：M1＝｛0.5，0.67｝；M2＝｛5.0，1.0｝。相應的方差及總體平方誤差分別是：e12＝4.17；e22＝2.00；E＝6.17；可以看出第一次迭代后，總體誤差顯著減小（從值27.48到6.17）。在這個簡單的例子中，第一次迭代同時也是最后一次迭代，因為如果繼續分析新中心和樣本間的距離，樣本將會全部分給同樣的簇，不將重新分配，算法停止。

k-means算法復雜度為O(nkt),因而它在處理大數據庫時也是相對有效的(具有可擴展性)。這里n為對象個數，k為聚類個數，t為循環次數。

但是k-means算法只適用于聚類均值有意義的情況。因此在某些應用中，諸如：數據集包含符號屬性時，直接應用k-means算法就有困難了。k-means算法另一個缺點就是用戶須事先指定聚類個數k。此外，k-means算法對噪聲和異常數據也很敏感，因為這類數據可能會影響到類的均值(計算結果)。

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

數據挖掘的內容經常含有離散數據，傳統的方法是轉換離散數據為數值值，經常得不出有意義的結果k-modes算法把k-means算法擴展到離散數據，定義了新的度量離散數據相異度的距離公式，并給出相應的更新聚類中心的方式，能夠迅速處理離散型數據。與k-means算法相比，k-modes算法使用了不同的非相似性度量以及一個基于頻率的方式對模式更新，k-modes算法根據離散屬性值出現的頻率更新聚類中心，聚類中出現頻率最高的屬性值被選為聚類中心，即modes（類模式）。

如：某一類中有4個樣本,屬性為：職稱，年齡，收入，信譽度職稱年齡收入信譽r1:教授老高高（modes)r2:副教授老高高r3:教授青中中

非相似性度量：設X，Y是由m個離散屬性描述的兩個離散對象，X，Y之間的距離度量:用兩個對象的對應的屬性離散值的總不匹配量來定義。

k-modes算法過程

k-modes算法不斷更新modes，使得所有對象與其最近modes的相異度總和最小：首先計算每一簇在某一屬性值的對象所占百分數。然后，取每個簇中頻率最大的一個屬性值作為類模式Q。分別對每個屬性進行上述計算，最后得到類模式Q，即初始聚類中心。k-modes算法與k-means的步驟類似：①預先定義好k類，確定各個類的初始類模式Q。②根據類模式Q把每個對象賦給最近鄰的類，然后更新類模式Q。③不斷重復②，直到不再發生變化為止。

將k-means算法和k-modes算法結合到一起，就可以對采用數值量和符號量描述對象進行聚類分析，從而構成了k-prototypes算法。k-prototypes算法

在實際應用中，數據可能是數值型的，同時也有離散型的。k-prototypes算法綜合了k-means和k-modes算法，采用新的距離度量方法，能夠快速處理混合類型數據集的聚類問題。k-prototypes算法的聚類中心由數值型數據的聚類中心和離散數據的聚類中心兩部分加權組成，其中數值型屬性的聚類中心和k-means算法類似，通過計算數值型屬性的平均值得到。而離散屬性的中心采用類似k-modes算法聚類中心的更新方式，通過計算可分類屬性值出現的頻率確定。

2．k-medoids算法k-means算法對異常數據很敏感。medoid設置一個參考點代替k-means算法中的各聚類的均值(作為聚類中心--medoid)。從而可以根據各對象與各參考點之間的距離(差異性)之和最小化的原則，繼續應用劃分方法。

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

基于：各對象與其聚類代表間距離的成本函數來對聚類質量進行評估。為了確定任一個非聚類代表對象orandom是否可以替換當前一個聚類代表oj需要根據以下四種情況對其它非聚類代表對象p進行檢查。

(1)如圖6．3(a)所示，若對象p當前屬于oj(所代表的聚類)，且如果用orandom替換oj作為新聚類代表，而p更接近其它oi，則將p歸類到