模式識別與人工智能之八

1、Pattern Recognition & artificial IntelligenceLecture 7: 聚類算法（四）,1,主要內(nèi)容,基于密度的聚類算法DBSCAN：基于高密度連通區(qū)域聚類 OPTICS：通過點排序識別聚類結構DENCLUE: 基于密度分布函數(shù)的聚類,2,基于密度的聚類方法,劃分和層次方法旨在發(fā)現(xiàn)球狀類。他們很難發(fā)現(xiàn)任意形狀的類。改進思想，將類看作數(shù)據(jù)空間中由低密度區(qū)域分隔開的高密度對象區(qū)

2、域。這是基于密度的聚類方法的主要策略?；诿芏鹊木垲惙椒梢杂脕磉^濾噪聲孤立點數(shù)據(jù)，發(fā)現(xiàn)任意形狀的類。,3,密度概念,核心對象 (Core object): 一個對象的?–鄰域至少包含最小數(shù)目MinPts個對象。邊界點：不是核心點 ，但落在某個核心 點的 Eps 鄰域內(nèi)的對象稱為邊界點。噪聲：不屬于任何類的對象為噪聲。邊界對象：對于空間中的一個對象，如果它在給定半徑e的鄰域中的對象個數(shù)大于密度閥值MinPts，則該對象被稱為核心

