數(shù)據(jù)挖掘原理算法及應(yīng)用聚類方法

數(shù)據(jù)挖掘原理算法及應(yīng)用聚類方法第1頁/共287頁5.1概述

聚類分析源于許多研究領(lǐng)域，包括數(shù)據(jù)挖掘、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、模式識別等。它是數(shù)據(jù)挖掘中的一個功能，但也能作為一個獨(dú)立的工具來獲得數(shù)據(jù)分布的情況，概括出每個簇的特點(diǎn)，或者集中注意力對特定的某些簇作進(jìn)一步的分析。此外，聚類分析也可以作為其他分析算法(如關(guān)聯(lián)規(guī)則、分類等)的預(yù)處理步驟，這些算法在生成的簇上進(jìn)行處理。第2頁/共287頁數(shù)據(jù)挖掘技術(shù)的一個突出的特點(diǎn)是處理巨大的、復(fù)雜的數(shù)據(jù)集，這對聚類分析技術(shù)提出了特殊的挑戰(zhàn)，要求算法具有可伸縮性、處理不同類型屬性、發(fā)現(xiàn)任意形狀的類、處理高維數(shù)據(jù)的能力等。根據(jù)潛在的各項(xiàng)應(yīng)用，數(shù)據(jù)挖掘?qū)垲惙治龇椒ㄌ岢隽瞬煌?。典型要求可以通過以下幾個方面來刻畫。第3頁/共287頁

(1)可伸縮性：指聚類算法不論對于小數(shù)據(jù)集還是對于大數(shù)據(jù)集，都應(yīng)是有效的。在很多聚類算法當(dāng)中，數(shù)據(jù)對象小于幾百個的小數(shù)據(jù)集合上魯棒性很好，而對于包含上萬個數(shù)據(jù)對象的大規(guī)模數(shù)據(jù)庫進(jìn)行聚類時，將會導(dǎo)致不同的偏差結(jié)果。研究大容量數(shù)據(jù)集的高效聚類方法是數(shù)據(jù)挖掘必須面對的挑戰(zhàn)。

(2)具有處理不同類型屬性的能力：指既可處理數(shù)值型數(shù)據(jù)，又可處理非數(shù)值型數(shù)據(jù)，既可以處理離散數(shù)據(jù)，又可以處理連續(xù)域內(nèi)的數(shù)據(jù)，如布爾型、序數(shù)型、枚舉型或這些數(shù)據(jù)類型的混合。第4頁/共287頁

(3)能夠發(fā)現(xiàn)任意形狀的聚類。許多聚類算法經(jīng)常使用歐幾里得距離來作為相似性度量方法，但基于這樣的距離度量的算法趨向于發(fā)現(xiàn)具有相近密度和尺寸的球狀簇。對于一個可能是任意形狀的簇的情況，提出能發(fā)現(xiàn)任意形狀簇的算法是很重要的。

(4)輸入?yún)?shù)對領(lǐng)域知識的弱依賴性。在聚類分析當(dāng)中，許多聚類算法要求用戶輸入一定的參數(shù)，如希望得到的簇的數(shù)目等。聚類結(jié)果對于輸入的參數(shù)很敏感，通常參數(shù)較難確定，尤其是對于含有高維對象的數(shù)據(jù)集更是如此。要求用人工輸入?yún)?shù)不但加重了用戶的負(fù)擔(dān)，也使得聚類質(zhì)量難以控制。一個好的聚類算法應(yīng)該對這個問題給出一個好的解決方法。

第5頁/共287頁

(5)對于輸入記錄順序不敏感。一些聚類算法對于輸入數(shù)據(jù)的順序是敏感的。例如，對于同一個數(shù)據(jù)集合，以不同的順序提交給同一個算法時，可能產(chǎn)生差別很大的聚類結(jié)果。研究和開發(fā)對數(shù)據(jù)輸入順序不敏感的算法具有重要的意義。第6頁/共287頁

(6)挖掘算法應(yīng)具有處理高維數(shù)據(jù)的能力，既可處理屬性較少的數(shù)據(jù)，又能處理屬性較多的數(shù)據(jù)。很多聚類算法擅長處理低維數(shù)據(jù)，一般只涉及兩維到三維，人類對兩、三維數(shù)據(jù)的聚類結(jié)果很容易直觀地判斷聚類的質(zhì)量。但是，高維數(shù)據(jù)聚類結(jié)果的判斷就不那樣直觀了。數(shù)據(jù)對象在高維空間的聚類是非常具有挑戰(zhàn)性的，尤其是考慮到這樣的數(shù)據(jù)可能高度偏斜并且非常稀疏。第7頁/共287頁

(7)處理噪聲數(shù)據(jù)的能力。在現(xiàn)實(shí)應(yīng)用中，絕大多數(shù)的數(shù)據(jù)都包含了孤立點(diǎn)、空缺、未知數(shù)據(jù)或者錯誤的數(shù)據(jù)。如果聚類算法對于這樣的數(shù)據(jù)敏感，將會導(dǎo)致質(zhì)量較低的聚類結(jié)果。

(8)基于約束的聚類。在實(shí)際應(yīng)用當(dāng)中可能需要在各種約束條件下進(jìn)行聚類。既要找到滿足特定的約束，又要具有良好聚類特性的數(shù)據(jù)分組是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。

(9)挖掘出來的信息是可理解的和可用的。這點(diǎn)很容易理解，但在實(shí)際挖掘中往往不能令人滿意。第8頁/共287頁5.1.1聚類分析在數(shù)據(jù)挖掘中的應(yīng)用

聚類分析在數(shù)據(jù)挖掘中的應(yīng)用主要有以下幾個方面：

(1)聚類分析可以作為其他算法的預(yù)處理步驟。利用聚類進(jìn)行數(shù)據(jù)預(yù)處理，可以獲得數(shù)據(jù)的基本概況，在此基礎(chǔ)上進(jìn)行特征抽取或分類就可以提高精確度和挖掘效率。也可將聚類結(jié)果用于進(jìn)一步關(guān)聯(lián)分析，以進(jìn)一步獲得有用的信息。第9頁/共287頁

(2)可以作為一個獨(dú)立的工具來獲得數(shù)據(jù)的分布情況。聚類分析是獲得數(shù)據(jù)分布情況的有效方法。例如，在商業(yè)上，聚類分析可以幫助市場分析人員從客戶基本資料數(shù)據(jù)庫中發(fā)現(xiàn)不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。通過觀察聚類得到的每個簇的特點(diǎn)，可以集中對特定的某些簇作進(jìn)一步分析。這在諸如市場細(xì)分、目標(biāo)顧客定位、業(yè)績估評、生物種群劃分等方面具有廣闊的應(yīng)用前景。

(3)聚類分析可以完成孤立點(diǎn)挖掘。許多數(shù)據(jù)挖掘算法試圖使孤立點(diǎn)影響最小化，或者排除它們。然而孤立點(diǎn)本身可能是非常有用的，如在欺詐探測中，孤立點(diǎn)可能預(yù)示著欺詐行為的存在。第10頁/共287頁5.1.2聚類分析算法的概念與基本分類

1.聚類概念

定義5.1

聚類分析的輸入可以用一組有序?qū)?X,s)或(X,d)表示，這里X表示一組樣本，s和d分別是度量樣本間相似度或相異度(距離)的標(biāo)準(zhǔn)。聚類系統(tǒng)的輸出是對數(shù)據(jù)的區(qū)分結(jié)果，即C={C1，C2，…，Ck)，其中Ci(i=1，2，…，k)是X的子集，且滿足如下條件：

(1)

C1∪C2∪…∪Ck=X；

(2)

Ci∩Cj=Ф，i≠j。第11頁/共287頁

C中的成員C1，C2，…，Ck稱為類或者簇。每一個類可以通過一些特征來描述。通常有如下幾種表示方式：·通過類的中心或類的邊界點(diǎn)表示一個類?！な褂镁垲悩渲械慕Y(jié)點(diǎn)圖形化地表示一個類。·使用樣本屬性的邏輯表達(dá)式表示類。用類的中心表示一個類是最常見的方式。當(dāng)類是緊密的或各向分布同性時，用這種方法非常好。然而，當(dāng)類是伸長的或各向分布異性時，這種方式就不能正確地表示它們了。第12頁/共287頁

2.聚類分析算法的分類聚類分析是一個活躍的研究領(lǐng)域，已經(jīng)有大量的、經(jīng)典的和流行的算法涌現(xiàn)，例如k平均、k中心點(diǎn)、PAM、CLARANS、BIRTH、CURE、OPTICS、DBSCAN、STING等。采用不同的聚類算法，對于相同的數(shù)據(jù)集可能有不同的劃分結(jié)果。很多文獻(xiàn)從不同角度對聚類分析算法進(jìn)行了分類。第13頁/共287頁

1)按聚類的標(biāo)準(zhǔn)劃分按照聚類的標(biāo)準(zhǔn)，聚類算法可分為如下兩種：

