基于三支决策的密度聚类算法

Density Based Spatial Clustering of Application with Noise Based on Three-Way Decision

摘要: 三支聚类使用核心域，边界域和琐碎域三个集合来表示类簇，将确定的元素放入核心域中，不确定的元素放入边界域中延迟决策，降低了决策风险。本文将含有噪声的基于密度的聚类算法(Density Based Spatial Clustering of Application with Noise, DBSCAN)与三支聚类进行结合，利用数学形态学中的腐蚀和膨胀思想，用自然最近邻算法定义了一个结构算子，对二支聚类的结果通过收缩和膨胀得到核心域和边界域。在UCI数据集和Shape数据集上的实验结果显示，该方法可以有效降低DBI的值，同时提高ACC和AS的值。

Abstract: Three-way clustering uses three sets of core region, boundary region and trivial region to represent the clusters. The determined elements are put into the core region, while the uncertain elements are put into the boundary region to delay the decision, thus reducing the decision risk. In this paper, DBSCAN (Density Based Spatial Clustering of Application with Noise) is combined with the three-way clustering, and a structural operator is defined by using the natural nearest neighbor algorithm based on the corrosion and expansion ideas in mathematical morphology. The core region and boundary region are obtained by shrinking and expanding the results of the two-way clustering. Experimental results on UCI datasets and shape datasets show that this method can effectively reduce the value of DBI and improve the value of ACC and AS.

1. 引言

聚类作为一种无监督的学习方式，广泛应用于图像处理 [1]、社会网络 [2] 等领域。简单来说，聚类就是将数据集划分成多个不同的类簇，使得同类簇中的数据点相似性较高，不同类簇中的数据点相似性较低。按聚类原理，目前流行的聚类算法可分为基于密度聚类、基于层次聚类、基于网格聚类、基于划分聚类、基于模型聚类五种 [3]。DBSCAN (Density Based Spatial Clustering of Application with Noise) [4] 就是基于密度的聚类算法，它可以在含有噪声的数据中识别出任意形状的类簇，在医学诊断 [5]、目标检测 [6] 等领域广泛应用。

传统聚类算法都属于硬聚类，聚类结果中对象要么属于一个类，要么不属于一个类，类簇之间有清晰的边界，但在处理不确定信息时，如果强制将某个对象划分到类簇中，会带来较高决策风险，降低聚类精度。为了解决传统聚类方法存在的问题，很多新的聚类方法被提出，Lingras [7] 提出粗糙聚类方法，用粗糙集的正域、负域和边界域来表示聚类结果。Yao [8] 等人用区间集来表示聚类结果中的一个类。Yu [9] [10] [11] 将三支决策引入聚类中，提出三支聚类的方法，Wang和Yao等人 [12] 提出了基于三支聚类的CE3理论，Wang等人 [13] 融合了k-means算法和三支决策理论，提出了三支k-means算法，Yang [14] 等人用复杂网络来分析三支决策文章中的数据集，构建了科学合作网络、大学合作网络、科学论文网络和关键词网络，分别揭示了作者、单位、论文以及关键词之间的关系，并解答了三支决策的相关问题。

最近，Yu [15] 等人提出了基于3W-DBSCAN算法，通过改进相似度的计算获得硬聚类结果，进而进行三支聚类。本文利用数学形态学中的腐蚀和膨胀思想，对DBSCAN获得的硬聚类结果，采用基于样本的自然最近邻域对其进行收缩和膨胀得到三支聚类的核心域与边界域，将不确定的元素划分到边界域中延迟决策，待信息充分时再做决策，以此来降低决策风险。仿真实验也验证了该方法的有效性和可行性。

2. 相关工作

2.1. 三支决策聚类

2010年，Yao [16] [17] 等人提出三支决策理论，核心思想是将研究对象分为正域、负域、边界域，使其更符合实际生活中人们认知的一种决策模式，三个域分别对应三种决策规则：接受、拒绝以及不承诺规则。相比于二支决策，三支决策能够有效降低信息不充分时的决策风险。

三支决策理论提出以来，广受各领域关注，刘强 [18] 等人提出基于 $\epsilon$ 邻域的三支决策聚类的方法。Yu [19] 等人提出用三支决策来检测和完善复杂网络中的重叠区域。Zhang [20] 等人建立了一个动态的三支决策模型。

三支聚类用 $Co\left(C\right)$ 、 $Fr\left(C\right)$ 、 $Tr\left(C\right)$ 三个集合来表示一个类簇，即核心域、边界域和琐碎域。其中核心域中的元素确定属于类C，边界域中的元素可能属于类C，琐碎域中的元素确定不属于类C。结果表示如下：

