一种优化初始点与自适应半径的密度聚类算法

王治和，曹旭琰，杜 辉

（西北师范大学计算机科学与工程学院，兰州 730070）

0 概述

数据挖掘是从大量数据中提取有价值信息的过程，将其转化成人们需要的且有组织的知识信息［1-2］，已在许多领域取得重要成果。聚类分析是数据挖掘的重要技术之一，可以作为一种独立的工具深入了解数据集的分布情况。其主要任务是将数据集中的每一个数据样本划分到相应的簇中，使簇内的样本彼此相似，而簇间的样本彼此不相似［3-4］。目前，聚类分析已经广泛地应用于图像分析［5］、模式识别［6］、生物信息学［7］、知识发现［8］、医学［9-10］和农业［11］等领域。基于密度的聚类算法是聚类分析的重要技术之一，其中经典算法有DBSCAN 算法［12］、OPTICS算法［13］、DENCLUE 算法［14］等。

文献［12］提出的DBSCAN 算法，聚类初始点是从数据集中任意取出一个样本，判断其为核心点后开始聚类，增加了算法的时间开销。该算法中的Eps和MinPts 是全局参数，在聚类过程中不能改变，所以不能正确聚类密度不均匀的数据集。因此，如何恰当地选择聚类的初始点和Eps 值是提高聚类准确度的关键因素，很多学者对此做了大量研究和改进。文献［13］提出OPTICS 算法，该算法并不产生数据集聚类，而是输出一个表示数据的基于密度的聚类结构的簇排序，克服了使用一组全局参数的缺点。但这种总是朝高密度区域扩张的策略，使那些无法连向下一个高密度区域的低密度点往往被累积在结果序列的末尾，导致这些低密度点与高密度点的相邻关系在映射时被分离［15］。文 献［16］提出的OSDBSCAN 算法优化了初始点的选择，并结合数据集的特点自适应计算Eps 和MinPts 值，但是引入了聚类个数k、密度参数α、倍率参数β3 个参数，不仅没有减少人为干预，而且带来更大的复杂性。文献［17］提出VDBSCAN 算法，该算法能够聚类密度不同的数据集，求每个数据样本的第k个近邻，利用k-dist 图选取不同密度层次相应的Eps 值，但是选取过程需要人为干预，存在很大的不确定性。文献［18］提出RNN-DBSCAN 算法，使用反向最近邻（RNN）的思想来定义密度和核心样本，但整体的聚类效果不佳且运行时间较长。文献［19］提出ADBSCAN 算法，利用最近邻图（NNG）固有的性质来识别局部高密度样本，运用密度估计对噪声样本进行滤波，但在某些情况下，该算法有时无法识别正确的簇数，而且需要对多个参数组合进行测试。

通过上述研究发现，RNN 算法对获取全局密度最大的数据样本起到重要作用，解决了DBSCAN 算法随机取初始点的问题。本文提出一种新的OIRDBSCAN 算法，借鉴OPTICS 算法中核心距离和可达距离的思路，通过调整核心距离和可达距离的值得到适合该簇的半径r，以解决DBSCAN 算法中Eps是全局参数的问题。

1 相关工作

1.1 DBSCAN 算法

DBSCAN 算法可以发现任意形状的簇，并识别噪点，不需要设定具体的簇数，聚类效果稳定。在Eps 邻域、MinPts 密度阈值、核心点、直接密度可达、密度可达的基础上设定了密度相连［20］概念。

DBSCAN 算法从任意一个点p出发，先判断其是否是核心点，若是，寻找Eps 邻域内与p直接密度可达的点，将这些点放入集合U中，然后遍历集合U中的所有核心点，寻找与它们密度可达的点，迭代上述步骤，直到集合U中没有可扩展的核心点，此时形成了一个完整的簇；若不是，暂时将其标注为噪点。聚类完成其中的一个簇后，对未遍历的数据点重复上述过程，进行其他簇的扩展，直至所有的点被遍历。其中既不是核心点也不是边界点的被称为噪点。

1.2 点x 的k 近邻和反向最近邻

假设X是d维空间中的数据点集，用n表示X的大小，n=|X|。∀x∈X，x∈Rd。对于X中的任意两个点x和y，用表示两点之间的距离，其中k的取值范围为1≤k≤n-1。

