俗話說,，物以類聚人以群分,。聚類(Clustering)是按照某個特定標準(如距離)把一個數(shù)據(jù)集分割成不同的類或簇，使得同一個簇內的數(shù)據(jù)對象的相似性盡可能大,，同時不在同一個簇中的數(shù)據(jù)對象的差異性也盡可能地大,。也即聚類后同一類的數(shù)據(jù)盡可能聚集到一起，不同類數(shù)據(jù)盡量分離,。聚類算法種類豐富,，根據(jù)聚類方法角度的不同大致可以劃分為以下幾種:

在python“的經(jīng)典機器學習庫--sklearn的參考文檔中，有一個非常直觀的圖可以對比不后聚類算法:

    從圖中可以看到,，對于不規(guī)則形狀分布的數(shù)據(jù),，K-means算法表現(xiàn)較差，難以聚出高質量的簇; 譜聚類(Spectral Clustering) ,、DBSCAN和OPTICS對于各種奇形怪狀分布的數(shù)據(jù)表現(xiàn)都較好,，其他算法或多或少會在一些場景上翻車

    由此可見，基于密度的聚類算法(DBSCAN和OPTICS) 通用性更高,，能在大多數(shù)情況下聚出質量較高的簇,。接下來將給大家深入介紹DBSCAN算法。

    DBSCAN（Density-Based Spatial Clustering of Applications with Noise,，具有噪聲的基于密度的聚類方法）是一種基于密度的空間聚類算法。

    該算法將具有足夠密度的區(qū)域劃分為簇,，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇,，它將簇定義為密度相連的點的最大集合。

    可以在有噪音的數(shù)據(jù)中發(fā)現(xiàn)各種形狀和各種大小的簇,。

尋找被低密度區(qū)域分離的高密度區(qū)域,，這些高密度區(qū)域就是一個一個的簇，這里的密度指的是一個樣本點的領域半徑內包含的點的數(shù)目

    可以用來過濾噪聲孤立點數(shù)據(jù),，發(fā)現(xiàn)任意形狀的簇（因為它將簇定義為密度相連的點的最大集合）

與k-means算法的不同之處在于它不需要事先指定劃分的簇的數(shù)目,。

1.1基礎概念

    作為最經(jīng)典的密度聚類算法，DBSCAN使用一組關于“鄰域”概念的參數(shù)來描述樣本分布的緊密程度,，將具有足夠密度的區(qū)域劃分成簇,，且能在有噪聲的條件下發(fā)現(xiàn)任意形狀的簇。在學習具體算法前,，我們先定義幾個相關的概念：

鄰域：對于任意給定樣本x和距離ε,，x的ε鄰域是指到x距離不超過ε的樣本的集合；

核心對象：若樣本x的ε鄰域內至少包含minPts個樣本,，則x是一個核心對象,；

密度直達：若樣本b在a的ε鄰域內,，且a是核心對象，則稱樣本b由樣本x密度直達,；

密度可達：對于樣本a,，b，如果存在樣例p1,p2,...,pn,其中,，p1=a,pn=b,且序列中每一個樣本都與它的前一個樣本密度直達,，則稱樣本a與b密度可達；

密度相連：對于樣本a和b,，若存在樣本k使得a與k密度可達,，且k與b密度可達，則a與b密度相連,。

當minPts=3時,，虛線圈表示ε鄰域，則從圖中我們可以觀察到：

x1是核心對象,；

x2由x1密度直達,；

x3由x1密度可達；

x3與x4密度相連,。

    為什么要定義這些看上去差不多又容易把人繞暈的概念呢,？其實ε鄰域使用（ε，minpts）這兩個關鍵的參數(shù)來描述鄰域樣本分布的緊密程度,，規(guī)定了在一定鄰域閾值內樣本的個數(shù)（這不就是密度嘛）,。那有了這些概念，如何根據(jù)密度進行聚類呢,？

