第8章+聚類分析：基本概念和算法課件

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

2、間相似性 聚類結(jié)果的好壞取決于該聚類方法采用的相似性評(píng)估方法以及該方法的具體實(shí)現(xiàn)；聚類方法的好壞還取決于該方法是否能發(fā)現(xiàn)某些還是所有的隱含模式；什么是一個(gè)好的聚類方法?一個(gè)好的聚類方法要能產(chǎn)生高質(zhì)量的聚類聚類的復(fù)雜性How many clusters?Four Clusters Two Clusters Six Clusters 聚類的復(fù)雜性How many clusters?Four C不同的聚類類型劃分聚類（Partitional Clustering）層次聚類（Hierarchical Clustering）互斥（重疊）聚類（exclusive clustering）非互斥聚類（non-

3、exclusive）模糊聚類（fuzzy clustering）完全聚類（complete clustering）部分聚類（partial clustering）不同的聚類類型劃分聚類（Partitional Cluste劃分聚類（Partitional Clustering）Original PointsA Partitional Clustering劃分聚類簡(jiǎn)單地將數(shù)據(jù)對(duì)象集劃分成不重疊的子集，使得每個(gè)數(shù)據(jù)對(duì)象恰在一個(gè)子集。劃分聚類（Partitional Clustering）Or層次聚類（Hierarchical Clustering）Traditional Hierarchical

4、ClusteringNon-traditional Hierarchical ClusteringNon-traditional DendrogramTraditional Dendrogram層次聚類是嵌套簇的集族，組織成一棵樹(shù)。層次聚類（Hierarchical Clustering）T互斥的、重疊的、模糊的互斥的（Exclusive）每個(gè)對(duì)象都指派到單個(gè)簇.重疊的（overlapping）或非互斥的（non-exclusive）聚類用來(lái)反映一個(gè)對(duì)象.同時(shí)屬于多個(gè)組（類）這一事實(shí)。例如：在大學(xué)里，一個(gè)人可能既是學(xué)生，又是雇員模糊聚類（Fuzzy clustering ）每個(gè)對(duì)象以一個(gè)0（絕

5、對(duì)不屬于）和1（絕對(duì)屬于）之間的隸屬權(quán)值屬于每個(gè)簇。換言之，簇被視為模糊集。部分的（Partial） 部分聚類中數(shù)據(jù)集某些對(duì)象可能不屬于明確定義的組。如：一些對(duì)象可能是離群點(diǎn)、噪聲。完全的（complete）完全聚類將每個(gè)對(duì)象指派到一個(gè)簇。互斥的、重疊的、模糊的互斥的（Exclusive）不同的簇類型明顯分離的基于原型的基于圖的基于密度的概念簇不同的簇類型明顯分離的簇類型: 明顯分離的（Well-Separated）每個(gè)點(diǎn)到同簇中任一點(diǎn)的距離比到不同簇中所有點(diǎn)的距離更近。3 well-separated clusters簇類型: 明顯分離的（Well-Separated）每個(gè)點(diǎn)到簇類型:基于原

6、型的每個(gè)對(duì)象到定義該簇的原型的距離比到其他簇的原型的距離更近。對(duì)于具有連續(xù)屬性的數(shù)據(jù)，簇的原型通常是質(zhì)心，即簇中所有點(diǎn)的平均值。當(dāng)質(zhì)心沒(méi)有意義時(shí)，原型通常是中心點(diǎn)，即簇中最有代表性的點(diǎn)。基于中心的（ Center-Based）的簇：每個(gè)點(diǎn)到其簇中心的距離比到任何其他簇中心的距離更近。4 center-based clusters簇類型:基于原型的每個(gè)對(duì)象到定義該簇的原型的距離比到其他簇的簇類型:基于圖的如果數(shù)據(jù)用圖表示，其中節(jié)點(diǎn)是對(duì)象，而邊代表對(duì)象之間的聯(lián)系。簇可以定義為連通分支（connected component）：互相連通但不與組外對(duì)象連通的對(duì)象組?；诮彽模?Contiguity-

7、Based）：其中兩個(gè)對(duì)象是相連的，僅當(dāng)它們的距離在指定的范圍內(nèi)。這意味著，每個(gè)對(duì)象到該簇某個(gè)對(duì)象的距離比到不同簇中任意點(diǎn)的距離更近。8 contiguous clusters簇類型:基于圖的如果數(shù)據(jù)用圖表示，其中節(jié)點(diǎn)是對(duì)象，而邊代表對(duì)簇類型: 基于密度的（Density-Based）簇是對(duì)象的稠密區(qū)域，被低密度的區(qū)域環(huán)繞。6 density-based clusters簇類型: 基于密度的（Density-Based）簇是對(duì)象的簇類型: 概念簇（Conceptual Clusters）可以把簇定義為有某種共同性質(zhì)的對(duì)象的集合。例如：基于中心的聚類。還有一些簇的共同性質(zhì)需要更復(fù)雜的算法才能識(shí)別

