韓家煒數(shù)據(jù)挖掘第十章聚類課件詳解

第十章聚類分析：基本概念和方法本章結(jié)構(gòu)

10.1聚類分析

10.2劃分方法10.3層次方法

10.4基于密度的方法

10.5基于網(wǎng)格的方法10.6聚類評(píng)估一、聚類分析*什么是聚類？聚類分析（clusteranalysis）簡稱聚類（cluster-ing）是把數(shù)據(jù)劃分成子集的過程。每個(gè)子集是一個(gè)簇（cluster），使得簇中的對(duì)象彼此相似，但與其他簇中的對(duì)象很不相似。*分類與聚類分類稱作監(jiān)督學(xué)習(xí)，事先知道訓(xùn)練樣本的標(biāo)簽，通過挖掘?qū)儆诓煌悇e標(biāo)簽的樣本分開，可利用得到的分類模型，預(yù)測樣本屬于哪個(gè)類別。而聚類是一種無監(jiān)督的學(xué)習(xí)，事先不知道樣本的類別標(biāo)簽，通過對(duì)相關(guān)屬性的分析，將具有類似屬性的樣本聚成一類。

一、聚類分析數(shù)據(jù)挖掘?qū)垲惖牡湫鸵螅?.處理不同屬性類型的能力

聚類的對(duì)象不只是數(shù)值，也有在二元的、標(biāo)稱的、

序數(shù)的等類型數(shù)據(jù)的應(yīng)用。現(xiàn)在，很多應(yīng)用需要

對(duì)諸如圖、序列、圖像這樣的復(fù)雜數(shù)據(jù)類型進(jìn)行

聚類的技術(shù)。2.聚類高維數(shù)據(jù)的能力高維度的數(shù)據(jù)往往比較稀松，而且高度傾斜，這

大大增加了聚類的難度。

3.基于約束的聚類找到既滿足約束條件，又具有良好聚類特性的數(shù)

據(jù)分組。4.簇的分離性

有些方法把數(shù)據(jù)對(duì)象劃分為互斥的簇。但在一些情況下一個(gè)數(shù)據(jù)可以屬于多個(gè)簇。10.2劃分方法給定n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集D，以及要生成的簇?cái)?shù)k，劃分算法把數(shù)據(jù)對(duì)象組織成k(k≤n)個(gè)分區(qū)，每個(gè)分區(qū)代表一個(gè)簇。

傳統(tǒng)的劃分方法可能需要窮舉所有可能的劃分，計(jì)算量極大，所以大多應(yīng)用都采用了啟發(fā)式方法，如：Ｋ－均值和ｋ－中心點(diǎn)算法。Ｋ－均值：一種基于形心的技術(shù)基于形心的技術(shù)使用簇Ci的中心點(diǎn)ｃi代表該簇。對(duì)象ｐ∈

Ci與ｃi之差用dist（p，ｃi）度量，簇Ci的質(zhì)量可以用簇內(nèi)變差度量，它是Ci中所有對(duì)象和型心ｃi之間的誤差的平方和。但是，n值和k值較大時(shí)優(yōu)化簇內(nèi)變差得到精確解的計(jì)算開銷非常巨大。所以，經(jīng)常使用k-均值（K-means）方法進(jìn)行聚類。Ｋ－均值：一種基于形心的技術(shù)K-均值算法過程：輸入：

輸出：k個(gè)簇的集合

k：簇的個(gè)數(shù)

D：包含n個(gè)數(shù)據(jù)的數(shù)據(jù)集

方法：（1）從D中任意選擇k個(gè)對(duì)象作為初始簇中心；（2）repeat（3）根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象分配到最相似的簇；（4）更新簇均值，即計(jì)算每個(gè)簇中對(duì)象的均值；（5）until不再發(fā)生變化；

k均值算法把簇的形心定義為簇內(nèi)點(diǎn)的均值。Ｋ－均值：一種基于形心的技術(shù)K-均值聚類算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)（1）思想簡單易行；

