基于均值漂移的三支聚类算法

Three-Way Clustering Algorithm Based on Mean Shift

摘要: 本文结合基于均值漂移的聚类算法与三支决策理论，首先利用核函数对中心点至样本点的向量进行加权求和，定义了偏移向量，据此不断移动中心点的位置，使样本中心点在密度梯度方向移动至密度最大的区域。然后根据样本点对类簇的访问频率将数据分为非噪声点和噪声点数据，对非噪声点数据采取传统的二支聚类得到核心域，对噪声点数据采取三支聚类，通过比较样本点对不同类簇的访问频率将样本点划分到相应类簇的边界域。将聚类结果用核心域和边界域表示。通过UCI数据集上的实验结果，验证了本文提出的算法相对于传统聚类可以提高聚类准确度、聚类结构的类内紧密度和类间分离度。

Abstract: By combining the clustering algorithm based on mean shift with the theory of three-way decision theory, this paper defines the mean shift vector according to the vector from the center point to the sample points, so that the center point of the samples is moved in the direction of the density gradient to the region of the highest density. According to the access frequency of the sample points to the class clusters the data are divided into non-noise point and noise point data, the traditional two-way clustering is taken to obtain the core domain for the non-noise point data, and the three-way clustering is taken for the noise point data, and the sample points are divided into the boundary domains of the corresponding class clusters by comparing the access frequency of the sample points to the different class clusters. The clustering results were expressed in terms of core and boundary domains. The experimental results on the UCI dataset verify the advantages of the proposed algorithm over traditional clustering algorithms, which can improve the clustering accuracy, the intra-class closeness of the clustering structure and the inter-class separation.

1. 引言

聚类 [1] 就是将一组数据对象集划分成几个类簇，使得处于同一个簇中的对象相似度较高，而处于不同簇中的样本相似度低。聚类在生物信息学 [2] 、图像处理 [3] 、企业管理 [4] 等领域有着广泛应用。聚类是一种无监督学习 [5] 方法，即在聚类的过程中没有数据集的原始类簇标签的信息，聚类算法也可以根据样本间相似度来进行划分，其优点是无需预先确定类簇个数也能进行聚类。按照聚类原理与数据结构的特性，聚类算法包括：基于层次的聚类算法，如凝聚层次聚类算法 [6] 和BIRCH算法 [7] 等；基于密度的聚类算法，如DBSCAN算法 [8] 和DENCLUE算法 [9] 等；基于模型的聚类算法，如GMM算法 [10] 和高斯混合模型算法 [11] 等。

传统聚类算法如层次聚类算法、DBSCAN算法均为硬聚类，即数据集上的元素要么属于一个类，要么不属于一个类。当决策不完全信息下的对象时，简单直接地将某个对象划分到相应类簇中，往往会导致聚类精度下降和决策风险提高。同时，硬聚类对噪声点和异常点往往较为敏感，对不符合正态分布、离散分布的数据集的聚类结果有着较高的误差。

Fukunage [12] 在1975年提出均值漂移聚类算法，其核心思想是通过滑动窗口进行局部密度估计，使得数据点朝向密度最大的区域聚集，从而实现聚类。后来，Cheng [13] 在此基础上定义了核函数与权重系数，通过对不同样本点对偏移值的贡献值，优化了聚类的性能指标。均值漂移聚类算法是一种基于密度的无监督学习算法，相较于传统聚类算法的优点是能够通过数据的特征自适应地进行聚类，无需事先确定聚类的数量，且适用于处理大规模数据集和复杂数据类型。均值漂移聚类算法尽管改善了传统聚类算法的部分缺点，但对处理不完全信息问题的决策风险仍然较高。