定义1点x的k近邻用Nk(x)=N表示，其中N满足以下条件：

定义2点x的反向最近邻用Rk(x)=R表示，其中R满足以下条件：

1）R⊆X/{x}。

2）∀y∈R：x∈Nk(y)。

下文用具体的示例对上述定义做出解释，该数据集共有5 个点，如图1 所示。

图1 二维空间5 个数据点的最近邻图Fig.1 Nearest neighbor graph of five data points in two-dimensional space

从图1可以看出：a点的最近邻是b，b点和c点互为最近邻，d点的最近邻是c，以此类推。在k近邻中，k取1 时为最近邻点，k取2 时为第二近邻点，k取n（n为正整数）时为第n个近邻点。图1 的最近邻表如表1 所示，取k=1。对于反向最近邻，需要满足定义2 的2 个条件，具体分析如表2 所示。

表1 二维空间5 个数据点的最近邻表Table 1 Nearest neighbor table of five data points in two-dimensional space

表2 二维空间5 个数据点的反向最近邻表Table 2 Reverse nearest neighbor table of five data points in two-dimensional space

反向最近邻表如表2 所示，其中以点b为例进行分析。点c满足∀x∈X：dist(b，c)≤dist(c，x)，所以c是b的反向最近邻点，a同理，满足∀x∈X：dist(b，a)≤dist(a，x)，所以a也是b的反向最近邻点。其他点的分析方法类似。

2 OIR-DBSCAN 算法

2.1 设计方法

首先寻找数据集中全局密度最大的数据样本，将该样本作为聚类初始点，然后用自适应半径的方法计算出该初始点所在簇相应的r值。以该样本为初始点，r值为半径开始聚类。当一个簇聚类完成后，再从剩余的数据样本中选出新的聚类初始点，迭代上述过程，直至所有数据样本被划分类别或有部分数据样本被当作噪声处理，聚类结束。

2.2 初始点优化

在K-means 算法中初始点的优化对算法的改进尤为重要。尽管DBSCAN 算法中初始点的优化对聚类结果的影响不太明显，但从算法的角度考虑，如果初始点选择的是全局密度最大的点，那么该点一定是核心点，可以省去判断某个点是否是核心点的时间。本文从文献［16，18］中得到启发，改进的算法能够找到数据集中全局密度最大的点。

在初始点优化思路中，运用到1.2 节中提到的k近邻算法和反向最近邻。从表2 可以看出，a点和e点无反向最近邻，b点的反向最近邻是a和c，c点的反向最近邻是b和d。也可以理解为：a和e没有出现在任何点的好友圈中，而b出现在a和c的好友圈中，c出现在b和d的好友圈中，d出现在e的好友圈中。可以看出b和c在好友圈的活跃程度最高，在一定程度上证明其周围数据点的密度较高。

首先根据反向最近邻表计算出每个点反向最近邻的个数m，m越大，意味着该点的活跃度越高，越有可能成为初始点。但是要计算出最终的聚类初始点，不能只根据m值，需要考虑下面这种情况，如图2 所示（设k=1）。

图2 52 个数据样本考虑m 值的示意图Fig.2 Fifty-two data samples only consider the schematic diagram of m value

观察箭头所指的两个点，通过计算得出它们的反向最近邻个数m均等于4。那么如果只考虑m，则两者大小一样。但图2 中右下角箭头所指的点所在簇的密度显然大于左上角中箭头所指的点所在簇的密度。因此，不能只考虑m的取值，还应该考虑该点与k个邻近距离和的大小，记为dist。dist 越大，密度越小；反之dist 越小，密度越大。

设数据集的相似度矩阵为MMatrix，相似度矩阵用欧式距离表示，每行按从小到大排序后，去除第一列的零元素，记为KNNMatrix。每个数据样本对应的m值记为minit。VValue(init)的大小决定该init 点是否可以作为聚类初始点，值越小，表明该点越适合作为聚类初始点；反之，不适合。因此，聚类初始点的判别公式如式（1）所示：

将当前最小的VValue(init)值对应的init 作为聚类初始点。当一个簇聚类完成后，将已经有聚类标签的点从候选init 队列中删除，方便重新选出下一次聚类的初始点。

初始点的选择如图3 所示，数据集的初始点依次为三角形、六边形和五角星所在的点。

