附加問題與算法PPT課件

1、比較比較k均值和均值和DBSCANlDBSCAN和k均值都是將每個對象指派到單個簇的劃分聚類算法，但是K均值一般聚類所有對象，而DBSCAN丟棄被它識別為噪聲的對象。lK均值使用簇的基于原形的概念，而DBSCAN使用基于密度的概念。lDBSCAN可以處理不同大小和不同形狀的簇，并且不太受噪聲和離群點的影響。K均值很難處理非球狀的簇和不同大小的簇。當(dāng)簇具有很不同的密度時，兩種算法的性能都很差。第第1頁頁/共共108頁頁lK均值只能用于具有明確定義的質(zhì)心（如均值或中位數(shù)）的數(shù)據(jù)。DBSCAN要求密度定義（基于傳統(tǒng)的歐幾里得密度概念）對于數(shù)據(jù)是有意義的。lK均值可以用于稀疏的高維數(shù)據(jù)，如文檔數(shù)據(jù)，D

2、BSCAN通常在這類數(shù)據(jù)上性能很差，因為對于高維數(shù)據(jù)，傳統(tǒng)的歐幾里得密度定義不能很好處理。lK均值和DBSCAN的最初版本都是針對歐幾里得數(shù)據(jù)設(shè)計的，但是它們都被擴展，以便處理其他類型的數(shù)據(jù)。第第2頁頁/共共108頁頁lDBSCAN不對數(shù)據(jù)的分布做任何假定?；緆均值算法等價于一種統(tǒng)計聚類方法（混合模型），假定所有的簇都來自球形高斯分布，具有不同的均值，但具有相同的斜方差矩陣。lDBSCAN和k均值都尋找使用所有屬性的簇，即它們都不尋找可能只涉及某個屬性子集的簇。lK均值可以發(fā)現(xiàn)不是明顯分離的簇，即便簇有重疊也可以發(fā)現(xiàn)，但是DBSCAN會合并有重疊的簇。lK均值算法的時間復(fù)雜度是O（m），而D

3、BSCAN的時間復(fù)雜度是O（m2）.第第3頁頁/共共108頁頁lDBSCAN多次運行產(chǎn)生相同的結(jié)果，而k均值通常使用隨機初始化質(zhì)心，不會產(chǎn)生相同的結(jié)果。lDBSCAN自動地確定簇個數(shù)；對于k均值，簇個數(shù)需要作為參數(shù)指定。然而，DBSCAN必須指定另外兩個參數(shù)：Eps和MinptslK均值聚類可以看作優(yōu)化問題，即最小化每個點到最近的質(zhì)心的誤差的平方和，并且可以看作一種統(tǒng)計聚類的特例。DBSCAN不基于任何形式化模型。第第4頁頁/共共108頁頁數(shù)據(jù)特性數(shù)據(jù)特性l高維性 隨著維度的增加，體積迅速增加，除非點的個數(shù)也隨著維度指數(shù)增加，否則密度將趨向于0. 處理該問題的方法是使用維歸約技術(shù)l規(guī)模 許多聚

4、類算法對于小規(guī)模和中等規(guī)模的數(shù)據(jù)集運行良好，但是不能處理大型數(shù)據(jù)集l稀疏性 稀疏數(shù)據(jù)通常由非對稱的屬性組成，其中零值沒有非零值重要。.第第5頁頁/共共108頁頁l噪聲和離群點 非常見點可能嚴(yán)重地降低聚類算法的性能，特別是k均值這樣的基于原型的算法 另一方面，噪聲也可能導(dǎo)致單鏈等技術(shù)合并兩個不應(yīng)當(dāng)合并的簇。l屬性和數(shù)據(jù)集類型 屬性可能是分類的（標(biāo)稱的或序數(shù)的）或定量的（區(qū)間的或比率的），二元的、離散的或連續(xù)的。 不同的近鄰性和密度度量適合于不同類型的數(shù)據(jù)。l尺度 不同的屬性，如高度和重量，可能用不同的尺度度量。這些差別可能嚴(yán)重影響兩個對象之間的距離或相似性，從而影響聚類分析的結(jié)果。第第6頁頁/共