(1)統(tǒng)計(jì)聚類算法。統(tǒng)計(jì)聚類算法基于對象之間的幾何距離進(jìn)行聚類。統(tǒng)計(jì)聚類分析包括系統(tǒng)聚類法、分解法、加入法、動態(tài)聚類法、有序樣品聚類、有重疊聚類和模糊聚類。這種聚類算法是一種基于全局比較的聚類，它需要考察所有的個體才能決定類的劃分。因此，它要求所有的數(shù)據(jù)必須預(yù)先給定，而不能動態(tài)地增加新的數(shù)據(jù)對象。

(2)概念聚類算法。概念聚類算法基于對象具有的概念進(jìn)行聚類。這里的距離不再是傳統(tǒng)方法中的幾何距離，而是根據(jù)概念的描述來確定的。典型的概念聚類或形成方法有COBWEB、OLOC和基于列聯(lián)表的方法。

第14頁/共287頁

2)按聚類算法所處理的數(shù)據(jù)類型劃分按照聚類算法所處理的數(shù)據(jù)類型，聚類算法可分為三種：(1)數(shù)值型數(shù)據(jù)聚類算法。數(shù)值型數(shù)據(jù)聚類算法所分析的數(shù)據(jù)的屬性為數(shù)值數(shù)據(jù)，因此可對所處理的數(shù)據(jù)直接比較大小。目前，大多數(shù)的聚類算法都是基于數(shù)值型數(shù)據(jù)的。

(2)離散型數(shù)據(jù)聚類算法。由于數(shù)據(jù)挖掘的內(nèi)容經(jīng)常含有非數(shù)值的離散數(shù)據(jù)，近年來人們在離散型數(shù)據(jù)聚類算法方面做了許多研究，提出了一些基于此類數(shù)據(jù)的聚類算法，如k模(kmode)、ROCK、CACTUS、STIRR等。

(3)混合型數(shù)據(jù)聚類算法?；旌闲蛿?shù)據(jù)聚類算法是能同時處理數(shù)值數(shù)據(jù)和離散數(shù)據(jù)的聚類算法，這類聚類算法通常功能強(qiáng)大，但性能往往不盡人意?；旌闲蛿?shù)據(jù)聚類算法的典型算法為k原型(kprototypes)算法。

第15頁/共287頁

3)按聚類的尺度劃分按照聚類的尺度，聚類算法可被分為以下三種：

(1)基于距離的聚類算法。距離是聚類分析常用的分類統(tǒng)計(jì)量。常用的距離定義有歐氏距離和馬氏距離。許多聚類算法都是用各式各樣的距離來衡量數(shù)據(jù)對象之間的相似度，如k－平均、k－中心點(diǎn)、BIRCH、CURE等算法。算法通常需要給定聚類數(shù)目k，或區(qū)分兩個類的最小距離?；诰嚯x的算法聚類標(biāo)準(zhǔn)易于確定、容易理解，對數(shù)據(jù)維度具有伸縮性，但只適用于歐幾里得空間和曼哈坦空間，對孤立點(diǎn)敏感，只能發(fā)現(xiàn)圓形類。為克服這些缺點(diǎn)，提高算法性能，k中心點(diǎn)、BIRCH、CURE等算法采取了一些特殊的措施。如CURE算法使用固定數(shù)目的多個數(shù)據(jù)點(diǎn)作為類代表，這樣可提高算法處理不規(guī)則聚類的能力，降低對孤立點(diǎn)的敏感度。第16頁/共287頁

(2)基于密度的聚類算法。從廣義上說，基于密度和基于網(wǎng)格的算法都可算作基于密度的算法。此類算法通常需要規(guī)定最小密度門限值。算法同樣適用于歐幾里得空間和曼哈坦空間，對噪聲數(shù)據(jù)不敏感，可以發(fā)現(xiàn)不規(guī)則的類，但當(dāng)類或子類的粒度小于密度計(jì)算單位時，會被遺漏。第17頁/共287頁

(3)基于互連性的聚類算法。基于互連性(LinkageBased)的聚類算法通?；趫D或超圖模型。它們通常將數(shù)據(jù)集映像為圖或超圖，滿足連接條件的數(shù)據(jù)對象之間畫一條邊，高度連通的數(shù)據(jù)聚為一類。屬于此類的算法有：ROCK、CHAMELEON、ARHP、STIRR、CACTUS等。此類算法可適用于任意形狀的度量空間，聚類的質(zhì)量取決于鏈或邊的定義，不適合處理太大的數(shù)據(jù)集。當(dāng)數(shù)據(jù)量大時，通常忽略權(quán)重小的邊，使圖變稀疏，以提高效率，但會影響聚類質(zhì)量。第18頁/共287頁

4)按聚類算法的思路劃分按照聚類分析算法的主要思路，聚類算法可以歸納為如下幾種：

(1)劃分法(PartitioningMethods)。給定一個n個對象或者元組的數(shù)據(jù)庫，劃分方法構(gòu)建數(shù)據(jù)的k個劃分，每個劃分表示一個簇，并且k≤n。也就是說，它將數(shù)據(jù)劃分為k個組，同時滿足如下的要求：每個組至少包含一個對象；每個對象必須屬于且只能屬于一個組。屬于該類的聚類算法有：k平均、k模、k原型、k中心點(diǎn)、PAM、CLARA、CLARANS等。

第19頁/共287頁

(2)層次法(HierarchicalMethods)。層次方法對給定數(shù)據(jù)對象集合進(jìn)行層次的分解。根據(jù)層次的分解方法，層次方法又可以分為凝聚的和分裂的。分裂的方法也稱為自頂向下的方法，一開始將所有的對象置于一個簇中，在迭代的每一步中，一個簇被分裂成更小的簇，直到每個對象在一個單獨(dú)的簇中，或者達(dá)到一個終止條件。如DIANA算法屬于此類。凝聚的方法也稱為自底向上的方法，一開始就將每個對象作為單獨(dú)的一個簇，然后相繼地合并相近的對象或簇，直到所有的簇合并為一個，或者達(dá)到終止條件。如AGNES算法屬于此類。

第20頁/共287頁

(3)基于密度的算法(DensitybasedMethods)?；诿芏鹊乃惴ㄅc其他方法的一個根本區(qū)別是：它不是用各式各樣的距離作為分類統(tǒng)計(jì)量，而是看數(shù)據(jù)對象是否屬于相連的密度域，屬于相連密度域的數(shù)據(jù)對象歸為一類。如DBSCAN屬于密度聚類算法。

(4)基于網(wǎng)格的算法(GridbasedMethods)?；诰W(wǎng)格的算法首先將數(shù)據(jù)空間劃分成為有限個單元(Cell)的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個單元為對象的。這樣處理的一個突出優(yōu)點(diǎn)是處理速度快，通常與目標(biāo)數(shù)據(jù)庫中記錄的個數(shù)無關(guān)，只與劃分?jǐn)?shù)據(jù)空間的單元數(shù)有關(guān)。但此算法處理方法較粗放，往往影響聚類質(zhì)量。代表算法有STING、CLIQUE、WaveCluster、DBCLASD、OptiGrid算法。第21頁/共287頁

(5)基于模型的算法(ModelBasedMethods)?；谀Ｐ偷乃惴ńo每一個簇假定一個模型，然后去尋找能夠很好地滿足這個模型的數(shù)據(jù)集。這樣一個模型可能是數(shù)據(jù)點(diǎn)在空間中的密度分布函數(shù)或者其他函數(shù)。它的一個潛在的假定是：目標(biāo)數(shù)據(jù)集是由一系列的概率分布所決定的。通常有兩種嘗試方案：統(tǒng)計(jì)的方案和神經(jīng)網(wǎng)絡(luò)的方案?；诮y(tǒng)計(jì)學(xué)模型的算法有COBWEB、Autoclass，基于神經(jīng)網(wǎng)絡(luò)模型的算法有SOM。第22頁/共287頁5.1.3距離與相似性的度量一個聚類分析過程的質(zhì)量取決于對度量標(biāo)準(zhǔn)的選擇，因此必須仔細(xì)選擇度量標(biāo)準(zhǔn)。為了度量對象之間的接近或相似程度，需要定義一些相似性度量標(biāo)準(zhǔn)。本章用s(x,y)表示樣本x和樣本y的相似度。當(dāng)x和y相似時，s(x,y)的取值是很大的；當(dāng)x和y不相似時，s(x,y)的取值是很小的。相似性的度量具有自反性，即s(x,y)=s(y,x)。對于大多數(shù)聚類算法來說，相似性度量標(biāo)準(zhǔn)被標(biāo)準(zhǔn)化為0≤s(x,y)≤1。第23頁/共287頁在通常情況下，聚類算法不計(jì)算兩個樣本間的相似度，而是用特征空間中的距離作為度量標(biāo)準(zhǔn)來計(jì)算兩個樣本間的相異度的。對于某個樣本空間來說，距離的度量標(biāo)準(zhǔn)可以是度量的或半度量的，以便用來量化樣本的相異度。相異度的度量用d(x,y)來表示，通常稱相異度為距離。當(dāng)x和y相似時，距離d(x,y)的取值很?。划?dāng)x和y不相似時，d(x,y)的取值很大。下面對這些度量標(biāo)準(zhǔn)作簡要介紹。按照距離公理，在定義距離測度時需要滿足距離公理的四個條件：自相似性、最小性、對稱性以及三角不等性。常用的距離函數(shù)有如下幾種。第24頁/共287頁