8、出來(lái)。. 2 Overlapping Circles簇類型: 概念簇（Conceptual Clusters）可K均值聚類K均值聚類基本K均值算法1.選擇k個(gè)點(diǎn)作為初始的質(zhì)心2.repeat3. 將每個(gè)點(diǎn)指派到最近的質(zhì)心，形成k個(gè)簇4. 重新計(jì)算每個(gè)簇的質(zhì)心5.until 質(zhì)心不發(fā)生變化基本K均值算法1.選擇k個(gè)點(diǎn)作為初始的質(zhì)心數(shù)據(jù)對(duì)象之間的相異度Euclidean Distance 數(shù)據(jù)對(duì)象之間的相異度Euclidean Distance明可夫斯基距離（Minkowski Distance）Minkowski Distancer = 1. 城市塊 (曼哈頓, 出租車, L1 范數(shù)) 距離.

9、r = 2. 歐氏距離（ L2 范數(shù)）r . 上確界 (Lmax或L 范數(shù)) 距離. 明可夫斯基距離（Minkowski Distance）Min二元數(shù)據(jù)的相似性度量?jī)蓚€(gè)僅包含二元屬性的對(duì)象之間的相似性度量也稱相似系數(shù)兩個(gè)對(duì)象的比較導(dǎo)致四個(gè)量f00 = x取0并且y取0的屬性個(gè)數(shù)f01 = x取0并且y取1的屬性個(gè)數(shù)f10 = x取1并且y取0的屬性個(gè)數(shù)f11 = x取1并且y取1的屬性個(gè)數(shù)簡(jiǎn)單匹配系數(shù)SMC = 值匹配的屬性個(gè)數(shù) / 屬性個(gè)數(shù) = (f11 +f00) / (f01 + f10 + f11 + f00)Jaccard(雅卡爾 ) 系數(shù) （非對(duì)稱二元屬性）J = 匹配的個(gè)數(shù) /

10、 不涉及0-0匹配的屬性個(gè)數(shù)= (f11) / (f01 + f10 +f11) 二元數(shù)據(jù)的相似性度量?jī)蓚€(gè)僅包含二元屬性的對(duì)象之間的相似性度量余弦相似度 If d1 and d2 are two document vectors, then cos( x, y ) = (x y) / |x| |y| , Example: x = 3 2 0 5 0 0 0 2 0 0 y = 1 0 0 0 0 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+

11、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余弦相似度 If d1 and d2 are two doc誤差平方和（sum of the squared error，SSE）誤差平方和它可以度量聚類的質(zhì)量。誤差平方和越小，意味著質(zhì)心是簇中點(diǎn)的更好代表?？梢宰C明：當(dāng)緊鄰函數(shù)是歐式距離（L2）時(shí)，使簇的SSE最小的質(zhì)心是均值，即可以證明：當(dāng)緊鄰函數(shù)是曼哈頓距離（L1）

12、時(shí)，使簇的L1絕對(duì)誤差和（SAE）最小的質(zhì)心是中位數(shù)誤差平方和（sum of the squared error當(dāng)緊鄰函數(shù)是歐式距離時(shí)，可對(duì)SSE求導(dǎo)當(dāng)緊鄰函數(shù)是歐式距離時(shí)，可對(duì)SSE求導(dǎo)選擇初始的質(zhì)心隨機(jī)選擇從層次聚類中提取K個(gè)簇，并用這些簇的質(zhì)心作為初始質(zhì)心隨機(jī)選擇第一個(gè)點(diǎn)，或取所有點(diǎn)的質(zhì)心作為第一個(gè)點(diǎn)。然后，對(duì)于每個(gè)后繼初始質(zhì)心，選擇離已經(jīng)選取過(guò)的初始質(zhì)心最遠(yuǎn)的點(diǎn)二分K均值選擇初始的質(zhì)心隨機(jī)選擇第8章+聚類分析：基本概念和算法課件第8章+聚類分析：基本概念和算法課件第8章+聚類分析：基本概念和算法課件二分k均值二分k均值算法是基本k均值算法的直接k個(gè)簇。它將所有點(diǎn)的集合分裂成兩個(gè)簇，從這