$CS=\left\{\left\{Co\left(C_1\right),Fr\left(C_1\right)\right\},\cdots ,\left\{Co\left(C_k\right),Fr\left(C_k\right)\right\}\right\}$

式中这三个集合满足如下性质：

$CS=\left\{\left\{Co\left(C_1\right),Fr\left(C_1\right)\right\},\cdots ,\left\{Co\left(C_k\right),Fr\left(C_k\right)\right\}\right\}$.

式中这三个集合满足如下性质：

1) $Co\left(C_i\right)\ne \varnothing ,i=1,2,\cdots ,k$

2) ${\displaystyle \underset{i=1}{\overset{k}{\cup }}\left(Co\left(C_i\right)\cup Fr\left(C_i\right)\right)}=U$

3) $Co\left(C_i\right)\cup Fr\left(C_i\right)\cup Tr\left(C_i\right)=U$

性质1) 表示 $Co\left(C\right)$ 不为空集，即每个类中至少要有一个对象；

性质2) 确保集合U中每个对象至少被划分到一个类中；

性质3) 确保任何一个类簇的三个集合的并集为U。

2.2. DBSCAN算法

DBSCAN是一种典型的基于密度的聚类算法，其核心思想 [21] 是用一个点的 $\epsilon$ 邻域内的邻居点个数来衡量该点所在空间的密度，优点是聚类时不需要事先确定类簇的个数。DBSCAN算法的主要定义如下：

定义1 (Eps邻域)：给定空间中的一点p，p的Eps邻域点集为以p为中心，Eps为半径的区域内包含样本点的集合，即

$N_{Eps}\left(p\right)=\left\{q\in D|dist\left(p,q\right)\le Eps\right\}$ (1)

其中：D为样本数据集， $dist\left(p,q\right)$ 为点p和点q之间的距离。

定义2 ( $Minpts$ 密度阈值)：形成一个高密度区域时，Eps邻域内至少需要的点的个数。

DBSCAN算法步骤如下：

2.3. 自然最近邻

传统最近邻算法主要是k最近邻算法和 $\epsilon$ 最近邻算法，k最近邻算法中每个数据点都有k个元素， $\epsilon$ 最近邻算法中每个数据点有相同的邻域半径 $\epsilon$，但这两种方法都需要进行参数的选取，参数设置准确程度会直接影响算法结果。为此，我们采用自然最近邻居算法，自然最近邻居 [22] 不同于传统的近邻算法，它不需要邻域参数，因而避免了人为因素对算法结果的影响，有如下定义：

定义1 (最近邻)： $N{N}_r\left(x_i\right)$ 表示样本点 $x_i$ 的r最近邻，r由自然最近邻搜索算法自动产生。

定义2 (逆近邻)： $RN{N}_r\left(x_i\right)$ 表示样本点 $x_i$ 的r逆最近邻：

$RN{N}_r\left(x_i\right)=\{x_j\in X|x_i\in N{N}_r\left(x_j\right),i\ne j\}$ (2)

定义3 (自然最近邻)： $NNN\left(x_i\right)$ 表示样本点

$x_i$ 的自然最近邻：

$NNN\left(x_i\right)=\left\{x_j\in X|x_i\in N{N}_r\left(x_j\right),x_i\in RN{N}_r\left(x_i\right)\right\}$ (3)

定义4 (自然邻居特征值 $su{p}_k$ )：当所有的样本点都有逆近邻或者逆近邻个数为0的样本点不变时，自然近邻搜索过程到达自然稳定状态，此时的搜索次数称为自然特征值，记为

$su{p}_k=\{r|\forall x\exists y\left(y\ne x\cap x\in N{N}_r\left(y\right)\right)\}$ (4)

2.4. 数学形态学

数学形态学(Mathematical Morphology)由Matheron和Serra提出 [23]，是图像处理中应用最为广泛的技术之一，主要用于从图像中提取对表达和描述区域形状有意义的图像分量，使后续的识别工作能够抓住目标对象最为本质的形状特征。其基本思想是用具有一点形态的结构元素去度量和提取图像中对应形状以达到图像分析和识别的目的 [24]。Bloch [25] 将数学形态学与粗糙集联系起来，下近似对应腐蚀操作，上近似对应膨胀操作，在此我们引入腐蚀和膨胀操作，有如下定义：

定义1 (腐蚀)：用集合B来腐蚀集合A，记作 $A\Theta B$ ：

$A\Theta B=\left\{x|\left(B\right)x\subseteq A\right\}$ (5)

其中B也称为结构元素， $\left(B\right)x$ 表示B平移x后得到的新集合，由上式可知，腐蚀可以使目标区域范围变小，其实质是造成图像的边界收缩，可以用来去除没有意义的目标物。

