基于阴影集的共享最邻近三支DBSCAN

Three-Way DBSCAN Text Clustering Based on Shadowed Sets and Shared Nearest Neighbor

摘要: 传统DBSCAN算法在处理数据时，将某些不确定的数据强制划分到某一类中往往容易带来决策风险。针对此问题，提出了基于阴影集的共享最邻近三支DBSCAN算法。该算法利用三支决策思想，将核心点划分到核心域中，对于非核心点引入阴影集理论，计算样本的隶属度，将样本划分到核心域或边界域中，并通过共享最邻近算法进一步细化边界域中的样本划分，从而提升聚类的准确性和鲁棒性。该算法应用在文本分析领域，通过实验对比分析，验证了该算法具有较好的性能，提高了文本聚类的准确性。

Abstract: The traditional DBSCAN algorithm, when processing data, often faces decision risks by forcing certain uncertain data points into a specific cluster. A three-way DBSCAN algorithm based on shadowed sets and Shared Nearest Neighbor is proposed to address this issue. This algorithm utilizes the three-way decision-making approach to classify core points into the core region. For non-core points, the theory of shadow sets is introduced to calculate the membership degree of the samples, categorizing them into either the core region or boundary region. The Shared Nearest Neighbor algorithm is then applied to further refine the classification of samples within the boundary region, thereby enhancing the accuracy and robustness of clustering. Applied in text analysis, experimental comparative analysis has verified that this algorithm demonstrates better performance and improves the accuracy of text clustering.

1. 引言

聚类分析是数据挖掘和机器学习中的一种常用方法，其目标是将数据集中的样本按照一定的规则分成若干个簇，使得同一簇内的样本具有较高的相似性，而不同簇之间的样本相似性较低[1]，从而揭示数据的内在结构和模式，为进一步的数据分析和决策提供依据。在当今信息爆炸的时代，文本数据的数量和复杂性呈现指数级增长，这对数据挖掘和知识发现提出了严峻挑战。文本聚类作为自然语言处理和数据挖掘的重要技术手段，能够有效地将大量无结构文本数据自动归类，从而在信息检索[2]、主题检测[3]、情感分析[4]等领域中发挥重要作用。

DBSCAN [5] [6]作为一种密度聚类算法，因其能够识别任意形状的簇且具备处理噪声数据的能力，已经成为经典的聚类算法之一。然而，DBSCAN在处理具有模糊边界或重叠簇时的局限性显而易见。由于其硬聚类的刚性，即将每个数据点严格划分为簇或噪声，常常在处理这些复杂数据时导致次优的结果[7]。为解决这一问题，一些改进方法引入了更具灵活性的策略。例如，基于模糊理论的FN-DBSCAN算法通过为每个数据点分配不同的隶属度，使其同时属于多个簇，从而有效处理模糊边界问题[8]。基于共享最近邻的SNN-DBSCAN算法通过结合最近邻算法的思想，将共享最近邻的概念引入密度计算，增强了处理重叠簇和边界模糊的能力[9]。基于三支决策模型的3W-DBSCAN通过引入边界域，允许对不确定数据点采取“延迟决策”的方式，避免了传统硬分类方法中过度刚性的分类决策，从而有效处理数据的不确定性和模糊性[10]。

然而，以上聚类算法大多仅停留在对边界点的分类优化，如何进一步细化边界点的划分，并提升整体聚类算法的鲁棒性仍是一个挑战。

由Witold Pedrycz等[11]-[14]提出的阴影集，广泛应用于处理模糊边界和不确定性数据的领域。它通过引入𝛼阈值将模糊集的多值逻辑演变为$\left\{1,\left[0,1\right],0\right\}$ 的三值逻辑，降低了隶属度带来的冗余信息。Jiang等[15]利用阴影集提出了新的聚类集成方法S-M3WCE。Zhang等[16]提出了一种改进的基于参数决策理论阴影集(RFKM-DTSS)的粗糙模糊k均值聚类方法，来使聚类边界合理化。在阴影集中，只有隶属度在区间$\left[\alpha ,1-\alpha \right]$ 内的元素保留了模糊性，其余的元素都被明确分类，阴影集不仅保留了模糊集的本质，还简化了处理并增强了结果的解释性。目前关于阴影集理论与DBSCAN算法相结合进行三支聚类的研究还相对较少，特别是应用阴影集理论优化DBSCAN算法以解决模糊边界问题研究领域仍处于初步阶段。

