機(jī)器學(xué)習(xí)中的DBSCAN是什么

本篇內(nèi)容主要講解“機(jī)器學(xué)習(xí)中的DBSCAN是什么”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“機(jī)器學(xué)習(xí)中的DBSCAN是什么”吧!

一、介紹

DBSCAN是一種基于密度的聚類(lèi)算法，這類(lèi)密度聚類(lèi)算法一般假定類(lèi)別可以通過(guò)樣本分布的緊密程度決定。同一類(lèi)別的樣本，他們之間的緊密相連的，也就是說(shuō)，在該類(lèi)別任意樣本周?chē)贿h(yuǎn)處一定有同類(lèi)別的樣本存在。

通過(guò)將緊密相連的樣本劃為一類(lèi)，這樣就得到了一個(gè)聚類(lèi)類(lèi)別。通過(guò)將所有各組緊密相連的樣本劃為各個(gè)不同的類(lèi)別，則我們就得到了最終的所有聚類(lèi)類(lèi)別結(jié)果。

二、DBSCAN密度定義

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

其中，?描述了某一樣本的鄰域距離閾值，MinPts描述了某一樣本的距離為?的鄰域中樣本個(gè)數(shù)的閾值。

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

　　　　1）?-鄰域：表示的是D樣本集中，距離xj的距離小于∈的區(qū)域，稱(chēng)為?-鄰域。在這個(gè)區(qū)域內(nèi)的點(diǎn)的個(gè)數(shù)記為|N?(xj)|。

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

　　　　2) 核心對(duì)象：對(duì)于任一樣本xj∈D，如果其?-鄰域?qū)?yīng)的N?(xj)至少包含MinPts個(gè)樣本，即如果|N?(xj)|≥MinPts，則xj是核心對(duì)象?！?strong>大白話就是，稱(chēng)為核心對(duì)象的前提是這個(gè)點(diǎn)周邊有比較多的離得近的點(diǎn)。

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

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

此時(shí)序列中的傳遞樣本p1,p2,...,pT?1均為核心對(duì)象，因?yàn)橹挥泻诵膶?duì)象才能使其他樣本密度直達(dá)。注意密度可達(dá)也不滿足對(duì)稱(chēng)性，這個(gè)可以由密度直達(dá)的不對(duì)稱(chēng)性得出。

　　　　5）密度相連：對(duì)于xi和xj,如果存在核心對(duì)象樣本xk，使xi和xj均由xk密度可達(dá)，則稱(chēng)xi和xj密度相連。注意密度相連關(guān)系是滿足對(duì)稱(chēng)性的。

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

　　　　有了上述定義，DBSCAN的聚類(lèi)定義就簡(jiǎn)單了。

三、DBSCAN密度聚類(lèi)思想

　　　　DBSCAN的聚類(lèi)定義很簡(jiǎn)單：由密度可達(dá)關(guān)系導(dǎo)出的最大密度相連的樣本集合，即為我們最終聚類(lèi)的一個(gè)類(lèi)別，或者說(shuō)一個(gè)簇。

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

　　　　那么怎么才能找到這樣的簇樣本集合呢？DBSCAN使用的方法很簡(jiǎn)單，它任意選擇一個(gè)沒(méi)有類(lèi)別的核心對(duì)象作為種子，然后找到所有這個(gè)核心對(duì)象能夠密度可達(dá)的樣本集合，即為一個(gè)聚類(lèi)簇。接著繼續(xù)選擇另一個(gè)沒(méi)有類(lèi)別的核心對(duì)象去尋找密度可達(dá)的樣本集合，這樣就得到另一個(gè)聚類(lèi)簇。一直運(yùn)行到所有核心對(duì)象都有類(lèi)別為止。

　　　　基本上這就是DBSCAN算法的主要內(nèi)容了，是不是很簡(jiǎn)單？但是我們還是有三個(gè)問(wèn)題沒(méi)有考慮。