5、共108頁頁簇特性簇特性l數(shù)據(jù)分布 某些聚類技術(shù)假定數(shù)據(jù)具有特定的分布。更具體的說，它們常常假定可以用混合分布對數(shù)據(jù)建模，其中每個簇對應(yīng)于一個分布。l形狀 有些簇具有規(guī)則的形狀，如矩形和球形。但是，更一般地，簇可以具有任意形狀。 如DBSCAN和單鏈等技術(shù)可以處理任意形狀?；谠偷姆椒ê鸵恍哟尉垲惣夹g(shù)不能進行這樣的處理。 Chameleon和cure是專門用來處理這一問題的技術(shù)第第7頁頁/共共108頁頁l不同大小 許多聚類算法，如k均值，當(dāng)簇具有不同的大小時不能很好的處理l不同密度 具有很不相同的密度的簇可能對諸如DBSCAN和k均值等算法造成影響 基于SNN密度的聚類技術(shù)可以處理這個問題

6、l無明顯分離的簇 當(dāng)簇接觸或重疊時，有些聚類技術(shù)將應(yīng)當(dāng)分開的簇合并。甚至有些發(fā)現(xiàn)不同簇的技術(shù)隨意地將點指派到一個或另一個簇。 模糊聚類可以處理這一問題第第8頁頁/共共108頁頁l簇之間的聯(lián)系 在大部分聚類技術(shù)中，都不考慮簇之間的聯(lián)系，如簇的相對位置 自組織映射（SOM）是一種在聚類期間直接考慮簇之間聯(lián)系的聚類技術(shù)。l子空間簇 簇可能只在維（屬性）的一個子集中存在，并且使用一個維集合確定的簇可能也使用另一個維確定的簇很不相同。第第9頁頁/共共108頁頁聚類算法的一般特征聚類算法的一般特征l次序依賴性 對于某些算法，所產(chǎn)生的簇的質(zhì)量和個數(shù)可能因數(shù)據(jù)處理的次序不同而顯著地變化。如SOMl非確定性 有

7、些算法不是次序依賴的，但是它們每次運行都產(chǎn)生不同的結(jié)果，因為它們依賴于需要隨機選擇的初始化步驟。l變換聚類問題到其他領(lǐng)域 將聚類問題映射到一個不同的領(lǐng)域。如，基于圖的聚類第第10頁頁/共共108頁頁l可伸縮性 包含數(shù)以百萬計對象的數(shù)據(jù)集并不罕見，而用于這種數(shù)據(jù)集的聚類算法應(yīng)當(dāng)具有線性或接近線性的時間或空間復(fù)雜度。 對于大型數(shù)據(jù)集，即使具有O(m2)復(fù)雜度也是不切實際的。 此外，數(shù)據(jù)集聚類技術(shù)不能總是假定數(shù)據(jù)放在內(nèi)存，或者數(shù)據(jù)元素可以隨機的訪問。這樣的算法對于大型數(shù)據(jù)集是不可行的。第第11頁頁/共共108頁頁l參數(shù)選擇 大部分聚類算法需要用戶設(shè)置一個或多個參數(shù)。選擇合適的參數(shù)值可能是困難的；因此

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

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

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

11、。l在聚類文獻(xiàn)中，那些不采用簇質(zhì)心增量更新方法的k均值版本有時稱為c均值。模糊c均值算法有時稱為FCMl算法9.1 基本模糊c均值算法 選擇一個初始模糊偽劃分，即對所有的wij賦值 Repeat 使用模糊偽劃分，計算每個簇的質(zhì)心 重新計算模糊偽劃分，即wij Until 質(zhì)心不發(fā)生變化第第18頁頁/共共108頁頁lFCM的結(jié)構(gòu)類似于K均值。 K均值可以看作FCM的特例。lK均值在初始化之后，交替地更新質(zhì)心和指派每個對象到最近的質(zhì)心。具體地說，計算模糊偽劃分等價于指派步驟。l與k均值一樣，F(xiàn)CM可以解釋為試圖最小化誤差的平方和（SSE），盡管FCM基于SSE的模糊版本。第第19頁頁/共共108頁

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