因此，本文提出了基于阴影集的共享最邻近三支DBSCAN算法，该算法在DBSCAN二支聚类结果基础上将核心点划分到核心域中，对于非核心点引入阴影集理论，通过计算样本的隶属度，将样本划分到核心域或边界域中，并通过共享最邻近(SNN)算法进一步细化边界域中的样本划分。这一方法不仅增强了对模糊边界的处理能力，还通过细化边界域的划分，提高了聚类结果的准确性，实验结果表明，该算法在文本聚类任务中具有较好的性能。

2. 相关工作

本小节分别回顾了DBSCAN、三支决策和阴影集的部分基础知识。

2.1. DBSCAN

DBSCAN [5] [6]是一个经典的密度基聚类算法。它将簇定义为密度相连点的最大集合，能够有效地识别数据中的类簇结构，并且能够自动处理噪声数据点。该算法能够将高密度区域划分为簇，并能在含有噪声的空间数据库中发现任意形状的聚类。

DBSCAN通过设定邻域半径Eps和最小点数MinPts，首先标记数据集中所有点为未访问状态，然后依次访问每个点，若点的邻域内包含的点数不少于MinPts，则将其标记为核心点，并扩展其邻域内的点加入同一个簇，否则标记为噪声点。核心点的邻域内所有点会被进一步检查和扩展，重复此过程直至所有点被访问并归类，最终形成类簇和噪声点的划分。

然而，DBSCAN在处理模糊边界时缺乏灵活性，并且对Eps和MinPts参数的选择高度敏感，可能导致聚类结果不稳定[7]。针对DBSCAN算法的局限性，研究者们提出了多种改进方法。主要的改进方向包括：

1) 参数自适应选择：利用不同的优化技术，来动态确定聚类所需的关键参数(Eps和MinPts)，以更好地适应数据集的分布特征[17]-[19]。

2) 模糊聚类：引入模糊理论，为数据点分配不同的隶属度，使每个点可以同时属于多个簇，从而有效应对模糊边界问题[8] [20]。

3) 三支聚类：该方法引入边界域，允许对不确定数据点采取“延迟决策”的方式，有效缓解了传统硬分类方法的过度刚性，改善了数据处理的灵活性[10] [21]。

2.2. 三支决策

在经典的二支决策聚类中，对象和类之间只有两种关系：对象属于类或不属于类。清晰边界的要求有利于分析结果，却不能充分显示数据集中的不确定性信息[1]。为了解决信息不确定性问题，Yao [22] [23]基于粗糙集提出的的三支决策理论，通过将决策过程分为接受、拒绝和延迟三种类型，提供了一种处理不确定性和模糊性的方法。

假设一个有限非空对象集合X和一个有限的标准集C。根据标准集C，可以将整体划分成3个两两互不相交的区域：POS，BND，NEG。且满足如下标准：

$\begin{array}{l}\left(1\right)POS\cap BND=\varnothing ,POS\cap NEG=\varnothing ,BND\cap NEG=\varnothing \\ \left(2\right)POS\cup BND\cup NEG=X\end{array}$ (1)

其中POS域，BND域，NEG域分别表示正域(接受决策)、边界域(延迟决策)和负域(拒绝决策)。

Yu [24] [25]将三支决策理论结合到聚类中提出的三支聚类框架，旨在将数据点划分为核心域、边界域和琐碎域，从而更有效地处理数据中的不确定性和模糊性。近年来，三支聚类引起了大量的研究，并开发了许多三支聚类算法。

三支聚类的聚类结果用二元集合表示$C=POS\left(C_i\right),BND\left(C_i\right)$ ，$POS\left(C_i\right)$ 表示第i类的核心域，对象肯定属于该类，$BND\left(C_i\right)$ 表示第i的边界域，对象不确定属于该类。三支聚类的类簇满足如下性质：