（2）時(shí)間復(fù)雜度接近線性；

（3）對(duì)大數(shù)據(jù)集，是可伸縮和有效的；

缺點(diǎn)（1）要求用戶事先給出要生成的簇?cái)?shù)k，不適合的k值可能

返回較差的結(jié)果

（2）不適合發(fā)現(xiàn)非凸形狀的簇，或者大小差別很大的

簇。（3）對(duì)噪聲和離群點(diǎn)敏感。Ｋ－均值：一種基于形心的技術(shù)對(duì)k-均值算法可伸縮性的改進(jìn)思路：（1）在大型數(shù)據(jù)集上聚類時(shí)使用合適的樣本。（2）使用過濾方法，使用空間層次數(shù)據(jù)索引節(jié)省計(jì)算均值的開

銷。（3）利用微聚類思想，就是在聚類前先把鄰近的對(duì)象劃分到一些“微簇”。K-中心點(diǎn)：一種基于代表對(duì)象的技術(shù)K均值算法對(duì)于離群點(diǎn)是敏感的，因?yàn)橐粋€(gè)有很大極端值的對(duì)象可能顯著地扭曲數(shù)據(jù)的分布。平方差的使用更是嚴(yán)重惡化了這一影響。

我們可以在每個(gè)簇中選出一個(gè)實(shí)際的對(duì)象來代表該簇。而不是利用均值。其余的每個(gè)對(duì)象分配到到與其最相似的代表性對(duì)象所在的簇中。這樣，劃分基于絕對(duì)誤差標(biāo)準(zhǔn)（absolute-errorcriterion）來進(jìn)行劃分。K-中心點(diǎn)聚類通過最小化該絕對(duì)誤差，把n個(gè)對(duì)象劃分到k個(gè)簇中。K-中心點(diǎn)：一種基于代表對(duì)象的技術(shù)

K-中心點(diǎn)：一種基于代表對(duì)象的技術(shù)K-中心點(diǎn)：一種基于代表對(duì)象的技術(shù)

K-中心點(diǎn)：一種基于代表對(duì)象的技術(shù)

10.3層次方法--層次聚類方法（hierarchicalclusteringmethod）

將數(shù)據(jù)對(duì)象組成一棵聚類樹。--根據(jù)層次分解是以自底向上（合并）還是自頂向下

（分裂）方式，層次聚類方法可以進(jìn)一步分為凝聚

的和分裂的。--一種純粹的層次聚類方法的質(zhì)量受限于：一旦合并

或分裂執(zhí)行，就不能修正。也就是說，如果某個(gè)合

并或分裂決策在后來證明是不好的選擇，該方法無

法退回并更正。凝聚的與分裂的層次聚類下圖描述了一種凝聚層次聚類算法AGNES和一種分裂層次聚類算法DIANA對(duì)一個(gè)包含五個(gè)對(duì)象的數(shù)據(jù)集合{a,b,c,d,e}的處理過程。Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)凝聚的與分裂的層次聚類*初始，AGNES將每個(gè)對(duì)象自為一簇，然后這些簇根據(jù)某種準(zhǔn)則逐步合并，直到所有的對(duì)象最終合并形成一個(gè)簇。例如，如果簇C1中的一個(gè)對(duì)象和簇C2中的一個(gè)對(duì)象之間的距離是所有

屬于不同簇的對(duì)象間歐氏距離中最小的，則C1和C2合并。*在DIANA中，所有的對(duì)象用于形成一個(gè)初始簇。根據(jù)某種原則（如，簇中最近的相鄰對(duì)象的最大歐氏距離），將該簇分裂。簇的分裂過程反復(fù)進(jìn)行，直到最終每個(gè)新簇只包含一個(gè)對(duì)象。*在凝聚或者分裂層次聚類方法中，用戶可以定義希望得到的簇?cái)?shù)目作為一個(gè)終止條件。凝聚的與分裂的層次聚類通常，使用一種稱作樹狀圖的樹形結(jié)構(gòu)表示層次聚類的過程。它展示出對(duì)象是如何一步步分組的。圖2顯示圖1的五個(gè)對(duì)象的樹狀圖。描述簇之間的相似程度。例如，{a,b}和{c,d,e}的相似度大約為0.16。凝聚的與分裂的層次聚類

