面向密度分布不均数据的加权逆近邻密度峰值聚类算法

吕莉,  陈威,  肖人彬,  韩龙哲,  谭德坤

downloadPDF
吕莉, 陈威, 肖人彬, 等. 面向密度分布不均数据的加权逆近邻密度峰值聚类算法 [J]. 智能系统学报, 2024, 19(1): 165-175. doi: 10.11992/tis.202212015
引用本文: 吕莉, 陈威, 肖人彬, 等. 面向密度分布不均数据的加权逆近邻密度峰值聚类算法 [J]. 智能系统学报, 2024, 19(1): 165-175. doi: 10.11992/tis.202212015
shu
LYU Li, CHEN Wei, XIAO Renbin, et al. Density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets [J]. CAAI Transactions on Intelligent Systems, 2024, 19(1): 165-175. doi: 10.11992/tis.202212015
Citation: LYU Li, CHEN Wei, XIAO Renbin, et al. Density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets [J]. CAAI Transactions on Intelligent Systems, 2024, 19(1): 165-175. doi: 10.11992/tis.202212015
shu

面向密度分布不均数据的加权逆近邻密度峰值聚类算法

doi: 10.11992/tis.202212015
  • 1.

    南昌工程学院 信息工程学院, 江西 南昌 330099;

  • 2.

    南昌工程学院 南昌市智慧城市物联感知与协同计算重点实验室, 江西 南昌 330099;

  • 3.

    华中科技大学 人工智能与自动化学院, 湖北 武汉 430074

基金项目: 国家自然科学基金项目(62066030); 江西省重点研发计划项目(20192BBE50076，20203BBGL73225); 江西省教育厅科技项目(GJJ190958).
详细信息
    作者简介:

    吕莉，教授，博士，主要研究方向为智能计算与计算智能、目标跟踪与检测、大数据与人工智能。 主持国家自然科学基金项目2项，发表学术论文80余篇。E-mail：lvli623@163.com;

    陈威，硕士研究生， 主要研究方向为数据挖掘。E-mail：chenwei9801@163.com;

    肖人彬，教授，博士生导师，主要研究方向为群体智能、大规模个性化定制、复杂系统与复杂性科学。主持国家自然科学基金项目11项，主持获得教育部自然科学奖1项和湖北省自然科学奖及科技进步奖4 项，发表学术论文300余篇。出版学术专著和教 材10余部。E-mail：rbxiao@hust.edu.cn.

    通讯作者:

    吕莉. E-mail：lvli623@163.com.

  • 中图分类号: TP301