$\begin{array}{l}POS\left(C_i\right)\ne \varnothing ,i=1,2,\cdots \\ POS\left(C_i\right)\cap POS\left(C_j\right)=\varnothing ,i\ne j\\ {\displaystyle {\cup }_{i=1}^k\left(POS\left(C_i\right)\cup BND\left(C_i\right)\right)}=X_i\end{array}$ (2)

然而，目前的三支决策聚类算法大多仅停留在对边界点的分类优化，如何进一步细化边界点的划分，并提升整体聚类算法的鲁棒性仍是一个挑战。

2.3. 阴影集

阴影集[11]-[14]是一种特殊的三支决策模型。对于阴影集来说，有3种量化级别：$\left\{1,\left[0,1\right],0\right\}$ ，即将模糊集转化成阴影集的三值逻辑，依次对应隶属度为1，0和隶属度不确定的区域。阴影集结构如图1所示。

Figure 1. Shadow set structure

图1. 阴影集结构

具体而言，如果对象x隶属度${\mu }_A\left(x\right)\le \alpha$ 通过降低操作将隶属度降低为0，该区域定义为降低区域(o₁)。如果对象x隶属度${\mu }_A\left(x\right)\ge 1-\alpha$ 通过提升操作将隶属度提升为1，该区域定义为提升区域(o₃)。如果对象x隶属度$\alpha <{\mu }_A\left(x\right)<1-\alpha$ 则变化区域定义为阴影区域(o₂)。

阴影集的一个重要问题是阈值的确定，Pedrycz在[11]为了计算最优阈值，当隶属度值的集合是连续函数时$\alpha$ 的取值应满足使式(3)取得最小值：

$V=\left|{\displaystyle {\int }_{{\mu }_A\left(x\right)\le \alpha }{\mu }_A\left(x\right)\text{d}x}+{\displaystyle {\int }_{{\mu }_A\left(x\right)\ge 1-\alpha }\left(1-{\mu }_A\left(x\right)\right)\text{d}x}-{\displaystyle {\int }_{\alpha <{\mu }_A\left(x\right)<1-\alpha }\text{d}x}\right|$ (3)

当处理隶属度值的集合而不是连续函数时$\alpha$ 的取值应满足使式(4)取得最小值：

$V=\left|{\displaystyle \sum _{{\mu }_A\left(x\right)\le \alpha }{\mu }_A\left(x\right)}+{\displaystyle \sum _{{\mu }_A\left(x\right)\ge 1-\alpha }\left(1-{\mu }_A\left(x\right)\right)}-\text{card}\left\{x_i\in U|\alpha <{\mu }_A\left(x\right)<1-\alpha \right\}\right|$ (4)

其中card{·}代表集合中对象的数量。

目前关于阴影集理论与DBSCAN算法相结合进行三支聚类的研究还相对较少。在这项工作中，我们引入将阴影集理论优化了现有的DBSCAN算法进行三支聚类。

3. 基于阴影集的共享最邻近三支DBSCAN

3.1. 隶属度和相似度设计

为解决传统DBSCAN对模糊和不确定数据处理不足的问题，设计隶属度函数，用于量化每个数据点对不同区域的归属程度，通过计算隶属度，数据点不再被简单地划分为核心点或噪声点，而是进一步细化为核心域、边界域和噪声域。

图2为带有一个噪声点的数据分布，由图2可以看出，噪声点和x₁到类中心的距离相等，如果隶属度函数只按照样本点到类中心的距离作为评价指标，将会赋予x₁和噪声点相同的隶属度，显然不符合实际。因此，为了度量图2中对象隶属度之间的差异，本文借鉴文献[26]结合样本到类中心的距离和样本周围的紧密度的隶属度函数设计得到每个簇中样本点的隶属度。本文隶属函数定义为：

$D_i=\frac{1}{K}{\displaystyle \sum _{x_j\in N_k\left(x_i\right)}\Vert x_i-x_j\Vert }$ (5)