凝聚的與分裂的層次聚類最小距離最大距離均值距離平均距離凝聚的與分裂的層次聚類

單連接算法例子*先將五個(gè)樣本都分別看成是一個(gè)簇，最靠近的兩個(gè)簇是3和4，因?yàn)樗麄兙哂凶钚〉拇亻g距離D（3，4）=5.0。*第一步：合并簇3和4，得到新簇集合1，2，(34)，5單連接算法例子*更新距離矩陣：

D(1,(34))=min(D(1,3)，D(1,4))=min(20.6，22.4)=20.6D(2,(34))=min(D(2,3)，D(2,4))=min(14.1，11.2)=11.2D(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。單連接算法例子單連接算法例子凝聚的與分裂的層次聚類*最小和最大度量代表了簇間距離度量的兩個(gè)極端。它

們趨向?qū)﹄x群點(diǎn)或噪聲數(shù)據(jù)過分敏感。*使用均值距離和平均距離是對(duì)最小和最大距離之間的

一種折中方法，而且可以克服離群點(diǎn)敏感性問題。*層次聚類方法的困難之處:(1)層次聚類方法盡管簡單，但經(jīng)常會(huì)遇到合并或分裂點(diǎn)選擇的困難。因?yàn)橐坏┮唤M對(duì)象合并或者分裂，下一步的處理將對(duì)新生成的簇進(jìn)行。(2)不具有很好的可伸縮性，因?yàn)楹喜⒒蚍至训臎Q定需要檢查和估算大量的對(duì)象或簇。BIRCH：使用聚類特征樹的多階段聚類*BIRCH方法通過集成層次聚類和其他聚類算法來對(duì)大量數(shù)值數(shù)據(jù)進(jìn)行聚類。其中層次聚類用于初始的微聚類階段，而其他方法如迭代劃分（在后來的宏聚類階段）。它克服了凝聚聚類方法所面臨的兩個(gè)困難：1.可伸縮性；2.不能撤銷前一步所做的工作；*BIRCH使用聚類特征來概括一個(gè)簇，使用聚類特征樹（CF樹）來表示聚類的層次結(jié)構(gòu)。這些結(jié)構(gòu)幫助聚類方法在大型數(shù)據(jù)庫中取得好的速度和伸縮性，還使得BIRCH方法對(duì)新對(duì)象增量和動(dòng)態(tài)聚類也非常有效。BIRCH：使用聚類特征樹的多階段聚類考慮一個(gè)n個(gè)d維的數(shù)據(jù)對(duì)象或點(diǎn)的簇，簇的聚類特征（ClusteringFeature，CF）是一個(gè)3維向量，匯總了對(duì)象簇的信息。定義如下