13、些簇中選取一個(gè)繼續(xù)分裂，如此下去，直到產(chǎn)生k個(gè)簇二分k均值二分k均值算法是基本k均值算法的直接k個(gè)簇。二分k均值算法初始化簇表，使之包含由所有的點(diǎn)組成的簇。Repeat 從簇表中取出一個(gè)簇。 for i=1 to 實(shí)驗(yàn)次數(shù) do 使用基本k均值，二分選定的簇。 end for 從二分實(shí)驗(yàn)中選擇具有最小總sse的兩個(gè)簇。 將這兩個(gè)簇添加到簇表中。Until 簇表中包含k個(gè)簇。二分k均值算法初始化簇表，使之包含由所有的點(diǎn)組成的簇。K means 的優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)：算法簡(jiǎn)單適用于球形簇二分k均值等變種算法運(yùn)行良好，不受初始化問(wèn)題的影響。缺點(diǎn)：不能處理非球形簇、不同尺寸和不同密度的簇對(duì)離群點(diǎn)、噪聲敏感

14、K means 的優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)：K-means 的局限性K-means has problems when clusters are of differing Sizes大小Densities密度Non-globular shapes非球形K-means 的局限性K-means has probleLimitations of K-means: Differing SizesOriginal PointsK-means (3 Clusters)Limitations of K-means: DifferLimitations of K-means: Differing DensityOrig

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

16、K-means 局限性的克服Original PointsOvercoming K-means LimitationsOriginal PointsK-means ClustersOvercoming K-means LimitationsOvercoming K-means LimitationsOriginal PointsK-means ClustersOvercoming K-means Limitations層次聚類層次聚類按數(shù)據(jù)分層建立簇，形成一棵以簇為節(jié)點(diǎn)的樹(shù)，稱為聚類圖。 按自底向上層次分解，則稱為凝聚的層次聚類。 按自頂向下層次分解，就稱為分裂的層次聚類。 層次聚類層次聚類按

17、數(shù)據(jù)分層建立簇，形成一棵以簇為節(jié)點(diǎn)的樹(shù)，稱凝聚的和分裂的層次聚類 凝聚的層次聚類采用自底向上的策略，開(kāi)始時(shí)把每個(gè)對(duì)象作為一個(gè)單獨(dú)的簇，然后逐次對(duì)各個(gè)簇進(jìn)行適當(dāng)合并，直到滿足某個(gè)終止條件。 分裂的層次聚類采用自頂向下的策略，與凝聚的層次聚類相反，開(kāi)始時(shí)將所有對(duì)象置于同一個(gè)簇中，然后逐次將簇分裂為更小的簇，直到滿足某個(gè)終止條件。傳統(tǒng)的算法利用相似性或相異性的臨近度矩陣進(jìn)行凝聚的或分裂的層次聚類。凝聚的和分裂的層次聚類 凝聚的層次聚類采用自底向上的策略，開(kāi)凝聚的和分裂的層次聚類 凝聚的和分裂的層次聚類 基本凝聚層次聚類方法凝聚層次聚類算法計(jì)算臨近度矩陣讓每個(gè)點(diǎn)作為一個(gè)clusterRepeat合并最

18、近的兩個(gè)類更新臨近度矩陣，以反映新的簇與原來(lái)的簇之間的臨近性Until 僅剩下一個(gè)簇 關(guān)鍵的操作是two clusters的鄰近度計(jì)算不同的鄰近度的定義區(qū)分了各種不同的凝聚層次技術(shù)基本凝聚層次聚類方法起始步驟 Start with clusters of individual points and a proximity matrixp1p3p5p4p2p1p2p3p4p5. . .Proximity Matrix起始步驟 Start with clusters of in中間步驟經(jīng)過(guò)部分融合之后 ，我們得到一些clusterC1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Prox

