基于劃分的聚類算法聚類算法

ClusteringAnalysis

(聚類分析)數據挖掘技術講座之——提綱聚類概述基于劃分的聚類算法介紹基于層次的聚類算法基于密度的聚類算法基于原型的聚類算法聚類介紹聚類的定義聚類分析的應用聚類分析原理介紹不同的聚類類型聚類算法性能評價什么是聚類

簡單地描述，聚類(Clustering)是將數據集劃分為若干相似對象組成的多個組(group)或簇(cluster)的過程，使得同一組中對象間的相似度最大化，不同組中對象間的相似度最小化。或者說一個簇(cluster)就是由彼此相似的一組對象所構成的集合，不同簇中的對象通常不相似或相似度很低。類間相似度最小化(距離最大化)類內相似度最大化(距離最小化)

一個具有清晰簇結構的數據集提出一個算法來尋找該例中的簇結構分類vs.聚類分類：有監(jiān)督的學習類別事先人工定義好，并且是學習算法的輸入一部分；聚類：無監(jiān)督的學習簇在沒有人工輸入的情況下從數據推理而得；很多因素會影響聚類的輸出結果：簇的個數、相似度計算方法、文檔的表示方式，等等聚類介紹文本聚類的定義聚類分析的應用聚類分析原理的介紹不同的聚類類型聚類算法性能評價聚類分析正在蓬勃發(fā)展，廣泛應用于一些探索性領域,如統計學與模式分析，金融分析，市場營銷，決策支持，信息檢索，WEB挖掘，網絡安全，圖象處理，地質勘探、城市規(guī)劃，土地使用、空間數據分析，生物學，天文學，心理學，考古學等。聚類分析無處不在誰經常光顧商店，誰買什么東西，買多少？按購物卡記錄的光臨次數、光臨時間、性別、年齡、職業(yè)、購物種類、金額等變量分類這樣商店可以….識別顧客購買模式（如喜歡一大早來買酸奶和鮮肉，習慣周末時一次性大采購）刻畫不同的客戶群的特征（用變量來刻畫，就象刻畫貓和狗的特征一樣）為什么這樣分類？因為每一個類別里面的人消費方式都不一樣，需要針對不同的人群，制定不同的關系管理方式，以提高客戶對公司商業(yè)活動的相應率。聚類分析無處不在挖掘有價值的客戶，并制定相應的促銷策略：如，對經常購買酸奶的客戶對累計消費達到12個月的老客戶針對潛在客戶派發(fā)廣告，比在大街上亂發(fā)傳單命中率更高，成本更低！聚類分析無處不在誰是銀行信用卡的黃金客戶？利用儲蓄額、刷卡消費金額、誠信度等變量對客戶分類，找出“黃金客戶”！這樣銀行可以……制定更吸引的服務，留住客戶！比如：一定額度和期限的免息透支服務！貴賓打折卡！在他或她生日的時候送上一個小蛋糕！聚類的應用領域經濟領域：幫助市場分析人員從客戶數據庫中發(fā)現不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。誰喜歡打國際長途，在什么時間，打到那里？對住宅區(qū)進行聚類，確定自動提款機ATM的安放位置股票市場板塊分析，找出最具活力的板塊龍頭股企業(yè)信用等級分類……萬維網對WEB上的文檔進行分類對WEB日志的數據進行聚類，以發(fā)現相同的用戶訪問模式數據挖掘領域作為其他數學算法的預處理步驟，獲得數據分布狀況，集中對特定的類做進一步的研究萬維望—搜索結果的聚類：更好地瀏覽萬維望—全局瀏覽:Yahoo聚類介紹文本聚類的定義聚類分析的應用聚類分析原理的介紹聚類方法的類型聚類算法性能評價聚類分析原理介紹聚類分析中“類”的特征：聚類所說的類不是事先給定的，而是根據數據的相似性和距離來劃分聚類的數目和結構都沒有事先假定聚類方法的目的是尋找數據中：潛在的自然分組結構感興趣的關系聚類分析原理介紹什么是自然分組結構?我們看看以下的例子：有16張牌如何將他們分為一組一組的牌呢？AKQJ聚類分析原理介紹分成四組每組里花色相同組與組之間花色相異AKQJ花色相同的牌為一副聚類分析原理介紹分成四組符號相同的牌為一組AKQJ符號相同的的牌聚類分析原理介紹分成兩組顏色相同的牌為一組AKQJ顏色相同的配對聚類分析原理介紹這個例子告訴我們：聚類的結果不是唯一的類(簇)的概念可能是模糊的AKQJ大配對和小配對聚類介紹文本聚類的定義聚類分析的應用聚類分析原理的介紹不同的聚類類型聚類算法性能評價不同的聚類類型層次的與劃分的一個聚類方法產生簇(cluster)的集合；

