聚類本文轉(zhuǎn)載自公眾號(hào)“讀芯術(shù)”(ID：AI_Discovery)分析是一種無(wú)監(jiān)督學(xué)習(xí)法，它將數(shù)據(jù)點(diǎn)分離成若干個(gè)特定的群或組，使得在某種意義上同一組中的數(shù)據(jù)點(diǎn)具有相似的性質(zhì)，不同組中的數(shù)據(jù)點(diǎn)具有不同的性質(zhì)。

聚類分析包括基于不同距離度量的多種不同方法。例如。K均值(點(diǎn)之間的距離)、Affinity propagation(圖之間的距離)、均值漂移(點(diǎn)之間的距離)、DBSCAN(最近點(diǎn)之間的距離)、高斯混合(到中心的馬氏距離)、譜聚類(圖之間距離)等。

2014年，DBSCAN算法在領(lǐng)先的數(shù)據(jù)挖掘會(huì)議ACM SIGKDD上獲得the testof time獎(jiǎng)(授予在理論和實(shí)踐中受到廣泛關(guān)注的算法)。

所有聚類法都使用相同的方法，即首先計(jì)算相似度，然后使用相似度將數(shù)據(jù)點(diǎn)聚類為組或群。本文將重點(diǎn)介紹具有噪聲的基于密度的聚類方法(DBSCAN)。

既然已經(jīng)有了K均值聚類，為什么還需要DBSCAN這樣的基于密度的聚類算法呢?

K均值聚類可以將松散相關(guān)的觀測(cè)聚類在一起。每一個(gè)觀測(cè)最終都成為某個(gè)聚類的一部分，即使這些觀測(cè)在向量空間中分散得很遠(yuǎn)。由于聚類依賴于聚類元素的均值，因此每個(gè)數(shù)據(jù)點(diǎn)在形成聚類中都起著作用。

數(shù)據(jù)點(diǎn)的輕微變化可能會(huì)影響聚類結(jié)果。由于聚類的形成方式，這個(gè)問(wèn)題在DBSCAN中大大減少。這通常不是什么大問(wèn)題，除非遇到一些具有古怪形狀的數(shù)據(jù)。

使用K均值的另一個(gè)困難是需要指定聚類的數(shù)量(“k”)以便使用。很多時(shí)候不會(huì)預(yù)先知道什么是合理的k值。

DBSCAN的優(yōu)點(diǎn)在于，不必指定使用它的聚類數(shù)量。需要的只是一個(gè)計(jì)算值之間距離的函數(shù)，以及一些將某些距離界定為“接近”的指令。在各種不同的分布中，DBSCAN也比K均值產(chǎn)生更合理的結(jié)果。下圖說(shuō)明了這一事實(shí)：

基于密度的聚類算法

基于密度的聚類是無(wú)監(jiān)督學(xué)習(xí)法，基于數(shù)據(jù)空間中的聚類是高點(diǎn)密度的連續(xù)區(qū)域，通過(guò)低點(diǎn)密度的連續(xù)區(qū)域與其他此類聚類分離，來(lái)識(shí)別數(shù)據(jù)中獨(dú)特的組/聚類。

具有噪聲的基于密度的聚類方法(DBSCAN)是基于密度聚類的一種基本算法。它可以從大量的數(shù)據(jù)中發(fā)現(xiàn)不同形狀和大小的聚類，這些聚類中正包含著噪聲和異常值。

DBSCAN算法使用以下兩種參數(shù)：

• eps (ε)：一種距離度量，用于定位任何點(diǎn)的鄰域內(nèi)的點(diǎn)。
• minPts：聚類在一起的點(diǎn)的最小數(shù)目(一個(gè)閾值)，使一個(gè)區(qū)域界定為密集。

如果探究?jī)蓚€(gè)稱為密度可達(dá)性(DensityReachability)和密度連接性(DensityConnectivity)的概念，就可以理解這些參數(shù)。

密度方面的可達(dá)性(Reachability)建立了一個(gè)可以到達(dá)另一個(gè)點(diǎn)的點(diǎn)，如果該點(diǎn)位于與另一個(gè)點(diǎn)的特定距離(eps)內(nèi)。

連接性(Connectivity)涉及到基于傳遞性的鏈接方法，以確定點(diǎn)是否位于特定的聚類中。例如，如果p->r->s->t->q，則p和q可以連接，其中a->b表示b在a的鄰域內(nèi)。

DBSCAN聚類完成后會(huì)產(chǎn)生三種類型的點(diǎn)：

• 核心點(diǎn)(Core)——該點(diǎn)表示至少有m個(gè)點(diǎn)在距離n的范圍內(nèi)。
• 邊界點(diǎn)(Border) ——該點(diǎn)表示在距離n處至少有一個(gè)核心。
• 噪聲點(diǎn)(Noise) ——它既不是核心點(diǎn)也不是邊界點(diǎn)。并且它在距離自身n的范圍內(nèi)有不到m個(gè)點(diǎn)。

DBSCAN聚類算法步驟

• 算法通過(guò)任意選取數(shù)據(jù)集中的一個(gè)點(diǎn)(直到所有的點(diǎn)都訪問(wèn)到)來(lái)運(yùn)行。
• 如果在該點(diǎn)的“ε”半徑范圍內(nèi)至少存在“minPoint”點(diǎn)，那么認(rèn)為所有這些點(diǎn)都屬于同一個(gè)聚類。
• 通過(guò)遞歸地重復(fù)對(duì)每個(gè)相鄰點(diǎn)的鄰域計(jì)算來(lái)擴(kuò)展聚類

參數(shù)估計(jì)

每個(gè)數(shù)據(jù)挖掘任務(wù)都存在參數(shù)問(wèn)題。每個(gè)參數(shù)都以特定的方式影響算法。DBSCAN需要參數(shù)ε和minPts。