13、向于1/k。 另一方面，隨著p趨向于1，該指數(shù)加大賦予離點最近的簇的權(quán)值。隨著p趨向于1，關(guān)于最近簇的隸屬權(quán)值趨向于1，而關(guān)于其他簇的隸屬權(quán)值趨向于0。這時對應(yīng)于k均值。kqpqipjiijcxdistcxdistw1112112),(/1 (),(/1 (第第22頁頁/共共108頁頁例子：三個圓形簇上的模糊例子：三個圓形簇上的模糊c均值均值第第23頁頁/共共108頁頁優(yōu)點與局限性優(yōu)點與局限性lFCM產(chǎn)生指示任意點屬于任意簇的程度的聚類。l它比K均值算法計算復(fù)雜性高。l除此之外，它與k均值算法具有相同的優(yōu)點和缺點。第第24頁頁/共共108頁頁基于原型的聚類基于原型的聚類l模糊聚類l使用混合模型

14、的聚類l自組織映射第第25頁頁/共共108頁頁使用混合模型的聚類使用混合模型的聚類l基于統(tǒng)計模型的聚類。通常，假定數(shù)據(jù)是由一個統(tǒng)計過程產(chǎn)生的，并且通過找出最佳擬合數(shù)據(jù)的統(tǒng)計模型來描述數(shù)據(jù)，其中統(tǒng)計模型用分布和該分布的一組參數(shù)描述。l混合模型（mixture models）：它使用若干統(tǒng)計分布對數(shù)據(jù)建模。每個分布對應(yīng)于一個簇，而每個分布的參數(shù)提供對應(yīng)于簇的描述，通常用中心和發(fā)散描述。第第26頁頁/共共108頁頁第第27頁頁/共共108頁頁算法算法l估計數(shù)據(jù)分布： 確定分布：一般假設(shè)數(shù)據(jù)取自高斯混合分布。然后，對分布的參數(shù)進行估計：利用EM算法進行最大似然估計 利用直方圖估計分布l對分布進行劃分、

15、分離。每個分布對應(yīng)于一個簇。第第28頁頁/共共108頁頁優(yōu)點和缺點優(yōu)點和缺點l混合模型比k均值或模糊c均值更一般，因為它可以使用各種類型的分布。l利用簡單的估計分布的方法（如直方圖）可能會錯誤估計數(shù)據(jù)的原始分布，導(dǎo)致結(jié)果不好。l利用復(fù)雜的方法（如EM算法），計算復(fù)雜性會大大增加。第第29頁頁/共共108頁頁基于原型的聚類基于原型的聚類l模糊聚類l使用混合模型的聚類l自組織映射第第30頁頁/共共108頁頁自組織映射自組織映射lKohonen自組織特征映射（SOFM或SOM）是一種基于神經(jīng)網(wǎng)絡(luò)觀點的聚類和數(shù)據(jù)可視化技術(shù)。l盡管SOM源于神經(jīng)網(wǎng)絡(luò)，但是它可以表示成一種基于原形的聚類的變形。l與其他基

16、于質(zhì)心的聚類技術(shù)一樣，SOM的目標(biāo)是發(fā)現(xiàn)質(zhì)心的集合，并將數(shù)據(jù)集中的每個對象指派到提供該對象最佳近似的質(zhì)心。用神經(jīng)網(wǎng)絡(luò)的術(shù)語，每個質(zhì)心都與一個神經(jīng)元相關(guān)聯(lián)。第第31頁頁/共共108頁頁SOM算法算法l初始化質(zhì)心。lRepeatl 選擇下一個對象l 確定到該對象最近的質(zhì)心l 更新該質(zhì)心和附近的質(zhì)心，即在一個特定鄰域 內(nèi)的質(zhì)心lUntil 質(zhì)心改變不多或超過某個域值l指派每個對象到最近的質(zhì)心，并返回質(zhì)心和簇第第32頁頁/共共108頁頁基于密度的聚類基于密度的聚類l基于網(wǎng)格的聚類l子空間聚類lDENCLUE第第33頁頁/共共108頁頁基于網(wǎng)格的聚類基于網(wǎng)格的聚類l網(wǎng)格是一種組織數(shù)據(jù)集的有效方法，至少在

17、低維空間中如此。l其基本思想是，將每個屬性的可能值分割成許多相鄰的區(qū)間，創(chuàng)建網(wǎng)格單元的集合。每個對象落入一個網(wǎng)格單元，網(wǎng)格單元對應(yīng)的屬性區(qū)間包含該對象的值。l存在許多利用網(wǎng)格進行聚類的方法，大部分方法是基于密度的。第第34頁頁/共共108頁頁例子例子第第35頁頁/共共108頁頁基于網(wǎng)格的算法基于網(wǎng)格的算法l定義一個網(wǎng)格單元集l將對象指派到合適的單元，并計算每個單元的密度l刪除密度低于指定的閾值的單元l由鄰近的稠密單元組形成簇第第36頁頁/共共108頁頁l定義網(wǎng)格單元 對于連續(xù)屬性，定義網(wǎng)格單元相當(dāng)于連續(xù)屬性離散化?？蓪⒅祫澐譃榈葘挼膮^(qū)間、等頻的區(qū)間、使用聚類確定的區(qū)間。l網(wǎng)格單元的密度 定義網(wǎng)

18、格單元密度的自然方法是：定義網(wǎng)格單元的密度為該區(qū)域中的點數(shù)除以區(qū)域的體積。 如果使用具有相同體積的網(wǎng)格單元，使得每個單元的點數(shù)直接度量單元的密度。第第37頁頁/共共108頁頁l鄰近的稠密單元組形成簇 密度閾值的設(shè)定是關(guān)鍵。如圖9-10和表9-2，如果密度閾值為9，則大簇的4個部分將丟失。 鄰近單元？一個二維網(wǎng)格單元有4個還是8個鄰接單元？第第38頁頁/共共108頁頁例子例子第第39頁頁/共共108頁頁優(yōu)點與局限性優(yōu)點與局限性l算法運行速度較快，可達(dá)o(mlogm)。這使得它成為許多聚類算法的基礎(chǔ)，如STING、GRIDCLUS、waveCluster、Bang-Clustering、CLIQU

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

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

21、應(yīng)于每個屬性的一維空間中的所有稠密區(qū)域。這是稠密的一維單元的集合。lK2lRepeatl 由稠密的k-1維單元產(chǎn)生所有的候選稠密k維單元l 刪除點數(shù)少于域值的單元l kk+1lUntil 不存在候選稠密k維單元l通過取所有鄰接的、高密度的單元的并發(fā)現(xiàn)簇l使用一小組描述簇中單元的屬性值域的不等式概括每一個簇。第第46頁頁/共共108頁頁CLIQUE的優(yōu)點與局限性的優(yōu)點與局限性lCLIQUE最大特點是，它提供了一種搜索子空間發(fā)現(xiàn)簇的有效技術(shù)。由于這種方法基于關(guān)聯(lián)分析的先驗原理，它的性質(zhì)能夠被很好地解釋。lCLIQUE能夠用一小組不等式概括構(gòu)成一個簇的單元列表。lCLIQUE的局限性與其他基于密度的

22、方法和Apriori算法相同。如，CLIQUE發(fā)現(xiàn)的簇可以共享對象。允許簇重疊可能大幅度增加簇的個數(shù)，并使得解釋更加困難。Apriori具有指數(shù)級的復(fù)雜度。第第47頁頁/共共108頁頁基于密度的聚類基于密度的聚類l基于網(wǎng)格的聚類l子空間聚類lDENCLUE第第48頁頁/共共108頁頁DENCLUE：基于密度聚類的一種基于核的方案：基于密度聚類的一種基于核的方案lDENCLUE(DENsity CLUstEring)是一種基于密度的聚類方法，它用與每個點相關(guān)聯(lián)的影響函數(shù)之和對點集的總密度建模。結(jié)果總密度函數(shù)將具有局部尖峰，并且這些局部尖峰用來以自然的方式定義簇。l具體的說，對于每個數(shù)據(jù)點，一個爬

23、山過程找出與該點相關(guān)聯(lián)的最近的尖峰，并且與一個特定的尖峰（稱作局部密度吸引點（local density attractor）相關(guān)聯(lián)的所有數(shù)據(jù)點成為一個簇。l如果局部尖峰處的密度太低，則相關(guān)聯(lián)的簇中的點將被視為噪聲而丟棄。l如果一個局部尖峰通過一條數(shù)據(jù)點路徑與另一個局部尖峰相連接，并且該路徑上每個點的密度都高于最小密度閾值，則與這些局部尖峰相關(guān)聯(lián)的簇合并在一起。第第49頁頁/共共108頁頁第第50頁頁/共共108頁頁DENCLUE算法算法l對數(shù)據(jù)點占據(jù)的空間推導(dǎo)密度函數(shù)l識別局部最大點（即密度吸引點）l通過沿密度增長最大的方向移動，將每個點關(guān)聯(lián)到一個密度吸引點l定義與特定的密度吸引點相關(guān)聯(lián)的點

24、構(gòu)成的簇l丟棄密度吸引點的密度小于用戶指定閾值的簇l合并通過密度大于或等于閾值的點路徑連接的簇第第51頁頁/共共108頁頁核密度估計核密度估計l核密度估計用函數(shù)描述數(shù)據(jù)的分布。每個點對總密度函數(shù)的貢獻(xiàn)用一個核函數(shù)表示?？偯芏群瘮?shù)僅僅是與每個點相關(guān)聯(lián)的核函數(shù)之核l核函數(shù)是對稱的，并且它的值隨到點的距離增加而下降。高斯函數(shù)常常用作核函數(shù)：222/),(tan)(yxcediseyk第第52頁頁/共共108頁頁第第53頁頁/共共108頁頁DENCLUE的優(yōu)點與局限性的優(yōu)點與局限性lDENCLUE具有堅實的理論基礎(chǔ)，因為它基于統(tǒng)計學(xué)發(fā)展完善的領(lǐng)域-核密度函數(shù)和核密度估計。因此，DENCLUE提供了比其

25、他基于網(wǎng)絡(luò)的聚類技術(shù)和DBSCAN更加靈活、更加精確的計算密度的方法。（DBSCAN是DENCLUE的特例）l基于核密度函數(shù)的方法本質(zhì)上是計算昂貴的，但DENCLUE使用基于網(wǎng)格的技術(shù)來處理該問題。盡管如此，DENCLUE可能比其他基于密度的聚類技術(shù)的計算開銷更大。lDENCLUE具有其他基于密度的方法的優(yōu)缺點。第第54頁頁/共共108頁頁基于圖的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-Patrick聚類算法l基于SNN密度的聚類第第55頁頁/共共108頁頁稀疏化稀疏化lm個數(shù)據(jù)點的mm鄰近度矩陣可以用一個稠密圖表示，每個節(jié)點與其他所有點相連，權(quán)值反

26、映鄰近性。l盡管每個對象與其他每個對象都有某種程度的近鄰性，但是對于大部分?jǐn)?shù)據(jù)集，對象只與少量對象高度相似，而與大部分其他對象的相似性很弱。這一性質(zhì)用來稀疏化鄰近度圖。l稀疏化可以這樣進行：斷開相似度低于指定閾值的邊、或僅保留連接到點的k個近鄰的邊。第第56頁頁/共共108頁頁稀疏化的好處稀疏化的好處l壓縮了數(shù)據(jù)量l可以更好的聚類 稀疏化技術(shù)保持了對象與最近鄰的連接，斷開與較遠(yuǎn)對象的連接。這與最近鄰原理一致，對象的最近鄰趨向于與對象在同一個類。這降低了噪聲和離群點的影響，增強了簇之間的差別。l可以使用圖劃分算法第第57頁頁/共共108頁頁l應(yīng)當(dāng)把鄰近度圖的稀疏化看成使用實際聚類算法之前的初始化