不同類型的聚類之間產生簇的集合是嵌套的，還是非嵌套的；或者，是層次的還是劃分的；劃分的聚類方法，將數據對象劃分到非重疊的子集(簇)中，使得每個對象屬于唯一的一個子集；層次的聚類方法，產生一個嵌套的簇的集合，它們可組織為一棵層次樹；劃分聚類原始點一個劃分聚類層次聚類傳統的層次聚類非傳統的層次聚類非傳統的樹圖傳統的樹圖互斥vs非互斥在非互斥的聚類中，一個點可能屬于多個不同的簇。

互斥的聚類中，每個對象都指派到單個簇?？梢员硎径鄠€類別或者邊界點模糊vs非模糊在模糊的聚類中，每個對象點以0和1之間的隸屬權重屬于每個簇，即簇視為模糊集約束條件：權重值和必須為1實際中，通過將對象指派到具有最高隸屬權值或概率的簇，將模糊或概率聚類轉換成互斥聚類。不同的聚類類型部分的vs完全的完全聚類將每個對象指派到一個簇部分聚類，數據集中某些對象可能不屬于明確定義的組，數據集中一些對象可能代表噪聲、離群點或“不感興趣的背景”。因此，只需要聚類部分數據不同的聚類類型聚類介紹文本聚類的定義聚類分析的應用聚類分析原理的介紹聚類方法的類型聚類算法性能評價怎樣判斷聚類結果的好壞?內部準則(internalcriterion)將簇內高相似度(簇內文檔相似)及簇間低相似度(不同簇之間的文檔不相似)的目標進行形式化后得到的一個函數。

內部準則往往不能評價聚類在應用中的實際效用外部準則(internalcriterion)按照用戶定義的分類結果來評價，即對一個分好類的數據集進行聚類，將聚類結果和事先的類別情況進行比照，得到最后的評價結果純度、歸一劃互信息NMI(NormalizedMutualInformation)、蘭德指數(RandIndex)以及F值。外部準則:純度?={ω1,ω2,...,ωK}是簇的集合C={c1,c2,...,cJ}是類別的集合對每個簇

ωk:找到一個類別cj

，該類別包含ωk中的元素最多，為nkj

個，也就是說ωk的元素最多分布在cj中將所有

nkj

求和，然后除以所有的文檔數目純度計算的例子為計算純度

maxj|ω1∩cj

|=5(classx,cluster1);maxj|ω2∩cj|=4(classo,cluster2);maxj|ω3∩cj|=3(class?,cluster3)

純度為(1/17)×(5+4+3)≈0.71.外部準則－F值將每個聚類結果看作是查詢的結果。這樣對于最終的某個聚類類別r和原來預定類別i。n(i,r)是聚類r中包含類別i中的文檔個數，ni是預定義類別的個數，nr是聚類形成的類別r中的文檔個數。外部準則－F值將每個聚類結果看作是查詢的結果。這樣對于最終的某個聚類類別r和原來預定類別r。最終聚類結果的評價函數為：這里n是所有測試文檔的個數。值得指出的是，通過以上這兩種方法獲得的聚類評價只是對數據集作一次劃分的評價。為了客觀評價聚類算法的性能.有必要進行多次聚類獲得其評價結果，并用其均值仿卻來評價算法?！趧澐值木垲愃惴ň垲愃惴?ClusteringAlgorithm)劃分方法對包含n個文檔的文本集合，劃分將生成k個分組，k<=n，每一個分組代表一個聚類典型的劃分方法（Partitioningmethods）:k-平均方法(k-meansMethods)k-中心點方法(K-medoidsMethods)

