機器學習中的DBSCAN是什么

本篇內容主要講解“機器學習中的DBSCAN是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“機器學習中的DBSCAN是什么”吧!

一、介紹

DBSCAN是一種基于密度的聚類算法，這類密度聚類算法一般假定類別可以通過樣本分布的緊密程度決定。同一類別的樣本，他們之間的緊密相連的，也就是說，在該類別任意樣本周圍不遠處一定有同類別的樣本存在。

通過將緊密相連的樣本劃為一類，這樣就得到了一個聚類類別。通過將所有各組緊密相連的樣本劃為各個不同的類別，則我們就得到了最終的所有聚類類別結果。

二、DBSCAN密度定義

在上一節我們定性描述了密度聚類的基本思想，本節我們就看看DBSCAN是如何描述密度聚類的。DBSCAN是基于一組鄰域來描述樣本集的緊密程度的，參數(?, MinPts)用來描述鄰域的樣本分布緊密程度。

其中，?描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為?的鄰域中樣本個數的閾值。

　　　　假設我的樣本集是D=(x1,x2,...,xm),則DBSCAN具體的密度描述定義如下：

　　　　1）?-鄰域：表示的是D樣本集中，距離xj的距離小于∈的區域，稱為?-鄰域。在這個區域內的點的個數記為|N?(xj)|。

                                注意：1、在代碼實踐的時候，距離需要業務自己定義。2、?-鄰域數量要不低于2，否則就無法將密度相連的那些點合并到一個簇了，也就失去了DBSCAN原有的意義。

　　　　2) 核心對象：對于任一樣本xj∈D，如果其?-鄰域對應的N?(xj)至少包含MinPts個樣本，即如果|N?(xj)|≥MinPts，則xj是核心對象。　大白話就是，稱為核心對象的前提是這個點周邊有比較多的離得近的點。

　　　　3）密度直達（ 或直接密度可達 ）：如果xi位于xj的?-鄰域中，且xj是核心對象，則稱xi由xj密度直達。注意反之不一定成立，即此時不能說xj由xi密度直達, 除非且xi也是核心對象。

　　　　4）密度可達：對于xi和xj,如果存在樣本序列p1,p2,...,pT,滿足p1=xi,pT=xj, 且pi+1由pi密度直達，則稱xj由xi密度可達。大白話就是：xi和xj能通過其它核心對象連接起來。

此時序列中的傳遞樣本p1,p2,...,pT?1均為核心對象，因為只有核心對象才能使其他樣本密度直達。注意密度可達也不滿足對稱性，這個可以由密度直達的不對稱性得出。

　　　　5）密度相連：對于xi和xj,如果存在核心對象樣本xk，使xi和xj均由xk密度可達，則稱xi和xj密度相連。注意密度相連關系是滿足對稱性的。

　　　　從下圖可以很容易看出理解上述定義，圖中MinPts=5，紅色的點都是核心對象，因為其??-鄰域至少有5個樣本。黑色的樣本是非核心對象。所有核心對象密度直達的樣本在以紅色核心對象為中心的超球體內，如果不在超球體內，則不能密度直達。圖中用綠色箭頭連起來的核心對象組成了密度可達的樣本序列。在這些密度可達的樣本序列的??-鄰域內所有的樣本相互都是密度相連的。

　　　　有了上述定義，DBSCAN的聚類定義就簡單了。

三、DBSCAN密度聚類思想

　　　　DBSCAN的聚類定義很簡單：由密度可達關系導出的最大密度相連的樣本集合，即為我們最終聚類的一個類別，或者說一個簇。

　　　　這個DBSCAN的簇里面可以有一個或者多個核心對象。如果只有一個核心對象，則簇里其他的非核心對象樣本都在這個核心對象的??-鄰域里；如果有多個核心對象，則簇里的任意一個核心對象的??-鄰域中一定有一個其他的核心對象，否則這兩個核心對象無法密度可達。這些核心對象的??-鄰域里所有的樣本的集合組成的一個DBSCAN聚類簇。

　　　　那么怎么才能找到這樣的簇樣本集合呢？DBSCAN使用的方法很簡單，它任意選擇一個沒有類別的核心對象作為種子，然后找到所有這個核心對象能夠密度可達的樣本集合，即為一個聚類簇。接著繼續選擇另一個沒有類別的核心對象去尋找密度可達的樣本集合，這樣就得到另一個聚類簇。一直運行到所有核心對象都有類別為止。

　　　　基本上這就是DBSCAN算法的主要內容了，是不是很簡單？但是我們還是有三個問題沒有考慮。

　　　　第一個是一些異常樣本點或者說少量游離于簇外的樣本點，這些點不在任何一個核心對象在周圍，在DBSCAN中，我們一般將這些樣本點標記為噪音點。

　　　　第二個是距離的度量問題，即如何計算某樣本和核心對象樣本的距離。在DBSCAN中，一般采用最近鄰思想，采用某一種距離度量來衡量樣本距離，比如歐式距離。這和KNN分類算法的最近鄰思想完全相同。對應少量的樣本，尋找最近鄰可以直接去計算所有樣本的距離，如果樣本量較大，則一般采用KD樹或者球樹來快速的搜索最近鄰。如果大家對于最近鄰的思想，距離度量，KD樹和球樹不熟悉，建議參考之前寫的另一篇文章K近鄰法(KNN)原理小結。

　　　　第三種問題比較特殊，某些樣本可能到兩個核心對象的距離都小于??，但是這兩個核心對象由于不是密度直達，又不屬于同一個聚類簇，那么如果界定這個樣本的類別呢？一般來說，此時DBSCAN采用先來后到，先進行聚類的類別簇會標記這個樣本為它的類別。也就是說DBSCAN的算法不是完全穩定的算法。

四、DBSCAN小結

和傳統的K-Means算法相比，DBSCAN最大的不同就是不需要輸入類別數k，當然它最大的優勢是可以發現任意形狀的聚類簇，而不是像K-Means，一般僅僅使用于凸的樣本集聚類。同時它在聚類的同時還可以找出異常點，這點和BIRCH算法類似。

那么我們什么時候需要用DBSCAN來聚類呢？一般來說，如果數據集是稠密的，并且數據集不是凸的，那么用DBSCAN會比K-Means聚類效果好很多。如果數據集不是稠密的，則不推薦用DBSCAN來聚類。

下面對DBSCAN算法的優缺點做一個總結。

DBSCAN的主要優點有：

1） 可以對任意形狀的稠密數據集進行聚類，相對的，K-Means之類的聚類算法一般只適用于凸數據集。

2） 可以在聚類的同時發現異常點，對數據集中的異常點不敏感。

3） 聚類結果沒有偏倚，相對的，K-Means之類的聚類算法初始值對聚類結果有很大影響。

DBSCAN的主要缺點有：

1）如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差，這時用DBSCAN聚類一般不適合。

2） 如果樣本集較大時，聚類收斂時間較長，此時可以對搜索最近鄰時建立的KD樹或者球樹進行規模限制來改進。

3） 調參相對于傳統的K-Means之類的聚類算法稍復雜，主要需要對距離閾值??，鄰域樣本數閾值MinPts聯合調參，不同的參數組合對最后的聚類效果有較大影響。

到此，相信大家對“機器學習中的DBSCAN是什么”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！