附加問題與算法ppt課件

1、聚類分析：附加的問題與算法聚類分析：附加的問題與算法第第9章章 聚類分析：附加的問題與算法聚類分析：附加的問題與算法l在各種領域，針對不同的運用類型，曾經開發(fā)了大量聚類算法。在這些算法中沒有一種算法可以順應一切的數(shù)據(jù)類型、簇和運用。l現(xiàn)實上，對于更加有效或者更適宜特定數(shù)據(jù)類型、簇和運用的新的聚類算法，看來總是有進一步的開發(fā)空間。l我們只能說我們曾經有了一些技術，對于某些情況運轉良好。其緣由是，在許多情況下，對于什么是一個好的簇集，依然憑客觀解釋。此外，當運用客觀度量準確地定義簇時，發(fā)現(xiàn)最優(yōu)聚類問題經常是計算不可行的。比較比較k均值和均值和DBSCANlDBSCAN和k均值都是將每個對象指派到單

2、個簇的劃分聚類算法，但是K均值普通聚類一切對象，而DBSCAN丟棄被它辨以為噪聲的對象。lK均值運用簇的基于原形的概念，而DBSCAN運用基于密度的概念。lDBSCAN可以處置不同大小和不同外形的簇，并且不太受噪聲和離群點的影響。K均值很難處置非球狀的簇和不同大小的簇。當簇具有很不同的密度時，兩種算法的性能都很差。lK均值只能用于具有明確定義的質心如均值或中位數(shù)的數(shù)據(jù)。DBSCAN要求密度定義基于傳統(tǒng)的歐幾里得密度概念對于數(shù)據(jù)是有意義的。lK均值可以用于稀疏的高維數(shù)據(jù)，如文檔數(shù)據(jù)，DBSCAN通常在這類數(shù)據(jù)上性能很差，由于對于高維數(shù)據(jù)，傳統(tǒng)的歐幾里得密度定義不能很益處置。lK均值和DBSCAN

3、的最初版本都是針對歐幾里得數(shù)據(jù)設計的，但是它們都被擴展，以便處置其他類型的數(shù)據(jù)。lDBSCAN不對數(shù)據(jù)的分布做任何假定。根本k均值算法等價于一種統(tǒng)計聚類方法混合模型，假定一切的簇都來自球形高斯分布，具有不同的均值，但具有一樣的斜方差矩陣。lDBSCAN和k均值都尋覓運用一切屬性的簇，即它們都不尋覓能夠只涉及某個屬性子集的簇。lK均值可以發(fā)現(xiàn)不是明顯分別的簇，即使簇有重疊也可以發(fā)現(xiàn)，但是DBSCAN會合并有重疊的簇。lK均值算法的時間復雜度是Om，而DBSCAN的時間復雜度是Om2.lDBSCAN多次運轉產生一樣的結果，而k均值通常運用隨機初始化質心，不會產生一樣的結果。lDBSCAN自動地確定

4、簇個數(shù)；對于k均值，簇個數(shù)需求作為參數(shù)指定。然而，DBSCAN必需指定另外兩個參數(shù)：Eps和MinptslK均值聚類可以看作優(yōu)化問題，即最小化每個點到最近的質心的誤差的平方和，并且可以看作一種統(tǒng)計聚類的特例。DBSCAN不基于任何方式化模型。數(shù)據(jù)特性數(shù)據(jù)特性l高維性l隨著維度的添加，體積迅速添加，除非點的個數(shù)也隨著維度指數(shù)添加，否那么密度將趨向于0.l處置該問題的方法是運用維歸約技術l規(guī)模l許多聚類算法對于小規(guī)模和中等規(guī)模的數(shù)據(jù)集運轉良好，但是不能處置大型數(shù)據(jù)集l稀疏性l稀疏數(shù)據(jù)通常由非對稱的屬性組成，其中零值沒有非零值重要。.l噪聲和離群點l非常見點能夠嚴重地降低聚類算法的性能，特別是k均值

