《數(shù)據(jù)挖掘導論完整版中》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)挖掘導論完整版中（109頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、Click to edit Master title style,,Click to edit Master text styles,,Second Level,,Third Level,,聚類分析：附加的問題與算法,第,9,章,,,聚類分析：附加的問題與算法,,,,,在各種領域，針對不同的應用類型，已經(jīng)開發(fā)了大量聚類算法。在這些算法中沒有一種算法能夠適應所有的數(shù)據(jù)類型、簇和應用。,,事實上，對于更加有效或者更適合特定數(shù)據(jù)類型、簇和應用的新的聚類算法，看來總是有進一步的開發(fā)空間。,,我們只能說我們已經(jīng)有了一些技術，對于某些情況運行良好。其原因是，在許多情況下，對于什么是一個好的簇集，仍然憑主觀

2、解釋。此外，當使用客觀度量精確地定義簇時，發(fā)現(xiàn)最優(yōu)聚類問題常常是計算不可行的。,比較,k,均值和,DBSCAN,DBSCAN,和,k,均值都是將每個對象指派到單個簇的劃分聚類算法，但是,K,均值一般聚類所有對象，而,DBSCAN,丟棄被它識別為噪聲的對象。,,K,均值使用簇的基于原形的概念，而,DBSCAN,使用基于密度的概念。,,DBSCAN,可以處理不同大小和不同形狀的簇，并且不太受噪聲和離群點的影響。,K,均值很難處理非球狀的簇和不同大小的簇。當簇具有很不同的密度時，兩種算法的性能都很差。,,,K,均值只能用于具有明確定義的質心（如均值或中位數(shù)）的數(shù)據(jù)。,DBSCAN,要求密度定義（基于

3、傳統(tǒng)的歐幾里得密度概念）對于數(shù)據(jù)是有意義的。,,K,均值可以用于稀疏的高維數(shù)據(jù)，如文檔數(shù)據(jù)，,DBSCAN,通常在這類數(shù)據(jù)上性能很差，因為對于高維數(shù)據(jù)，傳統(tǒng)的歐幾里得密度定義不能很好處理。,,K,均值和,DBSCAN,的最初版本都是針對歐幾里得數(shù)據(jù)設計的，但是它們都被擴展，以便處理其他類型的數(shù)據(jù)。,,,DBSCAN,不對數(shù)據(jù)的分布做任何假定。基本,k,均值算法等價于一種統(tǒng)計聚類方法（混合模型），假定所有的簇都來自球形高斯分布，具有不同的均值，但具有相同的斜方差矩陣。,,DBSCAN,和,k,均值都尋找使用所有屬性的簇，即它們都不尋找可能只涉及某個屬性子集的簇。,,K,均值可以發(fā)現(xiàn)不是明顯分離的

4、簇，即便簇有重疊也可以發(fā)現(xiàn)，但是,DBSCAN,會合并有重疊的簇。,,K,均值算法的時間復雜度是,O,（,m,），而,DBSCAN,的時間復雜度是,O,（,m2,）,.,,DBSCAN,多次運行產(chǎn)生相同的結果，而,k,均值通常使用隨機初始化質心，不會產(chǎn)生相同的結果。,,DBSCAN,自動地確定簇個數(shù)；對于,k,均值，簇個數(shù)需要作為參數(shù)指定。然而，,DBSCAN,必須指定另外兩個參數(shù)：,Eps,和,Minpts,,K,均值聚類可以看作優(yōu)化問題，即最小化每個點到最近的質心的誤差的平方和，并且可以看作一種統(tǒng)計聚類的特例。,DBSCAN,不基于任何形式化模型。,,數(shù)據(jù)特性,高維性,,隨著維度的增加，體

5、積迅速增加，除非點的個數(shù)也隨著維度指數(shù)增加，否則密度將趨向于,0.,,處理該問題的方法是使用維歸約技術,,規(guī)模,,許多聚類算法對于小規(guī)模和中等規(guī)模的數(shù)據(jù)集運行良好，但是不能處理大型數(shù)據(jù)集,,稀疏性,,稀疏數(shù)據(jù)通常由非對稱的屬性組成，其中零值沒有非零值重要。,.,,,噪聲和離群點,,非常見點可能嚴重地降低聚類算法的性能，特別是,k,均值這樣的基于原型的算法,,另一方面，噪聲也可能導致單鏈等技術合并兩個不應當合并的簇。,,屬性和數(shù)據(jù)集類型,,屬性可能是分類的（標稱的或序數(shù)的）或定量的（區(qū)間的或比率的），二元的、離散的或連續(xù)的。,,不同的近鄰性和密度度量適合于不同類型的數(shù)據(jù)。,,尺度,,不同的屬性，