27、步驟。l理論上講，一個完美的稀疏化應(yīng)當(dāng)將鄰近度圖劃分成對應(yīng)于期望簇的連通分支，但實際中這很難做到。很容易出現(xiàn)單條邊連接兩個簇，或者單個簇被分裂成若干個不相連接的子簇的情況。第第58頁頁/共共108頁頁基于圖的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-Patrick聚類算法l基于SNN密度的聚類第第59頁頁/共共108頁頁最小生成樹聚類（最小生成樹聚類（minimum spanning tree，MST）l計算相異度圖的最小生成樹lRepeatl 斷開對應(yīng)于最大相異度的邊，創(chuàng)建一個新的簇lUntil 只剩下單個簇l最小生成樹聚類是一種基于分裂的層次聚類算

28、法l最小生成樹聚類可以看作用稀疏化找出簇的方法第第60頁頁/共共108頁頁第第61頁頁/共共108頁頁基于圖的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-Patrick聚類算法l基于SNN密度的聚類第第62頁頁/共共108頁頁OPOSSUM：使用：使用METIS的稀疏相似度最優(yōu)劃分的稀疏相似度最優(yōu)劃分lOPOSSUM（Optimal Partitioning of Sparse Similarities Using METIS）是一種專門為諸如文檔或購物籃數(shù)據(jù)等稀疏、高維數(shù)據(jù)設(shè)計的聚類技術(shù)。與MST一樣，它基于鄰近度圖的稀疏化進行聚類。然而，OPOSSU