3、對象，否則稱為邊界對象。,4,由一個核心對象和其密度可達的所有對象構成聚類。,直接密度可達的(Directly density reachable, DDR): 給定對象集合D, 如果p是在q的?–鄰域內(nèi), 而q是核心對象, 我們說對象p是從對象q直接密度可達的(如果q是一個核心對象，p屬于q的鄰域，那么稱p直接密度可達q。)密度可達的(density reachable): 存在一個從p到q的DDR對象鏈(如果存在一條鏈，滿足

4、p1=p，pi=q，pi直接密度可達pi+1，則稱p密度可達q),密度概念,兩個參數(shù):Eps: 鄰域的最大半徑MinPts: 在 Eps-鄰域中的最少點數(shù) NEps(q):{q belongs to D | dist(p,q) = MinPts,密度概念,6,密度可達: 點 p 關于Eps, MinPts 是從 q密度可達的, 如果 存在一個節(jié)點鏈 p1, …, pn, p1 = q, pn = p 使得 pi+1 是從pi直

5、接密度可達的密度相連的:點 p關于 Eps, MinPts 與點 q是密度相連的, 如果 存在點 o 使得, p 和 q 都是關于Eps, MinPts 是從 o 密度可達的(如果存在o，o密度可達q和p，則稱p和q是密度連通的),,,,,,,,,,,,,,,,,p,q,,p1,,,密度概念,7,Eg: 假設半徑  ? =3 ， MinPts=3 。點 p 的&#

6、160; ?  鄰域中有點 {m, p, p1, p2, o}, 點 m 的  ?  鄰域中有點 {m, q, p, m1, m2}, 點 q的  ? 鄰域有 {q, m},點 o 的  ?  鄰域中有點 {o, p, s},  點 s 的

7、  ?  鄰域中有點 {o, s, s1}.那么核心對象有 p,m,o,s (q 不是核心對象，因為它對應的  ?  領域中點數(shù)量等于 2 ，小于 MinPts=3) ；點 m 從點 p 直接密度可達，因為 m 在 p 的  ? &#

8、160;領域內(nèi)，并且 p 為核心對象；點 q 從點 p 密度可達，因為點 q 從點 m 直接密度可達，并且點 m 從點 p 直接密度可達；點 q 到點 s 密度相連，因為點 q 從點 p 密度可達，并且 s

9、 從點 p 密度可達。,密度概念：例子,8,密度概念：例子,MinPts=3q是從p密度可達； p不是從q密度可達（q非核心）S和r從o密度可達；o從r密度可達；r, s密度相連,9,DBSCAN (Density Based Spatial Clustering of Applications with Noise),DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類方法，該算法將具有足夠高密度的

10、區(qū)域劃分為類，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的類。它將類定義為密度相連的點的最大集合。,10,DBSCAN通過檢查數(shù)據(jù)集中每個對象的ε-鄰域來尋找聚類。如果一個點p的ε-鄰域包含多于MinPts個對象，則創(chuàng)建一個p作為核心對象的新類C。然后，DBSCAN從C中尋找未被處理對象q的ε-鄰域，如果q的ε-鄰域包含多MinPts個對象，則還未包含在C中的q的鄰點被加入到類中，并且這些點的ε-鄰域將在下一步中進行檢測。這個過程反復執(zhí)行，

11、當沒有新的點可以被添加到任何類時，該過程結束。具體如下：,DBSCAN (Density Based Spatial Clustering of Applications with Noise),11,輸入：數(shù)據(jù)集D，參數(shù)MinPts, ε 輸出：類集合首先將數(shù)據(jù)集D中的所有對象標記unvisited ； do 從D中隨機選取一個unvisited對象p，并將p標記為visited ； if

12、 p的 ε 鄰域 包含的對象數(shù)至少為MinPts個 創(chuàng)建新類C ，并把p添加到c中； 令N為 p的 ε 鄰域 中對象的集合； for N 中每個點pi if pi 是unvisited 標記pi 為visited；

13、 if pi 的ε 鄰域 至少有MinPts個 對象，把這些對象添加到N ； if pi 還不是任何類的對象。將 pi 添加到 類C中 ； end for 輸出C Else 標記p 為噪聲 Untill 沒

14、有標記為unvisited 的對象,DBSCAN (Density Based Spatial Clustering of Applications with Noise),12,下面給出一個樣本事務數(shù)據(jù)庫（見下表），對它實施DBSCAN算法。 根據(jù)所給的數(shù)據(jù)通過對其進行DBSCAN算法，以下為算法的步驟（設n=12，用戶輸入ε=1，MinPts=4）,樣本事務數(shù)據(jù)庫,DBSCAN (Density Based Spatial Clus

15、tering of Applications with Noise),13,Step1: 在數(shù)據(jù)庫中選擇一點1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點（小于4），因此它不是核心點，選擇下一個點。Step2: 在數(shù)據(jù)庫中選擇一點2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點，因此它不是核心點，選擇下一個點。Step3:在數(shù)據(jù)庫中選擇一點3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點。,D

16、BSCAN (Density Based Spatial Clustering of Applications with Noise),14,Step4: 在數(shù)據(jù)庫中選擇一點4，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點。尋找從它出發(fā)可達的點（直接可達4個，間接可達3個），聚出的新類{1，3，4，5，9，10，12}，選擇下一個點。,DBSCAN (Density Based Spatial Clustering o

17、f Applications with Noise),,15,Step5: 在數(shù)據(jù)庫中選擇一點5，已經(jīng)在類1中，選擇下一個點。Step6: 在數(shù)據(jù)庫中選擇一點6，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點。,DBSCAN (Density Based Spatial Clustering of Applications with Noise),16,Step7: 在數(shù)據(jù)庫中選擇一點7，由于在以它為圓

18、心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，尋找從它出發(fā)可達的點，聚出的新類{2，6，7，8，11}，選擇下一個點。,DBSCAN (Density Based Spatial Clustering of Applications with Noise),,17,Step8: 在數(shù)據(jù)庫中選擇一點8，已經(jīng)在類2中，選擇下一個點。Step9: 在數(shù)據(jù)庫中選擇一點9，已經(jīng)在類1中，選擇下一個點。Step10: 在數(shù)據(jù)庫中選擇一點10

19、，已經(jīng)在類1中，選擇下一個點。Step11: 在數(shù)據(jù)庫中選擇一點11，已經(jīng)在類2中，選擇下一個點。Step12: 選擇12點，已經(jīng)在類1中，由于這已經(jīng)是最后一點所有點都以處理，程序終止。,DBSCAN (Density Based Spatial Clustering of Applications with Noise),18,算法執(zhí)行過程：,DBSCAN (Density Based Spatial Clustering of

20、Applications with Noise),19,Original Points,Clusters,特點： 抗噪聲能處理任意形狀聚類,DBSCAN (Density Based Spatial Clustering of Applications with Noise),20,Pros:能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點，可發(fā)現(xiàn)任意形狀的聚類，有效地處理數(shù)據(jù)集中的噪聲數(shù)據(jù)，數(shù)據(jù)輸入順序不敏感Cons: 輸

21、入?yún)?shù)敏感．確定參數(shù)ε，MinPts困難，若選取不當，將造成聚類質量下降．由于在DBSCAN算法中，變量ε，MinPts是全局惟一的， 當空間聚類的密度不均勻、聚類間距離相差很大時，聚類質量較差。計算密度單元的計算復雜度大，需要建立空間索引來降低計算量，且對數(shù)據(jù)維數(shù)的伸縮性較差。這類方法需要掃描整個數(shù)據(jù)庫，每個數(shù)據(jù)對象都可能引起一次查詢，因此當數(shù)據(jù)量大時會造成頻繁的I/O操作。,DBSCAN (Density Based Spati

22、al Clustering of Applications with Noise),21,下圖中所描述的數(shù)據(jù)集不能通過一個全局密度參數(shù)同時區(qū)分出類A 、B 、C、C1、C2和C3，只能得到A 、B 、C或C1、C2和C3，對于C1、C2和C3而言A 、B 、C都是噪聲。,DBSCAN ：can not handle varying densities,22,DBSCAN：sensitive to parameters,23,DBSCAN