定义2 (膨胀)：用结构算子B来膨胀A，记作 $A\oplus B$ ：

$A\oplus B=\left\{x|\left(\hat{B}\right)x\cap A\ne \varnothing \right\}$ (6)

其中集合B也称为结构元素， $\left(\hat{B}\right)x$ 表示B反射平移x后得到的新集合，由上式可知，膨胀会使目标边界向外部扩张，作用是用来填补目标区域中某些空洞以及消除包含在目标区域中的小颗粒噪声。

3. 基于三支决策的密度聚类算法

DBSCAN硬聚类的结果包括了噪声数据，因此在进行三支聚类的时候，应该将噪声数据单独进行处理，首先给出如下定义：

定义1：设 $\left\{C_1,C_2,\cdots ,C_k\right\}$ 是非噪声集合， $x_j\in C_i$， $x_t\in NN{N}_{nb}\left(x_j\right)$， $x_j$ 的平均自然最近邻居距离 $avg\left(x_j\right)=\frac{1}{nb\left(x_j\right)}{\displaystyle \underset{t=1}{\overset{nb\left(x_j\right)}{\sum }}d\left(x_t,x_j\right)}$，类 $C_i$ 的平均自然最近邻距离为 $avg\left(C_i\right)=\frac{1}{\left|C_i\right|}{\displaystyle \underset{j=1}{\overset{\left|C_i\right|}{\sum }}avg\left(x_j\right)}$。

定义2：令 $Allpos={\displaystyle \underset{i=1}{\overset{k}{\cup }}pos\left(C_i\right)}$ 为所有核心点的集合，则有如下定义：

$NCN\left(x\right)=y\leftarrow \arg \min d\left(x,y\right),y\in Allpos$

三支DBSCAN算法分为以下几步：

1) 对于非噪声集合 $\left\{C_1,C_2,\cdots ,C_k\right\}$，任取 $x_b\notin C_i$，如果 $x_b$ 的自然最近邻域与 $C_i$ 有交集，那么就把 $x_b$ 划分到 $C_i$ 的边界域中；如果对于 $x_j\in C_i$， $x_j$ 的自然最近邻域不包含于 $C_i$ 中，则把 $x_j$ 划分到 $C_i$ 的边界域中。

2) 给定一个参数 $\rho$ ( $\rho >1$ )，设 $x_j\in C_i$，计算 $x_j$ 的平均自然最近邻居距离，以及类 $C_i$ 的平均自然最近邻距离，比较 $\rho avg\left(C_i\right)$ 与 $avg\left(x_j\right)$ 大小，如果前者比较大，则划分到对应的核心域，反之划分到边界域中。

3) 处理噪声数据。计算噪声点到各个核心域中的元素的最小距离，将噪声点分配到核心点所在类簇边界域中。

4. 实验结果

论文采用三组UCI数据集和五组shape [26] 数据集，如表1及表2。利用ACC、DBI、AS指标，将三支DBSCAN聚类与DBSCAN进行比较，得出三支DBSCAN聚类可以提高聚类精度、改善聚类性能的结论。

本实验先对每组数据进行遍历，选取一个最佳邻域半径和阈值，然后选取DBI、ACC、AS的值作为评价指标，实验结果如表3所示。Congressional和R15上的实验结果可以看出，三支DBSCAN的准确率达到了99%，从表3可以看出，与DBSCAN算法相比较，该聚类算法在数据集上有较好的聚类效果，DBI的值明显下降，ACC和AS的值也均有上升，虽然ACC的上升并不明显，但相对于二支聚类，三支DBSCAN算法在结果上都得到了有效提升。综上所述，可以证实基于DBSCAN的三支聚类算法是有效的。

Table 1. UCI dataset

表1. UCI数据集

Table 2. Shape dataset

表2. Shape数据集

Table 3. Experimental results on datasets

表3. 数据集上的实验结果

5. 结束语

由于传统硬聚类在处理不确定信息时，强将元素划分到某一类别中，可能会带来决策风险。本文提出了借助样本的自然最近邻域将硬聚类结果转换成三支聚类，将不确定的元素划分到边界域中延迟决策，待信息充分时再做决策，以此提高聚类结果的准确性，实验结果也表明本文提出的算法可以提高其性能，可以有效降低DBI的值，同时提高ACC和AS的值。但由于DBSCAN聚类算法参数的配置需要人工判定，存在了一定的人为因素，同时由于本身的算法特点，DBSCAN在处理低维数据时性能更优越，但随着数据维度的提高，该算法性能表现变差。考虑到这个问题，下一阶段使用深度神经网络对样本进行特征提取，以达到数据降维的目的，保证了DBSCAN算法的可靠性。