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

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

10.1聚類分析

10.2劃分方法10.3層次方法

10.4基于密度的方法

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

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

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

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

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

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

大大增加了聚類的難度。

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

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

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

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

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

輸出：k個簇的集合

k：簇的個數(shù)

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

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

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

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

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

缺點（1）要求用戶事先給出要生成的簇數(shù)k，不適合的k值可能

返回較差的結(jié)果

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

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

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

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

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

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

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

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

（分裂）方式，層次聚類方法可以進一步分為凝聚

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

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

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

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

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

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

單連接算法例子*先將五個樣本都分別看成是一個簇，最靠近的兩個簇是3和4，因為他們具有最小的簇間距離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間的距離不變，修改后的距離矩陣如圖所示，在四個簇1，2，(34)，5中，最靠近的兩個簇是1和5，它們具有最小簇間距離D（1,5）＝7.07。單連接算法例子單連接算法例子凝聚的與分裂的層次聚類*最小和最大度量代表了簇間距離度量的兩個極端。它

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

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

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