23、：Determining the Parameters ε and MinPts,24,？,OPTICS (Ordering Points To Identify the Clustering Structure),為了同時構建不同的聚類, 應當以特定的順序來處理對象. 優(yōu)先選擇最小的?值密度可達的對象, 以便高密度的聚類能被首先完成 ；每個對象需要存儲兩個值：對象p的核心距離(core-distance)是使得p成為核心對象的最

24、小?。如果p不是核心對象， p的核心距離沒有定義 。對象q關于另一個對象p的可達距離(reachability-distance )是p的核心距離和p與q的歐幾里得距離之間的較大值. 如果p不是一個核心對象, p和q之間的可達距離沒有定義,OPTICS算法通過對象排序識別聚類結構。,25,OPTICS (Ordering Points To Identify the Clustering Structure),Eg: 設?=6(mm)

25、, MinPts=5. p的核心距離是p與四個最近的數(shù)據(jù)對象之間的距離?’ q1關于p的可達距離是p的核心距離(即?’=3mm), 因為它比從p到q1的歐幾里得距離要大. q2關于p的可達距離是從p到q2的歐幾里得距離, 它大于p的 核心距離,P的核心距離,可達距離 (p,q1)=?’=3mm可達距離 (p,q2)=d(p,q2),26,OPTICS (Ordering Points To Identify the Cluste

26、ring Structure),輸入：樣本集D, 鄰域半徑E, 給定點在E領域內(nèi)成為核心對象的最小領域點數(shù)MinPts輸出：具有可達距離信息的樣本點輸出排序方法： Step1: 創(chuàng)建兩個隊列，有序隊列和結果隊列。（有序隊列用來存儲核心對象及其該核心對象的直接可達對象，并按可達距離升序排列；結果隊列用來存儲樣本點的輸出次序）； Step2: 如果所有樣本集D中所有點都處理完畢，則算法結束。否則，選擇

27、一個未處理（即不在結果隊列中）且為核心對象的樣本點，找到其所有直接密度可達樣本點，如果該樣本點不存在于結果隊列中，則將其放入有序隊列中，并按可達距離排序； Step3: 如果有序隊列為空，則跳至上一步，否則，從有序隊列中取出第一個樣本點（即可達距離最小的樣本點）進行拓展，并將取出的樣本點保存至結果隊列中，如果它不存在結果隊列當中的話:,27,Step3.1 判斷該拓展點是否是核心對象，如果不是，回到步驟3，否則找到該拓展點所有的

28、直接密度可達點；Step3.2  判斷該直接密度可達樣本點是否已經(jīng)存在結果隊列，是則不處理，否則下一步；Step3.3 如果有序隊列中已經(jīng)存在該直接密度可達點，如果此時新的可達距離小于舊的可達距離，則用新可達距離取代舊可達距離，有序隊列重新排序；重新排序；Step3.4 如果有序隊列中不存在該直接密度可達樣本點，則插入該點，并對有序隊列Step4: 算法結束，輸出結果隊列中的有序樣本點。,OPTICS (Orderi

29、ng Points To Identify the Clustering Structure),28,OPTICS (Ordering Points To Identify the Clustering Structure),Example:,有如下表所示的數(shù)據(jù)集。當設置ε=2，MinPts=4時，采用OPTICS算法進行聚類的過程如下：,29,OPTICS (Ordering Points To Identify the Cluste

30、ring Structure),Example:,數(shù)據(jù)分布散點圖,求各個點的可達距離，如下表所示，表中序號指出輸出次序，對于未輸出的點，表示該點的可達距離沒有定義。,30,OPTICS (Ordering Points To Identify the Clustering Structure),Example:,如圖，按照算法，分三個階段輸出了三波值,{a,e,b,d,} ,{c,f,g,j,k,I,h},{n,q,o,m}這和DBS

