R 数据挖掘算法/聚类/基于密度的聚类

聚类技术在数据库中记录类别识别方面起着重要作用，因此它已成为数据挖掘研究的主要主题之一。空间聚类技术是聚类技术的一个子集，它应用于记录具有与某些空间语义内在相关的属性的数据库。前几章介绍的大多数传统聚类技术都适用于空间数据库。但是，当应用于空间上下文中的类别识别等任务时，传统技术可能无法取得良好的结果，例如，同一聚类中的元素可能没有足够的相似性，或者性能可能很差。

由空间聚类算法辅助的类别识别任务具有广泛的应用，因为在日益庞大的空间数据库中查找相关信息最近已成为一项高度需求的任务。示例包括来自卫星图像的地理数据、医学 X 射线图像处理或机器学习样本中的模式识别。

虽然已经提出了大量用于聚类空间相关数据的技术，但其中指定的大多数传统聚类算法都存在一些缺点。首先，基于 k 分区（如基于 k 均值的）的技术仅限于以凸形方式构建的聚类。许多数据库的聚类具有多种形状（图 1），因此传统的 k 分区算法将无法产生令人满意的结果。其次，大多数技术需要数据库的先验知识（领域知识）来确定最佳输入参数。例如，k 均值将预期聚类数量 k 作为输入，而 k 必须先验地已知才能应用于任何数据库。在许多现实生活中的数据库中，没有先验的领域知识，因此根据猜测选择参数值可能会导致不完整和不希望的结果。最后，大多数技术不可扩展，这意味着它们不能用于大型数据库，例如由数十万个元素组成的数据库。虽然大多数技术派生出属于多项式运行时间复杂度类的算法，但当它们应用于大型数据库（例如数百万或数十亿个元素）时，成本可能会变得过高。

上述限制可以通过使用一种新方法来克服，该方法基于密度来决定每个元素将位于哪个聚类中。下一节将介绍这种新方法 DBSCAN，它代表用于在具有噪声的大型空间数据库中发现聚类的基于密度的算法。

DBSCAN：基于密度的空间聚类应用于噪声

基于数据库密度属性构建聚类的想法源于人类自然聚类方法。通过查看图 1 中显示的二维数据库，人们几乎可以立即识别出三个聚类以及几个噪声点。聚类以及由此产生的类别很容易识别，因为它们相对于它们拥有的点具有更高的密度。另一方面，散布在数据库周围的单个点是离群值，这意味着由于它们位于浓度相对较低的区域，因此不属于任何聚类。

文件：具有三个聚类的二维数据库.PNG

图 1：具有三个非凸形聚类和几个离群值的二维空间数据库。

此外，正如将在以下部分中解释的那样，DBSCAN 算法最多需要两个参数：密度度量和聚类的最小大小。因此，与其他技术（即 k 均值）不同，不需要先验地估计聚类数量。最后，正如将在后面证明的那样，即使应用于大型数据库，DBSCAN 也是有效的。

重要概念

在描述 DBSCAN 算法之前，必须解释一些概念以使其完全理解。数据库的元素可以分为两种不同类型：边界点，位于聚类边缘的点，以及核心点，位于聚类内部区域。点 p 的邻域是所有距离度量小于预定值的点的集合，称为 Eps。因此，核心点的邻域大小通常大于边界点的邻域大小。如果点 p 属于 q 的邻域，并且 q 的邻域大小大于给定的常数 MinPts，则点 p 直接密度可达点 q。通过从先前的概念中规范地派生，可以定义一个通用的密度可达性：如果存在一个点链 p₁,..., p_n，其中 p₁ = q，p_n = p，并且 p_i+1 直接密度可达 p_i，则点 p 从 q 密度可达。然后将前述概念组合到聚类 D 的定义中

$\forall$ q,p : 如果 q $\in$ D 并且如果 q 从 p 密度可达，并且 p 的邻域大于 MinPts 阈值，则 p 属于 D。
$\forall$ q,p : 如果 q $\in$ D 并且 p $\in$ D，那么一定存在一个点 t 使得 q 和 p 直接可达 t。

根据上述定义，可能存在一些点不属于任何生成的聚类，这些点是离群值（噪声）。换句话说，聚类 D 由一组点组成，这些点满足一定程度的集中度，该集中度由 MinPts 和 Eps 约束设置。通过调整这些值，可以找到形状和密度不同的聚类。