1.明可夫斯基距離(Minkowski)

假定xi、yi分別是樣本x、y的第i個特征，i=1，2，…，n，n是特征的維數(shù)。x和y的明可夫斯基距離度量的定義如下：

(5.1)當(dāng)r取不同的值時，上述距離度量公式演化為一些特殊的距離測度：

(1)當(dāng)r=1時，明可夫斯基距離演變?yōu)榻^對值距離：

d(x,y)=d(x,y)=第25頁/共287頁(2)當(dāng)r=2時，明可夫斯基距離演變?yōu)闅W氏距離：d(x,y)=第26頁/共287頁

2.二次型距離(Quadratic)二次型距離測度的形式如下：

(5.2)當(dāng)A取不同的值時，上述距離度量公式演化為一些特殊的距離測度：

(1)當(dāng)A為單位矩陣時，二次型距離演變?yōu)闅W氏距離。

(2)當(dāng)A為對角陣時，二次型距離演變?yōu)榧訖?quán)歐氏距離，即(5.3)

(3)當(dāng)A為協(xié)方差矩陣時，二次型距離演變?yōu)轳R氏距離。d(x,y)=d(x,y)=第27頁/共287頁

3.余弦距離余弦距離的度量形式如下：d(x,y)=第28頁/共287頁

4.二元特征樣本的距離度量前面幾種距離度量對于包含連續(xù)特征的樣本是很有效的。但對于包含一些或全部不連續(xù)特征的樣本，計(jì)算樣本間的距離是比較困難的。因?yàn)椴煌愋偷奶卣魇遣豢杀鹊?，只用一個標(biāo)準(zhǔn)作為度量標(biāo)準(zhǔn)是不合適的。下面介紹幾種二元類型數(shù)據(jù)的距離度量標(biāo)準(zhǔn)。假定x和y分別是n維特征，xi和yi分別表示每維特征，且xi和yi的取值為二元類型數(shù)值{0,1}。則x和y的距離定義的常規(guī)方法是先求出如下幾個參數(shù)，然后采用SMC、Jaccard系數(shù)或Rao系數(shù)。第29頁/共287頁假設(shè)：

(1)a是樣本x和y中滿足xi=1，yi=1的二元類型屬性的數(shù)量。

(2)b是樣本x和y中滿足xi=1，yi=0的二元類型屬性的數(shù)量。

(3)c是樣本x和y中滿足xi=0，yi=1的二元類型屬性的數(shù)量。

(4)d是樣本x和y中滿足xi=0，yi=0的二元類型屬性的數(shù)量。則簡單匹配系數(shù)SMC(SimpleMatchCoefficient)定義為第30頁/共287頁Jaccard系數(shù)定義為：(5.5)(5.6)Rao系數(shù)定義為(5.7)第31頁/共287頁5.2劃分聚類方法

1.劃分聚類方法的主要思想定義5.2給定一個有n個對象的數(shù)據(jù)集，劃分聚類技術(shù)將構(gòu)造數(shù)據(jù)進(jìn)行k個劃分，每一個劃分就代表一個簇，k≤n。也就是說，它將數(shù)據(jù)劃分為k個簇，而且這k個劃分滿足下列條件：①每一個簇至少包含一個對象;②每一個對象屬于且僅屬于一個簇。第32頁/共287頁對于給定的k，算法首先給出一個初始的劃分方法，以后通過反復(fù)迭代的方法改變劃分，使得每一次改進(jìn)之后的劃分方案都較前一次更好。所謂好的標(biāo)準(zhǔn)，就是同一簇中的對象越近越好，而不同簇中的對象越遠(yuǎn)越好。目標(biāo)是最小化所有對象與其參照點(diǎn)之間的相異度之和。這里的遠(yuǎn)近或者相異度/相似度實(shí)際上是聚類的評價函數(shù)。第33頁/共287頁

2.評價函數(shù)大多數(shù)為聚類設(shè)計(jì)的評價函數(shù)著重考慮兩個方面：每個簇應(yīng)該是緊湊的；各個簇間的距離應(yīng)該盡量遠(yuǎn)。實(shí)現(xiàn)這種概念的一種直接方法就是觀察聚類C的類內(nèi)差異(Withincluster

variation)w(C)和類間差異(Betweenclustervariation)b(C)。類內(nèi)差異衡量類內(nèi)的緊湊性，類間差異衡量不同類之間的距離。類內(nèi)差異可以用多種距離函數(shù)來定義，最簡單的就是計(jì)算類內(nèi)的每一個點(diǎn)到它所屬類中心的距離的平方和，即第34頁/共287頁類間差異定義為類中心間的距離，即式(5.8)和式(5.9)中的、分別是Ci、Cj類的類中心(平均值)。聚類C的總體質(zhì)量可被定義為w(C)和b(C)的一個單調(diào)組合，比如w(C)/b(C)。下面討論的k平均算法就是用類內(nèi)的均值作為聚類中心、用歐氏距離定義d，并使w(C)最小化。第35頁/共287頁5.2.1

k-平均算法

k-平均(k-Means)也被稱為k-均值，是一種得到最廣泛使用的聚類算法。k-平均算法以k-為參數(shù)，把n個對象分為k個簇，以使簇內(nèi)具有較高的相似度。相似度的計(jì)算根據(jù)一個簇中對象的平均值來進(jìn)行。算法首先隨機(jī)地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心。對剩余的每個對象根據(jù)其與各個簇中心的距離，將它賦給最近的簇，然后重新計(jì)算每個簇的平均值。這個過程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。第36頁/共287頁

k-平均算法的準(zhǔn)則函數(shù)定義為其中x是空間中的點(diǎn)，表示給定的數(shù)據(jù)對象，是簇Ci的平均值。這個準(zhǔn)則可以保證生成的簇盡可能的緊湊和獨(dú)立。第37頁/共287頁

1.算法描述算法5.1

k－平均算法。輸入：簇的數(shù)目k；包含n個對象的數(shù)據(jù)集D。輸出：k個簇的集合。方法：

(1)從D中任意選擇k個對象作為初始簇中心；

(2)repeat；

(3)根據(jù)簇中對象的均值，將每個對象指派到最相似的簇；

(4)更新簇均值，即計(jì)算每個簇中對象的均值；

(5)計(jì)算準(zhǔn)則函數(shù)E；

(6)until準(zhǔn)則函數(shù)E不再發(fā)生變化；第38頁/共287頁

2.算法的性能分析

1)優(yōu)點(diǎn)

(1)k-平均算法是解決聚類問題的一種經(jīng)典算法，算法簡單、快速。

(2)對處理大數(shù)據(jù)集，該算法是相對可伸縮的和高效率的，因?yàn)樗膹?fù)雜度大約是O(nkt)，其中n是所有對象的數(shù)目，k是簇的數(shù)目，t是迭代的次數(shù)。通常地k<<

n。這個算法經(jīng)常以局部最優(yōu)結(jié)束。

(3)算法嘗試找出使平方誤差函數(shù)值最小的k個劃分。當(dāng)簇是密集的、球狀或團(tuán)狀的，而簇與簇之間區(qū)別明顯時，它的聚類效果較好。第39頁/共287頁

2)缺點(diǎn)

(1)k－平均方法只有在簇的平均值被定義的情況下才能使用，不適用于某些應(yīng)用，如涉及有分類屬性的數(shù)據(jù)不適用。

(2)要求用戶必須事先給出要生成的簇的數(shù)目k。

(3)對初值敏感，對于不同的初始值，可能會導(dǎo)致不同的聚類結(jié)果。

(4)不適合于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇。

(5)對于“噪聲”和孤立點(diǎn)數(shù)據(jù)敏感，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大影響。第40頁/共287頁

3)改進(jìn)措施為了實(shí)現(xiàn)對離散數(shù)據(jù)的快速聚類，k－模算法被提出，它保留了k－平均算法效率的同時，將k－平均的應(yīng)用范圍擴(kuò)大到離散數(shù)據(jù)。k－原型可以對離散與數(shù)值屬性兩種混合的數(shù)據(jù)進(jìn)行聚類，在k－原型中定義了一個對數(shù)值與離散屬性都計(jì)算的相異性度量標(biāo)準(zhǔn)。第41頁/共287頁

k－平均算法對于孤立點(diǎn)是敏感的。為了解決這個問題，不采用簇中的平均值作為參照點(diǎn)，可以選用簇中位置最靠近中心的對象，即中心點(diǎn)作為參照點(diǎn)。k－中心點(diǎn)算法的基本思路是：首先為每個簇任意選擇一個代表對象；剩余的對象根據(jù)其與代表對象的距離分配給最近的一個簇。然后反復(fù)地用非代表對象來代替代表對象，以改進(jìn)聚類的質(zhì)量。這樣的劃分方法仍然是基于最小化所有對象與其參照點(diǎn)之間的相異度之和的原則來執(zhí)行的。第42頁/共287頁5.2.2

k中心點(diǎn)算法

