基于密度聚类的三支K-Means聚类算法

Three-Way K-Means Algorithm Based on Density Clustering

摘要: 本文提出了一种基于密度聚类的三支K-Means算法。针对传统的K-Means算法在选取初始聚类中心时往往依赖于随机选择和无法处理不确定性数据对象的问题，本文采用基于密度聚类算法优化初始聚类中心的选择，并优化了截断距离的选取，最后使用三支决策的方法对聚类结果进行处理。实验结果表明，与传统的K-Means算法相比，改进的K-Means算法在聚类中表现出更高的聚类精度和稳定性。

Abstract: This paper proposes a three-branch K-Means algorithm based on density clustering. In view of the problem that the traditional K-Means algorithm often relies on random selection and cannot handle uncertain data objects when selecting initial clustering centers, this paper uses a density-based clustering algorithm to optimize the selection of initial clustering centers, and optimizes the selection of truncation distance. Finally, a three-branch decision method is used to process the clustering results. The experimental results show that the improved K-Means algorithm exhibits higher clustering accuracy and stability in clustering compared to the traditional K-Means algorithm.

1. 引言

在数据挖掘和机器学习领域中，聚类分析一直是一个重要的研究方向。聚类算法旨在将一组无标签的数据点按照某种相似性或距离度量标准划分为多个簇(Cluster)，使得同一簇内的数据点彼此相似，而不同簇间的数据点则差异显著[1]。这一特性使得聚类分析在数据探索、模式识别、图像分割、市场细分、生物信息学等多个领域得到了广泛应用。

聚类算法的研究从早期的层次聚类、划分聚类到后来的密度聚类、网格聚类、模型聚类等，各种算法层出不穷，各有千秋[2]。其中，K-Means算法以其简单高效、易于实现的特点成为最经典的聚类算法之一，但其对初始聚类中心选择的敏感性、对噪声和异常值的鲁棒性不足等问题也限制了其应用范围[3]。此外，传统的K-Means算法属于硬聚类算法，往往要求数据对象的边界清晰，一个数据对象最多只能属于一个类别。然而，在实际应用中，数据往往包含大量的不确定性。为了解决上述存在的问题，研究者们不断探索新的聚类算法和改进策略，以期在保持算法效率的同时，提高聚类结果的准确性和稳定性。

Yoder等[4]提出了半监督的K-Means++算法，该算法在随机选取一个初始聚类中心后，对数据集中的每一个样本，计算其与已选择的聚类中心之间的最短距离。然后，根据距离的平方为每个样本分配一个权重，权重越大表示该样本被选为下一个聚类中心的概率越高。最后，根据这些权重随机选择一个样本作为下一个聚类中心。孟子健等[5]提出了一种选择初始聚类中心的算法。该算法首先计算数据对象两两之间的相异度函数，构造一种新的相异度矩阵，然后选取k个与其他数据对象相异度较低且个数最多的数据对象作为初始聚类中心。张亚迪等[6]提出了一种基于密度参数和中心替换的改进K-Means算法DC-Kmeans。该算法采用数据对象的密度参数来逐步确定初始类簇中心，使用中心替换方法更新偏离实际位置的初始中心，因而比传统的聚类算法更加精确。QIAN Jin、Pingxin Wang等[7] [8]提出在聚类算法中引入三支决策。在三支聚类中，对象与簇之间的关系不仅仅是属于或不属于，还可能包括一种中间状态，如部分属于或具有某种程度的关联性，通过引入第三种可能性，三支聚类能够更好地处理数据中的不确定性和模糊性，从而提供更丰富、更细致的聚类结果[9]。孙旭阳等[10]提出了基于离群点和自适应参数的三支DBSCAN算法，该算法将三支决策思想与离群点检测LOF算法进行结合，有效地处理了数据集内不确定信息的聚类问题，并对聚类后产生的离群点做出了进一步的判断，显著提高了聚类的准确率。朱金等[11]提出了基于蚁群算法的三支K-Means聚类算法，利用蚁群算法中随机概率选择策略和信息素的正负反馈机制，动态调整权重的方法，对三支K-Means聚类算法进行优化。

