目錄：

一、算法思路

二、算法實現

三、算法實現過程中遇到的問題

四、算法運行結果

?

一、算法思路

DBSCAN算法的核心是“延伸”。先找到一個未訪問的點p，若該點是核心點，則創建一個新的簇C，將其鄰域中的點放入該簇，并遍歷其鄰域中的點，若其鄰域中有點q為核心點，則將q的鄰域內的點也劃入簇C，直到C不再擴展。直到最后所有的點都標記為已訪問。

點p通過密度可達來擴大自己的“地盤”，實際上就是簇在“延伸”。

?

圖示網站：https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/ 可以看一下簇是如何延伸的。

二、算法實現

1、計算兩點之間的距離

            
              # 計算兩個點之間的歐式距離，參數為兩個元組
def dist(t1, t2):
    dis = math.sqrt((np.power((t1[0]-t2[0]),2) + np.power((t1[1]-t2[1]),2)))
    # print("兩點之間的距離為："+str(dis))
    return dis


            
          

2、讀取文件，加載數據集

            
              def loadDataSet(fileName, splitChar='\t'):
    dataSet = []
    with open(fileName) as fr:
        for line in fr.readlines():
            curline = line.strip().split(splitChar)
            fltline = list(map(float, curline))
            dataSet.append(fltline)
    return dataSet


            
          

?

3、DBSCAN算法實現

1、標記點是否被訪問：我設置了兩個列表，一個存放未訪問的點unvisited，一個存放已訪問的點visited。每次訪問一個點，unvisited列表remove該點，visited列表append該點，以此來實現點的標記改變。

2、C作為輸出結果，初始時是一個長度為所有點的個數的值全為-1的列表。之后修改點對應的索引的值來設置點屬于哪個簇。

            
               DBSCAN算法，參數為數據集，Eps為指定半徑參數，MinPts為制定鄰域密度閾值
def dbscan(Data, Eps, MinPts):
    num = len(Data)  # 點的個數
    # print("點的個數："+str(num))
    unvisited = [i for i in range(num)]  # 沒有訪問到的點的列表
    # print(unvisited)
    visited = []  # 已經訪問的點的列表
    C = [-1 for i in range(num)]
    # C為輸出結果，默認是一個長度為num的值全為-1的列表
    # 用k來標記不同的簇，k = -1表示噪聲點
    k = -1
    # 如果還有沒訪問的點
    while len(unvisited) > 0:
        # 隨機選擇一個unvisited對象
        p = random.choice(unvisited)
        unvisited.remove(p)
        visited.append(p)
        # N為p的epsilon鄰域中的對象的集合
        N = []
        for i in range(num):
            if (dist(Data[i], Data[p]) <= Eps):# and (i!=p):
                N.append(i)
        # 如果p的epsilon鄰域中的對象數大于指定閾值，說明p是一個核心對象
        if len(N) >= MinPts:
            k = k+1
            # print(k)
            C[p] = k
            # 對于p的epsilon鄰域中的每個對象pi
            for pi in N:
                if pi in unvisited:
                    unvisited.remove(pi)
                    visited.append(pi)
                    # 找到pi的鄰域中的核心對象，將這些對象放入N中
                    # M是位于pi的鄰域中的點的列表
                    M = []
                    for j in range(num):
                        if (dist(Data[j], Data[pi])<=Eps): #and (j!=pi):
                            M.append(j)
                    if len(M)>=MinPts:
                        for t in M:
                            if t not in N:
                                N.append(t)
                # 若pi不屬于任何簇，C[pi] == -1說明C中第pi個值沒有改動
                if C[pi] == -1:
                    C[pi] = k
        # 如果p的epsilon鄰域中的對象數小于指定閾值，說明p是一個噪聲點
        else:
            C[p] = -1

    return C
            
          

#

三、算法實現過程中遇到的問題

代碼思路非常簡單，讓我以為實現起來也很簡單。結果拖拖拉拉半個多月才終于將算法改好。

算法實現過程中遇到的問題其實是小問題，但是導致的結果非常嚴重。因為不起眼所以才難以察覺。

這是剛開始我運行算法得到的結果（Eps為10，MinPts為10）：

Eps為2，MinPts為10（我改了點的大小）：

