節(jié)基于密度的聚類(lèi)

1、2.4 基于密度的聚類(lèi)算法w 基于密度的聚類(lèi)算法有：DBSCAN、GDBSCAN、OPTICS、DBCLASD等w 本節(jié)介紹基于密度聚類(lèi)的基本思路和基本概念，然后介紹DBSCANw 基于密度的算法聚類(lèi)時(shí)一般不需給定聚類(lèi)數(shù)k，聚類(lèi)的個(gè)數(shù)由算法的結(jié)果確定。w DBSCAN(Density Based Spatial Clustering of Applications with Noise)一、基本思路w 屬于一個(gè)聚類(lèi)的各點(diǎn)之間距離較小，密度較大。密度類(lèi)似于相似度。w 密度可以用一定范圍內(nèi)點(diǎn)數(shù)來(lái)表示。w 在一個(gè)點(diǎn)的一定距離范圍內(nèi)點(diǎn)很少，則可認(rèn)為該點(diǎn)是孤立點(diǎn)（類(lèi)）。去除孤立點(diǎn)可以減少計(jì)算量，同時(shí)可以

2、提高聚類(lèi)精度。w 點(diǎn)的密度是一種關(guān)系，能傳遞。因此若某點(diǎn)是密度高的，與它鄰近的其它點(diǎn)可以繼續(xù)尋找它們的鄰近點(diǎn)，看它們是否也是密度高的。二、幾個(gè)概念w 直接密度可達(dá)的n點(diǎn)q的Eps鄰域：n點(diǎn)p和q如果滿足如下條件：n則稱點(diǎn)p是從點(diǎn)q直接密度可達(dá)的，并且點(diǎn)q成為核。w 其中Eps和MinPts是需要提供給算法的參數(shù)，分別表示點(diǎn)的鄰域半徑和該鄰域的最少點(diǎn)數(shù)。),(|)(EpsqpdistDpqNMinPtsqNqNp| )(| )2),() 1w 密度可達(dá)的n如果存在點(diǎn)的序列：n其中 是從 直接密度可達(dá)的，則稱點(diǎn)pi+1是從q關(guān)于Eps和MinPts密度可達(dá)的。w 密度相連的n如果存在點(diǎn)r,p,q，

3、p和q都是從點(diǎn)r關(guān)于Eps和MinPts密度可達(dá)的，則稱點(diǎn)p是從點(diǎn)q關(guān)于Eps和MinPts密度相連的w 基于密度的簇n令D表示數(shù)據(jù)集，D的一個(gè)非空集合C滿足下列條件l對(duì)任意點(diǎn)p和q，若 且q是從p關(guān)于Eps和MinPts密度可達(dá)的，則有l(wèi) p與q是關(guān)于Eps和MinPts密度相連的。n則稱C是基于密度的簇12,iq p pp1ipipCpCq:,Cqpw 噪聲點(diǎn)集n令 是數(shù)據(jù)集中關(guān)于不同參數(shù)Eps和MinPts的基于密度的簇，則點(diǎn)集n稱作噪聲點(diǎn)集w 令p為數(shù)據(jù)集D中的一個(gè)點(diǎn)， ,則集合n是基于密度的簇w 令C是一個(gè)關(guān)于Eps和MinPts的簇，p為C中某個(gè)滿足 的點(diǎn)，則C應(yīng)滿足下列條件kCC

4、C,21:|iCpiDpMinPtspN| )(|密度可達(dá)的和關(guān)于是從MinPtsEpspqDqCMinPtspN| )(|密度可達(dá)的和關(guān)于是從MinPtsEpspqDqC關(guān)于密度可達(dá)的圖示三、DBSCAN算法w 輸入 ，Eps和MinPtsw 隨機(jī)選擇一點(diǎn) ，檢索它的Eps鄰域，若該鄰域的點(diǎn)數(shù)不少于MinPts，則點(diǎn) 是第一個(gè)核，它的Eps鄰域內(nèi)的點(diǎn)都是關(guān)于 直接密度可達(dá)的。w 檢索所有從點(diǎn) 的密度可達(dá)點(diǎn)，這就生成第一個(gè)基于密度的簇。w 訪問(wèn)數(shù)據(jù)集的下一個(gè)點(diǎn)，并同樣形成另一個(gè)基于密度的簇。w 基于參數(shù)Eps和MinPts，若沒(méi)有新的點(diǎn)是從任何簇中的點(diǎn)密度可達(dá)的，則計(jì)算結(jié)束。D中剩下的點(diǎn)是噪聲

5、點(diǎn)集，予以刪除。,21nxxxDDxiixixixDBSCAN的特點(diǎn)w 基于密度也需要距離計(jì)算w 每個(gè)基于密度的簇就是一個(gè)聚類(lèi)w 可以識(shí)別孤立點(diǎn)類(lèi)w 計(jì)算時(shí)間復(fù)雜度為O(nlogn)，因此效率較高w 它需要用戶給定控制參數(shù)Eps和MinPts，這兩個(gè)參數(shù)對(duì)聚類(lèi)質(zhì)量有較大影響，而用戶往往不能準(zhǔn)確設(shè)定這兩個(gè)參數(shù)w 高維數(shù)據(jù)集分布不均勻，難以給出一組全局的參數(shù)(Eps和MinPts)來(lái)刻畫(huà)內(nèi)在的聚類(lèi)結(jié)構(gòu)。例2-9 用DBSCAN對(duì)例2-2 實(shí)例聚類(lèi)：Eps=0.6,MinPts=1實(shí)例x屬性1屬性2屬性311.15.20.322.03.50.831.55.00.442.24.00.952.14.20

6、.861.02.00.570.92.10.581.34.80.3例2.9中各點(diǎn)之間的距離矩陣049. 7082. 214. 0012. 144. 248. 2034. 134. 237. 225. 0030. 096. 204. 308. 132. 1056. 181. 183. 171. 055. 063. 1045. 011. 321. 35 . 173. 146. 099. 108765432187654321計(jì)算有關(guān)點(diǎn)的鄰域w 隨機(jī)選擇點(diǎn)x1，根據(jù)上述距離矩陣，可以給出Eps的鄰域?yàn)?，其點(diǎn)數(shù)=2MinPts，因此x1是核。w 再給出 的Eps鄰域，沒(méi)有增加新的點(diǎn)，點(diǎn) 互相直接密度可達(dá)

7、的，它們成為一個(gè)基于密度的簇。w 再選擇x2，求它的Eps鄰域?yàn)閤4， x4的Eps鄰域?yàn)閤5， x5的鄰域沒(méi)有新點(diǎn)，因此它們構(gòu)成基于密度的簇。,83xx83,xx831,xxx求基于密度的簇w 同樣可發(fā)現(xiàn)x6 ，x7構(gòu)成基于密度的簇。w 因此我們找到三個(gè)基于參數(shù)Eps=0.6和MinPts=1的簇w 如果設(shè)Eps=0.5，則x2將從第二簇中分離出來(lái)，成為孤立點(diǎn)。該點(diǎn)可以刪除。,;,;,76542831xxxxxxxxOPTICS簡(jiǎn)介w OPTICS(Ordering Points to Identify the Clustering Structure)w OPTICS與DBSCAN在結(jié)果上是等價(jià)的，時(shí)間復(fù)雜度相同。w OPT