k均值用質心定義，其中質心是一組點的均值；k中心點使用中心點來定義，其中中心點是一組點中最有代表性的點；基本k-Means算法step1.任意選擇k個對象作為初始質心，k是用戶指定的參數，即所期望的簇的個數；step2.repeat

將每個點(文檔)指派到最近的質心，形成k個簇；重新計算每個簇的質心until質心不再發(fā)生變化,即沒有對象進行被重新分配

時，過程結束。

質心：基本k-Means算法－指派最近質心為了將點指派到最近的質心，需要鄰近性度量來量化數據的“最近”概念歐式空間中的點使用歐幾里得距離、曼哈頓距離文檔用余弦相似性，Jarccard系數歐氏距離：

曼哈頓距離：加權的歐幾里得距離：對每個變量根據其重要性賦予一個權重：基本k-Means算法－質心和目標函數歐幾里得空間中的數據：鄰近性度量為歐幾里得距離，使用誤差平方和(SumoftheSquaredError,SSE)作為度量聚類質量的目標函數。選擇誤差平方和最小的說明：dist是歐幾里得空間中兩個對象之間的標準歐幾里得

距離。ci是簇Ci的質心。計算每個數據點的誤差，該

誤差為它到最近質心的歐幾里得距離。文檔數據：鄰近性度量為余弦相似度，目標是最大化簇中文檔與簇的質心的相似性，該度量稱作簇的凝聚度(cohesion)。基本k-Means算法示例1：坐標表示5個點｛X1,X2,X3,X4,X5｝作為一個聚類分析的二維樣本：X1＝(0,2),X2＝(0,0),X3＝(1.5,0)，X4＝(5,0)，X5＝(5,2)。

假設要求的簇的數量k=2。思路：

由樣本的隨機分布形成兩個簇：C1={X1,X2,X4}和C2＝{X3,X5}這兩個簇的質心M1和M2是：