可以看出圖中顏色特別多，實際上就是聚成的簇太多，可實際上目測應該只有七八個簇。這是為什么呢？

原來是變量k的重復使用問題。

前面我用k來標識不同的簇，后面（如下圖）我又將k變成了循環變量，注意M列表中都是整數，代表點在數據集中的索引，所以實際上是k在整數列表中遍歷，覆蓋掉了前面用來標識不同簇的k值，導致每次運行出來k取值特別多（如下下圖）。

?

四、運行結果

?

附數據集

鏈接：數據集788個點
提取碼：rv06
?

附完整代碼

            
              # encoding:utf-8
import matplotlib.pyplot as plt
import random
import numpy as np
import math
from sklearn import datasets

list_1 = []
list_2 = []
# 數據集一：隨機生成散點圖,參數為點的個數
# def scatter(num):
#     for i in range(num):
#         x = random.randint(0, 100)
#         list_1.append(x)
#         y = random.randint(0, 100)
#         list_2.append(y)
#     print(list_1)
#     print(list_2)
#     data = list(zip(list_1, list_2))
#     print(data)
#     #plt.scatter(list_1, list_2)
#     #plt.show()
#     return data
#scatter(50)

def loadDataSet(fileName, splitChar='\t'):
    dataSet = []
    with open(fileName) as fr:
        for line in fr.readlines():
            curline = line.strip().split(splitChar)
            fltline = list(map(float, curline))
            dataSet.append(fltline)
    return dataSet

# 計算兩個點之間的歐式距離，參數為兩個元組
def dist(t1, t2):
    dis = math.sqrt((np.power((t1[0]-t2[0]),2) + np.power((t1[1]-t2[1]),2)))
    # print("兩點之間的距離為："+str(dis))
    return dis

# dis = dist((1,1),(3,4))
# print(dis)


# DBSCAN算法，參數為數據集，Eps為指定半徑參數，MinPts為制定鄰域密度閾值
def dbscan(Data, Eps, MinPts):
    num = len(Data)  # 點的個數
    # print("點的個數："+str(num))
    unvisited = [i for i in range(num)]  # 沒有訪問到的點的列表
    # print(unvisited)
    visited = []  # 已經訪問的點的列表
    C = [-1 for i in range(num)]
    # C為輸出結果，默認是一個長度為num的值全為-1的列表
    # 用k來標記不同的簇，k = -1表示噪聲點
    k = -1
    # 如果還有沒訪問的點
    while len(unvisited) > 0:
        # 隨機選擇一個unvisited對象
        p = random.choice(unvisited)
        unvisited.remove(p)
        visited.append(p)
        # N為p的epsilon鄰域中的對象的集合
        N = []
        for i in range(num):
            if (dist(Data[i], Data[p]) <= Eps):# and (i!=p):
                N.append(i)
        # 如果p的epsilon鄰域中的對象數大于指定閾值，說明p是一個核心對象
        if len(N) >= MinPts:
            k = k+1
            # print(k)
            C[p] = k
            # 對于p的epsilon鄰域中的每個對象pi
            for pi in N:
                if pi in unvisited:
                    unvisited.remove(pi)
                    visited.append(pi)
                    # 找到pi的鄰域中的核心對象，將這些對象放入N中
                    # M是位于pi的鄰域中的點的列表
                    M = []
                    for j in range(num):
                        if (dist(Data[j], Data[pi])<=Eps): #and (j!=pi):
                            M.append(j)
                    if len(M)>=MinPts:
                        for t in M:
                            if t not in N:
                                N.append(t)
                # 若pi不屬于任何簇，C[pi] == -1說明C中第pi個值沒有改動
                if C[pi] == -1:
                    C[pi] = k
        # 如果p的epsilon鄰域中的對象數小于指定閾值，說明p是一個噪聲點
        else:
            C[p] = -1

    return C


# 數據集二：788個點
dataSet = loadDataSet('788points.txt', splitChar=',')
C = dbscan(dataSet, 2, 14)
print(C)
x = []
y = []
for data in dataSet:
    x.append(data[0])
    y.append(data[1])
plt.figure(figsize=(8, 6), dpi=80)
plt.scatter(x,y, c=C, marker='o')
plt.show()
# print(x)
# print(y)
            
          

?