换句话说，一个簇 D 是由一组点组成的，这些点满足一定的浓度，该浓度由 MinPts 和 Eps 约束设定。通过调整这些值，可以创建形状和密度不同的簇。

算法

DBSCAN 算法（算法 1）从随机选择数据库中的一个元素 P 开始。如果 P 不是核心点，即 P 的邻居少于 MinPts，则将其标记为噪声。否则，它将被标记为当前簇的一部分，并将调用 ExpandCluster（算法 2）函数。它的目的是找到所有从 P 密度可达的点，并且目前被标记为未分类或噪声。尽管是一个递归函数，但 ExpandCluster 在没有明确使用递归的情况下实现。递归行为是通过使用一个集合来实现的，该集合的大小随着新密度可达点的发现而变化。当所有点都被正确分类时，算法结束。

文件：DBSCAN 算法.png

最后，在识别完所有簇之后，人们可能会想知道一个边界点是否可以同时属于两个簇。对于这个问题，当前实现的算法会将模糊的点视为首先聚合它们的簇的一部分。

文件：DBSCAN ExpandCluster 算法.PNG

R 中的 DBSCAN

R 是一种用于统计计算的编程语言和软件环境。除了是广泛使用的统计分析工具外，R 还集成了多种数据挖掘技术。因此，它已成为用于发现数据库知识的简单任务的主要工具。R 的源代码在 GNU 通用公共许可证下免费提供，并且已移植到除 Unix 变体之外的多个平台，例如 Windows 和 MacOS。虽然 R 主要使用命令行界面，但有几个 GUI 可用，这提高了它的用户友好性。DBSCAN 技术在 R 的 fpc 包中可用，由 Christian Hennig 开发，该包实现了针对固定点簇的聚类任务。DBSCAN 实现提供了高可配置性，因为它允许选择多个参数和选项值。此外，fpc 的 DBSCAN 具有可视化界面，可以迭代地可视化聚类过程。

不幸的是，fpc 包相当慢，因为它主要是用 R 编写的。DBSCAN 的一个更快版本存在于 dbscan 包中。

安装

可以使用 R 命令行上的以下命令安装 fpc 包

install.packages("fpc", dependencies = TRUE)

上述命令将递归地下载和安装 fpc 依赖的所有包，以及 fpc 本身。

使用

要开始使用 fpc 包，必须调用以下命令

library('fpc')

DBSCAN 过程

fpc 包允许用户使用以下过程直接应用 dbscan 技术

dbscan(data, eps, MinPts, scale, method, seeds, showplot, countmode)

参数

DBSCAN 过程接受以下参数

data：将被聚类的數據。它可以是數據矩阵、data.frame、差异矩阵或 dist 对象。
eps：可达距离（前面讨论过）。
MinPts：可达点的最小数量（前面讨论过）。
scale：用于对数据进行缩放。
method：通过约束性能配置内存使用情况，有三个选项
- "raw"：将数据视为原始数据并避免计算距离矩阵（节省内存，但可能很慢）。
- "dist"：将数据视为距离矩阵（相对较快，但内存消耗大）。
- "hybrid"：也需要原始数据，但会计算部分距离矩阵（速度非常快，内存需求适中）。
seeds：关于在 dbscan 对象中包含 isseed 向量配置，可以是 TRUE 或 FALSE。
showplot：绘图配置
- 0：不绘图
- 1：每次迭代绘图
- 2：每次子迭代绘图
countmode：NULL 或点号向量以报告进度。

前三个参数是迄今为止最重要的参数：data 是用于聚类的输入数据；eps 和 MinPts 变量保留与之前相同的含义，即它们分别是元素之间的最小距离和形成簇所需的点数。showplot 参数与结果可视化相关。method 参数直接影响算法的效率，可用于在内存受限的环境中校准内存性能权衡。

例子

本节中的示例将说明 fpc 的 DBSCAN 在图 1 所示的数据库上的使用情况。它还将展示聚类机制作为一个迭代可视化过程。首先，必须创建要聚类的數據