k-平均值算法對離群點(diǎn)是敏感的，因?yàn)榫哂泻艽蟮臉O端值的對象可能顯著地扭曲數(shù)據(jù)的分布。平方誤差函數(shù)的使用更是嚴(yán)重惡化了這一影響(見式(5.10))。改進(jìn)的方法：不采用簇中對象的均值作為參照點(diǎn)，而是在每個簇中選出一個實(shí)際的對象來代表該簇。其余的每個對象聚類到與其最相似的代表性對象所在的簇中。劃分方法仍然基于最小化所有對象與其對應(yīng)的參照點(diǎn)之間的相異度之和的原則來執(zhí)行。準(zhǔn)則函數(shù)使用絕對誤差標(biāo)準(zhǔn)(AbsoluteErrorCriterion)，其定義如下：第43頁/共287頁其中，E是數(shù)據(jù)集中所有對象的絕對誤差之和；P是空間中的點(diǎn)，代表簇C中一個給定對象；Oj是簇Cj中的代表對象。通常，該算法重復(fù)迭代，直到每個代表對象都成為它的簇的實(shí)際中心點(diǎn)，或最靠中心的對象。這是將n個對象劃分到k個簇的k-中心點(diǎn)方法的基礎(chǔ)。第44頁/共287頁

k-中心點(diǎn)聚類首先隨意選擇初始代表對象(或種子)，只要能夠提高聚類結(jié)果的質(zhì)量，迭代過程就繼續(xù)用非代表對象替換代表對象。聚類結(jié)果的質(zhì)量用代價函數(shù)來評估，該函數(shù)度量對象與其簇的代表對象之間的平均相異度。為了確定非代表對象Orandom是否是當(dāng)前代表對象Oj的好的替代，對于每一個非代表對象P，考慮四種情況，如圖5-1所示。第45頁/共287頁圖5-1

k-中心點(diǎn)聚類代價函數(shù)的四種情況第46頁/共287頁

(1)第一種情況：P當(dāng)前隸屬于代表對象Oj。如果Oj被Orandom所取代作為代表對象，并且P離其他代表對象Oi(i≠j)最近，則P重新分配給Oi。

(2)第二種情況：P當(dāng)前隸屬于代表對象Oj。如果Oj被Orandom所代替作為代表對象，并且P離Orandom最近，則P重新分配給Orandom。

(3)第三種情況：P當(dāng)前隸屬于代表對象Oi，i≠j。如果Oj被Orandom所代替作為代表對象，并且P仍然離Oi最近，則對象的隸屬不發(fā)生變化。

(4)第四種情況：P當(dāng)前隸屬于代表對象Oi，i≠j。如果Oj被Orandom所代替作為代表對象，并且P離Orandom最近，則P重新分配給Orandom。第47頁/共287頁每當(dāng)重新分配發(fā)生時，絕對誤差E的差對代價函數(shù)有影響。因此，如果當(dāng)前的代表對象被非代表對象所取代，代價函數(shù)就計(jì)算絕對誤差值的差。交換的總代價是所有非代表對象所產(chǎn)生的代價之和。如果總代價是負(fù)的，實(shí)際的絕對誤差E將會減小，Oi可以被Orandom取代或交換；如果總代價是正的，則當(dāng)前的代表對象Oj是可接受的，在本次迭代中沒有變化發(fā)生。第48頁/共287頁

PAM(PartitioningAroundMedoids，圍繞中心點(diǎn)的劃分)是最早提出的k中心點(diǎn)算法之一。它試圖確定n個對象的k個劃分。在隨機(jī)選擇k個初始代表對象之后，該算法反復(fù)地試圖選擇簇的更好的代表對象。分析所有可能的對象對，每對中的一個對象看做是代表對象，而另一個不是。對于每個這樣的組合，計(jì)算聚類結(jié)果的質(zhì)量。對象Oj被那個可以使誤差值減少最多的對象所取代。在一次迭代中產(chǎn)生的每個簇中最好的對象集合成為下次迭代的代表對象。最終集合中的代表對象便是簇的代表中心點(diǎn)。每次迭代的復(fù)雜度是O(k(n-k)2)，當(dāng)n和k的值較大時，計(jì)算代價相當(dāng)高。第49頁/共287頁在PAM算法中，可以把過程分為兩個步驟。

(1)建立：隨機(jī)選擇k個中心點(diǎn)作為初始的簇中心點(diǎn)。

(2)交換：對所有可能的對象對進(jìn)行分析，找到交換后可以使誤差減少的對象，代替原中心點(diǎn)。第50頁/共287頁算法5.2

PAM(k-中心點(diǎn)算法)。輸入：簇的數(shù)目k和包含n個對象的數(shù)據(jù)庫。輸出：k個簇，使得所有對象與其最近中心點(diǎn)的相異度總和最小。方法：

(1)任意選擇k個對象作為初始的簇中心點(diǎn)；

(2)REPEAT

(3)指派每個剩余的對象給離它最近的中心點(diǎn)所代表的簇；

(4)REPEAT

(5)選擇一個未被選擇的中心點(diǎn)Oi；

(6)

REPEAT

(7)選擇一個未被選擇過的非中心點(diǎn)對象Orandom；第51頁/共287頁

(8)計(jì)算用Orandom代替Oi的總代價并記錄在S中；

(9)UNTIL所有的非中心點(diǎn)都被選擇過；

(10)UNTIL所有的中心點(diǎn)都被選擇過；

(11)IF在S中的所有非中心點(diǎn)代替所有中心點(diǎn)后計(jì)算出的總代價有小于0的存在，THEN找出S中的用非中心點(diǎn)替代中心點(diǎn)后代價最小的一個，并用該非中心點(diǎn)替代對應(yīng)的中心點(diǎn)，形成一個新的k個中心點(diǎn)的集合；

(12)UNTIL沒有再發(fā)生簇的重新分配，即所有的S都大于0。第52頁/共287頁

k-中心點(diǎn)算法的性能分析：

(1)k-中心點(diǎn)算法消除了k-平均算法對孤立點(diǎn)的敏感性。

(2)當(dāng)存在“噪聲”和孤立點(diǎn)數(shù)據(jù)時，k-中心點(diǎn)方法比k平均方法更健壯，這是因?yàn)橹行狞c(diǎn)不像平均值那么容易被極端數(shù)據(jù)影響，但k-中心點(diǎn)方法的執(zhí)行代價比k-平均方法高。

(3)算法必須指定聚類的數(shù)目k-，k-的取值對聚類質(zhì)量有重大影響。

(4)PAM算法對于小的數(shù)據(jù)集非常有效(例如100個對象聚成5類)，但對于大數(shù)據(jù)集其效率不高。因?yàn)樵谔鎿Q中心點(diǎn)時，每個點(diǎn)的替換代價都可能計(jì)算，因此，當(dāng)n和k值較大時，計(jì)算代價相當(dāng)高。第53頁/共287頁5.2.3基于遺傳算法的k-中心點(diǎn)聚類算法

k-平均值聚類對“噪聲”和孤立點(diǎn)數(shù)據(jù)敏感，收斂到局部最優(yōu)值。k-中心點(diǎn)克服了k-平均值聚類的這些缺點(diǎn)，但算法時間復(fù)雜度高?；谶z傳算法的k-中心點(diǎn)聚類算法把遺傳算法和k-中心點(diǎn)聚類算法相結(jié)合，利用它們各自的優(yōu)點(diǎn)，達(dá)到對“噪聲”和孤立點(diǎn)數(shù)據(jù)不敏感，收斂到全局最優(yōu)值的目的。第54頁/共287頁

1.遺傳算法解決聚類問題的基礎(chǔ)

1)數(shù)據(jù)集的劃分設(shè)為待聚類樣本的全體(稱為論域)，xk=(xk1,xk2,…，xks)T∈Rs為觀測樣本xk的特征矢量或模式矢量，對應(yīng)特征空間中的一個點(diǎn)，xkj為特征矢量xk的第j維特征取值。聚類就是通過分析論域X中的n個樣本所對應(yīng)模式矢量間的相似性，按照樣本間的親疏關(guān)系把x1,x2，…，xn劃分成c個子集(也稱為族)X1,X2,…，Xc，并滿足如下條件：第55頁/共287頁(5.12)如果用隸屬函數(shù)μik=μXi(xk)表示樣本xk與子集Xi(1≤i≤c)的隸屬關(guān)系，則(5.13)第56頁/共287頁這樣硬c劃分也可以用隸屬函數(shù)來表示，即用c個子集的特征函數(shù)值構(gòu)成的矩陣U=［μik］c×n來表示。矩陣U中的第i行為第i個子集的特征函數(shù)，而矩陣U中的第k列為樣本xk相對于c個子集的隸屬函數(shù)。于是X的硬c劃分空間為(5.14)第57頁/共287頁第58頁/共287頁第59頁/共287頁第60頁/共287頁第61頁/共287頁在數(shù)據(jù)量較大時，第一種編碼方案的搜索空間就會很大，第二種編碼方案則只與聚類原型pi參數(shù)數(shù)目k(特征數(shù)目)和類數(shù)c有關(guān)，而與樣本數(shù)無直接關(guān)系，搜索空間往往比第一種方案要小得多。因而，使用遺傳算法來解決聚類問題一般采用第二種編碼方案。第62頁/共287頁第63頁/共287頁第64頁/共287頁

5)適應(yīng)度函數(shù)對于基于目標(biāo)函數(shù)的聚類問題，最優(yōu)聚類結(jié)果對應(yīng)于目標(biāo)函數(shù)的極小值，即聚類效果越好，則目標(biāo)函數(shù)越小，此時的適應(yīng)度應(yīng)越大。