1.2 DBSCAN聚類的原理

    由密度可達關系導出最大密度相連的樣本集合（聚類）,。這樣的一個集合中有一個或多個核心對象，如果只有一個核心對象,，則簇中其他非核心對象都在這個核心對象的ε鄰域內,；如果是多個核心對象，那么任意一個核心對象的ε鄰域內一定包含另一個核心對象（否則無法密度可達）,。這些核心對象以及包含在它ε鄰域內的所有樣本構成一個類。

    那么,，如何找到這樣一個樣本集合呢,？一開始任意選擇一個沒有被標記的核心對象，找到它的所有密度可達對象,，即一個簇,，這些核心對象以及它們ε鄰域內的點被標記為同一個類；然后再找一個未標記過的核心對象,，重復上邊的步驟,，直到所有核心對象都被標記為止,。

    算法的思想很簡單，但是我們必須考慮一些細節(jié)問題才能產(chǎn)出一個好的聚類結果：

    首先對于一些不存在任何核心對象鄰域內的點,，再DBSCAN中我們將其標記為離群點（異常）,；

    第二個是距離度量，如歐式距離,，在我們要確定ε鄰域內的點時,，必須要計算樣本點到所有點之間的距離，對于樣本數(shù)較少的場景,，還可以應付,，如果數(shù)據(jù)量特別大，一般采用KD樹或者球樹來快速搜索最近鄰,，不熟悉這兩種方法的同學可以找相關文獻看看,，這里不再贅述；

    第三個問題是如果存在樣本到兩個核心對象的距離都小于ε,，但這兩個核心對象不屬于同一個類,，那么該樣本屬于哪一個類呢？一般DBSCAN采用先來后到的方法,，樣本將被標記成先聚成的類,。

    之前我們學過了kmeans算法，用戶需要給出聚類的個數(shù)k,，然而我們往往對k的大小無法確定,。DBSCAN算法最大的優(yōu)勢就是無需給定聚類個數(shù)k，且能夠發(fā)現(xiàn)任意形狀的聚類,，且在聚類過程中能自動識別出離群點,。那么，我們在什么時候使用DBSCAN算法來聚類呢,？一般來說,，如果數(shù)據(jù)集比較稠密且形狀非凸，用密度聚類的方法效果要好一些,。

1.3 DBSCAN優(yōu)缺點

優(yōu)點：

不需要事先指定聚類個數(shù),，且可以發(fā)現(xiàn)任意形狀的聚類；

對異常點不敏感,，在聚類過程中能自動識別出異常點,；

聚類結果不依賴于節(jié)點的遍歷順序；

缺點：

對于密度不均勻,，聚類間分布差異大的數(shù)據(jù)集,，聚類質量變差；

樣本集較大時,，算法收斂時間較長,；

調參較復雜,，要同時考慮兩個參數(shù)；

另見：

OPTICS

在EPS的多個值上進行類似的聚類,。我們的實現(xiàn)是為內存使用而優(yōu)化的,。

注

有關示例，請看examples/cluster/plot_dbscan.py.

此實現(xiàn)批量計算所有鄰域查詢,，這會將內存復雜度增加到O(n.d)，其中d是鄰居的平均數(shù)量,，而原始DBSCAN的內存復雜度為O(n),。根據(jù)algorithm的不同,，在查詢這些最近的鄰域時，它可能會吸引更高的內存復雜度,。

避免查詢復雜性的一種方法是使用 NearestNeighbors.radius_neighbors_graph并設置 mode='distance',預先計算塊中的稀疏鄰域,，然后在這里使用 metric='precomputed' 。

另一種減少內存和計算時間的方法是刪除(接近)重復點,，并且使用 sample_weight 代替,。

參考

Ester, M., H. P. Kriegel, J. Sander, and X. Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise”. In: Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, pp. 226-231. 1996

Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. ACM Transactions on Database Systems (TODS), 42(3), 19.

示例

 from sklearn.cluster import DBSCAN
 import numpy as np
 X = np.array([[1, 2], [2, 2], [2, 3],
.               [8, 7], [8, 8], [25, 80]])
 clustering = DBSCAN(eps=3, min_samples=2).fit(X)
 clustering.labels_
array([ 0,  0,  0,  1,  1, -1])
 clustering
DBSCAN(eps=3, min_samples=2)

方法