19、imity Matrix中間步驟經(jīng)過(guò)部分融合之后 ，我們得到一些clusterC1C中間步驟我們希望合并兩個(gè)最鄰近的cluster (C2 and C5) 并更新臨近度矩陣C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5Proximity Matrix中間步驟我們希望合并兩個(gè)最鄰近的cluster (C2 an最終合并如何更新臨近度矩陣？ C1C4C2 U C5C3? ? ? ? ?C2 U C5C1C1C3C4C2 U C5C3C4Proximity Matrix最終合并如何更新臨近度矩陣？ C1C4C2 U C5C3? 如何定義cluster間的相似性 p1p3p5p4p2p1

20、p2p3p4p5. . .Similarity?MINMAXGroup AverageDistance Between CentroidsOther methods driven by an objective functionWards Method uses squared errorProximity Matrix如何定義cluster間的相似性 p1p3p5p4p2p1p p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixMINMAXGroup AverageDistance Between CentroidsOther methods driven b

21、y an objective functionWards Method uses squared error如何定義cluster間的相似性 p1p3p5p4p2p1p2p3p4p5. . .Pro p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixMINMAXGroup AverageDistance Between CentroidsOther methods driven by an objective functionWards Method uses squared error如何定義cluster間的相似性 p1p3p5p4p2p1p2p3p4p5.

22、 . .Pro p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixMINMAXGroup AverageDistance Between CentroidsOther methods driven by an objective functionWards Method uses squared error如何定義cluster間的相似性 p1p3p5p4p2p1p2p3p4p5. . .Pro p1p3p5p4p2p1p2p3p4p5. . .Proximity MatrixMINMAXGroup AverageDistance Between Centroi

23、ds其它方法Wards Method 利用平方誤差增量如何定義cluster間的相似性 p1p3p5p4p2p1p2p3p4p5. . .ProMIN or 單鏈 兩個(gè)cluster的相似性定義為基于這兩個(gè)cluster中最大相似度（最近距離）由一對(duì)最近鄰點(diǎn)決定12345MIN or 單鏈 兩個(gè)cluster的相似性定義為基于這兩分層聚類: MIN單鏈聚類單鏈樹(shù)狀圖12345612345分層聚類: MIN單鏈聚類單鏈樹(shù)狀圖12345612345單鏈的優(yōu)勢(shì)Original PointsTwo Clusters 單鏈技術(shù)可以處理非橢圓形狀的簇單鏈的優(yōu)勢(shì)Original PointsTwo Clus

24、te單鏈的局限性O(shè)riginal PointsTwo Clusters但對(duì)噪音和離群點(diǎn)很敏感單鏈的局限性O(shè)riginal PointsTwo ClustCluster Similarity: MAX or 全鏈兩個(gè)cluster的相似性定義為基于這兩個(gè)cluster中最小相似度（最大距離）12345Cluster Similarity: MAX or 全鏈兩分層聚類: MAX 或全鏈全鏈聚類全鏈樹(shù)狀圖12345612534分層聚類: MAX 或全鏈全鏈聚類全鏈樹(shù)狀圖12345612Original PointsTwo Clusters對(duì)噪音和離群不敏感全鏈的優(yōu)勢(shì)Original PointsT

25、wo Clusters對(duì)噪音Original PointsTwo Clusters可能使大的簇破裂偏好球型簇全鏈的局限性O(shè)riginal PointsTwo Clusters可能使Cluster Similarity: 組平均兩個(gè)簇的鄰近度定義為不同的所有點(diǎn)對(duì)的平均逐對(duì)鄰近度，是一種單鏈與全鏈的折中算法.12345Cluster Similarity: 組平均兩個(gè)簇的鄰近度分層聚類: Group AverageNested ClustersDendrogram12345612534分層聚類: Group AverageNested Clus優(yōu)勢(shì)對(duì)噪音和極端值影響小局限偏好球型簇分層聚類: Gr

26、oup Average分層聚類: Group Average其它近似度Ward：兩個(gè)簇合并時(shí)導(dǎo)致的誤差平方和的增量質(zhì)心：簇質(zhì)心之間的距離Lance-Willianms公式其它近似度Ward：兩個(gè)簇合并時(shí)導(dǎo)致的誤差平方和的增量Cluster Similarity: Wards Method兩個(gè)簇的鄰近度定義為兩個(gè)簇合并時(shí)導(dǎo)致的平方誤差增量當(dāng)鄰近度取它們之間的平方時(shí)，ward與組平均類似對(duì)噪音和極端值影響小偏好球型簇Cluster Similarity: Wards MetHierarchical Clustering: ComparisonGroup AverageWards Method123

27、45612534MINMAX123456125341234561253412345612345Hierarchical Clustering: Compa優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)：某些應(yīng)用領(lǐng)域需要層次結(jié)構(gòu)。如：系統(tǒng)發(fā)生樹(shù)，基因芯片有些研究表明，這種算法能夠產(chǎn)生較高質(zhì)量的聚類缺點(diǎn)：計(jì)算量、存儲(chǔ)量大對(duì)噪聲、高維數(shù)據(jù)敏感優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)：DBSCAN算法DBSCAN 是一種簡(jiǎn)單、有效的基于密度的聚類算法.基于中心的DBSCAN在基于中心的方法中，數(shù)據(jù)集中特定點(diǎn)的密度通過(guò)對(duì)該點(diǎn)Eps半徑之內(nèi)的點(diǎn)計(jì)數(shù)（包括點(diǎn)本身）來(lái)估計(jì)該方法實(shí)現(xiàn)簡(jiǎn)單，但是點(diǎn)的密度依賴于指定的半徑。例如，如果半徑足夠大，則所有點(diǎn)的密度都等于數(shù)據(jù)集中