2.基于遺傳算法的k-中心點(diǎn)聚類算法眾多文獻(xiàn)中對遺傳—中心點(diǎn)聚類算法有所涉獵，現(xiàn)總結(jié)如下：算法5.3遺傳—中心點(diǎn)聚類算法。輸入：聚類數(shù)目k，包含n個待聚類樣本的數(shù)據(jù)庫。輸出：劃分矩陣U和聚類原型P，使類內(nèi)平方誤差和最小。第65頁/共287頁方法：(1)設(shè)置GA相關(guān)參數(shù)，包括最大迭代次數(shù)、群體大小、交叉概率、變異概率；(2)群體初始化，按照式(5.18)的編碼方案對染色體群體進(jìn)行初始化；(3)群體評價，對染色體進(jìn)行解碼，獲得聚類原型P，按照式(5.19)求劃分矩陣U，計(jì)算當(dāng)前劃分下的聚類中心點(diǎn)矢量。按照式(5.16)對染色體群體進(jìn)行評價；

(4)染色體選擇，依據(jù)評價結(jié)果，選擇較優(yōu)的染色體，進(jìn)行下一步操作；第66頁/共287頁

(5)染色體交叉；

(6)染色體變異；

(7)染色體保留；

(8)中止條件檢驗(yàn)，如果小于最大迭代次數(shù)，則轉(zhuǎn)向(3)，否則停止迭代，輸出劃分矩陣U和聚類中心點(diǎn)矢量P。第67頁/共287頁5.3層次聚類方法

5.3.1凝聚和分裂層次聚類一般來說，有兩種類型的層次聚類方法：

(1)凝聚層次聚類：這種自底向上的策略首先將每個對象作為簇，然后合并這些原子簇為越來越大的簇，直到所有的對象都在一個簇中，或者達(dá)到了某個終止條件。絕大多數(shù)層次聚類方法屬于這一類，它們只是在簇間相似度的定義上有所不同。第68頁/共287頁

(2)分裂層次聚類：這種自頂向下的策略與凝聚層次聚類正好相反，它首先將所有對象置于一個簇中，然后將它逐步細(xì)分為越來越小的簇，直到每個對象自成一簇，或者達(dá)到了某個終止條件，例如達(dá)到了某個希望的簇?cái)?shù)目，或者每個簇的直徑都在某個閾值之內(nèi)。第69頁/共287頁

【例5.1】凝聚與分裂層次聚類。圖5-2描述了一種凝聚層次聚類算法AGENES(AGglomerativeNESting)和一種分裂層次聚類算法DIANA(DIvisiveANAlysis)對一個包含五個對象的數(shù)據(jù)集合{a,b,c,d,e}的處理過程。初始，AGNES將每個對象視為一簇，然后這些簇根據(jù)某種準(zhǔn)則逐步合并。例如，如果簇C1中的一個對象和簇C2中的一個對象之間的距離是所有屬于不同簇的對象間歐幾里得距離中最小的，則C1和C2可能合并。這是一種單鏈接(singlelink)方法，其每個簇可以用簇中所有對象代表，簇間的相似度用屬于不同簇中最近的數(shù)據(jù)點(diǎn)對之間的相似度來度量。聚類的合并過程反復(fù)進(jìn)行，直到所有的對象最終合并形成一個簇。第70頁/共287頁在DIANA中，所有的對象用于形成一個初始簇。根據(jù)某種原則(如，簇中最近的相鄰對象的最大歐幾里得距離)，將該簇分裂。簇的分裂過程反復(fù)進(jìn)行，直到最終每個新簇只包含一個對象。在凝聚或者分裂層次聚類方法中，用戶可以定義希望得到的簇?cái)?shù)目為一個終止條件。

第71頁/共287頁圖5-2對數(shù)據(jù)對象{a,b,c,d,e}的凝聚和分裂層次聚類第72頁/共287頁通常，使用一種稱做樹狀圖(Dendrogram)的樹形結(jié)構(gòu)表示層次聚類的過程。它展示出對象是如何一步步分組的。圖5-3顯示圖5-2中的五個對象的樹狀圖，其中，l=0顯示在第0層,五個對象都作為單元素簇。在l=1，對象a和b聚在一起形成第一個簇，并且在以后各層仍留在同一個簇中。還可以用一個垂直的數(shù)軸來顯示簇間的相似度尺度。例如，當(dāng)兩組對象{a,b}和{c,d,e}之間的相似度大約為0.16時，它們合并形成一個簇。第73頁/共287頁圖5-3數(shù)據(jù)對象{a,b,c,d,e}層次聚類的樹狀圖表示第74頁/共287頁四個廣泛采用的簇間距離度量方法如下，其中|p-p′|是兩個對象或點(diǎn)p和p′之間的距離，mi是簇Ci的均值，而ni是簇Ci中對象的數(shù)目。最小距離：dmin(Ci,Cj)=(5.23)最大距離：dmax(Ci,Cj)=(5.24)第75頁/共287頁均值距離：dmean(Ci,Cj)=|mi-mj|(5.25)平均距離：davg(Ci,Cj)=(5.26)第76頁/共287頁當(dāng)算法使用最小距離dmin(Ci,Cj)衡量簇間距離時，有時稱它為最近鄰聚類算法。此外，如果當(dāng)最近的簇之間的距離超過某個閾值時，聚類過程就會終止，則稱其為單連接算法。如果把數(shù)據(jù)點(diǎn)看做圖的節(jié)點(diǎn)，圖中的邊構(gòu)成簇內(nèi)節(jié)點(diǎn)間的路徑，那么兩個簇Ci和Cj的合并就對應(yīng)于在Ci和Cj的最近的一對節(jié)點(diǎn)之間添加一條邊。由于連接簇的邊總是從一個簇通向另一個簇，結(jié)果圖將形成一棵樹。因此，使用最小距離度量的凝聚層次聚類算法也稱為最小生成樹算法。當(dāng)一個算法使用最大距離dmax(Ci,Cj)度量簇間距離時，有時稱為最遠(yuǎn)鄰聚類算法(FarthestNeighborClusteringAlgorithm)。第77頁/共287頁如果當(dāng)最近簇之間的最大距離超過某個閾值時，聚類過程便終止，則稱其為全連接算法(CompleteLinkageAlgorithm)。通過把數(shù)據(jù)點(diǎn)看做圖中的節(jié)點(diǎn)，用邊來連接節(jié)點(diǎn)，可以把每個簇看成是一個完全子圖，也就是說，簇中所有節(jié)點(diǎn)都有邊來連接。兩個簇間的距離由兩個簇中距離最遠(yuǎn)的節(jié)點(diǎn)確定。最遠(yuǎn)鄰算法試圖在每次迭代中盡可能少地增加簇的直徑。如果真實(shí)的簇較為緊湊并且大小幾乎相等的話，這種方法將會產(chǎn)生高質(zhì)量的簇。否則，產(chǎn)生的簇可能毫無意義。

第78頁/共287頁最小和最大度量代表了簇間距離度量的兩個極端。它們趨向?qū)﹄x群點(diǎn)或噪聲數(shù)據(jù)過分敏感。使用均值距離或平均距離是對最小距離和最大距離的一種折中方法，而且可以克服離群點(diǎn)敏感性問題。盡管均值距離計(jì)算最簡單，但是平均距離也有它的優(yōu)勢，因?yàn)樗饶芴幚頂?shù)值數(shù)據(jù)又能處理分類數(shù)據(jù)。分類數(shù)據(jù)的均值向量可能很難計(jì)算或者根本無法定義。

第79頁/共287頁層次聚類方法盡管簡單，但選擇合并或分裂點(diǎn)比較困難。這樣的決定是非常關(guān)鍵的，因?yàn)橐坏┮唤M對象合并或者分裂，下一步的處理將對新生成的簇進(jìn)行。已做的處理不能撤銷，簇之間也不能交換對象。這樣的合并或分裂決定，如果在某一步?jīng)]有很好地選擇的話，就可能導(dǎo)致低質(zhì)量的聚類結(jié)果。此外，這種聚類方法不具有很好的可伸縮性，因?yàn)楹喜⒒蚍至训臎Q定需要檢查和估算大量的對象或簇。

第80頁/共287頁有希望改進(jìn)層次方法聚類質(zhì)量的一個方法是集成層次聚類和其他的聚類技術(shù)，形成多階段聚類。下面介紹了三種這類的方法。第一種方法稱為BIRCH，首先用樹結(jié)構(gòu)對對象進(jìn)行層次劃分，其中葉節(jié)點(diǎn)或者是低層次的非葉節(jié)點(diǎn)可以看做是由分辨率決定的“微簇”，然后使用其他的聚類算法對這些微簇進(jìn)行宏聚類；第二種方法ROCK基于簇間的互聯(lián)性進(jìn)行合并；第三種方法Chameleon探查層次聚類的動態(tài)建模。第81頁/共287頁5.3.2

