數據挖掘Topic3--聚類分析密度聚類2基于密度的方法基于密度聚類(Density-BasedClustering)主要特點:發現任意形狀的聚類處理噪音一遍掃描需要密度參數作為終止條件一些有趣的研究:DBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’98)3基于密度的聚類:背景I兩個參數:Eps:鄰域的最大半徑MinPts:在Eps-鄰域中的最少點數NEps(p): {qbelongstoD|dist(p,q)<=Eps}直接密度可達的:點p

關于Eps,MinPts

是從點q直接密度可達的,如果

1)p

屬于NEps(q)2)核心點條件:|NEps(q)|>=MinPts

pqMinPts=5Eps=1cm4密度概念核心對象(Coreobject):一個對象的–鄰域至少包含最小數目MinPts個對象,不是核心點,但落在某個核心點的Eps鄰域內的對象稱為邊界點,不屬于任何簇的對象為噪聲.對于空間中的一個對象，如果它在給定半徑e的鄰域中的對象個數大于密度閥值MinPts，則該對象被稱為核心對象，否則稱為邊界對象。CoreBorderOutlierEps=1cmMinPts=5由一個核心對象和其密度可達的所有對象構成一個聚類。密度概念直接密度可達的(Directlydensityreachable,DDR):給定對象集合D,如果p是在q的–鄰域內,而q是核心對象,我們說對象p是從對象q直接密度可達的(如果q是一個核心對象，p屬于q的鄰域，那么稱p直接密度可達q。)密度可達的(densityreachable):存在一個從p到q的DDR對象鏈(如果存在一條鏈<p1,p2,…..,pi>，滿足p1=p，pi=q，pi直接密度可達pi+1，則稱p密度可達q)pqMinPts=5Eps=1cm6基于密度的聚類:背景II密度可達:點p

關于Eps,MinPts

是從

q密度可達的,如果存在一個節點鏈p1,…,pn,p1=q,pn=p

使得pi+1

是從pi直接密度可達的密度相連的:點p關于Eps,MinPts

與點

q是密度相連的,如果存在點o使得,p

和

q

都是關于Eps,MinPts

是從

o密度可達的(如果存在o，o密度可達q和p，則稱p和q是密度連通的)pqp1pqo由一個核心對象和其密度可達的所有對象構成一個聚類。7密度概念Eg:

假設半徑

Ε=3

，

MinPts=3

，點

p

的

領域中有點

{m,p,p1,p2,o},

點

m

的

領域中有點

{m,q,p,m1,m2},

點

q的

領域中有

{q,m},

點

o

的

領域中有點

{o,p,s},

點

s

的

領域中有點

{o,s,s1}.那么核心對象有

p,m,o,s(q

不是核心對象，因為它對應的

領域中點數量等于

2

，小于

MinPts=3)

；點

m

從點

p

直接密度可達，因為

m

在

p

的

領域內，并且

p

為核心對象；點

q

從點

p

密度可達，因為點

q

從點

m

直接密度可達，并且點

m

從點

p

直接密度可達；點

q

到點

s

密度相連，因為點

q

從點

p

密度可達，并且

s

從點

p

密度可達。由一個核心對象和其密度可達的所有對象構成一個聚類。8例子MinPts=3q是從p密度可達；p不是從q密度可達（q非核心）S和r從o密度可達；o從r密度可達；r,s密度相連2023/7/22a為核心對象，b為邊界對象，且a直接密度可達b，但b不直接密度可達a,因為b不是一個核心對象2023/7/22c直接密度可達a,a直接密度可達b,所以c密度可達b，同理b不密度可達c，但b和c密度連通11DBSCAN(1996)DBSCAN(DensityBasedSpatialClusteringofApplicationswithNoise)

一個基于密度的聚類算法可以在帶有“噪音”的空間數據庫中發現任意形狀的聚類CoreBorderOutlierEps=1cmMinPts=512DBSCAN(1996)

DBSCAN：一種基于高密度連通區域的基于密度的聚類方法，該算法將具有足夠高密度的區域劃分為簇，并在具有噪聲的空間數據庫中發現任意形狀的簇。它將簇定義為密度相連的點的最大集合；13DBSCAN(續)算法任意選取一個點p得到所有從p

關于Eps

和MinPts密度可達的點.如果p

是一個核心點,則找到一個聚類.如果p

是一個邊界點,沒有從p

密度可達的點,DBSCAN將訪問數據庫中的下一個點.繼續這一過程,直到數據庫中的所有點都被處理.DBSCAN的復雜度采用空間索引,復雜度為O(nlogn),否則為O(n2)DBSCAN的缺點:對用戶定義的參數是敏感的,參數難以確定(特別是對于高維數據),設置的細微不同可能導致差別很大的聚類.（數據傾斜分布）全局密度參數不能刻畫內在的聚類結構2023/7/22DBSCAN從任一對象p開始，根據參數e和MinPts提取所有從p密度可達對象，得到一個聚類。1.