M1＝{(0+0+5)/3,(2+0+0)/3}＝{1.66,0.66｝；M2＝{(1.5+5)/2，(0+2)/2}={3.25,1.00}；基本k-Means算法示例樣本初始隨機分布之后，誤差是：

E12=[(0-1.66)2+(2-0.66)2]+[(0-1.66)2+(0-0.66)2]+[(5-1.66)2+(0-0.66)2]=19.36；E22=8.12；誤差平方和是：E2＝E12+E22＝19.36+8.12＝27.48基本k-Means算法示例

按與質心（M1或M2）間距離關系，選擇最小距離分配所有樣本，簇內樣本的重新分布如下：d(M1,X1)=(1.662+1.342)1/2=2.14d(M2,X1)=3.40==>X1∈C1；d(M1,X2)=1.79和d(M2,X2)=3.40==>X2∈C1d(M1,X3)=0.83和d(M2,X3)=2.01==>X3∈C1d(M1,X4)=3.41和d(M2,X4)=2.01==>X4∈C2d(M1,X5)=3.60和d(M2,X5)=2.01==>X5∈C2

新簇C1＝{X1,X2,X3}和C2＝{X4,X5}基本k-Means算法示例計算新的質心：M1＝｛0.5，0.67｝；M2＝｛5.0，1.0｝。相應的方差及總體平方誤差分別是：E12＝4.17；E22＝2.00；E＝6.17；可以看出第一次迭代后，總體誤差顯著減小(從值27.48到6.17)。在這個簡單的例子中，第一次迭代同時也是最后一次迭代，因為如果繼續(xù)分析新中心和樣本間的距離樣本將會全部分給同樣的簇，不將重新分配，算法停止。基本k-Means算法示例k-Means特點該算法試圖找出使誤差平方和最小的k個劃分。當結果簇是密集的，而簇與簇之間區(qū)分明顯時，它的效果較好。算法復雜度O(I*K*m*n)，其中I是迭代次數,m是點數，n是屬性數。因此其可擴展性較好，對大數據集處理有較高的效率。算法并不能保證達到全局最小值，特別是文檔集包含很多離群點時，這個問題尤其明顯。這些離群點遠離其他文檔，因此不適合歸入任何一個簇。如果離群點被選為初始種子，那么在后續(xù)迭代中不會有任何其他的向量被分配到該簇中。因此，常以局部最優(yōu)結束缺點：要求用戶必須事先給出要生成的簇的數目，聚類結果依賴于初始種子的選?。徊贿m合發(fā)現非凸面狀的簇。不適合大小差別較大的簇；對于噪聲和孤立點是敏感的，因為少量的該類數據能對平均值產生較大的影響。二分k-means算法－對初始化質心問題不太敏感二分K-means算法是基本k-means算法的直接擴充，基于如下想法：為了得到k個簇，將所有點的集合分裂成兩個簇，從中選擇一個繼續(xù)分裂，如此重復直到產生k個簇。算法詳細描述如下：初始化簇表，使之包含由所有的點組成的簇。Repeat

從簇表中選取一個簇。{對選定的簇進行多次二分“試驗”}Fori=1to試驗次數do

使用基本k-means，二分選定的簇Endfor從二分試驗中選擇具有最小總誤差平方和SSE的兩個簇。將這兩個簇添加到簇表中Until簇表中包含k個簇K-Mediods(K-中心點)算法k均值算法對離群點是敏感的，平方誤差函數也會扭曲數據的分布。修改k均值算法降低敏感性：

不采用簇中對象的均值作為參照點，而是在每個簇中選出一個實際的對象來代表該簇。

使用絕對誤差標準

k中心點算法之一--PAM算法：k中心點。PAM，一種基于中心點或中心對象進行劃分的k中心點算法。輸入：

k：結果簇的數目

D：包含n個對象的數據集輸出：k個簇的集合。方法：(1)從D中任意選擇k個對象作為初始的代表對象或種子；(2)repeat(3)將每個剩余對象指派到最近的代表對象所代表的簇；(4)隨機選擇一個非代表對象orandom；(5)計算用orandom交換代表對象oj的總代價S(所有非代表對象所產生的代價之和，代價就是絕對誤差值的差)；(6)

ifS<0(說明實際的絕對誤差E將會減小),then用orandom替換oj，形成新的k個代表對象的集合；(5)until不發(fā)生變化k中心點算法分析

當存在噪聲和離群點時，k-中心點方法比k-均值更魯棒，因為中心點不像均值那樣容易受離群點或其他極端值影響；k-中心點算法的每次迭代的復雜度時O(k(n-k)2)。當n和k的值較大時，這種計算開銷變得很大，遠高于k-均值方法；

兩種方法都需要用戶指定簇數k?！趯哟蔚木垲愃惴ň垲愃惴?ClusteringAlgorithm)層次聚類概述層次聚類的目標是生成目錄的一個層次結構：這個層次結構是自動創(chuàng)建的，可以通過自頂向下或自底向上的方法來實現。層次聚類概述主要有兩種類型凝聚式:一開始將每個對象作為單獨的一個簇在每一步，將最相近的簇合并，直到所有的組合并成一

個，或達到一個終止條件為止分裂式:一開始將所有的對象置于一類在迭代的每一步中，一個類不斷地分為更小的類，直到每

