【《密度峰值聚类算法的改进算法的比较分析》3900字】

密度峰值聚类算法的改进算法的比较分析目录TOC\o"1-3"\h\u14358密度峰值聚类算法的改进算法的比较分析 1234091.1引言 1294401.2局部密度优化算法的比较与分析 2194851.2.1数据集说明 2131401.2.2决策图对比 3287301.2.3聚类结果比较 4172431.3时空复杂度优化算法的验证与改进 6184791.3.1算法有效性的验证 7112631.3.2实验结果异常数据分析 889211.3.3算法的改进方案 81.1引言 本章对算法的实现均基于python，计算机所用操作系统为Windows10，处理器为Intel(R)Core(TM)i7-9750H，内存大小为16GB，编译器为pycharm2019，软件前端通过Django框架实现，主要软件界面如图4-1所示：（a）软件界面-数据集选择（b）软件界面-算法选择（c）软件界面-决策图生成（d）软件界面-聚类结果及评价指标图4-1主要软件界面展示1.2局部密度优化算法的比较与分析 密度峰值聚类算法的聚类过程存在主观选择影响，直接出示实验结果对于理解算法的改进思路存在局限性，无法直观地感受到算法之间的差异。 例如，RDO-DPC的改进在于决策图的优化，但可以通过主观选择聚类中心，也可以使得原算法和改进算法达到同等的聚类效果。但RDO-DPC优化之后的决策图，相比于原算法更适合程序计算，对于密度峰值聚类算法的去主观选择和自动化有实际意义。 故本节的对比与分析将由三个部分构成：数据集说明、决策图对比、聚类结果比较。 1.2.1数据集说明 本次对比实验用到的数据集分为聚类常用数据集和生成数据集。其中生成数据集由python库函数完成，此类数据集可以更好地针对改进算法的某一特点进行检测。 本次对比实验涉及到的常用数据集如表4-1所示。表4-1常用数据集说明数据名特征数样本数实际类数AggregationFlameIrisJainSpiralSynthesis2222227882401503733121980723235 使用到的生成数据集如图4-2所示。（a）blob数据集（b）moon数据集（c）circle数据集图4-2生成数据集 图4-2(a)为sklearn库生成的blob数据集，是随机生成的满足正态分布的数据集，可以控制生成数据集大小，簇的数量和离散程度。图4-2(b)为sklearn库生成的moon数据集，数据集呈现出流形特征，可以控制生成数据集大小和簇的离散程度。图4-2(c)为sklearn库生成的circle数据集，可以控制生成数据集的大小，簇的离散程度和两个圆之间的间隔大小。 1.2.2决策图对比 决策图作为算法最重要的步骤，如何优化决策图和实现决策图质心的自选取也是密度峰值算法的重要改进方向。而决策图也与手工确定的参数有关，为了让决策图的选取尽量客观和贴近各自的算法本意，本文所涉及到的决策图均为算法呈现出最优解时的决策图，见图4-3。（a）DPC-在Aggregation（b）RDO-DPC在Aggregation（c）KDE-DPC在Aggregation（d）DPC在Flame（e）RDO-DPC在Flame（f）KDE-DPC在Flame（g）DPC在Iris（h）RDO-DPC在Iris（i）KDE-DPC在Iris（j）DPC在Jain（k）RDO-DPC在Jain（l）KDE-DPC在Jain（m）DPC在Spiral（n）RDO-DPC在Spiral（o）KDE-DPC在Spiral（p）DPC在Synthesis（q）RDO-DPC在Synthesis（r）KDE-DPC在Synthesis图4-3DPC、RDO-DPC和KDE-DPC在各数据集的决策图对比 在决策图比较中，RDO-DPC算法相比于KDE-DPC算法和原算法更具优势。 在通过决策图确定质心时，除了观察决策图寻找右上角的离群点之外，对数据集的先验知识也可以帮助使用者更好地选择出聚类中心。例如，图4-3(g)(h)(i)三张图，Iris数据集本身存在3个簇类，但其中两个簇类的区分与第三个簇类的区分相比要更加困难，观察决策图很难发现到第三个簇中心的存在，而依据先验知识则可以挑出不太明显的第三个决策中心。 在这种情况下，RDO-DPC的决策图更加优秀，使用者可以直接向下顺延多选择一个点作为质心即可以完成聚类，而其他两种算法则需认真观察决策图以寻找第三个质心。这是RDO-DPC算法相比于其他两种算法存在的优势，RDO-DPC算法的质心选取更加直观且易于增加，更适合程序自动截取。 1.2.3聚类结果比较 算法在各种数据集上聚类结果的评价指标见表4-2。 分析表4-2，两个改进算法相比于原算法的聚类精度在大部分数据集上均有所提升，其中，KDE-DPC在Jain和Spiral等流形数据集上相比于原算法的精度有较大的提升，同时也有着更好确定的参数。在Aggregation和Iris数据集上，虽然三者能取得十分接近的聚类结果，但RDO-DPC的质心选取更加简单直观，可以通过更少的实验次数获得更好的实验结果。（a）DPC在Jain上的聚类结果（b）RDO-DPC在Jain上的聚类结果（c）KDE-DPC在Jain上的聚类结果（d）DPC在Spiral上的聚类结果（e）RDO-DPC在Spiral上的聚类结果(f)KDE-DPC在Spiral上的聚类结果图4-4各算法在Jain和Spiral数据集上的比较 表4-2算法在各种数据集上的评价指标对比数据集算法FMIRIARIAMIAggregationDPCRDO-DPCKDE-DPC0.998270.998270.998270.999250.999250.999250.997800.997800.997800.995630.995630.99563FlameDPCRDO-DPCKDE-DPC0.984591.01.00.983401.01.00.966611.01.00.935251.01.0IrisDPCRDO-DPCKDE-DPC0.947780.923430.923260.965630.949530.949530.922170.885790.885660.899880.868890.86054JainDPCRDO-DPCKDE-DPC0.834800.850231.00.808000.825131.00.609960.643771.00.569990.595091.0SpiralDPCRDO-DPCKDE-DPC0.430321.01.00.522361.01.00.041341.01.00.100791.01.0SynthesisDPCRDO-DPCKDE-DPC0.991300.992550.992970.991460.992710.993120.982920.985410.986240.959350.960240.96024 在实验中发现，当带宽参数h取值接近0时，KDE-DPC对于流形数据集均能表现出较好的聚类结果。相比之下，RDO-DPC和DPC算法则往往需要针对数据集手动确定合适的截断距离，反复多次才能取得较好的实验结果，时间成本较高。三种算法在Jain和Spiral上的聚类结果对比如图4-4所示。 虽然KDE-DPC算法在流形数据集上表现出了更为优秀的聚类结果，但对于数据集circle和path-based之类流形特征更加明显或数据分布情况更为多样的复杂流形数据集，算法能够取得的聚类结果依然比较有限。 在图4-5中可以看到，KDE-DPC在该类数据集的聚类效果较差，对于数据集外圈的圆环，不能进行有效的识别与聚类。面对复杂的流形数据集聚类上，一般学者更倾向于使用新的流形距离计算方法以使得密度峰值聚类算法可以更好地识别流形数据集。（a）KDE-DPC在circle上的聚类结果（b）KDE-DPC在path-based上的聚类结果图4-5KDE-DPC在circle和path-based上的聚类结果 综上所述，RDO-DPC相比于其他两种算法提供了更优秀的决策图，更适合于程序的自动化选择，而KDE-DPC则提供了流形数据集上更稳定的参数选择和适应性更好的聚类效果，两者各有所长。1.3时空复杂度优化算法的验证与改进 在3.3中，本文对于G-DPC算法的优化原理做了简单的介绍并分析了算法在密度差异较大的数据集上，由于粒度划分过少导致的质心点丢失问题做了阐述。本节将使用数据对于G-DPC算法的有效性做实验验证，并对于实验预期之外的异常数据做理论分析，最后对于3.3.2节中的问题提供一个可行的改进方法。1.3.1算法有效性的验证 在原文中作者已经对算法的时空复杂度做出了理论分析，本文直接使用算法耗时对其时间优化的有效性进行描述，并提供了更多的评价指标以验证G-DPC算法在耗时降低之后仍然具有聚类价值。 算法耗时的对比主要考虑数据集的规模，本节使用不同规模的生成数据集blob作为评价数据集，令数据集中心数为5，可得包含5个符合正态分布的簇的数据集。有效性对比依然使用算法在各数据集上的聚类效果做评价。 实验结果如表4-3和表4-4所示。可以发现，随着数据集规模的增长，DPC算法的实验时间耗时基本呈现出平方级别的上升，而G-DPC算法的耗时则有更好的表现，同时相比于DPC算法，G-DPC算法在聚类精度上损失并不多，仍然可以保持较为合理的聚类结果。 表4-3DPC算法与G-DPC算法耗时对比样本大小DPC耗时(s)G-DPC耗时(s)1k2k3k4k5k6k7k8k9k10k3.11568498611450212.14702701568603528.08788180351257349.14759993553161671.67314291000366111.83131432533264148.08308219909668198.4140808582306255.26737451553345312.499930858612060.20545148849480.74303197860711.70346236228943.05486512184145.20809674263005.65020227432255.00290822982787.216217994689912.49959850311215.712902307510表4-4G-DPC与DPC的性能比较数据集算法FMIRIARIAMIAggregationDPCG-DPC0.998270.991440.999250.996300.997800.989070.995630.97729FlameDPCG-DPC0.984590.976740.983400.975200.966610.950200.935250.91134IrisDPCG-DPC0.947780.935590.965630.957490.922170.903870.899880.89843SynthesisDPCG-DPC0.991300.985680.991460.985830.982920.971660.959350.942991.3.2实验结果异常数据分析 对表4-4做观察，注意到在样本大小为7k时G-DPC的算法耗时反而小于6k时的耗时，对此异常数据，本文作如下分析。 如图4-6所示案例，图4-6(a)为Flame数据集，数据集有样本点240个，划分之后生成非空网格143个。图4-6(b)和(c)为大小为300的blob数据集划分，划分之后生成非空网格69个。前者计算耗时0.0928秒，后者耗时0.0359秒。（a）Flame数据集网格划分结果（b）大小为300的blob数据集（c）大小为300的blob数据集划分结果图4-6G-DPC算法在不同数据集上的划分 Flame数据集相比于blob数据集的离散程度更高，意味着描述该数据集使用的非空网格更多，而G-DPC算法的时间复杂度依赖于非空网格，故在该数据集上G-DPC的提升效果更有限。 以此案例可知，7k数据集小于6k的原因为随机生成的7k数据集离散程度更低，所以拥有更短的耗时，异常数据的原因分析完毕。1.3.3算法的改进方案 3.3.2节中阐述了G-DPC在密度不匀数据集会产生较差的决策图使得聚类效果不佳，而前文所述的RDO-DPC算法即是对于该情况的解决方案，基于此，本节将对两种算法进行结合，使用RDO-DPC算法对于G-DPC算法进行改进，使得其可以获得在密度不均匀数据集上更好的决策图。 改进算法的核心思想在于使用G-DPC降低时空复杂度，将G-DPC的网格密度作为该网格的权重，之后使用样本点代替网格，重新生成新样本空间。再使用RDO-DPC对新生成的样本空间做重新聚类，算法的重要参数计算公式如下。 新样本空间样本的权值：w 局部密度计算公式：ρ 领域内样本点数量计算公式：N 其中，φx 改进算法流程如下：G-DPC改进算法输入:数据集S输出：聚类结果（1）基