從任一對象p開始。a)

如果p是核心對象，則p和p直接密度可達的所有對象被標記為類i。遞歸p直接密度可達的所有對象qi（即用qi代替p回到第一步）。b)

如果p是一個邊界對象，那么p被標記為噪聲。2.

i++3.

如果還有沒被標記的對象，則從中任選一個作為p，回到第一步。15DBSCAN(續)算法：

DBSCAN輸入：

—

半徑

MinPts

—

給定點在

鄰域內成為核心對象的最小領域點數

D

—

集合輸出：目標類簇集合方法：

repeat1)

判斷輸入點是否為核心對象2)

找出核心對象的

鄰域中的所有直接密度可達點

util

所有輸入點都判斷完畢

repeat

針對所有核心對象的

鄰域所有直接密度可達點找到最大密度相連對象集合，

中間涉及到一些密度可達對象的合并。

Util

所有核心對象的

鄰域都遍歷完畢作業（Duedate：5月9日）2023/7/22專題思路：把搜下來的網頁進行聚類，將聚類結果顯示給用戶，用戶可以選擇其中的一個類，標為關注，類的關鍵詞作為主題，用戶就可以跟蹤這主題、了解主題的文章的情感（就是其它部分的功能）雙層正方形或者三維同心球，其中第一類樣本的參數服從均勻布，第二類樣本的參數服從均勻分布,隨機產生20000個樣本數據進行聚類.17OPTICS(1999)OPTICS(OrderingPointsToIdentifythe在前面介紹的DBSCAN算法中，有兩個初始參數（鄰域半徑）和minPts(鄰域最小點數)需要用戶手動設置輸入，并且聚類的類簇結果對這兩個參數的取值非常敏感，不同的取值將產生不同的聚類結果，其實這也是大多數其他需要初始化參數聚類算法的弊端。ClusteringStructure)Ankerst,Breunig,Kriegel,和Sander提出(SIGMOD’99)為自動和交互的聚類分析計算一個簇次序(clusterordering).OPTICS并不顯示的產生結果類簇，而是為聚類分析生成一個增廣的簇排序（比如，以可達距離為縱軸，樣本點輸出次序為橫軸的坐標圖），這個排序代表了各樣本點基于密度的聚類結構。它包含的信息等價于從一個廣泛的參數設置所獲得的基于密度的聚類，換句話說，從這個排序中可以得到基于任何參數E和minPts的DBSCAN算法的聚類結果。18OPTICS(1999)這個次序代表了數據的基于密度的聚類結構。它包含了信息,等同于從一個廣域的參數設置所獲得的基于密度的聚類可用于自動和交互聚類分析,包括發現內在聚類結構可以使用圖形或可視化技術表示考慮DBSCAN,對一個恒定的MinPts值,關于高密度的(即較小的值)的聚類結果被完全包含在根據較低密度所獲得的密度相連的集合中

擴展DBSCAN算法來同時處理一組距離參數值19OPTICS(續)為了同時構建不同的聚類,應當以特定的順序來處理對象.優先選擇最小的值密度可達的對象,以便高密度的聚類能被首先完成

每個對象需要存儲兩個值對象p的核心距離(core-distance)是使得p成為核心對象的最小。如果p不是核心對象,p的核心距離沒有定義

對象q關于另一個對象p的可達距離(reachability-distance)是p的核心距離和p與q的歐幾里得距離之間的較大值.如果p不是一個核心對象,p和q之間的可達距離沒有定義

20OPTICS(續)例:設=6(mm),MinPts=5.p的核心距離是p與四個最近的數據對象之間的距離’.q1關于p的可達距離是p的核心距離(即’=3mm),因為它比從p到q1的歐幾里得距離要大.q2關于p的可達距離是從p到q2的歐幾里得距離,它大于p的核心距離

=6mm’=3mm=6mm’=3mmppq1q2P的核心距離可達距離(p,q1)=’=3mm可達距離(p,q2)=d(p,q2)2023/7/22例如：假設鄰域半徑E=2,minPts=3，存在點A(2,3),B(2,4),C(1,4),D(1,3),E(2,2),F(3,2)點A為核心對象，在A的E領域中有點{A,B,C,D,E,F}，其中A的核心距離為E’=1，因為在點A的E’鄰域中有點{A,B,D,E}>3;點F到核心對象點A的可達距離為

，因為A到F的歐幾里得距離

大于點A的核心距離1.OPTICS算法額外存儲了每個對象的核心距離和可達距離。基于OPTICS產生的排序信息來提取類簇。2023/7/22OPTICS算法輸入：樣本集D,

鄰域半徑E,

給定點在E領域內成為核心對象的最小領域點數MinPts輸出：具有可達距離信息的樣本點輸出排序方法：1

創建兩個隊列，有序隊列和結果隊列。（有序隊列用來存儲核心對象及其該核心對

