基于相互近邻和证据理论的密度峰值聚类算法

Density peaks clustering algorithm based on mutual nearest neighbors and Dempster⁃Shafer theory

摘要

密度峰值聚类（Density Peaks Clustering，DPC）是一种基于密度的聚类算法，能够在无需预设聚类数量的条件下自动识别任意形状的类簇.然而，DPC算法在处理具有密度差异的类簇时，会在密集类簇中误选多个聚类中心，而忽略稀疏类簇的聚类中心.此外，DPC算法的单步链式分配策略易引发“多米诺效应”，即单个样本的错误分配导致后续样本的分配出现连锁偏差.针对上述问题，提出一种基于相互近邻和证据理论的密度峰值聚类算法（Density Peaks Clustering Algorithm Based on Mutual Nearest Neighbors and Dempster⁃Shafer Theory，MDS⁃DPC）.首先，融合样本的距离相似性与邻域凝聚度，重新定义局部密度的计算方式，有效平衡簇间密度差异.其次，综合考虑样本局部和全局分布特征，基于局部密度峰与相互近邻图优化相对距离度量，更准确地表征样本间的相对位置关系.最后，引入证据理论，采用多阶段分配和跨簇连接样本分层微调策略，提高样本分配的准确性.在九个合成数据集与12个真实数据集上，将所提算法与六个优秀的聚类算法进行对比，实验结果表明，MDS⁃DPC算法的聚类效果更优.

Abstract

Density Peaks Clustering (DPC) is a density⁃based clustering algorithm capable of automatically identifying clusters of arbitrary shapes without requiring the number of clusters to be pre⁃specified. However，when processing datasets containing clusters with significant density variations，DPC tends to erroneously select multiple cluster centers within dense clusters while overlooking the true centers in sparse clusters. Furthermore，DPC's single⁃step chained allocation strategy is prone to a “domino effect”，where the misallocation of a single data point can trigger a cascade of erroneous assignments for subsequent points. To address these issues，this paper proposes a novel Density Peaks Clustering algorithm based on Mutual Nearest Neighbors and Dempster⁃Shafer Theory，termed MDS⁃DPC. First，by integrating a sample's distance⁃based similarity with its neighborhood cohesion，we redefine the calculation of local density to effectively mitigate inter⁃cluster density disparities. Second，to more accurately characterize the relative positional relationships between samples，we refine the relative distance metric by leveraging both local and global distribution characteristics，specifically through the integration of local density peaks and a mutual nearest neighbor graph. Finally，we introduce Dempster⁃Shafer theory and employ a multi⁃stage assignment strategy coupled with a hierarchical fine⁃tuning mechanism for cross⁃cluster connected samples to enhance the overall accuracy of sample allocation. We evaluated the proposed MDS⁃DPC algorithm against six state⁃of⁃the⁃art clustering algorithms on nine synthetic and twelve real⁃world datasets. The experimental results demonstrate that MDS⁃DPC achieves superior clustering performance.

Graphical abstract

关键词

密度峰值聚类 / 相互近邻 / 局部密度峰 / 证据理论 / 多阶段分配

Key words

density peaks clustering / mutual nearest neighbors / local density peaks / Dempster⁃Shafer theory / multi⁃stage assignment

聚类分析作为数据挖掘领域中关键的无监督学习方法，其核心目标是将数据划分为若干类簇，使簇内样本相似性高，簇间样本相似性低，进而发现数据内部潜在的结构特征与分布模式^［1］.目前，聚类分析已广泛应用于社区发现^［2-4］、多粒度建模^［5-6］、生物信息分析^［7-8］等场景.根据聚类机制的差异，现有的聚类算法可分为基于划分^［9］、基于层次^［10］、基于密度^［11］、基于网格^［12］、基于图^［13］和基于神经网络^［14］六大类.其中，基于密度的聚类方法以数据对象的密度为聚类依据，无需指定聚类数量即可发现任意形状的类簇，在处理具有复杂分布的数据时具有优势.

2014年Rodriguez and Laio^［15］首次提出密度峰值聚类（Density Peaks Clustering，DPC）算法，这是一种基于密度的聚类算法，通过定义局部密度与相对距离两个核心属性，将局部密度较大且相对距离较高的样本判定为聚类中心，而非中心样本则分配到最近高密度样本所在类簇，无需迭代即可快速聚类，具有原理简单、可操作性强的特点.但DPC算法认为每个类簇仅存在一个密度峰值样本，这种过于理想的假设导致其在处理具有簇间密度差异的数据时，容易在密集类簇中误选多个聚类中心，忽略稀疏类簇真实的聚类中心.其次，DPC算法基于欧氏距离来确定样本的相对距离，无法准确反映类簇的实际结构和分布特征，难以有效刻画非球形类簇上样本间的相对位置关系.此外，DPC算法将非中心样本分配到最近高密度样本所在类簇，这种分配策略易引发“多米诺效应”，即某个样本分配出现偏差，错误可能级联传播，最终导致聚类结果失真.针对上述问题，本文提出了一种基于相互近邻和证据理论的密度峰值聚类算法，主要贡献如下.

（1）优化局部密度计算方式.通过融合样本距离相似性和邻域凝聚度，打破单一距离度量的局限，重新定义局部密度，有效平衡了簇间密度差异，提升了聚类中心识别的准确性.

（2）改进相对距离度量方式.将样本划分为局部和非局部密度峰两类，并采用差异化的相对距离计算方式.其中，非局部密度峰的相对距离在k近邻中确定，局部密度峰通过相互近邻图求解，能更准确地表征样本间的相对距离.

（3）引入证据理论，提出多阶段分配和跨簇连接样本微调策略.通过聚类中心k近邻快速生长、队列迭代邻域扩散和证据理论信度融合，完成样本初步分配.在此基础上，对部分跨簇连接样本进行分层微调，进一步提高样本分配的准确性.

1 相关工作

DPC算法虽然凭借原理简洁、直观实用的优势得到了广泛的研究和应用，但存在一些局限.针对DPC存在的问题，目前的研究主要从局部密度、相对距离和分配策略三个方面进行改进.

针对DPC算法处理密度差异类簇时容易误选聚类中心的问题，Zang et al^［16］的DPC⁃DVND算法利用k近邻计算样本的局部密度并定义密度投票关系，可有效适配多密度峰值及不同密度分布的类簇.Xie et al^［17］的SFKNN⁃DPC算法充分考虑各特征对样本的特定贡献，通过标准差加权距离来重新定义样本间相似性，并优化局部密度计算方式以提高密度峰值获取的准确性.Guo et al^［18］的FNaN⁃DPC算法，基于自然近邻改进局部密度度量方式，可自适应消除簇间密度差异的干扰.Deng et al^［19］在DPC⁃MDMN算法中定义调和密度，弱化簇间样本密度差异，有效规避了密度不均导致的聚类中心误判.