依据上述问题，本文提出了基于密度聚类的三支K-Means聚类算法，本文简称为D3W-Kmeans算法。该算法首先通过密度峰值聚类算法(Density Peak Clustering Algorithm，简称DPC)优化初始聚类中心的选择，并采用中位数代替均值计算新的类簇中心，最后利用三支决策思想对聚类结果进行处理。本文首先介绍了K-Means算法基本原理和存在的问题，然后详细阐述了基于密度聚类的初始聚类中心优化方法和三支决策思想。最后，通过实验验证了所提方法的有效性和优越性。

2. 相关工作

2.1. 密度峰值聚类(DPC)算法

密度峰值聚类算法(Density Peak Clustering Algorithm，简称DPC)是一种无监督的聚类算法，由Alex Rodriguez和Alessandro Laio [12]于2014年提出。该算法的核心思想是通过自动发现数据中的密度峰值点，并将这些峰值点作为聚类中心，进而将剩余的数据点分配到最近的聚类中心所在的类簇中。DPC算法因其简单而高效的特点，在数据挖掘、模式识别、图像处理、社交网络分析等多个领域得到了广泛应用。

下面将介绍DPC算法的相关概念，如图1所示。

Figure 1. DPC algorithm-related concepts

图1. DPC算法相关概念

DPC算法基于两个关键概念：局部密度$\rho$ 和相对距离$\delta$ 。

定义1 局部密度

局部密度$\rho$ 表示一个数据点周围一定半径范围内的数据点数量，用于描述该点的密集程度。局部密度通常采用截断核(Cut-off kernel)的计算方式，对于数据集中的每一个点$x_i$ ，其局部密度${\rho }_i$ 的定义为：

${\rho }_i={\displaystyle \sum _{j\ne i}\chi \left(d_{ij}-d_c\right)}$ (1)

局部密度$\rho$ 表示一个数据点周围一定半径范围内的数据点数量，用于描述该点的密集程度。其中，$d_{ij}$ 是点$x_i$ 和点$x_j$ 之间的距离(多半采用欧氏距离)，$d_c$ 是截断距离(cutoff distance)，是一个需要预先设定的参数，$\chi \left(x\right)$ 是单位阶跃函数，如果$d_{ij}<d_c$ ，则$\chi \left(d_{ij}<d_c\right)=1$ ，否则为0。因此，${\rho }_i$ 实际上是点$x_i$ 的$d_c$ 邻域内其他点的数量。

定义2 相对距离

对于数据集中的每一个点$x_i$ ，其相对距离${\delta }_i$ 定义为：

${\delta }_i=\underset{j:{\rho }_j>{\rho }_i}{\min }\left(d_{ij}\right)$ (2)

即，${\delta }_i$ 是点$x_i$ 到所有局部密度大于${\rho }_i$ 的点$x_j$ 之间的最短距离。如果点$x_i$ 的局部密度是数据集中最大的，则通常将${\delta }_i$ 定义为数据集中所有点对之间的最大距离，以确保该点被选为聚类中心之一。

定义3 截断距离

截断距离$d_c$ 是一个需要预先设定的参数，但在实际应用中，它首先需要计算所有点对之间的距离，并构建一个距离矩阵，并对距离矩阵中所有的距离进行排序，最后选择一个百分比(如2%)的最大距离作为截断距离$d_c$ 。这个百分比的选择是经验性的，并且可能需要根据具体数据集进行调整。

2.2. K-Means聚类算法

K-Means是一种基于划分的无监督聚类算法，能将数据集分成k类，其中k是事先假定的。K-Means算法随机产生k个聚类中心，根据最近邻原则将数据点归类离其最近的聚类中心，形成k个类，并重新计算各类的聚类中心，重复上述步骤直到聚类中心不再改变位置或达到规定的迭代次数为止[13]。

定义4 欧氏距离

在K-Means算法中，通常使用欧氏距离来计算数据点与簇中心之间的距离。对于数据点$x_i$ 和簇中心$c_j$ ，其欧氏距离$d\left(x_i,c_j\right)$ 定义为：

$d\left(x_i,c_j\right)=\sqrt{{\displaystyle \sum _{k=1}^n{\left(x_{ik}-c_{jk}\right)}^2}}$ (3)