图3 52 个数据样本初始点示意图Fig.3 Schematic diagram of initial points of fifty-two data samples

初始点的优化算法如算法1 所示。

算法1初始点优化

输入k（k=4）

输出init

步骤1求出各个样本之间的相似度矩阵MMatrix，用欧式距离表示。

步骤2对Matrix 按行升序排序，去掉第一列的0 元素，得到矩阵KNNMatrix。

步骤3计算每个样本的反向最近邻个数m。

步骤4计算每个样本的k个近邻的距离和dist。将该样本的序号、步骤4 计算出的dist 值和步骤3 计算出的m放入列表RNNDist 中。

步骤5计算RNNDist列表中每个对象的VValue(init)值，参考式（1），按升序排列，得到列表SortRnnDist。

步骤6取SortRnnDist 列表的第一个值对应的init 为聚类初始点。

步骤7从第一个初始点开始的聚类结束后，将已经有标签的样本从SortRnnDist 列表中删除，重复步骤6，选取下一次的聚类初始点，重复步骤7，迭代直至聚类结束。

2.3 自适应半径r

在传统的DBSCAN 算法中，Eps 在聚类过程中不能改变。如果Eps 取值太小，将会导致数据集被分割成多个簇；如果Eps 取值太大，将会出现多个簇被合并的现象。无论哪种情况，都不能对有密度变化的数据集进行正确聚类。为克服上述困难，引入以下3 个概念：

1）核心距离。对象p的核心距离ε'是使得p的ε'-领域内至少有k个对象，即ε'是使得p成为核心对象的最小半径阈值。对于数据集中的任意一个对象，每个对象p的ε'都不同。如图3 所示，五角星点的ε'=0.5；六边形点的ε'=1；三角形点的ε'=1.25。

2）ε距离。ε的取值是一个全局的参数，由用户设定，如图4 所示，取ε=1。

图4 核距比之间的关系Fig.4 Relationship of kernel’s distance radio

3）核距比。表示核心距离ε'与ε距离的比值，核距比在一定程度上可以反映数据点分布的疏密情况。

在图4 中，图4（a）和图4（b）的核距比均小于1，其中图4（a）的核距比最小，得出数据之间的密度分布紧凑；图4（b）的核距比几乎为1，数据之间的密度分布适中；图4（c）的核距比大于1，明显数据较分散。但是对于核距比大于1 的数据点，存在是噪点的可能性，需要做进一步的判断。

设置一个参数α用来与核距比作比较，α设定的大小可以对自适应半径r的调节起到伸缩作用。α越小，半径r可调整的伸缩性越大；反之，伸缩性越小。自适应半径r的判断如图5 所示。

图5 自适应半径流程Fig.5 Procedure of self-adapting radius

从图5 可以看出，r的选择有如下3 种情况：

1）数据对象的密度紧密，当核距比远小于α时，如果直接取r=ε'，那么半径r取值太小，会导致本属于同一个簇的数据点被分割成多个簇。所以，采用图5 中适当增大ε'的方法重新计算核距比，使得α落在规定区间，此时取r=ε'。

2）数据对象的密度适中，当核距比正好落在α规定区间时，直接取r=ε。因为此时ε和ε'的大小相差甚微，所以选取值较大的ε，加快聚类速度。

3）数据对象的密度稀疏，当核距比远大于α时，如果直接判断为噪点，那么可能会忽略如图2 所示的左边簇的情况。所以，判断该数据对象的ε'邻域中的每个点是否有大于等于k个未被标识的对象，若有，则说明该点附近只是密度稀疏，并不是噪点，取r=ε'；反之，则为噪点。

2.4 算法描述

通过上述初始值的选取和半径的判定，得到init和r值，然后采用密度聚类的方法进行聚类。第一次聚类结束之后，从剩余未被标记的数据样本中选出第二次聚类的初始点init′和半径r′，进行第二次聚类、迭代，直至所有数据样本被划分类别或有部分数据做噪声处理。

对于数据集X中的每个样本x，标签用cluster表示，聚类过的样本添加到visited 列表中，未被聚类的样本存放在unvisited 列表中，将聚类结果存放在数组assign中。OIR-DBSCAN 算法的流程如算法2 所示。

算法2OIR-DBSCAN 算法

