基于自然最近邻的密度峰聚类改进概率传播算法

0Array 15 (2022) 1002320or(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license(http://creativecommons.org/licenses/by-nc-nd/4.0/)。0ScienceDirect提供的目录列表0Array0期刊主页：www.elsevier.com/locate/array0一种基于自然最近邻的密度峰聚类改进概率传播算法0左文迪a，侯新民a，b，c，�0a中国科学技术大学数据科学学院，中国安徽省合肥市230026；b中国科学技术大学数学科学学院，中国安徽省合肥市230026；c中国科学技术大学吴文俊数学重点实验室，中国安徽省合肥市230026。0文 献 信 息0关键词：聚类，密度峰，自然最近邻，概率传播0摘 要0快速搜索和密度峰聚类（DPC）（自2014年以来）已被证明是一种有效的聚类方法，通过发现密度峰高效地发现聚类中心。DPC的准确性取决于截断距离（��），聚类数（�）和聚类中心的选择。此外，最终的分配策略是敏感的，容错性差。上述缺点使得该算法对参数敏感，并且只适用于某些特定数据集。为了克服DPC的局限性，本文提出了一种基于自然最近邻的密度峰聚类改进概率传播算法（DPC-PPNNN）。通过引入自然最近邻和概率传播的思想，DPC-PPNNN实现了非参数聚类过程，并使该算法适用于更复杂的数据集。在几个数据集上的实验中，DPC-PPNNN表现出优于DPC、K均值和DBSCAN的性能。01. 引言0聚类，也称为无监督分类，旨在根据数据样本（物理或抽象）的相似度度量将数据集划分为子集或聚类，使得子集或聚类内的数据样本具有高度相似性，而属于不同子集或聚类的数据样本具有高度不相似性[1]。目前，聚类分析在社会科学、生物学、模式识别、信息检索等许多领域中发挥着重要作用[2]。在机器学习和数据挖掘中非常有用，因此许多研究人员都对其给予了很多关注。在过去的几十年中，已经为不同类型的应用程序开发了许多优秀的聚类算法。典型的算法包括基于分区的K均值[3]和K中值[4]、基于层次的CURE[5]和BIRCH[6]、基于密度的DBSCAN[7]和OPTICS[8]、基于网格的WaveCluster[9]和STING[10]以及基于模型的统计聚类[11]。2014年，Rodriguez和Laio提出了一种基于密度的聚类算法DPC[12]（快速搜索和密度峰聚类，Science，344（2014）1492）。该算法DPC的主要思想如下：对于每个数据点�，我们计算两个量：其局部密度��和其距离��来自更高密度的点通过将所有数据点映射到以�和�为两个轴的决策图，我们可以识别密度峰点（聚类中心）。0�通讯作者：中国科学技术大学数据科学学院，中国安徽省合肥市230026，电子邮件地址：zuowendi@mail.ustc.edu.cn（左文迪），xmhou@ustc.edu.cn（侯新民）。0作为值的点， � � 和  � �都异常地大。在找到聚类中心之后，每个剩余点都被分配给与其具有更高密度的最近邻相同的聚类。DPC算法简单高效，可以快速找到高密度峰值点（聚类中心），而无需迭代计算目标函数。此外，它适用于大规模数据的聚类分析。尽管DPC算法相对于其他聚类算法具有明显优势，但也存在一些缺点：DPC的准确性取决于截断距离（ � � ），聚类数（ �）和聚类中心的选择。此外，最终的分配策略是敏感的，容错性差。最后，该算法基于以下假设：聚类中心周围的邻居具有较低的局部密度，并且它们与任何具有更高局部密度的点的距离相对较大。为了避免DPC的缺陷，在本文中，我们提出了一种基于自然最近邻的密度峰值聚类改进概率传播算法（DPC-PPNNN）。通过引入自然最近邻的概念，我们可以避免手动设置 � � 。通过计算  �  =  �  ×  �  和  �  = � �，我们可以自动选择聚类中心。最后，基于概率传播的聚类算法可以帮助我们分配所有剩余的数据点。通过所有这些操作，DPC-PPNNN适用于更复杂的数据集，并且可以区分彼此接近的两个聚类。0https://doi.org/10.1016/j.array.2022.100232收到日期2022年7月10日；接受日期2022年7月12日2(1))2(2)𝛿𝑖 = min𝑗∶𝜌𝑗>𝜌𝑖0Array 15 (2022) 1002320W. Zuo和X. Hou0本文的其余部分安排如下。在第2节中，我们介绍0减少与DPC算法相关的研究进展。在第3节中，我们简要回顾传统DPC算法的基本定义和流程，并揭示其中的一些问题。在第4.1节中，我们介绍自然最近邻的基本概念和算法。在第4.2节中，我们展示了局部密度的改进和自动选择聚类中心的方法。在第4.3节中，我们提出了基于概率传播的分配算法。在第5节中，我们使用各种合成和真实世界数据集比较DPC-PPNNN算法与其他经典聚类算法。在第6节中，我们总结了DPC-PPNNN算法的优缺点，并指出了我们未来研究的方向。02. 相关工作0DPC已被证明是一种有效的聚类策略，但它0也存在许多限制，例如密度估计指标的任意选择，聚类中心和错误传播的风险。在过去的几年中，已经提出了许多优化的DPC变体，考虑了以下方面：0第一个方面是改进DPC算法的密度测量0算法。Du、Ding和Jia[13]提出了DPC-KNN，引入了K最近邻（KNN）的概念到DPC，并为计算局部密度提供了另一种选择。他们还使用PCA来降低数据的维度。然而，该方法仍然受到DPC的限制，因为它在确定聚类中心和分配其余点时应用相同的过程。Liu、Wang和Yu[2]提出了SNN-DPC，它基于共享最近邻相似性的想法来估计局部密度。然而，它仍然受到手动选择聚类中心数量的限制。Mehmood等人[14]提出了CFSFDP-HD，它应用非参数密度估计器（核密度估计，KDE）来消除DPC对截断距离  � �的依赖。0第二个方面是自动识别0聚类和聚类中心。Liang和Chen提出了3DC，引入了分而治之的策略来确定理想的聚类数量。然而，它忽略了数据集的局部结构，可能导致缺失聚类。Xu，Wang和Deng提出了DenPEHC，它可以自动检测所有可能的中心并为数据集构建层次结构。然而，3DC和DenPEHC都会由于分层聚类策略而加剧错误的传播。Li，Ge和Su提出了一种用于确定聚类中心密度的自动聚类算法。在该算法中，如果潜在聚类中心与已知聚类中心之间的最短距离小于截断距离 � �，则认为潜在聚类中心是多余的中心。否则，它被视为另一个聚类的实际中心。0第三个方面是改进分配策略以减少0错误传播。在大多数DPC变体中，K最近邻的思想被混合在聚合策略中。例如，Zhou等人构建了通过连接高密度区域中具有最高相似度的点对来形成聚类的脉络。然后，其余点被分配给最近的脉络。Xie等人提出了一个两步标签传播的过程。第一步策略从密度峰值开始搜索K个最近邻来分配非离群值。第二步策略使用模糊KNN技术来分配其他点。Geng等人提出了基于KNN图的标签传播策略来分配剩余的点。Liu，Wang和Yu介绍了一种基于不可避免和可能的从属分配非中心点的两步分配方法。03. DPC算法和分析03.1. DPC算法0Rodriguez和Laio提出的DPC算法基于以下假设0假设聚类中心周围的邻居具有较低的局部密度，并且它们与具有较高局部密度的点的距离相对较远。描述每个数据点 � 的两个量：其局部密度 � �和其与更高局部密度点的距离 � �。0DPC算法提供了两种计算局部密度的方法0数据点 � 的局部密度的两种计算方法：截断距离方法和核距离方法。对于数据点�，其局部密度 � � 定义为0� �  0� ≠ � � ( � ��  −  � � ) ,0{ 1 , � <  000 , � >  00使用截断距离方法，或者0� �  0� ≠ �exp0− ( � ��0� �0使用核距离方法，其中 � �� 是数据点 � 和 � 之间的欧氏距离，� �（>0），截断距离，是扫描其邻域的点的半径，由用户设置。因此，局部密度 � � 与与 �距离小于 � � 的点的数量呈正相关。两种方法最明显的区别在于对于公式（1），� �是离散值，而对于公式（2），它是连续值。但是，对于这两种方法，� � 对 � �都很敏感。0因此，在DPC中，� � 被定义为0( � �� ) (3)0对于具有最高局部密度 � � 的数据点 �，� � 通常被定义为0� �  = max � ( � �� ) (4)0如同公式（3）所示，� � 是点 � 与最近邻点之间的最小距离0局部密度  � �  > � � 的点  � 。0计算了两个量之后： �  和  � ，我们可以识别0密度峰点（聚类中心）是指其  � �  和  � �  的值异常大，通过将所有数据点映射到以  �和  �为两个轴的决策图来确定。然而，有时我们无法从决策图中正确选择聚类中心，因为它们彼此太接近。相反，我们可以按照方程（5）中定义的  �对所有数据点进行排序，并选择最大的  � （聚类数）个数据点作为聚类中心。0� �  =  � �  ×  � � (5)0由于聚类中心已经找到，每个剩余点都是0分配给具有更高密度的最近邻的同一聚类中。03.2. 分析0尽管使用DPC获得的实验结果表明0DPC在许多情况下表现良好，但明显存在以下缺点。0首先，DPC的准确性取决于截断的设置0距离（ � �）。如图1所示，有一个双月数据集。红色点是我们选择的聚类中心，其他图片中也是如此。当我们改变  � �的值时，即使对于这个简单的数据集，DPC的聚类结果也会受到很大影响。0其次，聚类数（ � ）很难确定。实际上，0我们大部分时间对数据集的分布几乎一无所知，更不用说为DPC选择理想的聚类数（ � ）。图2显示了传统DPC算法在Donut3数据集上的结果30Array 15 (2022) 1002320W. Zuo and X. Hou0图1. 在双月数据集上使用传统的DPC算法的结果。（有关本图例中颜色的解释，请参阅本文的网络版本。）0图2. 在Donut3数据集上使用传统的DPC算法的结果。0图3. 在密度差异很大的两个高斯聚类数据集上使用传统的DPC算法的结果。0数据集。在图2(a)中，我们将外环识别为噪声，并将聚类数设为2。然而，显然，结果无法令人满意。在图2(b)中，我们将外环识别为一个聚类，并将聚类数设为3。即使我们正确选择了外环中的聚类中心，我们也无法获得理想的结果。第三，很难识别聚类的中心。如图3所示，有一个数据集，基于高斯分布有两个聚类，其中一个密度远大于另一个。即使我们选择了具有最大  � �的两个数据点作为聚类中心，它们都将属于具有更大密度的同一聚类。这种现象的原因是两个聚类之间的密度差异很大，我们几乎无法无论是通过决策图还是通过按 �对所有数据点进行排序来识别聚类的中心。最后，最终的分配策略是敏感的，容错性差。如图2(b)所示，即使我们正确选择了三个聚类中心，我们仍然无法获得理想的结果。仍然有一些数据点无法分配到正确的聚类中。为了克服上述缺陷，本文提出了一种基于自然最近邻的密度峰聚类改进概率传播算法（DPC-PPNNN）。通过0通过引入自然最近邻的概念，我们可以避免手动设置 � � 。通过计算 � = � × � 和 � = � �，我们可以自动选择聚类中心。最后，基于概率传播的聚类算法可以帮助我们分配所有剩余的数据点。通过这些操作，DPC-PPNNN可以适用于更复杂的数据集，并区分彼此接近的两个聚类。04. DPC-PPNNN04.1. 自然最近邻居0自然最近邻居（NNN）[21]与传统的�-最近邻非常不同。NNN是一个无尺度的概念，并且在选择邻居时不需要参数。每个数据点的NNN的大小可能根据数据集的分布而不同。以下是通过相关概念的定义精确描述自然邻域方法。设�={�1,�2，…，��}�R�为数据集。我们使用欧几里得距离�（��，��）来衡量点��和��之间的距离。对于给定的整数�>0，���（��）是��{��}中��的第�个最近邻。将��的�-最近邻邻域（���（��））定义为��的�个最近邻，即0���（��）=∪��=1{���（��）}。0�-反向最近邻邻域（����（��））是��{��}中的点��∈���（��），即0����（��）={��∈��{��}|��∈���（��）}。0�-自然最近邻邻域（����（��））定义为0显然，����−1（��）=��{��}≠�对于任何��∈�。0定义1（自然最近邻居（���））。对于�中的每个��∈�，使得����（��）≠�的最小整数�被称为�的自然特征值。我们定义����（��）为��的自然最近邻居，记为���（��）。4Algorithm 1 (Logarithmic) Natural Nearest Neighborhood SearchAlgorithm (NNN)𝑟 + 1𝜌𝑖 =∑𝑥𝑗∈𝑁𝑁𝑁(𝑥𝑖)exp−(𝑑𝑖𝑗𝜎𝑖)2,(6)𝛿𝑖 = max𝑗𝑑𝑖𝑗 ,𝐶𝑎𝑛𝐶𝑒𝑛𝑠 = {𝑥𝑖 ∈ 𝑋 𝛾𝑖 > 𝐸(𝛾) + 1.65Var(𝛾)},(7)(8)𝐶𝑒𝑛𝑠(𝑋) = {𝑥𝑖 ∈ 𝐶𝑎𝑛𝐶𝑒𝑛𝑠𝜃𝑖 − 𝐸(𝜃) < 1.96Var(𝜃)},(9)Sec𝐶𝑒𝑛𝑠(𝑋), so the allocation strategy of DPC cannot be used here. Weneed a new allocation strategy to cluster all the data points using thecenters in 𝐶𝑒𝑛𝑠(𝑋).0Array 15（2022）1002320W. Zuo和X. Hou0令����（�）={����（��）|��∈�}。注意����（�）可能0一个多重集。让0���0�（�）={��|��∈� with ����（��）=�}。0根据定义1，自然特征值�代表了搜索自然最近邻居���（�）的迭代次数。0在搜索自然最近邻居���（�）=����（�）的过程中迭代次数。当���0�（�）在其不变时，引入ln�+ln�作为阈值来控制迭代次数，0为了减少数据集�中异常值或噪声的影响，我们在0自然最近邻居如下：0即���0�（�）=���0�+1（�）。形式上，我们定义对数0|{�|�≤�−1 with ���0�（�）=���0�+1（�）}|≥ln�+ln�0定义2（对数自然最近邻居）。我们称最小整数�为0根据定义2，对数自然特征值�代表了0定义对数自然特征值，并将����（��）定义为��的对数自然最近邻居，记为���（��），对于��∈�。0算法1（对数）自然最近邻居搜索算法（NNN）0在搜索对数自然最近邻居���（�）的过程中迭代次数，该过程将受到ln�+ln�的限制。数自然最近邻居���（�）可能包含一个空集。本文提出的基于NNN搜索算法[21]的鲁棒（对数）自然最近邻居搜索算法如Alg. 1所示。0输入：一组点  �  = { � 1 , � 2 , ..., � � }  �  R �0输出：(对数)自然特征值  �  =  �  和每个  � �  ∈  �  的  ��� ( � � ) = ��� � ( � � )01:  对于所有  � �  ∈  � ，最初设置  �� 0 ( � � ) = � ，  ��� 0 ( � � ) = � ，  ���，flag=0,  �  = 0 3:  当 flag=0  时循环 4: 对于所有  � �  ∈  �  执行05: 计算  �� � ( � � ) =  � �06: 重置  �� � ( � � ) =  �� � −1 ( � � ) ∪ { � � }07: 重置  ��� � ( � � ) =  ��� � −1 ( � � ) ∪ { � � }08: 重置  ��� � ( � � ) =  �� � ( � � ) ∩  ��� � ( � � )09: 结束 对于010: 计算集合  ��� 0 � ( � )011: 如果  ��� 0 � ( � )  保持不变  则014: 如果  �  ≥  ln  �  + ln  �  或  � �  ��� � ( � )  则016: 否则018: 结束 如果019:  结束 循环0备注。Zhu等人提出的NNN搜索算法不考虑异常值或噪声。相反，通过引入 ln  �+ ln  �作为阈值，我们提出的鲁棒自然最近邻搜索算法可以识别异常值并消除其影响。04.2. 局部密度估计和聚类中心的选择0如第4.1节所示，NNN是一个无标度的概念，并且不需要在选择邻居时的参数。DPC中的参数  � �0在选择邻居时需要参数。通过改变基于NNN的局部密度定义，可以避免DPC中的参数  � � 。对于任何数据点  � � ，新的局部密度定义为0其中  � �  = max{ � ( � � , � � )  |  � �  ∈  ��� ( � � )}。我们定义0对于具有最高局部密度  � �  的数据点  � ，定义0这与DPC中的定义相同。0令  � �  =  � �  ×  � �  如等式 (5) 中所定义。我们可以从CanCens中选择候选0基于标准正态分布的一个单侧95%置信区间定义候选中心点为0其中  � ( � )  是  �  的期望，Var ( � )  是  �  的方差，1.65是标准正态分布的95%分位数。0根据CanCens的定义，它不包含数据点0具有低局部密度  � �  和小距离  � � ，但可能存在一些具有大  �  和小  � 或小  �  和大  �的数据点，这些数据点不适合作为聚类中心。为了消除这些数据点，我们定义0其中1.96是标准正态分布的97.5%分位数。0在提供的概率传播聚类算法中04.3. 概率传播聚类算法0概率传播聚类算法的思想是0基于近年来流行病的传播。感染者会传染他们接触的人。因此，我们首先选择在  ����( � )  中具有最大局部密度  �的数据点作为零号病人。此外，他将传染他接触的人，即他的自然最近邻（ ���）。这些邻居将传染他们的自然最近邻，传播将继续，直到没有可以被感染的邻居。此时，我们将所有感染的数据点识别为一个簇。我们称形成一个簇的过程为一轮传播。其次，我们选择在  ���� ( � )中未被感染的数据点中具有最大局部密度的数据点，并重复上述过程，直到  ����中的所有数据点都被感染。0在现实世界中，即使有些人接触到感染者，也不会被感染0他们接触到感染者是因为他们具有抗体或其他原因。因此，在算法中，数据点  �∈  �  以一定的概率  � �  =  �  �  ( � ′ � +  � ′′ � ) 被感染，其中  � ′ � （和  � ′′ � ）5𝑝′𝑥 =𝑝′′𝑥 =0数组15（2022）1002320W. Zuo 和 X. Hou0表示  �  在当前传播轮次中的排名。形式上，在当前传播轮次中，如果点  �（待检查）和感染点可以被排序  � 1 ,  …  , � � −1 , �, � � +1 ,  …  , � �  满足  � ( � ≤  � ( � � −1 )  ≤  � ( � )  ≤  � ( � � +1 )  ≤  …  ≤  � ( � � ) ，那么我们定义0�0� 1 ,  …  , � � −1 , �, � � +1 ,  …  , � �  满足  � ( � 1 )  ≤  …  ≤  � ( � � −1 )  ≤  � ( ≤ …  ≤  � ( � � ) ，那么我们定义0�。0如果点  �  没有被感染，我们认为它具有抗体或其他原因0死亡并且不会再被感染。在传播过程开始时，我们增加被感染的概率  � �以确保传播过程会继续。在传播过程结束时，我们减少被感染的概率  � �以确保异常值或噪声不会被分类到任何簇中。0算法2  概率传播聚类算法（PP）0输入：点集  � �  R � ，  �  =  � ( � ) ，  ��� ( � ) 输出：聚类结果  ���1：初始设置  ����  =  ���� ( � ) 2： �  = 1 3：  �  =  ���� (max  � ( ���� ));  ����  =����  �  { � }; ��� ( � ) = � ,  ;  ��� ���  =  ��� ( � ) ;04：当  ��� ���  ≠  �时执行5：对于所有的  �  ∈  ��� ��� 执行06：计算 y 被感染的概率：  � �07：如果  �  被感染（概率为  � � ）则08：重置  ��� ( � ) =  ��� ( � ) ∪ { � }09：重置  ��� ���  =  ��� ���  ∪  ��� ( � )010：如果  �  ∈  ����  则011：重置  ����  =  ����  �  { � }012：结束如果013：否则014：y不属于任何簇015：结束如果016：重置  ��� ���  =  ��� ���  �  { � }017：结束循环018：结束循环19：如果 ����  ≠  �  则20： �  =  �  + 1021：转到步骤3022：结束如果23：将剩余的数据点分配到其自然最近邻中局部密度之和最大的簇中0传播过程结束后，将会有一些数据点0未被感染且不是异常值的数据点。我们将每个剩余数据点分配给包含它的自然最近邻居中局部密度之和最大的簇。0通过引入概率传播的思想，我们可以使聚类算法更接近现实。此外，我们可以区分彼此接近0更接近现实的聚类算法。此外，我们可以区分彼此接近的两个簇。概率传播聚类算法如算法2所示。记 �（�）= {�（�） | � ∈ �}。05. 实验0我们将算法1和2一起称为DPC-PPNNN算法0算法。为了测试DPC-PPNNN算法的性能，我们使用经典的合成数据集和真实世界数据集。此外，我们将传统的DPC、K均值和DBSCAN作为对照组，0表1 合成数据集。0数据集 记录数 属性数 簇数02d-4c-no9 876 2 4 3-spiral 312 2 3 Aggregation 788 2 7 Cassini 1000 2 3Complex9 3031 2 9 Compound 399 2 6 Dartboard1 1000 2 4 Jain 373 2 2 R15600 2 15 Shapes 1000 2 40表2 真实世界数据集。0数据集 记录数 属性数 簇数0数据集 记录数 属性数 簇数0K均值和DBSCAN算法是在Python的sklearn库中实现的，而DPC算法（不包括“Halo”部分）是基于作者提供的源代码，因为我们的数据集不包含噪声。所有显示的结果都是参数调整后的最佳结果。0真实世界数据集。0分别在表1和表2中呈现。0实验中使用的合成数据集和真实世界数据集0为了评估聚类算法的性能，引入了三个评价指标05.1. 准备工作0在测试之前，所有真实世界数据集都应进行调整0引入评价指标，即调整兰德指数（ARI）、调整互信息（AMI）和Fowlkes-Mallows指数（FMI）。这三个指标的上限为1，换句话说，指标的值越大，表示聚类结果越好。0�′�=0通过最小-最大归一化来消除不同维度范围的差异，如公式（10）所示。0其中 ��� 是��位置的原始数据。0为了更客观地反映各种算法的实际结果，0我们对每个算法进行参数调整，以确保它们的最佳性能得到比较。对于K均值，我们只需给出正确的簇数。对于DBSCAN，我们使用网格搜索找到最佳的参数配置。对于传统的DPC，我们从1%到2%选择最佳的��，并在密度估计过程中应用高斯核。05.2. 合成数据集0在这部分中，我们选择了一些合成数据集0广泛用于测试聚类算法的性能。这些数据集在分布和点数以及簇的数量方面都不同。它们可以模拟不同情况，以比较不同场景下各种聚类算法的性能。0表3显示了ARI、AMI和0FMI得分在表1中列出的所有合成数据集上。得分最高的评估标准用粗体标记，我们可以看到在大多数情况下，DPC-PPNNN获得了最高分，除了60Array 15 (2022) 1002320W. Zuo和X. Hou0图4. 第3.2节中三个反例的重新聚类结果。（有关本图图例中颜色的解释，请参阅本文的网络版本。）0图5. 四种算法在2d-4c-no9上的聚类结果0图6. 四种算法在3-spiral上的聚类结果0图7. 四种算法在Aggregation上的聚类结果0图8. 四种算法在Cassini上的聚类结果0Complex9（其中DPC-PPNNN的得分略低于DBSCAN）。在图4中，我们通过DPC-PPNNN重新对第3.2节中的三个反例进行聚类。显然，结果比原始的DPC要好得多，这意味着我们的算法可以克服DPC的缺陷。接下来，我们将展示DPC-PPNNN和对照组算法在合成数据集上的一些典型聚类结果。图中不同颜色的点分配给不同的0簇。从DPC和DPC-PPNNN获得的簇中心标记为红色。在图5中，我们可以看到2d-4c-no9数据集有四个簇，其中一个簇的密度非常高。DPC-PPNNN成功地检测到了所有这些簇，而对照组中的其他算法未能做到。0图6显示了3螺旋数据集上每个算法的结果。DPC-PPNNN能够正确识别四个簇。此外，DPC70Array 15 (2022) 1002320W. Zuo和X. Hou0图9. 四种算法在Complex9上的聚类结果0图10. 四种算法在Compound上的聚类结果0图11. 四种算法在Dartboard1上的聚类结果0图12. 四种算法在Jain上的聚类结果0图13. 四种算法在R15上的聚类结果0图14. 四种算法在Shapes上的聚类结果8DPC-PPNNN(ours)0.93750.93450.95431.00001.00001.0000DPC [12]0.39290.66660.49400.74390.84100.8145K-means [3]0.34610.61610.45171.00001.00001.0000DBSCAN [7]0.99980.99940.99981.00001.00001.0000DPC-PPNNN(ours)0.57610.56140.71600.86800.84460.9114DPC [12]0.26600.31790.43610.54140.67800.7539K-means [3]0.41150.59210.54820.71630.73870.8112DBSCAN [7]0.10040.12750.52820.56810.73160.7715DPC-PPNNN(ours)0.25950.34500.55340.75220.61080.8827DPC [12]0.06510.09840.35160.21050.23010.7530K-means [3]0.16620.29420.39450.62830.59090.8546DBSCAN [7]0.23820.35770.55000.67150.49110.8606DPC-PPNNN(ours)0.23800.21860.54320.71930.60540.8671DPC [12]0.00030.00020.70500.47050.46140.7860K-means [3]0.34880.26920.67550.73020.62260.8770DBSCAN [7]0.08610.12420.34170.22010.26180.6091DPC-PPNNN(ours)0.52870.41140.79350.74210.72680.8277DPC [12]0.00190.00130.73020.69900.72330.8006K-means [3]0.17760.13300.60530.85370.84000.9026DBSCAN [7]0.72140.63430.87790.42290.52090.64820Array 15 (2022) 1002320W. Zuo和X. Hou0和DBSCAN大部分能够正确识别四个簇，但尾部可能有一些错误数据点，可能是因为参数设置不正确，而KNN则完全无法识别。0DPC-PPNNN和其他三种算法的聚类结果0对照组中的算法在Aggregation数据集上的聚类结果如图7所示。该数据集可以被DPC-PPNNN和DPC正确检测。K均值无法做到这一点，因为对于K均值来说，该数据集有些复杂。DBSCAN无法区分右侧的两个簇。0从图8的聚类结果中，我们可以看到DPC-PPNNN0和DBSCAN能够检测Cassini数据集中的簇。尽管DPC能够找到正确的簇中心，但未能正确分配其他剩余的数据点。三个簇的形状不均匀，这导致K均值的错误聚类结果。0图9显示了四种算法在Complex9上的结果0数据集。DBSCAN能够成功识别所有簇。而对于DPC-PPNNN，一些簇的尾部可能有一些错误分类的点，因为这些点之间的连接不够紧密。DPC找到了正确的簇中心，但未能正确分配其他剩余的数据点。K均值的性能较差。0图10显示了在Compound数据集上的结果。DPC-PPNNN0能够大部分正确识别簇，并且也能识别噪声。DBSCAN擅长识别噪声，但也会将许多数据点误分类为噪声。DPC和K均值无法识别带有噪声的簇。0如图11所示，Dartboard1数据集有四个同心圆0环。DPC-PPNNN和DBSCAN的表现完美。DPC无法找到正确的簇中心，因为数据点的密度差异很小。此外，K-means的性能较差。0对于图12中的Jain数据集，只有DPC-PPNNN能够正确0识别所有簇。DPC未找到正确的簇中心，因为两个簇的密度差异太大。DBSCAN的性能也同样不佳。K-means不适用于具有流线形状的数据集。0图13显示了R15数据集的结果。0点使其成为所有算法中最直接的数据集。尽管它们之间存在一些小缺陷，但所有算法都能识别出簇和中心。0图14中显示的聚类演示了解决问题的能力0不同形状的簇的数据集。DPC-PPNNN、K-means和DBSCAN都表现良好。只有DPC无法检测到簇，因为存在具有流形结构的簇。05.3.真实世界数据集0在本节中，使用了8个UCI数据集，如表2所示，用于0展示了DPC-PPNNN聚类算法的性能。这些数据集在样本数量、特征数量和簇数量方面都有所不同。如表4所示，DPC-PPNNN在测试案例中表现几乎最佳。06.结论0在本文中，我们提出了一种改进的概率传播算法-0基于自然最近邻的密度峰聚类算法（DPC-NNN）。新算法不需要任何参数，可以自动识别簇中心。受传播流行病的启发，DPC-PPNNN的最终聚类过程表现良好，特别是对于区分彼此接近的两个簇。0然而，由于该算法基于密度和概率，0其性能还不够好和稳定，特别是当所有数据点具有相似的  �  或相似的密度  �时。未来的工作将致力于解决这些问题。0竞争利益声明0作者声明他们没有已知的竞争性财务关系0特别利益或个人关系可能会影响本文报告的工作。0表3不同聚类算法在不同合成数据集上的性能。0算法 ARI AMI FMI ARI AMI FMI02d-4c-no9化合物0DPC-PPNNN(我们的) 0.9931 0.9898 0.9951 0.9375 0.9345 0.9543 DPC [ 12 ] 0.3336 0.52610.6108 0.5099 0.7542 0.6235 K-means [ 3 ] 0.8952 0.9007 0.9241 0.5364 0.7128 0.6410DBSCAN [ 7 ] 0.8412 0.8810 0.8940 0.8774 0.8673 0.910303-螺旋Dartboard10DPC-PPNNN(我们的) 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 DPC [ 12 ] 0.9521 0.94060.9680 0.0006 0.0130 0.3213 K-means [ 3 ] − 0.0060 − 0.0055 0.3274 − 0.0030 − 0.00330.2470 DBSCAN [ 7 ] 0.9953 0.9918 0.9969 1.0000 1.0000 1.00000聚集Jain0DPC-PPNNN(我们的) 0.9927 0.9881 0.9943 1.0000 1.0000 1.0000 DPC [ 12 ] 0.9978 0.99560.9983 0.6438 0.5951 0.8502 K-means [ 3 ] 0.7624 0.8776 0.8159 0.3241 0.3677 0.7005DBSCAN [ 7 ] 0.8719 0.9223 0.9051 0.9350 0.8476 0.97420Cassini R150DPC-PPNNN(我们的) 1.0000 1.0000 1.0000 0.9928 0.9938 0.9932 DPC [ 12 ] 0.4886 0.58790.6736 0.9857 0.9885 0.9866 K-means [ 3 ] 0.5308 0.5400 0.7012 0.9928 0.9938 0.9932DBSCAN [ 7 ] 1.0000 1.0000 1.0000 0.8307 0.8905 0.84160复杂的形状0表4 不同聚类算法在不同真实世界数据集上的性能。0算法 ARI AMI FMI ARI AMI FMI0大肠杆菌 鸢尾花0玻璃 甲状腺0心脏-statlog Wdbc0Iono 葡萄酒0致谢0该工作得到了国家自然科学基金0中国国家自然科学基金（No.12071453），中国国家重点研发计划（2020YFA0713100），中国安徽量子信息技术倡议（AHY150200）和中国量子科学技术创新计划（2021ZD0302904）的支持。0参考文献0[1] Tan PN, Steinback M, Kumar V. 数据挖掘导论。数据挖掘。2011。0[2] Liu R, Wang H, Yu X. 基于共享最近邻的快速搜索聚类0并发现密度峰值。Inform Sci 2018;450:200–26。90Array 15 (2022) 1002320W.左和X.侯0[3] Macqueen JB. 多元观测分类和分析的一些方法。在：1967年第五届伯克利数学统计和概率研讨会论文集。1967。0观测。在：1967年第五届伯克利数学统计和概率研讨会论文集。1967。0[4] Kaufmann L, Rousseeuw PJ. 通过中位数进行聚类。北荷兰；0[5] Guha S, Rastogi R, Shim K. Cure: 大规模高效的聚类算法0数据库中的数据聚类。Inf Syst 1998;26:35–58。0[6] Zhang T, Ramakrishnan R, Livny M. Birch: 一种高效的数据聚类方法0用于非常大型数据库。ACM SIGMOD Rec 1996;25:103–14。0[7] Ester M, Kriegel HP, Sander J, Xu X. 一种基于密度的发现算法0大型空间数据库中的噪声聚类。AAAI出版社；1996。0[8] Ankerst M, Breunig MM, Kriegel HP, Sander J. Optics: 对点进行排序0识别聚类结构。在：SIGMOD 1999年，ACMSIGMOD国际数据管理会议论文集，1999年6月1-3日。美国宾夕法尼亚州费城；1999。0[9] Sheikholeslami G, Chatt