目錄：
一、算法思路
二、算法實現
三、算法實現過程中遇到的問題
四、算法運行結果
?
一、算法思路
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)
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