象的直接可達對象，并按可達距離升序排列；結果隊列用來存儲樣本點的輸出次序）；

2

如果所有樣本集D中所有點都處理完畢，則算法結束。否則，選擇一個未處理（即不在結果隊列中）且為核心對象的樣本點，找到其所有直接密度可達樣本點，如過該樣本點不存在于結果隊列中，則將其放入有序隊列中，并按可達距離排序；

3

如果有序隊列為空，則跳至步驟2，否則，從有序隊列中取出第一個樣本點（即可達距離最小的樣本點）進行拓展，并將取出的樣本點保存至結果隊列中，如果它不存在結果隊列當中的話。

3.1

判斷該拓展點是否是核心對象，如果不是，回到步驟3，否則找到該拓展點所有的直接密度可達點；3.2

判斷該直接密度可達樣本點是否已經存在結果隊列，是則不處理，否則下一步；3.2

如果有序隊列中已經存在該直接密度可達點，如果此時新的可達距離小于舊的可達距離，則用新可達距離取代舊可達距離，有序隊列重新排序；

重新排序；3.3

如果有序隊列中不存在該直接密度可達樣本點，則插入該點，并對有序隊列

4

算法結束，輸出結果隊列中的有序樣本點。2023/7/22大家或許會很疑惑，這里不也有輸入參數E和MinPts嗎？其實這里的E和MinPts只是起到算法輔助作用，也就是說E和MinPts的細微變化并不會影響到樣本點的相對輸出順序，這對我們分析聚類結果是沒有任何影響。我們采用與先前DBSCAN相同的樣本點集合，對于樣本點a={2,3};b={2,4};c={1,4};d={1,3};e={2,2};f={3,2};g={8,7};h={8,6};i={7,7};j={7,6};k={9,5};l={100,2};//孤立點m={8,20};n={8,19};o={7,18};p={7,17};q={8,21};并且使用相同的E=2

MinPts=4時，輸出具有可達距離信息的樣本點輸出排序OPTICS算法(續)2023/7/221->a:1.02->e:1.03->b:1.04->d:1.05->c:1.41421356237309516->f:1.4142135623730951------7->g:1.41421356237309518->j:1.41421356237309519->k:1.414213562373095110->i:1.414213562373095111->h:1.4142135623730951------12->n:2.013->q:2.014->o:2.015->m:2.0OPTICS(續)2023/7/22如圖，按照算法，分三個階段輸出了三波值,{a,e,b,d,},{c,f,g,j,k,I,h},{n,q,o,m}

這和DBSCAN的類簇結果是一樣的。不僅如此，我們通過分析有序圖還能直接得到當參數E=1.5,minPts=4時DBSCAN的類簇結果，只要在坐標圖中找到Y值小于1.5的樣本點即可，只有兩類{a,e,b,d,c,f},{g,j,k,I,h},其他點被認為是孤立點，和DBSCAN聚類算法取E=1.5,minPts=4時的結果一致。所以說，這個OPTICS聚類算法所得的簇排序信息等價于一個廣泛的參數設置所獲得的基于密度的聚類結果。OPTICS(續)26OPTICS(續)這些值怎樣使用？OPTICS算法創建了數據庫中對象的一個次序,額外存儲了每個對象的核心距離和一個適當的可達距離已經提出了一種算法,基于OPTICS產生的次序信息來抽取聚類.對于小于在生成該次序中采用的距離的任何距離’,為提取所有基于密度的聚類,這些信息是足夠的

一個數據集合的聚類次序可以被圖形化地描述，以助于理解

由于OPTICS算法與DBSCAN在結構上的等價性,它具有和DBSCAN相同的時間復雜度,即當使用空間索引時,復雜度為O(nlogn)

27可達距離對象的簇次序無定義‘28DENCLUE(1998)DENCLUE(DENsity-basedCLUstEring)由Hinneburg和Keim(KDD’98)提出,是基于密度分布函數的聚類方法主要特點堅實的數學基礎,概括了其他的聚類方法,包括基于劃分的,層次的,及基于位置的方法適用于具有大量噪音的數據集可用于高維數據集任意形狀的聚類,它給出了簡潔的數學描述明顯快于現有算法(比DBSCAN快45倍)但是,需要大量參數,要求對密度參數σ和噪音閥值ξ進行仔細的選擇29使用柵格單元,但只保存實際存放數據點的柵格單元信息,并且在一個基于樹的存取結構中管理這些單元.影響函數(Influencefunction):描述數據點在其鄰域的影響.數據空間的整體密度可以被模擬為所有數據點的影響函數的總和聚類可以通過確定密度吸引點(densityattractor)來得到.密度吸引點是全局密度函數的局部最大值.Denclue:技術要點30DENCLUE(續)設x和y是d維特征空間Fd中的對象.數據對象y對x的影響函數是一個函數fyB：Fd→R+0,它是根據一個基本的影響函數fB來定