5、這樣的基于原型的算法l另一方面，噪聲也能夠導致單鏈等技術合并兩個不該當合并的簇。l屬性和數(shù)據(jù)集類型l屬性能夠是分類的標稱的或序數(shù)的或定量的區(qū)間的或比率的，二元的、離散的或延續(xù)的。l不同的近鄰性和密度度量適宜于不同類型的數(shù)據(jù)。l尺度l不同的屬性，如高度和分量，能夠用不同的尺度度量。這些差別能夠嚴重影響兩個對象之間的間隔或類似性，從而影響聚類分析的結果。簇特性簇特性l數(shù)據(jù)分布l某些聚類技術假定數(shù)據(jù)具有特定的分布。更詳細的說，它們經常假定可以用混合分布對數(shù)據(jù)建模，其中每個簇對應于一個分布。l外形l有些簇具有規(guī)那么的外形，如矩形和球形。但是，更普通地，簇可以具有任不測形。l如DBSCAN和單鏈等技術可

6、以處置任不測形。基于原型的方法和一些層次聚類技術不能進展這樣的處置。lChameleon和cure是專門用來處置這一問題的技術l不同大小l許多聚類算法，如k均值，當簇具有不同的大小時不能很好的處置l不同密度l具有很不一樣的密度的簇能夠對諸如DBSCAN和k均值等算法呵斥影響l基于SNN密度的聚類技術可以處置這個問題l無明顯分別的簇l當簇接觸或重疊時，有些聚類技術將該當分開的簇合并。甚至有些發(fā)現(xiàn)不同簇的技術隨意地將點指派到一個或另一個簇。l模糊聚類可以處置這一問題l簇之間的聯(lián)絡l在大部分聚類技術中，都不思索簇之間的聯(lián)絡，如簇的相對位置l自組織映射SOM是一種在聚類期間直接思索簇之間聯(lián)絡的聚類技術

7、。l子空間簇l簇能夠只在維屬性的一個子集中存在，并且運用一個維集合確定的簇能夠也運用另一個維確定的簇很不一樣。聚類算法的普通特征聚類算法的普通特征l次序依賴性l對于某些算法，所產生的簇的質量和個數(shù)能夠因數(shù)據(jù)處置的次序不同而顯著地變化。如SOMl非確定性l有些算法不是次序依賴的，但是它們每次運轉都產生不同的結果，由于它們依賴于需求隨機選擇的初始化步驟。l變換聚類問題到其他領域l將聚類問題映射到一個不同的領域。如，基于圖的聚類l可伸縮性l包含數(shù)以百萬計對象的數(shù)據(jù)集并不稀有，而用于這種數(shù)據(jù)集的聚類算法該當具有線性或接近線性的時間或空間復雜度。l對于大型數(shù)據(jù)集，即使具有O(m2)復雜度也是不真實踐的。

8、l此外，數(shù)據(jù)集聚類技術不能總是假定數(shù)據(jù)放在內存，或者數(shù)據(jù)元素可以隨機的訪問。這樣的算法對于大型數(shù)據(jù)集是不可行的。l參數(shù)選擇l大部分聚類算法需求用戶設置一個或多個參數(shù)。選擇適宜的參數(shù)值能夠是困難的；因此，通常的態(tài)度是“參數(shù)越少越好。l將聚類作為最優(yōu)化問題處置l聚類經常被看作優(yōu)化問題。將點劃分成簇，根據(jù)用戶指定的目的函數(shù)度量，最大化結果簇集合的優(yōu)良度。如k均值試圖發(fā)現(xiàn)簇的集合，使得每個點到最近的簇質心間隔的平方和最小。基于原型的聚類基于原型的聚類l模糊聚類l運用混合模型的聚類l自組織映射模糊聚類模糊聚類l模糊集合l1965年，Lotfi Zadeh引進模糊集合論fuzzy set theory和模