6、如高度和重量，可能用不同的尺度度量。這些差別可能嚴重影響兩個對象之間的距離或相似性，從而影響聚類分析的結果。,簇特性,數(shù)據(jù)分布,,某些聚類技術假定數(shù)據(jù)具有特定的分布。更具體的說，它們常常假定可以用混合分布對數(shù)據(jù)建模，其中每個簇對應于一個分布。,,形狀,,有些簇具有規(guī)則的形狀，如矩形和球形。但是，更一般地，簇可以具有任意形狀。,,如,DBSCAN,和單鏈等技術可以處理任意形狀。基于原型的方法和一些層次聚類技術不能進行這樣的處理。,,Chameleon,和,cure,是專門用來處理這一問題的技術,,,不同大小,,許多聚類算法，如,k,均值，當簇具有不同的大小時不能很好的處理,,不同密度,,具有很不

7、相同的密度的簇可能對諸如,DBSCAN,和,k,均值等算法造成影響,,基于,SNN,密度的聚類技術可以處理這個問題,,無明顯分離的簇,,當簇接觸或重疊時，有些聚類技術將應當分開的簇合并。甚至有些發(fā)現(xiàn)不同簇的技術隨意地將點指派到一個或另一個簇。,,模糊聚類可以處理這一問題,,,簇之間的聯(lián)系,,在大部分聚類技術中，都不考慮簇之間的聯(lián)系，如簇的相對位置,,自組織映射（,SOM,）是一種在聚類期間直接考慮簇之間聯(lián)系的聚類技術。,,子空間簇,,簇可能只在維（屬性）的一個子集中存在，并且使用一個維集合確定的簇可能也使用另一個維確定的簇很不相同。,,聚類算法的一般特征,次序依賴性,,對于某些算法，所產(chǎn)生的簇

8、的質量和個數(shù)可能因數(shù)據(jù)處理的次序不同而顯著地變化。如,SOM,,非確定性,,有些算法不是次序依賴的，但是它們每次運行都產(chǎn)生不同的結果，因為它們依賴于需要隨機選擇的初始化步驟。,,變換聚類問題到其他領域,,將聚類問題映射到一個不同的領域。如，基于圖的聚類,,,,可伸縮性,,包含數(shù)以百萬計對象的數(shù)據(jù)集并不罕見，而用于這種數(shù)據(jù)集的聚類算法應當具有線性或接近線性的時間或空間復雜度。,,對于大型數(shù)據(jù)集，即使具有,O(m2),復雜度也是不切實際的。,,此外，數(shù)據(jù)集聚類技術不能總是假定數(shù)據(jù)放在內存，或者數(shù)據(jù)元素可以隨機的訪問。這樣的算法對于大型數(shù)據(jù)集是不可行的。,,參數(shù)選擇,,大部分聚類算法需要用戶設置一個

9、或多個參數(shù)。選擇合適的參數(shù)值可能是困難的；因此，通常的態(tài)度是“參數(shù)越少越好”。,,,將聚類作為最優(yōu)化問題處理,,聚類常常被看作優(yōu)化問題。將點劃分成簇，根據(jù)用戶指定的目標函數(shù)度量，最大化結果簇集合的優(yōu)良度。如,k,均值試圖發(fā)現(xiàn)簇的集合，使得每個點到最近的簇質心距離的平方和最小。,,基于原型的聚類,模糊聚類,,,使用混合模型的聚類,,,自組織映射,模糊聚類,模糊集合,,1965,年，,Lotfi Zadeh,引進模糊集合論（,fuzzy set theory,）和模糊邏輯（,fuzzy logic,）作為一種處理不精確和不確定性的方法。,,簡要的說，模糊集合論允許對象以,0,和,1,之間的某個隸屬

10、度屬于一個集合，而模糊邏輯允許一個陳述以,0,和,1,之間的確定度為真。,,傳統(tǒng)的集合論和邏輯是對應的模糊集合論和模糊邏輯的特殊情況，它們限制集合的隸屬度或確定度或者為,0,，或者為,1.,,考慮如下模糊邏輯的例子,,陳述“天空多云”為真的程度可以定義為天空被云覆蓋的百分比。例如，天空的,50%,被云覆蓋，則“天空多云”為真的程度是,0.5,。,,如果我們有兩個集合“多云天”和“非多云天”，則我們可以類似地賦予每一天隸屬于這兩個集合的程度。,,這樣，如果一天,25%,多云，則它在“多云天”集合中具有,0.25,的隸屬度，而在“非多云天”集合中具有,0.75,的隸屬度。,,模糊簇,,假定我們有一

