DBSCAN 算法

DBSCAN的由来

DBSCAN它将簇定义为密度相连的点组成的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类

在k-means中 , 每个点有且只有一个簇 , 且必须属于一个簇 , 但是在DBSCAN中 , 点最多属于一个簇 , 不属于任何簇的点叫做噪声点

DBSCAN的簇是一个一个形成的 , 不是同时形成的

只要样本点的密度大于阈值，则将该样本添加到最近的簇中。

由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。

对象的ε-邻域（r-邻域)：给定对象在半径ε内的区域
核心点：对于给定的数目m，如果一个对象的ε-邻域至少包含m个对象，则称该对象为核心对象
直接密度可达：给定一个对象集合D，如果p是在q的ε-邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的
密度可达：如果存在一个对象链p 1，p 2， …，p n ，p 1 =q，p n =p，对p i ∈D，(1≤i ≤n)，p i+1 是从p i关于ε和m直接密度可达的，则对象p是从对象q关于ε和m密度可达的
密度相连：如果对象集合D中存在一个对象o，使得对象p和q是从o关于ε和m密度可达的，那么对象p和q是关于ε和m密度相连的
簇：一个基于密度的簇是最大的密度相连对象的集
噪声：不包含在任何簇中的对象称为噪声

输入: 包含n个对象的数据库

输出: 所有生成的簇 , 达到密度要求

过程:

随机遍历数据库中的一个点 , 算所有点到这个点的距离 , 如果小于等于, 则点属于ε-邻域的点 , ε-邻域的点的个数(就是密度)如果达到要求(大于等于m) , 这团点就是密集的,则核心点成立, 如果没有达到要求,则ε-邻域与核心点都不成立
将周边的点一个个根据这样的要求进行计算 , 找出所有从第一个核心点的密度可达的对象 , 形成一个簇 , 直到抽取的点是边缘点 , 跳出本次循环 , 寻找下一个点 ,
数据库的所有点都会被遍历一遍,不属于任何簇的点就是噪声点
如果有点处在两个簇的交集位置 , 那么哪个簇先包含它 , 它就属于哪个簇 , 但第二个簇在算个数时会算它
计算ε-邻域点的个数时,该范围内的核心点也要算进去,只是它不会再作为核心点

1.导入模块

from sklearn.cluster import DBSCAN

2.准备数据

feature = data[['house_lat' ,  'house_lng']]

3.调用DBSCAN类

clf = DBSCAN().fit(feature)

DBSCAN(eps=0.5 , min_samples=5 , metric='euclidean' , algorthm='auto' , leaf_size=30 , p=None , random_state=None)

clf.core_sample_indices_ # 核心点索引

clf.components_ # 核心点的值

clf.labels_ #每个样本所属的簇

clf.fit_predict # 预测

clf.get_params() # 获得算法参数

DBSCAN类的重要参数也分为两类，一类是DBSCAN算法本身的参数，一类是最近邻度量的参数

eps： DBSCAN算法参数，即我们的ϵ-邻域的距离阈值，和样本距离超过ϵ的样本点不在ϵ-邻域内。默认值是0.5
min_samples： DBSCAN算法参数，即样本点要成为核心对象所需要的ϵ-邻域的样本数阈值。默认值是5
metric：最近邻距离度量参数
algorithm：最近邻搜索算法参数，算法一共有三种，第一种是蛮力实现‘brute’，第二种是KD树实现‘kd_tree’，第三种是球树实现‘ball_tree’
leaf_size：最近邻搜索算法参数，为使用KD树或者球树时，停止建子树的叶子节点数量的阈值。这个值越小，则生成的KD树或者球树就越大 , 默认是30
p: 最近邻距离度量参数 , p=1为曼哈顿距离，p=2为欧式距离