• ε：可以使用k距離圖來(lái)選擇ε的值，表示到k=minPts-1最近鄰的距離，從最大值到最小值排序。當(dāng)此圖顯示“elbow”時(shí)，ε值較好：如果ε選擇得太小，則很大一部分?jǐn)?shù)據(jù)將無(wú)法聚類;如果ε值太高，聚類將合并，同時(shí)大多數(shù)對(duì)象將位于同一聚類中。一般來(lái)說(shuō)，較小的ε值是可取的，根據(jù)經(jīng)驗(yàn)，只有一小部分點(diǎn)應(yīng)在此距離內(nèi)。
• 距離函數(shù)：距離函數(shù)的選擇與ε的選擇密切相關(guān)，對(duì)結(jié)果有重要影響。通常，在選擇參數(shù)ε之前，必須首先確定數(shù)據(jù)集的合理相似性度量。沒(méi)有對(duì)此參數(shù)的估計(jì)，但需要為數(shù)據(jù)集適當(dāng)?shù)剡x擇距離函數(shù)。
• minPts：根據(jù)經(jīng)驗(yàn)，最小minPts可以從數(shù)據(jù)集中的維度數(shù)D導(dǎo)出，即minPts≥D+1。低值minPts=1是沒(méi)有意義的，因?yàn)榇藭r(shí)每個(gè)點(diǎn)本身就已經(jīng)是一個(gè)聚類了。當(dāng)minPts≤2時(shí)，結(jié)果將與采用單鏈路度量的層次聚類相同，且樹(shù)狀圖在高度ε處切割。因此，必須至少選擇3個(gè)minPts。

然而，對(duì)于有噪聲的數(shù)據(jù)集，較大的值通常更好，并將產(chǎn)生更顯著的聚類。根據(jù)經(jīng)驗(yàn)，可以使用minPts=2·dim，但對(duì)于非常大的數(shù)據(jù)、噪聲數(shù)據(jù)或包含許多重復(fù)項(xiàng)的數(shù)據(jù)，可能需要選擇更大的值。

用sklearn實(shí)現(xiàn)DBSCAN python

首先用DBSCAN對(duì)球形數(shù)據(jù)進(jìn)行聚類。

先生成750個(gè)帶有相應(yīng)標(biāo)簽的球形訓(xùn)練數(shù)據(jù)點(diǎn)。然后對(duì)訓(xùn)練數(shù)據(jù)的特征進(jìn)行標(biāo)準(zhǔn)化，最后應(yīng)用sklearn庫(kù)中的DBSCAN。

聚類球形數(shù)據(jù)中的DBSCAN

黑色數(shù)據(jù)點(diǎn)表示上述結(jié)果中的異常值。接下來(lái)，用DBSCAN對(duì)非球形數(shù)據(jù)進(jìn)行聚類。

import numpy as np 
           importmatplotlib.pyplot as plt 
           from sklearn import metrics 
           fromsklearn.datasets import make_circles 
           fromsklearn.preprocessing importStandardScaler 
           from sklearn.clusterimportDBSCAN 
           X, y =make_circles(n_samples=750, factor=0.3, noise=0.1) 
           X=StandardScaler().fit_transform(X) 
           y_pred=DBSCAN(eps=0.3, min_samples=10).fit_predict(X) 
           plt.scatter(X[:,0], X[:,1], c=y_pred) 
           print('Number ofclusters: {}'.format(len(set(y_pred[np.where(y_pred !=-1)])))) 
           print('Homogeneity:{}'.format(metrics.homogeneity_score(y, y_pred))) 
           print('Completeness:{}'.format(metrics.completeness_score(y, y_pred))) 
           print("V-measure:%0.3f"% metrics.v_measure_score(labels_true,labels)) 
           print("Adjusted RandIndex: %0.3f" 
                 % metrics.adjusted_rand_score(labels_true,labels)) 
           print("AdjustedMutual Information: %0.3f" 
                 % metrics.adjusted_mutual_info_score(labels_true,labels)) 
           print("SilhouetteCoefficient: %0.3f" 
                 % metrics.silhouette_score(X, labels)) 

聚類非球形數(shù)據(jù)中的DBSCAN

這絕對(duì)是完美的。如果與K均值進(jìn)行比較，會(huì)給出一個(gè)完全不正確的輸出，如：

K-均值聚類結(jié)果

DBSCAN聚類算法的復(fù)雜性

• 平均情況：與最佳/最壞情況相同，取決于數(shù)據(jù)和算法的實(shí)現(xiàn)。
• 最佳情況：如果使用索引系統(tǒng)來(lái)存儲(chǔ)數(shù)據(jù)集，使得鄰域查詢?cè)趯?duì)數(shù)時(shí)間內(nèi)執(zhí)行，可得到O(nlogn)的平均運(yùn)行時(shí)復(fù)雜度。
• 最壞情況：如果不使用索引結(jié)構(gòu)或?qū)ν嘶瘮?shù)據(jù)(例如，所有距離小于ε的點(diǎn))，最壞情況下的運(yùn)行時(shí)間復(fù)雜度仍為O(n²)。

基于密度的聚類算法可以學(xué)習(xí)任意形狀的聚類，而水平集樹(shù)算法可以在密度差異很大的數(shù)據(jù)集中學(xué)習(xí)聚類。

但需要指出的是，這些算法與參數(shù)聚類算法(如K均值)相比，調(diào)整起來(lái)有些困難。與K均值的聚類參數(shù)相比，DBSCAN或水平集樹(shù)的epsilon參數(shù)在推理時(shí)不那么直觀，因此為這些算法選擇較好的初始參數(shù)值更加困難。