x <- matrix(scan("file.dat",1926), nrow=1926, ncol=2, byrow=TRUE); # Read 1926 points on file "file.dat".
par(bg="grey40");                                                   # Set background to gray.
plot(x);                                                           # Plot original database.
d <- dbscan(x,10,showplot = 2);                                    # Calls DBSCAN routine (eps = 10 and MinPts is set to its default, which is 5).
d;                                                                 # Shows DBSCAN result.
# Notice that setting showplot to 2 will make dbscan show the result iteratively by its sub-iterations.

输出

DBSCAN 的输出显示了有关刚刚创建的簇的信息

dbscan Pts=1926 MinPts=5 eps=20
       0 1 2  3 4   5 6   7 8   9 10 11 12 13 14 15 16 17 18 19
seed   0 8 8 12 8 844 8 312 8 616  8 18  8  8 10 10  8  8 12  8
border 4 0 0  0 0   0 0   0 0   0  0  0  0  0  0  0  0  0  0  0
total  4 8 8 12 8 844 8 312 8 616  8 18  8  8 10 10  8  8 12  8

每个簇用一列表示，行显示它有多少个种子（核心）、边界和总点。请注意，散布在整个数据库中的微小簇实际上是由多个点组成的。因此，它们被认为是有效的簇，因为 MinPts 参数没有设置，并且它的默认值太低。

可视化

属于某个簇的点用不同颜色的三角形分隔。属于同一个簇的所有点都用相同颜色的三角形分隔。不属于任何簇的点保留与之前相同的颜色，并且如将要显示的那样，通常用黑色圆圈表示。此外，将 showplot 参数设置为 2 意味着在 DBSCAN 算法的每个子迭代中，例程都会在屏幕上显示部分簇。以下是其中的五个时刻

File:DBSCAN Iteration1.PNG File:DBSCAN Iteration2.PNG File:DBSCAN Iteration3.PNG

File:DBSCAN Iteration4.PNG File:DBSCAN Iteration5.PNG

第一张图像显示了在调用 DBSCAN 例程之前（命令 plot(x)）的点。第二张图像显示了聚类算法的开始，第一个主要簇正在数据库的顶部中心形成。第五张图像显示了算法结束时获得的 19 个簇。

案例研究：识别天体

以下部分将讨论由 DBSCAN 辅助并在空间数据库上应用的常见类识别任务：天文学中的天体识别。

场景

通过捕捉天体发射的辐射来识别天体是天文学中一项反复出现的工作。一个天体实体可能是电磁辐射的来源本身（例如，恒星），也可能是从其他来源反射的（例如，行星）。通常，一个实体会在不同的波长上发射辐射，这些辐射加起来可以帮助识别它的类别：它可能是一颗行星、任何类型或年龄的恒星，甚至是一个星系或其他以前未识别的奇异实体。从电磁频谱的每个范围内收集到的强度存储在单独的二维网格中（例如，一个用于紫外线，另一个用于伽马射线）。现代天文学研究小组能够收集和存储数千个大维网格，每个网格代表天空中的不同视角（或图像），并使用多达几 TB 的存储空间。

除了捕捉实体在特定频谱范围内发射的电磁强度外，传感器还可能捕捉到传感器产生的噪声，以及来自大气和太空本身的漫射发射。传统上，消除漫射发射和部分噪声的方法是通过已知阈值约束相关强度。例如，只有当强度超过 5 $\rho$ rms 时才会被认为是相关的。一个更大的问题是，电磁波在不同的频谱范围内穿过介质时会产生不同的干涉。这种现象被称为瑞利散射，最终会导致波在被传感器捕捉时偏转。因此，当考虑从空间同一区域但来自不同频谱范围的多个图像时，必须完成以下步骤才能正确识别天体。

方法和执行

例如，考虑图 2，它显示了从星系中心拍摄的图像。该图像包含一个天体图像上的噪声病理例子。以下是提取该图像上的天体对象的步骤。

步骤 1：预处理

首先，必须应用一个预处理步骤来去除噪声和漫射发射。如前所述，这可以通过使用阈值来实现。此步骤在图 3 中显示，而原始图像可以在图 2 中查看，它代表了描绘星系中心的原始图像。阈值设置为 50，这意味着只有强度小于 50（因此更暗）的像素才被考虑。

步骤 2：DBSCAN 聚类

其次，DBSCAN 算法可以应用于单个像素，将电磁频谱每个通道的图像上的完整发射区域链接在一起。这是通过将 eps 参数设置为某个值来完成的，该值将定义源被认为所需的最小面积。eps 参数将定义以像素为单位的距离度量。每个生成的簇将定义一个天体实体。图 4 显示了此步骤的结果，其中 eps 和 MinPts 参数设置为 5。

