第8章_聚類分析：基本概念和算法

1、聚類分析：基本概念和算法聚類分析：基本概念和算法第第8章章 聚類分析：基本概念和算法聚類分析：基本概念和算法什么是聚類分析什么是聚類分析?l聚類分析將數(shù)據(jù)劃分成有意義或有用的組（簇）。l聚類分析僅根據(jù)在數(shù)據(jù)中發(fā)現(xiàn)的描述對象及其關系的信息，將數(shù)據(jù)對象分組。其目標是，組內的對象相互之間是相似的，而不同組中的對象是不同的。Inter-cluster distances are maximizedIntra-cluster distances are minimized什么是一個好的聚類方法什么是一個好的聚類方法?l一個好的聚類方法要能產(chǎn)生高質量的聚類結果簇，這些簇要具備以下兩個特點： 高的簇內相似性

2、 低的簇間相似性 l聚類結果的好壞取決于該聚類方法采用的相似性評估方法以及該方法的具體實現(xiàn)；l聚類方法的好壞還取決于該方法是否能發(fā)現(xiàn)某些還是所有的隱含模式；聚類的復雜性聚類的復雜性How many clusters?Four Clusters Two Clusters Six Clusters 不同的聚類類型不同的聚類類型l劃分聚類（Partitional Clustering）l層次聚類（Hierarchical Clustering）l互斥（重疊）聚類（exclusive clustering）l非互斥聚類（non-exclusive）l模糊聚類（fuzzy clustering）l完全聚

3、類（complete clustering）l部分聚類（partial clustering）劃分聚類（劃分聚類（Partitional Clustering）Original PointsA Partitional Clusteringl劃分聚類簡單地將數(shù)據(jù)對象集劃分成不重疊的子集，使得每個數(shù)據(jù)對象恰在一個子集。層次聚類（層次聚類（Hierarchical Clustering）p4p1p3p2 p4 p1 p3 p2 p4p1p2p3p4p1 p2p3Traditional Hierarchical ClusteringNon-traditional Hierarchical Cluste

4、ringNon-traditional DendrogramTraditional Dendrograml層次聚類是嵌套簇的集族，組織成一棵樹?；コ獾?、重疊的、模糊的互斥的、重疊的、模糊的l互斥的（Exclusive） 每個對象都指派到單個簇.l重疊的（overlapping）或非互斥的（non-exclusive） 聚類用來反映一個對象.同時屬于多個組（類）這一事實。 例如：在大學里，一個人可能既是學生，又是雇員l模糊聚類（Fuzzy clustering ） 每個對象以一個0（絕對不屬于）和1（絕對屬于）之間的隸屬權值屬于每個簇。換言之，簇被視為模糊集。l部分的（Partial） 部分聚類

5、中數(shù)據(jù)集某些對象可能不屬于明確定義的組。如：一些對象可能是離群點、噪聲。l完全的（complete） 完全聚類將每個對象指派到一個簇。不同的簇類型不同的簇類型l明顯分離的l基于原型的l基于圖的l基于密度的l概念簇簇類型簇類型: 明顯分離的（明顯分離的（Well-Separated）l每個點到同簇中任一點的距離比到不同簇中所有點的距離更近。3 well-separated clusters簇類型簇類型:基于原型的基于原型的l每個對象到定義該簇的原型的距離比到其他簇的原型的距離更近。對于具有連續(xù)屬性的數(shù)據(jù)，簇的原型通常是質心，即簇中所有點的平均值。當質心沒有意義時，原型通常是中心點，即簇中最有代表

6、性的點。l基于中心的（ Center-Based）的簇：每個點到其簇中心的距離比到任何其他簇中心的距離更近。4 center-based clusters簇類型簇類型:基于圖的基于圖的l如果數(shù)據(jù)用圖表示，其中節(jié)點是對象，而邊代表對象之間的聯(lián)系。l簇可以定義為連通分支（connected component）：互相連通但不與組外對象連通的對象組。l基于近鄰的（ Contiguity-Based）：其中兩個對象是相連的，僅當它們的距離在指定的范圍內。這意味著，每個對象到該簇某個對象的距離比到不同簇中任意點的距離更近。8 contiguous clusters簇類型簇類型: 基于密度的（基于密度的（

7、Density-Based）l簇是對象的稠密區(qū)域，被低密度的區(qū)域環(huán)繞。6 density-based clusters簇類型簇類型: 概念簇（概念簇（Conceptual Clusters）l可以把簇定義為有某種共同性質的對象的集合。例如：基于中心的聚類。還有一些簇的共同性質需要更復雜的算法才能識別出來。. 2 Overlapping CirclesK均值聚類均值聚類基本基本K均值算法均值算法l1.選擇k個點作為初始的質心l2.repeatl3. 將每個點指派到最近的質心，形成k個簇l4. 重新計算每個簇的質心l5.until 質心不發(fā)生變化數(shù)據(jù)對象之間的相異度數(shù)據(jù)對象之間的相異度lEucli