$u\left(x_i\right)={\left(1-\beta \frac{d_i}{\underset{j}{\max }\left(d_j\right)+0.0001}-\left(1-\beta \right)\frac{D_i-\underset{j}{\min }\left(D_j\right)}{\underset{j}{\max }\left(D_j\right)-\underset{j}{\min }\left(D_j\right)+0.0001}\right)}^m$ (6)

其中，$\beta \in \left(0,1\right)$ ，m的取值范围为$\left\{0.1,0.2,0.3,\cdots ,1.0\right\}$ ，$N_k\left(x_i\right)$ 为$x_i$ 的k个邻近样本的集合，$d_i$ 为$x_i$ 到类中心之间的距离。本文$\beta =0.7,m=0.2$ 。

Figure 2. Data distribution chart

图2. 数据分布图

为了更好地细化对文本数据边界点的划分，共享最邻近相似度通过计算每个点与其他点共享的最近邻个数，增强了对点与点之间关系的度量。本文相似度定义为：

$SNN\left(P,Q\right)=\left|N_k\left(P\right)\cap N_k\left(Q\right)\right|$ (7)

其中，$N_k\left(P\right)$ 和$N_k\left(Q\right)$ 是点P和Q的k最近邻集合，本文k = 6。

3.2. 算法思想

本文提出了一种基于阴影集的共享最邻近三支DBSCAN聚类算法(SS3W-DBSCAN)。该算法的核心思想在DBSCAN二支聚类结果基础上将核心点划分到核心域中，对于非核心点引入阴影集理论，通过计算样本的隶属度，将样本划分到核心域或边界域中。本文通过引入阴影集理论，允许不确定的数据点保留在边界域中，避免强制归类。之后，利用共享最近邻(SNN)方法对这些边界点进行进一步细化，确保文本的正确归类。算法具体步骤如下：

算法SS3W-DBSCAN

输入：数据集Data，Eps，MinPts，K最邻近 输出 $C_j=\left(C_j^p,C_j^B\right)$

步骤1：将数据集输入到DBSCAN算法中进行初始聚类，得到初始聚类结果$C_i$ ，$i=1,2,3,\cdots ,k$ 。

步骤2：对于噪声点，将噪声点归类到离它最近的核心点的类簇中的边界域。

步骤3：根据式(6)和式(4)分别计算各类簇的样本点隶属度和最优阈值${\alpha }_i$ ，$i=1,2,3,\cdots ,k$ 。

步骤4：对于类簇$C_j$ 中任意点p，如果点p是核心点，则将点p划分到$C_j$ 的核心域$C_j^p$ 之中。否则，获得p点的隶属度${\mu }_j\left(p\right)$ ，若${\mu }_j\left(p\right)\ge 1-{\alpha }_j$ 则把点p划分到$C_j$ 的核心域$C_j^p$ 之中。若${\mu }_j\left(p\right)<1-{\alpha }_j$ 则把点划分边界域$C_j^B$ 之中。

步骤5：对于划分到类$C_j$ 中边界域中的样本点，由于可能是其他类簇的边界域中的对象，需要进一步处理，处理策略如下：对于$p\in C_j^B$ ，得到点p的$eps$ 邻域$N_{eps}p$ ，若点x为p的$eps$ 邻域中的点，即$x\in N_{eps}p$ ，有$x\in C_i,j\ne i$ ，则把p也划分到$C_i$ 的边界域中，即$p\in C_i^B$ 。 步骤6：根据式(7)计算边界点与核心点之间的SNN相似度。如果某个边界点与簇内某个核心点的相似度大于$\frac{K}{2}$ ，则该边界点归入该核心点所在簇的核心域中；反之，该点将保留在边界域中。细化处理完成后，生成最终的三支聚类结果。

4. 实验和结果分析

为了验证本文算法的有效性和先进性，首先，将SS3W-DBSCAN算法与3W-DBSCAN算法[10]进行对比，使用三支聚类评价指标进行评估，三支聚类评价指标在4.2小节中已给出详细定义。然后，将SS3W-DBSCAN算法对文本集进行文本聚类，使用ARI、NMI、ACC指标进行评估。

4.1. 实验设置