针对DPC算法依赖欧氏距离计算相对距离，难以有效刻画复杂形状类簇的问题，Guo et al^［20］在DPC⁃CE算法中设计融合欧氏距离与连通性距离的惩罚机制，通过连通性估计表征邻接关系与路径强度，增强对不规则分布的适配能力.陈梅等^［21］在KNNG⁃DPC算法中，构建局部与全局k近邻图并引入最短路径思想，重新定义相对距离度量，更准确地刻画了样本空间分布特征.Ding et al^［22］的RDPCM算法用测地距离替代欧氏距离，结合改进的相互近邻策略优化测地距离的计算，可有效捕捉类簇局部流形结构.Xie et al^［23］的SMFK⁃DPC算法融合标准差加权的曼哈顿距离与欧氏距离，通过双距离加权机制提升距离度量的泛化性.

针对DPC算法分配策略容错性较低，容易引发“多米诺效应”的问题，张清华等^［24］的基于代表点和k近邻的RKNN⁃DPC算法设计了一种加权的k近邻分配策略，借助双队列结构完成非中心样本的分配，提高了聚类精度.Hou et al^［25］的DBSCAN⁃DPC算法以局部密度最大样本为中心，先通过DBSCAN生成初始聚类，再按上级节点归属规则自适应扩展至无有效候选样本，改进了DPC的分配策略.Xie et al^［26］的WANN⁃DPC算法结合了最近邻关系和加权归属度，采用两步分配策略，缓解了“多米诺效应”的影响.Zang et al^［27］在DPC⁃MFP算法中定义从属点，并将其划分为确定型和不确定型两类，采用混合分配策略，进一步优化聚类效果.

2 相关理论

2.1　DPC算法

DPC^［15］是一种基于密度的聚类算法，其核心思想依托两个假设：（1）聚类中心周围分布着较多样本；（2）不同聚类中心相互远离.基于上述假设，定义刻画样本的两个关键属性：局部密度和相对距离.局部密度的计算如下：

{\rho }_i=\sum _{j\ne i}\mathrm{e}\mathrm{x}\mathrm{p}\left(-\frac{d_{ij}^{\mathrm{2}}}{d_c^{\mathrm{2}}}\right)(1)