BIRCH聚類算法BIRCH方法通過集成層次聚類和其他聚類算法來對大量數(shù)值數(shù)據(jù)進(jìn)行聚類，其中層次聚類用于初始的微聚類階段，而其他方法如迭代劃分(在后來的宏聚類階段)，它克服了凝聚聚類方法所面臨的兩個困難：①可伸縮性；②不能撤銷前一步所做的工作。BITCH引入兩個概念：聚類特征和聚類特征樹(CF樹)，它們用于概括描述簇的整體特征。這些結(jié)構(gòu)幫助聚類方法在大型數(shù)據(jù)庫中取得好的速度和伸縮性，使得BIRCH方法對增量聚類(在線聚類)和動態(tài)聚類也非常有效。

第82頁/共287頁

1.聚類特征給定簇中n個d維的數(shù)據(jù)對象或點(diǎn)，可以用以下公式定義該簇的質(zhì)心x0，半徑R和直徑D：

(5.27)(5.28)(5.29)第83頁/共287頁其中R是成員對象到質(zhì)心的平均距離，D是簇中成對的平均距離。R和D都反映了質(zhì)心周圍簇的緊湊程度。聚類特征(CF)是一個三維向量，匯總了對象簇的特征信息。在給定簇中，n個d維對象或點(diǎn){xi}，則該簇的CF定義如下:

CF=〈n，LS,SS〉(5.30)其中，n是簇中點(diǎn)的數(shù)目，LS是n個點(diǎn)的線性和(即)，SS是數(shù)據(jù)點(diǎn)的平方和(即)。第84頁/共287頁聚類特征實(shí)際是對給定簇的統(tǒng)計(jì)匯總。從統(tǒng)計(jì)學(xué)的觀點(diǎn)來看，它是簇的零階矩、一階矩和二階矩。聚類特征是可加的。例如，假定有兩個不相交的簇C1和C2，分別具有聚類特征CF1和CF2。那么由C1和C2合并而成的簇的聚類特征就是CF1+CF2。在BIRCH中做出聚類決策所需要的一切度量值都可以通過聚類特征計(jì)算。BIRCH通過使用聚類特征來匯總對象簇的信息，從而避免存儲所有對象，有效地利用了存儲空間。第85頁/共287頁

【例5.2】假定在簇C1中有三個點(diǎn)(2，5)，(3，2)和(4，3)。C1的聚類特征為

CF1=〈3，(2+3+4，5+2+3)，(22+32+42，52+22+32)〉=〈3，(9，10)，(29，38)〉假定C1和C2是不相交的，其中CF2=〈3，(35，36)，(417，440)〉。C1和C2合并形成一個新的簇C3，其聚類特征便是CF1和CF2之和，即：

CF3=〈3+3，(9+35，10+36)，(29+417，38+440)〉=〈(6，(44，46)，(446，478)〉第86頁/共287頁

2.聚類特征樹(CF樹)

CF樹是一棵高度平衡的樹，它存儲了層次聚類的聚類特征。圖5-4給出了一個例子。根據(jù)定義，樹中的非葉節(jié)點(diǎn)有后代或“子女”。非葉節(jié)點(diǎn)存儲了其子女的CF的總和，因而匯總了關(guān)于其子女的聚類信息。CF樹有兩個參數(shù)：分支因子B和閾值T。分支因子定義了每個非葉節(jié)點(diǎn)子女的最大數(shù)目，而閾值T給出了存儲在樹的葉節(jié)點(diǎn)中的子簇的最大直徑。這兩個參數(shù)影響結(jié)果樹的大小。第87頁/共287頁圖5-4

CF樹結(jié)構(gòu)第88頁/共287頁

BIRCH試圖利用可用的資源生成最好的簇。給定有限的主存，一個重要的考慮是最小化I/O所需時間。BIRCH采用了一種多階段聚類技術(shù)：數(shù)據(jù)集合的單遍掃描產(chǎn)生一個基本的好聚類，一或多遍的額外掃描可以用來進(jìn)一步(優(yōu)化)改進(jìn)聚類質(zhì)量。它主要包括兩個階段：

(1)階段一：BIRCH掃描數(shù)據(jù)庫，建立一棵存放于內(nèi)存的初始CF樹，它可以看做數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)的內(nèi)在的聚類結(jié)構(gòu)。

(2)階段二：BIRCH采用某個(選定的)聚類算法對CF樹的葉節(jié)點(diǎn)進(jìn)行聚類，把稀疏的簇當(dāng)做離群點(diǎn)刪除，而把稠密的簇合并為更大的簇。第89頁/共287頁

在階段一，隨著對象被插入，CF樹動態(tài)地構(gòu)造。這樣，該方法支持增量聚類。一個對象插入到最近的葉子節(jié)點(diǎn)(子簇)。如果在插入后存儲在葉子節(jié)點(diǎn)中的子簇的直徑大于閾值，那么該葉子節(jié)點(diǎn)或許還有其他節(jié)點(diǎn)被分裂。新對象插入后，關(guān)于該對象的信息向著樹根傳遞。通過修改閾值，CF樹的大小可以改變。如果存儲CF樹需要的內(nèi)存大于主存的大小，可以定義較小的閾值，并重建CF樹。重建樹從舊樹的葉節(jié)點(diǎn)建造一棵新樹，重建樹的過程不需要重讀所有的對象或點(diǎn)，這類似于B+樹構(gòu)建中的插入和節(jié)點(diǎn)分裂。為了建樹，只需讀一次數(shù)據(jù)。采用一些啟發(fā)式方法，通過額外的數(shù)據(jù)掃描可以處理離群點(diǎn)和改進(jìn)CF樹的質(zhì)量。CF樹建好后，可以在階段二使用任意聚類算法，例如典型的劃分方法。第90頁/共287頁

BIRCH聚類算法的計(jì)算復(fù)雜度是O(n)，其中n是聚類的對象的數(shù)目。實(shí)驗(yàn)表明該算法關(guān)于對象數(shù)目是線性可伸縮的，并且具有較好的數(shù)據(jù)聚類質(zhì)量。然而，既然CF樹的每個節(jié)點(diǎn)由于大小限制只能包含有限數(shù)目的條目，一個CF樹節(jié)點(diǎn)并不總是對應(yīng)于用戶所考慮的一個自然簇。此外，如果簇不是球形的，BIRCH不能很好地工作，因?yàn)樗褂冒霃交蛑睆降母拍顏砜刂拼氐倪吔纭５?1頁/共287頁5.3.3

CURE聚類算法

CURE是一種聚類算法，它使用各種不同的技術(shù)創(chuàng)建一種能夠處理大型數(shù)據(jù)、離群點(diǎn)和具有非球形和非均勻大小的簇的數(shù)據(jù)的方法。CURE使用簇中的多個代表點(diǎn)來表示一個簇。理論上，第一個代表點(diǎn)選擇離簇中心最遠(yuǎn)的點(diǎn)，而其余的點(diǎn)選擇離所有已經(jīng)選取的點(diǎn)最遠(yuǎn)的點(diǎn)。這樣，代表點(diǎn)自然地相對分散，這些點(diǎn)捕獲了簇的幾何形狀。選取的點(diǎn)的個數(shù)是一個參數(shù)，研究表明，點(diǎn)的個數(shù)選擇10或更大的值效果很好。第92頁/共287頁一旦選定代表點(diǎn)，它們就以因子α向簇中心收縮。這有助于減輕離群點(diǎn)的影響(離群點(diǎn)一般遠(yuǎn)離中心，因此收縮更多)。例如，一個到中心的距離為10個單位的代表點(diǎn)將移動3個單位(對于α=0.7)，而到中心距離為1個單位的代表點(diǎn)僅移動0.3個單位。

CURE使用一種凝聚層次聚類方案進(jìn)行實(shí)際的聚類。兩個簇之間的距離是任意兩個代表點(diǎn)(在它們向它們代表的中心收縮之后)之間的最短距離。盡管這種方案與我們看到的其他層次聚類方案不完全一樣，但是如果α=0，它等價于基于質(zhì)心的層次聚類；而α=1時它與單鏈層次聚類大致相同。注意，盡管使用層次聚類方案，但是CURE的目標(biāo)是發(fā)現(xiàn)用戶指定個數(shù)的簇。

第93頁/共287頁