Density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets

  • 1.

    School of Information Engineering, Nanchang Institute of Technology, Nanchang 330099, China;

  • 2.

    Nanchang Key Laboratory of IoT Perception and Collaborative Computing for Smart City, Nanchang Institute of Technology, Nanchang 330099, China;

  • 3.

    School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China

    摘要
  • 摘要: 针对密度分布不均数据，密度峰值聚类算法易忽略类簇间样本的疏密差异，导致误选类簇中心；分配策略易将稀疏区域的样本误分到密集区域，导致聚类效果不佳的问题，本文提出一种面向密度分布不均数据的加权逆近邻密度峰值聚类算法。该算法首先在局部密度公式中引入基于sigmoid函数的权重系数，增加稀疏区域样本的权重，结合逆近邻思想，重新定义了样本的局部密度，有效提升类簇中心的识别率；其次，引入改进的样本相似度策略，利用样本间的逆近邻及共享逆近邻信息，使得同一类簇样本间具有较高的相似度，可有效改善稀疏区域样本分配错误的问题。在密度分布不均、复杂形态和UCI数据集上的对比实验表明，本文算法的聚类效果优于IDPC-FA、FNDPC、FKNN-DPC、DPC和DPCSA算法。

     

    Abstract: For data with uneven density distribution, the density peak clustering algorithm disregards the sparsity difference among intercluster samples, causing an inaccurate selection of the cluster center. Moreover, the allocation strategy easily divides the samples in sparse areas into dense areas by mistake, leading to a poor clustering effect. Therefore, the density peak clustering algorithm based on the weighted reverse nearest neighbor (DPC-WR) against datasets with uneven density distribution is proposed in this paper. First, the weight coefficient based on the sigmoid function is introduced to the local density formula to increase the weight of samples in sparse areas. Combined with the concept of reverse nearest neighbor, the local density of samples is then redesigned to improve the recognition rate of cluster centers effectively. Second, an improved sample similarity strategy is introduced, which utilizes reverse nearest neighbors and shares this neighbor’s information between samples to increase the similarity of samples in the same cluster. This effectively solves the problem of sample allocation error in sparse areas. Experiments on uneven density distribution, complex morphology, and UCI datasets show that the clustering effect of the DPC-WR algorithm outperforms that of IDPC-FA, FNDPC, FKNN-DPC, DPC, and DPCSA algorithms.

     

    • HTML全文

  • 聚类是数据分析中一种重要的无监督学习方法，致力于揭示看似杂乱无章的未知数据背后隐藏的内在属性和规律，为决策提供支持，并已成功应用于许多领域，如图像分析[1]、模式识别[2]、社会网络挖掘[3]、市场统计分析[4]和医学研究[5]等。

    传统的聚类算法分为基于划分的[6]、基于层次的[7]、基于网格的[8]、基于模型的[9]和基于密度的[10]聚类算法。K-means[11]是最著名的划分聚类算法，通过多次迭代获得最优聚类中心。K-means收敛速度快，对大规模数据集的处理效率高，但该算法的性能依赖于初始聚类中心的选择，且对噪声点和异常值敏感。BIRCH(balanced iterative reducing and clustering using hierarchies)[12]是一种基于层次的聚类算法，利用聚类特征树自底向上进行聚类。BIRCH聚类速度快，能识别噪声点，但不适用于高维和非凸数据。CLIQUE(clustering in quest)[13]是一种基于网格的聚类算法，把数据空间分为不同的网格，将样本对应到网格中，并进行密度的计算。CLIQUE适用于高维和大规模数据集，但该算法聚类的准确度较低。EM(expectation maximization)[14]是一种基于模型的聚类算法，根据极大后验概率估计寻找样本的概率模型参数进行聚类。该算法计算结果稳定、准确，但对初始化数据敏感。DBSCAN(density-based spatial clustering of applications with noise)[15]是典型的基于密度的聚类算法，它将样本分为核心点和噪声点，根据密度可达将核心点聚合到同一个集群中。该算法可以识别任意形状的稠密数据集且对数据集中的异常点不敏感，但不能处理密度差异过大的数据。

    2014年，Science发表了通过快速搜索和寻找密度峰值聚类[16](clustering by fast search and find of density peaks, DPC)算法。由于其新颖的设计理念和强大的性能，使得基于密度的聚类算法受到更广泛的关注和应用。DPC算法基于两点假设：聚类中心周围的样本的局部密度相对较低；不同聚类中心间的距离相对较远。DPC算法计算过程无需迭代，只需预先设定一个参数来识别聚类中心，但DPC算法仍有一些缺点：1）算法局部密度无法准确识别各类簇间样本的疏密差异，易造成类簇中心的误判；2）虽然DPC中的分配规则非常有效，但是当聚类过程出现某一个样本被错误分配，就会出现多米诺骨牌效应。

    针对DPC算法易出现类簇中心选取错误的问题，吕莉等[17]提出二阶K近邻和多簇合并的密度峰值聚类算法(density peaks clustering with second-order k-nearest neighbors and multi-cluster merging, DPC-SKMM)。DPC-SKMM算法提出最小二阶K近邻的概念，根据K近邻和二阶K近邻信息重新定义局部密度，凸显聚中心与非聚类中心的密度差异。Sun等[18]提出了基于最近邻优化分配策略的自适应密度峰值聚类算法(nearest neighbors-based adaptive density peaks clustering with optimized allocation strategy, NADPC)。NADPC算法提出了候选簇心和相对密度的概念，根据候选聚类中心的相对密度和高密度最近邻距离，计算聚类中心的可信度，从而选择聚类中心。赵嘉等[19]提出了K近邻和加权相似性的密度峰值聚类算法(density peaks clustering algorithm with k-nearest neighbors and weighted similarity, DPC-KWS)。DPC-KWS算法从样本的K近邻信息出发，重新定义了局部密度，调整了不同类簇中局部密度的大小。

    针对分配规则出现的问题，吴润秀等[20]提出基于相对密度估计和多簇合并的密度峰值聚类算法(density peaks clustering based on relative density estimating and multi cluster merging, DPC-RD-MCM)。DPC-RD-MCM算法重新定义了微簇间相似性度量准则，通过多簇合并策略得到最终聚类结果，避免了分配错误连带效应。Ding等[21]提出了基于中心和邻居的社区检测算法(community detection by propagating the label of center, DCN)。DCN算法根据样本的邻居传播标签，提出了标签传播的多重策略，有效解决了DPC分配策略的多米诺效应。赵嘉等[22]提出面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法(density peaks clustering algorithm based on geodesic distance and cosine mutual reverse nearest neighbors for manifold datasets, DPC-GDCN)。DPC-GDCN算法将互逆近邻和余弦相似性相结合，得到基于余弦互逆近邻的样本相似度矩阵，为流形类簇准确分配样本。

    上述算法均有效提高了DPC算法的聚类效果，但忽略了样本间的分布特征，无法对密度分布不均等特定数据集取得较好的聚类效果。因此，本文提出了面向密度分布不均数据的加权逆近邻密度峰值聚类算法(density peak clustering algorithm based on weighted reverse nearest neighbor for uneven density datasets, DPC-WR)。DPC-WR算法充分利用了逆近邻和共享逆近邻信息，算法的主要创新点如下：1）结合sigmoid函数及逆近邻思想重新定义了局部密度，平衡了样本间疏密程度的差异，提高了类簇中心的识别率；2）在样本分配策略中，引入逆近邻及共享逆近邻信息，避免了稀疏区域样本的错误分配，提高了聚类效果。

    1.   DPC算法

    DPC是一种高效的密度峰值聚类算法，可以快速找到聚类中心，对多种聚类任务具有良好的适应性。该算法基于聚类中心密度大于邻域密度，聚类中心间的距离相对较远的思想，提出了两种描述样本$ {{\boldsymbol{x}}_i} $的密度和距离的方法，即局部密度$ {\rho _i} $和相对距离$ {\delta _i} $。

    设有数据集${\boldsymbol{X}}{\text{ = }}\left\{ {{{\boldsymbol{x}}_1}{{,}}{{\boldsymbol{x}}_2}{{,}} \cdots {{,}}{{\boldsymbol{x}}_{{n}}}} \right\}$。对数据集$ {\boldsymbol{X}} $中的每个样本$ \left\{ {{{\boldsymbol{x}}_i}} \right\}_{i = 1}^n $，样本间的欧氏距离为

    $$ {d}_{ij}=\Vert {{\boldsymbol{x}}}_{i}-{{\boldsymbol{x}}}_{j}\Vert $$ (1)

    局部密度$ {\rho _i} $有两种定义方式：

    $$ {\rho _i} = \sum\limits_{i \ne j} {\chi \left( {{d_{ij}} - {d_{\text{c}}}} \right)} {\text{ }} $$ (2)

    其中：$\chi \left( {{x}} \right) = \left\{ {\begin{array}{*{20}{c}}{1,}&{{x} < 0}\\{0,}&{{x} \geqslant 0}\end{array}} \right.$，$ {d_{\text{c}}} $是截止距离。

    $$ {\rho _i} = \sum\limits_{i \ne j} {\exp \left( { - \frac{{d_{ij}^2}}{{d_{\text{c}}^{\text{2}}}}} \right)} $$ (3)

    式(2)为截断核，式(3)为高斯核。相对距离$ {\delta _i} $的定义如下：对于每个样本$ {{\boldsymbol{x}}_i} $，找到所有比样本$ {{\boldsymbol{x}}_i} $密集的样本$ {{\boldsymbol{x}}_j} $，选择最小的$ {d_{ij}} $；如果情况相反，则选择最大的$ {d_{ij}} $。$ {\delta _i} $的计算公式如下：

    $${\delta _i} = \left\{ {\begin{array}{*{20}{l}} {\mathop {\min }\limits_j \left( {{d_{ij}}} \right), \quad \exists {{j}}\;{\rm{s}}{\rm{.t}}{\rm{.}}\;{\rho _i} > {\rho _j}}\\ {\mathop {\max }\limits_j \left( {{d_{ij}}} \right),\quad 其他} \end{array}} \right.$$ (4)

    类簇中心由决策图确定，以局部密度$ {\rho _i} $为横坐标，相对距离$ {\delta _i} $为纵坐标，建立决策图。理想情况下，聚类中心选取为密度较高且相距较远的样本。定义如下：

    $$ {\gamma _i} = {\rho _i} \cdot {\delta _i} $$ (5)

    最后，选取前$ n $个较大的值作为聚类中心，$ n $为最终类簇数。

    2.   DPC-WR算法

    在聚类算法中，K近邻和逆近邻在表征密度时起着重要作用。K近邻能准确反映样本在空间中的局部分布特征。而逆近邻基于全局视角检查它的邻域，数据分布的变化会对样本的逆近邻造成影响，使得算法更容易识别聚类中心和提升算法聚类性能。因此，本文引入逆近邻和共享逆近邻信息，重新定义了局部密度，设计了样本相似度策略，充分考虑了样本的总体分布，使样本的局部一致性和全局一致性得到较好的均衡。

    2.1   加权逆近邻的局部密度

    定义1　逆近邻[23]。设样本$ {{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j} \in {\boldsymbol{X}} $，$ {{\boldsymbol{x}}_i} $在$ {{\boldsymbol{x}}_j} $的K近邻集中，那么$ {{\boldsymbol{x}}_j} $是$ {{\boldsymbol{x}}_i} $的逆近邻，具体定义如下：

    $$ {\text{RNN}}\left( {{{\boldsymbol{x}}_i}} \right) = \left\{ {{{\boldsymbol{x}}_j} \in {\boldsymbol{X}}\left| {{{\boldsymbol{x}}_i} \in {\text{KNN}}\left( {{{\boldsymbol{x}}_j}} \right)} \right.} \right\} $$ (6)

    定义2 　隶属度。样本$ {{\boldsymbol{x}}_i} $和$ {{\boldsymbol{x}}_j} $的隶属度$ {\mu _{ij}} $定义如下：

    $$ {\mu _{ij}} = \exp \left[ { - \frac{{d_{ij}^2}}{{k \cdot \left[ {1 + \left| {R\left( i \right)} \right|} \right]}}} \right] $$ (7)

    其中：$ k $为样本的近邻数；$ \left| {R\left( i \right)} \right| $表示样本$ {{\boldsymbol{x}}_i} $的逆近邻数，该值越大，该点的隶属度越大。

    定义3　加权逆近邻的局部密度。局部密度定义如下：

    $$ {\rho _i} = \sum\limits_{j \in {\text{RNN}}\left( i \right)} {{\lambda _{ij}} \cdot {\mu _{ij}}} $$ (8)

    权重系数：

    $$ {\lambda _{ij}} = \frac{{{\text{RNN}}\left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right)}}{{1 + \exp \left( { - \left| {R\left( i \right)} \right|} \right)}} $$ (9)
    $$\text{RNN}\left({x}_{i},{x}_{j}\right)=\left\{ \begin{aligned} &1\text{ },\text{ }{x}_{i}\in \text{RNN}\left({x}_{j}\right)\text{ }且\text{ }{x}_{i}\ne {x}_{j} \\ &0\text{ },\text{ }其他\end{aligned} \right.$$

    其中：$\dfrac{1}{{1 + \exp \left( { - x} \right)}}$为sigmoid函数，x为实数。

    类簇密度不同时，数据稠密区域与数据稀疏区域的样本对聚类中心选取的贡献程度是不同的。因此，处理密度分布不均数据时，通过引入权重对样本的贡献进行处理，可以达到良好的均衡效果。本文以样本的逆近邻数作为衡量密度的重要指标，引入sigmoid函数，对不同类簇中的样本进行权重调整。

    式(9)中$ {\lambda _{ij}} $为权重系数，它在sigmoid函数的基础上进行重构，分母部分以样本的逆近邻数替代了原函数的变量$ x $值，分子部分采用逆近邻代替实数值，使密度分布不均数据在不同区域具有辨识度。从函数可知，随着逆近邻数逐渐增加，其函数值趋近于1，说明位于高密度区域的样本所加的权重近似于1。对于较高密度的样本，被选为聚类中心的概率较大，此时逆近邻数起到关键的作用。当逆近邻数不断减少直至为0时，样本的权重将会从1发生非线性变化减少到0.5，这不仅考虑到各样本间细微的影响，还提高了聚类中心与非聚类中心的区分，使式(7)的隶属度定义更为合理。

    2.2   逆近邻和共享逆近邻的分配策略

    定义4　共享逆近邻。设样本$ {{\boldsymbol{x}}_i} $的逆近邻集为$ {\text{RNN}}\left( {{{\boldsymbol{x}}_i}} \right) $，$ {{\boldsymbol{x}}_j} $的逆近邻集为$ {\text{RNN}}\left( {{{\boldsymbol{x}}_j}} \right) $，样本$ {{\boldsymbol{x}}_i} $与$ {{\boldsymbol{x}}_j} $的共享逆近邻定义如下所示：

    $$ \begin{gathered} \psi \left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right) = \left\{ {{{\boldsymbol{x}}_i} \in {\boldsymbol{X}},{{\boldsymbol{x}}_j} \in {\boldsymbol{X}}\left| {{\text{RNN}}\left( {{{\boldsymbol{x}}_i}} \right) \cap {\text{RNN}}\left( {{{\boldsymbol{x}}_j}} \right)} \right.} \right\} \end{gathered} $$ (10)

    定义5　逆近邻和共享逆近邻的样本邻近度。通过样本间的逆近邻信息，定义了邻近度$ {\omega _{ij}} $，其定义如下：

    $$ {\omega _{ij}} = \left\{ \begin{gathered} \begin{array}{*{20}{l}} {{{\text{e}}^{{d_{ij}}}}},&{{{\boldsymbol{x}}_j} \in {\text{RNN}}\left( {{{\boldsymbol{x}}_i}} \right)} \end{array} \\ \begin{array}{*{20}{l}} {\dfrac{{{{\text{e}}^{{d_{ij}}}}}}{{\max \left( d \right)}}},&{{{\boldsymbol{x}}_j} \notin {\text{RNN}}\left( {{{\boldsymbol{x}}_i}} \right)} \end{array} \\ \end{gathered} \right. $$ (11)

    其中$ \max \left( d \right) $表示数据集$ {\boldsymbol{X}} $中样本间欧氏距离的最大值。

    式(11)中第一行表示当样本$ {{\boldsymbol{x}}_j} $位于样本$ {{\boldsymbol{x}}_i} $的逆近邻范围内时所赋予的邻近度；第二行表示当样本$ {{\boldsymbol{x}}_j} $不处于样本$ {{\boldsymbol{x}}_i} $的逆近邻范围时，由于样本间的紧密程度低，若将值赋0，易忽略未在范围内的样本的细微影响，故其邻近度在逆近邻范围的基础上除以最大距离所得。

    定义6　样本相似度。基于逆近邻和共享逆近邻，得到样本$ {{\boldsymbol{x}}_i} $和$ {{\boldsymbol{x}}_j} $的相似度：

    $$ \begin{gathered} S\left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right) = \left[ {\left| {\psi \left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right)} \right| + {\text{RNN}}\left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right)} \right] \cdot \beta \left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right) \end{gathered} $$ (12)

    式中：$ \left| {\psi \left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right)} \right| $表示$ \psi \left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right) $集合中样本的个数，$ \;\beta \left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right) $的定义如下：

    $$ \beta \left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right) =\frac{1} {k} \left[{{\displaystyle\sum\limits_{i,j = 1}^n {\omega \left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right)} }} \right]$$ (13)

    $ \; \beta \left( {{{\boldsymbol{x}}_i},{{\boldsymbol{x}}_j}} \right) $反映了样本所处空间的紧密程度，分子部分为每个样本的相似度之和，分母部分为归一化参数。式(12)考虑了样本本身及其共享逆近邻样本在定义样本间相似度方面起着重要的作用，因此，只有当样本之间存在逆近邻或共享逆近邻时，才存在相似性。

    2.3   算法步骤

    输入　数据集$ {\boldsymbol{X}} = \left\{ {{{\boldsymbol{x}}_i}} \right\}_{i = 1}^n $，近邻数$ k $

    输出　聚类结果$ C $

    1）数据归一化；

    2）计算数据集样本间的欧氏距离；

    3）根据式(8)和式(4)分别计算各样本的局部密度$ \;{\rho _i} $和相对距离$ {\delta _i} $；

    4）根据式(5)计算各样本的决策值$ {\gamma _i} $并选取聚类中心；

    5）根据式(12)计算基于逆近邻和共享逆近邻的样本相似度并构建相似度矩阵；

    6）对于所有已分配的样本，找到相似度最高的未分配样本并将其分配到已分配样本所在的簇中；

    7）若所有已分配样本与未分配样本间的相似度为0，转至步骤8），否则转至步骤6）；

    8）若还存在未分配的样本，则按DPC算法分配策略分配；

    9）输出聚类结果。

    2.4   算法复杂度分析

    设样本规模为$ n $，$ k $为近邻数。DPC算法的时间复杂度为$ O\left( {{n^2}} \right) $[24]。DPC-WR算法的时间复杂度主要由以下6个部分组成：1）计算样本间距离矩阵的复杂度$ O\left( {{n^2}} \right) $；2）计算样本的局部密度，包括计算样本间的K近邻和样本间的逆近邻与逆近邻数，前者复杂度为$ O\left( n \right) $，后者为$ O\left( {kn} \right) $和$ O\left( {{n^2}} \right) $；3）计算样本相对距离的复杂度$ O\left( {{n^2}} \right) $；4）计算样本决策值的复杂度$ O\left( {{n^2}} \right) $；5）计算样本的共享逆近邻与邻近度的复杂度$ O\left( {{n^2}} \right) $；6）计算样本最坏分配情况的复杂度$ O\left( {{n^2}\log n} \right) $。综上，DPC-WR算法的时间复杂度为$ O\left( {{n^2}\log n} \right) $。

    3.   实验结果与分析

    3.1   实验设置

    为验证DPC-WR算法的性能，本文在密度分布不均数据集、复杂形态数据集和UCI真实数据集上进行实验。将DPC-WR算法与IDPC-FA[25]、FNDPC[26]、FKK-DPC[20]、DPC[16]和DPCSA[27]算法进行比较。其中，IDPC-FA、DPCSA和DPC算法由原作者提供，FNDPC和FKNN-DPC算法参照原文献编程实现。除了DPCSA和IDPC-FA无需对参数调优外，其余算法均需要调整参数。DPC-WR和FKNN-DPC算法参数$ k $值的选取是1~50之间的最优值；DPC算法的截断距离$ {d_{\text{c}}} $的选取在0.1%~5%，步长为0.1%；FNDPC算法参数$ \varepsilon $的选取在0.01~1，步长为0.01。实验环境为Win10 64 bit操作系统，AMD Ryzen 7 5800H with Radeon Graphics 3.20 GHz处理器，16.0GB内存。

    本文采用调整互信息（adjusted mutual information, AMI）[28]、Fowlkes-Mallows指数（fowlkes-mallows index, FMI）[28]和调整兰德系数（adjusted rand index, ARI）[29]对聚类效果进行评价，其中，3个指标的最佳结果都为1，各指标值接近1的程度越高，表明聚类结果越好。

    3.2   密度分布不均数据集的实验结果与分析

    本文选取了6个不同规模的密度分布不均数据集进行实验，其基本特征如表1所示。

    表  1  密度分布不均数据集的基本特征
    Table  1  Basic characteristics of datasets with uneven density distribution
    数据集样本规模维度类簇数
    Jain37322
    Twomoons150222
    Cmc100223
    Ring120022
    LineBlobs26623
    Ls174126

    表2给出了6种算法在密度分布不均数据集上的聚类结果，其中最优结果以粗体表示，“Arg-”表示各算法的最优参数取值。“—”表示不含参数。DPC-WR算法在6个数据集上均获得最佳的聚类效果。IDPC-FA算法对Jain和LineBlobs具有较好的聚类效果，对其他数据集的聚类效果较差。FKNN-DPC算法对Cmc和LineBlobs数据集聚类效果较好，对其他数据集聚类效果不佳。DPCSA算法仅对LineBlobs数据集具有较好的聚类效果。FNDPC和DPC算法在6个数据集上的聚类性能均低于DPC-WR和FKNN-DPC算法。

    表  2  6种算法在密度分布不均数据集上的聚类结果
    Table  2  Clustering results of six algorithms on datasets with uneven density distribution
    算法Jain
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 24
    IDPC-FA 1.0000 1.0000 1.0000 —
    FNDPC 0.5961 0.7257 0.9051 0.47
    FKNN-DPC 0.7092 0.8224 0.9359 43
    DPC 0.6183 0.7146 0.8819 0.8
    DPCSA 0.2167 0.0442 0.5924 —
    算法Twomoons
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 39
    IDPC-FA 0.5171 0.6106 0.8458 —
    FNDPC 1.0000 1.0000 1.0000 0.12
    FKNN-DPC 1.0000 1.0000 1.0000 77
    DPC 0.6671 0.7621 0.9005 4.7
    DPCSA 0.3647 0.2746 0.6607 —
    算法Cmc
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 20
    IDPC-FA 0.8093 0.8421 0.9027 —
    FNDPC 0.8093 0.8421 0.9027 0.28
    FKNN-DPC 1.0000 1.0000 1.0000 49
    DPC 0.3857 0.2661 0.5377 5
    DPCSA 0.6656 0.5761 0.7454 —
    算法Ring
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 4
    IDPC-FA 0.1333 0.0886 0.6362 —
    FNDPC 0.0276 0.0104 0.6566 0.01
    FKNN-DPC 0.5702 0.5900 0.8005 24
    DPC 0.2073 0.1815 0.6431 0.06
    DPCSA 0.6362 0.6721 0.8387 —
    续表 2
    算法LineBlobs
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 4
    IDPC-FA 1.0000 1.0000 1.0000 —
    FNDPC 0.7794 0.7179 0.8148 0.11
    FKNN-DPC 1.0000 1.0000 1.0000 7
    DPC 0.8375 0.8237 0.8842 4.2
    DPCSA 1.0000 1.0000 1.0000 —
    算法Ls
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 40
    IDPC-FA 0.7076 0.6274 0.7325 —
    FNDPC 0.7564 0.6898 0.7808 0.37
    FKNN-DPC 0.8719 0.8179 0.8735 48
    DPC 0.7665 0.6894 0.7779 0.91
    DPCSA 0.7252 0.5999 0.7129 —

    Friedman检验[30]是利用秩实现对多个总体分布是否存在显著差异的非参数检验方法。将对比算法进行检验可以更准确地反映算法间评价指标的差异，秩均值越高则算法的聚类效果越优。从表3可以发现，在密度分布不均数据集上聚类评价指标AMI、ARI和FMI的秩均值排名中，DPC-WR算法都位列第1，且秩均值都大于5.4。

    表  3  6种算法在密度分布不均数据集上的秩均值
    Table  3  Rank mean of the six algorithms on the unevenly distributed density datasets
    AMIARIFMI
    算法秩均值算法秩均值算法秩均值
    DPC-WR5.42DPC-WR5.42DPC-WR5.42
    IDPC-FA3.08IDPC-FA3.25IDPC-FA3.08
    FNDPC2.58FNDPC2.92FNDPC3.25
    FKNN-DPC4.67FKNN-DPC4.67FKNN-DPC4.67
    DPC2.67DPC2.33DPC2.17
    DPCSA2.58DPCSA2.42DPCSA2.42

    由于篇幅所限，本文选取了1个典型的密度分布不均数据集。图1给出了DPC-WR、IDPC-FA、FNDPC、FKNN-DPC、DPC和DPCSA算法在Jain数据集上的聚类结果。图中不同的颜色代表不同的类簇，类簇中心用“六角星”表示。

    图  1  6种算法在Jain数据集上的聚类结果
    Fig.  1  The clustering results of 6 algorithms on Jain dataset
    下载: 全尺寸图片

    Jain数据集由2个稠密程度不同的新月形类簇构成。从图1可知，DPC-WR和IDPC-FA算法充分考虑了样本间的密度差，能准确地找到类簇中心；FNDPC和FKNN-DPC算法虽然找到了正确的类簇中心，但样本分配策略存在错误，导致稀疏类簇样本的错误分配；DPC和DPCSA算法没有找到正确的聚类中心，导致聚类效果不佳。

    3.3   复杂形态数据集的实验结果与分析

    复杂形态数据集是指具有多尺度、簇类形状多样等结构的数据集。本文选取了6个复杂形态的数据集，其基本特征如表4所示。表5给出了6种算法在复杂形态数据集上的聚类结果。从表5可知，DPC-WR和IDPC-FA算法比其他对比算法的聚类结果更优，都存在4个聚类效果较好的数据集。从整体来看，DPC-WR算法的聚类效果最佳，具体表现在Flame、R15、Sticks和Pathbased数据集。

    表  4  复杂形态数据集的基本特征
    Table  4  Basic characteristics of complex
    数据集样本规模维度类簇数
    Flame24022
    R15600215
    Aggregation78827
    D313100231
    Sticks51224
    Pathbased30023

    表6为6种算法在6个复杂形态数据集上评价指标的秩均值。从表6可以发现，DPC-WR算法在AMI、ARI和FMI评价指标的秩均值中位列第一，其次是IDPC-FA算法，然后是FNDPC算法。

    表  5  6种算法在复杂形态数据集上的聚类结果
    Table  5  Clustering results of six algorithms on complex morphological datasets
    算法Flame
    AMIARIFMIArg-
    DPC-WR1.00001.00001.00001
    IDPC-FA1.00001.00001.0000—
    FNDPC1.00001.00001.00000.13
    FKNN-DPC0.92670.96670.98455
    DPC1.00001.00001.00002.8
    DPCSA1.00001.00001.0000—
    算法R15
    AMIARIFMIArg-
    DPC-WR0.99380.99280.993332
    IDPC-FA0.99380.99280.9933—
    FNDPC0.99380.99280.99330.03
    FKNN-DPC0.99380.99280.993327
    DPC0.99380.99280.99330.6
    DPCSA0.98850.98570.9866—
    算法Aggregation
    AMIARIFMIArg-
    DPC-WR0.99220.99560.996612
    IDPC-FA1.00001.00001.0000—
    FNDPC0.98640.99130.99320.02
    FKNN-DPC0.99050.99490.996020
    DPC0.99220.99560.99664
    DPCSA0.95370.95810.9673—
    表  6  6种算法在复杂形态数据集上的秩均值
    Table  6  Rank mean of 6 algorithms on complex morphological datasets
    AMIARIFMI
    算法秩均值 算法秩均值 算法秩均值
    DPC-WR4.67DPC-WR4.67DPC-WR4.67
    IDPC-FA4.42IDPC-FA4.42IDPC-FA4.42
    FNDPC3.25FNDPC3.08FNDPC3.17
    FKNN-DPC3.92FKNN-DPC3.92FKNN-DPC3.92
    DPC2.92DPC3.08DPC3.00
    DPCSA1.83DPCSA1.83DPCSA1.83
    续表 5
    算法D31
    AMIARIFMIArg-
    DPC-WR0.96170.94650.948250
    IDPC-FA0.95750.94020.9421—
    FNDPC0.95550.93640.93850.04
    FKNN-DPC0.96580.95220.953723
    DPC0.95540.93650.93850.7
    DPCSA0.95520.93530.9374—
    算法Sticks
    AMIARIFMIArg-
    DPC-WR1.00001.00001.00003
    IDPC-FA1.00001.00001.0000—
    FNDPC1.00001.00001.00000.22
    FKNN-DPC1.00001.00001.00007
    DPC0.80940.75340.82352
    DPCSA0.76340.63600.7443—
    算法Pathbased
    AMIARIFMIArg-
    DPC-WR0.94010.95900.97275
    IDPC-FA0.84420.85930.9067—
    FNDPC0.57510.50670.70650.01
    FKNN-DPC0.93050.94990.96659
    DPC0.52120.47170.66643.8
    DPCSA0.70730.61330.7511—

    3.4   UCI数据集的实验结果与分析

    UCI数据集又称真实数据集，它是一个常用的标准测试数据集。为了进一步验证DPC-WR算法的有效性，本文选取了8个真实数据集，对6种算法进行实验。其中测试的数据集包括Iris、Wine、Seeds、Ecoli、Inonsphere、Libras、Dermatology和Wdbc。表7给出了各数据集的基本特征。表8为6种算法在UCI数据集上的聚类效果。从表8可以发现，处理Seeds数据集时，DPC-WR算法的聚类效果不及IDPC-FA、FKNN-DPC和DPC算法。处理Inonsphere数据集时，DPC-WR算法的聚类效果低于FKNN-DPC算法。处理Dermatology数据集时，DPC-WR算法的聚类效果比DPCSA算法好，但略逊于其他算法。剩余的Iris、Wine、Ecoli、Libras和Wdbc数据集，DPC-WR算法的聚类效果都优于其他算法。

    表  7  UCI数据集的基本特征
    Table  7  Basic characteristics of UCI datasets
    数据集样本规模维度类簇数
    Iris15043
    Wine178133
    Seeds21073
    Ecoli33688
    Inonsphere351342
    Libras3609015
    Dermatology366336
    Wdbc569302
    表  8  6种算法在UCI数据集上的聚类结果
    Table  8  Clustering results of six algorithms on UCI datasets
    算法Iris
    AMIARIFMIArg-
    DPC-WR0.89710.90930.93569
    IDPC-FA0.86230.88570.9233—
    FNDPC0.88310.90380.93550.11
    FKNN-DPC0.88310.90380.935522
    DPC0.86060.88570.92330.2
    DPCSA0.88310.90380.9355—
    算法Wine
    AMIARIFMIArg-
    DPC-WR0.87160.89750.931944
    IDPC-FA0.76750.77130.8478—
    FNDPC0.78980.80250.86860.26
    FKNN-DPC0.84810.88390.92298
    DPC0.70650.67240.78352
    DPCSA 0.74800.74140.8283—
    算法Seeds
    AMIARIFMIArg-
    DPC-WR0.71610.76350.84167
    IDPC-FA0.72990.76700.8444—
    FNDPC0.71360.75450.83610.07
    FKNN-DPC0.77570.80240.86829
    DPC0.72990.76700.84440.7
    DPCSA0.66090.68730.7918—
    算法Ecoli
    AMIARIFMIArg-
    DPC-WR0.66970.76490.83581
    IDPC-FA0.66380.75610.8284—
    FNDPC0.48330.56180.71780.35
    FKNN-DPC0.58780.58940.70272
    DPC0.49780.44650.57750.4
    DPCSA0.44060.45930.6467—
    续表 8
    算法Inonsphere
    AMIARIFMIArg-
    DPC-WR0.22890.31220.672210
    IDPC-FA0.13550.21830.6432—
    FNDPC0.16300.24830.65310.06
    FKNN-DPC0.34850.47900.77168
    DPC0.15040.23570.64910.5
    DPCSA0.13350.21350.6390—
    算法Libras
    AMIARIFMIArg-
    DPC-WR0.57570.39150.445313
    IDPC-FA0.57330.38160.4247—
    FNDPC0.54940.32900.38690.17
    FKNN-DPC0.55540.34590.404410
    DPC0.53580.31930.37170.3
    DPCSA0.53880.30950.3791—
    算法Dermatology
    AMIARIFMIArg-
    DPC-WR0.86540.73980.79296
    IDPC-FA0.83080.84640.8764—
    FNDPC0.79330.80290.84410.17
    FKNN-DPC0.80830.83610.870635
    DPC0.83540.83890.87151.5
    DPCSA0.74700.60990.6922—
    算法Wdbc
    AMIARIFMIArg-
    DPC-WR0.72080.82430.919014
    IDPC-FA0.62370.74230.8829—
    FNDPC0.60760.36450.87580.05
    FKNN-DPC0.64230.76130.88942
    DPC0.43660.49640.79410.5
    DPCSA0.33610.37710.7595—

    表9为6种算法在UCI数据集上评价指标的秩均值。从表9可知，DPC-WR算法相较于其他对比算法评价指标的秩均值都是最高的，其次是FKNN-DPC和IDPC-FA算法。由此可以得出，在UCI真实数据集上，DPC-WR算法的聚类效果明显优于IDPC-FA、FNDPC、FKNN-DPC、DPC和DPCSA算法。

    表  9  6种算法在UCI数据集上的秩均值
    Table  9  Rank mean of six algorithms on UCI datasets
    AMIARIFMI
    算法秩均值 算法秩均值 算法秩均值
    DPC-WR5.38DPC-WR5.00DPC-WR5.00
    IDPC-FA3.81IDPC-FA3.88IDPC-FA3.88
    FNDPC3.00FNDPC3.00FNDPC3.38
    FKNN-DPC4.63FKNN-DPC4.75FKNN-DPC4.63
    DPC2.56DPC2.63DPC2.38
    DPCSA1.63DPCSA1.75DPCSA1.75

    3.5   算法的仿真时间与分析

    本文中，仿真时间指完成单个数据集聚类所花费的时长，是评价算法聚类性能的重要指标。为计算聚类算法的聚类时间，本文针对前述3类数据集进行了相应的实验，结果详见表10。

    表  10  6种算法在3类数据集上的仿真时间
    Table  10  Simulation time of six algorithms on three types of datasets s
    数据集DPC-WRIDPC-FAFNDPCFKNN-DPCDPCDPCSA
    Jain0.0711.230.10.10.060.06
    Twomoons1.57341.540.230.310.230.23
    Cmc0.3887.320.180.210.140.13
    Ring0.3134.560.180.160.130.15
    LineBlobs0.036.470.10.060.060.06
    Ls2.42672.190.320.350.280.3
    Flame0.015.530.090.050.050.06
    R150.1845.650.260.130.180.17
    Aggregation0.2148.780.190.190.130.13
    D3115.437093.371.591.531.071.15
    Sticks0.0718.420.140.090.080.1
    Pathbased0.037.760.120.070.060.06

    从表10可以发现，对于样本规模较小的数据集，如Jain、LineBlobs等，DPC-WR算法可以与对比算法相媲美或者更优；对于样本规模较大的数据集，如Twomoons、Cmc等，DPC-WR算法弱于FNDPC、FKNN-DPC、DPC和DPCSA算法，但是，相较于IDPC-FA算法，DPC-WR算法加速效应明显。这主要是由于DPC-WR算法的时间复杂度为$ O\left( {{n^2}\log n} \right) $，样本规模的增大，$ \log n $的影响将变得更加明显。

    续表 10
    数据集DPC-WRIDPC-FAFNDPCFKNN-DPCDPCDPCSA
    Iris0.023.830.120.070.060.06
    Wine0.044.420.110.060.070.06
    Seeds0.035.230.110.070.070.06
    Ecoli0.0214.230.170.080.10.11
    Inonsphere0.0613.370.120.060.070.06
    Libras0.09430.270.110.180.15
    Dermatology0.0617.070.160.10.090.09
    Wdbc0.1728.360.140.070.080.08

    4.   结束语

    针对DPC算法在面对密度分布不均数据集时易出现误选类簇中心以及样本分配错误的问题，本文提出了一种面向密度分布不均数据的加权逆近邻密度峰值聚类算法。DPC-WR算法首先引入基于sigmoid函数的权重系数及逆近邻思想，重新定义样本的局部密度；随后，利用逆近邻和共享逆近邻计算样本相似度；最后，按照样本相似度将剩余样本进行分配。实验结果表明，DPC-WR算法有效改善了类簇间样本疏密差异导致误判聚类中心以及稀疏区域样本错误分配的问题，在密度分布不均数据集、复杂形态数据集和UCI数据集上的聚类效果明显优于其对比算法。由于DPC-WR的聚类结果往往取决于参数$ k $的选择，如何快速选择$ k $的最佳值是下一步的研究重点。同时，群体智能[31-32]的引入有望进一步提升聚类算法的性能，特别是借助群智能进化[33-35]的途径将使得聚类算法的自适应性更加趋于完善。

  • 图  1   6种算法在Jain数据集上的聚类结果

    Fig.  1   The clustering results of 6 algorithms on Jain dataset

    下载: 全尺寸图片

    表  1   密度分布不均数据集的基本特征

    Table  1   Basic characteristics of datasets with uneven density distribution

    数据集样本规模维度类簇数
    Jain37322
    Twomoons150222
    Cmc100223
    Ring120022
    LineBlobs26623
    Ls174126

    表  2   6种算法在密度分布不均数据集上的聚类结果

    Table  2   Clustering results of six algorithms on datasets with uneven density distribution

    算法Jain
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 24
    IDPC-FA 1.0000 1.0000 1.0000 —
    FNDPC 0.5961 0.7257 0.9051 0.47
    FKNN-DPC 0.7092 0.8224 0.9359 43
    DPC 0.6183 0.7146 0.8819 0.8
    DPCSA 0.2167 0.0442 0.5924 —
    算法Twomoons
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 39
    IDPC-FA 0.5171 0.6106 0.8458 —
    FNDPC 1.0000 1.0000 1.0000 0.12
    FKNN-DPC 1.0000 1.0000 1.0000 77
    DPC 0.6671 0.7621 0.9005 4.7
    DPCSA 0.3647 0.2746 0.6607 —
    算法Cmc
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 20
    IDPC-FA 0.8093 0.8421 0.9027 —
    FNDPC 0.8093 0.8421 0.9027 0.28
    FKNN-DPC 1.0000 1.0000 1.0000 49
    DPC 0.3857 0.2661 0.5377 5
    DPCSA 0.6656 0.5761 0.7454 —
    算法Ring
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 4
    IDPC-FA 0.1333 0.0886 0.6362 —
    FNDPC 0.0276 0.0104 0.6566 0.01
    FKNN-DPC 0.5702 0.5900 0.8005 24
    DPC 0.2073 0.1815 0.6431 0.06
    DPCSA 0.6362 0.6721 0.8387 —
    续表 2
    算法LineBlobs
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 4
    IDPC-FA 1.0000 1.0000 1.0000 —
    FNDPC 0.7794 0.7179 0.8148 0.11
    FKNN-DPC 1.0000 1.0000 1.0000 7
    DPC 0.8375 0.8237 0.8842 4.2
    DPCSA 1.0000 1.0000 1.0000 —
    算法Ls
    AMI ARI FMI Arg-
    DPC-WR 1.0000 1.0000 1.0000 40
    IDPC-FA 0.7076 0.6274 0.7325 —
    FNDPC 0.7564 0.6898 0.7808 0.37
    FKNN-DPC 0.8719 0.8179 0.8735 48
    DPC 0.7665 0.6894 0.7779 0.91
    DPCSA 0.7252 0.5999 0.7129 —

    表  3   6种算法在密度分布不均数据集上的秩均值

    Table  3   Rank mean of the six algorithms on the unevenly distributed density datasets

    AMIARIFMI
    算法秩均值算法秩均值算法秩均值
    DPC-WR5.42DPC-WR5.42DPC-WR5.42
    IDPC-FA3.08IDPC-FA3.25IDPC-FA3.08
    FNDPC2.58FNDPC2.92FNDPC3.25
    FKNN-DPC4.67FKNN-DPC4.67FKNN-DPC4.67
    DPC2.67DPC2.33DPC2.17
    DPCSA2.58DPCSA2.42DPCSA2.42

    表  4   复杂形态数据集的基本特征

    Table  4   Basic characteristics of complex

    数据集样本规模维度类簇数
    Flame24022
    R15600215
    Aggregation78827
    D313100231
    Sticks51224
    Pathbased30023

    表  5   6种算法在复杂形态数据集上的聚类结果

    Table  5   Clustering results of six algorithms on complex morphological datasets

    算法Flame
    AMIARIFMIArg-
    DPC-WR1.00001.00001.00001
    IDPC-FA1.00001.00001.0000—
    FNDPC1.00001.00001.00000.13
    FKNN-DPC0.92670.96670.98455
    DPC1.00001.00001.00002.8
    DPCSA1.00001.00001.0000—
    算法R15
    AMIARIFMIArg-
    DPC-WR0.99380.99280.993332
    IDPC-FA0.99380.99280.9933—
    FNDPC0.99380.99280.99330.03
    FKNN-DPC0.99380.99280.993327
    DPC0.99380.99280.99330.6
    DPCSA0.98850.98570.9866—
    算法Aggregation
    AMIARIFMIArg-
    DPC-WR0.99220.99560.996612
    IDPC-FA1.00001.00001.0000—
    FNDPC0.98640.99130.99320.02
    FKNN-DPC0.99050.99490.996020
    DPC0.99220.99560.99664
    DPCSA0.95370.95810.9673—

    表  6   6种算法在复杂形态数据集上的秩均值

    Table  6   Rank mean of 6 algorithms on complex morphological datasets

    AMIARIFMI
    算法秩均值 算法秩均值 算法秩均值
    DPC-WR4.67DPC-WR4.67DPC-WR4.67
    IDPC-FA4.42IDPC-FA4.42IDPC-FA4.42
    FNDPC3.25FNDPC3.08FNDPC3.17
    FKNN-DPC3.92FKNN-DPC3.92FKNN-DPC3.92
    DPC2.92DPC3.08DPC3.00
    DPCSA1.83DPCSA1.83DPCSA1.83
    续表 5
    算法D31
    AMIARIFMIArg-
    DPC-WR0.96170.94650.948250
    IDPC-FA0.95750.94020.9421—
    FNDPC0.95550.93640.93850.04
    FKNN-DPC0.96580.95220.953723
    DPC0.95540.93650.93850.7
    DPCSA0.95520.93530.9374—
    算法Sticks
    AMIARIFMIArg-
    DPC-WR1.00001.00001.00003
    IDPC-FA1.00001.00001.0000—
    FNDPC1.00001.00001.00000.22
    FKNN-DPC1.00001.00001.00007
    DPC0.80940.75340.82352
    DPCSA0.76340.63600.7443—
    算法Pathbased
    AMIARIFMIArg-
    DPC-WR0.94010.95900.97275
    IDPC-FA0.84420.85930.9067—
    FNDPC0.57510.50670.70650.01
    FKNN-DPC0.93050.94990.96659
    DPC0.52120.47170.66643.8
    DPCSA0.70730.61330.7511—

    表  7   UCI数据集的基本特征

    Table  7   Basic characteristics of UCI datasets

    数据集样本规模维度类簇数
    Iris15043
    Wine178133
    Seeds21073
    Ecoli33688
    Inonsphere351342
    Libras3609015
    Dermatology366336
    Wdbc569302

    表  8   6种算法在UCI数据集上的聚类结果

    Table  8   Clustering results of six algorithms on UCI datasets

    算法Iris
    AMIARIFMIArg-
    DPC-WR0.89710.90930.93569
    IDPC-FA0.86230.88570.9233—
    FNDPC0.88310.90380.93550.11
    FKNN-DPC0.88310.90380.935522
    DPC0.86060.88570.92330.2
    DPCSA0.88310.90380.9355—
    算法Wine
    AMIARIFMIArg-
    DPC-WR0.87160.89750.931944
    IDPC-FA0.76750.77130.8478—
    FNDPC0.78980.80250.86860.26
    FKNN-DPC0.84810.88390.92298
    DPC0.70650.67240.78352
    DPCSA 0.74800.74140.8283—
    算法Seeds
    AMIARIFMIArg-
    DPC-WR0.71610.76350.84167
    IDPC-FA0.72990.76700.8444—
    FNDPC0.71360.75450.83610.07
    FKNN-DPC0.77570.80240.86829
    DPC0.72990.76700.84440.7
    DPCSA0.66090.68730.7918—
    算法Ecoli
    AMIARIFMIArg-
    DPC-WR0.66970.76490.83581
    IDPC-FA0.66380.75610.8284—
    FNDPC0.48330.56180.71780.35
    FKNN-DPC0.58780.58940.70272
    DPC0.49780.44650.57750.4
    DPCSA0.44060.45930.6467—
    续表 8
    算法Inonsphere
    AMIARIFMIArg-
    DPC-WR0.22890.31220.672210
    IDPC-FA0.13550.21830.6432—
    FNDPC0.16300.24830.65310.06
    FKNN-DPC0.34850.47900.77168
    DPC0.15040.23570.64910.5
    DPCSA0.13350.21350.6390—
    算法Libras
    AMIARIFMIArg-
    DPC-WR0.57570.39150.445313
    IDPC-FA0.57330.38160.4247—
    FNDPC0.54940.32900.38690.17
    FKNN-DPC0.55540.34590.404410
    DPC0.53580.31930.37170.3
    DPCSA0.53880.30950.3791—
    算法Dermatology
    AMIARIFMIArg-
    DPC-WR0.86540.73980.79296
    IDPC-FA0.83080.84640.8764—
    FNDPC0.79330.80290.84410.17
    FKNN-DPC0.80830.83610.870635
    DPC0.83540.83890.87151.5
    DPCSA0.74700.60990.6922—
    算法Wdbc
    AMIARIFMIArg-
    DPC-WR0.72080.82430.919014
    IDPC-FA0.62370.74230.8829—
    FNDPC0.60760.36450.87580.05
    FKNN-DPC0.64230.76130.88942
    DPC0.43660.49640.79410.5
    DPCSA0.33610.37710.7595—

    表  9   6种算法在UCI数据集上的秩均值

    Table  9   Rank mean of six algorithms on UCI datasets

    AMIARIFMI
    算法秩均值 算法秩均值 算法秩均值
    DPC-WR5.38DPC-WR5.00DPC-WR5.00
    IDPC-FA3.81IDPC-FA3.88IDPC-FA3.88
    FNDPC3.00FNDPC3.00FNDPC3.38
    FKNN-DPC4.63FKNN-DPC4.75FKNN-DPC4.63
    DPC2.56DPC2.63DPC2.38
    DPCSA1.63DPCSA1.75DPCSA1.75

    表  10   6种算法在3类数据集上的仿真时间

    Table  10   Simulation time of six algorithms on three types of datasets s

    数据集DPC-WRIDPC-FAFNDPCFKNN-DPCDPCDPCSA
    Jain0.0711.230.10.10.060.06
    Twomoons1.57341.540.230.310.230.23
    Cmc0.3887.320.180.210.140.13
    Ring0.3134.560.180.160.130.15
    LineBlobs0.036.470.10.060.060.06
    Ls2.42672.190.320.350.280.3
    Flame0.015.530.090.050.050.06
    R150.1845.650.260.130.180.17
    Aggregation0.2148.780.190.190.130.13
    D3115.437093.371.591.531.071.15
    Sticks0.0718.420.140.090.080.1
    Pathbased0.037.760.120.070.060.06
    续表 10
    数据集DPC-WRIDPC-FAFNDPCFKNN-DPCDPCDPCSA
    Iris0.023.830.120.070.060.06
    Wine0.044.420.110.060.070.06
    Seeds0.035.230.110.070.070.06
    Ecoli0.0214.230.170.080.10.11
    Inonsphere0.0613.370.120.060.070.06
    Libras0.09430.270.110.180.15
    Dermatology0.0617.070.160.10.090.09
    Wdbc0.1728.360.140.070.080.08
    • 参考文献(35)
  • [1] SZALONTAI B, DEBRECZENY M, FINTOR K, et al. SVD-clustering, a general image-analyzing method explained and demonstrated on model and Raman micro-spectroscopic maps[J]. Scientific reports, 2020, 10: 4238. doi: 10.1038/s41598-020-61206-9
    [2] 程鹏宇, 赵嘉, 韩龙哲, 等. 双向多尺度LSTM的短时温度预测[J]. 江西师范大学学报(自然科学版), 2022, 46(2): 134–139. doi: 10.16357/j.cnki.issn1000-5862.2022.02.04

    CHENG Pengyu, ZHAO Jia, HAN Longzhe, et al. The short-term temperature prediction based on bidirectional multi-scale LSTM[J]. Journal of Jiangxi normal university (natural science edition), 2022, 46(2): 134–139. doi: 10.16357/j.cnki.issn1000-5862.2022.02.04
    [3] LI Chunlin, BAI Jingpan. Automatic content extraction and time-aware topic clustering for large-scale social network on cloud platform[J]. The journal of supercomputing, 2019, 75(5): 2890–2924. doi: 10.1007/s11227-018-2704-z
    [4] MIRZAL A. Statistical analysis of microarray data clustering using NMF, spectral clustering, kmeans, and GMM[J]. IEEE/ACM transactions on computational biology and bioinformatics, 2022, 19(2): 1173–1192.
    [5] ZHAO Yuan, FANG Zhaoyu, LIN Cuixiang, et al. RFCell: a gene selection approach for scRNA-seq clustering based on permutation and random forest[J]. Frontiers in genetics, 2021, 12: 665843. doi: 10.3389/fgene.2021.665843
    [6] TAVALLALI P, TAVALLALI P, SINGHAL M. K-means tree: an optimal clustering tree for unsupervised learning[J]. The journal of supercomputing, 2021, 77(5): 5239–5266. doi: 10.1007/s11227-020-03436-2
    [7] CHU Zhenyue, WANG Weifeng, LI Bangzhun, et al. An operation health status monitoring algorithm of special transformers based on BIRCH and Gaussian cloud methods[J]. Energy reports, 2021, 7: 253–260.
    [8] BUREVA V, POPOV S, TRANEVA V, et al. Generalized net model of cluster analysis using CLIQUE: clustering in quest[J]. International journal bioautomation, 2019, 23(2): 131–138.
    [9] REN Jie, WANG Zulin, XU Mai, et al. An EM-based user clustering method in non-orthogonal multiple access[J]. IEEE transactions on communications, 2019, 67(12): 8422–8434. doi: 10.1109/TCOMM.2019.2945334
    [10] ZHU Qidan, TANG Xiangmeng, ELAHI A. Application of the novel harmony search optimization algorithm for DBSCAN clustering[J]. Expert systems with applications, 2021, 178: 115054. doi: 10.1016/j.eswa.2021.115054
    [11] ZHANG En, LI Huimin, HUANG Yuchen, et al. Practical multi-party private collaborative k-means clustering[J]. Neurocomputing, 2022, 467: 256–265. doi: 10.1016/j.neucom.2021.09.050
    [12] ZHANG Tian, RAMAKRISHNAN R, LIVNY M. Birch[J]. ACM SIGMOD record, 1996, 25(2): 103–114. doi: 10.1145/235968.233324
    [13] AGRAWAL R, GEHRKE J, GUNOPULOS D, et al. Automatic subspace clustering of high dimensional data for data mining applications[C]//Proceedings of the 1998 ACM SIGMOD international conference on Management of data. Seattle: ACM, 1998: 94−105.
    [14] DEMPSTER A P, LAIRD N M, RUBIN D B. Maximum likelihood from incomplete data via the EM algorithm[J]. Journal of the royal statistical society:series B (methodological), 1977, 39(1): 1–22. doi: 10.1111/j.2517-6161.1977.tb01600.x
    [15] ESTER M. A density-based Algorithm for discovering clusters in large spatial databases with noise[C]//KDD '96: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining. Oregon: AAAI Press, 1996: 226−231.
    [16] RODRIGUEZ A, LAIO A. Machine learning. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492–1496. doi: 10.1126/science.1242072
    [17] 吕莉, 朱梅子, 康平, 等. 二阶K近邻和多簇合并的密度峰值聚类算法[J/OL]. 吉林大学学报(工学版). (2023−01−31)[2023−07−13]. https://kns.cnki.net/kcms/detail/22.1341.t.20230131.1100. 005. html.

    LYU Li, ZHU Meizi, KANG Ping, et al. Density peaks clustering with second-order K-nearest neighbors and multi-cluster merging[J/OL]. Journal of Jilin University (engineering and technology edition). (2023−01−31) [2023−07−13]. https://kns.cnki.net/kcms/detail/22.1341.t.20230131.1100.005.html.
    [18] SUN Lin, QIN Xiaoying, DING Weiping, et al. Nearest neighbors-based adaptive density peaks clustering with optimized allocation strategy[J]. Neurocomputing, 2022, 473: 159–181. doi: 10.1016/j.neucom.2021.12.019
    [19] 赵嘉, 陈磊, 吴润秀, 等. K近邻和加权相似性的密度峰值聚类算法[J]. 控制理论与应用, 2022, 39(12): 2349–2357.

    ZHAO Jia, CHEN Lei, WU Runxiu, et al. Density peaks clustering algorithm with K-nearest neighbors and weighted similarity[J]. Control theory & applications, 2022, 39(12): 2349–2357.
    [20] 吴润秀, 尹士豪, 赵嘉, 等. 基于相对密度估计和多簇合并的密度峰值聚类算法[J]. 控制与决策, 2023, 38(4): 1047–1055. doi: 10.13195/j.kzyjc.2021.1286

    WU Runxiu, YIN Shihao, ZHAO Jia, et al. Density peaks clustering based on relative density estimating and multi cluster merging[J]. Control and decision, 2023, 38(4): 1047–1055. doi: 10.13195/j.kzyjc.2021.1286
    [21] DING Jiajun, HE Xiongxiong, YUAN Junqing, et al. Community detection by propagating the label of center[J]. Physica A:statistical mechanics and its applications, 2018, 503: 675–686. doi: 10.1016/j.physa.2018.02.174
    [22] 赵嘉, 王刚, 吕莉, 等. 面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法[J]. 电子学报, 2022, 50(11): 2730–2737.

    ZHAO Jia, WANG Gang, LYU Li, et al. Density peaks clustering algorithm based on geodesic distance and cosine mutual reverse nearest neighbors for manifold datasets[J]. Acta electronica sinica, 2022, 50(11): 2730–2737.
    [23] BRYANT A, CIOS K. RNN-DBSCAN: a density-based clustering algorithm using reverse nearest neighbor density estimates[J]. IEEE transactions on knowledge and data engineering, 2017, 30(6): 1109–1121.
    [24] 陈磊, 吴润秀, 李沛武, 等. 加权K近邻和多簇合并的密度峰值聚类算法[J]. 计算机科学与探索, 2022, 16(9): 2163–2176. doi: 10.3778/j.issn.1673-9418.2102021

    CHEN Lei, WU Runxiu, LI Peiwu, et al. Weighted K-nearest neighbors and multi-cluster merge density peaks clustering algorithm[J]. Journal of frontiers of computer science and technology, 2022, 16(9): 2163–2176. doi: 10.3778/j.issn.1673-9418.2102021
    [25] ZHAO Jia, TANG Jingjing, SHI Aiye, et al. Improved density peaks clustering based on firefly algorithm[J]. International journal of bio-inspired computation, 2020, 15(1): 24. doi: 10.1504/IJBIC.2020.105899
    [26] DU Mingjing, DING Shifei, XUE Yu. A robust density peaks clustering algorithm using fuzzy neighborhood[J]. International journal of machine learning and cybernetics, 2018, 9(7): 1131–1140. doi: 10.1007/s13042-017-0636-1
    [27] YU Donghua, LIU Guojun, GUO Maozu, et al. Density peaks clustering based on weighted local density sequence and nearest neighbor assignment[J]. IEEE access, 2019, 7: 34301–34317. doi: 10.1109/ACCESS.2019.2904254
    [28] VINH N X, EPPS J, BAILEY J. Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance[J]. Journal of machine learning research, 2010, 11: 2837–2854.
    [29] FOWLKES E B, MALLOWS C L. A method for comparing two hierarchical clusterings[J]. Journal of the American statistical association, 1983, 78(383): 553–569. doi: 10.1080/01621459.1983.10478008
    [30] ZIMMERMAN D W, ZUMBO B D. Relative power of the wilcoxon test, the Friedman test, and repeated-measures ANOVA on ranks[J]. The journal of experimental education, 1993, 62(1): 75–86. doi: 10.1080/00220973.1993.9943832
    [31] 肖人彬. 面向复杂系统的群集智能[M]. 北京: 科学出版社, 2013.
    [32] 肖人彬, 冯振辉, 王甲海. 群体智能的概念辨析与研究进展及应用分析[J]. 南昌工程学院学报, 2022, 41(1): 1–21. doi: 10.3969/j.issn.1006-4869.2022.01.002

    XIAO Renbin, FENG Zhenhui, WANG Jiahai. Collective intelligence: conception, research progresses and application analyses[J]. Journal of Nanchang institute of technology, 2022, 41(1): 1–21. doi: 10.3969/j.issn.1006-4869.2022.01.002
    [33] 张曦, 李璠, 付雪峰, 等. 随机学习萤火虫算法优化的模糊软子空间聚类算法[J]. 江西师范大学学报(自然科学版), 2021, 45(2): 137–144. doi: 10.16357/j.cnki.issn1000-5862.2021.02.05

    ZHANG Xi, LI Fan, FU Xuefeng, et al. The fuzzy soft subspace clustering algorithm optimized by random learning firefly algorithm[J]. Journal of Jiangxi normal university (natural science edition), 2021, 45(2): 137–144. doi: 10.16357/j.cnki.issn1000-5862.2021.02.05
    [34] 肖人彬, 陈峙臻. 从群智能优化到群智能进化[J]. 南昌工程学院学报, 2023, 42(1): 1–10. doi: 10.3969/j.issn.1006-4869.2023.01.001

    XIAO Renbin, CHEN Zhizhen. From swarm intelligence optimization to swarm intelligence evolution[J]. Journal of Nanchang institute of technology, 2023, 42(1): 1–10. doi: 10.3969/j.issn.1006-4869.2023.01.001
    [35] 赵嘉, 谢智峰, 吕莉, 等. 深度学习萤火虫算法[J]. 电子学报, 2018, 46(11): 2633–2641. doi: 10.3969/j.issn.0372-2112.2018.11.010

    ZHAO Jia, XIE Zhifeng, LYU Li, et al. Firefly algorithm with deep learning[J]. Acta electronica sinica, 2018, 46(11): 2633–2641. doi: 10.3969/j.issn.0372-2112.2018.11.010
WeChat 点击查看大图
图(1)  /  表(14)
出版历程
  • 收稿日期:  2022-12-13
  • 网络出版日期:  2023-08-02

目录

    /

    返回文章
    返回