8、dean Distance nkkkyxyxd12)(),(明可夫斯基距離（明可夫斯基距離（Minkowski Distance）lMinkowski Distancelr = 1. 城市塊 (曼哈頓, 出租車, L1 范數(shù)) 距離. lr = 2. 歐氏距離（ L2 范數(shù)）lr . 上確界 (Lmax或L 范數(shù)) 距離. rnkrkkyxyxd11)|(),(二元數(shù)據(jù)的相似性度量二元數(shù)據(jù)的相似性度量l兩個僅包含二元屬性的對象之間的相似性度量也稱相似系數(shù)l兩個對象的比較導致四個量f00 = x取0并且y取0的屬性個數(shù)f01 = x取0并且y取1的屬性個數(shù)f10 = x取1并且y取0的屬性個數(shù)f

9、11 = x取1并且y取1的屬性個數(shù)l簡單匹配系數(shù)SMC = 值匹配的屬性個數(shù) / 屬性個數(shù) = (f11 +f00) / (f01 + f10 + f11 + f00)lJaccard(雅卡爾 ) 系數(shù) （非對稱二元屬性）J = 匹配的個數(shù) / 不涉及0-0匹配的屬性個數(shù)= (f11) / (f01 + f10 +f11) 余弦相似度余弦相似度l If d1 and d2 are two document vectors, then cos( x, y ) = (x y) / |x| |y| , l Example: x = 3 2 0 5 0 0 0 2 0 0 y = 1 0 0 0 0

10、 0 0 1 0 2 x y= 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5 |x| = (3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481 |y| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245 cos( d1, d2 ) = 0.3150誤差平方和（誤差平方和（sum of the squared error，SSE）l誤差平方和l它可以度量聚類的質量。誤

11、差平方和越小，意味著質心是簇中點的更好代表。l可以證明：當緊鄰函數(shù)是歐式距離（L2）時，使簇的SSE最小的質心是均值，即l可以證明：當緊鄰函數(shù)是曼哈頓距離（L1）時，使簇的L1絕對誤差和（SAE）最小的質心是中位數(shù)21( , )ikiix CSSEdist c x1iixCicxml當緊鄰函數(shù)是歐式距離時，可對SSE求導2121()()2()012()0iikkkkiix Ckkkiix Ckkkx Ckkkkx Cx ckSSEcxcccxccxcxcxm選擇初始的質心選擇初始的質心l隨機選擇l從層次聚類中提取K個簇，并用這些簇的質心作為初始質心l隨機選擇第一個點，或取所有點的質心作為第一個

12、點。然后，對于每個后繼初始質心，選擇離已經(jīng)選取過的初始質心最遠的點l二分K均值二分二分k均值均值l二分k均值算法是基本k均值算法的直接k個簇。l它將所有點的集合分裂成兩個簇，從這些簇中選取一個繼續(xù)分裂，如此下去，直到產(chǎn)生k個簇二分二分k均值算法均值算法l初始化簇表，使之包含由所有的點組成的簇。lRepeatl 從簇表中取出一個簇。l for i=1 to 實驗次數(shù) dol 使用基本k均值，二分選定的簇。l end forl 從二分實驗中選擇具有最小總sse的兩個簇。l 將這兩個簇添加到簇表中。lUntil 簇表中包含k個簇。K means 的優(yōu)點與缺點的優(yōu)點與缺點l優(yōu)點：l算法簡單l適用于球形

13、簇l二分k均值等變種算法運行良好，不受初始化問題的影響。l缺點：l不能處理非球形簇、不同尺寸和不同密度的簇l對離群點、噪聲敏感K-means 的局限性的局限性lK-means has problems when clusters are of differing Sizes大小 Densities密度 Non-globular shapes非球形Limitations of K-means: Differing SizesOriginal PointsK-means (3 Clusters)Limitations of K-means: Differing DensityOriginal Po

14、intsK-means (3 Clusters)Limitations of K-means: Non-globular ShapesOriginal PointsK-means (2 Clusters)K-means 局限性的克服局限性的克服Original PointsK-means ClustersOne solution is to use many clusters.Find parts of clusters, but need to put together.Overcoming K-means LimitationsOriginal PointsK-means Clusters

15、Overcoming K-means LimitationsOriginal PointsK-means Clusters層次聚類層次聚類l層次聚類按數(shù)據(jù)分層建立簇，形成一棵以簇為節(jié)點的樹，稱為聚類圖。 l按自底向上層次分解，則稱為凝聚的層次聚類。 l按自頂向下層次分解，就稱為分裂的層次聚類。 13254600.012345612345凝聚的和分裂的層次聚類凝聚的和分裂的層次聚類 l凝聚的層次聚類采用自底向上的策略，開始時把每個對象作為一個單獨的簇，然后逐次對各個簇進行適當合并，直到滿足某個終止條件。 l分裂的層次聚類采用自頂向下的策略，與凝聚的層次聚類相反，開始時將所有

16、對象置于同一個簇中，然后逐次將簇分裂為更小的簇，直到滿足某個終止條件。l傳統(tǒng)的算法利用相似性或相異性的臨近度矩陣進行凝聚的或分裂的層次聚類。凝聚的和分裂的層次聚類凝聚的和分裂的層次聚類 a, b, c, d, e c, d, e d, e a, b e d c b a 第 4 步 第 3 步 第 2 步 第 1 步 第 0 步 凝聚的（AGENS） 第 0 步 第 1 步 第 2 步 第 3 步 第 4 步 分裂的（DIANA） 基本凝聚層次聚類方法基本凝聚層次聚類方法l凝聚層次聚類算法1.計算臨近度矩陣2.讓每個點作為一個cluster3.Repeat4.合并最近的兩個類5.更新臨近度矩陣，

17、以反映新的簇與原來的簇之間的臨近性6.Until 僅剩下一個簇 l關鍵的操作是two clusters的鄰近度計算不同的鄰近度的定義區(qū)分了各種不同的凝聚層次技術起始步驟起始步驟 lStart with clusters of individual points and a proximity matrixp1p3p5p4p2p1p2p3p4p5. . .Proximity Matrix中間步驟中間步驟l經(jīng)過部分融合之后 ，我們得到一些clusterC1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrix中間步驟中間步驟l我們希望合并兩個最鄰近的cluster

18、 (C2 and C5) 并更新臨近度矩陣C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrix最終合并最終合并l如何更新臨近度矩陣？ C1C4C2 U C5C3? ? ? ? ?C2 U C5C1C1C3C4C2 U C5C3C4Proximity Matrix如何定義如何定義cluster間的相似性間的相似性 p1p3p5p4p2p1p2p3p4p5. . .Similarity?lMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective

19、function Wards Method uses squared errorProximity Matrix p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective function Wards Method uses squared error如何定義如何定義cluster間的相似性間的相似性 p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAX

20、lGroup AveragelDistance Between CentroidslOther methods driven by an objective function Wards Method uses squared error如何定義如何定義cluster間的相似性間的相似性 p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between CentroidslOther methods driven by an objective function Wards Method uses

21、squared error如何定義如何定義cluster間的相似性間的相似性 p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixlMINlMAXlGroup AveragelDistance Between Centroidsl其它方法 Wards Method 利用平方誤差增量 如何定義如何定義cluster間的相似性間的相似性MIN or 單鏈單鏈 l兩個cluster的相似性定義為基于這兩個cluster中最大相似度（最近距離）l由一對最近鄰點決定I1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70

22、0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345分層聚類分層聚類: MIN單鏈聚類單鏈聚類單鏈樹狀圖單鏈樹狀圖1234561234536254100.0單鏈的優(yōu)勢單鏈的優(yōu)勢Original PointsTwo Clusters 單鏈技術可以處理非橢圓形狀的簇單鏈技術可以處理非橢圓形狀的簇單鏈的局限性單鏈的局限性Original PointsTwo Clusters但對噪音和離群點很敏感但對噪音和離群點很敏感Cluster Simil

23、arity: MAX or 全鏈全鏈兩個cluster的相似性定義為基于這兩個cluster中最小相似度（最大距離）I1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345分層聚類分層聚類: MAX 或全鏈或全鏈全鏈聚類全鏈聚類全鏈樹狀圖全鏈樹狀圖36412500.050.412345612534Original

24、 PointsTwo Clusters對噪音和離群不敏感對噪音和離群不敏感全鏈的優(yōu)勢全鏈的優(yōu)勢Original PointsTwo Clusters可能使大的簇破裂可能使大的簇破裂偏好球型簇偏好球型簇全鏈的局限性全鏈的局限性Cluster Similarity: 組平均組平均l兩個簇的鄰近度定義為不同的所有點對的平均逐對鄰近度，是一種單鏈與全鏈的折中算法.|Cluster|Cluster)p,pproximity()Cluster,Clusterproximity(jiClusterpClusterpjijijjiiI1I2I3I4I5I1 1.00 0.90 0.10 0.65 0.20I2

25、 0.90 1.00 0.70 0.60 0.50I3 0.10 0.70 1.00 0.40 0.30I4 0.65 0.60 0.40 1.00 0.80I5 0.20 0.50 0.30 0.80 1.0012345分層聚類分層聚類: Group AverageNested ClustersDendrogram36412500.00.2512345612534l優(yōu)勢 對噪音和極端值影響小l局限 偏好球型簇分層聚類分層聚類: Group Average其它近似度其它近似度lWard：兩個簇合并時導致的誤差平方和的增量l質心：簇質心之間的距離lLance-Willian

26、ms公式Cluster Similarity: Wards Methodl兩個簇的鄰近度定義為兩個簇合并時導致的平方誤差增量 當鄰近度取它們之間的平方時，ward與組平均類似 對噪音和極端值影響小l偏好球型簇Hierarchical Clustering: ComparisonGroup AverageWards Method12345612534MINMAX123456125341234561253412345612345優(yōu)點與缺點優(yōu)點與缺點l優(yōu)點：l某些應用領域需要層次結構。如：系統(tǒng)發(fā)生樹，基因芯片l有些研究表明，這種算法能夠產(chǎn)生較高質量的聚類l缺點：l計算量、存儲量大l對噪聲、高維數(shù)據(jù)敏

27、感DBSCAN算法算法lDBSCAN 是一種簡單、有效的基于密度的聚類算法.l基于中心的DBSCANl在基于中心的方法中，數(shù)據(jù)集中特定點的密度通過對該點Eps半徑之內的點計數(shù)（包括點本身）來估計l該方法實現(xiàn)簡單，但是點的密度依賴于指定的半徑。例如，如果半徑足夠大，則所有點的密度都等于數(shù)據(jù)集中的點數(shù)m。類似地，如果半徑太小，則所有點的密度都是1。DBSCAN: 核心點核心點, 邊界點邊界點, 噪聲點噪聲點DBSCAN 算法算法l將所有點標記為核心點、邊界點或噪聲點l刪除噪聲點l為距離在Eps之內的所有核心點之間賦予一條邊。l每組連通的核心點形成一個簇。l將每個邊界點指派到一個與之關聯(lián)的核心點的簇

28、中。DBSCAN: 選擇選擇 EPS and MinPtsl基本方法是觀察點到它的k個最近鄰的距離（稱為k-距離）的特性。l計算所有點的k-距離，以遞增次序將它們排序，然后繪制排序后的值，則我們預期會看到k-距離的急劇變化，對應于合適的Eps值。l如果我們選取該距離為Eps參數(shù)，而取k的值為MinPts參數(shù)。Original PointsPoint types: core, border and noiseEps = 10, MinPts = 4變密度的簇變密度的簇l如果簇的密度變化很大，DBSCAN可能會有問題?？紤]圖8-24，它包含4個埋藏在噪聲中的簇。l簇和噪聲區(qū)域的密度由它們的明暗度指

29、出。較密的兩個簇A和B周圍的噪聲的密度與簇C和D的密度相同。l如果Eps域值足夠低，使得DBSCAN可以發(fā)現(xiàn)簇C和D，則A、B和包圍它們的點將變成單個簇。l如果Eps域值足夠高，使得DBSCAN可以發(fā)現(xiàn)A和B，并且將包圍它們的點標記為噪聲，則C、D和包圍它們的點也將標記為噪聲。Original Points(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) Varying densities High-dimensional dataDBSCAN的優(yōu)點與缺點的優(yōu)點與缺點l因為DBSCAN使用簇的基于密度的定義，因此它是相對抗噪聲的，并且能夠處理任意形狀和大小的

30、簇。這樣，DBSCAN可以發(fā)現(xiàn)使用K均值不能發(fā)現(xiàn)的許多簇。l然而，正如前面所指出的，當簇的密度變化太大時，DBSCAN就會有麻煩。對于高維數(shù)據(jù)，它也有問題，因為對于這樣的數(shù)據(jù)，密度定義更困難。最后，當近鄰計算需要計算所有的點對近鄰度時，DBSCAN可能是開銷很大的。簇評估簇評估 l如何評估聚類結果的好壞？l為什么要評估聚類? To avoid finding patterns in noise To compare clustering algorithms To compare two sets of clusters To compare two clusters隨機數(shù)據(jù)的聚類結果隨機數(shù)據(jù)

31、的聚類結果00.81xyRandom Points00.81xyK-means00.81xyDBSCAN00.81xyComplete LinkMeasuring Cluster Validity Via CorrelationlCorrelation of incidence and prox

32、imity matrices for the K-means clusterings of the following two data sets. 00.81xy00.81xyCorr = -0.9235Corr = -0.5810lOrder the similarity matrix with respect to cluster labels and inspect visually. Using Similarity Matrix f

33、or Cluster Validation00.81xyPointsPoints20406080100102030405060708090100Similarity01Using Similarity Matrix for Cluster ValidationClusters in random data are not so crispPointsPoints20406080100102030405060708090100Similarity01DBSCAN00.81xyPointsPoint