DBSCAN 解读
DBSCAN 全拼为:
A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.
该算法为基于密度聚类的抗噪聚类算法.
算法分为两大步骤
第一大步骤:
寻找核心点形成临时聚类簇
对应源码
neighbors_model = NearestNeighbors(radius=self.eps,algorithm=self.algorithm,leaf_size=self.leaf_size,metric=self.metric,metric_params=self.metric_params,p=self.p,n_jobs=self.n_jobs,
)neighbors_model.fit(X)
# This has worst case O(n^2) memory complexity
neighborhoods = neighbors_model.radius_neighbors(X, return_distance=False)
解读
扫描全部样本点，如果某个样本点eps半径范围内点数目>=min_samples，则将其纳入核心点列表，并将其密度直达的点形成对应的临时聚类簇.
第二大步骤:
合并临时聚类簇得到聚类簇
core_samples = np.asarray(n_neighbors >= self.min_samples, dtype=np.uint8)
dbscan_inner(core_samples, neighborhoods, labels)
其中 dbscan_inner 在 _dbscan_inner.pyx (.pyx 文件类似于 C 语言的 .c 源代码文件，.pyx 文件中有 Cython 模块的源代码 被编译成 .c 文件 后实现计算加速)
dbscan_inner 函数计算是DBSCAN 算法的核心
借助【栈】 对簇的合并 深度优先搜索从i开始,这与经典的连通计算算法非常相似
组件，区别在于将非核心点标记为是簇的一部分，但不要扩展其邻居。
while True:if labels[i] == -1:labels[i] = label_numif is_core[i]:neighb = neighborhoods[i]for i in range(neighb.shape[0]):v = neighb[i]if labels[v] == -1:push(stack, v)if stack.size() == 0:breaki = stack.back()stack.pop_back()
需要注意的问题:
- the parameter min_samples primarily controls how tolerant the algorithm is towards noise.the parameter eps is crucial to choose appropriately for the data set and distance function and usually cannot be left at the default value.
邻域半径eps和最少点数目min_samples。这两个算法参数控制了聚类的效果,不能用默认值.
2.the clusters to which non-core samples are assigned can differ depending on the data order. This would happen when a non-core sample has a distance lower than eps to two core samples in different clusters.
这是常被忽略的另一个问题.当以不同的顺序提供数据时,聚类的结果可能不相同!详见:https://github.com/irvingc/dbscan-on-spark/issues/19 边界点问题:(比Kmeans 严重) 某样本点到两个核心对象的距离都小于eps,但是核心对象不是密度直达的,又不属于同一个簇,此时应该如何确定?先进行聚类的类别会标记这个样本成为它的类别
3.其他
metric,metric_params=None,algorithm=“auto”,leaf_size=30,p=2,着几个参数决定了样本点之间的距离计算方式,默认为欧式距离完全遍历计算.sample_weight这个参数为对应到每个样本的权重,默认为1,该值越大则越能促进成为核心样本点,反之则能抑制成为核心样本点.n_jobs 是否并行化计算.
https://blog.csdn.net/qq_35405379/article/details/103755803
https://zhuanlan.zhihu.com/p/336501183