個對象在單獨的一個類中，或達到一個終止條件傳統的層次聚類算法需要用到一個相似性或者距離矩陣層次聚類概述層次聚類的優(yōu)點：不必事先假定特定數目的簇，在樹圖中合適的層次上做切面，就可以得到任意理想數量的簇；可能對應于有意義的分類層次，如在生物學中(e.g.,動物王國,生物種系,…)凝聚式聚類更普遍的一種聚類方法基本算法很直觀關鍵操作是計算兩個簇之間的鄰近度使用不同的鄰近度方法，產生不同的聚類算法初始情形每個點構成一個簇，并給出它們的鄰近度矩陣p1p3p5p4p2p1p2p3p4p5......鄰近度矩陣聚類過程中的情形經過一些合并后，得到了一些簇C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5鄰近度矩陣聚類過程中的情形假設需要合并兩個最近的簇(C2和C5)，并需要更新鄰近度矩陣C1C4C2C5C3C2C1C1C3C5C4C2C3C4C5鄰近度矩陣合并后問題是“如何更新鄰近度矩陣?”C1C4C2UC5C3???? ???C2UC5C1C1C3C4C2UC5C3C4鄰近度矩陣如何定義簇間的相似度

p1p3p5p4p2p1p2p3p4p5......相似度MINMAX組平均GroupAverage質心距離DistanceBetweenCentroids目標函數驅動方法Ward’sMethodusessquarederror鄰近度矩陣簇相似度:MIN或者單鏈(SingleLink)最小距離法(singlelinkagemethod)Min定義簇的鄰近度為不同簇的兩個最近的點之間的鄰近度，或者使用圖的術語，不同的結點子集中兩個結點之間的最短邊。簇相似度:MIN或者單鏈(SingleLink)示例2，有6個二維點的樣本數據。點x和y坐標，以及點之間的歐幾里得距離如下表所示。點X坐標Y坐標P10.40050.5306P20.21480.3854P30.35470.3156P40.26520.1875P50.07890.4139p60.45480.3022P1P2P3P4P5P6P100.23570.22180.36880.34210.2347P20.235700.14830.20420.13880.2540P30.22180.148300.15130.28430.1100P40.36880.20420.151300.29320.2216P50.34210.13880.28430.293200.3921p60.23470.25400.11000.22160.39210簇相似度:MIN或者單鏈(SingleLink)示例2，有6個二維點的樣本數據。點x和y坐標，以及點之間的歐幾里得距離如下表所示。樹圖嵌套的簇12345612345dist({3,6},{2,5})=min(dist(3,2),dist(6,2),dist(3,5),dist(6,5))=min(0.15,0.25,0.28,0.39)=0.15簇相似度:MAX或全鏈(CompleteLinkage)最大距離法(completelinkagemethod)MAX定義簇的鄰近度為不同簇中兩個最遠的點之間的鄰近度，或者使用圖的術語，不同的結點子集中兩個結點之間的最長邊?；氐絼偛诺睦幼畲缶嚯x法(completelinkagemethod)dist({3,6},{4})=max(dist(3,4),dist(6,4))=max(0.15,0.22)=0.22dist({3,6},{2,5})=max(dist(3,2),dist(6,2),dist(3,5),dist(6,5))=max(0.15,0.25,0.28,0.39)=0.39dist({3,6},{1})=max(dist(3,1),dist(6,1))=max(0.22,0.23)=0.23回到剛才的例子最大距離法(completelinkagemethod)12345612534嵌套的簇樹圖簇相似度:組平均組平均距離法(averagelinkagemethod)類間所有樣本點的平均距離該法利用了所有樣本的信息，是單鏈和全鏈之間的折中，被認為是較好的層次聚類法回到剛才的例子組平均距離法dist({3,6,4},{1})=(0.22+0.37+0.23)/(3*1)=0.28dist({2,5},{1})=(0.2357+0.342d1)/(2*1)=0.2889dist({3,6,4},{2,5})=(0.15+0.28+0.25+0.39+0.20+0.29)/(3*2)=0.26因為dist({3,6,4},{2,5})比dist({3,6,4},{1})和dist({2,5},{1})小，簇{3,6,4}和{2,5}在第4階段合并層次聚類:組平均51234561234嵌套的簇樹圖層次聚類：時間和空間復雜度空間復雜度：O(N2)N是點的數量使用了鄰近度矩陣大多數情況下時間復雜度：O(N3)由N步構成，在每一步，大小為N2的鄰近度矩陣需要更新和搜索對于某些方法，復雜度可以減少到O(N2log(N))層次聚類:問題和局限性一旦決定合并兩個簇，就不能撤銷缺乏全局目標函數凝聚層次聚類技術使用各種標準，在每一步局部地確定哪些簇應當合并，這種方法產生的聚類算法避開了解決困難的組合優(yōu)化問題這種方法沒有很難選擇初始點的問題不同的方案存在一個或多個下列問題:對噪音和離群點敏感處理不同大小和凸狀形狀時存在困難會分裂大型簇——基于密度的聚類算法聚類算法(ClusteringAlgorithm)基于密度的聚類聚類標準基于密度，即尋找被低密度區(qū)域分離的高密度區(qū)域主要特征:能發(fā)現具有任意形狀的簇易于處理離群點需要用密度參數作為終止條件幾種方法:DBSCAN:Ester等(KDD’96)OPTICS:Ankerst等(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal等(SIGMOD’98)(基于神經網絡)72DBSCAN是一種基于高密度連通區(qū)域的聚類方法，該算法將具有足夠高密度的區(qū)域劃分為簇，并在具有噪聲的空間數據庫中發(fā)現任意形狀的簇，它將簇定義為密度相連的點的最大的集合。根據點的密度將點分為三類：稠密區(qū)域內部的點(核心點)，(2)稠密區(qū)域邊緣上的點(邊界點)，(3)稀疏區(qū)域中的點(噪聲或背景點)。給定一個對象集合D，對象之間的距離函數為distance(*，*)，鄰域半徑為Eps。DBSCAN－基于中心的密度方法DBSCAN－基于中心的密度方法點的密度：在點的給定半徑(Eps)之內的點計數(包括點本身)

該點密度取決于指定的半徑，如果半徑足夠大，則所有點的密度都等于數據集中的點數，如果半徑太小，則所有點的密度都是1一個點是核心點，如果該點的給定鄰域內的點的個數超過指定數量(MinPts)的點這些點在簇內部，點的鄰域由距離函數和用戶指定的距離參數Eps決定。一個邊界點不是核心點，但它落在某個核心點的鄰域內。邊界點可能落在多個核心點的鄰域內。一個噪音點既不是核心點也不是邊界點DBSCAN:核心、邊界和噪音點直接密度可達：如果p在q的Eps鄰域內，而q是一個核心對象，則稱對象p從對象q出發(fā)時是直接密度可達的(directlydensity-reachableDBSCAN－基于中心的密度方法MinPts=5Eps=1cmpq密度可達：如果存在一個對象鏈，對于,是從關于Eps和MinPts直接密度可達的，則對象p是從對象q關于Eps和MinPts密度可達的(density-reachable)。p1pq密度相連：如果存在對象O∈D，使對象p和q都是從O關于Eps和MinPts密度可達的，那么對象p到q是關于Eps和MinPts密度相連的(density-connected)。DBSCAN－基于中心的密度方法pqoDBSCAN算法示例如圖，Eps用一個相應的半徑表示，設MinPts=3。圖4.7“直接密度可達”和“密度可達”概念示意描述解答：根據以上概念知道：由于有標記的各點-M、P、O和R的Eps近鄰均包含3個以上的點，因此它們都是核對象；M-是從P“直接密度可達”；而Q則是從-M“直接密度可達”；基于上述結果，Q是從P“密度可達”；但P從Q無法“密度可達”(非對稱)。類似地，S和R從O是“密度可達”的；O、R和S均是“密度相連”的。密度可達是直接密度可達的傳遞閉包，這種關系式非對稱的。只有核心對象之間相互密度可達。密度相連性是一個對稱關系基于密度的蔟是基于密度可達性的最大的密度相連對象的集合不包含在任何蔟中的對象被認為是噪聲。DBSCAN－基于中心的密度方法DBSCAN通過檢查數據集中每點的Eps鄰域來搜索簇。如果點p的Eps鄰域包含的點多于MinPts個，則創(chuàng)建一個以p為核心對象的簇；然后DBSCAN迭代地聚集從這些核心對象直接密度可達的對象，這個過程可能涉及一些密度可達簇的合并；當沒有新的點添加到任何簇時，該過程結束。DBSCAN－基于中心的密度方法算法具體描述(1)首先將數據集D中的所有對象標記為未處理狀態(tài)(2)for數據集D中每個對象pdo(3)ifp已經歸入某個簇或標記為噪聲then(4)continue;(5)else(6)檢查對象p的Eps鄰域；(7)if包含的對象數小于MinPtsthen(8)標記對象p為邊界點或噪聲點；(9)else(10)標記對象p為核心點，并建立新簇C；(11)for中所有尚未被處理的對象qdo(12)檢查其Eps鄰域，若包含至少MinPts個對象，則將中未歸入任何一個簇的對象加入C；(13)endfor(14)endif(15)endif(16)endforDBSCAN算法示例對于表所示二維平面上的數據集，取Eps=3，MinPts=3來演示DBSCAN算法的聚類過程(使用Mahattan距離公式)。表聚類過程示例數據集3P1P2P3P4P5P6P7P8P9P10P11P12P1312245667913532143879951212123解答：(1)隨機選擇一個點，如P1(1，2)，其Eps鄰域中包含{P1，P2，P3，P13}，P1是核心點，其鄰域中的點構成簇1的一部分，依次檢查P2，P3，P13的Eps鄰域，進行擴展，將點P4并入，P4為邊界點；(2)檢查點P5，其Eps鄰域中包含{P5，P6，P7，P8}，P5是核心點，其鄰域中的點構成簇2的一部分，依次檢查P6，P7，P8的Eps鄰域，進行擴展，每個點都是核心點，不能擴展；(3)檢查點P9，其Eps鄰域中包含{P9}，P9為噪聲點或邊界點；(4)檢查點P10，其Eps鄰域中包含{P10，P11}，P10為噪聲點或邊界點；檢查P11，其Eps鄰域中包含{P10，P11，P12}，P11為核心點，其鄰域中的點構成簇3的一部分；進一步檢查，P10、P12為邊界點。DBSCAN算法示例所有點標記完畢，P9沒有落在任何核心點的鄰域內，為噪聲點。最終識別出三個簇，P9為噪聲點。簇1包含{P1，P2，P3，P4，P13}，P4為邊界點，其它點為核心點；簇2包含{P5，P6，P7，P8}，其全部點均為核心點；簇3包含{P10，P11，P12}，P10、P12為邊界點，P11為核心點；如果MinPts=4，則簇3中的點均被識別成噪聲點。DBSCAN算法的優(yōu)點：可以識別具有任意形狀和不同大小的蔟，自動確定蔟的數目，分離簇和環(huán)境噪聲，一次掃描數據即可完成聚類。DBSCAN算法示例DBSCAN適用的情形原始點簇抗噪能夠處理不同形狀和大小的簇DBSCAN:確定EPS和MinPts同一個簇中的點到它們的k個最近鄰的距離大致相當噪音點到它們的k個最近鄰距離則比較遠對于某個k，計算所有點的k距離(點到它的k個最近鄰的距離)，并增序排列，然后繪制排序后的值，則會看到k-距離的急劇變化，對應于合適的Eps值。選取該距離為Eps參數，取k值為MinPts參數，則k-距離小于Eps的點將被標記為核心點，而其他點將被標記為噪聲或邊界點?！谠偷木垲愃惴ň垲愃惴?ClusteringAlgorithm)基于原型的聚類基于原型的聚類：簇是對象的集合，一個簇中的任何對象離該簇的原型比其他簇的原型更近k-means，使用簇中對象的質心作為簇的原型擴展基于原型的聚類允許對象屬于多個簇，即對象以某個權值屬于每一個簇模糊聚類用統計分布對簇進行建模，即對象通過一個隨機過程，由一個被若干統計參數(如均值和方差)刻畫的統計分布產生EM聚類模糊聚類如果數據對象分布在明顯分離的組中，則把對象明確分類成不相交的簇是一種理想的方法；在大部分情況下，數據集中的對象不能劃分明顯分離的簇，指派一個對象到一個特定的簇具有一定的任意性。

對每個對象和每個簇賦予一個權值，指明該對象屬于該簇的程度。模糊聚類理論基礎:模糊集合論：對象以0和1之間的某個隸屬度屬于一個集合模糊邏輯：一個命題以0和1之間的確定度為真模糊簇：假定有一個數據點集合{x1,x2,…,xm}，模糊簇集c1,c2,…,ck(1)wij表示xi屬于cj的隸屬度,滿足

(2)每個簇Cj以非零權值至少包含一個點，但不以權值1包含所有的點模糊聚類算法-k均值的模糊版本基本的模糊c均值算法（FCM）1選擇一個初始模糊劃分，即對所有的wij

賦值2repeat3

使用模糊劃分，計算每個簇的質心4

重新計算模糊劃分，即wij5until質心不發(fā)生變化(替換的終止條件是“如果誤差的變化低于指定的閾值”或“如果所有wij的變化的絕對值都低于指定的閾值)與K均值一樣，FCM可以解釋為視圖最小化誤差的平方和(SSE)初始化：通常隨機選取，與k-means類似。對于權值，隨機地選取，同時限定與任何對象相關聯地權值之和必須等于1計算質心：所有點都需要考慮，每個點對質心的貢獻根據隸屬度加權p>1,p越大，劃分越來越模糊，p=1，則為傳統的K均值更新模糊劃分模糊聚類算法更新模糊劃分模糊聚類算法分析：權值wij指明點xi在簇Cj中的隸屬度。如果xi靠近質心cj，則wij相對較高；而如果xi遠離質心cj，則wij相對較低。P=2P>2分析：該指數降低賦予離點最近的簇的權值。事實上，隨著p趨向無窮大，該指數趨向于0，而權值趨向于1/k；另一方面，隨著p趨向于1，該指數加大賦予離點最近的簇的權值。隨著p趨向于1，關于最近簇的隸屬度權值趨向于1，而關于其他簇的隸屬度權值趨向于0，這對應于K均值。目標函數-誤差的平方和模糊聚類算法三個圓形簇上的模糊c均值。對于100點的二維數據集，使用模糊c均值發(fā)現其三個簇的結果。每個點指派到它具有最大隸屬度權值的簇。屬于各個簇的點用不同的標記顯示，而點在簇中的隸屬度用明暗程度表示。模糊聚類算法的優(yōu)點與局限性能指示任意點屬于任意簇的程度與k-means具有相同的優(yōu)缺點計算密集性更高使用混合模型的聚類基于統計模型的聚類假定數據由一個統計過程產生，通過找出最佳擬合數據的統計模型來描述數據，其中統計模型用分布和該分布的一組參數描述EM算法基于混合模型使用若干統計分布對數據建模，每個分布對應于一個簇，每個分布的參數提供對應簇的描述使用混合模型的聚類混合模型混合模型將數據看作從不同的概率分布得到的觀測值的集合，概率分布可以是任意分布，但通常是多元正態(tài)的混合模型對應于如下數據產生過程，給定幾個分布(通常類型相同但參數不同)，隨機地選取一個分布并由它產生一個對象。重復該過程m次，其中m是對象的個數形式的，假定有k個分布和m個對象x1,…,xm，第j個分布的參數θj,Θ是所有參數的集合，即Θ={θ1,…,θk}，prob(xi|θj)是第i個對象來自第j個分布的概率，wj是對象x由第j個分布產生的概率，∑wj=1，對象x的概率

如果對象以獨立的方式產生，則整個對象集的概率是