为了降低传统聚类方法带来的决策风险，学者们尝试将三支决策思想引入无监督学习聚类，构建了许多基于三支决策的聚类算法。Lingras [14] 等构建了粗糙聚类模型，引入粗糙集的正域、负域和边界域来表示聚类结果。Jiang [15] 提出了基于三支决策的密度聚类算法，通过将DBSCAN算法与三支决策方法结合，引入数学形态学中的腐蚀和膨胀思想 [16] ，进行三支聚类，将聚类结果用核心域和边界域表示。Li [17] 等提出了基于样本稳定性的三支聚类算法，根据每个样本的稳定性与设定阈值的关系，将样本分为稳定样本与不稳定样本，进行三支聚类得到核心域和边界域。

本文将在均值漂移算法的基础上引入三支决策思想，提出了一种基于三支决策的均值漂移聚类算法，传统的均值漂移聚类算法是一种基于密度的二支决策聚类算法，而本文根据对象访问不同类簇的次数是否满足给定的收敛阈值条件，分离出聚类的核心域和边界域，对满足阈值条件的样本点进行划分至相应的核心域中；对不满足阈值条件的样本点进行延迟决策，即根据样本点访问类簇的次数将其划分至相应的边界域中，进而较好地解决了不确定信息带来的风险问题。根据核心域的聚类结果计算聚类评价指标，可以提高聚类结果的整体性能。

2. 相关工作

2.1. 三支决策聚类

三支决策是二支决策的延伸和拓展，2010年由Yao [18] 在决策粗糙集的研究基础上提出的决策理论，其核心思想是将研究对象分为正域、负域和边界域，使其能有效降低信息不充分时的决策风险。3个域分别对应3种决策规则，正域对应的是接受规则；负域对应的是拒绝规则；边界域对应的是不承诺规则。

目前，三支决策理论得到不断地充实与发展，并在各个领域得到广泛应用。Yu [19] 将三支决策思想结合聚类模型，据此提出了三支聚类框架，即用核心域和边界域来代表一个类簇；提出了基于 $\epsilon$ 邻域的三支决策聚类模型，并引入数学形态学中腐蚀和膨胀思想得到核心域与边界域；Wang [20] 提出了基于密度敏感谱聚类的三支决策聚类模型，引入容差参数和扰动分析得到类簇的核心域和边界域；Xu [21] 提出了基于人工蜂群的三支k-means聚类算法，构造蜜源的适应度函数解决了初始聚类中心敏感的问题。

传统的二支聚类结果通常用独立的集合域来表示，二支聚类的集合域对应的是三支聚类的核心域 $Co\left(C\right)$ ，集合域互不相交，保证了集合域中的元素一定且仅属于此类，二支聚类的结果可以表示为：

$U=\left\{Co\left(C_1\right),Co\left(C_2\right),\cdots ,Co\left(C_k\right)\right\}$

与传统的二支聚类不同，三支聚类通常使用三个互不相交的集合 $Co\left(C\right)$ 、 $Fr\left(C\right)$ 、 $Tr\left(C\right)$ 来分别表示核心域、边界域和外域。其中核心域中的元素一定属于此类，边界域中的元素可能属于此类，也有可能不属于此类，外域中的元素一定不属于此类。任意聚类结果应满足以下3个条件：

(1) $Co\left(C_i\right)\ne \varnothing$ ；

(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)\cap Co\left(C_i\right)=\varnothing ,i\ne j$ 。

条件(1)保证任意类簇不能为空；条件(2)保证数据集U中的任意元素要么属于某个类簇中的核心域，要么属于某个或多个类簇中的边界域；条件(3)保证任意不同类簇之间有明显的界限，即它们的核心域是没有交集的。

因此，成对的核心域和边界域可以用来代表类簇的聚类结果，即三支聚类的结果可以表示为：

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

2.2. 均值漂移算法(Mean Shift, MS)