CURE利用層次聚類過程的特性，在聚類過程的兩個不同階段刪除離群點(diǎn)。首先，如果一個簇增長緩慢，則意味它主要由離群點(diǎn)組成，因?yàn)楦鶕?jù)定義，離群點(diǎn)遠(yuǎn)離其他點(diǎn)，并且不會經(jīng)常與其他點(diǎn)合并。在CURE中，第一個離群點(diǎn)刪除階段一般出現(xiàn)在簇的個數(shù)是原來點(diǎn)數(shù)的1/3時。第二個離群點(diǎn)刪除階段出現(xiàn)在簇的個數(shù)達(dá)到k(期望的簇個數(shù))的量級時，小簇又被刪除。第94頁/共287頁由于CURE在最壞情況下復(fù)雜度為D(m2logm)(m數(shù)據(jù)點(diǎn)個數(shù))，它不能直接用于大型數(shù)據(jù)集。因此CURE使用了兩種技術(shù)來加快聚類過程。第一種技術(shù)是取隨機(jī)樣本，并在抽樣的數(shù)據(jù)點(diǎn)上進(jìn)行層次聚類。隨后是最終掃描，將數(shù)據(jù)集中剩余的點(diǎn)指派到最近代表點(diǎn)的簇中。稍后更詳細(xì)地討論CURE的抽樣方法。第二種附加的技術(shù)：CURE劃分樣本數(shù)據(jù)，然后聚類每個劃分中的點(diǎn)。完成預(yù)聚類步后，通常進(jìn)行中間簇的聚類，以及將數(shù)據(jù)集中的每個點(diǎn)指派到一個簇的最終掃描。CURE的劃分方案稍后也將更詳細(xì)地討論。第95頁/共287頁下面總結(jié)了CURE算法。k是期望的簇個數(shù)，m是點(diǎn)的個數(shù)，p是劃分的個數(shù)，q是一個劃分中點(diǎn)的期望壓縮，即一個劃分中簇的個數(shù)是。因此，簇的總數(shù)是。例如，如果m=10000，p=10并且q=100，則每個劃分包含10000/10=1000個點(diǎn)，每個劃分有1000/100=10個簇，而總共有10000/100=100個簇。第96頁/共287頁算法5.4CURE算法。輸入：簇的數(shù)目k；m個對象的數(shù)據(jù)庫D；劃分的個數(shù)p；期望壓縮q；收縮因子α。輸出：k個簇。

(1)由數(shù)據(jù)集抽取一個隨機(jī)樣本。經(jīng)驗(yàn)公式指出了樣本的大小(為了以較高的概率確保所有的簇都被最少的點(diǎn)代表)。

(2)將樣本劃分成p個大小相等的劃分。

(3)使用CURE的層次聚類算法，將每個劃分中的點(diǎn)聚類成m/(pq)個簇，得到總共m/q

個簇。注意，在此處理過程中將刪除某些離群點(diǎn)。

(4)使用CURE的層次聚類算法對上一步發(fā)現(xiàn)的m/q個簇進(jìn)行聚類，直到只剩下k個簇。

(5)刪除離群點(diǎn)。這是刪除離群點(diǎn)的第二階段。

(6)將所有剩余的數(shù)據(jù)點(diǎn)指派到最近的簇，得到完全聚類。第97頁/共287頁

1.CURE的抽樣使用抽樣的一個關(guān)鍵問題是樣本是否具有代表性，即它是否捕獲了感興趣的特性。對于聚類，該問題轉(zhuǎn)化為是否能夠在樣本中發(fā)現(xiàn)與在整個對象集中相同的簇。理想情況下，希望對于每個簇樣本集都包含一些對象，對于整個數(shù)據(jù)集中屬于不同簇的對象，在樣本集中也在不同的簇中。第98頁/共287頁

一個更具體和可達(dá)到的目標(biāo)是(以較高的概率)確保對于每個簇，至少抽取一些點(diǎn)。這樣的樣本所需要的點(diǎn)的個數(shù)因數(shù)據(jù)集而異，并且依賴于對象的個數(shù)和簇的大小。CURE的創(chuàng)建者推導(dǎo)出了一個樣本大小的界，指出為了(以較高的概率)確保從每個簇至少抽取一定數(shù)量的點(diǎn)，樣本集合應(yīng)當(dāng)多大。這個界由如下定理給出。第99頁/共287頁定理5.1

設(shè)f是一個分?jǐn)?shù)，0≤f≤1。對于大小為mi的簇Ci，以概率1-δ(0≤δ≤1)從簇Ci得到至少f×m個對象，樣本的大小s由下式給出：(5.31)其中，m是對象的個數(shù)。第100頁/共287頁假定有100000個對象，目標(biāo)是以80％的可能性得到10％的Ci簇對象，其中Ci的大小是1000。在此情況下，f=0.1，δ=0.2，m=100000，這樣s=11962。如果目標(biāo)是得到5％的Ci簇對象，其中Ci的大小是2000，則大小為5981的樣本就足夠了。第101頁/共287頁

2．劃分當(dāng)抽樣不夠時，CURE還使用劃分方法。其基本思想是，將點(diǎn)劃分成p個大小為m/p的組，使用CURE對每個劃分聚類，q可以粗略地看做劃分中的簇的平均大小，總共產(chǎn)生m/q個簇(注意，由于CURE用多個代表表示一個簇，因此對象個數(shù)的壓縮量不是q)。然后，m／q個中間簇的最終聚類產(chǎn)生期望的簇個數(shù)(k)。兩遍聚類都使用CURE的層次聚類算法，而最后一遍將數(shù)據(jù)集中的每個點(diǎn)指派到一個簇。第102頁/共287頁5.3.4

Chameleon聚類算法凝聚層次聚類技術(shù)通過合并兩個最相似的簇來聚類，其中簇的相似性定義依賴于具體的算法。有些凝聚聚類算法，如組平均，將其相似性概念建立在兩個簇之間的連接強(qiáng)度上(例如，兩個簇中點(diǎn)的逐對相似性)，而其他技術(shù)，如單鏈方法，使用簇的接近性(例如，不同簇中點(diǎn)的最小距離)來度量簇的相似性。盡管有兩種基本方法，但是僅使用其中一種方法可能導(dǎo)致錯誤的簇合并。如圖5-5所示，它顯示了4個簇。如果使用簇的接近性(用不同簇的最近的兩個點(diǎn)度量)作為合并標(biāo)準(zhǔn)，則將合并兩個圓形簇，如圖5-5(c)和(d)(它們幾乎接觸)所示，而不是合并兩個矩形簇，如圖5-5(a)和(b)(它們被一個小間隔分開)所示。然而，直觀地應(yīng)當(dāng)合并(a)和(b)。

第103頁/共287頁圖5-5接近性不是適當(dāng)?shù)暮喜?biāo)準(zhǔn)的情況第104頁/共287頁大部分聚類技術(shù)都有一個全局(靜態(tài))簇模型。例如，k均值假定簇是球形的，而DBSCAN基于單個密度閾值定義簇。使用這樣一種全局模型的聚類方案不能處理諸如大小、形狀和密度等簇特性在簇間變化很大的情況。作為簇的局部(動態(tài))建模的重要性的一個例子，考慮圖5-6。如果使用簇的接近性來決定哪一對簇應(yīng)當(dāng)合并，例如，使用單鏈聚類算法，則我們將合并簇(a)和(b)。然而并未考慮每個個體簇的特性。具體地，忽略了個體簇的密度。對于簇(a)和(b)，它們相對稠密，兩個簇之間的距離顯著大于同一個簇內(nèi)兩個最近鄰點(diǎn)之間的距離。對于簇(c)和(d)，就不是這種情況，它們相對稀疏。事實(shí)上，與合并簇(a)和(b)相比，簇(c)和(d)合并所產(chǎn)生的簇看上去與原來的簇更相似。

第105頁/共287頁圖5-6相對接近性概念的圖示第106頁/共287頁

Chameleon是一種凝聚聚類技術(shù)，它解決前面提到的問題。它將數(shù)據(jù)的初始劃分(使用一種有效的圖劃分算法)與一種新穎的層次聚類方案相結(jié)合。這種層次聚類使用接近性和互連性概念以及簇的局部建模。其關(guān)鍵思想是：當(dāng)合并后的結(jié)果簇類似于原來的兩個簇時，這兩個簇才應(yīng)當(dāng)合并。首先介紹自相似性，然后提供Chameleon算法的其余細(xì)節(jié)。第107頁/共287頁

1.確定合并哪些簇凝聚層次聚類技術(shù)重復(fù)地合并兩個最接近的簇，各具體技術(shù)之間的主要區(qū)別是簇的鄰近度定義方式不同。相比之下，Chameleon力求合并的一對簇，在合并后產(chǎn)生的簇，用接近性和互連性度量，與原來的一對簇最相似。因?yàn)檫@種方法僅依賴于簇對而不是全局模型，Chameleon能夠處理包含具有各種不同特性的簇的數(shù)據(jù)。下面是接近性和互連性的更詳細(xì)解釋。為了理解這些性質(zhì)，需要用鄰近度圖的觀點(diǎn)，并且考慮簇內(nèi)和簇間點(diǎn)之間的邊數(shù)和這些邊的強(qiáng)度。第108頁/共287頁

(1)相對接近度(relativecloseness，RC)是被簇的內(nèi)部接近度規(guī)范化的兩個簇的絕對接近度。僅當(dāng)結(jié)果簇中的點(diǎn)之間的接近程度幾乎與原來的每個簇一樣時，兩個簇合并。數(shù)學(xué)表述為(5.32)其中，mi和mj分別是簇Ci和Cj的大?。籆i,Cj是連接簇Ci和Cj的(k-最近鄰圖的)邊的平均權(quán)值；(Ci)是最小二分簇Ci的邊的平均權(quán)值；是最小二分簇Cj的邊的平均權(quán)值；EC表示割邊。圖5-6解釋了相對接近度的概念。正如前面的討論，盡管簇(a)和(b)比簇(c)和(d)更絕對接近，但是如果考慮簇的特性，則情況并非如此。第109頁/共287頁