\begin{array}{l}{\rho }_i=\sum _{j\ne i}\chi \left(d_{ij}-d_c\right)\\ \chi \left(\Delta \right)=\left\{\begin{array}{cc}\mathrm{1},& \Delta \le \mathrm{0}\\ \mathrm{0},& \mathrm{其他}\mathrm{情况}\end{array}\right.\end{array}(2)

其中，d_{ij}是样本x_i和样本x_j间的欧氏距离，d_c是截断距离.式（1）对应的高斯核能获得较平滑的结果，适用于小规模数据集；式（2）对应的截断核计算效率较高，适用于大规模数据集.相对距离的计算如下：

{\delta }_i=\left\{\begin{array}{cc}\underset{j:{\rho }_j>{\rho }_i}{\mathrm{m}\mathrm{i}\mathrm{n}}\left\{d_{ij}\right\},& {\rho }_i\ne {\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}\\ \underset{j\ne i}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{d_{ij}\right\},& \mathrm{其他}\end{array}\right.(3)

其中，{\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}是所有样本局部密度的最大值.样本的相对距离是该样本与最近高密度样本之间的欧氏距离.而对于全局最大局部密度的样本，其相对距离为该样本与其他所有样本之间的最大欧氏距离.

DPC算法以局部密度为横轴，相对距离为纵轴绘制决策图，决策图右上方同时具有较高局部密度和相对距离的样本被判定为聚类中心.由于在决策图中人工选取聚类中心存在主观性，因此常利用决策值对聚类中心进行量化判定.决策值的计算如下所示：

{\gamma }_i={\rho }_i\cdot {\delta }_i(4)

对所有样本，按决策值降序排序后，选取前s个样本作为聚类中心，通常，s等于真实聚类数量，该方式提高了聚类中心选择的客观性和自动化程度.聚类中心确定后，剩余非中心样本按局部密度从高到低的顺序，依次分配到各自最近高密度样本所属类簇中.

2.2　证据理论

证据理论^［28］是一种能显式量化“未知”的数学推理框架，主要通过识别框架与基本信度分配表示不确定信息，并采用Dempster融合规则和Pignistic概率转换，实现多源不确定性证据到确定性决策的转换.

在证据理论中，识别框架是所有可能且互斥的基本命题构成的完备集合，记为\Theta =\left\{{\theta }_{\mathrm{1}},{\theta }_{\mathrm{2}},\right.

\left.\cdots ,{\theta }_n\right\}.在此基础上，每个证据对命题的支持度通过基本信度分配函数量化，该函数记作μ.对于识别框架Θ的子集A，\mu \left(A\right)表示对命题A的信度，需满足以下性质：

\begin{array}{ccc}\mu :{\mathrm{2}}^{\Theta }\to \left[\mathrm{0,1}\right],& \mu \left(\mathrm{\varnothing }\right)=\mathrm{0},& \sum _{A\subseteq \Theta }\mu \left(A\right)=\mathrm{1}\end{array}(5)

特别地，\mu \left(\Theta \right)是分配给整个识别框架的信度，表示完全未知或无法区分的程度.

由于单一证据往往不足以作出可靠决策，因此，证据理论常使用Dempster融合规则，通过求交集来聚焦共识，并利用归一化因子\mathrm{1}-K对冲突引起的信度进行重新分配，实现对不一致信息的合成.假设两个独立证据源基本信度分别为μ₁和μ₂，命题A综合信度的计算如下：

\left({\mu }_{\mathrm{1}}\oplus {\mu }_{\mathrm{2}}\right)\left(A\right)=\frac{\sum _{B\bigcap C=A}{\mu }_{\mathrm{1}}\left(B\right){\mu }_{\mathrm{2}}\left(C\right)}{\mathrm{1}-K}(6)

其中，K=\sum _{B\bigcap C=\mathrm{\varnothing }}{\mu }_{\mathrm{1}}\left(B\right){\mu }_{\mathrm{2}}\left(C\right)是冲突系数，用于度量证据间的不一致程度.

融合后得到的综合信度，通常使用Pignistic概率转换公式，将分配给任一复合命题的总信度平均分配给该命题包含的所有基本元素，进而转化为标准概率值，为最终决策提供更直观的量化依据.Pignistic概率转换公式如下所示：

P\left({\theta }_i\right)=\sum _{A\subseteq \Theta ,{\theta }_i\in A}\frac{\mu \left(A\right)}{\left|A\right|}(7)

其中，\left|A\right|代表命题A中包含基本元素{\theta }_i的总数.

3 MDS⁃DPC算法

3.1　融合距离相似性和邻域凝聚度的局部密度

DPC及其大部分改进算法在计算样本局部密度时通常仅依赖单一距离度量，忽略了样本的局部拓扑信息，容易在簇间密度分布不均的数据上产生估计偏差，导致聚类中心的误判.对此，本文基于k近邻和相互近邻，融合距离相似性与邻域凝聚度，重新定义局部密度计算方式，有效平衡了簇间密度分布差异.

定义1

k近邻^［29］ 给定数据X=\left\{x_{\mathrm{1}},x_{\mathrm{2}},\right.

\left.\cdots ,x_n\right\},对于任意样本x_i\in X，若样本x_k是距离样本x_i第k近的样本，则样本x_i的k近邻可表示为：

N_k\left(x_i\right)=\left\{x_j\in X\left|d_{ij}\le d_{ik}\right.\right\}(8)

若x_j是x_i的k近邻，且x_i也是x_j的k近邻，则样本x_i和样本x_j为相互近邻^［30］.样本x_i所有的相互近邻可表示为：

M_k\left(x_i\right)=\left\{x_j\in X\left|x_j\in N_k\left(x_i\right)\wedge x_i\in N_k\left(x_j\right)\right.\right\}(9)

定义2

距离相似性 给定数据X=\left\{x_{\mathrm{1}},\right.

\left.x_{\mathrm{2}},\cdots ,x_n\right\}，对于任意样本x_i\in X，若样本x_j是样本x_i的相互近邻，则样本x_i与其相互近邻的距离相似性可表示为：

d{s}_i=\sum _{{\mathit{x}}_j\in M_k\left(x_i\right)}\frac{\mathrm{e}\mathrm{x}\mathrm{p}\left(-d_{ij}\right)}{\mathrm{1}+d_{ij}}(10)

其中，\mathrm{e}\mathrm{x}\mathrm{p}\left(-d_{ij}\right)随距离增大，呈指数级减小，而\mathrm{1}+d_{ij}随距离线性递增.引入\mathrm{1}+d_{ij}可以避免在距离过小时距离相似度过大，起到平滑约束作用.

定义3

邻域凝聚度 给定数据X=\left\{x_{\mathrm{1}},x_{\mathrm{2}},\right.

\left.\cdots ,x_n\right\}，对于任意样本x_i\in X，若样本x_j是样本x_i的k近邻，则样本x_i的邻域凝聚度可表示为：

s{s}_i=\frac{\mathrm{1}}{k}\sum _{x_j\in N_k(x_i)}\frac{\left|M_k\left(x_j\right)\bigcap N_k\left(x_i\right)\right|}{\left|M_k\left(x_j\right)\bigcup N_k\left(x_i\right)\right|}(11)

其中，\left|M_k\left(x_j\right)\bigcap N_k\left(x_i\right)\right|衡量了样本x_j稳定邻域与样本x_i局部邻域的重叠程度，分式比值越接近1，表明两个样本的局部结构越紧密.求和取平均后，s{s}_i量化了样本x_i与其所有k近邻的内聚程度.

最后，将距离相似性和邻域凝聚度融合，改进局部密度的计算方式.新的局部密度如下所示：

{\rho }_i^{\text{'}}=d{s}_i+s{s}_i(12)

其中，d{s}_i通过引入平滑权重，抑制了高密度类簇中因样本间距离较小而产生的密度值膨胀；s{s}_i通过度量局部邻域的拓扑结构一致性，为距离稀疏但结构内聚的低密度样本提供必要的密度补充.二者协同作用，修正了单纯依赖距离导致的密度估计偏差.

图1是Jain数据集在不同计算方式下样本局部密度分布热力图，颜色越亮表示样本局部密度越大，图1a和图1b分别为使用式（1）和式（12）计算局部密度的结果.由图可见，MDS⁃DPC算法定义的局部密度，使两个类簇中大部分样本的亮度更接近，有效平衡了簇间密度差异.

3.2　基于局部密度峰和相互近邻图的相对距离

DPC算法中，局部密度较低的样本在确定相对距离时，需要计算并比较其与所有高密度样本的欧氏距离，耗时较高.此外，基于欧氏距离的相对距离无法准确刻画非球形类簇的实际分布.对此，本文引入局部密度峰和相互近邻图，优化相对距离的计算方式，能更准确地表征样本间相对位置关系.

定义4

局部密度峰 给定数据X=\left\{x_{\mathrm{1}},x_{\mathrm{2}},\right.

\left.\cdots ,x_n\right\},对于任意样本x_i\in X及其k近邻x_j\in N_k\left(x_i\right),若样本x_i满足：

x_i=\underset{x_j\in N_k\left(x_i\right)\bigcup \left\{x_i\right\}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}\left\{{\rho }_j^{\text{'}}\right\}(13)

则称样本x_i为一个局部密度峰.所有局部密度峰构成的集合可表示为：

DP=\left\{x_i\in X\left|x_i=\underset{x_j\in N_k\left(x_i\right)\bigcup \left\{x_i\right\}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}\left\{{\rho }_j^{\text{'}}\right\}\right.\right\}(14)

根据定义4，局部密度峰是指局部密度高于其所有k近邻的样本；反之，若某样本的k近邻中存在局部密度更高的样本，则该样本为非局部密度峰.非局部密度峰在其k近邻内即可确定最近的高密度样本，从而缩小相对距离的计算与搜索范围.此外，结合KD⁃Tree加速样本k近邻搜索，可进一步降低近邻范围内欧氏距离计算的时间复杂度.

局部密度峰需要在全局范围内确定相对距离，为了更准确地刻画数据真实分布，引入图距离来度量局部密度峰的相对距离.图距离通过在数据构造的图结构中求解最短路径得到，本质是对测地距离的近似，可以有效地表征复杂形状的簇结构.为了构建稳健的图结构，本文采用相互近邻图刻画样本关联.该结构通过双向近邻来约束建边，剔除了不稳定的单向边和伪关联边.相比于k近邻图，相互近邻图更稀疏，而且能有效地抑制噪声与异常样本干扰，更真实地反映簇结构和样本关联紧密性.

相互近邻图的定义如下.

定义5

相互近邻图^［30］ 相互近邻图G_m=\left(V,E\right)为一个加权无向图，其中，每个节点v\in V表示一个样本，每条边e\in E的两个端点样本满足相互近邻关系.给定数据X=\left\{x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_n\right\},相互近邻图中边权重定义如下：

W_m\left(i,j\right)=\left\{\begin{array}{cc}{d}_{ij},& \exists x_j\in M_k\left(x_i\right)\\ \mathrm{0},& \mathrm{其他}\end{array}\right.(15)

综上，基于局部密度峰和相互近邻图，改进的相对距离的计算方式如下：

{\delta }_i^{\text{'}}=\left\{\begin{array}{cc}\underset{j:{\rho }_j^{\text{'}}>{\rho }_i^{\text{'}}}{\mathrm{m}\mathrm{i}\mathrm{n}}{d}_{ij},& \forall x_i\notin DP,\exists x_j\in N_k\left(x_i\right),{\rho }_j^{\text{'}}>{\rho }_i^{\text{'}}\\ \underset{j:{\rho }_j^{\text{'}}>{\rho }_i^{\text{'}}}{\mathrm{m}\mathrm{i}\mathrm{n}}{d}_{G_{m}ij},& \forall x_i\in DP,\exists x_j\in X,{\rho }_j^{\text{'}}>{\rho }_i^{\text{'}}\\ \underset{j\ne i}{\mathrm{m}\mathrm{a}\mathrm{x}}{\delta }^{\text{'}},& \mathrm{其他}\end{array}\right.(16)

其中，d_{G_{m}ij}为相互近邻图中某局部密度峰到更高密度样本的最短路径长度，{\delta }^{\text{'}}为样本相对距离的集合.

根据式（16），局部密度峰的相对距离取其到所有更高密度样本最短路径的最小值，最短路径由Dijkstra算法^［31］求解.图2是k=\mathrm{10}时，Flame数据集上构建的相互近邻图，其中，黄色样本代表局部密度峰，A，B和C三个局部密度峰沿紫色路径分别确定了最近高密度样本F，D和G，路径长度即为对应的相对距离.对于局部密度最大的样本，其相对距离取所有样本相对距离的最大值.需要说明，在相互近邻图中可能出现部分局部密度峰与所有更高密度样本均无连通路径，这类局部密度峰为“孤立峰”，其局部范围内已形成较稳定的小类簇结构，属于潜在聚类中心.为了实现相对距离的有效量化，将“孤立峰”的相对距离同样设为全局最大的相对距离，以突出其在决策值图中的聚类中心特征.

利用式（12）与式（16）分别计算各样本的局部密度和相对距离后，MDS⁃DPC依据样本决策值大小选取聚类中心.和原始DPC算法相比，MDS⁃DPC算法能够在存在簇间密度差异的Jain数据集上识别出低密度类簇的聚类中心.

3.3　基于证据理论和跨簇连接样本微调的分配策略

DPC算法采用基于样本局部密度偏序关系的一步分配策略，容错性较差，分配错误容易级联传播，引发“多米诺效应”，影响聚类效果.对此，引入证据理论，通过多阶段分配与跨簇连接样本分层微调策略来提升样本分配的准确性.

首先，聚类中心确定后，将各聚类中心的k近邻直接划分至该中心所属的类簇中，快速形成各类簇的核心区域，为后续扩展提供初始种子点.随后，进入队列引导的扩展阶段，将已分配样本加入队列Q，依次取队首样本x_i遍历其k近邻.对于k近邻中未分配的样本x_j，计算其与x_i的距离d_{ij}，并与样本x_i的局部自适应距离阈值{\overline{d}}_i比较.该阈值定义为样本x_i到其k近邻的平均距离，即：

{\overline{d}}_i=\frac{\mathrm{1}}{k}\sum _{x_j\in N_k(x_i)}{d}_{ij}(17)

若d_{ij}\le {\overline{d}}_i，则将x_j划入x_i所在类簇，并将x_j加入队尾，作为后续扩展的新起点.

重复上述步骤，直至队列Q为空.两阶段执行完毕后，初始类簇形成.

对于前两阶段尚未分配的样本，基于证据理论完成更准确的分配.具体地，对于每个未分配的样本x_p计算其属于各已知类簇的归属概率.以类簇集合\Theta =\left\{C_{\mathrm{1}},C_{\mathrm{2}},\cdots ,C_s\right\}为识别框架，其中，C_i表示第i个类簇.证据来源于未分配样本x_p的k近邻x_q\in N_k\left(x_p\right),若样本x_q已划入类簇C_i，则其支持样本x_p归属于C_i的基本信度分配为{\mu }^{x_p,x_q}\left(C_i\right)={\omega }_{pq}.计算方式如下：

{\omega }_{pq}=\frac{\mathrm{1}}{\mathrm{1}+d{}_{pq}{}^{}}\cdot \frac{\mathrm{m}\mathrm{i}\mathrm{n}\left\{{\rho }_p^{\text{'}},{\rho }_q^{\text{'}}\right\}}{\mathrm{m}\mathrm{a}\mathrm{x}\left\{{\rho }_p^{\text{'}},{\rho }_q^{\text{'}}\right\}}(18)

其中，\frac{\mathrm{1}}{\mathrm{1}+d{}_{pq}{}^{}}以距离倒数量化几何位置上的邻近性证据，证据与待分配样本越靠近，提供的证据可靠性越强；\frac{\mathrm{m}\mathrm{i}\mathrm{n}\left\{{\rho }_p^{\text{'}},{\rho }_q^{\text{'}}\right\}}{\mathrm{m}\mathrm{a}\mathrm{x}\left\{{\rho }_p^{\text{'}},{\rho }_q^{\text{'}}\right\}}可对比待分配样本与证据样本的局部密度，二者密度越相近，比值越接近1，该证据样本对待分配样本的类簇归属越具参考价值.已分配的近邻样本对识别框架整体的不确定性赋值{\mu }^{x_p,x_q}\left(\Theta \right)=\mathrm{1}-{\omega }_{pq}，若某近邻样本尚未分配，对应的基本信度为{\mu }^{x_p,x_q}\left(\Theta \right)=\mathrm{1}.

使用Dempster融合规则，根据式（6）融合k近邻证据，即{\mu }^{x_p}={\mu }^{x_p,x_{q\mathrm{1}}}\oplus {\mu }^{x_p,x_{q\mathrm{2}}}\oplus \cdots \oplus {\mu }^{x_p,x_{qk}},将当前两个证据的融合结果和下一个证据融合，经过k-\mathrm{1}次两两合并得到综合信度.最后，利用式（7）进行Pignistic概率转换，得到未分配样本属于各类簇的归属概率.基于证据理论的分配过程整体以概率驱动，采用迭代的方式推进.每一轮从所有未分配的样本中选出当前归属某个类簇概率值最高的样本，将其分配到该概率值对应的类簇中，同时，将该样本对于所有类簇的归属概率置为负无穷大.样本的归属确定后，部分样本k近邻证据情况发生变化，这类受影响的样本定义如下.

定义6

受影响样本 给定数据X=\left\{x_{\mathrm{1}},x_{\mathrm{2}},\right.

\left.\cdots ,x_n\right\}和当前被分配到类簇C_i的样本x_t，若某未分配样本x_r的k近邻中包含样本x_t，则x_r为受样本x_t影响的样本.所有受x_t影响的样本可表示为：

R\left(x_t\right)=\left\{x_r\in X\left|\exists x_t\in N_k\left(x_r\right),I\left(x_r\right)=-\mathrm{1}\right.\right\}(19)

其中，I\left(x_r\right)代表样本x_r的标签，I\left(x_r\right)=-\mathrm{1}代表样本x_r暂未被分配.当样本x_t的类簇归属确定后，x_t转变为一个确定证据，因此需要重新计算受影响样本x_r的归属概率.重复上述过程，直到所有样本均被分配.

在聚类过程中，跨簇连接样本的密度与距离特征同相邻类簇样本比较相似，易使其在相邻类簇间的归属概率接近.若仅依据概率大小进行分配，此类样本极易被误分.因此，有必要对其进行识别并执行二次分配.本文所提算法认为，跨簇连接样本通常分布在类簇边界，局部密度较低，且其相互近邻中同时包含来自不同类簇的样本.基于上述特征，跨簇连接样本的定义如下.

定义7

跨簇连接样本 给定数据X=\left\{x_{\mathrm{1}},\right.

\left.x_{\mathrm{2}},\cdots ,x_n\right\}，若存在样本x_i\in X，满足其局部密度{\rho }_i^{\text{'}}低于阈值\overline{\rho }，且在其相互近邻中存在与样本x_i不同标签的样本x_j，则称x_i为跨簇连接样本.所有跨簇连接样本可表示为：

(20)

其中，阈值\overline{\rho }为全局所有样本局部密度的平均值，即：

\overline{\rho }=\frac{\mathrm{1}}{n}\sum _{x_i\in X}{\rho }_i^{\text{'}}(21)

跨簇连接样本通常位于多簇交界区域，类簇归属不确定性较强.基于证据理论融合此类样本的k近邻信息，其中，非跨簇近邻对识别框架\Theta的基本信度与前文计算方式保持一致，跨簇近邻需微调标签，目前归属也未确定，故提供\mu \left(\Theta \right)=\mathrm{1}的不确定性.融合后，以对识别框架\Theta的综合信度对此类样本的归属不确定性进行量化，即：

u_i={\mu }^{x_i}\left(\Theta \right)(22)

其中，u_i的值越大，表示样本归属不确定性越高.

设跨簇连接样本总数为M=\left|\Gamma \right|，对不同的不确定性样本实施差异化处理.将所有跨簇连接样本按不确定性升序排列，得到排序集合{\Gamma }_{\mathrm{s}\mathrm{o}\mathrm{r}\mathrm{t}}=\left\{x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_M\right\}，其中u_{\mathrm{1}}\le u_{\mathrm{2}}\le \cdots \le u_M.采用四分位数25%和75%将其划分为三个不确定层次，如式（23）所示：

\left\{\begin{array}{l}{\Gamma }_{\mathrm{l}\mathrm{o}\mathrm{w}}={\Gamma }_{\mathrm{s}\mathrm{o}\mathrm{r}\mathrm{t}}\left[\mathrm{1}:q_{\mathrm{25}\mathrm{\%}}\right]\\ {\Gamma }_{\mathrm{m}\mathrm{i}\mathrm{d}}={\Gamma }_{\mathrm{s}\mathrm{o}\mathrm{r}\mathrm{t}}\left[q_{\mathrm{25}\mathrm{\%}}+\mathrm{1}:q_{\mathrm{75}\mathrm{\%}}\right]\\ {\Gamma }_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}={\Gamma }_{\mathrm{s}\mathrm{o}\mathrm{r}\mathrm{t}}\left[q_{\mathrm{75}\mathrm{\%}}+\mathrm{1}:M\right]\end{array}\right.(23)

其中，{\Gamma }_{\mathrm{l}\mathrm{o}\mathrm{w}},{\Gamma }_{\mathrm{m}\mathrm{i}\mathrm{d}}\mathrm{和}{\Gamma }_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}分别代表低、中和高不确定层次样本；q_{\mathrm{25}\mathrm{\%}}=⌊\mathrm{25}\mathrm{\%}M⌋和q_{\mathrm{75}\mathrm{\%}}=⌊\mathrm{75}\mathrm{\%}M⌋分别代表下四分位和上四分位样本位置，⌊\cdot ⌋代表向下取整.

对于低不确定层次样本，直接保留上一阶段的分配结果，不做修正.在处理后续样本前，先将中与高不确定层次样本统一置为未分配状态，标签设为-1.对于中不确定层次样本，按局部密度降序排列后，依次分配至最近高密度样本所在类簇.若该样本尚未分配，则沿密度链向上追溯一级，以该样本的最近高密度样本为分配依据，若仍无法分配则延迟处理.对于高不确定层次样本，按局部密度降序排列后，依次分配至相互最近邻所在类簇中.若相互最近邻尚未分配，同样延迟处理.最后，对所有延迟处理的样本采用多数投票机制，以其k近邻中出现频次最高的标签作为最终类别.

3.4　算法步骤

根据3.1~3.3，MDS⁃DPC的算法流程如图3所示，算法描述如下所示.

1.对数据集X进行最小⁃最大归一化处理，初始化所有样本x_i\in X标签I\left(x_i\right)\leftarrow -\mathrm{1};

2.根据式（12）和式（16）分别计算每个样本的局部密度和相对距离；

3.根据式（4）计算所有样本的决策值并按降序排序；

4.选取决策值前s个样本作为聚类中心\left\{C_{\mathrm{1}},C_{\mathrm{2}},\cdots ,\right.

\left.C_s\right\},设I\left(C_i\right)\leftarrow i，并存入已分配集合S_a；

5.将所有聚类中心的k近邻样本标签置为i，并存入已分配集合S_a和队列Q；

6.while Q\ne \mathrm{\varnothing } do

7. 取出队首元素x_i，遍历其k近邻，找到d_{ij}\le {\overline{d}}_i且未分配的样本x_j；

8. I\left(x_j\right)\leftarrow I\left(x_i\right),S_a\leftarrow S_a\bigcup \left\{x_j\right\}并将x_j加入队列Q;

9.end while；

10.确定当前未分配样本X-S_a，以其各自的k近邻为证据源，根据式（7）初始化归属概率矩阵A；

11.repeat

12. 找出A中概率最大值对应的样本x_p和类簇C_i，将I\left(x_p\right)\leftarrow I\left(C_i\right),S_a\leftarrow S_a\bigcup \left\{x_p\right\},同时将矩阵A中的样本x_p对所有类簇的归属概率置为负无穷大；

13. 根据式（19）确定受影响的样本集合R\left(x_p\right)，重新计算其归属概率并更新矩阵A；

14.until \left|S_a\right|=\left|X\right|；

15.根据式（20）识别跨簇连接样本集合\Gamma；

16.if \Gamma \ne \mathrm{\varnothing } then

17. 根据式（22）计算\Gamma中各样本的不确定性，并按式（23）划分为{\Gamma }_{\mathrm{l}\mathrm{o}\mathrm{w}}，{\Gamma }_{\mathrm{m}\mathrm{i}\mathrm{d}}，{\Gamma }_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}；

18. 对于{\Gamma }_{\mathrm{m}\mathrm{i}\mathrm{d}}样本，按局部密度降序排序，沿其最近高密度路径链追溯分配，若均未分配则存入集合\phi；

19. 对于{\Gamma }_{\mathrm{h}\mathrm{i}\mathrm{g}\mathrm{h}}样本，按局部密度降序排序，分配到其相互最近邻所在类簇，若相互最近邻未分配则存入集合\phi；

20. 对于\phi集合，按局部密度降序排序，根据样本k近邻中出现频率最高的标签进行多数表决分配；

21.end if；

22.返回最终聚类结果C.

算法时间的复杂度主要由五个部分决定.

聚类中心识别的时间复杂度为O\left(n\mathrm{l}\mathrm{g}n+\right.

\left.n{k}^{\mathrm{2}}+mnk\mathrm{l}\mathrm{g}n\right),其中，m为局部密度峰的数量，与k的选取有关.聚类中心k近邻扩散的时间复杂度为O\left(sk\right)，其中，s为类簇数量.队列引导簇生长的时间复杂度为O\left(nk\right).证据理论融合和分配的时间复杂度为O\left(n^{\mathrm{2}}{k}^{\mathrm{2}}s\right).跨簇连接样本识别和微调的时间复杂度为O\left(nk+n\mathrm{l}\mathrm{g}n\right).所提算法总的时间复杂度为O\left(mnk\mathrm{l}\mathrm{g}n+n^{\mathrm{2}}{k}^{\mathrm{2}}s\right).

4 实验与分析

4.1　实验设置

为了评估MDS⁃DPC算法的聚类性能，在九个合成数据集和12个真实数据集上进行对比实验，数据集的基本信息如表1所示.对比算法包括OPTICS^［32］，DPC^［15］，DPC⁃CE^［20］，DPC⁃DVND^［16］，DBSCAN⁃DPC^［25］和DPC⁃MFP^［27］.其中，OPTICS和DPC为经典的密度聚类算法，OPTICS直接调用pyclustering库实现，DPC参照原论文核心思路复现.DPC⁃DVND和DPC⁃MFP为基于近邻关系的DPC改进算法.DPC⁃CE利用连通性距离优化了DPC中有关距离的度量方式.DBSCAN⁃DPC是借助DBSCAN优化DPC分配策略的联合聚类方法.以上算法代码均由原作者提供.为了消除量纲差异和统一数值尺度，所有数据集均经过最小⁃最大归一化处理后再输入各算法.聚类性能的评价指标使用ARI （Adjusted Rand Index）^［33］，NMI （Normalized Mutual Information）^［34］和FMI （Fowlkes⁃Mallows Index）^［35］，各指标数值越接近1，聚类效果越好.

4.2　算法参数设置

为了保证实验结果的可比性，所有对比算法都经过参数调优，取其在最优参数组合下的指标值.其中，OPTICS邻域半径搜索区间为\left[\mathrm{0.01,1}\right],步长为0.01；最小样本数区间为\left[\mathrm{1,40}\right],步长为1.DPC截断距离占比区间为\left[\mathrm{1}\mathrm{\%},\mathrm{2}\mathrm{\%}\right],步长为0.1%.DPC⁃CE采用原论文默认参数，截断距离为2%，决策阈值为0.25，惩罚因子为0.3.在DPC⁃DVND与DPC⁃MFP算法的原论文中，k近邻数搜索区间为\left[\mathrm{1,50}\right],步长为1.为了统一对比，MDS⁃DPC中k值的选取范围与上述两种算法保持一致.此外，DPC⁃MFP中同源特征样本数量阈值的取值区间为\left[\mathrm{1,30}\right],步长为1.DBSCAN⁃DPC参照原论文设置，最近邻比例区间为\left[\mathrm{0.026,0.028}\right],步长为0.001；最近邻数区间为\left[\mathrm{3,20}\right],步长为1；最小样本数固定为4.

4.3　合成数据集实验结果分析

选取的九个合成数据集覆盖多种数据分布，可验证算法处理复杂数据的聚类性能.各算法在合成数据集上的实验结果如表2所示，其中，粗体字表示最优值，Arg⁃表示最优参数.

因篇幅限制，图4和图5仅可视化了各算法在Jain和Aggregation数据集上的聚类结果，其中，星号代表算法选择的类簇中心，叉号代表被识别为噪声的样本.

Jain和Cth数据集中类簇存在密度差异.由图4可见，Jain数据集中稀疏类簇内样本间距较大，OPTICS受局部稀疏性影响，导致密度可达链断裂，将单一类簇误拆分为两个子簇，产生了聚类偏差.DPC在密集类簇中误识多个类簇中心，严重干扰了后续非中心样本的分配，聚类效果低于其他算法.其余算法均能有效克服密度差异，实现精准聚类.在Cth数据集上，OPTICS沿密度可达路径成功识别了真实类簇结构，各项指标达到最优值1.DPC⁃CE虽然能准确识别各类簇中心，但误将外部环形类簇中的部分样本与内部球形类簇样本视为连通，触发了补偿机制，造成样本类别错误绑定.其余算法采用近邻扩散分配或形成特征样本集合的方式，有效刻画了簇结构和簇内连通性，获得了与真实类簇分布一致的聚类结果.

Flame数据集中间簇的边界模糊，过渡样本较多.MDS⁃DPC借助分层微调策略，有效处理了簇间交界样本.DPC⁃MFP首先生成稳定的簇核心，为边界样本的分配提供了可靠的依据，再将不确定性样本归属至最近的高密度簇核心所在类簇，提高了样本的分配精度.DPC⁃DVND综合了密度差异与扩散距离规则来实现邻域标签扩散，降低了边界区域样本的误分概率.上述三种算法在Flame数据集上均实现了完全正确的聚类.DBSCAN⁃DPC由于固定邻域与最小样本数约束难以适配模糊边界，交界样本易被误判为噪声或被跨簇误分，导致聚类结果失真.在该数据集上，OPTICS的聚类性能优于DPC与DBSCAN⁃DPC算法.

Aggregation和2circles_noise数据集中存在类簇粘连现象.由图5可见，在Aggregation数据集上，除了DPC以外，其余算法仅误分少量桥接样本.其中，MDS⁃DPC与DPC⁃MFP的表现最优，DPC⁃CE与DPC⁃DVND的性能持平，为次优算法，整体聚类效果良好.在2circles_noise数据集上，除了DPC与DPC⁃CE以外，各算法聚类结果与真实类簇分布完全匹配.MDS⁃DPC，DPC⁃MFP及DPC⁃DVND通过优化分配策略，有效提升了桥接样本分配的准确性，避免了跨簇误分.由于2circles_noise数据集中桥接样本间距较大，OPTICS将密度可达范围控制在簇内，在该数据集上的表现较好.DPC⁃CE在2circles_noise数据集上，受环形结构嵌套及桥接样本与噪声特征接近的影响，连通性判断失效，且距离补偿加剧了跨环误分问题，聚类效果较差.

Blobs与D31数据集中的类簇呈近球形分布，且存在簇间重叠现象.MDS⁃DPC在Blobs数据集上表现最优，在D31数据集上的聚类效果虽略逊于DPC⁃MFP，但各项评价指标的最大差值仅为0.2%，性能接近.DPC算法对此类近球形且密度均匀的类簇具有良好的适配性，聚类效果良好.OPTICS算法受簇间重叠影响，其密度可达范围跨簇，导致聚类精度降低.DPC⁃DVND邻域扩散受标签混杂干扰，标签错误传播风险增大，使其聚类性能不佳.其余算法聚类效果介于OPTICS与最优算法之间.

CMC数据集包含球形与流形混合类簇，Atom数据集中的类簇呈三维嵌套特征.在CMC数据集上，OPTICS存在轻微聚类偏差，DPC难以有效处理流形类簇上的样本.DPC⁃CE因连通性判断失误导致部分样本被错分，其余算法均聚类正确.在Atom数据集上，DPC出现多米诺效应，DPC⁃CE和DBSCAN⁃DPC分别因连通性和可达性误判，样本分配的准确性降低.以上三种算法在该数据集上均未获得正确的聚类结果.

整体上，MDS⁃DPC算法在多个合成数据集上取得了最优聚类效果，表明其具备处理簇间密度差异、簇间边界模糊和复杂形状类簇的能力.

4.4　真实数据集实验结果分析

选取12个涵盖低维简单结构、高维小样本、类别不均衡和多类别复杂分布特点的UCI数据集，进一步验证算法在真实数据上的聚类能力.各算法在真实数据集上的实验结果如表3所示，表中粗体字表示最优值，Arg⁃表示最优参数.

Iris与Seeds数据集属于低维简单结构数据集，类别分布均衡，类簇间仅存在轻微重叠.在Iris数据集上，MDS⁃DPC，DPC⁃DVND与DPC⁃MFP均取得最优聚类结果.在Seeds数据集上，MDS⁃DPC的聚类效果仅次于DPC⁃MFP，较OPTICS和DPC提升显著.表明MDS⁃DPC与DPC⁃MFP均可识别数据的类簇结构，且能对类别重叠区域实现较准确的聚类.

Wine与Parkinsons数据集的样本规模较小，但数据维度较高.MDS⁃DPC在这两个数据集上分别取得最优与次优聚类结果，可较好地适配高维小样本的数据特性.与DPC⁃MFP相比，MDS⁃DPC的各项聚类指标差值均控制在2.5%以内，二者性能接近.

Vehicle与Dermatology数据集内部分布复杂，Vote数据集虽然为二分类数据，但特征以离散值为主，数据分布同样较复杂.在Vehicle数据集上，MDS⁃DPC仅NMI略低于DPC⁃MFP.在Dermatology数据集上，MDS⁃DPC聚类效果较好，ARI指标较次优算法DPC⁃MFP提升约10%.在Vote数据集上，MDS⁃DPC的三项评价指标均为最优.实验结果表明该算法在复杂分布及离散特征数据上具有较好的适配性.

German与Yeast数据集存在类别分布不均衡的问题.MDS⁃DPC在该类数据集上整体表现优于多数对比算法.在German数据集上，MDS⁃DPC的聚类效果与DPC⁃MFP接近.在Yeast数据集上，MDS⁃DPC有两项指标优于其余对比算法.实验结果表明，该算法对类别不均衡数据具备良好的处理能力.

Abalone，Waveform与Satellite数据集样本规模较大.在Abalone数据集上，MDS⁃DPC性能虽略低于OPTICS，但优于其余对比算法，在Waveform数据集上获得了最优的聚类结果.仅在Sa⁃tellite数据集上，DPC⁃CE的性能表现更为突出，MDS⁃DPC与该算法存在性能差距.

整体上，OPTICS与DPC在多数数据集上性能表现较弱，尤其在高维、多类别及类别不均衡数据集上，性能下降明显.DPC⁃CE与DBSCAN⁃DPC虽在部分数据集上具有一定效果，但在高维、复杂分布场景中也存在一定局限.相比之下，MDS⁃DPC，DPC⁃MFP和DPC⁃DVND在多数数据集上的聚类效果较好，整体性能更加稳定.

4.5　参数分析

本文提出的算法需要设置近邻数k.分别选取具有不同结构与分布特征的五个合成数据集和五个真实数据集，以NMI为评价指标，测试k在\left[\mathrm{1,50}\right]变化时算法的聚类效果，实验结果如图6所示.

整体上，当时，由于样本邻域范围较小，可利用的局部信息不足，算法在多数数据集上聚类效果较差.随着k的增大，邻域信息逐渐充分，NMI呈明显上升趋势.当k在\left[\mathrm{5,35}\right]取值时，合成数据集与真实数据集的NMI整体维持在较高水平，且各数据集的最优NMI均可在该区间取到，说明该区间的k值能较好地平衡局部与全局分布，对不同特征的数据均有较好的适配能力.尽管部分数据集在此区间内存在小幅波动，但在该区间内取多数k值时，算法性能优于时的小邻域场景.当k>\mathrm{35}时，部分数据集的NMI出现波动或下降，主要原因可能是邻域范围过大，引入了大量无关样本，削弱了样本的局部结构特征，导致聚类效果不稳定.

实验结果表明，近邻数k对算法的聚类效果有一定影响.受数据分布与结构的影响，算法在不同数据集上的最优k值存在差异，但其最优值普遍出现在\left[\mathrm{5,35}\right].

综上，在合理的参数搜索范围内\left(\left[\mathrm{1,50}\right]\right),所提算法可获得较优的聚类结果.

5 结论

本文提出一种基于相互近邻和证据理论的密度峰值聚类算法MDS⁃DPC，解决DPC算法难以识别稀疏类簇的聚类中心和样本分配策略容错性较低的问题.通过融合样本距离相似性和邻域凝聚度来重新定义局部密度的计算方式，算法有效平衡了样本间的密度差异.此外，将欧氏距离和相互近邻图距离相结合，差异化确定局部和非局部密度峰的相对距离，更准确地反映了样本间的相对位置关系.同时，引入证据理论，充分考虑已分配样本信息，采用多阶段分配和跨簇连接样本分层微调策略，有效缓解了“多米诺效应”的影响.未来将尝试与粒球计算相结合，提升算法在大规模数据中的聚类表现.

参考文献

[1] 陈斌，谢文波，付勋，等. 基于改进局部密度的可扩展层次聚类算法. 南京大学学报(自然科学)，2024，60(3)：370-382.

[2] 王英楠，郑文萍，杨贵. 基于双视角网络嵌入聚类集成社区发现算法. 山东大学学报(工学版)，2025，55(1)：41-50.

[3] Zhang W T， Wang W X， Shang R H，et al. Overlapping community detection based on graph attention autoencoder and self⁃trained clustering. Applied Soft Computing，2025，183：113584.

[4] Ma Y C， Shi K Z， Peng X P，et al. Deep graph clustering with triple fusion mechanism for community detection. IEEE Transactions on Computational Social Systems，2025，12(4)：1743-1758.

[5] Ni Y T， Qian J， Chen E H，et al. GBK⁃DPC：Density peak clustering based on granular ball with k⁃nearest neighbor. Pattern Recognition，2026，171(Part B)：112243.

[6] 薛任煊，伊士超，王平心. GBDEN：一种基于粒球的大规模数据快速聚类方法. 计算机科学，2024，51(12)：166-173.

[7] Zeng Z， Zhao Z Y， Xu K X，et al. CoIn：Correlation induced clustering for cognition of high dimensional bioinformatics data. IEEE Journal of Biomedical and Health Informatics，2023，27(2)：598-607.

[8] Gu Z G， Hübschmann D. simplifyEnrichment：A bioconductor package for clustering and visualizing functional enrichment results. Genomics，Proteomics & Bioinformatics，2023，21(1)：190-202.

[9] Zhang Z T， Chen X J， Wang C，et al. Structured multi⁃view k⁃means clustering. Pattern Recognition，2025，160：111113.

[10] Long J W， Wang Q， Liu L P. A robust hierarchical clustering algorithm for automatic identification of clusters. Applied Intelligence，2025，55(7)：497.

[11] 代少升，刘小兵，赖智颖，等. 网格化局部自适应DBSCAN聚类算法. 重庆邮电大学学报(自然科学版)，2022，34(2)：250-257.

[12] Zhou X R， Zhang Q H， Zhao F，et al. A novel multi⁃granularity clustering algorithm based on grid partition and fuzzy quotient space. IEEE Transactions on Fuzzy Systems，2026，34(1)：311-323.

[13] Feng R X， Zhong C M， Qian J B，et al. A fair spectral clustering with weighted fairness constraints. Pattern Recognition，2026，173：112821.

[14] Chowdhury A R， Gupta A， Das S. Deep multi⁃view clustering：A comprehensive survey of the contem⁃porary techniques. Information Fusion，2025，119：103012.

[15] Rodriguez A， Laio A. Clustering by fast search and find of density peaks. Science，2014，344(6191)：1492-1496.

[16] Zang W K， Che J， Ma L L，et al. Density peaks clustering based on density voting and neighborhood diffusion. Information Sciences，2024，681：121209.

[17] Xie J Y， Liu X L， Wang M Z，et al. SFKNN⁃DPC：Standard deviation weighted distance based density peak clustering algorithm. Information Sciences，2024，653：119788.

[18] Guo X F， Liu Q， Huang C Q，et al. Density peaks clustering algorithm via fusing natural neighbor and fuzzy information. Neurocomputing，2025，653：131152.

[19] Deng C， Zhang Q H， Zhou X R，et al. Density peaks clustering algorithm integrating manifold distance and mutual nearest neighbors. Pattern Recognition，2026，172(Part B)：112554.

[20] Guo W J， Wang W H， Zhao S P，et al. Density peak clustering with connectivity estimation. Knowledge⁃Based Systems，2022，243：108501.

[21] 陈梅，魏礼磊，尤远毓秀，等. 基于k近邻图的密度峰值聚类算法. 控制与决策，2025，40(7)：2242-2250.

[22] Ding L， Li C， Ding S F，et al. Robust density peaks clustering for manifold data with multiple peaks. IEEE Transactions on Pattern Analysis and Machine Intelligence，2025，47(11)：10696-10708.

[23] Xie J Y， Chen X H， Wang M Z，et al. SMFK⁃DPC：Enhanced density peak clustering by the weighted Manhattan distance. Knowledge⁃Based Systems，2026，332：114871.

[24] 张清华，周靖鹏，代永杨，等. 基于代表点与K近邻的密度峰值聚类算法. 软件学报，2023，34(12)：5629-5648.

[25] Hou J， Lin H S， Yuan H Q，et al. Flexible density peak clustering for real⁃world data. Pattern Recognition，2024，156：110772.

[26] Xie J Y， Yan H， Wang M Z，et al. WANN⁃DPC：Density peaks finding clustering based on weighted adaptive nearest neighbors. Pattern Recognition，2026，170：111953.

[27] Zang W K， Liu X C， Ma L L，et al. DPC⁃MFP：An adaptive density peaks clustering algorithm with multiple feature points. Neurocomputing，2025，618：129060.

[28] Gan H T， Yang Z， Zhou R，et al. Safe semi⁃supervised clustering based on Dempster⁃Shafer evidence theory. Engineering Applications of Artificial Intelligence，2023，123(Part B)：106334.

[29] Wang J F， Zhao W L， Xiao S H，et al. Dynamic NN⁃Descent：An efficient kNN graph construction method. IEEE Transactions on Big Data，2025，11(2)：879-886.

[30] Wang Y Z， Pang W， Jiao Z X，et al. An adaptive mutual k⁃nearest neighbors clustering algorithm based on maximizing mutual information. Pattern Recognition，2023，137：109273.

[31] Duan R， Mao J Y， Mao X，et al. Breaking the sorting barrier for directed single⁃source shortest paths∥Proceedings of the 57^th Annual ACM Symposium on Theory of Computing.New York，NY，USA：Association for Computing Machinery，2025：36-44.

[32] Ankerst M， Breunig M M， Kriegel H P，et al. OPTICS：Ordering points to identify the clustering structure∥Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data. New York，NY，USA：Association for Computing Machinery，1999：49-60.

[33] Vinh N X， Epps J， Bailey J. Information theoretic measures for clusterings comparison：Variants，properties，normalization and correction for chance. Journal of Machine Learning Research，2010，11：2837-2854.

[34] Wang Y， Hu B G. Derivations of normalized mutual information in binary classifications∥2009 6th International Conference on Fuzzy Systems and Knowledge Discovery. Tianjin，China：IEEE，2009：155-163.

[35] Fowlkes E B， Mallows C L. A method for comparing two hierarchical clusterings. Journal of the American Statistical Association，1983，78(383)：553-569.

[36] Wang Y Z， Qian J X， Hassan M，et al. Density peak clustering algorithms：A review on the decade 2014-2023. Expert Systems with Applications，2024，238：121860.

[37] Cheng D D， Zhang S L， Huang J L，et al. Dense members of local cores⁃based density peaks clustering algorithm. Knowledge⁃Based Systems，2020，193：105454.

[38] Seyedi S A， Lotfi A， Moradi P，et al. Dynamic graph⁃based label propagation for density peaks clustering. Expert Systems with Applications，2019，115：314-328.

[39] Dua D， Graff C. UCI machine learning repository. Irvine：School of Information and Computer Science，University of California. https：//archive.ics.uci.edu/ml/,2019.

基金资助

国家重点研发计划(2026YFE0201300)

国家自然科学基金(62576056)

重庆市自然科学基金创新发展联合基金(CSTB2023⁃NSCQ⁃LZX0164)

重庆市教委科学技术研究(KJZD⁃K202300613)