均值漂移算法是基于核密度估计 [22] 的无监督聚类算法，即不需要提前确定类簇的数量，使其更符合实际情况。Mean Shift算法的核心思想是在 $\epsilon$ 邻域内利用中心点至样本点的向量用核函数进行加权求和，得到中心点x的偏移向量，类簇的样本中心点根据偏移向量不断地沿着密度梯度方向移动，当中心点x的偏移向量的模shift小于给定的收敛阈值eps时，中心点最终落在密度最大的区域。最后，比较样本点 $x_i$ 对不同类簇的访问次数，将其划分至其类簇中，完成聚类。

定义1 ( ε 邻域)

以给定区域中某样本点p为中心， $\epsilon$ 为半径的区域所包含样本点的集合，称为 $\epsilon$ 邻域，即

$N_{\epsilon }\left(p\right)=\left\{q\in U|dist\left(p,q\right)\le \epsilon \right\}$

其中，U为总数据集，q为数据集中的某一点， $dist\left(p,q\right)$ 为p和q之间的欧式距离。

定义2 (偏移向量)

给定数据集U和d维空间 $R^d$ ，对空间中的任一样本点 $x_i\in U$ ，偏移向量的基本形式定义为

$M_h\left(x\right)=\frac{1}{k}{\displaystyle \underset{x_i\in S_h}{\sum }\left(x_i-x\right)}$

其中，k表示在n个样本点 $x_i$ 中有k个点落在 $S_h$ 区域。 $S_h$ 表示以x为球心，h为半径的球内所有数据点的集合， $x_i$ 表示数据集U中第i个数据点，即

$S_h=\left\{y:{\left(y-x\right)}^{\text{T}}\left(y-x\right)\le h^2\right\}$

偏移向量决定了中心点在下一次迭代的移动移动方向，将当前中心点x更新为x加上偏移向量 $M_h\left(x\right)$ ，即

$x^{\prime }=x+M_h<span\; class="bracketMark">(\; x\; )</span>$

$x^{\prime }$ 为下一次迭代时样本中心点的坐标。

定义3 (收敛阈值eps)

在均值漂移的迭代过程中，当中心点的偏移距离shift，即偏移向量的模小于收敛阈值eps时，算法认为系统达到了最优聚类结果，并停止迭代。因此，收敛阈值又被称为终止准则。收敛阈值的选取需要综合考虑实际情况和数据结构特性，一般来说，较小的收敛阈值会增加迭代次数并产生更精确的聚类结果，较大的收敛阈值会减少迭代次数并产生更粗糙的聚类结果。

定义4 (访问频率矩阵 $A_{n\times k}$ )

由于均值漂移聚类算法不能直接输出聚类的结果，因此需要定义访问频率矩阵 $A_{n\times k}$ ，并根据每个样本点对不同类簇的访问次数的大小，对每个样本点进行类簇的划分， $A_{n\times k}$ 的基本形式为

$A_{n\times k}=\left[\begin{array}{ccc}{a}_{11}& \cdots & a_{1k}\\ ⋮& \ddots & ⋮\\ a_{n1}& \cdots & a_{nk}\end{array}\right]$

$A_{n\times k}$ 的行数表示数据点的个数为n，列数表示最终聚类的类簇数量k。需要注意的是，类簇数量k不是事先确定的，而是通过数据的特征而自适应选择的。 $a_{ij}$ 表示第i个样本点对类簇 $C_j$ 的访问次数的大小，则每个样本所属类簇则是该行中访问次数最大的那一类。

均值漂移聚类算法的核心在于求样本中心点的偏移向量，并根据最终样本中心的移动位置得到聚类结果。在给定数据集U和d维空间 $R^d$ 的情况下，其详细步骤为：

初始化参数：给定 $\epsilon$ 邻域半径和收敛阈值eps，将所有样本点标记为unvisited；

初始化中心点：在被标记为unvisited的样本点中随机选取一个点作为类簇C的样本中心点 $x_0$ ；

更新访问次数：在 $x_0$ 的 $\epsilon$ 邻域范围内找出所有样本点 $x_i$ ，记作集合M，将集合M中的点在类簇C上的访问次数加1，将访问次数保存在访问频率矩阵 $A_{n\times k}$ 的相应位置，同时认为这些点属于类簇C；