本文在常用的人工数据集和UCI数据集上将本文所提算法与其他聚类算法进行对比，数据集的信息如表1所示，其中1~5为人工数据集，6~10为UCI数据集。

Table 1. Data set

表1. 数据集

序号	数据集	类个数	维度	样本数
1	Flame	2	2	240
2	Aggregation	7	2	788
3	Square	4	2	1000
4	R15	15	2	600
5	Cure	3	2	2000
6	Iris	3	4	150
7	Wine	3	13	178

续表

8	Seeds	3	7	197
9	Ecoli	5	7	210
10	Heart	4	13	303

4.2. 评价指标

4.2.1. 硬聚类评价指标

1) 调整兰德系数(ARI)是一种用于评估聚类结果的外部评价指标。其取值范围在[−1, 1]之间，其中1表示完全一致的聚类结果，值越接近1表示聚类效果越好。

$\text{ARI}=\frac{{\displaystyle \sum _{i,j}\left(\begin{array}{c}{n}_{ij}\\ 2\end{array}\right)}-\left({\displaystyle \sum _i\left(\begin{array}{c}{a}_i\\ 2\end{array}\right)}\times {\displaystyle \sum _j\left(\begin{array}{c}{b}_j\\ 2\end{array}\right)}\right)/\left(\begin{array}{c}n\\ 2\end{array}\right)}{\frac{1}{2}\left({\displaystyle \sum _i\left(\begin{array}{c}{a}_i\\ 2\end{array}\right)}+{\displaystyle \sum _j\left(\begin{array}{c}{b}_j\\ 2\end{array}\right)}\right)-\left({\displaystyle \sum _i\left(\begin{array}{c}{a}_i\\ 2\end{array}\right)}\times {\displaystyle \sum _j\left(\begin{array}{c}{b}_j\\ 2\end{array}\right)}\right)/\left(\begin{array}{c}n\\ 2\end{array}\right)}$ (8)

其中，n表示数据集中的样本总数，$n_{ij}$ 表示真实标签为${\alpha }_i$ 且聚类结果为$b_j$ 的样本数。

2) 标准化互信息(NMI)是度量聚类结果和真实标签的相似程度的外部评价指标。其取值范围在[0, 1]之间，值越高表示越相似，聚类效果越好。

$\text{NMI}=\frac{2\times I\left(U,V\right)}{H\left(U\right)+H\left(V\right)}$ (9)

其中，$I\left(U,V\right)$ 是聚类结果U和真实标签V之间的互信息，$H\left(U\right)$ 是聚类结果U的熵，$H\left(V\right)$ 是真实标签V的熵。

3) 准确度(ACC)可以衡量聚类结果的准确性。其取值范围[0, 1]之间，1表示聚类结果与真实标签完全一致，值越高聚类效果越好。

$\text{ACC}=\frac{1}{n}{\displaystyle \sum _{i=1}^k{C}_i}$ (10)

其中，n表示数据集中的样本总数，$C_i$ 表示类簇i与真实标签一致的对象个数，k表示类簇的个数。

4.2.2. 三支聚类评价指标

由于硬聚类指标无法评估类簇的核心域和边界域之间的关系，而三支聚类在处理模糊边界以及提供更丰富的样本与簇关系信息方面具有显著优势。因此本文也使用了三支聚类指标进行评估。

第一个评价指标是Maji等[27]于2007年提出，其公式定义为：

$\gamma =\frac{1}{n}{\displaystyle \sum _{j=1}^k\left|C_j^p\right|}$ (11)

其中，n表示数据集中的样本总数，k表示类簇的个数，$\left|C_j^p\right|$ 表示$C_j$ 核心域中对象个数。$\gamma$ 表示所有类簇的核心域的平均质量，其值越高表示聚类效果越好。

第二个评价指标是Zhang等[28]于2019年提出，其公式定义为：

$\alpha =\frac{1}{k}{\displaystyle \sum _{j=1}^k\frac{\left|C_j^p\right|}{\left|C_j^p\right|+\left|C_j^b\right|}}$ (12)

