机器学习算法1DBSCAN

1.DBSCAN算法的基本原理

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚类算法，是一种基于高密度连通区域的、基于密度的聚类算法，能够将具有足够高密度的区域划分为簇(Cluster)，并在具有噪声的数据中发现任意形状的簇。DBSCAN算法通过距离定义出一个密度函数，计算出每个样本附近的密度，从而根据每个样本附近的密度值来找出那些样本相对比较集中的区域，这些区域就是我们要找的簇。

其它聚类方法大都是基于对象之间的距离进行聚类，聚类结果是球状的簇。DBSCAN 算法利用簇的高密度连通性，寻找被低密度区域分离的高密度区域，可以发现任意形状的簇，其基本思想是:对于一个簇中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目。

DBSCAN算法中有两个重要参数：ε表示定义密度时的邻域半径，M表示定义核心点时的阈值

1.1基本概念

ε-邻域：以某个对象为中心、以ε为半径的空间；

核心点：某个点在其近邻ε区域中点的数量超过某一定义的数量（M）；

边界点：某个点在其近邻区域ε的点少于m个，但是该点是核心点的近邻；

噪声点：既不是核心点，也不是边界点

大量实验表明，m>4和m=4时，dbscn聚类没有显著的差别，但在m>4时却需要更多的计算，实际应用中，往往设置m=4进行排除。

直接密度可达：对于核心对象q和对象p，如果p在q的ϵ−邻域内，则称p是从q直接密度可达；（两点）

密度可达：如果存在一个对象链p1,p2...pn，使得p1=q,pn=p，并且对于在样本集中的pi，有pi+1是从pi关于ϵ和M直接密度可达的，则p是从q密度可达。（两点加多点）

密度相连：如果样本中存在一个对象q，使得对象p1和对象p2都是从q关于ϵ和M密度可达的，则对象p1,p2是密度相连的。（两点关于一点）

如上图所示，

m是核心对象，

对象q在m的领域内，就说对象q是从核心对象m直接密度可达的，

如果再有核心对象m是从核心对象p直接密度可达的，我们就说对象q是从核心对象p密度可达。

对象s，r是密度相连的。

2、算法主要步骤

随机选择点P

根据ε和m参数检索所有与p密度可达的点

如果p是核心点，形成新的聚类或者扩展已经存在的聚类

如果p是边界点。且没有点与p是密度可达的，则DBSCN算法访问数据库中的下一个点

重复上述过程处理数据库中的每一个点，直到数据库中的所有点都被处理。

参数D：输入数据集

参数ϵ：指定半径

MinPts：密度阈值

3、优缺点

DBSCAN算法不需要事先确定聚类的数目，优于K-Means

DBSCAN可用于任意形状的聚类

DBSCAN考虑了噪声的影响，消除了聚类中的异常点

DBSCAN仅仅需要两个参数，半径ϵ和MinPts，对数据中点的顺序不敏感。

缺点：效率很慢，

缺点：发现近邻采用欧氏距离，在处理高维数据时容易导致维度灾难。

在这里给大家提供一个国外的网站，我们可以可视化K-Means以及DBSCAN这两种算法的聚类过程。

https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/

4、 源程序代码

该程序在pycharm和python3环境下运行成功。

fromsklearnimportdatasets

importnumpyasnp

importrandom

importmatplotlib.pyplotasplt

importtime

# 定义函数用来寻找邻域里的所有相近的点

deffindNeighbor(j,X,eps):

N = []

forpinrange(X.shape[]):# 找到所有领域内对象

temp = np.sqrt(np.sum(np.square(X[j] - X[p])))# 欧氏距离

# 如果两个点之间的距离小于半径，这两个点为同一个蔟

if(temp

N.append(p)

returnN

# 定义dbscn聚类算法

# NeighborPts 某点j邻域内属于同一个蔟的所有对象

# Ner_NeighborPts： NeighborPts中每一个点再计算距离寻找其中每个点的邻域

# fil 已访问对象列表

# gama 未访问对象列表

defdbscan(X,eps,min_Pts):

k = -1

NeighborPts= []# array,某点领域内的对象

Ner_NeighborPts= []

fil = []# 初始时 已访问对象列表 为空

gama = [xforxinrange(len(X))]# 初始时 将所有点标记为 未访问

cluster = [-1foryinrange(len(X))]

whilelen(gama) >:# 有点

j = random.choice(gama)# j是随机选择全体数据中未标记的点

gama.remove(j)# 未访问列表中移除

fil.append(j)# 添加入访问列表

NeighborPts = findNeighbor(j,X,eps)

iflen(NeighborPts)

cluster[j] = -1# 标记为噪声点

else:# 不是噪声点,判断是不是边界点还是核心点，或是密度可达点

k = k +1

cluster[j] = k

foriinNeighborPts:# i是邻域内所有的点

ifinot infil:# 在邻域中，但是该点未被访问（NeighborPts已经）

gama.remove(i)# 未访问列表中移除

fil.append(i)# 添加入访问列表

Ner_NeighborPts = findNeighbor(i,X,eps)# 邻域中的点计算距离

iflen(Ner_NeighborPts) >= min_Pts:# 如果大于最小密度，这个点在核心点邻域内

forainNer_NeighborPts:# 遍历所有邻域中的点

ifanot inNeighborPts:# 如果不在NeighborPts这个邻域中，加入到NeighborPts。

NeighborPts.append(a)

if(cluster[i] == -1):# 如果是噪声点

cluster[i] = k

returncluster

# 自己做数据，X1, y1是圈型，X2, y2是圆形的

X1,y1 = datasets.make_circles(n_samples=5000,factor=.6,

noise=.05)

X2,y2 = datasets.make_blobs(n_samples=1000,n_features=2,centers=[[1.2,1.2]],cluster_std=[[.1]],

random_state=9)

# 将X1, y1和X2, y2连接在一起

X = np.concatenate((X1,X2))

eps =0.08

min_Pts =10

# 运行dbscn算法

C = dbscan(X,eps,min_Pts)

plt.figure(figsize=(12,9),dpi=80)

plt.scatter(X[:,],X[:,1],c=C)

plt.show()

程序运行结果如下：