11、個數(shù)據(jù)點的集合,X={x1,x2,…,xm},，其中每個點,xi,是一個,n,維點，即,xi=,（,xi1,xi2,…,xin),。模糊簇集,C1,C2,…,Ck,是,X,的所有可能模糊子集的一個子集。,,這簡單地意味著對于每個點,xi,和每個簇,Cj,，隸屬權值（度）,wij,已經(jīng)賦予,0,和,1,之間的值。,,然而，我們還想將以下合理的條件施加在簇上，以確定簇形成模糊偽劃分（,fuzzy psuedo-partition,）。,,給定點,xi,的所有權值之和為,1,：,,,,,每個簇,Cj,以非零權值至少包含一個點，但不以權值,1,包含所有的點,,,盡管存在多種模糊聚類，我們只考慮,k,均

12、值的模糊版本，稱作模糊,c,均值。,,在聚類文獻中，那些不采用簇質心增量更新方法的,k,均值版本有時稱為,c,均值。模糊,c,均值算法有時稱為,FCM,,算法,9.1,基本模糊,c,均值算法,,選擇一個初始模糊偽劃分，即對所有的,wij,賦值,,Repeat,,,使用模糊偽劃分，計算每個簇的質心,,重新計算模糊偽劃分，即,wij,,Until,質心不發(fā)生變化,,FCM,的結構類似于,K,均值。,K,均值可以看作,FCM,的特例。,,K,均值在初始化之后，交替地更新質心和指派每個對象到最近的質心。具體地說，計算模糊偽劃分等價于指派步驟。,,與,k,均值一樣，,FCM,可以解釋為試圖最小化誤差的平

13、方和（,SSE,），盡管,FCM,基于,SSE,的模糊版本。,,,計算,SSE,,公式：,,,其中,cj,是第,j,個簇的質心，而,p,是確定權值影響的指數(shù)，在,1,和,∞,之間取值,,初始化,,通常使用隨機初始化。特殊地，權值隨機的選取，同時限制與任何對象相關聯(lián)的權值之和等于,1,。,,計算質心,,,公式：,,,,模糊質心的定義類似于傳統(tǒng)的質心定義，不同之處在于所有點都考慮，并且每個點對質心的貢獻要根據(jù)它的隸屬度加權。,,,,更新模糊偽劃分,,,,公式,:,,,,如果,p>2,，則該指數(shù)降低賦予離點最近的簇的權值。事實上，隨著,p,趨向于無窮大，該指數(shù)趨向于,0,，而權值趨向于,1/k,。,

14、,另一方面，隨著,p,趨向于,1,，該指數(shù)加大賦予離點最近的簇的權值。隨著,p,趨向于,1,，關于最近簇的隸屬權值趨向于,1,，而關于其他簇的隸屬權值趨向于,0,。這時對應于,k,均值。,,例子：三個圓形簇上的模糊,c,均值,優(yōu)點與局限性,FCM,產(chǎn)生指示任意點屬于任意簇的程度的聚類。,,它比,K,均值算法計算復雜性高。,,除此之外，它與,k,均值算法具有相同的優(yōu)點和缺點。,基于原型的聚類,模糊聚類,,,使用混合模型的聚類,,,自組織映射,使用混合模型的聚類,基于統(tǒng)計模型的聚類。通常，假定數(shù)據(jù)是由一個統(tǒng)計過程產(chǎn)生的，并且通過找出最佳擬合數(shù)據(jù)的統(tǒng)計模型來描述數(shù)據(jù)，其中統(tǒng)計模型用分布和該分布的一組

15、參數(shù)描述。,,混合模型（,mixture models,）：它使用若干統(tǒng)計分布對數(shù)據(jù)建模。每個分布對應于一個簇，而每個分布的參數(shù)提供對應于簇的描述，通常用中心和發(fā)散描述。,,算法,估計數(shù)據(jù)分布：,,確定分布：一般假設數(shù)據(jù)取自高斯混合分布。然后，對分布的參數(shù)進行估計：利用,EM,算法進行最大似然估計,,利用直方圖估計分布,,對分布進行劃分、分離。每個分布對應于一個簇。,,,,優(yōu)點和缺點,混合模型比,k,均值或模糊,c,均值更一般，因為它可以使用各種類型的分布。,,利用簡單的估計分布的方法（如直方圖）可能會錯誤估計數(shù)據(jù)的原始分布，導致結果不好。,,利用復雜的方法（如,EM,算法），計算復雜性會大大

16、增加。,基于原型的聚類,模糊聚類,,,使用混合模型的聚類,,,自組織映射,自組織映射,Kohonen,自組織特征映射（,SOFM,或,SOM,）是一種基于神經(jīng)網(wǎng)絡觀點的聚類和數(shù)據(jù)可視化技術。,,盡管,SOM,源于神經(jīng)網(wǎng)絡，但是它可以表示成一種基于原形的聚類的變形。,,與其他基于質心的聚類技術一樣，,SOM,的目標是發(fā)現(xiàn)質心的集合，并將數(shù)據(jù)集中的每個對象指派到提供該對象最佳近似的質心。用神經(jīng)網(wǎng)絡的術語，每個質心都與一個神經(jīng)元相關聯(lián)。,SOM,算法,初始化質心。,,Repeat,,,選擇下一個對象,,,確定到該對象最近的質心,,,更新該質心和附近的質心，即在一個特定鄰域,,內的質心,,Until,