29、M使用METIS算法，該算法是專門為劃分圖設(shè)計的。lOPOSSUM聚類算法l1：計算稀疏化的相似度圖l2：使用METIS，將相似度圖劃分成k個不同的分支（簇）第第63頁頁/共共108頁頁 l所使用的相似性度量是適合于稀疏、高維數(shù)據(jù)的度量，如擴充的Jaccard度量或余弦度量。lMETIS圖劃分程序?qū)⑾∈鑸D劃分為k個不同的分支，其中k是用戶指定的參數(shù)，旨在（1）最小化分支之間邊的權(quán)值（2）實現(xiàn)平衡約束。OPOSSUM使用如下兩種約束中的一種：（1）每個簇中的對象個數(shù)必須粗略相等，或（2）屬性值的和必須粗略相等。第第64頁頁/共共108頁頁優(yōu)點與缺點優(yōu)點與缺點lOPOSSUM簡單、速度快。l它將數(shù)

30、據(jù)劃分大小粗略相等的簇。根據(jù)聚類的目標(biāo)這可能看作優(yōu)點或缺點。第第65頁頁/共共108頁頁基于圖的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-Patrick聚類算法l基于SNN密度的聚類第第66頁頁/共共108頁頁Chameleon第第67頁頁/共共108頁頁第第68頁頁/共共108頁頁lChameleon是一種凝聚聚類技術(shù)，它解決前兩段提到的問題。它將數(shù)據(jù)的初始劃分與一種新穎的層次聚類方案相結(jié)合。l這種層次聚類使用接近性和互連性概念以及簇的局部建模。關(guān)鍵思想是：僅當(dāng)合并后的結(jié)果簇類似于原來的兩個簇時，這兩個簇才應(yīng)當(dāng)合并。第第69頁頁/共共108頁頁確定合