CF=<n,LS,SS>其中，n是簇中點(diǎn)的數(shù)目，LS是n個(gè)點(diǎn)的線性和（即）,SS是數(shù)據(jù)點(diǎn)的平方和（即）。BIRCH：使用聚類特征樹的多階段聚類使用聚類特征，我們可以很容易地推導(dǎo)出簇的許多有用的統(tǒng)計(jì)量。例如，簇的形心x0，半徑R和直徑D分別是：其中R是成員對(duì)象到形心的平均距離，D是簇中逐對(duì)對(duì)象的平均距離。R和D都反映了形心周圍簇的緊湊程度。BIRCH：使用聚類特征樹的多階段聚類*使用聚類特征概括簇可以避免存儲(chǔ)個(gè)體對(duì)象或點(diǎn)的詳細(xì)信息。我們只需要固定大小的空間來存放聚類特征。這是空間中BIRCH有效性的關(guān)鍵。*聚類特征是可加的。也就是說，對(duì)于兩個(gè)不相交的簇C1和C2，其聚類特征分別為CF1=<n1，LS1，SS1>和CF2=<n2，LS2，SS2>，合并C1和C2后的簇的聚類特征是CF1+CF2=<n1+n2，LS1+LS2，SS1+SS2>假定在簇C1中有三個(gè)點(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和第2個(gè)簇C2是不相交的，其中CF2=<3,(35,36),(417,440)>。C1和C2合并形成一個(gè)新的簇C3，其聚類特征便是CF1和CF2之和，即：CF3=<3+3,(9+35,10+36),(29+417,38+440)>=<6,(44,46),(446,478)>BIRCH：使用聚類特征樹的多階段聚類*CF樹是一棵高度平衡的樹，它存儲(chǔ)了層次聚類的聚類特征。如圖給出了一個(gè)例子。樹中的非葉節(jié)點(diǎn)有后代或“子女”。非葉節(jié)點(diǎn)存儲(chǔ)了其子女的CF的總和，因而匯總了關(guān)于其子女的聚類信息。*CF樹有兩個(gè)參數(shù)：分支因子B和閾值T。分支因子定義了每個(gè)非葉節(jié)點(diǎn)子女的最大數(shù)目。而閾值參數(shù)給出了存儲(chǔ)在樹的葉節(jié)點(diǎn)中的子簇的最大直徑。這兩個(gè)參數(shù)影響結(jié)果數(shù)的大小。BIRCH：使用聚類特征樹的多階段聚類*BIRCH主要包括兩個(gè)階段：階段一：BIRCH掃描數(shù)據(jù)庫，建立一棵存放于內(nèi)存的初始CF樹，它可以看作數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)的內(nèi)在的聚類結(jié)構(gòu)。階段二：BIRCH采用某個(gè)（任意的）聚類算法對(duì)CF樹的葉節(jié)點(diǎn)進(jìn)行聚類，把稀疏的簇當(dāng)作離群點(diǎn)刪除，而把稠密的簇合并為更大的簇。*在階段一中，隨著對(duì)象被插入，CF樹被動(dòng)態(tài)地構(gòu)造。這樣，該方法支持增量聚類。BIRCH：使用聚類特征樹的多階段聚類*實(shí)驗(yàn)表明該算法關(guān)于對(duì)象數(shù)目是線性可伸縮的，并且具有較好的數(shù)據(jù)聚類質(zhì)量。*因?yàn)镃F樹的每個(gè)節(jié)點(diǎn)由于大小限制只能包含有限數(shù)目的條目，一個(gè)CF樹節(jié)點(diǎn)并不總是對(duì)應(yīng)于用戶所考慮的一個(gè)自然簇。*此外，如果簇不是球形的，BIRCH不能很好地工作，因?yàn)樗褂冒霃交蛑睆降母拍顏砜刂拼氐倪吔?。Chameleon：使用動(dòng)態(tài)建模的多階段層次聚類*Chameleon是一種層次聚類算法，它采用動(dòng)態(tài)建模來確定一對(duì)簇之間的相似度。*在Chameleon中，簇的相似度依據(jù)如下兩點(diǎn)評(píng)估：（1）簇中對(duì)象的連接情況（2）簇的鄰近性也就是說，如果兩個(gè)簇的互連性都很高并且它們又靠的很近就將其合并。*Chameleon算法的思想是：首先使用一種圖劃分算法將k最近鄰圖劃分成大量相對(duì)較小的子簇。然后使用凝聚層次聚類算法，基于子簇的相似度反復(fù)地合并子簇。*Chameleon在發(fā)現(xiàn)高質(zhì)量的任意形狀的簇方面具有很強(qiáng)的能力