17、質心改變不多或超過某個域值,,指派每個對象到最近的質心，并返回質心和簇,基于密度的聚類,基于網(wǎng)格的聚類,,,子空間聚類,,,DENCLUE,基于網(wǎng)格的聚類,網(wǎng)格是一種組織數(shù)據(jù)集的有效方法，至少在低維空間中如此。,,其基本思想是，將每個屬性的可能值分割成許多相鄰的區(qū)間，創(chuàng)建網(wǎng)格單元的集合。每個對象落入一個網(wǎng)格單元，網(wǎng)格單元對應的屬性區(qū)間包含該對象的值。,,存在許多利用網(wǎng)格進行聚類的方法，大部分方法是基于密度的。,例子,基于網(wǎng)格的算法,定義一個網(wǎng)格單元集,,將對象指派到合適的單元，并計算每個單元的密度,,刪除密度低于指定的閾值的單元,,由鄰近的稠密單元組形成簇,,定義網(wǎng)格單元,,對于連續(xù)屬性，定義

18、網(wǎng)格單元相當于連續(xù)屬性離散化?？蓪⒅祫澐譃榈葘挼膮^(qū)間、等頻的區(qū)間、使用聚類確定的區(qū)間。,,網(wǎng)格單元的密度,,定義網(wǎng)格單元密度的自然方法是：定義網(wǎng)格單元的密度為該區(qū)域中的點數(shù)除以區(qū)域的體積。,,如果使用具有相同體積的網(wǎng)格單元，使得每個單元的點數(shù)直接度量單元的密度。,,,鄰近的稠密單元組形成簇,,密度閾值的設定是關鍵。如圖,9-10,和表,9-2,，如果密度閾值為,9,，則大簇的,4,個部分將丟失。,,鄰近單元？一個二維網(wǎng)格單元有,4,個還是,8,個鄰接單元？,例子,優(yōu)點與局限性,算法運行速度較快，可達,o(mlogm),。這使得它成為許多聚類算法的基礎，如,STING,、,GRIDCLUS,、,

19、waveCluster,、,Bang-Clustering,、,CLIQUE,和,MAFIA,。,,網(wǎng)格單元形狀選擇影響聚類效果。如矩形網(wǎng)格單元不能準確地捕獲圓形邊界區(qū)域的密度。,,對于高維數(shù)據(jù)，基于網(wǎng)格的聚類效果較差。,,密度閾值的選擇對算法效果影響較大。,,基于密度的聚類,基于網(wǎng)格的聚類,,,子空間聚類,,,DENCLUE,,迄今為止，所考慮的聚類技術都是使用所有的屬性來發(fā)現(xiàn)簇。然而，如果僅考慮特征子集，則我們發(fā)現(xiàn)的簇可能因子空間不同而很不相同。,,有兩個理由，子空間的簇可能是有趣的。,,數(shù)據(jù)關于少量屬性的集合可能可以聚類，而關于其余屬性是隨機分布的。,,在某些情況下，在不同的維集合中存在

20、不同的簇。,,例子：考慮記錄不同時間、不同商品銷售情況的數(shù)據(jù)集（時間是維，商品是對象）。某些商品對于特定的月份集（如夏天）可能表現(xiàn)出類似行為，但是不同的簇可能被不同的月份（維）刻畫。,,,CLIQUE,算法,CLIQUE,（,Clustering In QUEst,）是系統(tǒng)地發(fā)現(xiàn)子空間簇的基于網(wǎng)格的聚類算法。檢查每個子空間尋找簇是不現(xiàn)實的，因為這樣的子空間的數(shù)量是維度的指數(shù)。,,基于密度的簇的單調性：如果一個點集在,k,維上形成一個基于密度的簇，則相同的點集在這些維的所有可能的子集上也是基于密度的簇的一部分。,CLIQUE,算法,找出對應于每個屬性的一維空間中的所有稠密區(qū)域。這是稠密的一維單元