28、的點(diǎn)數(shù)m。類似地，如果半徑太小，則所有點(diǎn)的密度都是1。DBSCAN算法DBSCAN 是一種簡(jiǎn)單、有效的基于密度的聚第8章+聚類分析：基本概念和算法課件DBSCAN: 核心點(diǎn), 邊界點(diǎn), 噪聲點(diǎn)DBSCAN: 核心點(diǎn), 邊界點(diǎn), 噪聲點(diǎn)DBSCAN 算法將所有點(diǎn)標(biāo)記為核心點(diǎn)、邊界點(diǎn)或噪聲點(diǎn)刪除噪聲點(diǎn)為距離在Eps之內(nèi)的所有核心點(diǎn)之間賦予一條邊。每組連通的核心點(diǎn)形成一個(gè)簇。將每個(gè)邊界點(diǎn)指派到一個(gè)與之關(guān)聯(lián)的核心點(diǎn)的簇中。DBSCAN 算法將所有點(diǎn)標(biāo)記為核心點(diǎn)、邊界點(diǎn)或噪聲點(diǎn)DBSCAN: 選擇 EPS and MinPts基本方法是觀察點(diǎn)到它的k個(gè)最近鄰的距離（稱為k-距離）的特性。計(jì)算所有點(diǎn)的k-

29、距離，以遞增次序?qū)⑺鼈兣判?，然后繪制排序后的值，則我們預(yù)期會(huì)看到k-距離的急劇變化，對(duì)應(yīng)于合適的Eps值。如果我們選取該距離為Eps參數(shù)，而取k的值為MinPts參數(shù)。DBSCAN: 選擇 EPS and MinPts基本方法是Original PointsPoint types: core, border and noiseEps = 10, MinPts = 4Original PointsPoint types: co變密度的簇如果簇的密度變化很大，DBSCAN可能會(huì)有問(wèn)題。考慮圖8-24，它包含4個(gè)埋藏在噪聲中的簇。簇和噪聲區(qū)域的密度由它們的明暗度指出。較密的兩個(gè)簇A和B周圍的噪聲的密

30、度與簇C和D的密度相同。如果Eps域值足夠低，使得DBSCAN可以發(fā)現(xiàn)簇C和D，則A、B和包圍它們的點(diǎn)將變成單個(gè)簇。如果Eps域值足夠高，使得DBSCAN可以發(fā)現(xiàn)A和B，并且將包圍它們的點(diǎn)標(biāo)記為噪聲，則C、D和包圍它們的點(diǎn)也將標(biāo)記為噪聲。變密度的簇如果簇的密度變化很大，DBSCAN可能會(huì)有問(wèn)題。考第8章+聚類分析：基本概念和算法課件Original Points(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) Varying densities High-dimensional dataOriginal Points(MinPts=4, Eps=DBSCAN

31、的優(yōu)點(diǎn)與缺點(diǎn)因?yàn)镈BSCAN使用簇的基于密度的定義，因此它是相對(duì)抗噪聲的，并且能夠處理任意形狀和大小的簇。這樣，DBSCAN可以發(fā)現(xiàn)使用K均值不能發(fā)現(xiàn)的許多簇。然而，正如前面所指出的，當(dāng)簇的密度變化太大時(shí)，DBSCAN就會(huì)有麻煩。對(duì)于高維數(shù)據(jù)，它也有問(wèn)題，因?yàn)閷?duì)于這樣的數(shù)據(jù)，密度定義更困難。最后，當(dāng)近鄰計(jì)算需要計(jì)算所有的點(diǎn)對(duì)近鄰度時(shí)，DBSCAN可能是開(kāi)銷很大的。DBSCAN的優(yōu)點(diǎn)與缺點(diǎn)因?yàn)镈BSCAN使用簇的基于密度的定簇評(píng)估 如何評(píng)估聚類結(jié)果的好壞？為什么要評(píng)估聚類?To avoid finding patterns in noiseTo compare clustering algorithmsTo compare two sets of clustersTo compare two clusters簇評(píng)估 隨機(jī)數(shù)據(jù)的聚類結(jié)果Random PointsK-meansDBSCANComplete Link隨機(jī)數(shù)據(jù)的聚類結(jié)果Random PointsK-meansDMeasuring Cluster Validity Via CorrelationCorrelation of incidence and proximity matrices for the K-means clusterings of the following two data sets. Corr = -0