其中，n是数据点的维度，$x_{ik}$ 是数据点$x_i$ 在第k维上的值，$c_{jk}$ 是簇中心$c_j$ 在第k维上的值。

在每次迭代中，每个簇的质心$c_i$ 会根据簇内所有点的均值进行更新。对于第j个簇，其新的质心${c^{\prime }}_j$ 的定义为：

${c^{\prime }}_j=\frac{1}{\left|C_j\right|}{\displaystyle \sum _{x_i\in C_j}{x}_i}$ (4)

其中，$C_j$ 是第j个簇中所有点的集合，$\left|C_j\right|$ 是该簇中点的数量，$x_i$ 是簇$C_j$ 中的点。

K-Means算法的停止条件可以基于多种因素，常见的有以下几种：

质心变化：如果连续两次迭代中所有簇的质心变化非常小(例如，小于某个预设的阈值)，则算法停止。

迭代次数：达到预设的最大迭代次数后停止。

目标函数：K-Means算法的目标是最小化所有点到其簇中心的距离平方和(SSE, Sum of Squared Errors)。当SSE的变化非常小或达到某个阈值时，算法可以停止。在K-Means算法中，SSE (Sum of Squared Errors，误差平方和)是衡量聚类效果的一个重要指标。它表示的是每个数据点到其所属簇中心点的距离的平方和。SSE越小，表示数据点与簇中心点的距离越近，聚类的效果越好。SSE的计算公式如下：

$\text{SSE}={\displaystyle \sum _{k=1}^K{\displaystyle \sum _{i\in C_k}{\left(x_i-c_k\right)}^2}}$ (5)

其中，K表示簇的数量；$C_k$ 表示第k个簇，即包含所有属于第k个簇的数据点的集合；$x_i$ 表示数据集中的每个数据点；$c_k$ 表示第k个簇的中心点。

2.3. 三支聚类

Yao [14] [15]在决策粗糙集和概率粗糙集的假设中提出了三只决策理论，它是一种基于人类认知的决策模式，主要用于处理不确定性和模糊性的决策问题。三支决策理论将决策空间划分为三个互不重叠的区域：核心域(Positive Region，R-域)、琐碎域(Negative Region，L-域)和边界域(Boundary Region，M-域)。这三个区域分别对应了决策中的三种状态：接受、拒绝和不确定。

Yu [16]等将三支决策理论结合到聚类方法中，提出了三支聚类方法。三支聚类将一个论域划分为三个不相交的区域：核心域(Core Region)、边界域(Fringe Region)和琐碎域(Trivial Region)，分别对应聚类中的肯定、不确定和否定状态。各区域的具体定义如下：

定义5 核心域

核心域(Co(C))包含那些明确属于某个聚类的对象，这些对象与聚类中心的相似度或距离满足一定的阈值条件。

定义6 边界域

边界域(Fr(C))包含那些可能属于某个聚类但又不完全确定的对象，这些对象与聚类中心的相似度或距离处于一定的模糊范围内。

定义7 琐碎域

琐碎域(Tr(C))包含那些明确不属于任何聚类的对象，这些对象与所有聚类中心的相似度或距离都低于某个阈值。

三支聚类通常使用一对集合来表示一个聚类：

$C=\left(Co\left(C\right),Fr\left(C\right)\right)$ (6)

其中Co(C)和Fr(C)分别表示聚类的核心区域和边缘区域，而外部区域Tr(C)则是论域U中除了Co(C)和Fr(C)之外的所有对象组成的集合，即

$Tr\left(C\right)=U-Fr\left(C\right)-Co\left(C\right)$ (7)

3. 基于密度聚类的三支K-Means算法

3.1. 基于密度聚类的初始聚类中心选择算法

本文所提出的初始聚类中心选择算法，旨在通过计算数据集中各数据对象的密度来明确初始类簇中心，从而有效规避K-Means算法因随机选择初始类簇中心而导致的聚类结果不稳定问题。二支聚类与三支聚类的区别如图2所示。

Figure 2. Two-branch clustering is different from three-branch clustering

图2. 二支聚类与三支聚类区别

