代碼實(shí)現(xiàn)密度聚類(lèi)DBSCAN

一提到密度聚類(lèi)，腦海中立馬就能呈現(xiàn)出一個(gè)聚類(lèi)結(jié)果圖，不自然的就感覺(jué)非常的簡(jiǎn)單，不就是基于密度的聚類(lèi)嘛，原理不用看也懂了，但是真的實(shí)現(xiàn)起來(lái)，仿佛又不知道從哪里開(kāi)始下手。這時(shí)候再仔細(xì)回想一下腦海中的密度聚類(lèi)結(jié)果圖，好像和K-means聚類(lèi)的結(jié)果圖是一樣的，那真實(shí)的密度聚類(lèi)是什么樣子的呢？看了西瓜書(shū)的偽代碼后還是沒(méi)法實(shí)現(xiàn)？今天小編就帶大家解決一下密度聚類(lèi)的難點(diǎn)。

實(shí)現(xiàn)一個(gè)神經(jīng)網(wǎng)絡(luò)，一定一定要先明白這個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)，**輸入是什么？輸出是什么？網(wǎng)絡(luò)的層級(jí)結(jié)構(gòu)是什么？權(quán)值是什么？每個(gè)節(jié)點(diǎn)代表的是什么？網(wǎng)絡(luò)的工作流程是什么？**

    對(duì)于密度聚類(lèi)，有兩個(gè)關(guān)鍵的要素，一個(gè)是密度的最小值，另一個(gè)是兩個(gè)樣本之間的最大距離。規(guī)定了密度最小值就規(guī)定了核心樣本鄰域包含數(shù)據(jù)的最小值，規(guī)定兩個(gè)樣本之間的最大距離就規(guī)定了兩個(gè)樣本相聚多遠(yuǎn)才算是一類(lèi)。而且，這兩個(gè)值都是需要不斷測(cè)試之后才選取的，并不是一次就那么容易定下來(lái)的。另一個(gè)需要了解的就是，密度聚類(lèi)中有 **核心對(duì)象、密度直達(dá)、密度可達(dá)、和密度相連** ，這幾個(gè)概念。

    核心對(duì)象就是指的一個(gè)類(lèi)的核心，滿(mǎn)足兩個(gè)條密度聚類(lèi)的關(guān)鍵要素，初始的核心對(duì)象有很多，但是經(jīng)過(guò)不斷迭代整合后，核心對(duì)象越來(lái)越少，到最后一個(gè)類(lèi)形成后，核心對(duì)象就是一個(gè)抽象的概念，并不能明確的指出這個(gè)類(lèi)的核心對(duì)象是哪一個(gè)，但一定是初始核心對(duì)象中的一個(gè)。初始的核心對(duì)象的鄰域中，一定包含多個(gè)核心對(duì)象。

    用下圖來(lái)區(qū)分密度直達(dá)，密度可達(dá)和密度相連，假設(shè)X1為核心對(duì)象，那么X1和X2密度直達(dá)，X1和X3是密度可達(dá)，X3和X4是密度相連。密度相連就是兩個(gè)相聚比較遠(yuǎn)的邊緣節(jié)點(diǎn)了，密度直達(dá)和密度可達(dá)距離都比較近。

我們先理清一下密度聚類(lèi)的過(guò)程：

1. 首先要找到核心對(duì)象，即滿(mǎn)足周?chē)鷶?shù)據(jù)距離小于密度最小值的數(shù)據(jù)數(shù)量大于密度最小值，并且記錄下核心對(duì)象的鄰居節(jié)點(diǎn)。
2. 隨機(jī)選取一個(gè)核心對(duì)象，找到對(duì)應(yīng)的鄰居節(jié)點(diǎn)，即密度直達(dá)的節(jié)點(diǎn)，查看鄰居節(jié)點(diǎn)中包含的核心對(duì)象，將這幾個(gè)節(jié)點(diǎn)記錄下來(lái)，并在核心對(duì)象列表中刪除包含的核心對(duì)象，然后依次遍歷這幾個(gè)核心對(duì)象和它們的鄰居，按照相同的方法，記錄下的就是密度可達(dá)的節(jié)點(diǎn)。在遍歷開(kāi)始時(shí)，添加一個(gè)判斷條件，判斷這個(gè)節(jié)點(diǎn)是不是滿(mǎn)足核心節(jié)點(diǎn)的條件，如果不滿(mǎn)足，那么就不再查找它的鄰域，這些節(jié)點(diǎn)就是密度相連節(jié)點(diǎn)，也就是這一個(gè)類(lèi)的邊緣節(jié)點(diǎn)。

