深圳市深圳市住房和建设局网站首页,大连市中心是哪个区,wordpress 换首页,下载网站的服务器文件一、概述 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法#xff0c;簇集的划定完全由样本的聚集程度决定。聚集程度不足以构成簇落的那些样本视为噪声点#xff0c;因此DBSCAN聚类的方式也可以用于异常点的检测。
二、算法…一、概述 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法簇集的划定完全由样本的聚集程度决定。聚集程度不足以构成簇落的那些样本视为噪声点因此DBSCAN聚类的方式也可以用于异常点的检测。
二、算法原理
1.基本原理 算法的关键在于样本的‘聚集程度’这个程度的刻画可以由聚集半径和最小聚集数两个参数来描述。如果一个样本聚集半径领域内的样本数达到了最小聚集数那么它所在区域就是密集的就可以围绕该样本生成簇落这样的样本被称为核心点。如果一个样本在某个核心点的聚集半径领域内但其本身又不是核心点则被称为边界点既不是核心点也不是边界点的样本即为噪声点。其中最小聚集数通常由经验指定一般是数据维数1或者数据维数的2倍。 通俗地讲核心点就是构成一个簇落的核心成员边界点就是构成一个簇落的非核心成员它们分布于簇落的边界区域噪声点是无法归属在任何一个簇集的游离的异常样本。如图所示。 对于聚成的簇集这里有三个相关的概念密度直达密度可达密度相连。
密度直达 对一个核心点p它的聚集半径领域内的有点q那么称p到q密度直达。密度直达不具有对称性。
密度可达 有核心点p1,p2,…,pn非核心点q如果pi到pi1i1,2,…,n-1是密度直达的pn到q是密度直达的那么称核心点pi(i1,2,…,n)到其他的点是密度可达的。密度可达不具有对称性。
密度相连 如果有核心点P到两个点A和B都密度可达那么称A和B密度相连。密度相连具有对称性。 简单地讲核心点到其半径邻域内的点是密度直达的核心点到其同簇集内的点是密度可达的同一个簇集里的成员间是密度相连的。 由定义易知密度直达一定密度可达密度可达一定密度相连。密度相连就是对聚成的一个簇集最直接的描述。
2.算法描述
输入 样本集D聚集半径r最小聚集数MinPts 输出 簇集C1C2…,Cn噪声集O. 根据样本聚集程度传播式地划定聚类簇并将不属于任何一个簇的样本划入噪声集合。
1随机搜寻一个核心点p S1.从样本集D中随机选择一个未归入任何集合的且未被标记的样本对象p S2.计算p的r邻域大小 ∣ N r ( p ) ∣ \left| N_r(p) \right| ∣Nr(p)∣ 若 ∣ N r ( p ) ∣ ≥ M i n P t s \left| N_r(p) \right|\geq MinPts ∣Nr(p)∣≥MinPts 则标记为核心点否则标记为非核心点并选择其他的点进行判别. S3.重复上面的步骤直至找到一个核心点若未找到将未归集的样本划入噪声集O. 2在核心点p处建立簇C将r邻域内所有的点加入簇C.
3对邻域内所有未被标记的点迭代式进行考察扩展簇集. 若一个邻域点q为核心点则将它领域内未归入集合的点加入簇C中. 4重复以上步骤直至所有样本划入了指定集合
5输出簇集C1C2…Cn和噪声集合O。
3.优缺点
优势 1.可以发现任意形状的簇适用于非凸数据集 2.可以进行异常检测 3.不需要指定簇数根据样本的密集程度适应性地聚集。
不足 1.当样本集密度不均匀不同簇中的平均密度相差较大时效果较差 2.聚集半径和最小聚集数两个参数需人工指定。
三、示例 假设二维空间中有下列样本坐标为
(1,2),(1,3),(3,1),(2,2),(9,8),(8,9),(9,9),(18,18) 由DBSCAN算法完成聚类操作。
过程演算 由经验指定参数聚集半径r2最小聚集数MinPts3。
1随机搜寻一个核心点若不存在返回噪声集合。 考察点(1,2)它到各点的距离分别为 在它的r邻域内包括了自身在内的共三个样本点达到了MinPts数因此(1,2)为核心点。
2在核心点(1,2)处建立簇C1原始簇成员为r邻域内样本(1,2)、(1,3)、(2,2)。
3对簇落C1成员迭代式进行考察扩展簇集。 先考察(1,3)它到各点的距离分别为 在它的r邻域内包括了自身在内的共三个样本点达到了MinPts数因此(1,3)为核心点它邻域内的样本均已在簇C1中无需进行操作。 再考察(2,2)它到各点的距离分别为 在它的r邻域内包括了自身在内的共四个样本点达到了MinPts数因此(2,2)为核心点将它领域内尚未归入任何一个簇落的点(3,1)加入簇C1。 再考察(3,1)它到各点的距离分别为 在它的r邻域内包括了自身在内的共两个样本点因此(3,1)是非核心点。 考察结束簇集C1扩展完毕。
4在其余未归簇的样本点中搜寻一个核心点若不存在返回噪声集合。 考察点(9,8)它到各点的距离分别为 在它的r邻域内包括了自身在内的共三个样本点达到了MinPts数因此(9,8)为核心点。
5在核心点(9,8)处建立簇C2原始簇成员为r邻域内样本(9,8)、(8,9)、(9,9)。
6对簇落C2成员迭代式进行考察扩展簇集。 先考察(8,9)它到各点的距离分别为 在它的r邻域内包括了自身在内的共三个样本点达到了MinPts数因此(8,9)为核心点它邻域内的样本均已在簇C2中无需进行操作。 再考察(9,9)它到各点的距离分别为 在它的r邻域内包括了自身在内的共三个样本点达到了MinPts数因此(9,9)为核心点。它邻域内的样本均已在簇C2中无需进行操作。 考察结束簇集C2扩展完毕。
7在其余未归簇的样本点中搜寻一个核心点若不存在返回噪声集合。 其余未归簇的样本点集合为{(18,18)}考察(18,18)它到各点的距离分别为 在它的r邻域内包括了自身在内的共一个样本点未达到MinPts数因此(18,18)为非核心点。其余未归簇的样本中不存在核心点因此归入噪声集O{(18,18)}。
8输出聚类结果 簇类C1{(1,2),(1,3),(3,1),(2,2)} 簇类C2{(9,8),(8,9),(9,9)} 噪声集O{(18,18)}
四、Python实现
示例的Python实现。 功能用python实现DBSCAN聚类算法。from sklearn.cluster import DBSCAN
import numpy as np
import matplotlib.pyplot as plt# 初始化数据
data np.array([(1,2),(1,3),(3,1),(2,2),(9,8),(8,9),(9,9),(18,18)])# 定义DBSCAN模型
dbscan DBSCAN(eps2,min_samples3)# 计算数据获取标签
labels dbscan.fit_predict(data)# 定义颜色列表
colors [b,r,c]
T [colors[i] for i in labels]# 输出簇类
print(\n 聚类结果 \n)
ue np.unique(labels)
for i in range(ue.size):CLS []for k in range(labels.size):if labels[k] ue[i]:CLS.append(tuple(data[k]))print(簇类{}:.format(ue[i]),CLS)# 结果可视化
plt.figure()
plt.scatter(data[:,0],data[:,1],cT,alpha0.5) # 绘制数据点
plt.show() 运行结果 End. 资源打包下载 https://download.csdn.net/download/Albert201605/88152784?spm1001.2014.3001.5503