${\alpha }^{\ast }=\frac{{\displaystyle \sum _{j=1}^k\left|C_j^p\right|}}{{\displaystyle \sum _{j=1}^k\left(\left|C_j^p\right|+\left|C_j^b\right|\right)}}$ (13)

其中，$\left|C_j^b\right|$ 表示$C_j$ 边界域中对象个数，$\alpha$ 和${\alpha }^{*}$ 分别表示所有类簇的平均质量和整体质量，其值越高表示聚类效果越好。

4.3. 三支聚类实验

本小节使用3W-DBSCAN算法与本文所提出的SS3W-DBSCAN算法对10个常用数据集进行三支聚类，其中，在人工数据集上的参数设置如表2所示，聚类效果如图3~7所示。在UCI数据集和人工数据集进行聚类得到的三支聚类结果评价指标评估得分如表3所示。

图3~7为SS3W-DBSCAN算法3W-DBSCAN算法在人工数据集中的聚类结果，从图中可以看出，与3W-DBSCAN聚类结果相比，SS3W-DBSCAN算法进一步细化边界点的划分，减少了样本在边界区域的过度分配，在保留模糊信息的同时，也能够避免必要的确定性信息的丢失。

通过表3数据可知，SS3W-DBSCAN算法在识别核心点和边界点时更加准确，使得聚类结果更加精确，特别是在处理类间差异明显的数据集时优势尤为明显，有效地减少了样本点在边界区域的过度分配，降低了不确定性的影响，显著提升了在三支聚类任务中的表现。

Table 2. Parameter settings for synthetic datasets

表2. 人工数据集参数设置

数据集	Flame	Aggregation	Square	R15	Cure
Eps	1.550	2.737	3.420	0.772	0.267
MinPts	13	31	126	32	155

(a) 3W-DBSCAN (b) SS3W-DBSCAN

Figure 3. Clustering results of flame

图3. Flame聚类结果

(a) 3W-DBSCAN (b) SS3W-DBSCAN

Figure 4. Clustering results of aggregation

图4. Aggregation聚类结果

(a) 3W-DBSCAN (b) SS3W-DBSCAN

Figure 5. Clustering results of square

图5. Square聚类结果

(a) 3W-DBSCAN (b) SS3W-DBSCAN

Figure 6. Clustering results of R15

图6. R15聚类结果

(a) 3W-DBSCAN (b) SS3W-DBSCAN

Figure 7. Clustering results of cure

图7. Cure聚类结果

Table 3. Three-way clustering evaluation results

表3. 三支聚类评价结果

数据集	$\gamma$		$\alpha$		${\alpha }^{*}$
	3W-DBSCAN	SS3W-DBSCAN	3W-DBSCAN	SS3W-DBSCAN	3W-DBSCAN	SS3W-DBSCAN
Flame	0.550	0.829	0.522	0.794	0.522	0.809
Aggregation	0.473	0.722	0.331	0.693	0.473	0.722
Square	0.530	0.796	0.526	0.764	0.526	0.764
R15	0.672	1.000	0.672	1.000	0.672	1.000
Cure	0.598	0.728	0.832	0.886	0.598	0.728
Iris	0.540	0.860	0.526	0.854	0.523	0.854
Wine	0.500	0.854	0.351	0.795	0.489	0.792
Seeds	0.519	0.857	0.494	0.799	0.495	0.800
Ecoli	0.476	0.878	0.388	0.883	0.476	0.878
Heart	0.535	0.772	0.504	0.695	0.513	0.696

4.4. 文本聚类实验

本文选用了THUCNews数据集和SogouCS数据集，THUCNews由清华大学自然语言处理实验室收集和发布包含74万篇新闻文本，涵盖14个类别，选取体育、科技、教育、家居、财经5个类别，每个类240篇，共1200篇文档。SogouCS数据集由搜狐公司推出包含270多万篇新闻文本涵盖社会、经济、科技等多个类别，选取IT、健康、教育、旅游、体育5个类别，1210篇文档，其中，IT、健康每个类245篇，其余每个类240篇。关于文本数据集的详细信息如表4所示。

Table 4. Text dataset

表4. 文本数据集

数据集	类别数	具体类别	数据总量
THUCNews	5	体育、科技、教育、家居、财经	1200
SogouCS	5	IT、健康、教育、旅游、体育	1210

