模式識(shí)別與人工智能之八

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

2、域。這是基于密度的聚類方法的主要策略。基于密度的聚類方法可以用來(lái)過(guò)濾噪聲孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的類。,3,密度概念,核心對(duì)象 (Core object): 一個(gè)對(duì)象的?–鄰域至少包含最小數(shù)目MinPts個(gè)對(duì)象。邊界點(diǎn)：不是核心點(diǎn) ，但落在某個(gè)核心 點(diǎn)的 Eps 鄰域內(nèi)的對(duì)象稱為邊界點(diǎn)。噪聲：不屬于任何類的對(duì)象為噪聲。邊界對(duì)象：對(duì)于空間中的一個(gè)對(duì)象，如果它在給定半徑e的鄰域中的對(duì)象個(gè)數(shù)大于密度閥值MinPts，則該對(duì)象被稱為核心

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

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

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

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

7、  ?  鄰域中有點(diǎn) {o, s, s1}.那么核心對(duì)象有 p,m,o,s (q 不是核心對(duì)象，因?yàn)樗鼘?duì)應(yīng)的  ?  領(lǐng)域中點(diǎn)數(shù)量等于 2 ，小于 MinPts=3) ；點(diǎn) m 從點(diǎn) p 直接密度可達(dá)，因?yàn)?#160;m 在 p 的  ? &#

8、160;領(lǐng)域內(nèi)，并且 p 為核心對(duì)象；點(diǎn) q 從點(diǎn) p 密度可達(dá)，因?yàn)辄c(diǎn) q 從點(diǎn) m 直接密度可達(dá)，并且點(diǎn) m 從點(diǎn) p 直接密度可達(dá)；點(diǎn) q 到點(diǎn) s 密度相連，因?yàn)辄c(diǎn) q 從點(diǎn) p 密度可達(dá)，并且 s

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

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

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

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

13、 if pi 的ε 鄰域 至少有MinPts個(gè) 對(duì)象，把這些對(duì)象添加到N ； if pi 還不是任何類的對(duì)象。將 pi 添加到 類C中 ； end for 輸出C Else 標(biāo)記p 為噪聲 Untill 沒(méi)

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

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

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

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

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

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

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

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

22、al Clustering of Applications with Noise),21,下圖中所描述的數(shù)據(jù)集不能通過(guò)一個(gè)全局密度參數(shù)同時(shí)區(qū)分出類A 、B 、C、C1、C2和C3，只能得到A 、B 、C或C1、C2和C3，對(duì)于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),為了同時(shí)構(gòu)建不同的聚類, 應(yīng)當(dāng)以特定的順序來(lái)處理對(duì)象. 優(yōu)先選擇最小的?值密度可達(dá)的對(duì)象, 以便高密度的聚類能被首先完成 ；每個(gè)對(duì)象需要存儲(chǔ)兩個(gè)值：對(duì)象p的核心距離(core-distance)是使得p成為核心對(duì)象的最

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

25、, MinPts=5. p的核心距離是p與四個(gè)最近的數(shù)據(jù)對(duì)象之間的距離?’ q1關(guān)于p的可達(dá)距離是p的核心距離(即?’=3mm), 因?yàn)樗葟膒到q1的歐幾里得距離要大. q2關(guān)于p的可達(dá)距離是從p到q2的歐幾里得距離, 它大于p的 核心距離,P的核心距離,可達(dá)距離 (p,q1)=?’=3mm可達(dá)距離 (p,q2)=d(p,q2),26,OPTICS (Ordering Points To Identify the Cluste

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

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

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

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

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

31、CAN的聚類結(jié)果是一樣的。不僅如此，我們通過(guò)分析有序圖還能直接得到當(dāng)參數(shù)E=1.5,minPts=4時(shí)DBSCAN的類類結(jié)果，只要在坐標(biāo)圖中找到Y(jié)值小于1.5的樣本點(diǎn)即可，只有兩類{a,e,b,d,c,f} ,{g,j,k,I,h},其他點(diǎn)被認(rèn)為是孤立點(diǎn)，和DBSCAN聚類算法取E=1.5,minPts=4時(shí)的結(jié)果一致。所以說(shuō)，OPTICS聚類算法所得的類排序信息等價(jià)于一個(gè)廣泛的參數(shù)設(shè)置所獲得的基于密度的聚類結(jié)果。,31,OPTICS

32、 (Ordering Points To Identify the Clustering Structure),對(duì)于真實(shí)的，高維的數(shù)據(jù)集合而言，絕大多數(shù)算法對(duì)參數(shù)值是非常敏感的，參數(shù)的設(shè)置通常是依靠經(jīng)驗(yàn)，難以確定。而OPTICS算法可以幫助找出合適的參數(shù)。OPTICS算法通過(guò)對(duì)象排序識(shí)別聚類結(jié)構(gòu)。OPTICS沒(méi)有顯式地產(chǎn)生一個(gè)數(shù)據(jù)類類，它為自動(dòng)和交互的聚類分析計(jì)算一個(gè)類排序。這個(gè)次序代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)。,特點(diǎn)：,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,總 結(jié),掌握DBSCAN, DENCLUE, OPTICS的基本思想掌握DBSCAN, DENCLUE, OPTICS的優(yōu)缺點(diǎn)能夠利用python實(shí)