9、糊邏輯fuzzy logic作為一種處置不準確和不確定性的方法。l簡要的說，模糊集合論允許對象以0和1之間的某個隸屬度屬于一個集合，而模糊邏輯允許一個陳說以0和1之間確實定度為真。l傳統(tǒng)的集合論和邏輯是對應的模糊集合論和模糊邏輯的特殊情況，它們限制集合的隸屬度或確定度或者為0，或者為1.l思索如下模糊邏輯的例子l陳說“天空多云為真的程度可以定義為天空被云覆蓋的百分比。例如，天空的50%被云覆蓋，那么“天空多云為真的程度是0.5。l假設我們有兩個集合“多云天和“非多云天，那么我們可以類似地賦予每一天隸屬于這兩個集合的程度。l這樣，假設一天25%多云，那么它在“多云天集合中具有0.25的隸屬度，而

10、在“非多云天集合中具有0.75的隸屬度。l模糊簇l假定我們有一個數(shù)據(jù)點的集合X=x1,x2,xm，其中每個點xi是一個n維點，即xi=xi1,xi2,xin) 。模糊簇集C1,C2,Ck是X的一切能夠模糊子集的一個子集。l這簡單地意味著對于每個點xi和每個簇Cj，隸屬權值度wij曾經賦予0和1之間的值。l然而，我們還想將以下合理的條件施加在簇上，以確定簇構成模糊偽劃分fuzzy psuedo-partition。l給定點xi的一切權值之和為1：l每個簇Cj以非零權值至少包含一個點，但不以權值1包含一切的點kjwij11mwijmi10l雖然存在多種模糊聚類，我們只思索k均值的模糊版本，稱作模糊

11、c均值。l在聚類文獻中，那些不采用簇質心增量更新方法的k均值版本有時稱為c均值。模糊c均值算法有時稱為FCMl算法9.1 根本模糊c均值算法l選擇一個初始模糊偽劃分，即對一切的wij賦值lRepeatl 運用模糊偽劃分，計算每個簇的質心l 重新計算模糊偽劃分，即wijlUntil 質心不發(fā)生變化lFCM的構造類似于K均值。 K均值可以看作FCM的特例。lK均值在初始化之后，交替地更新質心和指派每個對象到最近的質心。詳細地說，計算模糊偽劃分等價于指派步驟。l與k均值一樣，F(xiàn)CM可以解釋為試圖最小化誤差的平方和SSE，雖然FCM基于SSE的模糊版本。l計算SSEl公式：l其中cj是第j個簇的質心，

