DBSCAN基础到深入

DBSCAN 全称

它是一种非常推荐的无监督学习方法，用于开发模型和机器学习算法。它是一种聚类技术，用于区分低密度和高密度簇。它将数据点分成若干个组，以确保属于同一组的点具有相似的属性。1996 年，Xiaowei Xu、Jorg Sander、Martin Ester 和 Hans-Peter Kriegel 提出了该算法。

DBSCAN 的目的是处理具有快速区域查询的数据库。对于密度差异很大的数据集，它无法进行聚类。

特性

• 由于它可以识别数据集中任意形状的簇，因此它可以发现任意形状的簇。
• 它基于对噪声和簇的基本概念。
• 它以很强的鲁棒性检测数据集中的异常值。
• 它只需要两个点，并且完全不关心数据集的点排序。

好处

• 可以不指定数据集中数据簇的数量。
• 即使其他簇环绕着一个簇，它仍然可以找到任何形状的簇。
• 它可以轻松地找到数据集中的异常值。
• 它具有噪声容忍性，因为它对噪声不是很敏感。
• 在 K-Means 之后，它是第二受欢迎的聚类技术。

缺点

• regionQuery 函数的距离度量决定了结果的好坏。
• 它部分是确定性的，因为边界点可能根据它们被处理的顺序出现在任何簇中。
• 当计算最近邻的成本很高时，它可能会很昂贵。
• 在高维情况下，其执行可能会变慢。
• 对于局部密度的变化，适应性不足。

不同组中的数据点具有不同的属性，并且同一组中具有相似属性的数据点被一个称为聚类评估或简单聚类的无监督学习技术分隔开。它包含广泛的差分进化技术。

所有聚类技术的核心都是相同的：我们首先计算相似性，然后利用这些信息对数据点进行分组或批处理。

带噪声点的空间聚类（DBSCAN）

数据空间中的密集区域称为簇，它们被低密度区域分隔。这种“簇”和“噪声”的逻辑概念是 DBSCAN 算法的基础。

DBSCAN 的独特之处是什么？

通过 K-Means 和 PAM 聚类等划分技术以及层次聚类，可以找到凸形或球形簇。换句话说，它们的适用性仅限于紧凑且分离良好的簇。此外，数据中存在噪声和异常值也会对它们产生负面影响。

真实世界的数据可能存在以下异常：

• 簇可以有任何形状，如下面的插图所示。
• 数据中可能存在噪声。

上图显示了一个包含非凸形簇和离群值的数据集。对于这样的输入，K-Means 算法在找到这些随机形状的簇方面存在困难。

DBSCAN 算法所需的参数

EPS：它确定了数据点的邻域边界；也就是说，如果两个点的距离小于或等于‘eps’，则它们被认为是近邻。如果 EPS 值设置得太低，将有很大一部分数据被视为异常值。如果 EPS 选择得太高，簇将合并，大部分数据点将位于同一簇中。可以使用 k 距离图作为确定 EPS 值的依据。

MinPts 是指 EPS 半径内邻居（数据点）的最小数量。对于较大的数据集，必须选择更大的 MinPts 值。

通常，MinPts >= D+1，这是最小 MinPts，可以从数据集中维度 D 的数量获得。

在此技术中，我们使用三种不同类型的数据点。

核心点：如果一个点在 EPS 半径内包含超过 MinPts 个点，则该点被视为核心点。

边界点：边界点是靠近核心点但其 EPS 半径内的点数少于 MinPts 的点。

DBSCAN 算法步骤

• 找到 EPS 半径内的所有邻近点，并确定哪些是核心点或具有超过 MinPts 的邻居的点。
• 如果核心点尚未分配到任何簇，则为每个核心点创建一个新簇。
• 递归地找到所有与之密度连接的点，然后将它们与核心点一起分组到同一个簇中。
• 如果存在一个点 c，其邻居中有足够多的点，并且点 a 和点 b 都在 EPS 距离内，那么这两个点就被称为密度连接。这个过程涉及链式连接。
• 因此，可以推断，如果 b 是 c 的邻居，c 是 d 的邻居，d 是 e 的邻居，e 是 a 的邻居，那么 b 是 a 的邻居。
• 迭代地遍历数据集中剩余的未探索点。不属于任何簇的点被视为噪声点。