输入数据集dataset

输出assign

步骤1对数据集作归一化处理。

步骤2根据算法1 计算出初始点init。

步骤3根据图5 的流程图计算出自适应半径r。

步骤4通过DBSCAN 算法，将和初始点init 属于同一类的数据样本划分出来，cluster 加1。

步骤5执行步骤2、步骤3。

步骤6用步骤4 的方法对剩余点聚类。

步骤7迭代，直至所有数据被聚类或部分数据被当作噪声处理。

2.5 参数选择

算法中k值是固定参数，取值为4，k主要用来控制核心距离ε'，进而影响半径r。参数ε人为设定。α的大小可以对自适应半径r的调节起到伸缩作用，经大量实验测试，α的取值范围是0.25～0.8。参数MinPts 和DBSCAN 算法中的MinPts 一样，用来控制核心点的判断。虽然该参数也是人为设定的参数，但经过大量实验论证，取值范围一般为3～15，且为正整数。

3 实验结果与分析

为对本文算法性能进行评估，检测其有效性，本文进行以下对比实验。对比算法包括DBSCAN 算法、OPTICS 算法和RNN-DBSCAN 算法。数据集采用人工数据集和真实数据集，人工数据集包括Compound、Pathbased、Jain、Aggregation、grid.orig；真实数据集包括iris、WBC、Thyroid、Ecoli、Pima、Vote、Vowel 等。其中人工数据集如表3 所示。

表3 人工数据集Table 3 Artificial datasets

实验环境为Inter®CoreTMi7-1065G7 CPU@1.30 GHz 1.50 GHz，内存为16 GB，编程环境为python3.8，编译器为Jupter Notebook、PyCharm。

聚类的评价指标选用调整兰德指数（ARI）［21］、归一化交互信息（NMI）［22］、同质性指标（homogeneity）、完整性指标（completeness）和同质性与完整性的调和平均（V-measure）［23］。

ARI 是调整的RI，相对RI 来说有更高的区分度。ARI 的取值范围是［-1，1］，数值越接近1 代表聚类结果越好，越接近0 代表聚类结果越差，计算公式如式（2）所示：

其中：max 表示取最大值；E表示期望。

ARI 计算公式如式（3）所示：

其中：i、j分别表示为真实簇类和预测簇类；nij表示聚类正确的样本个数；max（RI）表示如果聚类结果完全正确时的值；E[RI]表示求RI 的期望值。

NMI 是一个外部指标，通过将聚类结果与“真实”的类标签对比衡量聚类效果，如式（4）所示：

其中：k（C）是聚类结果的簇数；k（T）是真实聚类结果的簇数；ni是簇i的样本个数；nj是簇j的样本个数；ni，j是聚类结果C中属于簇i的样本与真实聚类结果T中属于簇j的样本之间的样本个数；n是数据集的样本总数。

同质性h表示每个簇只包含单一类别成员的程度；完整性c表示一个给定类的所有成员分配到单一簇的程度；V-measure 表示两者的调和平均。其中同质性和完整性如式（5）和式（6）所示：

其中：H(C|K)是给定簇。

类的条件熵如式（7）所示：

H(C)是类的熵，计算公式如式（8）所示：

其中：n表示数据集的样本总数；nc和nk分别表示属于簇c和簇k的样本数；nc，k为类c中的样本分配给簇k的数量。

V-measure 的表达式如式（9）所示：

3.1 人工数据集