21、的集合。,,K,?2,,Repeat,,,由稠密的,k-1,維單元產(chǎn)生所有的候選稠密,k,維單元,,,刪除點數(shù)少于域值的單元,,k?k+1,,Until,不存在候選稠密,k,維單元,,通過取所有鄰接的、高密度的單元的并發(fā)現(xiàn)簇,,使用一小組描述簇中單元的屬性值域的不等式概括每一個簇。,CLIQUE,的優(yōu)點與局限性,CLIQUE,最大特點是，它提供了一種搜索子空間發(fā)現(xiàn)簇的有效技術。由于這種方法基于關聯(lián)分析的先驗原理，它的性質能夠被很好地解釋。,,CLIQUE,能夠用一小組不等式概括構成一個簇的單元列表。,,CLIQUE,的局限性與其他基于密度的方法和,Apriori,算法相同。如，,CLIQUE,

22、發(fā)現(xiàn)的簇可以共享對象。允許簇重疊可能大幅度增加簇的個數(shù)，并使得解釋更加困難。,Apriori,具有指數(shù)級的復雜度。,基于密度的聚類,基于網(wǎng)格的聚類,,,子空間聚類,,,DENCLUE,DENCLUE,：基于密度聚類的一種基于核的方案,DENCLUE(DENsity CLUstEring),是一種基于密度的聚類方法，它用與每個點相關聯(lián)的影響函數(shù)之和對點集的總密度建模。結果總密度函數(shù)將具有局部尖峰，并且這些局部尖峰用來以自然的方式定義簇。,,具體的說，對于每個數(shù)據(jù)點，一個爬山過程找出與該點相關聯(lián)的最近的尖峰，并且與一個特定的尖峰（稱作局部密度吸引點（,local density attractor

23、,））相關聯(lián)的所有數(shù)據(jù)點成為一個簇。,,如果局部尖峰處的密度太低，則相關聯(lián)的簇中的點將被視為噪聲而丟棄。,,如果一個局部尖峰通過一條數(shù)據(jù)點路徑與另一個局部尖峰相連接，并且該路徑上每個點的密度都高于最小密度閾值，則與這些局部尖峰相關聯(lián)的簇合并在一起。,,DENCLUE,算法,對數(shù)據(jù)點占據(jù)的空間推導密度函數(shù),,識別局部最大點（即密度吸引點）,,通過沿密度增長最大的方向移動，將每個點關聯(lián)到一個密度吸引點,,定義與特定的密度吸引點相關聯(lián)的點構成的簇,,丟棄密度吸引點的密度小于用戶指定閾值的簇,,合并通過密度大于或等于閾值的點路徑連接的簇,,核密度估計,核密度估計用函數(shù)描述數(shù)據(jù)的分布。每個點對總密度函數(shù)

24、的貢獻用一個核函數(shù)表示?？偯芏群瘮?shù)僅僅是與每個點相關聯(lián)的核函數(shù)之核,,核函數(shù)是對稱的，并且它的值隨到點的距離增加而下降。高斯函數(shù)常常用作核函數(shù)：,,DENCLUE,的優(yōu)點與局限性,DENCLUE,具有堅實的理論基礎，因為它基于統(tǒng)計學發(fā)展完善的領域,-----,核密度函數(shù)和核密度估計。因此，,DENCLUE,提供了比其他基于網(wǎng)絡的聚類技術和,DBSCAN,更加靈活、更加精確的計算密度的方法。（,DBSCAN,是,DENCLUE,的特例）,,基于核密度函數(shù)的方法本質上是計算昂貴的，但,DENCLUE,使用基于網(wǎng)格的技術來處理該問題。盡管如此，,DENCLUE,可能比其他基于密度的聚類技術的計算開銷

25、更大。,,DENCLUE,具有其他基于密度的方法的優(yōu)缺點。,,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,稀疏化,m,個數(shù)據(jù)點的,m×m,鄰近度矩陣可以用一個稠密圖表示，每個節(jié)點與其他所有點相連，權值反映鄰近性。,,盡管每個對象與其他每個對象都有某種程度的近鄰性，但是對于大部分數(shù)據(jù)集，對象只與少量對象高度相似，而與大部分其他對象的相似性很弱。這一性質用來稀疏化鄰近度圖。,,稀疏化可以這樣進行：斷開相似度低于指定閾值的邊、或僅保留連接到點的,k,個近鄰的邊。,稀疏化的好處,壓縮了數(shù)據(jù)量,,可以更好的聚

26、類,,稀疏化技術保持了對象與最近鄰的連接，斷開與較遠對象的連接。這與最近鄰原理一致，對象的最近鄰趨向于與對象在同一個類。這降低了噪聲和離群點的影響，增強了簇之間的差別。,,可以使用圖劃分算法,,應當把鄰近度圖的稀疏化看成使用實際聚類算法之前的初始化步驟。,,理論上講，一個完美的稀疏化應當將鄰近度圖劃分成對應于期望簇的連通分支，但實際中這很難做到。很容易出現(xiàn)單條邊連接兩個簇，或者單個簇被分裂成若干個不相連接的子簇的情況。,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,最小生成樹聚類（,minimum s