(2)相對互連度(RelativeInterconnectivity，RI)是被簇的內(nèi)部互連度規(guī)范化的兩個簇的絕對互連度。如果結(jié)果簇中的點(diǎn)之間的連接幾乎與原來的每個簇一樣強(qiáng)，則兩個簇合并。數(shù)學(xué)表述為(5.33)第110頁/共287頁其中，EC(Ci,Cj)是連接簇Ci和Cj(k-最近鄰圖的)的邊之和；EC(Ci)是二分簇Ci的割邊的最小和：EC(Cj)是二分簇Cj的割邊的最小和。圖5-7解釋了相對互連度的概念。兩個圓形簇(c)和(d)比兩個矩形簇(a)和(b)具有更多連接。然而，合并(c)和(d)產(chǎn)生的簇具有非常不同于(c)和(d)的連接性。相比之下，合并(a)和(b)產(chǎn)生的簇的連接性與簇(a)和簇(b)非常類似。chanleleon使用的一種方法是合并最大化(RI(Ci,Cj)×RC(Ci,Cj))α的簇對，其中α是用戶指定的參數(shù)，通常大于1。第111頁/共287頁圖5-7相對互聯(lián)性概念的圖示第112頁/共287頁

2.Chameleon算法

Chameleon算法由三個關(guān)鍵步驟組成：稀疏化、圖劃分和層次聚類。算法5.5和圖5-8描述了這些步驟。

圖5-8

Chameleon進(jìn)行聚類的整個步驟第113頁/共287頁算法5.5

Chameleon算法。輸入：數(shù)據(jù)庫D；輸出：m個簇。

(1)構(gòu)造k-鄰近圖。

(2)使用多層圖劃分算法劃分圖。

(3)Repeat。

(4)合并關(guān)于相對互聯(lián)性和相對接近性的簇，最好地保持簇的自相似的簇。

(5)Until只剩下m個簇。稀疏化：Chameleon算法的第一步是產(chǎn)生k-最近鄰圖。概念上講，這樣的圖由鄰近度圖導(dǎo)出，并且僅包含點(diǎn)和它的k個最近鄰(即最近的點(diǎn))之間的邊。導(dǎo)出過程如下：第114頁/共287頁

m個數(shù)據(jù)點(diǎn)的m×m鄰近度矩陣可以用一個稠密圖表示，圖中每個結(jié)點(diǎn)與其他所有結(jié)點(diǎn)相連接，任何一對結(jié)點(diǎn)之間邊的權(quán)值反映它們之間的鄰近性。盡管每個對象與其他對象都有某種程度的鄰近性，但是對于大部分?jǐn)?shù)據(jù)集，對象只與少量其他對象高度相似，而與大部分其他對象的相似性很弱。這一性質(zhì)可以用來稀疏化鄰近度圖(矩陣)。在實(shí)際的聚類過程開始之前，將許多低相似度(高相異度)的值置0。例如，稀疏化可以這樣進(jìn)行：斷開相似度(相異度)低于(高于)指定閾值的邊，或僅保留連接到點(diǎn)的k個最近鄰的邊。后一種方法創(chuàng)建所謂k-最近鄰圖(k-nearestneighborgraph)。第115頁/共287頁使用稀疏化的鄰近度圖而不是完全的鄰近度圖可以顯著地降低噪聲和離群點(diǎn)的影響，提高計(jì)算的有效性。圖劃分:一旦得到稀疏化的圖，就可以使用有效的多層圖劃分算法來劃分?jǐn)?shù)據(jù)集。Chameleon從一個全包含的圖(簇)開始，然后，二分當(dāng)前最大的子圖(簇)，直到?jīng)]有一個簇多于MIN_SIZE個點(diǎn)，其中MIN_SIZE是用戶指定的參數(shù)。這一過程導(dǎo)致大量大小大致相等的、良連接的頂點(diǎn)(高度相似的數(shù)據(jù)點(diǎn))的集合。目標(biāo)是確保每個劃分包含的對象大部分都來自一個真正的簇。凝聚層次聚類:Chameleon基于自相似性概念合并簇。可以用參數(shù)指定，讓Chameleon一步合并多個簇對，并且在所有的對象都合并到單個簇之前停止。第116頁/共287頁

3.復(fù)雜性假定m是數(shù)據(jù)點(diǎn)的個數(shù)，p是劃分的個數(shù)。在圖劃分得到的p個劃分上進(jìn)行凝聚層次聚類需要O(p2logp)時間。劃分圖需要的時間總量是O(mp+mlogm)。圖稀疏化的時間復(fù)雜度依賴于建立k-最近鄰圖需要多少時間。對于低維數(shù)據(jù)，如果使用k-d樹或類似的數(shù)據(jù)結(jié)構(gòu)，則需要O(mlogm)時間。不幸的是，這種數(shù)據(jù)結(jié)構(gòu)只適用于低維數(shù)據(jù)，因此，對于高維數(shù)據(jù)集，稀疏化的時間復(fù)雜度變成O(m2)。由于只需要存放k-最近鄰表，空間復(fù)雜度是O(km)加上存放數(shù)據(jù)所需要的空間。

第117頁/共287頁

【例5.3】Chameleon用于其他聚類算法(如K均值和DBSCAN)很難聚類的兩個數(shù)據(jù)集。聚類的結(jié)果如圖5-9所示。簇用點(diǎn)的明暗區(qū)分。在圖5-9(a)中，兩個簇具有不規(guī)則的形狀，并且相當(dāng)接近，此外，還有噪聲。在圖5-9(b)中，兩個簇通過一個橋連接，并且也有噪聲。盡管如此，Chameleon還是識別出了大部分人認(rèn)為自然的簇。這表明Chameleon對于空間數(shù)據(jù)聚類很有效。最后，注意與其他聚類方案不同，Chameleon并不丟棄噪聲點(diǎn)，而是把它們指派到簇中。第118頁/共287頁圖5-9使用Chameleon對兩個二維點(diǎn)集進(jìn)行聚類第119頁/共287頁

4．優(yōu)點(diǎn)與局限性

Chameleon能夠有效地聚類空間數(shù)據(jù)，即便存在噪聲和離群點(diǎn)，并且簇具有不同的形狀、大小和密度。Chameleon假定由稀疏化和圖劃分過程產(chǎn)生的對象組群是子簇，即一個劃分中的大部分點(diǎn)屬于同一個真正的簇。如果不是，則凝聚層次聚類將混合這些錯誤，因?yàn)樗^對不可能再將已經(jīng)錯誤地放到一起的對象分開。這樣，當(dāng)劃分過程未產(chǎn)生子簇時，Chameleon就有問題。對于高維數(shù)據(jù)，常常出現(xiàn)這種情況。第120頁/共287頁5.4密度聚類方法

5.4.1

DBSCAN基于密度的聚類尋找被低密度區(qū)域分離的高密度區(qū)域。DBSCAN是一種簡單、有效的基于密度的聚類算法，它解釋了基于密度的聚類方法的許多重要概念。第121頁/共287頁

1.傳統(tǒng)的密度：基于中心的方法盡管定義密度的方法沒有定義相似度的方法多，但仍存在幾種不同的方法。本節(jié)討論DBSCAN使用的基于中心的方法。在基于中心的方法中，數(shù)據(jù)集中特定點(diǎn)的密度通過對該點(diǎn)Eps半徑之內(nèi)的點(diǎn)計(jì)數(shù)(包括點(diǎn)本身)來估計(jì)，如圖5-10所示。點(diǎn)A的Eps半徑內(nèi)點(diǎn)的個數(shù)為7，包括A本身。該方法實(shí)現(xiàn)簡單，但是點(diǎn)的密度依賴于指定的半徑。例如，如果半徑足夠大，則所有點(diǎn)的密度都等于數(shù)據(jù)集中的點(diǎn)數(shù)m。類似地，如果半徑太小，則所有點(diǎn)的密度都是1。對于低維數(shù)據(jù)，一種確定合適半徑的方法在討論DBSCAN算法時給出。第122頁/共287頁基于中心的點(diǎn)的密度方法可以將點(diǎn)分為以下幾類：

(1)稠密區(qū)域內(nèi)部的點(diǎn)(核心點(diǎn))。

(2)稠密區(qū)域邊緣上的點(diǎn)(邊界點(diǎn))。

(3)稀疏區(qū)域中的點(diǎn)(噪聲或背景點(diǎn))。第123頁/共287頁圖5-10基于中心的密度第124頁/共287頁圖5-11核心點(diǎn)、邊界點(diǎn)和噪聲點(diǎn)第125頁/共287頁圖5-11使用二維點(diǎn)集圖示了核心點(diǎn)、邊界點(diǎn)和噪聲點(diǎn)的概念。下文給出更詳盡的描述。

(1)核心點(diǎn)(CorePoint)：這些點(diǎn)在基于密度的簇內(nèi)部。點(diǎn)的鄰域由距離函數(shù)和用戶指定的距離參數(shù)ε決定。一個點(diǎn)是核心點(diǎn)，如果該點(diǎn)在給定鄰域內(nèi)的點(diǎn)的個數(shù)超過給定的閾值MinPts，其中MinPts也是一個用戶指定的參數(shù)。在圖5-11中，如果MinPts≥7，則對于給定的半徑(ε)，點(diǎn)A是核心點(diǎn)。

(2)邊界點(diǎn)(BorderPoint)：邊界點(diǎn)不是核心點(diǎn)，但它落在某個核