x <- matrix(scan("file.dat",1214), nrow=1214, ncol=2, byrow=TRUE);
dbscan(x,5,showplot = 2);

结果

dbscan Pts=1214 MinPts=5 eps=5
         0  1  2  3  4 5 6  7 8  9 10 11 12 13 14 15 16
seed     0 28 26 26 26 6 6 18 2 10 18  8 16 16  8 28 20
border 226  0  0  0  0 0 0  0 4  0  0  0  0  0  0  0  0
total  226 28 26 26 26 6 6 18 6 10 18  8 16 16  8 28 20
        17 18 19 20 21 22 23 24 25 26 27 28 29  30 31 32
seed    14 14  8 18  6  6  6 14  6  6  6 14  8 112  6 18
border   0  0  0  0  0  0  0  0  0  0  0  0  0   0  0  0
total   14 14  8 18  6  6  6 14  6  6  6 14  8 112  6 18
        33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
seed     6 20 20 20 16 10  6  6  8 14  8 10 14 10  6 36
border   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  2
total    6 20 20 20 16 10  6  6  8 14  8 10 14 10  6 38
       49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
seed   24  6  6 14  6 24 18  6 16  6 14 28 26 26 10 10  8
border  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
total  24  6  6 14  6 24 18  6 16  6 14 28 26 26 10 10  8

步骤 3：多光谱相关

识别完所有簇后，可以应用多光谱相关过程来考虑来自每个电磁波长的结果（生成的簇）。这里不会详细说明，但一种常见的方法是只考虑与电磁频谱的其他通道上的某些阈值足够接近的簇，这些簇有一个或多个对应物。

分析

图 4 显示了 DBSCAN 算法在 MinPts 和 eps 设置为 5 后执行聚类后的结果。从结果来看，我们可以看到许多孤立点没有被聚类，因为 MinPts 参数通过元素的最小值限制了簇的大小。此限制将删除被认为是不相关的发射源的太小的簇，因此被归类为噪声。通过限制 MinPts 参数，强度较弱的天体（例如，它们可能太远或没有发出强辐射）将从结果中排除。这通常是可取的，但当必须分析由较小区域定义的发射源时，可能会成为问题。因此，必须仔细选择 MinPts 值，因为它可能会极大地改变结果。

尽管如此，还是发现了 64 个簇和 224 个离群值。大多数簇没有大量的点，有一些例外，例如位于数据库中心的巨大簇，它代表着星系核心，这是一个强发射区域。eps 参数起着重要的作用，因为它将定义代表相同发射源的像素的最小半径。设置为 5 意味着欧几里得距离大于 5 的点不属于同一个发射源。虽然 5 对 eps 参数来说相对较大，但一些簇（如 (300,0) 上的簇）没有聚类在一起。这是因为尽管彼此接近，但根据 eps 值，它们不代表同一个天体。因此，设置 eps 的作用类似于 MinPts，因为它将根据距离度量来定义噪声对象，与 MinPts 的计数度量相同。

结论

随着天文学和天体物理学成为研究的突出领域，自动识别天体实体类别的需求变得越来越重要。随着技术的发展，以及越来越多的数据样本需要分析，对这项任务的需求不断增长。在没有计算辅助的情况下，这项任务是不可能的，而 DBSCAN 技术的出现让这项任务变得更加容易，它允许分析更大的样本，同时获得更精确的结果。

参考资料

Martin Ester, Hans-Peter Kriegel, Joerg Sander, Xiaowei Xu (1996)。用于在大型空间数据库中发现带有噪声的簇的基于密度的算法。慕尼黑大学计算机科学研究所。第二届知识发现与数据挖掘国际会议（KDD-96）论文集。
CRAN 上的 FPC 包：https://cran.r-project.org.cn/web/packages/fpc/index.html
FPC 中实现的 DBSCAN 算法手册位于 http://bm2.genes.nig.ac.jp/RGM2/R_current/library/fpc/man/dbscan.html
Jörg Sander, Martin Ester, Hans-Peter Kriegel, Xiaowei Xu (1998)。空间数据库中的基于密度的聚类：GDBSCAN 算法及其应用