數(shù)據(jù)挖掘?qū)д撏暾嬷?/h3>

Click to edit Master title style,,Click to edit Master text styles,,Second Level,,Third Level,,聚類分析：附加的問題與算法,第,9,章,,,聚類分析：附加的問題與算法,,,,,在各種領(lǐng)域，針對不同的應(yīng)用類型，已經(jīng)開發(fā)了大量聚類算法。在這些算法中沒有一種算法能夠適應(yīng)所有的數(shù)據(jù)類型、簇和應(yīng)用。,,事實(shí)上，對于更加有效或者更適合特定數(shù)據(jù)類型、簇和應(yīng)用的新的聚類算法，看來總是有進(jìn)一步的開發(fā)空間。,,我們只能說我們已經(jīng)有了一些技術(shù)，對于某些情況運(yùn)行良好。其原因是，在許多情況下，對于什么是一個(gè)好的簇集，仍然憑主觀解釋。此外，當(dāng)使用客觀度量精確地定義簇時(shí)，發(fā)現(xiàn)最優(yōu)聚類問題常常是計(jì)算不可行的。,比較,k,均值和,DBSCAN,DBSCAN,和,k,均值都是將每個(gè)對象指派到單個(gè)簇的劃分聚類算法，但是,K,均值一般聚類所有對象，而,DBSCAN,丟棄被它識別為噪聲的對象。,,K,均值使用簇的基于原形的概念，而,DBSCAN,使用基于密度的概念。,,DBSCAN,可以處理不同大小和不同形狀的簇，并且不太受噪聲和離群點(diǎn)的影響。,K,均值很難處理非球狀的簇和不同大小的簇。當(dāng)簇具有很不同的密度時(shí)，兩種算法的性能都很差。,,,K,均值只能用于具有明確定義的質(zhì)心（如均值或中位數(shù)）的數(shù)據(jù)。,DBSCAN,要求密度定義（基于傳統(tǒng)的歐幾里得密度概念）對于數(shù)據(jù)是有意義的。,,K,均值可以用于稀疏的高維數(shù)據(jù)，如文檔數(shù)據(jù)，,DBSCAN,通常在這類數(shù)據(jù)上性能很差，因?yàn)閷τ诟呔S數(shù)據(jù)，傳統(tǒng)的歐幾里得密度定義不能很好處理。,,K,均值和,DBSCAN,的最初版本都是針對歐幾里得數(shù)據(jù)設(shè)計(jì)的，但是它們都被擴(kuò)展，以便處理其他類型的數(shù)據(jù)。,,,DBSCAN,不對數(shù)據(jù)的分布做任何假定。基本,k,均值算法等價(jià)于一種統(tǒng)計(jì)聚類方法（混合模型），假定所有的簇都來自球形高斯分布，具有不同的均值，但具有相同的斜方差矩陣。,,DBSCAN,和,k,均值都尋找使用所有屬性的簇，即它們都不尋找可能只涉及某個(gè)屬性子集的簇。,,K,均值可以發(fā)現(xiàn)不是明顯分離的簇，即便簇有重疊也可以發(fā)現(xiàn)，但是,DBSCAN,會(huì)合并有重疊的簇。,,K,均值算法的時(shí)間復(fù)雜度是,O,（,m,），而,DBSCAN,的時(shí)間復(fù)雜度是,O,（,m2,）,.,,DBSCAN,多次運(yùn)行產(chǎn)生相同的結(jié)果，而,k,均值通常使用隨機(jī)初始化質(zhì)心，不會(huì)產(chǎn)生相同的結(jié)果。,,DBSCAN,自動(dòng)地確定簇個(gè)數(shù)；對于,k,均值，簇個(gè)數(shù)需要作為參數(shù)指定。然而，,DBSCAN,必須指定另外兩個(gè)參數(shù)：,Eps,和,Minpts,,K,均值聚類可以看作優(yōu)化問題，即最小化每個(gè)點(diǎn)到最近的質(zhì)心的誤差的平方和，并且可以看作一種統(tǒng)計(jì)聚類的特例。,DBSCAN,不基于任何形式化模型。,,數(shù)據(jù)特性,高維性,,隨著維度的增加，體積迅速增加，除非點(diǎn)的個(gè)數(shù)也隨著維度指數(shù)增加，否則密度將趨向于,0.,,處理該問題的方法是使用維歸約技術(shù),,規(guī)模,,許多聚類算法對于小規(guī)模和中等規(guī)模的數(shù)據(jù)集運(yùn)行良好，但是不能處理大型數(shù)據(jù)集,,稀疏性,,稀疏數(shù)據(jù)通常由非對稱的屬性組成，其中零值沒有非零值重要。,.,,,噪聲和離群點(diǎn),,非常見點(diǎn)可能嚴(yán)重地降低聚類算法的性能，特別是,k,均值這樣的基于原型的算法,,另一方面，噪聲也可能導(dǎo)致單鏈等技術(shù)合并兩個(gè)不應(yīng)當(dāng)合并的簇。,,屬性和數(shù)據(jù)集類型,,屬性可能是分類的（標(biāo)稱的或序數(shù)的）或定量的（區(qū)間的或比率的），二元的、離散的或連續(xù)的。,,不同的近鄰性和密度度量適合于不同類型的數(shù)據(jù)。,,尺度,,不同的屬性，如高度和重量，可能用不同的尺度度量。這些差別可能嚴(yán)重影響兩個(gè)對象之間的距離或相似性，從而影響聚類分析的結(jié)果。,簇特性,數(shù)據(jù)分布,,某些聚類技術(shù)假定數(shù)據(jù)具有特定的分布。更具體的說，它們常常假定可以用混合分布對數(shù)據(jù)建模，其中每個(gè)簇對應(yīng)于一個(gè)分布。,,形狀,,有些簇具有規(guī)則的形狀，如矩形和球形。但是，更一般地，簇可以具有任意形狀。,,如,DBSCAN,和單鏈等技術(shù)可以處理任意形狀?；谠偷姆椒ê鸵恍哟尉垲惣夹g(shù)不能進(jìn)行這樣的處理。,,Chameleon,和,cure,是專門用來處理這一問題的技術(shù),,,不同大小,,許多聚類算法，如,k,均值，當(dāng)簇具有不同的大小時(shí)不能很好的處理,,不同密度,,具有很不相同的密度的簇可能對諸如,DBSCAN,和,k,均值等算法造成影響,,基于,SNN,密度的聚類技術(shù)可以處理這個(gè)問題,,無明顯分離的簇,,當(dāng)簇接觸或重疊時(shí)，有些聚類技術(shù)將應(yīng)當(dāng)分開的簇合并。甚至有些發(fā)現(xiàn)不同簇的技術(shù)隨意地將點(diǎn)指派到一個(gè)或另一個(gè)簇。,,模糊聚類可以處理這一問題,,,簇之間的聯(lián)系,,在大部分聚類技術(shù)中，都不考慮簇之間的聯(lián)系，如簇的相對位置,,自組織映射（,SOM,）是一種在聚類期間直接考慮簇之間聯(lián)系的聚類技術(shù)。,,子空間簇,,簇可能只在維（屬性）的一個(gè)子集中存在，并且使用一個(gè)維集合確定的簇可能也使用另一個(gè)維確定的簇很不相同。,,聚類算法的一般特征,次序依賴性,,對于某些算法，所產(chǎn)生的簇的質(zhì)量和個(gè)數(shù)可能因數(shù)據(jù)處理的次序不同而顯著地變化。如,SOM,,非確定性,,有些算法不是次序依賴的，但是它們每次運(yùn)行都產(chǎn)生不同的結(jié)果，因?yàn)樗鼈円蕾囉谛枰S機(jī)選擇的初始化步驟。,,變換聚類問題到其他領(lǐng)域,,將聚類問題映射到一個(gè)不同的領(lǐng)域。如，基于圖的聚類,,,,可伸縮性,,包含數(shù)以百萬計(jì)對象的數(shù)據(jù)集并不罕見，而用于這種數(shù)據(jù)集的聚類算法應(yīng)當(dāng)具有線性或接近線性的時(shí)間或空間復(fù)雜度。,,對于大型數(shù)據(jù)集，即使具有,O(m2),復(fù)雜度也是不切實(shí)際的。,,此外，數(shù)據(jù)集聚類技術(shù)不能總是假定數(shù)據(jù)放在內(nèi)存，或者數(shù)據(jù)元素可以隨機(jī)的訪問。這樣的算法對于大型數(shù)據(jù)集是不可行的。,,參數(shù)選擇,,大部分聚類算法需要用戶設(shè)置一個(gè)或多個(gè)參數(shù)。選擇合適的參數(shù)值可能是困難的；因此，通常的態(tài)度是“參數(shù)越少越好”。,,,將聚類作為最優(yōu)化問題處理,,聚類常常被看作優(yōu)化問題。將點(diǎn)劃分成簇，根據(jù)用戶指定的目標(biāo)函數(shù)度量，最大化結(jié)果簇集合的優(yōu)良度。如,k,均值試圖發(fā)現(xiàn)簇的集合，使得每個(gè)點(diǎn)到最近的簇質(zhì)心距離的平方和最小。,,基于原型的聚類,模糊聚類,,,使用混合模型的聚類,,,自組織映射,模糊聚類,模糊集合,,1965,年，,Lotfi Zadeh,引進(jìn)模糊集合論（,fuzzy set theory,）和模糊邏輯（,fuzzy logic,）作為一種處理不精確和不確定性的方法。,,簡要的說，模糊集合論允許對象以,0,和,1,之間的某個(gè)隸屬度屬于一個(gè)集合，而模糊邏輯允許一個(gè)陳述以,0,和,1,之間的確定度為真。,,傳統(tǒng)的集合論和邏輯是對應(yīng)的模糊集合論和模糊邏輯的特殊情況，它們限制集合的隸屬度或確定度或者為,0,，或者為,1.,,考慮如下模糊邏輯的例子,,陳述“天空多云”為真的程度可以定義為天空被云覆蓋的百分比。例如，天空的,50%,被云覆蓋，則“天空多云”為真的程度是,0.5,。,,如果我們有兩個(gè)集合“多云天”和“非多云天”，則我們可以類似地賦予每一天隸屬于這兩個(gè)集合的程度。,,這樣，如果一天,25%,多云，則它在“多云天”集合中具有,0.25,的隸屬度，而在“非多云天”集合中具有,0.75,的隸屬度。,,模糊簇,,假定我們有一個(gè)數(shù)據(jù)點(diǎn)的集合,X={x1,x2,…,xm},，其中每個(gè)點(diǎn),xi,是一個(gè),n,維點(diǎn)，即,xi=,（,xi1,xi2,…,xin),。模糊簇集,C1,C2,…,Ck,是,X,的所有可能模糊子集的一個(gè)子集。,,這簡單地意味著對于每個(gè)點(diǎn),xi,和每個(gè)簇,Cj,，隸屬權(quán)值（度）,wij,已經(jīng)賦予,0,和,1,之間的值。,,然而，我們還想將以下合理的條件施加在簇上，以確定簇形成模糊偽劃分（,fuzzy psuedo-partition,）。,,給定點(diǎn),xi,的所有權(quán)值之和為,1,：,,,,,每個(gè)簇,Cj,以非零權(quán)值至少包含一個(gè)點(diǎn)，但不以權(quán)值,1,包含所有的點(diǎn),,,盡管存在多種模糊聚類，我們只考慮,k,均值的模糊版本，稱作模糊,c,均值。,,在聚類文獻(xiàn)中，那些不采用簇質(zhì)心增量更新方法的,k,均值版本有時(shí)稱為,c,均值。模糊,c,均值算法有時(shí)稱為,FCM,,算法,9.1,基本模糊,c,均值算法,,選擇一個(gè)初始模糊偽劃分，即對所有的,wij,賦值,,Repeat,,,使用模糊偽劃分，計(jì)算每個(gè)簇的質(zhì)心,,重新計(jì)算模糊偽劃分，即,wij,,Until,質(zhì)心不發(fā)生變化,,FCM,的結(jié)構(gòu)類似于,K,均值。,K,均值可以看作,FCM,的特例。,,K,均值在初始化之后，交替地更新質(zhì)心和指派每個(gè)對象到最近的質(zhì)心。具體地說，計(jì)算模糊偽劃分等價(jià)于指派步驟。,,與,k,均值一樣，,FCM,可以解釋為試圖最小化誤差的平方和（,SSE,），盡管,FCM,基于,SSE,的模糊版本。,,,計(jì)算,SSE,,公式：,,,其中,cj,是第,j,個(gè)簇的質(zhì)心，而,p,是確定權(quán)值影響的指數(shù)，在,1,和,∞,之間取值,,初始化,,通常使用隨機(jī)初始化。特殊地，權(quán)值隨機(jī)的選取，同時(shí)限制與任何對象相關(guān)聯(lián)的權(quán)值之和等于,1,。,,計(jì)算質(zhì)心,,,公式：,,,,模糊質(zhì)心的定義類似于傳統(tǒng)的質(zhì)心定義，不同之處在于所有點(diǎn)都考慮，并且每個(gè)點(diǎn)對質(zhì)心的貢獻(xiàn)要根據(jù)它的隸屬度加權(quán)。,,,,更新模糊偽劃分,,,,公式,:,,,,如果,p>2,，則該指數(shù)降低賦予離點(diǎn)最近的簇的權(quán)值。事實(shí)上，隨著,p,趨向于無窮大，該指數(shù)趨向于,0,，而權(quán)值趨向于,1/k,。,,另一方面，隨著,p,趨向于,1,，該指數(shù)加大賦予離點(diǎn)最近的簇的權(quán)值。隨著,p,趨向于,1,，關(guān)于最近簇的隸屬權(quán)值趨向于,1,，而關(guān)于其他簇的隸屬權(quán)值趨向于,0,。這時(shí)對應(yīng)于,k,均值。,,例子：三個(gè)圓形簇上的模糊,c,均值,優(yōu)點(diǎn)與局限性,FCM,產(chǎn)生指示任意點(diǎn)屬于任意簇的程度的聚類。,,它比,K,均值算法計(jì)算復(fù)雜性高。,,除此之外，它與,k,均值算法具有相同的優(yōu)點(diǎn)和缺點(diǎn)。,基于原型的聚類,模糊聚類,,,使用混合模型的聚類,,,自組織映射,使用混合模型的聚類,基于統(tǒng)計(jì)模型的聚類。通常，假定數(shù)據(jù)是由一個(gè)統(tǒng)計(jì)過程產(chǎn)生的，并且通過找出最佳擬合數(shù)據(jù)的統(tǒng)計(jì)模型來描述數(shù)據(jù)，其中統(tǒng)計(jì)模型用分布和該分布的一組參數(shù)描述。,,混合模型（,mixture models,）：它使用若干統(tǒng)計(jì)分布對數(shù)據(jù)建模。每個(gè)分布對應(yīng)于一個(gè)簇，而每個(gè)分布的參數(shù)提供對應(yīng)于簇的描述，通常用中心和發(fā)散描述。,,算法,估計(jì)數(shù)據(jù)分布：,,確定分布：一般假設(shè)數(shù)據(jù)取自高斯混合分布。然后，對分布的參數(shù)進(jìn)行估計(jì)：利用,EM,算法進(jìn)行最大似然估計(jì),,利用直方圖估計(jì)分布,,對分布進(jìn)行劃分、分離。每個(gè)分布對應(yīng)于一個(gè)簇。,,,,優(yōu)點(diǎn)和缺點(diǎn),混合模型比,k,均值或模糊,c,均值更一般，因?yàn)樗梢允褂酶鞣N類型的分布。,,利用簡單的估計(jì)分布的方法（如直方圖）可能會(huì)錯(cuò)誤估計(jì)數(shù)據(jù)的原始分布，導(dǎo)致結(jié)果不好。,,利用復(fù)雜的方法（如,EM,算法），計(jì)算復(fù)雜性會(huì)大大增加。,基于原型的聚類,模糊聚類,,,使用混合模型的聚類,,,自組織映射,自組織映射,Kohonen,自組織特征映射（,SOFM,或,SOM,）是一種基于神經(jīng)網(wǎng)絡(luò)觀點(diǎn)的聚類和數(shù)據(jù)可視化技術(shù)。,,盡管,SOM,源于神經(jīng)網(wǎng)絡(luò)，但是它可以表示成一種基于原形的聚類的變形。,,與其他基于質(zhì)心的聚類技術(shù)一樣，,SOM,的目標(biāo)是發(fā)現(xiàn)質(zhì)心的集合，并將數(shù)據(jù)集中的每個(gè)對象指派到提供該對象最佳近似的質(zhì)心。用神經(jīng)網(wǎng)絡(luò)的術(shù)語，每個(gè)質(zhì)心都與一個(gè)神經(jīng)元相關(guān)聯(lián)。,SOM,算法,初始化質(zhì)心。,,Repeat,,,選擇下一個(gè)對象,,,確定到該對象最近的質(zhì)心,,,更新該質(zhì)心和附近的質(zhì)心，即在一個(gè)特定鄰域,,內(nèi)的質(zhì)心,,Until,質(zhì)心改變不多或超過某個(gè)域值,,指派每個(gè)對象到最近的質(zhì)心，并返回質(zhì)心和簇,基于密度的聚類,基于網(wǎng)格的聚類,,,子空間聚類,,,DENCLUE,基于網(wǎng)格的聚類,網(wǎng)格是一種組織數(shù)據(jù)集的有效方法，至少在低維空間中如此。,,其基本思想是，將每個(gè)屬性的可能值分割成許多相鄰的區(qū)間，創(chuàng)建網(wǎng)格單元的集合。每個(gè)對象落入一個(gè)網(wǎng)格單元，網(wǎng)格單元對應(yīng)的屬性區(qū)間包含該對象的值。,,存在許多利用網(wǎng)格進(jìn)行聚類的方法，大部分方法是基于密度的。,例子,基于網(wǎng)格的算法,定義一個(gè)網(wǎng)格單元集,,將對象指派到合適的單元，并計(jì)算每個(gè)單元的密度,,刪除密度低于指定的閾值的單元,,由鄰近的稠密單元組形成簇,,定義網(wǎng)格單元,,對于連續(xù)屬性，定義網(wǎng)格單元相當(dāng)于連續(xù)屬性離散化。可將值劃分為等寬的區(qū)間、等頻的區(qū)間、使用聚類確定的區(qū)間。,,網(wǎng)格單元的密度,,定義網(wǎng)格單元密度的自然方法是：定義網(wǎng)格單元的密度為該區(qū)域中的點(diǎn)數(shù)除以區(qū)域的體積。,,如果使用具有相同體積的網(wǎng)格單元，使得每個(gè)單元的點(diǎn)數(shù)直接度量單元的密度。,,,鄰近的稠密單元組形成簇,,密度閾值的設(shè)定是關(guān)鍵。如圖,9-10,和表,9-2,，如果密度閾值為,9,，則大簇的,4,個(gè)部分將丟失。,,鄰近單元？一個(gè)二維網(wǎng)格單元有,4,個(gè)還是,8,個(gè)鄰接單元？,例子,優(yōu)點(diǎn)與局限性,算法運(yùn)行速度較快，可達(dá),o(mlogm),。這使得它成為許多聚類算法的基礎(chǔ)，如,STING,、,GRIDCLUS,、,waveCluster,、,Bang-Clustering,、,CLIQUE,和,MAFIA,。,,網(wǎng)格單元形狀選擇影響聚類效果。如矩形網(wǎng)格單元不能準(zhǔn)確地捕獲圓形邊界區(qū)域的密度。,,對于高維數(shù)據(jù)，基于網(wǎng)格的聚類效果較差。,,密度閾值的選擇對算法效果影響較大。,,基于密度的聚類,基于網(wǎng)格的聚類,,,子空間聚類,,,DENCLUE,,迄今為止，所考慮的聚類技術(shù)都是使用所有的屬性來發(fā)現(xiàn)簇。然而，如果僅考慮特征子集，則我們發(fā)現(xiàn)的簇可能因子空間不同而很不相同。,,有兩個(gè)理由，子空間的簇可能是有趣的。,,數(shù)據(jù)關(guān)于少量屬性的集合可能可以聚類，而關(guān)于其余屬性是隨機(jī)分布的。,,在某些情況下，在不同的維集合中存在不同的簇。,,例子：考慮記錄不同時(shí)間、不同商品銷售情況的數(shù)據(jù)集（時(shí)間是維，商品是對象）。某些商品對于特定的月份集（如夏天）可能表現(xiàn)出類似行為，但是不同的簇可能被不同的月份（維）刻畫。,,,CLIQUE,算法,CLIQUE,（,Clustering In QUEst,）是系統(tǒng)地發(fā)現(xiàn)子空間簇的基于網(wǎng)格的聚類算法。檢查每個(gè)子空間尋找簇是不現(xiàn)實(shí)的，因?yàn)檫@樣的子空間的數(shù)量是維度的指數(shù)。,,基于密度的簇的單調(diào)性：如果一個(gè)點(diǎn)集在,k,維上形成一個(gè)基于密度的簇，則相同的點(diǎn)集在這些維的所有可能的子集上也是基于密度的簇的一部分。,CLIQUE,算法,找出對應(yīng)于每個(gè)屬性的一維空間中的所有稠密區(qū)域。這是稠密的一維單元的集合。,,K,?2,,Repeat,,,由稠密的,k-1,維單元產(chǎn)生所有的候選稠密,k,維單元,,,刪除點(diǎn)數(shù)少于域值的單元,,k?k+1,,Until,不存在候選稠密,k,維單元,,通過取所有鄰接的、高密度的單元的并發(fā)現(xiàn)簇,,使用一小組描述簇中單元的屬性值域的不等式概括每一個(gè)簇。,CLIQUE,的優(yōu)點(diǎn)與局限性,CLIQUE,最大特點(diǎn)是，它提供了一種搜索子空間發(fā)現(xiàn)簇的有效技術(shù)。由于這種方法基于關(guān)聯(lián)分析的先驗(yàn)原理，它的性質(zhì)能夠被很好地解釋。,,CLIQUE,能夠用一小組不等式概括構(gòu)成一個(gè)簇的單元列表。,,CLIQUE,的局限性與其他基于密度的方法和,Apriori,算法相同。如，,CLIQUE,發(fā)現(xiàn)的簇可以共享對象。允許簇重疊可能大幅度增加簇的個(gè)數(shù)，并使得解釋更加困難。,Apriori,具有指數(shù)級的復(fù)雜度。,基于密度的聚類,基于網(wǎng)格的聚類,,,子空間聚類,,,DENCLUE,DENCLUE,：基于密度聚類的一種基于核的方案,DENCLUE(DENsity CLUstEring),是一種基于密度的聚類方法，它用與每個(gè)點(diǎn)相關(guān)聯(lián)的影響函數(shù)之和對點(diǎn)集的總密度建模。結(jié)果總密度函數(shù)將具有局部尖峰，并且這些局部尖峰用來以自然的方式定義簇。,,具體的說，對于每個(gè)數(shù)據(jù)點(diǎn)，一個(gè)爬山過程找出與該點(diǎn)相關(guān)聯(lián)的最近的尖峰，并且與一個(gè)特定的尖峰（稱作局部密度吸引點(diǎn)（,local density attractor,））相關(guān)聯(lián)的所有數(shù)據(jù)點(diǎn)成為一個(gè)簇。,,如果局部尖峰處的密度太低，則相關(guān)聯(lián)的簇中的點(diǎn)將被視為噪聲而丟棄。,,如果一個(gè)局部尖峰通過一條數(shù)據(jù)點(diǎn)路徑與另一個(gè)局部尖峰相連接，并且該路徑上每個(gè)點(diǎn)的密度都高于最小密度閾值，則與這些局部尖峰相關(guān)聯(lián)的簇合并在一起。,,DENCLUE,算法,對數(shù)據(jù)點(diǎn)占據(jù)的空間推導(dǎo)密度函數(shù),,識別局部最大點(diǎn)（即密度吸引點(diǎn)）,,通過沿密度增長最大的方向移動(dòng)，將每個(gè)點(diǎn)關(guān)聯(lián)到一個(gè)密度吸引點(diǎn),,定義與特定的密度吸引點(diǎn)相關(guān)聯(lián)的點(diǎn)構(gòu)成的簇,,丟棄密度吸引點(diǎn)的密度小于用戶指定閾值的簇,,合并通過密度大于或等于閾值的點(diǎn)路徑連接的簇,,核密度估計(jì),核密度估計(jì)用函數(shù)描述數(shù)據(jù)的分布。每個(gè)點(diǎn)對總密度函數(shù)的貢獻(xiàn)用一個(gè)核函數(shù)表示?？偯芏群瘮?shù)僅僅是與每個(gè)點(diǎn)相關(guān)聯(lián)的核函數(shù)之核,,核函數(shù)是對稱的，并且它的值隨到點(diǎn)的距離增加而下降。高斯函數(shù)常常用作核函數(shù)：,,DENCLUE,的優(yōu)點(diǎn)與局限性,DENCLUE,具有堅(jiān)實(shí)的理論基礎(chǔ)，因?yàn)樗诮y(tǒng)計(jì)學(xué)發(fā)展完善的領(lǐng)域,-----,核密度函數(shù)和核密度估計(jì)。因此，,DENCLUE,提供了比其他基于網(wǎng)絡(luò)的聚類技術(shù)和,DBSCAN,更加靈活、更加精確的計(jì)算密度的方法。（,DBSCAN,是,DENCLUE,的特例）,,基于核密度函數(shù)的方法本質(zhì)上是計(jì)算昂貴的，但,DENCLUE,使用基于網(wǎng)格的技術(shù)來處理該問題。盡管如此，,DENCLUE,可能比其他基于密度的聚類技術(shù)的計(jì)算開銷更大。,,DENCLUE,具有其他基于密度的方法的優(yōu)缺點(diǎn)。,,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,稀疏化,m,個(gè)數(shù)據(jù)點(diǎn)的,m×m,鄰近度矩陣可以用一個(gè)稠密圖表示，每個(gè)節(jié)點(diǎn)與其他所有點(diǎn)相連，權(quán)值反映鄰近性。,,盡管每個(gè)對象與其他每個(gè)對象都有某種程度的近鄰性，但是對于大部分?jǐn)?shù)據(jù)集，對象只與少量對象高度相似，而與大部分其他對象的相似性很弱。這一性質(zhì)用來稀疏化鄰近度圖。,,稀疏化可以這樣進(jìn)行：斷開相似度低于指定閾值的邊、或僅保留連接到點(diǎn)的,k,個(gè)近鄰的邊。,稀疏化的好處,壓縮了數(shù)據(jù)量,,可以更好的聚類,,稀疏化技術(shù)保持了對象與最近鄰的連接，斷開與較遠(yuǎn)對象的連接。這與最近鄰原理一致，對象的最近鄰趨向于與對象在同一個(gè)類。這降低了噪聲和離群點(diǎn)的影響，增強(qiáng)了簇之間的差別。,,可以使用圖劃分算法,,應(yīng)當(dāng)把鄰近度圖的稀疏化看成使用實(shí)際聚類算法之前的初始化步驟。,,理論上講，一個(gè)完美的稀疏化應(yīng)當(dāng)將鄰近度圖劃分成對應(yīng)于期望簇的連通分支，但實(shí)際中這很難做到。很容易出現(xiàn)單條邊連接兩個(gè)簇，或者單個(gè)簇被分裂成若干個(gè)不相連接的子簇的情況。,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,最小生成樹聚類（,minimum spanning tree,，,MST,）,計(jì)算相異度圖的最小生成樹,,Repeat,,,斷開對應(yīng)于最大相異度的邊，創(chuàng)建一個(gè)新的簇,,Until,只剩下單個(gè)簇,,,最小生成樹聚類是一種基于分裂的層次聚類算法,,最小生成樹聚類可以看作用稀疏化找出簇的方法,,,,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,OPOSSUM,：使用,METIS,的稀疏相似度最優(yōu)劃分,OPOSSUM,（,Optimal Partitioning of Sparse Similarities Using METIS,）是一種專門為諸如文檔或購物籃數(shù)據(jù)等稀疏、高維數(shù)據(jù)設(shè)計(jì)的聚類技術(shù)。與,MST,一樣，它基于鄰近度圖的稀疏化進(jìn)行聚類。然而，,OPOSSUM,使用,METIS,算法，該算法是專門為劃分圖設(shè)計(jì)的。,,OPOSSUM,聚類算法,,1,：計(jì)算稀疏化的相似度圖,,2,：使用,METIS,，將相似度圖劃分成,k,個(gè)不同的分支（簇）,,所使用的相似性度量是適合于稀疏、高維數(shù)據(jù)的度量，如擴(kuò)充的,Jaccard,度量或余弦度量。,,METIS,圖劃分程序?qū)⑾∈鑸D劃分為,k,個(gè)不同的分支，其中,k,是用戶指定的參數(shù)，旨在（,1,）最小化分支之間邊的權(quán)值（,2,）實(shí)現(xiàn)平衡約束。,OPOSSUM,使用如下兩種約束中的一種：（,1,）每個(gè)簇中的對象個(gè)數(shù)必須粗略相等，或（,2,）屬性值的和必須粗略相等。,優(yōu)點(diǎn)與缺點(diǎn),OPOSSUM,簡單、速度快。,,它將數(shù)據(jù)劃分大小粗略相等的簇。根據(jù)聚類的目標(biāo)這可能看作優(yōu)點(diǎn)或缺點(diǎn)。,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,Chameleon,,,Chameleon,是一種凝聚聚類技術(shù)，它解決前兩段提到的問題。它將數(shù)據(jù)的初始劃分與一種新穎的層次聚類方案相結(jié)合。,,這種層次聚類使用接近性和互連性概念以及簇的局部建模。關(guān)鍵思想是：僅當(dāng)合并后的結(jié)果簇類似于原來的兩個(gè)簇時(shí)，這兩個(gè)簇才應(yīng)當(dāng)合并。,確定合并哪些簇,相對接近度（,relative closeness,，,RC,）：是被簇的內(nèi)部接近度規(guī)范化的兩個(gè)簇的絕對接近度。兩個(gè)簇合并，僅當(dāng)結(jié)果簇中的點(diǎn)之間的接近程度幾乎與原來的每個(gè)簇一樣。,,,,,,,mi,和,mj,分別是簇,ci,和,cj,的大小。,SEC,（,ci,，,cj,）是連接簇,ci,和,cj,的邊的平均值；,SEC,（,ci,）是二分簇,ci,的邊的平均權(quán)值。,,相對互連度（,relative interconnectivity, RI,）：是被簇的內(nèi)部互連度規(guī)范化的兩個(gè)簇的絕對互連度。如果結(jié)果簇中的點(diǎn)之間的連接幾乎與原來的每個(gè)簇一樣強(qiáng)，兩個(gè)簇合并。,,,,,,其中，,EC,（,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 interconnectivity schemes will merge (c) and (d),Chameleon,算法,構(gòu)造,k-,最近鄰圖,,使用多層圖劃分算法劃分圖,,Repeat,,,合并關(guān)于相對互連性和相對接近性而言，最好,,地保持簇的自相似性的簇,,Until,不再有可以合并的簇,例子,,,優(yōu)點(diǎn)與局限性,Chameleon,能夠有效地聚類空間數(shù)據(jù)，即便存在噪聲和離群點(diǎn)，并且簇具有不同的形狀、大小和密度。,,Chameleon,假定由稀疏化和圖劃分過程產(chǎn)生的對象組群是子簇，即一個(gè)劃分中的大部分點(diǎn)屬于同一個(gè)真正的簇。如果不是，則凝聚層次聚類將混合這些錯(cuò)誤，因?yàn)樗^對不可能再將已經(jīng)錯(cuò)誤地放到一起的對象分開。這樣，當(dāng)劃分過程未產(chǎn)生子簇時(shí)，,chameleon,就有問題，對于高維數(shù)據(jù)，常常出現(xiàn)這種情況。,共享最近鄰相似性,SNN,（,shared nearest neighbor,）相似度計(jì)算：,,1.,找出所有點(diǎn)的,k-,近鄰,,2.If,兩個(gè)點(diǎn),x,和,y,不是相互在對方的,k-,最近鄰中,then,,3. similarity(x,y),?0,,4.Else,,5.,,similarity(x,y)?,共享的近鄰個(gè)數(shù),,6.End if,,,SNN,相似度由于通過使用共享最近鄰的個(gè)數(shù)考慮了對象的環(huán)境，,SNN,相似度可以處理一個(gè)對象碰巧與另一對象相對接近，但屬于不同的類。在這種情況下，對象一般不共享許多近鄰，并且它們的,SNN,相似度低。,,SSN,相似度也能處理變密度簇的問題。在低密度區(qū)域，對象比高密度區(qū)域的對象分開得更遠(yuǎn)。然而，一對點(diǎn)之間的,SNN,相似度只依賴于兩個(gè)對象共享的最近鄰的個(gè)數(shù)，而不是這些近鄰之間的相距多遠(yuǎn)。,SNN,關(guān)于點(diǎn)的密度進(jìn)行自動(dòng)縮放。,基于圖的聚類,最小生成樹聚類,,OPOSSUM,,Chameleon,,Jarvis-Patrick,聚類算法,,基于,SNN,密度的聚類,Jarvis-Patrick,（,JP,）聚類算法,計(jì)算,SNN,相似度圖,,使用相似度閾值，稀疏化,SNN,相似度圖,,找出稀疏化的,SNN,相似度圖的連通分支,,優(yōu)點(diǎn)與局限性,因?yàn)?JP,聚類基于,SNN,相似度概念，它擅長于處理噪聲和離群點(diǎn)，并且能夠處理不同大小、形狀和密度的簇。,,該算法對高維數(shù)據(jù)效果良好，尤其擅長發(fā)現(xiàn)強(qiáng)相關(guān)對象的緊密簇。,,JP,聚類把簇定義為,SNN,相似度圖的連通分支。這樣，一個(gè)對象集是分裂成兩個(gè)簇還是作為一個(gè)簇留下，可能依賴于一條鏈。,,基于,SNN,密度的聚類,算法：,,計(jì)算,SNN,相似度圖,,以用戶指定的參數(shù),Eps,和,MinPts,，使用,DBSCAN,,,SNN,密度的聚類算法比,Jarvis-Patrick,聚類或,DBSCAN,更加靈活。,,不象,DBSCAN,，它可以用于高維數(shù)據(jù)和簇具有不同密度的情況。,,不象,Jarvis-Patrick,聚類簡單地使用域值，然后取連通分支作為簇，基于,SNN,密度的聚類使用基于,SNN,密度和核心點(diǎn)概念的方法。,,核心點(diǎn)：一個(gè)點(diǎn)是核心點(diǎn)，如果在該點(diǎn)給定鄰域內(nèi)的點(diǎn)數(shù)超過某個(gè)閾值,MinPts,。,,邊界點(diǎn)。邊界點(diǎn)不是核心點(diǎn)，但是它落在一個(gè)核心點(diǎn)的鄰域內(nèi)。,,噪聲點(diǎn)是既非核心點(diǎn)，也非邊界點(diǎn)的任何點(diǎn)。,SNN Density,,a) All Points b) High SNN Density,c) Medium SNN Density d) Low SNN Density,例子：解釋該算法處理高維數(shù)據(jù)能力,SNN Clusters of SLP.,SNN Density of Points on the Globe.,41,年期間，在,2.5,度的經(jīng)緯度網(wǎng)格的每個(gè)點(diǎn)上的月平均海平面氣壓（,SLP,）,優(yōu)點(diǎn)與局限性,基于,SNN,密度的聚類的優(yōu)點(diǎn)與局限性類似于,JP,聚類。,,然而，核心點(diǎn)和,SNN,密度的使用大大增加了該方法的能力和靈活性。,可伸縮：一般問題和方法,BIRCH,,CURE,,如果運(yùn)行時(shí)間長得不可接受，或者需要的存儲量太大，即使最好的聚類算法也沒有多大價(jià)值。,,許多聚類算法所需要的存儲量都是非線性的。例如：使用層次聚類，存儲需求一般是,O(m2),。類似地，有些聚類算法所需要的計(jì)算量也是非線性的。,,可伸縮性可以通過如下技術(shù)實(shí)現(xiàn)：多維或空間存取方法、鄰近度約束、抽樣、劃分?jǐn)?shù)據(jù)對象、匯總、并行與分布計(jì)算。,,CURE,CURE,（,Clustering Using REpresentative,）是一種聚類算法，它使用各種不同的技術(shù)創(chuàng)建一種能夠處理大型數(shù)據(jù)、離群點(diǎn)、具有非球形和非均勻大小的簇的數(shù)據(jù)的方法。,,CURE,使用簇中的多個(gè)代表點(diǎn)來表示一個(gè)簇。理論上，這些點(diǎn)捕獲了簇的幾何形狀。,,具體來說，第一個(gè)代表點(diǎn)選擇離簇中心最遠(yuǎn)的點(diǎn)，而其余的點(diǎn)選擇離所有已經(jīng)選取的點(diǎn)最遠(yuǎn)的點(diǎn)。這樣，代表點(diǎn)相對分離。,,選取的點(diǎn)的個(gè)數(shù)是一個(gè)參數(shù)，但是一般取,>10,效果較好。,,一旦選定代表點(diǎn)，它們就以因子,a,向簇中心收縮。這有助于減輕離群點(diǎn)的影響。,,例如，一個(gè)到中心的距離為,10,個(gè)單位的代表點(diǎn)將移動(dòng),3,個(gè)單位（對于,a=0.7,），而到中心距離為,1,個(gè)單位的代表點(diǎn)僅移動(dòng),0.3,個(gè)單位。,?,,CURE,使用一種凝聚層次聚類方案進(jìn)行實(shí)際的聚類。兩個(gè)簇之間的距離是任意兩個(gè)代表點(diǎn)（在它們向它們代表點(diǎn)的中心收縮之后）之間的最短距離。,,如果,a=0,，它等價(jià)于基于質(zhì)心的層次聚類；,a=1,時(shí)，它與單鏈層次聚類大致相同。,,注意，盡管使用層次聚類方案，但是,CURE,的目標(biāo)是發(fā)現(xiàn)用戶指定個(gè)數(shù)的簇。,,CURE,在聚類過程的兩個(gè)不同階段刪除離群點(diǎn)。首先，如果一個(gè)簇增長緩慢，則這意味它主要由離群點(diǎn)組成，因?yàn)楦鶕?jù)定義，離群點(diǎn)遠(yuǎn)離其他點(diǎn)，并且不會(huì)經(jīng)常與其他點(diǎn)合并。,,在,CURE,中，離群點(diǎn)刪除的第一個(gè)階段一般出現(xiàn)在簇的個(gè)數(shù)是原來點(diǎn)數(shù)的,1/3,時(shí)。第二個(gè)離群點(diǎn)刪除階段出現(xiàn)在簇的個(gè)數(shù)達(dá)到,K,的量級時(shí)。此時(shí)，小簇又被刪除。,,CURE,在最壞情況下復(fù)雜度為,O(m,2,logm),，它不能直接用于大型數(shù)據(jù)集。因此，,CURE,使用了兩種技術(shù)來加快聚類過程。,,第一種技術(shù)是取隨機(jī)樣本，并在抽樣的數(shù)據(jù)點(diǎn)上進(jìn)行層次聚類。隨后是最終掃描，將數(shù)據(jù)集中剩余的點(diǎn)指派到簇中。,,在某些情況下，聚類所需要的樣本仍然太大，需要第二種技術(shù)解決。在這種情況下，,CURE,劃分樣本數(shù)據(jù)，然后聚類每個(gè)劃分中的點(diǎn)。這種預(yù)聚類步后通常緊隨中間簇的聚類，以及將數(shù)據(jù)集中的每個(gè)點(diǎn)指派到一個(gè)簇的最終掃描。,CURE,算法,由數(shù)據(jù)集抽取一個(gè)隨機(jī)樣本集。,,將樣本集劃分成,p,個(gè)大小相同的劃分。,,使用,CURE,的層次聚類算法，將每個(gè)劃分中的點(diǎn)聚類成,m/pq,個(gè)簇，得到總共,m/q,個(gè)簇。,,使用,CURE,的層次聚類算法對上一步發(fā)現(xiàn)的,m/q,個(gè)簇進(jìn)行聚類，直到只剩下,k,個(gè)簇。,,刪除離群點(diǎn)。,,將所有剩余的數(shù)據(jù)點(diǎn)指派到最近的簇，得到完全聚類。,,K,是期望的簇個(gè)數(shù)，,m,是點(diǎn)的個(gè)數(shù)，,p,是劃分的個(gè)數(shù)，而,q,是一個(gè)劃分中的點(diǎn)的期望壓縮，即一個(gè)劃分中的簇的個(gè)數(shù)是,m/pq,，簇的總數(shù)是,m/q,,例如，如果,m=10000,，,p=10,并且,q=100,，則每個(gè)劃分包含,10000/10=1000,個(gè)點(diǎn)，每個(gè)劃分有,1000/100=10,個(gè)簇，而總共有,10000/100=100,個(gè)簇。,CURE,的抽樣,CURE,抽樣盡力確保抽到每個(gè)簇的樣本。為了保證這樣的抽樣，,CURE,的作者推算出了能夠?qū)崿F(xiàn)這一保證的樣本集大小的上界。,,,,,,S,為我們應(yīng)該抽取的樣本大小,,假設(shè)有,100000,個(gè)對象，我們的目標(biāo)是以,80%,的可能性得到,10%,的,Ci,簇對象，其中,Ci,的大小是,1000,。在此情況下，,f=0.1,，,δ,=0.2,，,m=100000,，這樣,s=11962,。,,S=11962,是為了以,80%,的概率得到,10%,的,Ci,簇對象，需要抽取的樣本大小,,劃分,將點(diǎn)劃分成,p,個(gè)大小為,m/p,的組，使用,CURE,對每個(gè)劃分聚類，將對象的個(gè)數(shù)壓縮一個(gè)因子,q>1,,其中,q,可以粗略地看作劃分中的簇的平均大小?？偣伯a(chǎn)生,m/q,個(gè)簇。然后，預(yù)聚類后隨,m/q,個(gè)中間簇的最終聚類，產(chǎn)生期望的簇個(gè)數(shù)。兩遍聚類都使用,CURE,的層次聚類算法，而最后一遍將數(shù)據(jù)集中的每個(gè)點(diǎn)指派到一個(gè)簇。,,P,和,q,的選取是關(guān)鍵。應(yīng)盡力選擇合適的,p,，使得整個(gè)劃分可以以合理的時(shí)間在內(nèi)存處理。此外，應(yīng)盡力選擇合適的,p,和,q,使得同一基本簇的對象最終在一個(gè)簇中。,A subnetwork 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ù)集和屬性的特征噪聲和離群點(diǎn),,數(shù)據(jù)對象的個(gè)數(shù),,屬性的個(gè)數(shù),,簇描述,,算法考慮,,,數(shù)據(jù),,探索數(shù)據(jù),,分類：基本概念、決策樹與模型評估,,分類：其他技術(shù),,關(guān)聯(lián)分析：基本概念和算法,,關(guān)聯(lián)分析：高級概念,,聚類分析：基本概念和算法,,聚類分析：附加問題與算法,,異常檢測,