　　　　第一個(gè)是一些異常樣本點(diǎn)或者說(shuō)少量游離于簇外的樣本點(diǎn)，這些點(diǎn)不在任何一個(gè)核心對(duì)象在周?chē)?，在DBSCAN中，我們一般將這些樣本點(diǎn)標(biāo)記為噪音點(diǎn)。

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

　　　　第三種問(wèn)題比較特殊，某些樣本可能到兩個(gè)核心對(duì)象的距離都小于??，但是這兩個(gè)核心對(duì)象由于不是密度直達(dá)，又不屬于同一個(gè)聚類(lèi)簇，那么如果界定這個(gè)樣本的類(lèi)別呢？一般來(lái)說(shuō)，此時(shí)DBSCAN采用先來(lái)后到，先進(jìn)行聚類(lèi)的類(lèi)別簇會(huì)標(biāo)記這個(gè)樣本為它的類(lèi)別。也就是說(shuō)DBSCAN的算法不是完全穩(wěn)定的算法。

四、DBSCAN小結(jié)

和傳統(tǒng)的K-Means算法相比，DBSCAN最大的不同就是不需要輸入類(lèi)別數(shù)k，當(dāng)然它最大的優(yōu)勢(shì)是可以發(fā)現(xiàn)任意形狀的聚類(lèi)簇，而不是像K-Means，一般僅僅使用于凸的樣本集聚類(lèi)。同時(shí)它在聚類(lèi)的同時(shí)還可以找出異常點(diǎn)，這點(diǎn)和BIRCH算法類(lèi)似。

那么我們什么時(shí)候需要用DBSCAN來(lái)聚類(lèi)呢？一般來(lái)說(shuō)，如果數(shù)據(jù)集是稠密的，并且數(shù)據(jù)集不是凸的，那么用DBSCAN會(huì)比K-Means聚類(lèi)效果好很多。如果數(shù)據(jù)集不是稠密的，則不推薦用DBSCAN來(lái)聚類(lèi)。

下面對(duì)DBSCAN算法的優(yōu)缺點(diǎn)做一個(gè)總結(jié)。

DBSCAN的主要優(yōu)點(diǎn)有：

1） 可以對(duì)任意形狀的稠密數(shù)據(jù)集進(jìn)行聚類(lèi)，相對(duì)的，K-Means之類(lèi)的聚類(lèi)算法一般只適用于凸數(shù)據(jù)集。

2） 可以在聚類(lèi)的同時(shí)發(fā)現(xiàn)異常點(diǎn)，對(duì)數(shù)據(jù)集中的異常點(diǎn)不敏感。

3） 聚類(lèi)結(jié)果沒(méi)有偏倚，相對(duì)的，K-Means之類(lèi)的聚類(lèi)算法初始值對(duì)聚類(lèi)結(jié)果有很大影響。

DBSCAN的主要缺點(diǎn)有：

1）如果樣本集的密度不均勻、聚類(lèi)間距差相差很大時(shí)，聚類(lèi)質(zhì)量較差，這時(shí)用DBSCAN聚類(lèi)一般不適合。

2） 如果樣本集較大時(shí)，聚類(lèi)收斂時(shí)間較長(zhǎng)，此時(shí)可以對(duì)搜索最近鄰時(shí)建立的KD樹(shù)或者球樹(shù)進(jìn)行規(guī)模限制來(lái)改進(jìn)。

3） 調(diào)參相對(duì)于傳統(tǒng)的K-Means之類(lèi)的聚類(lèi)算法稍復(fù)雜，主要需要對(duì)距離閾值??，鄰域樣本數(shù)閾值MinPts聯(lián)合調(diào)參，不同的參數(shù)組合對(duì)最后的聚類(lèi)效果有較大影響。

到此，相信大家對(duì)“機(jī)器學(xué)習(xí)中的DBSCAN是什么”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！