12、而p是確定權值影響的指數(shù)，在1和之間取值l初始化l通常運用隨機初始化。特殊地，權值隨機的選取，同時限制與任何對象相關聯(lián)的權值之和等于1。kjmijipijkcxdistwCCCSSE11221),(),.,(l計算質心l公式：l模糊質心的定義類似于傳統(tǒng)的質心定義，不同之處在于一切點都思索，并且每個點對質心的奉獻要根據(jù)它的隸屬度加權。mipijmiipijjwxwc11l更新模糊偽劃分l公式:l假設p2，那么該指數(shù)降低賦予離點最近的簇的權值?，F(xiàn)實上，隨著p趨向于無窮大，該指數(shù)趨向于0，而權值趨向于1/k。l另一方面，隨著p趨向于1，該指數(shù)加大賦予離點最近的簇的權值。隨著p趨向于1，關于最近簇的隸

13、屬權值趨向于1，而關于其他簇的隸屬權值趨向于0。這時對應于k均值。kqpqipjiijcxdistcxdistw1112112),(/1 (),(/1 (例子：三個圓形簇上的模糊例子：三個圓形簇上的模糊c均值均值優(yōu)點與局限性優(yōu)點與局限性lFCM產生指示恣意點屬于恣意簇的程度的聚類。l它比K均值算法計算復雜性高。l除此之外，它與k均值算法具有一樣的優(yōu)點和缺陷?；谠偷木垲惢谠偷木垲恖模糊聚類l運用混合模型的聚類l自組織映射運用混合模型的聚類運用混合模型的聚類l基于統(tǒng)計模型的聚類。通常，假定數(shù)據(jù)是由一個統(tǒng)計過程產生的，并且經過找出最正確擬合數(shù)據(jù)的統(tǒng)計模型來描畫數(shù)據(jù)，其中統(tǒng)計模型用分布和該分布

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

15、l模糊聚類l運用混合模型的聚類l自組織映射自組織映射自組織映射lKohonen自組織特征映射SOFM或SOM是一種基于神經網(wǎng)絡觀念的聚類和數(shù)據(jù)可視化技術。l雖然SOM源于神經網(wǎng)絡，但是它可以表示成一種基于原形的聚類的變形。l與其他基于質心的聚類技術一樣，SOM的目的是發(fā)現(xiàn)質心的集合，并將數(shù)據(jù)集中的每個對象指派到提供該對象最正確近似的質心。用神經網(wǎng)絡的術語，每個質心都與一個神經元相關聯(lián)。SOM算法算法l初始化質心。lRepeatl 選擇下一個對象l 確定到該對象最近的質心l 更新該質心和附近的質心，即在一個特定鄰域 l 內的質心lUntil 質心改動不多或超越某個域值l指派每個對象到最近的質心，

16、并前往質心和簇基于密度的聚類基于密度的聚類l基于網(wǎng)格的聚類l子空間聚類lDENCLUE基于網(wǎng)格的聚類基于網(wǎng)格的聚類l網(wǎng)格是一種組織數(shù)據(jù)集的有效方法，至少在低維空間中如此。l其根本思想是，將每個屬性的能夠值分割成許多相鄰的區(qū)間，創(chuàng)建網(wǎng)格單元的集合。每個對象落入一個網(wǎng)格單元，網(wǎng)格單元對應的屬性區(qū)間包含該對象的值。l存在許多利用網(wǎng)格進展聚類的方法，大部分方法是基于密度的。例子例子基于網(wǎng)格的算法基于網(wǎng)格的算法l定義一個網(wǎng)格單元集l將對象指派到適宜的單元，并計算每個單元的密度l刪除密度低于指定的閾值的單元l由臨近的稠密單元組構成簇l定義網(wǎng)格單元l對于延續(xù)屬性，定義網(wǎng)格單元相當于延續(xù)屬性離散化?？蓪⒅祫澐?/p>

17、為等寬的區(qū)間、等頻的區(qū)間、運用聚類確定的區(qū)間。l網(wǎng)格單元的密度l定義網(wǎng)格單元密度的自然方法是：定義網(wǎng)格單元的密度為該區(qū)域中的點數(shù)除以區(qū)域的體積。l假設使器具有一樣體積的網(wǎng)格單元，使得每個單元的點數(shù)直接度量單元的密度。l臨近的稠密單元組構成簇l密度閾值的設定是關鍵。如圖9-10和表9-2，假設密度閾值為9，那么大簇的4個部分將喪失。l臨近單元？一個二維網(wǎng)格單元有4個還是8個鄰接單元？例子例子優(yōu)點與局限性優(yōu)點與局限性l算法運轉速度較快，可達o(mlogm)。這使得它成為許多聚類算法的根底，如STING、GRIDCLUS、waveCluster、Bang-Clustering、CLIQUE和MAFI

18、A。l網(wǎng)格單元外形選擇影響聚類效果。如矩形網(wǎng)格單元不能準確地捕獲圓形邊境區(qū)域的密度。l對于高維數(shù)據(jù)，基于網(wǎng)格的聚類效果較差。l密度閾值的選擇對算法效果影響較大?；诿芏鹊木垲惢诿芏鹊木垲恖基于網(wǎng)格的聚類l子空間聚類lDENCLUEl迄今為止，所思索的聚類技術都是運用一切的屬性來發(fā)現(xiàn)簇。然而，假設僅思索特征子集，那么我們發(fā)現(xiàn)的簇能夠因子空間不同而很不一樣。l有兩個理由，子空間的簇能夠是有趣的。l數(shù)據(jù)關于少量屬性的集合能夠可以聚類，而關于其他屬性是隨機分布的。l在某些情況下，在不同的維集合中存在不同的簇。l例子：思索記錄不同時間、不同商品銷售情況的數(shù)據(jù)集時間是維，商品是對象。某些商品對于特定的月

19、份集如夏天能夠表現(xiàn)出類似行為，但是不同的簇能夠被不同的月份維描寫。CLIQUE算法算法lCLIQUEClustering In QUEst是系統(tǒng)地發(fā)現(xiàn)子空間簇的基于網(wǎng)格的聚類算法。檢查每個子空間尋覓簇是不現(xiàn)實的，由于這樣的子空間的數(shù)量是維度的指數(shù)。l基于密度的簇的單調性：假設一個點集在k維上構成一個基于密度的簇，那么一樣的點集在這些維的一切能夠的子集上也是基于密度的簇的一部分。CLIQUE算法算法l找出對應于每個屬性的一維空間中的一切稠密區(qū)域。這是稠密的一維單元的集合。lK2lRepeatl 由稠密的k-1維單元產生一切的候選稠密k維單元l 刪除點數(shù)少于域值的單元l kk+1lUntil 不存

20、在候選稠密k維單元l經過取一切鄰接的、高密度的單元的并發(fā)現(xiàn)簇l運用一小組描畫簇中單元的屬性值域的不等式概括每一個簇。CLIQUE的優(yōu)點與局限性的優(yōu)點與局限性lCLIQUE最大特點是，它提供了一種搜索子空間發(fā)現(xiàn)簇的有效技術。由于這種方法基于關聯(lián)分析的先驗原理，它的性質可以被很好地解釋。lCLIQUE可以用一小組不等式概括構成一個簇的單元列表。lCLIQUE的局限性與其他基于密度的方法和Apriori算法一樣。如，CLIQUE發(fā)現(xiàn)的簇可以共享對象。允許簇重疊能夠大幅度添加簇的個數(shù)，并使得解釋更加困難。Apriori具有指數(shù)級的復雜度。基于密度的聚類基于密度的聚類l基于網(wǎng)格的聚類l子空間聚類lDEN

21、CLUEDENCLUE：基于密度聚類的一種基于核的方案：基于密度聚類的一種基于核的方案lDENCLUE(DENsity CLUstEring)是一種基于密度的聚類方法，它用與每個點相關聯(lián)的影響函數(shù)之和對點集的總密度建模。結果總密度函數(shù)將具有部分尖峰，并且這些部分尖峰用來以自然的方式定義簇。l詳細的說，對于每個數(shù)據(jù)點，一個爬山過程找出與該點相關聯(lián)的最近的尖峰，并且與一個特定的尖峰稱作部分密度吸引點local density attractor相關聯(lián)的一切數(shù)據(jù)點成為一個簇。l假設部分尖峰處的密度太低，那么相關聯(lián)的簇中的點將被視為噪聲而丟棄。l假設一個部分尖峰經過一條數(shù)據(jù)點途徑與另一個部分尖峰相銜接

22、，并且該途徑上每個點的密度都高于最小密度閾值，那么與這些部分尖峰相關聯(lián)的簇合并在一同。DENCLUE算法算法l對數(shù)據(jù)點占據(jù)的空間推導密度函數(shù)l識別部分最大點即密度吸引點l經過沿密度增長最大的方向挪動，將每個點關聯(lián)到一個密度吸引點l定義與特定的密度吸引點相關聯(lián)的點構成的簇l丟棄密度吸引點的密度小于用戶指定閾值的簇l合并經過密度大于或等于閾值的點途徑銜接的簇核密度估計核密度估計l核密度估計用函數(shù)描畫數(shù)據(jù)的分布。每個點對總密度函數(shù)的奉獻用一個核函數(shù)表示?？偯芏群瘮?shù)僅僅是與每個點相關聯(lián)的核函數(shù)之核l核函數(shù)是對稱的，并且它的值隨到點的間隔添加而下降。高斯函數(shù)經常用作核函數(shù)：222/),(tan)(yxc

23、ediseykDENCLUE的優(yōu)點與局限性的優(yōu)點與局限性lDENCLUE具有堅實的實際根底，由于它基于統(tǒng)計學開展完善的領域-核密度函數(shù)和核密度估計。因此，DENCLUE提供了比其他基于網(wǎng)絡的聚類技術和DBSCAN更加靈敏、更加準確的計算密度的方法。DBSCAN是DENCLUE的特例l基于核密度函數(shù)的方法本質上是計算昂貴的，但DENCLUE運用基于網(wǎng)格的技術來處置該問題。雖然如此，DENCLUE能夠比其他基于密度的聚類技術的計算開銷更大。lDENCLUE具有其他基于密度的方法的優(yōu)缺陷?；趫D的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-Patrick聚類算

24、法l基于SNN密度的聚類稀疏化稀疏化lm個數(shù)據(jù)點的mm臨近度矩陣可以用一個稠密圖表示，每個節(jié)點與其他一切點相連，權值反映臨近性。l雖然每個對象與其他每個對象都有某種程度的近鄰性，但是對于大部分數(shù)據(jù)集，對象只與少量對象高度類似，而與大部分其他對象的類似性很弱。這一性質用來稀疏化臨近度圖。l稀疏化可以這樣進展：斷開類似度低于指定閾值的邊、或僅保管銜接到點的k個近鄰的邊。稀疏化的益處稀疏化的益處l緊縮了數(shù)據(jù)量l可以更好的聚類l稀疏化技術堅持了對象與最近鄰的銜接，斷開與較遠對象的銜接。這與最近鄰原理一致，對象的最近鄰趨向于與對象在同一個類。這降低了噪聲和離群點的影響，加強了簇之間的差別。l可以運用圖劃

25、分算法l該當把臨近度圖的稀疏化看成運用實踐聚類算法之前的初始化步驟。l實際上講，一個完美的稀疏化該當將臨近度圖劃分成對應于期望簇的連通分支，但實踐中這很難做到。很容易出現(xiàn)單條邊銜接兩個簇，或者單個簇被分裂成假設干個不相銜接的子簇的情況?；趫D的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-Patrick聚類算法l基于SNN密度的聚類最小生成樹聚類最小生成樹聚類minimum spanning tree，MSTl計算相異度圖的最小生成樹lRepeatl 斷開對應于最大相異度的邊，創(chuàng)建一個新的簇lUntil 只剩下單個簇l最小生成樹聚類是一種基于分裂的層次聚類

26、算法l最小生成樹聚類可以看作用稀疏化找出簇的方法基于圖的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-Patrick聚類算法l基于SNN密度的聚類OPOSSUM：運用：運用METIS的稀疏類似度最優(yōu)劃分的稀疏類似度最優(yōu)劃分lOPOSSUMOptimal Partitioning of Sparse Similarities Using METIS是一種專門為諸如文檔或購物籃數(shù)據(jù)等稀疏、高維數(shù)據(jù)設計的聚類技術。與MST一樣，它基于臨近度圖的稀疏化進展聚類。然而，OPOSSUM運用METIS算法，該算法是專門為劃分圖設計的。lOPOSSUM聚類算法l1：計算稀

27、疏化的類似度圖l2：運用METIS，將類似度圖劃分成k個不同的分支簇 l所運用的類似性度量是適宜于稀疏、高維數(shù)據(jù)的度量，如擴展的Jaccard度量或余弦度量。lMETIS圖劃分程序將稀疏圖劃分為k個不同的分支，其中k是用戶指定的參數(shù)，旨在1最小化分支之間邊的權值2實現(xiàn)平衡約束。OPOSSUM運用如下兩種約束中的一種：1每個簇中的對象個數(shù)必需粗略相等，或2屬性值的和必需粗略相等。優(yōu)點與缺陷優(yōu)點與缺陷lOPOSSUM簡單、速度快。l它將數(shù)據(jù)劃分大小粗略相等的簇。根據(jù)聚類的目的這能夠看作優(yōu)點或缺陷?；趫D的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-Patri

28、ck聚類算法l基于SNN密度的聚類ChameleonlChameleon是一種凝聚聚類技術，它處理前兩段提到的問題。它將數(shù)據(jù)的初始劃分與一種新穎的層次聚類方案相結合。l這種層次聚類運用接近性和互連性概念以及簇的部分建模。關鍵思想是：僅當合并后的結果簇類似于原來的兩個簇時，這兩個簇才該當合并。確定合并哪些簇確定合并哪些簇l相對接近度relative closeness，RC：是被簇的內部接近度規(guī)范化的兩個簇的絕對接近度。兩個簇合并，僅當結果簇中的點之間的接近程度幾乎與原來的每個簇一樣。lmi和mj分別是簇ci和cj的大小。SECci，cj是銜接簇ci和cj的邊的平均值；SECci是二分簇ci的邊

29、的平均權值。)()(),(),(jECjiiiECjiijiECjiCSmmmCSmmmCCSCCRCl相對互連度relative interconnectivity, RI：是被簇的內部互連度規(guī)范化的兩個簇的絕對互連度。假設結果簇中的點之間的銜接幾乎與原來的每個簇一樣強，兩個簇合并。l其中，ECCi，Cj是銜接簇Ci和Cj的邊之和；EC(Ci)是二分簇Ci的割邊的最小和；EC(Cj)是二分簇Cj的割邊的最小和。lRI和RC可以用多種不同的方法組合，產生自類似性的總量。Chameleon運用的方法是合并最大化RI(Ci,Cj)*RC(Ci,Cj)a簇對。其中a值大于1.)()(21),(),(

30、jijijiCECCECCCECCCRILimitations of Current Merging SchemesRelative Closeness schemes will merge (a) and (b)(a)(b)(c)(d)Relative interconnectivity schemes will merge (c) and (d)Chameleon算法算法l構造k-最近鄰圖l運用多層圖劃分算法劃分圖lRepeatl 合并關于相對互連性和相對接近性而言，最好 l 地堅持簇的自類似性的簇lUntil 不再有可以合并的簇例子例子優(yōu)點與局限性優(yōu)點與局限性lChameleon可以有效

31、地聚類空間數(shù)據(jù)，即使存在噪聲和離群點，并且簇具有不同的外形、大小和密度。lChameleon假定由稀疏化和圖劃分過程產生的對象組群是子簇，即一個劃分中的大部分點屬于同一個真正的簇。假設不是，那么凝聚層次聚類將混合這些錯誤，由于它絕對不能夠再將曾經錯誤地放到一同的對象分開。這樣，當劃分過程未產生子簇時，chameleon就有問題，對于高維數(shù)據(jù)，經常出現(xiàn)這種情況。共享最近鄰類似性共享最近鄰類似性lSNNshared nearest neighbor類似度計算：l1.找出一切點的k-近鄰l2.If 兩個點x和y不是相互在對方的k-最近鄰中 thenl3. similarity(x,y) 0l4.El

32、sel5. similarity(x,y)共享的近鄰個數(shù)l6.End iflSNN類似度由于經過運用共享最近鄰的個數(shù)思索了對象的環(huán)境，SNN類似度可以處置一個對象碰巧與另一對象相對接近，但屬于不同的類。在這種情況下，對象普通不共享許多近鄰，并且它們的SNN類似度低。lSSN類似度也能處置變密度簇的問題。在低密度區(qū)域，對象比高密度區(qū)域的對象分開得更遠。然而，一對點之間的SNN類似度只依賴于兩個對象共享的最近鄰的個數(shù)，而不是這些近鄰之間的相距多遠。SNN關于點的密度進展自動縮放?；趫D的聚類基于圖的聚類l最小生成樹聚類lOPOSSUMlChameleonlJarvis-Patrick聚類算法l基于

33、SNN密度的聚類Jarvis-PatrickJP聚類算法聚類算法l計算SNN類似度圖l運用類似度閾值，稀疏化SNN類似度圖l找出稀疏化的SNN類似度圖的連通分支優(yōu)點與局限性優(yōu)點與局限性l由于JP聚類基于SNN類似度概念，它擅長于處置噪聲和離群點，并且可以處置不同大小、外形和密度的簇。l該算法對高維數(shù)據(jù)效果良好，尤其擅長發(fā)現(xiàn)強相關對象的嚴密簇。lJP聚類把簇定義為SNN類似度圖的連通分支。這樣，一個對象集是分裂成兩個簇還是作為一個簇留下，能夠依賴于一條鏈?；诨赟NN密度的聚類密度的聚類l算法：l計算SNN類似度圖l以用戶指定的參數(shù)Eps和MinPts，運用DBSCANlSNN密度的聚類算法比

34、Jarvis-Patrick聚類或DBSCAN更加靈敏。l不象DBSCAN，它可以用于高維數(shù)據(jù)和簇具有不同密度的情況。l不象Jarvis-Patrick聚類簡單地運用域值，然后取連通分支作為簇，基于SNN密度的聚類運用基于SNN密度和中心點概念的方法。l中心點：一個點是中心點，假設在該點給定鄰域內的點數(shù)超越某個閾值MinPts。l邊境點。邊境點不是中心點，但是它落在一個中心點的鄰域內。l噪聲點是既非中心點，也非邊境點的任何點。SNN Density a) All Points b) High SNN Densityc) Medium SNN Density d) Low SNN Density