31、并哪些簇確定合并哪些簇l相對接近度（relative closeness，RC）：是被簇的內(nèi)部接近度規(guī)范化的兩個簇的絕對接近度。兩個簇合并，僅當(dāng)結(jié)果簇中的點之間的接近程度幾乎與原來的每個簇一樣。lmi和mj分別是簇ci和cj的大小。SEC（ci，cj）是連接簇ci和cj的邊的平均值；SEC（ci）是二分簇ci的邊的平均權(quán)值。)()(),(),(jECjiiiECjiijiECjiCSmmmCSmmmCCSCCRC第第70頁頁/共共108頁頁l相對互連度（relative interconnectivity, RI）：是被簇的內(nèi)部互連度規(guī)范化的兩個簇的絕對互連度。如果結(jié)果簇中的點之間的連接幾乎與

32、原來的每個簇一樣強，兩個簇合并。l其中，EC（Ci，Cj）是連接簇Ci和Cj的邊之和；EC(Ci)是二分簇Ci的割邊的最小和；EC(Cj)是二分簇Cj的割邊的最小和。lRI和RC可以用多種不同的方法組合，產(chǎn)生自相似性的總量。Chameleon使用的方法是合并最大化RI(Ci,Cj)*RC(Ci,Cj)a簇對。其中a值大于1.)()(21),(),(jijijiCECCECCCECCCRI第第71頁頁/共共108頁頁Limitations of Current Merging SchemesRelative Closeness schemes will merge (a) and (b)(a)(

33、b)(c)(d)Relative interconnectivity schemes will merge (c) and (d)第第72頁頁/共共108頁頁Chameleon算法算法l構(gòu)造k-最近鄰圖l使用多層圖劃分算法劃分圖lRepeatl 合并關(guān)于相對互連性和相對接近性而言，最好 地保持簇的自相似性的簇lUntil 不再有可以合并的簇第第73頁頁/共共108頁頁例子例子第第74頁頁/共共108頁頁第第75頁頁/共共108頁頁第第76頁頁/共共108頁頁優(yōu)點與局限性優(yōu)點與局限性lChameleon能夠有效地聚類空間數(shù)據(jù)，即便存在噪聲和離群點，并且簇具有不同的形狀、大小和密度。lChamel

34、eon假定由稀疏化和圖劃分過程產(chǎn)生的對象組群是子簇，即一個劃分中的大部分點屬于同一個真正的簇。如果不是，則凝聚層次聚類將混合這些錯誤，因為它絕對不可能再將已經(jīng)錯誤地放到一起的對象分開。這樣，當(dāng)劃分過程未產(chǎn)生子簇時，chameleon就有問題，對于高維數(shù)據(jù)，常常出現(xiàn)這種情況。第第77頁頁/共共108頁頁共享最近鄰相似性共享最近鄰相似性lSNN（shared nearest neighbor）相似度計算：l1.找出所有點的k-近鄰l2.If 兩個點x和y不是相互在對方的k-最近鄰中 thenl3. similarity(x,y) 0l4.Elsel5. similarity(x,y)共享的近鄰個數(shù)

35、l6.End if第第78頁頁/共共108頁頁第第79頁頁/共共108頁頁lSNN相似度由于通過使用共享最近鄰的個數(shù)考慮了對象的環(huán)境，SNN相似度可以處理一個對象碰巧與另一對象相對接近，但屬于不同的類。在這種情況下，對象一般不共享許多近鄰，并且它們的SNN相似度低。lSSN相似度也能處理變密度簇的問題。在低密度區(qū)域，對象比高密度區(qū)域的對象分開得更遠(yuǎn)。然而，一對點之間的SNN相似度只依賴于兩個對象共享的最近鄰的個數(shù)，而不是這些近鄰之間的相距多遠(yuǎn)。SNN關(guān)于點的密度進行自動縮放。第第80頁頁/共共108頁頁基于圖的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-

36、Patrick聚類算法l基于SNN密度的聚類第第81頁頁/共共108頁頁Jarvis-Patrick（JP）聚類算法）聚類算法l計算SNN相似度圖l使用相似度閾值，稀疏化SNN相似度圖l找出稀疏化的SNN相似度圖的連通分支第第82頁頁/共共108頁頁第第83頁頁/共共108頁頁優(yōu)點與局限性優(yōu)點與局限性l因為JP聚類基于SNN相似度概念，它擅長于處理噪聲和離群點，并且能夠處理不同大小、形狀和密度的簇。l該算法對高維數(shù)據(jù)效果良好，尤其擅長發(fā)現(xiàn)強相關(guān)對象的緊密簇。lJP聚類把簇定義為SNN相似度圖的連通分支。這樣，一個對象集是分裂成兩個簇還是作為一個簇留下，可能依賴于一條鏈。第第84頁頁/共共108

37、頁頁第第85頁頁/共共108頁頁基于基于SNN密度的聚類密度的聚類l算法：l計算SNN相似度圖l以用戶指定的參數(shù)Eps和MinPts，使用DBSCANlSNN密度的聚類算法比Jarvis-Patrick聚類或DBSCAN更加靈活。l不象DBSCAN，它可以用于高維數(shù)據(jù)和簇具有不同密度的情況。l不象Jarvis-Patrick聚類簡單地使用域值，然后取連通分支作為簇，基于SNN密度的聚類使用基于SNN密度和核心點概念的方法。第第86頁頁/共共108頁頁l核心點：一個點是核心點，如果在該點給定鄰域內(nèi)的點數(shù)超過某個閾值MinPts。l邊界點。邊界點不是核心點，但是它落在一個核心點的鄰域內(nèi)。l噪聲點是

38、既非核心點，也非邊界點的任何點。第第87頁頁/共共108頁頁SNN Density a) All Points b) High SNN Densityc) Medium SNN Density d) Low SNN Density第第88頁頁/共共108頁頁例子：解釋該算法處理高維數(shù)據(jù)能力例子：解釋該算法處理高維數(shù)據(jù)能力26 SLP Clusters via Shared Nearest Neighbor Clustering (100 NN, 1982-1994) longitudelatitude-180-150-120-90 -60 -30 0 30 60 90 120 150 180