本组实验用上述提及的5 个人工数据集进行测试，聚类结果如图6～图10 所示。Compound 数据集中有若干个密度不同的簇，图6 的实验结果表明，只有本文提出的OIR-DBSCAN 算法能得到正确的聚类结果，而DBSCAN 算法中由于Eps 参数的局限性，误将左上角的簇当作噪点处理，OPTICS 算法和RNN-DBSCAN 算法的聚类结果差强人意；在图7中，数据集的分布较为松散且密度分布无规律，DBSCAN 算法、OPTICS 算法和RNN-DBSCAN 算法在聚类内部簇的过程中都会将最外层的数据样本聚类进来，导致一个簇中出现了很多本不属于该簇的数据样本，而OIR-DBSCAN 算法通过对核心距离和ε距离的调整计算出合适的半径r，从而进一步得到较好的聚类结果；在图8 中，上下两个簇有较大的密度差异，DBSCAN 算法中若Eps 取值小，则上面的簇会被分割成几部分，如图8（a）所示，RNN-DBSCAN算法和OPTICS 算法在聚类过程中将一个簇分成两个，聚类效果较差，只有OIR-DBSCAN 算法能得到正确的聚类结果；在图9 中，数据样本的密度分布相对均匀，部分簇之间相连，经过聚类结果分析发现4 种算法都有不错的聚类效果，其中OIR-DBSCAN聚类结果最好，RNN-DBSCAN 算法次之，OPTICS 算法相对最差；在图10 中，簇内样本分布均匀，但两个簇的密度差异大且簇间距离很近，这种数据集最能充分体现出OIR-DBSCAN 算法的优越性，该算法针对不同密度的簇自适应地计算出不同的半径r进行聚类，得到了较好的聚类结果，而DBSCAN 算法和OPTICS 算法在聚类右下角的簇时，将离该簇最近但本属于左簇的部分数据样本聚类进来，得到了错误的聚类结果，RNN-DBSCAN 算法的聚类结果最差。

图6 4 种算法在Compound 数据集上的聚类结果Fig.6 Clustering results of four algorithms on Compound dataset

图7 4 种算法在Pathbased 数据集上的聚类结果Fig.7 Clustering results of four algorithms on Pathbased dataset

图8 4 种算法在Jain 数据集上的聚类结果Fig.8 Clustering results of four algorithms on Jain dataset

图9 4 种算法在Aggregation 数据集上的聚类结果Fig.9 Clustering results of four algorithms on Aggregation dataset

图10 4 种算法在grid.orig 数据集上的聚类结果Fig.10 Clustering results of four algorithms on grid.orig dataset

通过图6～图10 所示的可视化对比实验分析可以得到，在Aggregation 等数据集上，其中一部分算法也可以达到较好的聚类效果。但总体来说，无论是密度不均匀的数据集还是普通数据集，OIRDBSCAN 算法都能够得到很好的聚类结果。4 个聚类算法在人工数据集上性能的对比如表4 所示（粗体为最优值）。4 种算法在聚类过程中达到最优效果的具体参数取值如表5 所示。

表5 4 种算法在人工数据集上的参数值Table 5 Parameter values of four algorithms on artificial datasets

3.2 真实数据集

在人工数据集上，OIR-DBSCAN 算法表现出较好的聚类结果。为进一步验证其聚类性能，还需要在真实数据集上进行验证，UCI 数据集如表6所示。

表6 UCI 数据集Table 6 UCI datasets

在UCI 数据集中，因为高维数据集可视化难度较大，所以通过聚类评价指标ARI、NMI、homogeneity、completeness 和V-measure 进行对比，聚类评价指标的对比结果如表7 所示（粗体为最优值）。在Pima 数据集中，DBSCAN 算法的NMI 值高于OIR-DBSCAN算法0.006 9，在Vote 数据集中，DBSCAN 算法的NMI 值高于OIR-DBSCAN算法0.013 9，但从整体对比结果来看，OIR-DBSCAN 算法的ARI、NMI 等评价指标都明显高于其他聚类算法。通过比较发现，OIR-DBSCAN 算法的聚类效果最好，DBSCAN 算法和OPTICS 算法次之，RNN-DBSCAN 算法效果相对最不理想。

表7 4 种算法在UCI 数据集上的评价指标对比Table 7 Comparison of evaluation index of four algorithms on UCI dataset

4 结束语

本文提出一种优化初始点与自适应半径的密度聚类算法。将反向最近邻和相似度矩阵相结合，迭代选取每次聚类开始的初始点，该初始点即为全局密度最大的样本。优化DBSCAN 算法中Eps 全局参数，调整核心距离ε'和ε距离之间的核距比与参数α得出最终半径值r，使得密度稀疏的簇和密度稠密的簇分别对应各自适合的r值，该参数具有较好的灵活性。实验结果证明，OIR-DBSCAN 算法可以正确聚类密度不均匀的数据集，而且对高维甚至簇间有重叠的数据集也有较好的聚类能力。本文算法在聚类大规模数据集时会出现聚类时间较长的现象，下一步将从改进算法性能和提高聚类速度方向入手，以使算法的聚类效果达到最优。