27、panning tree,，,MST,）,計算相異度圖的最小生成樹,,Repeat,,,斷開對應于最大相異度的邊，創(chuàng)建一個新的簇,,Until,只剩下單個簇,,,最小生成樹聚類是一種基于分裂的層次聚類算法,,最小生成樹聚類可以看作用稀疏化找出簇的方法,,,,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,OPOSSUM,：使用,METIS,的稀疏相似度最優(yōu)劃分,OPOSSUM,（,Optimal Partitioning of Sparse Similarities Using METIS,）是一種專門

28、為諸如文檔或購物籃數(shù)據(jù)等稀疏、高維數(shù)據(jù)設計的聚類技術。與,MST,一樣，它基于鄰近度圖的稀疏化進行聚類。然而，,OPOSSUM,使用,METIS,算法，該算法是專門為劃分圖設計的。,,OPOSSUM,聚類算法,,1,：計算稀疏化的相似度圖,,2,：使用,METIS,，將相似度圖劃分成,k,個不同的分支（簇）,,所使用的相似性度量是適合于稀疏、高維數(shù)據(jù)的度量，如擴充的,Jaccard,度量或余弦度量。,,METIS,圖劃分程序將稀疏圖劃分為,k,個不同的分支，其中,k,是用戶指定的參數(shù)，旨在（,1,）最小化分支之間邊的權值（,2,）實現(xiàn)平衡約束。,OPOSSUM,使用如下兩種約束中的一種：（,1

29、,）每個簇中的對象個數(shù)必須粗略相等，或（,2,）屬性值的和必須粗略相等。,優(yōu)點與缺點,OPOSSUM,簡單、速度快。,,它將數(shù)據(jù)劃分大小粗略相等的簇。根據(jù)聚類的目標這可能看作優(yōu)點或缺點。,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,Chameleon,,,Chameleon,是一種凝聚聚類技術，它解決前兩段提到的問題。它將數(shù)據(jù)的初始劃分與一種新穎的層次聚類方案相結合。,,這種層次聚類使用接近性和互連性概念以及簇的局部建模。關鍵思想是：僅當合并后的結果簇類似于原來的兩個簇時，這兩個簇才應當合并。,確定

30、合并哪些簇,相對接近度（,relative closeness,，,RC,）：是被簇的內部接近度規(guī)范化的兩個簇的絕對接近度。兩個簇合并，僅當結果簇中的點之間的接近程度幾乎與原來的每個簇一樣。,,,,,,,mi,和,mj,分別是簇,ci,和,cj,的大小。,SEC,（,ci,，,cj,）是連接簇,ci,和,cj,的邊的平均值；,SEC,（,ci,）是二分簇,ci,的邊的平均權值。,,相對互連度（,relative interconnectivity, RI,）：是被簇的內部互連度規(guī)范化的兩個簇的絕對互連度。如果結果簇中的點之間的連接幾乎與原來的每個簇一樣強，兩個簇合并。,,,,,,其中，,EC,

31、（,Ci,，,Cj,）是連接簇,Ci,和,Cj,的邊之和；,EC(Ci),是二分簇,Ci,的割邊的最小和；,EC(Cj),是二分簇,Cj,的割邊的最小和。,,RI,和,RC,可以用多種不同的方法組合，產(chǎn)生自相似性的總量。,Chameleon,使用的方法是合并最大化,RI(Ci,Cj)*RC(Ci,Cj),a,簇對。其中,a,值大于,1.,Limitations of Current Merging Schemes,Relative Closeness schemes will merge (a) and (b),(a),(b),(c),(d),Relative interconnectivit

32、y schemes will merge (c) and (d),Chameleon,算法,構造,k-,最近鄰圖,,使用多層圖劃分算法劃分圖,,Repeat,,,合并關于相對互連性和相對接近性而言，最好,,地保持簇的自相似性的簇,,Until,不再有可以合并的簇,例子,,,優(yōu)點與局限性,Chameleon,能夠有效地聚類空間數(shù)據(jù)，即便存在噪聲和離群點，并且簇具有不同的形狀、大小和密度。,,Chameleon,假定由稀疏化和圖劃分過程產(chǎn)生的對象組群是子簇，即一個劃分中的大部分點屬于同一個真正的簇。如果不是，則凝聚層次聚類將混合這些錯誤，因為它絕對不可能再將已經(jīng)錯誤地放到一起的對象分開。這樣，當劃