使用 Python 中的机器学习实现 DBSCAN 算法

在这里，我们将使用 Python 的 sklearn 模块来计算 DBSCAN。此外，还将使用 matplotlib.pyplot 包来可视化簇。

导入库

DBSCAN 算法的机器学习评估指标

我们将使用轮廓系数（Silhouette score）和调整兰德指数（Adjusted rand score）来评估聚类技术。轮廓系数的评分范围是 -1 到 1。如果一个数据点可能属于一个非常紧密的簇，并且与其他簇分离，那么它的评分将接近 1。值为 -1 是最差的。接近 0 的值表示簇重叠。

调整兰德指数的范围是 0 到 1。如果聚类恢复率显著高于 0.8，则认为其准确；如果显著高于 0.9，则认为其值得注意。恢复率低于 0.5 被认为是不充分的。

输出

Coefficient:0.13
Adjusted Rand Index: 0.31

黑点是异常值。我们可以通过调整 MinPts 和 eps 来改变簇的设置。

现在，需要提出的问题是：

在进行聚类分析时，DBSCAN 是否优于 K-Means？

使用相似的属性统计数据，K-Means 和 DBSCAN（带噪声点的空间聚类）是两种聚类算法。然而，它们基于不同的理论运行，并且适用于不同类型的数据。当数据的形状不是球形或类别的范围很大且事先未知时，我们选择使用 DBSCAN。

DBSCAN（带噪声点的空间聚类）是一种频繁用于数据挖掘和机器学习的聚类技术。它在查找空间数据中的随机形状簇方面尤其有用。

以下是 DBSCAN 功能的简要概述：

基于密度的方法

DBSCAN 的基础是数据点的密度。簇被定义为由稀疏区域分隔的密集数据点区域。

核心点、边界点和干扰

• 核心点：如果一个数据点周围至少有一定数量的其他数据点（MinPts）在设定的 EPS 距离内，则该数据点被视为核心点。
• 边界点：如果一个数据点在其自身的 EPS 邻域内拥有的 MinPts 少于指定值，但它位于某个核心点的 EPS 范围内，则该数据点被视为边界点。

算法步骤

• 随机选择一个尚未访问过的数据点。
• 如果选定的点是核心点，则创建一个新簇，并将所有与之密度可达的点分配到同一簇。
• 如果选定的点是边界点，则将其分配到现有簇中，前提是它位于该簇核心点的 eps 范围内。
• 以此类推，直到所有点都被访问。

结果

该算法生成一组簇，以及被指定为噪声的点。

设置参数

DBSCAN 的两个最重要参数是 eps，它衡量样本之间允许一个样本被归类为另一个样本的邻域内的最大距离，以及 MinPts，它衡量创建密集区域所需的最少记录点数。

结论

总之，强大的聚类算法 DBSCAN（带噪声点的空间聚类）在查找各种形状的地理数据簇方面尤其出色。由于其基于密度的方法，它能够找到基于数据点密度的簇，因此对簇大小和形状的变化具有抵抗力。DBSCAN 使用数据点的密度来定义簇。如果给定半径内有足够的邻居，它会找到核心点并在它们周围创建簇。簇由核心点、边界点和噪声点（不属于任何簇的点）组成。该算法使用密度标准来区分它们。

与其他一些聚类方法不同，DBSCAN 可以发现不同形状的簇，因此可以用于具有复杂结构的数据集。算法运行需要指定两个参数：min_samples（创建密集区域所需的最少数据点数）和 eps。要获得有意义的簇，正确的参数调整至关重要。通过将这些点分类到不同的组中，DBSCAN 可以有效地处理数据中的噪声，并对离群值具有弹性。可以使用各种库和编程语言来实现 DBSCAN。Scikit-learn 在 Python 中提供了简单的实现。

尽管 DBSCAN 是一种有效的算法，但它只能在某些情况下有效工作。在处理密度差异很大的数据集或簇的大小和形状变化很大的情况时，它的性能可能不佳。此外，选择正确的参数可能很困难，并且需要一些反复试验。DBSCAN 是实践中聚类任务的有用工具，尤其是在处理空间数据或具有复杂簇拓扑的数据集时。理解其指导原则、尝试调整参数并根据数据的具体情况调整其使用方式至关重要。