求得偏移向量 $M_r$ ：以样本中心点 $x_0$ 为圆心， $\epsilon$ 为半径，计算欧几里得空间下中心点 $x_0$ 至 $\epsilon$ 邻域内所有样本点的向量，将向量求和得到样本中心点 $x_0$ 的偏移向量 $M_r$ ；

更新中心点：根据偏移向量 $M_r$ 和漂移公式 ${x^{\prime }}_0=x_0+M_r$ ，样本中心点 $x_0$ 进行移动，即 $x_0$ 沿着 ${\stackrel{\to }{M}}_r$ 方向移动了 $\Vert M_r\Vert$ 的距离；

停止迭代：重复上述操作，当偏移向量的模 $\Vert M_r\Vert$ 小于给定的收敛阈值eps时，停止迭代，将此时的样本中心点 $x_0$ 存入样本中心点矩阵；

确定类簇数量：将样本中心点矩阵中的元素，即不同类簇之间的中心点 $x_0,x_1,\cdots ,x_k$ 进行两两作差，若差值的模 $\Vert x_i-x_j\Vert$ 小于收敛阈值eps，则将相应的两个类簇归并为同一类；若差值的模 $\Vert x_i-x_j\Vert$ 大于或等于收敛阈值eps，则认为 $x_j$ 对应的类簇 $C_j$ 为新的类簇，增加一类；

划分聚类结果：重复上述步骤直到所有样本点均被标记为visited，根据访问频率矩阵中的数值，将每个样本点划分至其访问次数最多的一类中，完成聚类。

MSC算法流程如下：(表1)

Table 1. MSC algorithm flowchart

表1. MSC算法流程图

3. 基于三支决策的均值漂移聚类(Meanshift Clustering Based on Three-Way Decisionm TWMSC)

MSC算法是一种二支聚类算法，其基本步骤是首先随机选择一个未被访问的数据点作为中心点，计算中心点到以 $\epsilon$ 为半径内数据点的向量之和作为偏移向量，据此不断迭代更新中心点的位置，使中心点在密度梯度方向上移动，最终聚集在密度最大的区域。重复以上步骤直到所有点均被访问且收敛阈值eps满足条件时跳出循环。最后，根据访问频率矩阵对样本点进行聚类的划分，将样本点划分至其访问次数最多的类簇中，且认为该点仅属于此类。当某个样本点对多个类簇的访问频率相近时，MSC算法只会将其划分至被访问次数最多的那一类中，而忽略了该样本点可能也属于被访问次数较多的那一类或几类中。

由此可见，尽管MSC算法在传统聚类算法的基础上进行了改进，具有能够根据数据特征自适应确定类簇个数，并且不需要初始化聚类中心从而避免局部最优解等优点，但与传统聚类算法相同的是，对不充分信息的数据点仍有着较高的决策风险。本文提出了基于三支决策的均值漂移聚类算法，即TWMSC算法，在TWMSC算法中考虑噪声数据点以及不充分信息带来的决策影响，通过均值漂移聚类的过程中噪声数据点的寻找和访问频率矩阵 $A_{n\times k}$ 对二支聚类的结果进行优化。

定义1 (噪声数据点)

根据访问频率矩阵 $A_{n\times k}$ 的定义，将每个数据点对每个类簇的访问次数作为矩阵元素存入访问频率矩阵 $A_{n\times k}$ ，得到

$A_{n\times k}=\left[\begin{array}{ccc}{a}_{11}& \cdots & a_{1k}\\ a_{21}& \ddots & ⋮\\ a_{n1}& \cdots & a_{nk}\end{array}\right]$