33、分過程未產(chǎn)生子簇時，,chameleon,就有問題，對于高維數(shù)據(jù)，常常出現(xiàn)這種情況。,共享最近鄰相似性,SNN,（,shared nearest neighbor,）相似度計算：,,1.,找出所有點的,k-,近鄰,,2.If,兩個點,x,和,y,不是相互在對方的,k-,最近鄰中,then,,3. similarity(x,y),?0,,4.Else,,5.,,similarity(x,y)?,共享的近鄰個數(shù),,6.End if,,,SNN,相似度由于通過使用共享最近鄰的個數(shù)考慮了對象的環(huán)境，,SNN,相似度可以處理一個對象碰巧與另一對象相對接近，但屬于不同的類。在這種情況下，對象一般不共

34、享許多近鄰，并且它們的,SNN,相似度低。,,SSN,相似度也能處理變密度簇的問題。在低密度區(qū)域，對象比高密度區(qū)域的對象分開得更遠。然而，一對點之間的,SNN,相似度只依賴于兩個對象共享的最近鄰的個數(shù)，而不是這些近鄰之間的相距多遠。,SNN,關于點的密度進行自動縮放。,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,Jarvis-Patrick,（,JP,）聚類算法,計算,SNN,相似度圖,,使用相似度閾值，稀疏化,SNN,相似度圖,,找出稀疏化的,SNN,相似度圖的連通分支,,優(yōu)點與局限性,因為,JP

35、,聚類基于,SNN,相似度概念，它擅長于處理噪聲和離群點，并且能夠處理不同大小、形狀和密度的簇。,,該算法對高維數(shù)據(jù)效果良好，尤其擅長發(fā)現(xiàn)強相關對象的緊密簇。,,JP,聚類把簇定義為,SNN,相似度圖的連通分支。這樣，一個對象集是分裂成兩個簇還是作為一個簇留下，可能依賴于一條鏈。,,基于,SNN,密度的聚類,算法：,,計算,SNN,相似度圖,,以用戶指定的參數(shù),Eps,和,MinPts,，使用,DBSCAN,,,SNN,密度的聚類算法比,Jarvis-Patrick,聚類或,DBSCAN,更加靈活。,,不象,DBSCAN,，它可以用于高維數(shù)據(jù)和簇具有不同密度的情況。,,不象,Jarvis-Pa

36、trick,聚類簡單地使用域值，然后取連通分支作為簇，基于,SNN,密度的聚類使用基于,SNN,密度和核心點概念的方法。,,核心點：一個點是核心點，如果在該點給定鄰域內的點數(shù)超過某個閾值,MinPts,。,,邊界點。邊界點不是核心點，但是它落在一個核心點的鄰域內。,,噪聲點是既非核心點，也非邊界點的任何點。,SNN Density,,a) All Points b) High SNN Density,c) Medium SNN Density d) Low SNN Density,例子：解釋該算法處理高維數(shù)據(jù)能力,SNN Clusters o

37、f SLP.,SNN Density of Points on the Globe.,41,年期間，在,2.5,度的經(jīng)緯度網(wǎng)格的每個點上的月平均海平面氣壓（,SLP,）,優(yōu)點與局限性,基于,SNN,密度的聚類的優(yōu)點與局限性類似于,JP,聚類。,,然而，核心點和,SNN,密度的使用大大增加了該方法的能力和靈活性。,可伸縮：一般問題和方法,BIRCH,,CURE,,如果運行時間長得不可接受，或者需要的存儲量太大，即使最好的聚類算法也沒有多大價值。,,許多聚類算法所需要的存儲量都是非線性的。例如：使用層次聚類，存儲需求一般是,O(m2),。類似地，有些聚類算法所需要的計算量也是非線性的。,,可伸縮

38、性可以通過如下技術實現(xiàn)：多維或空間存取方法、鄰近度約束、抽樣、劃分數(shù)據(jù)對象、匯總、并行與分布計算。,,CURE,CURE,（,Clustering Using REpresentative,）是一種聚類算法，它使用各種不同的技術創(chuàng)建一種能夠處理大型數(shù)據(jù)、離群點、具有非球形和非均勻大小的簇的數(shù)據(jù)的方法。,,CURE,使用簇中的多個代表點來表示一個簇。理論上，這些點捕獲了簇的幾何形狀。,,具體來說，第一個代表點選擇離簇中心最遠的點，而其余的點選擇離所有已經(jīng)選取的點最遠的點。這樣，代表點相對分離。,,選取的點的個數(shù)是一個參數(shù)，但是一般取,>10,效果較好。,,一旦選定代表點，它們就以因子,a,向簇中

39、心收縮。這有助于減輕離群點的影響。,,例如，一個到中心的距離為,10,個單位的代表點將移動,3,個單位（對于,a=0.7,），而到中心距離為,1,個單位的代表點僅移動,0.3,個單位。,?,,CURE,使用一種凝聚層次聚類方案進行實際的聚類。兩個簇之間的距離是任意兩個代表點（在它們向它們代表點的中心收縮之后）之間的最短距離。,,如果,a=0,，它等價于基于質心的層次聚類；,a=1,時，它與單鏈層次聚類大致相同。,,注意，盡管使用層次聚類方案，但是,CURE,的目標是發(fā)現(xiàn)用戶指定個數(shù)的簇。,,CURE,在聚類過程的兩個不同階段刪除離群點。首先，如果一個簇增長緩慢，則這意味它主要由離群點組成，因為

