? ? ? ?聲明:代碼的運行環境為Python3。Python3與Python2在一些細節上會有所不同,希望廣大讀者注意。本博客以代碼為主,代碼中會有詳細的注釋。相關文章將會發布在我的個人博客專欄《Python從入門到深度學習》,歡迎大家關注~
? ? ? ?K-Means算法、K-Means++算法以及Mean Shift算法都是基于距離的聚類算法,一般此類聚類的聚類結果都是球狀的簇,但當聚類結果是非球狀的時候,基于距離聚類的聚類算法得到的聚類結果并不是那么的好,然而,基于密度的聚類算法可以完美的解決此類問題。DBSCAN聚類算法是一種典型的基于密度的算法。
一、基本概念
? ? ? ?在DBSCAN算法中,有兩個基本的鄰域參數,分別是
鄰域和MinPts。其中
鄰域表示的是在數據集D中與樣本點
的距離不大于
的樣本。MinPts表示的是在樣本點
的
鄰域內的最少樣本點數目,基于此,在DBSCAN算法中數據點分為三類:核心點、邊界點、噪音點。
二、DBSCAN算法原理
? ? ? ?在DBSCAN算法中,由核心對象出發,找到與該核心對象密度可達的所有樣本形成一個聚類簇。其流程大致如下:
? ? ? ?(1)根據給定的鄰域參數
和MinPts確定所有的核心對象;
? ? ? ?(2)對每一個核心對象,選擇一個未處理過的核心對象,找到由其密度可達的樣本生成聚類簇;
? ? ? ?(3)重復上述過程。
? ? ? ?下面我們使用Python語言實現DBSCAN算法:
def dbscan(data, eps, MinPts):
'''
DBSCAN算法
:param data: 聚類的數據集
:param eps: 半徑
:param MinPts: 半徑內最少的數據點的個數
:return: 返回每個樣本的類型、每個樣本所屬的類別
'''
m = np.shape(data)[0]
# 區分核心點1,邊界點0和噪音點-1
types = np.mat(np.zeros((1, m)))
sub_class = np.mat(np.zeros((1, m)))
# 用于判斷該點是否處理過,0表示未處理過
dealed = np.mat(np.zeros((m, 1)))
# 計算每個數據點之間的距離
distance = dist(data)
# 用于標記類別
number = 1
# 對每一個點進行處理
for i in range(m):
# 找到未處理的點
if dealed[i, 0] == 0:
# 找到第i個點到其他所有點的距離
I = distance[i,]
# 找到半徑eps內的所有點
index = find_epsilon(I, eps)
# 區分點的類型
# 邊界點
if len(index) > 1 and len(index) < MinPts + 1:
types[0, i] = 0
sub_class[0, i] = 0
# 噪音點
if len(index) == 1:
types[0, i] = -1
sub_class[0, i] = -1
dealed[i, 0] = 1
# 核心點
if len(index) >= MinPts + 1:
types[0, i] = 1
for x in index:
sub_class[0, x] = number
# 判斷核心點是否密度可達
while len(index) > 0:
dealed[index[0], 0] = 1
I = distance[index[0],]
tmp = index[0]
del index[0]
index_1 = find_epsilon(I, eps)
if len(index_1) > 1: # 處理非噪音點
for x1 in index_1:
sub_class[0, x1] = number
if len(index_1) >= MinPts + 1:
types[0, tmp] = 1
else:
types[0, tmp] = 0
for j in range(len(index_1)):
if dealed[index_1[j], 0] == 0:
dealed[index_1[j], 0] = 1
index.append(index_1[j])
sub_class[0, index_1[j]] = number
number += 1
# 最后處理所有未分類的點為噪音點
index_2 = ((sub_class == 0).nonzero())[1]
for x in index_2:
sub_class[0, x] = -1
types[0, x] = -1
return types, sub_class
? ? ? ?其中,dist()方法用于計算每個數據點之間的距離,find_epsilon()方法用于找出距離小于等于epsilon樣本的下標,這兩個方法的實現過程如下:
(1)dist()方法
def dist(data):
'''
計算每個數據點之間的距離
:param data: 訓練數據
:return: 返回計算結果
'''
m, n = np.shape(data)
distance = np.mat(np.zeros((m, m)))
for i in range(m):
for j in range(i, m):
tmp = 0
for k in range(n):
tmp += (data[i, k] - data[j, k]) * (data[i, k] - data[j, k])
distance[i, j] = np.sqrt(tmp)
distance[j, i] = distance[i, j]
return distance
(2)find_epsilon()方法
def find_epsilon(dist_i, eps):
'''
找出距離小于等于epsilon樣本下標
:param dist_i: 樣本i和其他樣本之間的距離
:param eps: 半徑
:return: 返回距離小于等于eps樣本下標
'''
index = []
n = np.shape(dist_i)[1]
for j in range(n):
if dist_i[0, j] <= eps:
index.append(j)
return index
? ? ? ?DBSCAN聚類算法的聚類結果是與
和MinPts有關系的,這里還需要定義一個
函數,當然也可以手動指定
的值:
def epsilon(data, MinPts):
'''
計算最佳半徑
:param data: 訓練數據
:param MinPts: 半徑內數據點的個數
:return:返回得到的最佳半徑
'''
m, n = np.shape(data)
xMax = np.max(data, 0)
xMin = np.min(data, 0)
# np.prod()默認情況下計算所有元素的乘積
eps = ((np.prod(xMax - xMin) * MinPts * math.gamma(0.5 * n + 1)) / (m * math.sqrt(math.pi ** n))) ** (1.0 / n)
return eps
三、DBSCAN算法舉例
1、數據集:數據集有兩個特征,如下所示:
2、加載數據集
? ? ? ?我們此處使用如下方法加載數據集,也可使用其他的方式進行加載,此處可以參考我的另外一篇文章《Python兩種方式加載文件內容》。加載文件內容代碼如下:
def load_data(file_path):
'''
加載數據
:param file_path: 文件路徑
:return: 以矩陣形式返回數據
'''
f = open(file_path)
data = []
for line in f.readlines():
data_tmp = []
lines = line.strip().split("\t")
for x in lines:
data_tmp.append(float(x.strip()))
data.append(data_tmp)
f.close()
return np.mat(data)
3、保存聚類結果
? ? ? ?得到聚類結果之后,我們使用如下方法對聚類結果進行保存:
def save_result(file_name, data):
'''
保存聚類結果
:param file_name: 保存的文件名
:param data: 需要保存的數據
:return:
'''
f = open(file_name, "w")
n = np.shape(data)[1]
tmp = []
for i in range(n):
tmp.append(str(data[0, i]))
f.write("\n".join(tmp))
f.close()
4、調用DBSCAN算法
if __name__ == "__main__":
MinPts = 5 # 定義半徑內的最少的數據點的個數
data = load_data("F://data.txt")
eps = epsilon(data, MinPts)
types, sub_class = dbscan(data, eps, MinPts)
save_result("types", types)
save_result("sub_class", sub_class)
5、得到的結果如下所示
? ? ? ? 你們在此過程中遇到了什么問題,歡迎留言,讓我看看你們都遇到了哪些問題。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