39、90 60 30 0 -30-60-9013 26 24 25 22 14 16 20 17 18 19 15 23 1 9 6 4 7 10 12 11 3 5 2 8 21 SNN Clusters of SLP.SNN Density of SLP Time Series Datalongitudelatitude-180 -150 -120-90 -60 -30 0 30 60 90 120 150 180 90 60 30 0 -30-60-90SNN Density of Points on the Globe.l41年期間，在2.5度的經(jīng)緯度網(wǎng)格的每個點上的月平均海平面氣壓（SL

40、P）第第89頁頁/共共108頁頁優(yōu)點與局限性優(yōu)點與局限性l基于SNN密度的聚類的優(yōu)點與局限性類似于JP聚類。l然而，核心點和SNN密度的使用大大增加了該方法的能力和靈活性。第第90頁頁/共共108頁頁可伸縮：一般問題和方法可伸縮：一般問題和方法lBIRCHlCURE第第91頁頁/共共108頁頁l如果運行時間長得不可接受，或者需要的存儲量太大，即使最好的聚類算法也沒有多大價值。l許多聚類算法所需要的存儲量都是非線性的。例如：使用層次聚類，存儲需求一般是O(m2)。類似地，有些聚類算法所需要的計算量也是非線性的。l可伸縮性可以通過如下技術(shù)實現(xiàn)：多維或空間存取方法、鄰近度約束、抽樣、劃分?jǐn)?shù)據(jù)對象、匯

