分布式和并行数据库 （2019） 37：73–99 https://doi.org/10.1007/s10619-018-7253-1
MDCUT：一种多密度聚类算法，可自动检测噪声数据中的密度变化
Soumaya Lauhichi ·玛丽亚姆·扎拉 ·哈宁·本-阿卜杜拉
网络出版日期： 2018-10-16 © Springer Science+Business Media， LLC， part of Springer Nature 2018
抽象
尽管在许多应用中都采用了基于密度的聚类算法，但在处理具有不同密度、聚类和/或相邻聚类的数据时，它们的性能效率低下。密度较低的聚类可以归类为异常值，而具有不同密度的相邻和混合聚类可以被聚合。为了处理这种低效率问题，MDCUT 算法 （Multiple Density ClUsTering） （Louhichi et al. in Pattern Recogn Lett 93：48–57， 2017） 检测多个局部密度参数以处理数据中的密度变化。MDCUT 通过数学分析插值的 k 最近邻函数来提取密度局部水平。为每个密度级别提供聚类子例程，以形成该级别的聚类。与众所周知的基于密度的聚类算法相比，MDCUT在人工数据集上取得了良好的结果。MDCUT 的主要缺点是它对所用插值技术的参数 p 和最近邻数的参数 k 敏感。在本文中，我们提出了MDCUT算法的新扩展，以自动检测值对（k，ε）来表征数据中的密度水平，其中k和ε分别代表邻居的数量和半径阈值代表第i个密度水平。我们研究了 MDCUTalgo- 的性能。
B. Soumaya Lauhichi Lauhici.Soumaya@জিএমএআইএল.com
玛丽姆·格扎拉（Mariem Gzara mariem.gzara@gmail.com
哈内·本-阿卜杜拉 hbenabdallah@hct.ac.ae
1
MIRACL：多媒体信息系统和高级计算实验室，BP 1030，Sfax 3018，突尼斯
2
莫纳斯提尔大学计算机科学与数学高等学院， Avenue de la Korniche， B.P. 223， Monastir 5000， 突尼斯
3
高等理工学院，DBC，迪拜，阿拉伯联合酋长国
123
74
分布式和并行数据库 （2019） 37：73–99
通过比较基于参考密度的聚类算法，对已知数据集进行 RITHM。此扩展改进了以前的分类结果。
关键词 clustering ·MDCUT切割 ·任意形状的簇 ·样条插值 ·密度变化
1 引言
聚类分析已广泛应用于许多科学领域，如社会科学、生物学、统计学、模式识别、信息检索、机器学习和数据挖掘。例如，聚类分析已被用于对相关文档进行分组以供浏览，查找具有相似功能的基因和蛋白质，并提供地震易发位置的分组。此外，聚类分析已被用于各种应用中的预处理步骤，例如数据压缩和有效查找最近的相邻点。尽管如此，现有的聚类算法（例如[2,3]）仍然面临着数据大小增加和不均匀分布带来的一些挑战。事实上，数据聚类仍然是一项具有挑战性的任务，由于聚类的形状不规则、大小不同、密度不同以及分离不明确而变得复杂。
在应对这些挑战的有前途的方法中，一些研究人员研究了基于密度的聚类（例如，[4]）。他们能够找到任意形状的星团并处理噪声，而无需事先了解星团的数量。总体而言，集群被认为是由低密度区域分隔的高密度区域。该假设使得表征具有任意形状和具有非凸区的群成为可能。通常，现有的基于密度的聚类算法的性能在很大程度上依赖于用户的密集干预，以指定密度阈值，这对于区分数据中存在的所有密度水平至关重要。但是，对于未知的大量数据，这些密度阈值通常难以估计。此外，使用全局密度阈值可能会导致对较低密度聚类的错误分类。
在我们之前的工作中，我们提出通过使用插值作为数值分析技术来表征数据集中的密度水平来绕过阈值估计问题。我们采用DBSCAN的聚类形成理念来聚类不同密度水平的数据。我们对所提出的算法（称为多元密度ClUsTering（MDCUT））的实验评估表明，与DBSCAN相比，MDCUT具有1%的平均错误率，平均准确率为98%，平均召回率为99%。然而，我们的实验评估突出了MDCUT的两个缺点：它生成的聚类数量高于实际聚类，并且需要估计样条的张力作为输入参数，并考虑最近邻的数量。这些参数会影响检测到的密度水平数量和阈值。更具体地说，如果省略密度水平，则可能会聚合某些聚类。如果在分类过程中使用了太多级别，则对数据进行深度分区。事实上，最近邻数的选择和样条的张力系数都会影响数目
123
分布式和并行数据库 （2019） 37：73–99
75
图1 MDCUT聚类结果，当变化k
获得的密度水平等最终结果。为了说明输入参数的选择有多重要，让我们分析图 1 和图 2 中的聚类结果。
在图 1 中，我们将张力参数的值固定为 1，并更改了最近邻 k 的数量 （k 5， 7， 9），而对于第二个图，我们将最近邻的数量固定为 9，并更改了张力参数的值（张伸系数 0.5、1、1.2）。从图1和图2中得到的聚类结果表明，k和张力因子的选择非常重要，用户必须正确组合k值和张力因子参数才能获得良好的聚类结果。
在本文中，我们扩展了 MDCUT 以克服这两个缺点并提高其性能。我们通过消除对最近邻数（称为参数 （k））的任意选择来限制对用户干预的敏感性。我们插值了从 k 到 k 的 k 最近邻图。对于每个 k 值，我们将插值曲线中的变化点表征为局部密度水平。我们通过ε的降序对得到的密度参数（ε，k）进行排序。然后，我们研究了这些密度参数的插值曲线，以挑选出具有代表性的阈值。通过检索密度连接点作为输出聚类，为每个密度级别启动聚类过程。我们使用参考文献[25]中提出的发生器来自动设置张力样条参数。我们通过使用参考文献[25]中提出的发生器来避免张力样条的手动设置。MDCUTuse 中的插值函数
123
76
分布式和并行数据库 （2019） 37：73–99
图2 张力因子参数变化下的MDCUT聚类结果
由发电机自动设置的多个张力参数。曲线更平滑，解决了先前版本中观察到的假振荡问题。因此，检测到的拐点数量减少，并且对应于密度水平的实际数量。
MDCUT改进了聚类结果。与基于参考密度的聚类算法（DBSCAN和SNN）相比，MDCUT在几乎所有研究数据集中都表现良好。该算法的效率也显示在真实数据集上。
本文的其余部分组织如下：第 2 节概述了基于密度的聚类中使用的一些基本定义，并简要讨论了众所周知的现有基于密度的聚类算法。第 3 节详细介绍了所提出的 MDCUT 算法以及如何定位不同密度水平并介绍其聚类过程。实验结果见第4节。结论和今后的工作方向是最后一节的主题。
2 基于密度的聚类
基于密度的聚类算法依赖于这样一种思想，即数据可以被视为由稀疏或低密度区域分隔的密集区域。因此，它们形成一个集合
123
分布式和并行数据库 （2019） 37：73–99
77
由低密度点集分隔的高密度点。该技术的优点是可以生成具有任意形状的簇，并且可以很好地处理噪声，而无需事先了解簇的数量。
围绕这一思想已经开发了几种算法，其中我们引用了基于密度的噪声应用空间聚类（DBSCAN）[5]，使用动态建模的分层聚类算法[6]，DENCLUE（DENsityCLUstEring）[7]，共享最近邻算法（SNN）[8]，排序点以识别聚类结构（OPTICS）[9]。在讨论这些算法之前，我们发现有必要概述一下DBSCAN[10\u201212]首先引入的一些定义。
2.1 基本定义
定义 1（点 x 的 eps 邻域）：对于给定的 eps，eps 邻域
数据集 D 中的点 x 的定义如下
N（x） {y ∈ D ： d（x， y） ≤ eps}
其中 d（x，y） 是 x 和 y 之间的距离。
非正式地，点 x 的 eps 邻域是一组点，其与 x 的距离最多为给定的 eps。
定义 2（核心点）：如果一个点的 eps 邻域至少包含最小数量的点 MinPts，则该集合称为核心点。
定义 3（可直接到达密度）：我们说，如果 x 在 y 的 eps 邻域内，并且 y 是核心点，则点 x 可以从点 y 直接到达密度。
请注意，对于成对的核心点（聚类内的点），“密度可达”关系是对称的，但在处理一个核心点和一个边界点（聚类边界上的点）时，它通常不对称。
定义 4（密度可达）：如果存在一系列点 x x、x...x y 使得，当 j = 1,..., i−1 时，我们有 x 可直接从 x 到达密度。
定义 5（密度连接）：如果存在一个点 z，使得 x 和 y 都可以从 z 到达密度，则称两点 x 和 y 相对于一组点 D 中的 eps 和 MinPts 是密度相连的。
基于上述定义，我们可以将聚类定义为一组密度连接点，这些点在密度可达性方面是最大的。
定义 6（聚类）：对于给定的 ε 和 MinPts，数据集 D 中的聚类 C 是非空子集，因此：
1.
∀x， y ∈ D， i f x ∈ Candyis 密度——相对于 ε 和 Min Pts 可达到，然后 y ∈ C;和
2.
∀x、y ∈ C、xandyare 密度与 ε 和 Min Pts 相关
123
78
分布式和并行数据库 （2019） 37：73–99
2.2 现有算法概述
DBSCAN 算法使用两个密度参数 Eps 和 MinPts。它将数据中存在的数据点分类为核心点、边界点或噪声点，并使用核心点根据密度可达性和密度连接关系扩展聚类。DBSCAN可以发现具有任意形状和不同大小的簇，并且可以识别噪声点。然而，它的性能对输入参数（eps 和 MinPts）很敏感，对于使用 kd 树结构的具有 n 个点的数据集 O（nlog（n）），它具有很高的时间复杂度 （O（n）），并且它无法处理数据中存在的密度变化。其中一些缺点已通过后来提出的聚类算法得到解决。
为了克服MinPts问题的估计，GMDBSCAN（MultiDensity DBSCAN Cluster Based on Grid）算法[13]将数据空间划分为网格，为每个网格识别一个局部MinPts，并为每个网格应用相应的MinPt的聚类过程。
另一方面，为了处理密度差异，DDSC（密度微分空间聚类）算法[14]使用了同质核心对象的概念。均匀核心物体是密度不大于也不小于其任何相邻物体密度的 σ 倍的核心点。基于这一概念，DDSC从一个同质核心点开始形成一个集群，并不断添加密度可直接到达的同质核心对象，直到没有检测到其他同质核心对象。
DVBSCAN（一种基于密度的算法，用于在大型空间数据库中发现密度变化的聚类）[15]建议使用两种度量来处理密度变化：将聚类密度平均CDM计算为增长聚类，并计算任何核心点的聚类密度方差CDV，如果该核心点的CDV小于或等于阈值并满足相似性，则应进一步扩展指数。Borah开发的DD-DBSCAN聚类算法[16]扩展了DBSCAN算法，以检测不同密度的聚类。DD-DBSCAN聚类算法使用三个参数：Eps、MinPts和α。DD-DBSCAN算法中Eps和MinPts参数的含义和用途与DBSCAN算法相同，α用于判断簇是否具有均匀密度[17]。OVDBSCAN（Optimum VDBSCAN）[18]旨在通过从k最近邻曲线中选择密度水平来寻找不同密度的聚类。
光学（用于识别聚类结构的排序点）[9]影响每个对象的三个信息：其顺序，核心距离和可达距离。OPTICS 中的对象是根据可达距离排序的，OPTICS 的核心思想是使用这种排序中的可达性图。此图概述了内在聚类结构。OPTICS 不会显式生成聚类结果，但可达性图中的谷值与数据中存在的聚类相关，并且可以对其进行分层建模。
DENCLUE （DENsityCLUstEring） [7] 算法是另一种基于密度的算法，旨在处理数据中存在的密度变化。该算法基于密度分布函数。该算法的主要思想是确定数据空间的密度，该密度是根据每个数据空间的影响计算的
123
分布式和并行数据库 （2019） 37：73–99
79
指向它的邻居。这种影响是使用称为影响函数的函数计算的。数据空间的整体密度可以解析建模为应用于所有数据点的影响函数的总和。然后，可以通过识别密度吸引子来数学确定聚类[19]。DENCLUE的主要优点是：在具有大量噪声的数据集中具有良好的聚类特性，并且对高维数据集中任意形状的聚类具有紧凑的数学描述。然而，DENCLUE需要两个参数，其选择对结果聚类的质量有很大影响：（i）第一个参数（σ）决定了数据点在其邻域中的影响，（ii）另一个参数（ξ）描述了密度吸引子是否显著，从而可以减少密度吸引子的数量，并有助于提高DENCLUE的性能[20]。
SNN（共享最近邻）算法[8]通过改变其密度定义并引入相似度度量的新概念，从根本上扩展了DBSCAN：首先，SNN搜索每个点的k个最近邻，并将相似性视为它们之间的公共邻的数量。其次，它遵循与DBSCAN相同的原理对数据点进行分类。尽管SNN设法克服了密度的变化，但它会产生不完整的聚类，并将未分类的点视为噪声。
Chameleon算法（一种使用动态建模的分层聚类算法）[6]是一种能够表征任意形状聚类的分层算法。它分两个阶段运作。在第一阶段，它使用图分区算法将数据聚类到大量相对较小的子集群中。在第二阶段使用分层聚类算法，将第一阶段找到的子聚类合并为最终聚类。
AUTOCLUST（AUTOmaticCLUSTering）算法[21]消除了所有输入参数，采用基于图的方法，基于Voronoi建模和Delaunay图[22]自动提取集群的边界。AUTOCLUST 消除了对任何输入参数的需求，而是从 Voronoi 建模的邻近结构中揭示了它们。此外，AUTOCLUST 在 Delaunay 图上应用聚类操作，其中数据点成为顶点，数据空间邻近性模型边连接点对。它仅适用于二维数据集。
总而言之，一个好的基于密度的聚类算法应该能够处理数据中存在的密度变化、聚类的形状和噪声的存在。现有算法的不足与计算时间、参数设置、输入参数数量多和密度变化等多个方面有关。这些要求促使MDCUT算法提出检测精确密度水平，从而可以检测不同形状、大小和密度的簇。在这项工作中，我们通过减小张力样条参数并自动设置每个级别的 k 值和局部密度阈值来扩展 MDCUT。用户只需要设置 k 最近邻的间隔 [k， k]，这比指定唯一值 k 更容易。此外，对于所有密度水平，k 的合适值并不相同。
123
80
分布式和并行数据库 （2019） 37：73–99
3 数学背景
插值是通过数学表达式找到一个数学模型（多项式、三角函数、指数等）来描述给定的对数据集（x、y）的问题。
有不同的插值方法，最流行的是三次样条和张力样条（也称为指数样条）。指数样条用作形状保持插值的工具。指数样条插值[23]的主要特征是它们能够通过添加张力因子来保持数据中存在的凸性和单调性，这具有使曲线比使用三次样条[24]时获得的曲线更紧的效果。因此，张力样条插值非常适合离散数据集的近似曲线。
这种方法的主要缺点是使用称为张力参数的输入参数。生成的曲线很大程度上取决于此参数。在我们之前的工作 [1] 中，我们使用样条插值来近似 de k 最近邻曲线，其中张力参数是用户设置的。对于没有数值分析经验的人来说，方便地设置它是一项艰巨的任务。
数值分析文献研究了张力参数设置问题。在他们的工作[25]中，作者提出了一种自动估计张力参数值的方法，此外，他们还提出了使用许多张力因子来避免和减少振荡的不良影响。
具有许多张力因子的张力样条插值定义如下：给定平面的 n 个数据点：P（x， y）、P（x， y）,..., P（x， y），定义一组指数函数 E， E,...,其中函数 E 在以下条件下在区间 [x， x] 上定义：
•
E（x） y
•
E（x） y
•
E（x） y
•
它是 （x） y
•
E− （p/= x− x） E 0 in [x， x]
其中 p是函数 E 的张力参数。这五个条件确保 E 在 [x， x] 中是可导数两次的。
指数样条基于基本系统 {1， x，exp（px），exp（−px）}，这导致了指数样条的局部表示：
E（x） yt + y（1 − t） +
d
p
（Sinh（u t）
sinh（u ）
− 吨） +
d
p
sinh（u （1 − t））
sinh（u ）
− （1 − t））
(1)
式中： x ≤ x < x ， h x − x ， t （x − x ）， u pH .对于 i 0 . . . ， n − 1y E（x） 是给定的数据点，E（x） 是未知的二阶导数。
123
分布式和并行数据库 （2019） 37：73–99
81
在[25]中解决了找到一组良好的张力参数的问题，作者提出了一种算法，通过以下四个步骤迭代计算指数样条参数：
1.
张力因子初始化为零。
2.
根据当前张力值计算样条曲线，以找到发电机的参数并找到一组良好的张力因子。
3.
计算新的张力因子。
4.
使用新的因子值重新计算样条曲线
对于给定边界的条件，即 d = d = 0，二阶导数 d 由对称的正定三对角线系统 Td = b 的解唯一确定，其中：
T
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
Q+ 二维码
r
.
. .
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
. r
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
d（d，d
1
）、b（b、b
1
）和 b
y− y
h
−
y− y
h
(2)
在pH值中
(3)
q
u cosh（u ） − sinh（u ）
USINH（U）
h
(4)
r
正弦（U） − U
USINH（U）
h
(5)
至于启发式生成器 p（参见方程 （1），它们在第一次测试运行中设置为零。之后，根据三次样条曲线在 x 处的二阶导数的符号与二阶差商 b 的符号之间的比较来计算它们（参见方程 （2））。不同的符号表示不需要的振荡，并选择张力参数 p 0。从启发式研究[25]中，我们有：
ph
⎧
⎨
⎩
15 如果 y y
4 +
1
0.1+
||
max
else
(6)
回顾一下，我们根据以下伪代码计算指数样条：
– 计算区间长度 h – 确定 （3） 中定义的 u – 确定 T：
123
82
分布式和并行数据库 （2019） 37：73–99
– 确定 （4） 中定义的对角线 （q[i] + q[i + 1]） – 确定 （5） 中定义的对角线外 r[i]
– 确定右侧 d[i + 1]−d[i] – 确定 （2） 中定义的第二差商 b – 三对角线系统 Td b 的解
此外，我们根据以下伪代码生成张力参数：
– 验证第二个差商 b 的符号和第二个差商的符号
每个 d 区间 [x，x] 中的导数： – 如果 bi*d 的符号为正，则为该区间设置一个等于零的张力参数 – 否则使用方程 （6） 确定张力参数的正确值
4 MDCUT算法
MDCUT算法扩展了我们之前的工作MDCUT。它是一种两阶段算法。在第一阶段，它会自动定位数据集中的局部密度水平。每个级别都由一对值 （ki，ε） 表征，其中 k 是级别 i 的最近邻数，ε 是距离阈值。在第二阶段，根据其密度特征形成团簇。首先提取密度较大的聚类，然后从剩余的非分类点中检测密度较低的聚类。MDCUT通过使用第 3 节中解释的发生器消除了张力样条参数设置。虽然以前的版本要求唯一值 k 来计算局部密度阈值，但 MDCUT会自动为每个密度级别计算合适的值 k。此值取决于集群之间的数据分布和集群密度。
4.1 密度水平测定
通过研究到第 k 个最近邻的距离的行为，可以自动检测数据集中的密度水平。很明显，对于给定的 k，一个点位于密度越大的区域，它与第 k 个最近邻的距离越低，反之亦然。因此，属于密度变化较小的区域的点将具有接近 k-dist 的值。同时，对于属于具有不同密度区域的点，它们的 k-dist 值之间会有差距。排序后的 k-dist 值的散点图可以可视化数据之间的密度分布。我们绘制数据点的秩及其对应的 k-dist。在图 3 和图 4 中，我们给出了两个数据集的这些图的示例。
k-dist图的出现表明存在多阶段谷，两个连续谷之间存在过渡带。属于同一谷的数据点容易属于数据空间中具有大致相同数据密度的区域。生成具有不同
123
分布式和并行数据库 （2019） 37：73–99
83
图3 数据集D1的排序k-dist值散点图
密度，我们可以分两步进行：选择一个山谷的数据点并从中构建聚类。
MDCUT 算法通过指数样条插值对 k-dist 图进行插值。从一个密度水平到另一个密度水平的转变伴随着 k 个最近邻的曲线凹度的变化。密度水平在MDCUT中建模，半径ε可以从拐点或k最近邻距离曲线中的拐点获得。图5显示了基于检测到的拐点，在每个密度水平下的k-dist曲线、变化点和选定的核心点。
在图 3 和图 4 中，数据集 D1 和 D2 具有两个密度水平。在 D1 中，簇被很好地分离。在 D2 中，较密集的簇被封闭在较稀疏的簇中。对于数据集 D1，我们给出了 k 5、9、15 和 20 的 k-dist 图。对于k 5，数据集D1中存在的密度水平之间的过渡在视觉上并不清晰。对于k 9、15和20，我们注意到随着k值的增加，密度水平之间的过渡更加尖锐。对于数据集 D2，属于曲线两侧的点的 k-dist 值之间存在不连续性。随着 k 值的增加，属于每个密度水平的点之间的曲线分离是清晰的。但是，对于密度变化的聚合簇和相邻簇，k-dist曲线的行为会发生变化，并且对于较大的k值，谷可能会消失。
123
84
分布式和并行数据库 （2019） 37：73–99
图4 数据集D2的排序k-dist值散点图
图5 数据集D1中检索到的一组核心点
密度阈值 ε 的值取决于 k 的选择，而 k 又是任意的。
此外，软膝经常出现在 k 最近邻曲线中，几乎不影响
123
分布式和并行数据库 （2019） 37：73–99
85
图6 数据集及其4最近邻曲线和KNN分布
选择最佳ε值。这实际上证明了从一个 k 最近邻图中选择的密度半径不能始终准确反映其他 k 最近邻距离曲线中存在的其他密度半径。事实上，如 KNN 分布 （k 1...30）在图6的右侧，膝盖覆盖了很宽的ε范围（目视上，第一个范围低于0.2，第二个范围在0.2和0.6之间）。
同一张图描绘了具有两个密度级别的数据集;其 4 最近邻曲线的形式表示存在两个水平谷，这意味着两个密度水平。问题在于，4 最近邻曲线不能准确反映其他 k-dist 曲线形状，在这些形状中，我们可以看到第一密度水平的 ε 范围低于 0.15，而第二密度水平的范围超过 0.35。
图 7 显示，对于相同的密度水平，在改变 k 值的同时获得 ε 的近值。但是，从一个级别传递到另一个级别时，ε 值之间存在跳跃。我们在 k-ε 图中观察到谷的存在以及在两个密度水平之间检测到的半径阈值之间的过渡。对于一个密度水平，对于高 k 值，ε 值会突然增加。这些值出现在连续密度水平之间的过渡区。必须从 k-ε 图中检测出 ε 的最优值。为此，我们插值 k-ε 图，然后从 k-ε 曲线计算最佳ε。k-ε曲线中的变化点是我们正在寻找的局部密度阈值。因此，密度水平的特征是几个值 （k，ε） 代表获得半径阈值ε的 k 值。
为了找到局部密度阈值，MDCUT 算法分两个主要步骤工作：
– 第 1 步 确定每个值的局部密度阈值 k，k 范围从 k到 k。
– 第 2 步：根据所有检索到的局部密度阈值检索最佳阈值。
更具体地说，我们自动确定最佳局部密度阈值，如下所示：
1.
从 kd 树中确定 [k，k] 中每个 k 值的 k-dist 值。
2.
在 [k，k] 中对 k 进行排序的 k-dist 插值。
123
86
分布式和并行数据库 （2019） 37：73–99
图7 检索到的阈值图和代表阈值的选择
3.
在 [k，k] 中 k 的 k-dist 曲线中求拐点。
4.
插值 3 中提取的所有密度半径的排序 k-ε。
5.
在 k-ε 曲线中找到膝盖点。
6.
返回 （k，ε） 级别 i、i 1、...，n，其中 nis 检测到的密度级别数。
在步骤 1 中，我们使用 k kthan 构建 kd 树，我们从这棵树中检索所有 k-dist。在步骤 2 和 4 中，我们通过张力样条插值对数据进行插值。张力参数由第 4 节中描述的发电机自动设置。在步骤 3 和 5 中，我们使用变化点的数学定义来确定膝盖点。我们提醒，局部阈值与满足此条件的点集一致：{（x， F（x）），其中 F（x） 0 和 F（x） 0， x ∈ [1，n]}。在 6 中，我们返回值 （k ，ε） 的对来表征数据中的密度水平，其中 k和 ε 分别代表邻居的数量和 i 密度水平的半径阈值。
4.2 基于局部密度阈值的聚类过程
传统上，基于密度的聚类算法使用全局密度参数对数据进行聚类。全局参数的选择会影响聚类结果的质量。具有不同密度的数据集由具有不同数据点分布的区域组成，因此每个区域都有自己的密度特征。为了克服这一限制，我们的想法是使用多个局部密度阈值和不同的最小最近邻数值来描述数据集中的每个密度变化。基于这些密度参数，具有不同密度的数据可以通过其密度水平来描述。数据可以看作是不同的密度级别分区。因此，每个密度级别分区都是由具有相同密度的数据点形成的，并且该级别中的密度变化非常小或不存在。从一个层次到另一个层次的通道的特征是密度分布的急剧变化
123
分布式和并行数据库 （2019） 37：73–99
87
数据点。预计被归类为噪声或异常值的点位于聚类边界或孤立点之外的稀疏区域。
MDCUT使用从密度曲线 k-dist 和 k-ε 中提取的局部密度阈值。密度水平 i 由< 1，n 中 i 的一对 （k ，ε） 表征>其中 n是数据中自动检测到的密度水平的数量。
接下来，在描述聚类过程之前，我们给出一些定义。
定义 7（局部阈值）：局部阈值是满足以下条件的点集：{（x， F（x）） 其中 F（x） 0 和 F（x） 0， x ∈ [1，n]} 其中 F 是排序的 k-dist 的插值函数，n 是数据集的大小。
定义 8（代表性阈值）：代表性阈值是满足此条件的对 （k，ε）， i 1..n： {（x， F （x）） 其中 F（x） 0 和 F（x） 0， x ∈[1，l] 其中 lis 局部阈值列表的长度}。
代表性阈值是从局部阈值曲线 （k-ε） 中提取的拐点。k-ε 曲线是从 k 范围的 k-dist 曲线中检测到的排序局部阈值的插值函数。
定义 9（密度级分区）：密度级分区 （DLP） 定义如下：DLP {一组点p 与满足 kdist（p） < = ε} ε<最近邻的距离，其中 ε 和 ε 是两个连续的代表性阈值，i 1...NAND ε 0。
密度级别分区由具有相同密度分布的所有点组成。也就是说，该水平的密度变化非常小或不存在。每个密度级别分区的特征是描述该级别中密度分布的阈值和最小最近邻数的值;我们称此阈值为代表性阈值 （K，ε）。
定义 10（局部核心点）：点 q 是密度级分区的局部核心点
DLP （i = 1...n ） 如果：
•
0 < kdist（q） ≤ ε 表示 i 1 （第一级分区）
•
ε< kdist（q） ≤ ε否则
•
q /∈∪C（eps ） （q 尚未分配给任何集群）
其中 C（eps） 是在密度级别分区 DPL 中检索到的簇，∪C（eps） 是在该级别检索到的簇。
定义 11（噪声和异常值）：噪声点是未分配给任何聚类的所有点。
自动检测到的代表性密度阈值用于识别具有不同密度的聚类。这些阈值按半径ε的升序排列。e 值的增加意味着数据点的分布更稀疏。在聚类过程中，首先检测密度较大的聚类，以避免聚类。
簇发现过程使用其两个代表性密度参数（代表性阈值、最小最近邻数）应用于每个分区级别 DPL。给定一对 （eps ，k），聚类过程包括根据代表性阈值最大化密度连接点。
123
88
分布式和并行数据库 （2019） 37：73–99
从 DPL 中检索到未标记的核心点 q，并启动集群 C。半径 epsis 邻域中 q 的所有邻居都添加到聚类 C 中。如果到达的邻居是核心点，则该点将用于扩展聚类 C。以递归方式应用相同的过程，直到检索到所有连接的点。从核心点 q 启动集群后，集群构建过程将从 DPL 中的另一个未标记点重新启动，并创建一个新集群。因此，基于局部点和该层中不同点之间的连通性关系，我们可以提取具有相同密度水平的不同聚类。这项工作是针对检测到的每个密度水平完成的。在MDCUT中自动检测数据中存在的密度水平数。
MDCUT 算法的伪代码如下：
123
分布式和并行数据库 （2019） 37：73–99
89
表1 数据集说明
数据
Type
Size
尺寸
数量
集群
描述
DS1
假
282
2
2
具有嵌套和不同密度聚类的数据
DS2
假
299
2
3
具有分离良好且密度变化的聚类的数据
DS3
假
371
2
2
具有不同密度和相邻聚类的数据
DS4
假
1100
2
5
具有不同密度聚类的噪声数据
DS5
假
2586
2
7
具有任意形状和不同密度聚类的数据
DS6
假
8394
2
12
具有任意形状、嵌套、相邻和不同密度聚类的数据
DS7
假
8000
2
6
存在噪声的任意形状数据
DS8
假
8000
2
8
存在噪声的任意形状数据
DS9
假
10,000
2
9
存在噪声的任意形状数据
种子
Real
210
7
3
基于密度的数据
Landsat（大地卫星）
Real
6435
36
7
许多聚类算法使用的数据
Optd
Real
3823
64
10
许多聚类算法使用的数据
5 实验结果
我们已经在主要用于验证基于密度的聚类算法的基准数据集上测试了 MDCUT 算法的性能。我们考虑了人工数据集和真实数据集。我们使用了 9 个人工数据集和 3 个真实数据集（见表 1）。如图8和图12所示，这些数据集中的聚类具有不同的密度、任意形状和复杂形状。
123
90
分布式和并行数据库 （2019） 37：73–99
图8 任意形状和不同密度数据集
聚类结果通过可视化散点图和计算性能指标（调整后的兰德指数、纯度和误差）给出。
纯度指数计算如下：具有两个分区 x 和 y，x 类相对于 y 类的纯度等于
∑
j
最大 N
/
n
其中 n 是
X 类 I 和 Y 类 J 类中物体的联合频率是物体的总数。
调整后的兰德指数是兰德指数的归一化差值，定义如下[26]：
AR I
(
C, C
)
∑
i1
∑
j1
(
m
2
)
− t
1
2
（t+t）
其中 C {C， ， C } 是数据的引用分区，C
{
C， ， C
}
获取的数据分区。
米 |C ∩ C
∣
∣
∣， 1 ≤ i ≤ k， 1 ≤ j ≤ l
t
k
∑
i1
(
|C |
2
)
, t
l
∑
j1
( ∣
∣
∣C
∣
∣
∣
2
)
，t nand n 是对象的总数。
对于第一个和第二个度量值，值越高表示聚类结果越好。
评估算法的性能也使用错误分类错误率来衡量，错误分类错误率等于错误分类单元总数除以数据点总数。根据此度量，错误率低的聚类结果是良好的聚类。
我们通过与 MDCUT、DBSCAN 和 SNN 的比较来评估 MDCUT 的性能。表 2 给出了所研究算法的参数设置
123
分布式和并行数据库 （2019） 37：73–99
91
表2 4种算法的参数设置
数据
参数
MDCUT的
MDCUT的
DBSCAN扫描
SNN
k
P
[K,
K]
Minpt
Eps
K
Eps
Minpt
DS1
8
0.000001
4
0.5
5
0.7
4
DS2
10
1
10
0.14
15
0.6
8
DS3
10
1.2
4
15
15
5
10
DS4
10
0.49
5
0.15
15
5
10
DS5
10
0.49
5
15
15
5
10
DS6
7
1
5
0.01
15
5
10
DS7
4
1.5
10
8
85
15
80
DS8
5
0.187
5
8
80
15
75
DS9
5
0.1265
4
6.2
85
15
80
里斯。我们进行了大量的实验来修复MDCUT、DBSCAN和SNN算法的合适参数。
5.1 视觉验证
5.1.1 具有不同密度数据集的任意复杂形状（密度的影响）
如图8所示，所研究的数据集包含凸簇和非凸簇。使用MDCUT的聚类结果显示，如图9所示，它既可以处理任意形状的数据，也可以处理数据中存在的密度变化。相反，如图10所示，当簇具有不同的密度时，DBSCAN无法正确表征簇。例如，对于包含两个密度级别的 DS1，DBSCAN 只能检测到一个簇，因此无法很好地处理密度变化的簇。当 DBSCAN 将两个嵌入式簇合并为一个 DS6 的灰色簇，并且无法检测到两个不同密度的簇并将它们视为 DS2 的一个簇时，DS2 和 DS6 也证明了这一缺点。对于SNN，该实验表明，该算法可以处理密度的变化，前提是人们成功地选择了正确的输入参数组合，但它不能很好地处理混合簇，如图1所示。
5.1.2 有噪声的数据集（噪声的影响）
处理嘈杂数据是聚类分析的一项具有挑战性的任务。在这个实验中，我们使用嘈杂数据集DS7、DS8和DS9测试了我们的算法，这些数据集是Chameleon算法[6]使用的基准数据集。仔细观察
123
92
分布式和并行数据库 （2019） 37：73–99
图9 任意形状和不同密度数据集上的MDCUT聚类结果
图10 任意形状和不同密度数据集上的DBSCAN聚类结果
从图12和图13可以看出，MDCUT成功地正确地发现了三个数据集中的原始聚类。从图14和图15中可以得出结论，SNN算法在DS8和DS9中划分了一些簇，而DBSCAN算法在DS8中合并了一些簇，并且不能很好地检测DS9中被认为是核心的噪声点。
5.2 定量评估
如表3所示，纯度、ARI和误差测量值介于0和1之间。与 SNN 相比，MDCUT在所有指标的四个数据集（DS1、DS2、DS3 和 DS9）上表现更好。根据误差标准，MDCUT要么正确分类所有数据点，要么比SNN的分类误差更少。总体而言，除数据集 DS5 和 DS6 外，MDCUT 的性能更好或与 SNN 相当。此外，MDCUT的优点是不需要对三个参数（k，minpts，Eps）的值进行仲裁。
123
分布式和并行数据库 （2019） 37：73–99
93
图11 任意形状和不同密度数据集上的SNN聚类结果
图12 具有噪声的任意形状数据集
图 13 MDCUT在任意形状的噪声数据集上的聚类结果
123
94
分布式和并行数据库 （2019） 37：73–99
13 MDCUT在具有噪声的任意形状数据集上的聚类结果 图14 在具有噪声的任意形状数据集上的SNN聚类结果
图15 具有噪声的任意形状数据集上的DBSCAN聚类结果
MDCUT完全优于五个数据集（DS2、DS3、DS4、DS5 和 DS9）的 DBSCAN。对于 DS1，MDCUT 和 DBSCAN 在 ARI 索引和错误上具有相同的性能值。但是，MDCUT在准确性方面超过了DBSCAN。对于其余数据集（DS6、DS7 和 DS8），根据 ARI 和错误标准，MDCUT 的性能优于 DBSCAN。
与MDCUT相比，所提出的扩展在很大程度上改善了几乎所有数据集在所有标准上的聚类结果。
MDCUT的平均准确率为89%，而DBSCAN为71%，SNN为70%。根据 ARI，MDCUT 的平均值为 97%，DBSCAN 的平均值为
123
分布式和并行数据库 （2019） 37：73–99
95
表3 9个数据集聚类算法评价
MDCUT的
MDCUT的
DBSCAN扫描
SNN
DS1
准确性
0.024
1
0
0.080
ARI
0.401
1
1
0.311
错误
0.102
0
0
0.124
DS2
准确性
1
1
1
0.080
ARI
1
1
0.630
0.997
错误
0
0
0.204
0
DS3
准确性
0.567
1
0.425
0.983
ARI
0.806
1
0.417
0.949
错误
0.029
0
0.005
0.008
DS4
准确性
0.345
0.951
0.949
0.942
ARI
0.412
0.965
0.962
0.970
错误
0.228
0.024
0.024
0.023
DS5
准确性
0.9982
0.988
0.645
0.994
ARI
0.9974
0.994
0.952
0.992
错误
0.0015
0.003
0.019
0.003
DS6
准确性
0.586
0.575
0.943
0.739
ARI
0.925
0.917
0.818
0.957
错误
0.0001
0.0030
0.1434
0.0002
DS7
准确性
0.194
0.903
0.921
0.916
ARI
0.439
0.998
0.954
0.959
错误
0.087
0.0006
0.020
0.021
DS8
准确性
0.7475
0.744
0.788
0.922
ARI
0.646
0.960
0.728
0.930
错误
0.187
0.0242
0.211
0.0243
DS9
准确性
0.02
0.8535
0.794
0.698
ARI
0.635
0.949
0.825
0.909
错误
0.138
0.0321
0.0874
0.052
对于每种聚类算法，每个数据集中的最佳性能以粗体显示
123
96
分布式和并行数据库 （2019） 37：73–99
每个数据集中的最佳性能以粗体显示 图16 MDCUT、SNN和DBSCAN的执行时间比较
80%，SNN为88%。根据误差度量，MDCUT、DBSCAN和SNN的平均值分别为0.9%、7%和2%。总之，MDCUT 在精度和 ARI 方面更可靠，并且根据误差度量优于其他算法。
5.3 执行时间
执行时间也可以用作算法的性能标准。我们使用 DBSCAN 的 C++ 实现，SNN 的 JAVA 实现，并且我们用 R 语言实现了 MDCUT。对于 MDCUT，执行时间很大程度上取决于最近邻域的 kand kof 数以及检索到的密度水平数。如表 4 所示，如图 16 所示，当数据集大小增加（DS8 和 DS9）时，与 SNN 相比，MDCUT 需要更少的执行时间，而 DBSCAN 需要的执行时间最短。MDCUT 比 MDCUT 更快，因为在新版本中，我们运行 K 次的快速排序算法范围，即 O（（k-k）*n*logn）。因此，预计 MDCUT 比 MDCUT 慢约 （k−k） 时间。
5.4 对真实世界数据集的比较评估
我们使用了三个真实数据集来研究MDCUT在真实数据上的性能。第一个研究的数据集是UCI Seeds，这是一个流行的基于密度的数据集，用于验证聚类算法。在种子数据集中，我们有属于三个不同小麦组的籽粒：Kama、Rosa 和 Canadian。有 70 个元素
123
分布式和并行数据库 （2019） 37：73–99
97
表4 不同合成数据集执行时间
数据
Size
（分钟）
（分钟）
DBSCAN时间
（分钟）
SNN时间
（分钟）
DS1
282
0.001466747
0.03535202
0.001533433
0.0145175
DS2 299 0.001816781 0.03271853 0.0006167173 0.003250182 DS3 371 0.001900101 0.0368521 0.0007000327 0.002483483 DS4 1100 0.007433786 0.108529 0.0007000486 0.007533769 DS5 2586 0.0127174 0.3231351 0.0008667032 0.03686878
DS6
8394
0.03546868
1.728499
0.002083449
0.2155123
DS7
8000
0.02515144
1.804495
0.001366735
2.29713
DS8 8000 0.08500485 1.86399 0.001350065 1.96347 DS9 10000 0.1386913 2.743774 0.001583417 3.39902
每组各有尽。理想情况下，聚类算法应生成三个高质量的聚类，每个聚类有 70 个点。
第二个研究数据集是来自 UCI 机器学习存储库的 Landsat 卫星数据集，由 4435 个对象组成;它是从遥感卫星图像中获得的。每个物体代表一个 3 × 3 区域，每个子区域都通过在不同波长下进行的四次强度测量来记录。因此，每个对象有 36 个属性。还为每个对象提供了指示中心子区域类型的类标签。
最后研究的数据是 Optdigits 数据;它是一个众所周知的数据集，由 UCI 机器学习 Repositoryhttps://archive.ics.uci.edu/ml/index.html 上提供的手写数字集合组成。该数据包含从 30 个不同的人那里收集的 3823 张手写数字图像。每个图像是 8 像素 x 8 像素，因此每行有 64 个数字，加上一个标签，总共 65 个。
表5给出了三种研究算法在真实数据集上的评估。
这些结果表明，MDCUT在准确率方面优于DBSCAN和SNN。MDCUT的平均准确率为81%，而DBSCAN的平均准确率为78%，SNN的平均准确率为64%。与 MDCUT 相比，MDCUT 改进了所有性能指标度量。
6 结论
总而言之，我们可以说基于密度的聚类算法具有发现不同大小和形状的聚类的好处。聚类被视为包含给定半径内最小点数的连通邻域。该假设需要调整参数以提前获得该区域的正确面积值，就像在 DBSCAN 和 SNN 算法中一样。参数选择步骤可能会受到高计算成本的影响，并且可能需要专家用户来完成，这会影响结果的质量。
123
98
分布式和并行数据库 （2019） 37：73–99
表5 基于真实数据集的聚类算法评估
MDCUT的
MDCUT的
DBSCAN扫描
SNN
种子
准确性
0.6751
0.8833
0.9259
0.5647
ARI
0.4115
0.4148
0.3946
0.6203
错误
0.2761
0.3428
0.3523
0.1095
Landsat（大地卫星）
准确性
0.6169
0.6877
0.6079
0.5738
ARI
0.3670
0.4745
0.4691
0.3667
错误
0.4045
0.3490
0.3670
0.3988
Optd
准确性
0.6295
0.8748
0.8498
0.8018
ARI
0.0149
0.7772
0.7827
0.7480
错误
0.0589
0.1749
0.1718
0.1755
对于每种聚类算法，每个数据集中的最佳性能以粗体显示
MDCUT是一种基于相邻图的基于密度的聚类算法。
研究这些图形以搜索数据中存在的密度阈值。使用插值的目的是自动提取数据中的密度水平。聚类过程是使用检测到的密度值执行的。MDCUT 是一种聚类算法，它消除了人为干预，以找到聚类过程所需的最佳参数组合，并且能够检测具有不同密度、任意形状和不同大小的聚类。使用许多合成和真实数据集演示了 MDCUT 算法的性能。
引用
1.
Louhichi， S.， Gzara， M.， Ben-Abdallah， H.：使用样条曲线的基于无监督可变密度的聚类算法。模式记录。Lett. 93， 48–57 （2017年）
2.
Steinbach， M.， Ertöz， L.， Kumar， V.：聚类高维数据的挑战。统计物理学的新方向，第 273-309 页。施普林格，柏林，海德堡（2004）
3.
Ashour， W.， Murtaja， M.：使用基于距离的技术在集群密集区域内进行查找。I.J.智力。系统应用 14， 42–48 （2012）
4.
Parimala， M.， Lophne， D.， Senthilkumar， N.C.：关于用于挖掘大型空间数据库的基于密度的聚类算法的调查。Int. J. Adv. Sci. Technol. 31， 59 （2011）
5.
Ester， M.， Kriegel， H.， Sander， J.， and Xu， X.：一种基于密度的算法，用于在大型空间数据库中发现带有噪声的聚类。收录于：Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining （KDD'96），第 226–231 页（1996 年）
6.
Karypis， G.， Han， E.， Kumar， V.：Chameleon：一种使用动态建模的分层聚类算法。IEEE计算。32(8), 68–75 (1999)
7.
Hinneburg， A. 和 Keirn， D.A.：一种在具有噪声的大型多媒体数据库中进行聚类的有效方法。载于：Proceedings on Fourth International Conference on Knowledge Discovery and Data Mining（第四届知识发现和数据挖掘国际会议论文集），第 58–65 页（1998 年）
8.
Ertoz， L.、Steinbach， M. 和 Kumar， V.：在嘈杂的高维数据中寻找不同大小、形状和密度的聚类。收录于：Proceedings on 2nd SIAM International Conference on Data Mining，旧金山，第 1–12 页（2003 年）
9.
Mihael， A.， Markus， M.B.， Hans-Peter， K.， Sander， J.：光学：用于识别聚类结构的排序点。收录于：ACM SIGMOD，第 49–60 页（1999 年）
123
分布式和并行数据库 （2019） 37：73–99
99
10.
Han， J.， Kamber， M.：数据挖掘：概念和技术，第 2 版。Morgan Kaufmann Publishers，伯灵顿（2006）
11.
Gan，G.，马，C.，Wu，J.：数据聚类：理论，算法和应用，ASA-SIAM统计和应用概率系列。费城暹罗 （2007）
12.
Popat， S.K.， Emmanuel， M.：聚类技术的回顾和比较研究。国际 J. Comput.Sci. Inf. Technol. 5（1）， 805–812 （2014）
13.
Xiong， C.， Yufang， M.， Yan， Z.， and Ping， W.， “GMDBSCAN：基于网格的多密度DBSCAN集群。在：IEEE电子商务工程国际会议（2008）
14.
Borah， B.， Bhattacharyya， D.K.： DDSC：一种密度差分空间聚类技术。J.计算。3, 72–79 (2008)
15.
Ram， A.， Jalal， S.， Jalal， A.S.， Kumar， M.：一种基于密度的算法，用于在大型空间数据库中发现密度变化聚类。国际 J. Comput.应用3， 1 （2010）
16.
Borah， B. 和 Bhattacharyya， D. K.：一种使用密度差的聚类技术。收录于：Proceedings of International Conference on Signal Processing， Communications and Networking（《信号处理、通信和网络国际会议论文集》），第 585–588 页（2007 年）
17.
Tsai， C. 和 Huang， Y.：DDCT：使用新型聚类技术检测密度差异。收录于：Proceedings of the 9th WSEAS International Conference on Multimedia Systems and Signal Processing（第 9 届 WSEAS 多媒体系统和信号处理国际会议论文集），第 243–248 页（2009 年）
18.
Wang，W.，周，S.和Xiao，Q.：用于识别市中心区域的最佳Vdbscan（O-VDBSCAN）。国际 J. 数字。Inf. Wirel.公社。66–71 (2013)
19.
Obula Reddy， B.G.， Ussenaiah， M.：关于聚类技术的文献调查。IOSR J. 计算。工程 3（1）， 01–12 （2012）
20.
Das S.、Abraham， A. 和 Konar， A.：元启发式聚类 178 （2009）
21.
Estivill-Castroand， V. 和 Lee， I.：AUTOCLUST：通过边界提取对大规模点数据集进行自动聚类。收录于：第五届国际地球计算会议论文集（2000年）
22.
Gold， C.M.：处理空间数据的问题 - Voronoi 方法。CISM J 45（65–80）， 1991 （1991）
23.
Späth， H.：指数样条插值。计算 4， 225–233 （1969）
24.
Grevile， T.N.E.：样条函数、插值和数值正交。在：Ralston， A.， Wilf， H.S. （eds.） Mathematical Methods for Digital Computers，第二卷，第 156-168 页。威利，纽约 （1967）
25.
Rentrop， P.：一种用于计算指数样条的算法。数字。数学 35， 81–93 （1980）
26.
Kuncheva， L.I.， Hadjitodorov， S.T.：在集群集合中使用多样性。在：IEEE SMC系统，人与控制论国际会议（2004）
出版商注：施普林格·自然（Springer Nature）对已出版地图和机构隶属关系中的管辖权主张保持中立。
123