本文所提出的初始聚类中心选择算法，旨在通过计算数据集中各数据对象的密度来明确初始类簇中心，从而有效规避K-Means算法因随机选择初始类簇中心而导致的聚类结果不稳定问题。二支聚类与三支聚类的区别如图2所示。

定义8 基于欧氏距离，所有数据对象之间距离的中位数定义为MedianDist。

定义9 动态中位距离

对于不同的数据集，聚类后所生成的簇的数量以及各类簇中包含的数据对象的数目可能会存在差异。伴随着类簇数量以及各个类簇中数据对象的变化，数据对象之间的距离也会相应地发生变化。为此，定义基于所有数据对象之间距离中位数和簇数的动态中位距离DyMeDist作为截断距离$d_c$ ：

$DyMeDist=MedianDist/K$ (8)

$d_c=DyMeDist$ (9)

其中，K为数据集D被划分的类簇的数目。

3.2. 类簇中心的替换

针对K-Means算法对离群值敏感的问题，本文采用中位数代替均值计算新的类簇中心的方法，并根据数据集规模采取了两种不同的计算方式。当数据集规模较小时，计算所有数据对象欧氏距离的中位数；当数据集规模较大时，随机选取设定数量的数据对象并计算其欧氏距离的中位数，以此提升处理大规模数据集时的效率。

3.3. 三支聚类

在K-Means聚类后，每个数据点都被分配到了一个簇中。然而，由于数据的复杂性和噪声的存在，某些数据点的簇分配可能并不明确，即存在不确定性。本文引入三支决策思想来处理聚类结果的不确定性。

为了量化三支决策的决策区域，本文定义以下公式：设$x_i$ 为数据点，$c_i$ 为第i个簇的簇中心，$d\left(x_i,c_i\right)$ 为点$x_i$ 到簇中心$c_i$ 的欧氏距离，$\delta$ 为划分核心域与边界域的阈值。

如果$\forall j\ne i$ ，$d\left(x_i,c_i\right)<d\left(x_i,c_j\right)$ ，则$x_i$ 属于$c_i$ 的核心域。

如果$\exists j\ne i$ ，$d\left(x_i,c_i\right)<d\left(x_i,c_j\right)-\delta$ ，则$x_i$ 不属于$c_i$ 的核心域。

且如果$d\left(x_i,c_i\right)>{\max }_{k}d\left(x_i,c_k\right)+\delta$ ，则$x_i$ 属于$c_i$ 的琐碎域。

不满足核心域和琐碎域条件的则属于边界域。

3.4. D3W-K-Means算法流程

输入：数据集$D=\left\{x_1,x_2,\cdots ,x_n\right\}$ ；类簇数K

输出：数据集$C=\left\{C_1,C_2,\cdots ,C_K\right\}$

Step1：计算数据集D中任意一对数据对象$\left(x_i,x_j\right)$ 之间的动态中位距离(DyMeDist)作为截断距离$d_c$

Step2：for $i=1,2,\cdots ,n$ do

计算数据$x_i$ 对象的密度$\rho \left(x_i,d_c\right)$

Step3：for $k=1,2,\cdots ,K$ do //搜索并确定k个初始类簇中心，随后将它们添加到初始类簇中心集合V中

Step3.1：从数据集D中选取密度最高的数据对象x，并删除从数据集D中x邻域内的所有数据对象。设x为第k个初始类簇中心$v_k$

Step3.2：$V\leftarrow v_k$ ；//将$v_k$ 放入初始类簇中心的集合V

Step4：初始化各个类簇$C_k$

Step5：将D中的各个数据对象放入相应的类簇中。计算数据对象$x_i$ 和V中各个类簇中心之间的距离，将$x_i$ 放入距离最近的类簇中

Step6：用中位数替代均值计算新的类簇中心$v_k$ 并在更新类簇中心后初始化类簇$C_k$ 。当$v_k$ 不再改变，此时中止迭代

Step7：利用三支决策思想划分每个类簇$C_k$ 的核心域$Co\left(C\right)$ 和边界域$Fr\left(C\right)$ ，此时聚类完成

4. 聚类结果评价指标

4.1. ACC (Accuracy)