其中，第i个数据点对类簇 $C_j$ 的访问次数记为 $a_{ij}$ 。设数据点 $x_i$ 对类簇 $C_1,C_2,\cdots ,C_k$ 的访问次数为 $a_{i1},a_{i2},\cdots ,a_{ik},a_{ij}\in B$ ，记 $a_{i\max }=\max \left\{a_{i1},a_{i2},\cdots ,a_{ik}\right\}$ ，若集合B中存在与 $a_{i\max }$ 数值相近的元素，即存在一个或多个类簇的被访问次数与访问所属类簇的次数相近，则认为该点为噪声数据点。

聚类的结果是通过寻找数据点 $x_i$ 对所有类簇的访问次数 $a_{ij}$ 最大的类簇，将其归属于类簇 $C_i$ 。在聚类的过程中，通常会出现以下两种情形：

1) ${\rm I}=\left\{s|s=\frac{a_{ij}}{a_{i\max }}<\alpha ,a_i=\max \left\{a_{i1},a_{i2},\cdots ,a_{ik}\right\},a_{ij}\in B\right\}$ ；

2) $\text{ΙΙ}=\left\{s|s=\frac{a_{ij}}{a_{i\max }}\ge \alpha ,a_i=\max \left\{a_{i1},a_{i2},\cdots ,a_{ik}\right\},a_{ij}\in B\right\}$ 。

其中，s为访问次数的比例系数， $s\in \left(0,1\right)$ ，s越大，说明该类簇的被访问次数越接近所属类簇被访问的次数；反之，则说明该类簇的被访问次数越小。 $\alpha$ 为给定的比例阈值， $\alpha \in \left(0,1\right)$ ，用于判别数据点 $x_i$ 能否被认为是噪声数据点， $\alpha$ 越大，则数据点 $x_i$ 为噪声数据点的概率越小，更可能被划分至相应的核心域中；反之， $\alpha$ 越小，则数据点 $x_i$ 为噪声数据点概率越大，更可能被划分至相应的边界域中。

若 $x_i$ 属于情形I，其访问次数 $t_i$ 在该数据点对所有类簇的访问次数最大，且满足对其他类簇的访问次数与对类簇 $C_i$ 的访问次数的比值 $<\alpha$ ，说明数据点 $x_i$ 仅属于一个类簇 $C_i$ 的核心域；若 $x_i$ 属于情形II，虽然其访问次数 $t_i$ 在该数据点对所有类簇的访问次数最大，但存在该点对其他类簇的访问次数与对类簇 $C_i$ 的访问次数的比值 $\ge \alpha$ ，可以认为该点是噪声数据点，应把该点看作满足访问次数要求的类簇的边界域。

由于TWMSC算法在得到访问频率矩阵 $A_{n\times k}$ 及之前的步骤与MSC算法完全一致，因此在给定数据集U和d维空间 $R^d$ 的情况下，TWMSC算法的具体步骤可以简化为：

1) 初始化参数：给定 $\epsilon$ 邻域半径和收敛阈值eps；

2) 利用MSC算法得到聚类的访问频率矩阵 $A_{n\times k}$ ；

3) 根据数据特征确定比例阈值 $\alpha$ ，并利用访问频率矩阵 $A_{n\times k}$ 计算比例系数s，根据数据点 $x_i$ 所属的情形，将数据点 $x_i$ 分为噪声数据点与非噪声数据点；

4) 若 $x_i$ 属于情形I，则认为 $x_i$ 是非噪声数据点，对 $x_i$ 使用MSC算法，将其划分至被访问次数最多的类簇的核心域，进行直接决策；若 $x_i$ 属于情形II，则认为 $x_i$ 是噪声数据点，对 $x_i$ 使用TWMSC算法，记满足情形II条件的类簇为集合P，将该数据点划分至集合P中每个类簇的边界域，进行延迟决策。

5) 完成聚类，将聚类结果用成对的核心域和边界域表示：

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

TWMSC算法流程如下：(表2)

Table 2. TWMSC algorithm flowchart

表2. TWMSC算法流程图

