DBSCAN算法

一 分类

• 基于分层的聚类：自底向上，或者自顶向下
• 基于划分聚类，如k-Means聚类
• 基于密度的聚类：不是基于距离而是基于密度的，优点是可以克服基于距离算法只能发现‘类圆形’的聚类的缺点，DBSCAN算法
• 基于网格的聚类：将数据空间划分成网格，处理时以单个单元为对象，处理速度快
• 基于模型的聚类：统计的方案和神经网络的方案

二 数据规范化

• 按小数定标规范化：直接简单，不能消除属性间权值差异
• 最小-最大值规范化：可以消除权值差异，对离群点比较敏感
• z-score规范化：基于属性值得均值和方差进行规范化，对离群点规范化比较好，但是时间复杂度较高

三 DBScan

1 思想是衡量一个点的e领域内的邻居点数衡量该点所在的空间密度，不需要知道cluster的个数。

2 重要的参数：Eps和MinPts

个人总结：

• Eps定义密度时的领域半径
• 定义核心点时的阈值

• 基于密度聚类的算法目标是寻找低密度区域分离高密度区域，基于距离的聚类的结果是一个球形的族

• DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。
• 即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻

spark DBSCAN实践

默认情况下，KDP分区器尝试通过将数据沿着具有最大方差的轴进行分裂，并通过假设中值接近平均值来近似中间值来将数据拆分成几乎相同大小的集合（在+/- 0.9标准偏差内）。 在后续分区上重复此过程，直到获得所需数量的分区（max_partitions），并且存储边界框的相应字典（BoundingBox对象包含指定分割后每个分区的上限和下限的向量）。

然后将这些边界框扩展为DBSCAN半径（eps）的两倍，并用于创建一组邻域，每个邻域包含相应边界框内的点和该边界框的标签。 请注意，此扩展方法仅适用于度量标准为欧几里得，曼哈顿或类似度量标准，因为其他度量标准可以找到这些方框外的eps中的点。 然后将这些邻域合并在一起（导致在放大的边界框的重叠内重复点），并且使用邻域ID对产生的RDD进行重新分区。

在每个分区内，使用sklearn DBSCAN算法执行DBSCAN。 这些点然后用分区ID，集群ID以及该点是否是sklearn DBSCAN找到的核心点进行标记并发送给RDD。

这些带标签的点按其索引分组，并将其集群的ID进行合并，而且也创建分区级别集群ID与全局ID之间的映射。DBSCAN是一种贪婪算法，因此可以将非核心点分配给任何可以访问它们的群集。 因此如果一个非核心点可以从多个集群到达，则可以将其分配给这些集群的任意一个。 必须忽略此类标签，否则在组合群集标识时，群集可能会不当地合并。

最后，标记的点将映射到其全局群集ID上。 对于具有多个标签的点，只使用第一个标签。 对于核心点，标签的选择是无关紧要的，但非核心点将随机分配到一个集群。

参考文献：https://blog.csdn.net/itplus/article/details/10087581

https://www.cnblogs.com/pinard/p/6208966.html