4.4.1. 文本关于类别数量变化实验

本次实验目的是测试聚类效果关于文档类别数量的变化。对比实验分成两类：DBSCAN算法、本文提出的SS3W-DBSCAN算法，使用THUCNews数据集，分成五组试验：第一组实验的数据集包含5类，每一类100篇共500篇文档；第二组实验的数据集包含6类，每一类100篇共600篇文档；以此类推，第五组实验的数据集是9类共900篇文档。每组实验均采用BERT模型处理文档向量化，使用去噪自编码器进行降维，每组实验过程完全一致。ACC指标随类别数量变化如图8所示。

Figure 8. ACC metrics vary with the number of categories

图8. ACC指标随类别数量变化图

从实验结果可以知道文本聚类的ACC值会随着文本类别的增加而降低，当类别数较小时，ACC值很高，当类别数增加时，ACC值逐渐降低。使用SS3W-DBSCAN算法后，聚类效果更好且稳定，在聚类类别小于10时，文档聚类的ACC值一直超80个百分点。

4.4.2. 文本综合对比实验

本次实验目的是验证SS3W-DBSCAN算法的文本聚类效果。对比实验分成五类：DBSCAN算法、FDBSCAN算法[29]、KANN-DBSCAN算法[18]、3W-DBSCAN算法[10]和本文提出的SS3W-DBSCAN算法。实验均采用BERT模型进行文本向量化，使用去噪自编码器进行降维，实验过程完全一致，仅聚类算法不同。

实验结果如表5~7所示，SS3W-DBSCAN算法在THUCNews和SogouCS数据集上的各项指标均优于对比算法，其ACC指标分别达到0.898和0.901，NMI和ARI指标也显著提升。相比经典DBSCAN算法，ACC指标分别提升了16.9%和14.1%，相比3W-DBSCAN算法，也有显著提升，体现了更高的聚类精度。无论是在较小规模的THUCNews数据集还是在较大规模的SogouCS数据集上，SS3W-DBSCAN均表现出了较好的性能。

Table 5. ACC comparison on text datasets

表5. 文本数据集上的ACC对比

Model	数据集
	THUCNews	SogouCS
	ACC	ACC
DBSCAN	0.729	0.675
FDBSCAN	0.809	0.777
KANN-DBSCAN	0.822	0.821
3W-DBSCAN	0.871	0.881
SS3W-DBSCAN	0.898	0.901

Table 6. NMI comparison on text datasets

表6. 文本数据集上的NMI对比

Model	数据集
	THUCNews	SogouCS
	NMI	NMI
DBSCAN	0.719	0.707
FDBSCAN	0.800	0.778
KANN-DBSCAN	0.809	0.785
3W-DBSCAN	0.816	0.828
SS3W-DBSCAN	0.842	0.848

Table 7. ARI comparison on text datasets

表7. 文本数据集上的ARI对比

Model	数据集
	THUCNews	SogouCS
	ARI	ARI
DBSCAN	0.655	0.652
FDBSCAN	0.728	0.703
KANN-DBSCAN	0.747	0.727
3W-DBSCAN	0.781	0.798
SS3W-DBSCAN	0.839	0.803

5. 结束语

本文提出的基于阴影集的共享最邻近三支DBSCAN聚类算法(SS3W-DBSCAN)，有效解决了传统DBSCAN在处理文本数据时存在的模糊边界和不确定性问题。通过引入阴影集理论，避免了将不确定的边界点强制归类的风险；而与共享最邻近算法的结合，进一步细化了边界点的划分，提升了文本聚类的准确性和鲁棒性。实验结果表明，SS3W-DBSCAN在不同文本数据集上的表现优于传统DBSCAN算法。接下来研究可以考虑进一步优化算法的计算效率，降低复杂度，以便更好地适应更多应用场景。

基金项目

哈尔滨师范大学双一流-提高人才培养质量项目(1504120015)；哈尔滨师范大学计算机科学与信息工程学院教育教学改革项目(JKYJGY202205)。

NOTES

^*通讯作者。