40、根據(jù)定義，離群點遠離其他點，并且不會經(jīng)常與其他點合并。,,在,CURE,中，離群點刪除的第一個階段一般出現(xiàn)在簇的個數(shù)是原來點數(shù)的,1/3,時。第二個離群點刪除階段出現(xiàn)在簇的個數(shù)達到,K,的量級時。此時，小簇又被刪除。,,CURE,在最壞情況下復雜度為,O(m,2,logm),，它不能直接用于大型數(shù)據(jù)集。因此，,CURE,使用了兩種技術來加快聚類過程。,,第一種技術是取隨機樣本，并在抽樣的數(shù)據(jù)點上進行層次聚類。隨后是最終掃描，將數(shù)據(jù)集中剩余的點指派到簇中。,,在某些情況下，聚類所需要的樣本仍然太大，需要第二種技術解決。在這種情況下，,CURE,劃分樣本數(shù)據(jù)，然后聚類每個劃分中的點。這種預聚類步后

41、通常緊隨中間簇的聚類，以及將數(shù)據(jù)集中的每個點指派到一個簇的最終掃描。,CURE,算法,由數(shù)據(jù)集抽取一個隨機樣本集。,,將樣本集劃分成,p,個大小相同的劃分。,,使用,CURE,的層次聚類算法，將每個劃分中的點聚類成,m/pq,個簇，得到總共,m/q,個簇。,,使用,CURE,的層次聚類算法對上一步發(fā)現(xiàn)的,m/q,個簇進行聚類，直到只剩下,k,個簇。,,刪除離群點。,,將所有剩余的數(shù)據(jù)點指派到最近的簇，得到完全聚類。,,K,是期望的簇個數(shù)，,m,是點的個數(shù)，,p,是劃分的個數(shù)，而,q,是一個劃分中的點的期望壓縮，即一個劃分中的簇的個數(shù)是,m/pq,，簇的總數(shù)是,m/q,,例如，如果,m=1000

42、0,，,p=10,并且,q=100,，則每個劃分包含,10000/10=1000,個點，每個劃分有,1000/100=10,個簇，而總共有,10000/100=100,個簇。,CURE,的抽樣,CURE,抽樣盡力確保抽到每個簇的樣本。為了保證這樣的抽樣，,CURE,的作者推算出了能夠實現(xiàn)這一保證的樣本集大小的上界。,,,,,,S,為我們應該抽取的樣本大小,,假設有,100000,個對象，我們的目標是以,80%,的可能性得到,10%,的,Ci,簇對象，其中,Ci,的大小是,1000,。在此情況下，,f=0.1,，,δ,=0.2,，,m=100000,，這樣,s=11962,。,,S=11962,

43、是為了以,80%,的概率得到,10%,的,Ci,簇對象，需要抽取的樣本大小,,劃分,將點劃分成,p,個大小為,m/p,的組，使用,CURE,對每個劃分聚類，將對象的個數(shù)壓縮一個因子,q>1,,其中,q,可以粗略地看作劃分中的簇的平均大小?？偣伯a(chǎn)生,m/q,個簇。然后，預聚類后隨,m/q,個中間簇的最終聚類，產(chǎn)生期望的簇個數(shù)。兩遍聚類都使用,CURE,的層次聚類算法，而最后一遍將數(shù)據(jù)集中的每個點指派到一個簇。,,P,和,q,的選取是關鍵。應盡力選擇合適的,p,，使得整個劃分可以以合理的時間在內存處理。此外，應盡力選擇合適的,p,和,q,使得同一基本簇的對象最終在一個簇中。,A subnetwor

44、k is defined as a gene set that induces a single connected component in the protein–protein interaction network. Given a particular subnetwork M, let a represent its vector of activity scores over the tumor samples, and let c represent the corresponding vector of class labels (metastatic or non-metastatic).,,使用哪種聚類算法？,聚類的類型,,簇的類型,,簇的特性,,數(shù)據(jù)集和屬性的特征噪聲和離群點,,數(shù)據(jù)對象的個數(shù),,屬性的個數(shù),,簇描述,,算法考慮,,,數(shù)據(jù),,探索數(shù)據(jù),,分類：基本概念、決策樹與模型評估,,分類：其他技術,,關聯(lián)分析：基本概念和算法,,關聯(lián)分析：高級概念,,聚類分析：基本概念和算法,,聚類分析：附加問題與算法,,異常檢測,