41、總、并行與分布計算。第第92頁頁/共共108頁頁CURElCURE（Clustering Using REpresentative）是一種聚類算法，它使用各種不同的技術(shù)創(chuàng)建一種能夠處理大型數(shù)據(jù)、離群點、具有非球形和非均勻大小的簇的數(shù)據(jù)的方法。lCURE使用簇中的多個代表點來表示一個簇。理論上，這些點捕獲了簇的幾何形狀。l具體來說，第一個代表點選擇離簇中心最遠(yuǎn)的點，而其余的點選擇離所有已經(jīng)選取的點最遠(yuǎn)的點。這樣，代表點相對分離。l選取的點的個數(shù)是一個參數(shù)，但是一般取10效果較好。第第93頁頁/共共108頁頁l一旦選定代表點，它們就以因子a向簇中心收縮。這有助于減輕離群點的影響。l例如，一個到中心

42、的距離為10個單位的代表點將移動3個單位（對于a=0.7），而到中心距離為1個單位的代表點僅移動0.3個單位。 第第94頁頁/共共108頁頁lCURE使用一種凝聚層次聚類方案進行實際的聚類。兩個簇之間的距離是任意兩個代表點（在它們向它們代表點的中心收縮之后）之間的最短距離。l如果a=0，它等價于基于質(zhì)心的層次聚類；a=1時，它與單鏈層次聚類大致相同。l注意，盡管使用層次聚類方案，但是CURE的目標(biāo)是發(fā)現(xiàn)用戶指定個數(shù)的簇。第第95頁頁/共共108頁頁lCURE在聚類過程的兩個不同階段刪除離群點。首先，如果一個簇增長緩慢，則這意味它主要由離群點組成，因為根據(jù)定義，離群點遠(yuǎn)離其他點，并且不會經(jīng)常與其

43、他點合并。l在CURE中，離群點刪除的第一個階段一般出現(xiàn)在簇的個數(shù)是原來點數(shù)的1/3時。第二個離群點刪除階段出現(xiàn)在簇的個數(shù)達(dá)到K的量級時。此時，小簇又被刪除。第第96頁頁/共共108頁頁lCURE在最壞情況下復(fù)雜度為O(m2logm)，它不能直接用于大型數(shù)據(jù)集。因此，CURE使用了兩種技術(shù)來加快聚類過程。l第一種技術(shù)是取隨機樣本，并在抽樣的數(shù)據(jù)點上進行層次聚類。隨后是最終掃描，將數(shù)據(jù)集中剩余的點指派到簇中。l在某些情況下，聚類所需要的樣本仍然太大，需要第二種技術(shù)解決。在這種情況下，CURE劃分樣本數(shù)據(jù)，然后聚類每個劃分中的點。這種預(yù)聚類步后通常緊隨中間簇的聚類，以及將數(shù)據(jù)集中的每個點指派到一個簇的最終掃描。第第97頁頁/共