35、例子：解釋該算法處置高維數(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 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 T

36、ime 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度的經緯度網(wǎng)格的每個點上的月平均海平面氣壓SLP優(yōu)點與局限性優(yōu)點與局限性l基于SNN密度的聚類的優(yōu)點與局限性類似于JP聚類。l然而，中心點和SNN密度的運用大大添加了該方法的才干和靈敏性?？缮炜s：普通問題和方法可伸縮：普通問題和方法lBIRCHlCUREl假設運轉時間長得不可接受，或者需求的存儲量太大，即

37、使最好的聚類算法也沒有多大價值。l許多聚類算法所需求的存儲量都是非線性的。例如：運用層次聚類，存儲需求普通是O(m2)。類似地，有些聚類算法所需求的計算量也是非線性的。l可伸縮性可以經過如下技術實現(xiàn)：多維或空間存取方法、臨近度約束、抽樣、劃分數(shù)據(jù)對象、匯總、并行與分布計算。CURElCUREClustering Using REpresentative是一種聚類算法，它運用各種不同的技術創(chuàng)建一種可以處置大型數(shù)據(jù)、離群點、具有非球形和非均勻大小的簇的數(shù)據(jù)的方法。lCURE運用簇中的多個代表點來表示一個簇。實際上，這些點捕獲了簇的幾何外形。l詳細來說，第一個代表點選擇離簇中心最遠的點，而其他的點選

38、擇離一切曾經選取的點最遠的點。這樣，代表點相對分別。l選取的點的個數(shù)是一個參數(shù)，但是普通取10效果較好。l一旦選定代表點，它們就以因子a向簇中心收縮。這有助于減輕離群點的影響。l例如，一個到中心的間隔為10個單位的代表點將挪動3個單位對于a=0.7，而到中心間隔為1個單位的代表點僅挪動0.3個單位。 lCURE運用一種凝聚層次聚類方案進展實踐的聚類。兩個簇之間的間隔是恣意兩個代表點在它們向它們代表點的中心收縮之后之間的最短間隔。l假設a=0，它等價于基于質心的層次聚類；a=1時，它與單鏈層次聚類大致一樣。l留意，雖然運用層次聚類方案，但是CURE的目的是發(fā)現(xiàn)用戶指定個數(shù)的簇。lCURE在聚類過

39、程的兩個不同階段刪除離群點。首先，假設一個簇增長緩慢，那么這意味它主要由離群點組成，由于根據(jù)定義，離群點遠離其他點，并且不會經常與其他點合并。l在CURE中，離群點刪除的第一個階段普通出如今簇的個數(shù)是原來點數(shù)的1/3時。第二個離群點刪除階段出如今簇的個數(shù)到達K的量級時。此時，小簇又被刪除。lCURE在最壞情況下復雜度為O(m2logm)，它不能直接用于大型數(shù)據(jù)集。因此，CURE運用了兩種技術來加快聚類過程。l第一種技術是取隨機樣本，并在抽樣的數(shù)據(jù)點上進展層次聚類。隨后是最終掃描，將數(shù)據(jù)集中剩余的點指派到簇中。l在某些情況下，聚類所需求的樣本依然太大，需求第二種技術處理。在這種情況下，CURE劃分樣本數(shù)據(jù)，然后聚類每