ACC，即聚类准确率，是聚类算法外部评价指标之一[17]。它通过比较聚类算法为每个样本分配的聚类标签与样本的真实标签之间的匹配程度，来评估聚类算法的性能。ACC的取值范围在0到1之间，值越接近1，表示聚类结果越准确，即聚类算法的性能越好。

定义10 ACC

ACC的计算公式基于样本的聚类标签与真实标签之间的对应关系。具体来说，假设有N个样本，第i个样本聚类产生的标签是$p_i$ ，真实标签是$y_i$ ，则ACC的计算公式可以表示为：

$\text{ACC}=\frac{1}{N}{\displaystyle \sum _{i=1}^N\delta \left(y_i,map\left(p_i\right)\right)}$ (10)

其中，$\delta \left(x,y\right)$ 是一个delta函数，当$x=y$ 时，$\delta \left(x,y\right)=1$ ，否则$\delta \left(x,y\right)=0$ 。$map\left(p_i\right)$ 是一个映射函数，用于将聚类标签$p_i$ 映射到真实标签$y_i$ 相对应的最佳排列上。这是因为聚类算法可能会产生与真实标签顺序不一致的聚类标签，但只要聚类结果中的样本分配是正确的，就可以通过映射函数找到与真实标签相对应的聚类标签排列。

4.2. F值

F值，也称为F-Measure或F-Score，是信息检索和机器学习领域中常用的一种性能评价指标，它综合了查准率和查全率的优点，用于衡量聚类算法生成的聚类结果与真实标签之间的匹配程度[18]。F值越高，表示聚类效果越好，即聚类算法的性能越优。

定义11 F值

F值的计算公式如下：

$F_{\beta }=\frac{\left({\beta }^2+1\right)\times P\times R}{{\beta }^2\times P+R}$ (11)

其中，$F_{\beta }$ 表示F值，$\beta$ 是一个调整参数，用于平衡查准率(P)和查全率(R)的重要性。当$\beta =1$ 时，F值退化为最常见的F1值，此时查准率和查全率的重要性相等。

查准率和查全率的公式分别为：

查准率：$P=\frac{\left|P_j\cap C_i\right|}{\left|C_i\right|}$ (12)

表示聚类算法将样本正确分配到某个簇的比例。其中，$P_j$ 表示真实标签中的第j个簇，$C_i$ 表示聚类算法生成的第i个簇，$\left|P_i\cap C_i\right|$ 表示真实簇$P_j$ 和聚类簇$C_i$ 的交集大小，$\left|C_i\right|$ 表示聚类簇$C_i$ 的大小。

查全率：$R=\frac{\left|P_j\cap C_i\right|}{\left|P_j\right|}$ (13)

表示真实簇$P_j$ 中的样本被聚类算法正确分配到簇$C_i$ 的比例。其中，$\left|P_j\right|$ 表示真实簇$P_j$ 的大小。

F值广泛应用于聚类效果的评估中，特别是在有外部标签信息的情况下，可以通过将聚类结果与真实标签进行比较来计算F值。通过F值，我们可以评估聚类算法在不同参数设置下的性能表现，选择最优的聚类算法和参数设置。

4.3. Purity

Purity的基本思想是将聚类结果中的每个簇分配给与其包含最多相同真实标签的类别，然后计算所有簇分配正确的样本数占总样本数的比例[19]。这个比例越高，表示聚类结果与真实标签的一致性越好，即聚类算法的纯度越高。

定义12 Purity

Purity的计算公式可表示为：

$Purity=\frac{1}{N}{\displaystyle \sum _{i=1}^k\underset{j}{\max }\left|{\omega }_i\cap c_j\right|}$ (14)

其中，N是样本总数；k是聚类结果中簇的个数；${\omega }_i$ 表示第i个簇中的样本集合；$c_j$ 表示真实标签中第j个类别的样本集合；$\left|{\omega }_i\cap c_j\right|$ 表示第i个簇与第j个真实类别之间的交集大小，即同时属于该簇和该类别的样本数；${\max }_j\left|{\omega }_i\cap c_j\right|$ 表示第i个簇与所有真实类别交集大小中的最大值，即该簇分配给与其包含最多相同真实标签的类别。

5. 实验结果与分析

