各種聚類算法介紹及對比-資料下載頁
2025-06-23 16:43本頁面
【正文】 ts，則稱點P為核心點。③DBSCAN聚類使用到一個k距離的概念，k距離是指：給定數(shù)據(jù)集P={p(i)。 i=0,1,…n}，對于任意點P(i)，計算點P(i)到集合D的子集S={p(1), p(2), …, p(i1), p(i+1), …, p(n)}中所有點之間的距離，距離按照從小到大的順序排序，假設(shè)排序后的距離集合為D={d(1), d(2), …, d(k1), d(k), d(k+1), …,d(n)}，則d(k)就被稱為k距離。也就是說，k距離是點p(i)到所有點（除了p(i)點）之間距離第k近的距離。對待聚類集合中每個點p(i)都計算k距離，最后得到所有點的k距離集合E={e(1), e(2), …, e(n)}。④根據(jù)經(jīng)驗計算半徑Eps：根據(jù)得到的所有點的k距離集合E，對集合E進(jìn)行升序排序后得到k距離集合E’，需要擬合一條排序后的E’集合中k距離的變化曲線圖，然后繪出曲線，通過觀察，將急劇發(fā)生變化的位置所對應(yīng)的k距離的值，確定為半徑Eps的值。⑤根據(jù)經(jīng)驗計算最少點的數(shù)量MinPts：確定MinPts的大小，實際上也是確定k距離中k的值，DBSCAN算法取k=4，則MinPts=4。⑥另外，如果覺得經(jīng)驗值聚類的結(jié)果不滿意，可以適當(dāng)調(diào)整Eps和MinPts的值，經(jīng)過多次迭代計算對比，選擇最合適的參數(shù)值?？梢钥闯觯绻鸐inPts不變，Eps取得值過大，會導(dǎo)致大多數(shù)點都聚到同一個簇中，Eps過小，會導(dǎo)致一個簇的分裂；如果Eps不變，MinPts的值取得過大，會導(dǎo)致同一個簇中點被標(biāo)記為噪聲點，MinPts過小，會導(dǎo)致發(fā)現(xiàn)大量的核心點。我們需要知道的是，DBSCAN算法，需要輸入2個參數(shù)，這兩個參數(shù)的計算都來自經(jīng)驗知識。半徑Eps的計算依賴于計算k距離，DBSCAN取k=4，也就是設(shè)置MinPts=4，然后需要根據(jù)k距離曲線，根據(jù)經(jīng)驗觀察找到合適的半徑Eps的值。2）連通核心點生成簇核心點能夠連通（有些書籍中稱為：“密度可達(dá)”），它們構(gòu)成的以Eps長度為半徑的圓形鄰域相互連接或重疊，這些連通的核心點及其所處的鄰域內(nèi)的全部點構(gòu)成一個簇。假設(shè)MinPts=4，則連通的核心點示例，如下圖所示：計算連通的核心點的思路是，基于廣度遍歷與深度遍歷集合的方式：從核心點集合S中取出一個點p，計算點p與S集合中每個點（除了p點）是否連通，可能會得到一個連通核心點的集合C1，然后從集合S中刪除點p和C1集合中的點，得到核心點集合S1；再從S1中取出一個點p1，計算p1與核心點集合S1集中每個點（除了p1點）是否連通，可能得到一個連通核心點集合C2，再從集合S1中刪除點p1和C2集合中所有點，得到核心點集合S2，……最后得到p、pp……，以及CC……就構(gòu)成一個簇的核心點。最終將核心點集合S中的點都遍歷完成，得到所有的簇。參數(shù)eps的設(shè)置，如果eps設(shè)置過大，則所有的點都會歸為一個簇，如果設(shè)置過小，那么簇的數(shù)目會過多。如果MinPts設(shè)置過大的話，很多點將被視為噪聲點。根據(jù)數(shù)據(jù)點的密度分為三類點：(1)核心點：該點在鄰域內(nèi)的密度超過給定的閥值MinPs。(2)邊界點：該點不是核心點，但是其鄰域內(nèi)包含至少一個核心點。(3)噪音點：不是核心點，也不是邊界點。有了以上對數(shù)據(jù)點的劃分，聚合可以這樣進(jìn)行：各個核心點與其鄰域內(nèi)的所有核心點放在同一個簇中，把邊界點跟其鄰域內(nèi)的某個核心點放在同一個簇中。聚類的效果如下圖，黑色是噪音點：初識聚類算法: 因為DBSCAN使用簇的基于密度的定義，因此它是相對抗噪音的，并且能處理任意形狀和大小的簇。但是如果簇的密度變化很大，例如ABCD四個簇，AB的密度大大大于CD，而且AB附近噪音的密度與簇CD的密度相當(dāng)，這是當(dāng)MinPs較大時，無法識別簇CD，簇CD和AB附近的噪音都被認(rèn)為是噪音；當(dāng)MinPs較小時，能識別簇CD，但AB跟其周圍的噪音被識別為一個簇。這個問題可以基于共享最近鄰(SNN)的聚類結(jié)局。DBSCAN的優(yōu)缺點：優(yōu)點：1. 與Kmeans方法相比，DBSCAN不需要事先知道要形成的簇類的數(shù)量。2. 與Kmeans方法相比，DBSCAN可以發(fā)現(xiàn)任意形狀的簇類。3. 同時，DBSCAN能夠識別出噪聲點。，即Pattern的輸入順序?qū)Y(jié)果的影響不大。但是，對于處于簇類之間邊界樣本，可能會根據(jù)哪個簇類優(yōu)先被探測到而其歸屬有所擺動。缺點：1. DBScan不能很好反映高尺寸數(shù)據(jù)。2. DBScan不能很好反映數(shù)據(jù)集變化的密度。，點之間極為稀疏，密度就很難定義了。9
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1