python實(shí)現(xiàn)dbscan

原理

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一個比較有代表性的基于密度的聚類算法。它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。

DBSCAN中的幾個定義：

1. Ε鄰域：給定對象半徑為Ε內(nèi)的區(qū)域稱為該對象的Ε鄰域；
2. 核心對象：如果給定對象Ε鄰域內(nèi)的樣本點(diǎn)數(shù)大于等于MinPts，則稱該對象為核心對象；

DBSCAN 算法步驟

1. 初始化：
   從數(shù)據(jù)集中任意選擇一個點(diǎn) p，判斷它是否為核心點(diǎn)（即 ε 鄰域內(nèi)是否包含至少 minPts 個點(diǎn)）。
2. 擴(kuò)展簇：
   如果 p 是核心點(diǎn)，則開始一個新簇，將 p 及其鄰域中的點(diǎn)加入簇中，并不斷對新的核心點(diǎn)的鄰域進(jìn)行擴(kuò)展。
3. 處理噪聲點(diǎn)：
   如果一個點(diǎn)既不在任何簇中，也不滿足成為核心點(diǎn)的條件，則將其標(biāo)記為噪聲點(diǎn)。
4. 重復(fù)處理：
   繼續(xù)檢查所有未訪問的點(diǎn)，直到所有點(diǎn)都被訪問為止。

python實(shí)現(xiàn)

從大神哪里復(fù)制過來的代碼
https://github.com/lansinuote/Machine-Learning-In-Numpy/blob/master/%E6%97%A0%E7%9B%91%E7%9D%A3%E7%AF%87/5.DBSCAN/1.DBSCAN.ipynb

from sklearn.datasets import make_moons
from matplotlib import pyplot as pltimport numpy as np#加載數(shù)據(jù)
x, y = make_moons(n_samples=300, noise=0.05, random_state=42)
print(type(x))print(x)
x[0,0] = 2
x[0,1] = 2def my_dbscan(x, eps, minpts):#被訪問過的放這里visited = []#被分組過的放這里grouped = []#分組結(jié)果groups = []#求一個點(diǎn)周圍的鄰居def get_neighbors(xi):diff = x - xidiff = diff**2diff = diff.sum(axis=1)diff = diff**0.5#這里的eps是超參數(shù)，是畫圓的半徑index = diff <= epsreturn np.where(index)[0]#獲取一個沒有訪問過的x索引def get_unvisited_idx():for i in range(len(x)):if i not in visited:return ireturn None#從一個中心點(diǎn)開始擴(kuò)散成一個組def build_group(i, group):#如果一個點(diǎn)已經(jīng)被訪問過，則不進(jìn)行任何計算if i in visited:return#標(biāo)記這個點(diǎn)已經(jīng)被訪問過了visited.append(i)#獲取這個點(diǎn)所有的鄰居neighbors = get_neighbors(x[i])#如果鄰居數(shù)小于minpts，說明不是中心點(diǎn)，不進(jìn)行任何計算if len(neighbors) < minpts:return#如果是中心點(diǎn)，把它加入到組中if i not in grouped:group.append(i)grouped.append(i)#遍歷中心點(diǎn)的所有鄰居，如果在它的鄰居中也有中心點(diǎn)，則擴(kuò)散for j in neighbors:#如果鄰居還沒有被分過組，則歸入中心點(diǎn)的組if j not in grouped:group.append(j)grouped.append(j)build_group(j, group)#遍歷直到所有點(diǎn)被訪問while True:i = get_unvisited_idx()if i == None:break#每次重新開始擴(kuò)散，是一個新的組group = []build_group(i, group)if group:groups.append(group)#結(jié)果畫圖predict = -1 * np.ones(len(x)) # 沒有分簇的都是-1分類for i in range(len(groups)):predict[groups[i]] = ireturn predictpredict = my_dbscan(x, 0.25, 5)print(predict)
plt.scatter(x[:, 0], x[:, 1], c=predict)
plt.show()