31、CAN的聚類結果是一樣的。不僅如此，我們通過分析有序圖還能直接得到當參數(shù)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聚類算法所得的類排序信息等價于一個廣泛的參數(shù)設置所獲得的基于密度的聚類結果。,31,OPTICS

32、 (Ordering Points To Identify the Clustering Structure),對于真實的，高維的數(shù)據(jù)集合而言，絕大多數(shù)算法對參數(shù)值是非常敏感的，參數(shù)的設置通常是依靠經(jīng)驗，難以確定。而OPTICS算法可以幫助找出合適的參數(shù)。OPTICS算法通過對象排序識別聚類結構。OPTICS沒有顯式地產(chǎn)生一個數(shù)據(jù)類類，它為自動和交互的聚類分析計算一個類排序。這個次序代表了數(shù)據(jù)的基于密度的聚類結構。,特點：,32,D

33、BSCAN VS OPTICS,When OPTICS Works Well,,,,,,,Cluster-order of the objects,,,,,,,When OPTICS Does NOT Work Well,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Cluster-order of the objects,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

34、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,Definition 1: Influence FunctionThe influence of a data point y at a point x in the data space is modeled by a function,e.g.:,DENCLUE (DENsity-b

35、ased CLUstEring),Definition 2: Density FunctionThe density at a point x in the data space is defined as the sum of influences of all data points x,e.g.:,DENCLUE (DENsity-based CLUstEring),Example,DENCLUE (DENsity-based

36、CLUstEring),Definition 3: GradientThe gradient of a density function is defined ase.g.:,DENCLUE (DENsity-based CLUstEring),Definition 4: Density AttractorA point x* ∈Fd is called a density attractor for a given infl

37、uence function, if f (x*) is a local maximum of the density-function,Example of Density-Attractor,DENCLUE (DENsity-based CLUstEring),Definition 5: Density attracted pointA point xk ∈Fd is density attracted to a density

38、attractor x*, if k ∈N: d(xk, x*) ? ? withxi is a point in the path between xk and its attractor x*density-attracted points are determined by a gradient-based hill-climbing method,DENCLUE (DENsity-based CLUstEring),

39、Definition 6: Center-Defined ClusterA center-defined cluster with density-attractor x* ( ) is the subset of the database which is density-attracted by x*.,DENCLUE (DENsity-based CLUstEring),Definitio

40、n 7: Arbitrary-shaped clusterA arbitrary-shaped cluster for the set of density-attractors X is a subset C? D, where1) ?x?C, x* ? X: x is density attracted to x* and2) ?x1*,x2*?X: ? a path P? Fd fromx1* to

41、 x2* with ? p?P:,DENCLUE (DENsity-based CLUstEring),Noise-InvarianceAssumption: Noise is uniformly distributed in the data spaceLemma: The density-attractors do not change when the noise level increases.Idea of the Pr

42、oof:- partition density function into signal and noise- density function of noise approximates a constant.,DENCLUE (DENsity-based CLUstEring),Example of noise invariance,DENCLUE (DENsity-based CLUstEring),Parameter-σ

43、:It describes the influence of a data point in the data space. It determines the number of clusters.,DENCLUE (DENsity-based CLUstEring),Parameter-σ:Choose σ such that number of density attractors is constant for the l

44、ongest interval of σ.,DENCLUE (DENsity-based CLUstEring),Parameter- ξIt describes whether a density-attractor is significant, helping reduce the number of density-attractors such that improving the performance.,DENCLUE

45、(DENsity-based CLUstEring),49,Clusters are defined according to the point density function which is the sum of influence functions of the data points.It has good clustering in data sets with large amounts of noise.It c

46、an deal with high-dimensional data sets.It is significantly faster than existing algorithms,DENCLUE (DENsity-based CLUstEring),Properties,50,總 結,掌握DBSCAN, DENCLUE, OPTICS的基本思想掌握DBSCAN, DENCLUE, OPTICS的優(yōu)缺點能夠利用python實