4. 实验结果

为了验证本文算法的高效性，本文选取6组UCI数据集对算法进行验证。UCI数据集的数据量适中、数据质量较高、数据噪声点少等优点，因此被广泛认可。数据集如表3所示。

Table 3. The dataset used in the experiment

表3. 实验中使用的数据集

聚类的评价指标大多是通过紧凑性和可分性来定义的：紧凑性是衡量聚类中元素彼此之间的距离，可分性是衡量不同类簇之间的距离。聚类的评价指标可分为两类：外部指标和内部指标。外部指标对应的是外部评估方法，是指在知道真实标签的情况下来衡量聚类结果的好坏，例如准确率 [23] (ACC)，兰德指数 [24] (Rand Index)等。内部指标对应的是内部评估方法，是指仅通过数据来衡量聚类结果的好坏，常见的有平均轮廓系数 [25] (AS)，Davies-Bouldin指数 [26] (DBI)等。本文所选用的评价指标为准确率(Accuracy)，平均轮廓系数(Average Sihouette Coefficient)和DBI，其中，准确率和平均轮廓系数值越高，聚类效果就越好，DBI值越小，聚类效果越好。

为了比较基于均值漂移的三支聚类算法与传统聚类算法的有效性，本文选取传统的k-means聚类算法和MSC算法对选取的6组UCI数据集进行二支聚类。同时根据经验调整邻域半径 $\epsilon$ 和收敛阈值eps，使用TWMSC算法，对选取的6组UCI数据集进行聚类，再选取聚类评价指标ACC、AS和DBI对三种聚类结果进行评价。本实验对选取的每组数据集进行50次重复实验，聚类评价指标性能用均值代替，实验结果如表4所示。

由实验结果得知：TWMSC算法能够有效地改善聚类评价指标ACC、AS和DBI，在某些数据集上的聚类结果明显优于传统的k-means算法和MSC算法，聚类效果的总体性能有着一定的提升。以iris数据集为例，本文给出的TWMSC算法相较于k-means算法和MSC算法，ACC和AS变大，DBI变小，同时提高了聚类准确度、聚类结构的类内紧密性和类间分离性。即使在某些数据集上TWMSC算法的聚类

Table 4. The clustering results of the dataset used in the experiment

表4. 实验中使用的数据集的聚类结果

效果不如传统的k-means算法，例如R15数据集上的AS，但DBI仅下降了0.18%，对聚类效果的总体性能影响不大。相较于传统聚类算法，TWMSC算法无需预先确定聚类的数量以及初始样本中心点，能够根据实际的数据特征自适应调整类簇数量，并且可以精确高效地定位样本点的密集区域，因此聚类的准确度得到提高。此外，三支决策思想的引入有效地解决了非离散分布和非正态分布的数据集等不充分信息下的问题。

综上所述，本文提出的TWMSC算法能够有效提高聚类结果的ACC、AS等性能指标，相较于传统的聚类算法和MSC算法有着一定的优势，可以说明基于均值漂移的三支聚类算法是高效可行的。

5. 结束语

本文提出的基于均值漂移的三支聚类算法在预先不确定聚类数量的情况下为处理不完整信息的聚类问题提供了一种有效的解决方案。在处理高维数据和大规模数据时，该算法能快速准确地定位密集区域，提高了聚类的总体性能，在数据分析、模式识别和数据挖掘等领域具有指导意义。考虑到TWMSC算法中的参数是根据实际情况人工选取的，因此在聚类的过程中会存在一定偏差。因此，在本文研究的基础上，未来的研究可以进一步探索：1) 如何根据数据结构特征自适应地选取收敛阈值eps等参数，进而提升算法的可靠性。2) 如何降低离群点对参数的自适应选取以及聚类结果的影响，使得算法高效可行且不会陷入局部最优解。

基金项目

本文受到江苏省高等学校大学生创新创业训练计划项目资助。