本节选取了5组UCI数据集(表1)对基于密度聚类的三支K-Means聚类算法的性能进行测试及评估。

Table 1. Data set description

表1. 数据集描述

ID	数据集	样本数	属性数	类别数
1	Iris	150	4	3
2	Seeds	210	7	3
3	Wine	178	13	3
4	Glass	214	9	6
5	Wdbc	569	30	2

为了对所提出的算法验证其有效性，对聚类结果分别计算ACC、F值、Purity来评价聚类效果。数值越大，表明聚类效果越好。为了能更好地体现出D3W-Kmeans算法在ACC、F值、Purity性能指标上有所提升，将所提出的算法与传统K-Means算法和DC-Kmeans算法进行聚类性能指标比较，实验结果如表2。

Table 2. Results on the UCI data set

表2. UCI数据集上的结果

ID	算法	ACC	F值	Purity
1	K-Means	0.7603	0.7321	0.7533
	DC-Kmeans	0.8455	0.8346	0.8842
	D3W-Kmeans	0.8741	0.8566	0.9084
2	K-Means	0.6573	0.6405	0.7534
	DC-Kmeans	0.7576	0.7433	0.8708
	D3W-Kmeans	0.7666	0.7504	0.9253
3	K-Means	0.6475	0.6683	0.6714
	DC-Kmeans	0.7159	0.7152	0.7345
	D3W-Kmeans	0.6943	0.6836	0.7259
4	K-Means	0.5981	0.5874	0.6124
	DC-Kmeans	0.6357	0.6145	0.6896
	D3W-Kmeans	0.6782	0.6317	0.7021
5	K-Means	0.8541	0.8268	0.8562
	DC-Kmeans	0.8764	0.8467	0.8865
	D3W-Kmeans	0.8863	0.8475	0.9043

根据表2的实验结果可以看出，与K-Means和DC-Kmeans算法比较，本文中算法在5个数据集上对性能指标ACC、F值、Purity上有所提高。实验结果表明，基于密度聚类的D3W-Kmeans聚类算法在大部分数据集上相比传统K-Means聚类算法和DC-Kmeans算法拥有更高的聚类精度和准确性。鉴于UCI真实数据集的数据分布往往错综复杂，具有高度的多样性和非均匀性，这种复杂性对传统K-Means聚类算法构成了严峻挑战，导致其在处理这些真实数据时表现欠佳。相比之下，D3W-Kmeans算法通过引入密度聚类，规避了传统K-Means算法随机选取初始聚类中心的影响，利用三支决策思想将样本更精确地划分为核心域、边界域、琐碎域，更加灵活地适应了复杂数据分布的特点，从而在真实数据集中实现了显著的准确率提升。这种改进不仅增强了算法对数据局部特性的敏感性和适应性，还有效提升了聚类结果的准确性和鲁棒性，为处理复杂数据集提供了一种更为高效和可靠的解决方案。

6. 结束语

本文首先提出改进K-Means算法来解决传统K-Means算法的不足。在算法的初始阶段，采用了密度聚类的方法来确定初始类簇中心，这一策略有效地规避了传统K-Means算法随机选择初始中心点可能导致的聚类效果不佳的问题。进入迭代阶段后，进一步优化了类簇中心的更新机制。传统的K-Means算法使用均值来计算新的类簇中心，但在某些情况下，均值可能会受到极端值或噪声数据的影响，导致聚类结果偏离实际。为了解决这个问题，该算法引入了使用中位数代替均值的方法来计算新的类簇中心。中位数作为一种更加稳健的统计量，能够更好地反映数据的中心趋势，减少噪声数据的干扰，从而提高聚类的准确性和稳定性。此外，针对传统K-Means算法在处理不确定性数据时存在的局限性，本文引入了三支决策思想。三支决策思想将聚类结果划分为核心域和边界域，其中核心域包含确定性较高的数据点，而边界域则包含不确定性较高的数据点。

为了验证本文提出的方法的有效性，本文进行了大量的实验测试。测试结果表明，与传统K-Means算法相比，本文提出的方法在聚类准确率、稳定性和鲁棒性等方面均表现出显著的优势，在数据挖掘、机器学习等领域的广泛应用前景。