下面就是整個(gè)密度聚類(lèi)的代碼：

#密度聚類(lèi)
import numpy as np
import random
import time
import copy
np.set_printoptions(suppress=True)
def euclidean_distance(x, w):  # 歐式距離公式√∑（xi﹣wi）2
    return round(np.linalg.norm(np.subtract(x, w), axis=-1),8)


def find_neighbor(j, x, eps):
    N = list()
    for i in range(x.shape[0]):
        temp = euclidean_distance(X[i],X[j])  # 計(jì)算歐式距離
        print(str(j)+"到",str(i)+"的距離",'%.8f' % temp)
        if temp <= eps:
            N.append(i)
    return set(N)




def DBSCAN(X, eps, min_Pts):
    k = -1
    neighbor_list = []  # 用來(lái)保存每個(gè)數(shù)據(jù)的鄰域
    omega_list = []  # 核心對(duì)象集合
    gama = set([x for x in range(len(X))])  # 初始時(shí)將所有點(diǎn)標(biāo)記為未訪(fǎng)問(wèn)
    cluster = [-1 for _ in range(len(X))]  # 聚類(lèi)
    for i in range(len(X)):
        neighbor_list.append(find_neighbor(i, X, eps))
        if len(neighbor_list[-1]) + int(count_matrix[i]) >= min_Pts:    #如果權(quán)值對(duì)應(yīng)位置的數(shù)據(jù)樣本數(shù)量和相似權(quán)值的數(shù)量之和大于一定的數(shù)
            omega_list.append(i)  # 將樣本加入核心對(duì)象集合
    omega_list = set(omega_list)  # 轉(zhuǎn)化為集合便于操作
    while len(omega_list) > 0:
        gama_old = copy.deepcopy(gama)  #上一狀態(tài)未訪(fǎng)問(wèn)的節(jié)點(diǎn)
        j = random.choice(list(omega_list))  # 隨機(jī)選取一個(gè)核心對(duì)象
        k = k + 1  #第幾個(gè)類(lèi)別
        Q = list()
        Q.append(j)  #選出來(lái)的核心對(duì)象
        gama.remove(j)  #標(biāo)記為訪(fǎng)問(wèn)過(guò)
        while len(Q) > 0:#初始Q只有一個(gè)，但是后面會(huì)擴(kuò)充
            q = Q[0]
            Q.remove(q)  #把遍歷完的節(jié)點(diǎn)刪除
            #正是下面這一個(gè)if決定了密度聚類(lèi)的邊緣，不滿(mǎn)足if語(yǔ)句的就是密度相連，滿(mǎn)足就是密度直達(dá)或者密度可達(dá)
            if len(neighbor_list[q]) >= min_Pts:#驗(yàn)證是不是核心對(duì)象，找出密度直達(dá)
                delta = neighbor_list[q] & gama #set的交集，鄰域中包含的未訪(fǎng)問(wèn)過(guò)的數(shù)據(jù)
                deltalist = list(delta)
                for i in range(len(delta)):
                    Q.append(deltalist[i])#將沒(méi)訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)添加到隊(duì)列
                    gama = gama - delta #節(jié)點(diǎn)標(biāo)記為訪(fǎng)問(wèn)
        Ck = gama_old - gama  #記錄這一類(lèi)中的節(jié)點(diǎn)
        Cklist = list(Ck)  
        for i in range(len(Ck)):
            cluster[Cklist[i]] = k  #標(biāo)記這一類(lèi)的數(shù)據(jù)
        omega_list = omega_list - Ck #刪除核心對(duì)象
    return cluster


加載數(shù)據(jù)
X = np.load("文件位置")
X = X.reshape((-1,向量維度)) #修改維度


eps = 0.0000002    #兩個(gè)樣本之間的最大距離
min_Pts = 20   #樣本的最小值
C = DBSCAN(X, eps, min_Pts)
C = np.array(C)
np.save("classify.npy",C)
print("C",C.reshape([X原來(lái)的維度]))

注意一點(diǎn)，密度聚類(lèi)的輸入數(shù)據(jù)，不管是多少維，用這個(gè)代碼的話(huà)都要轉(zhuǎn)換成一維數(shù)據(jù)再進(jìn)行密度聚類(lèi)。舉個(gè)例子，二維數(shù)據(jù)row行,loc列，那么數(shù)據(jù)reshape成一維數(shù)據(jù)后，當(dāng)前位置 i 對(duì)應(yīng)的位置就是[（row*loc）+i]。如果有不懂或者有任何問(wèn)題，歡迎留言討論!