【《密度峰值聚类算法的改进算法概述》3100字】

密度峰值聚类算法的改进算法概述目录TOC\o"1-3"\h\u7606密度峰值聚类算法的改进算法概述 1226531.1引言 1294631.2基于局部密度计算方式优化的密度峰值聚类算法 1253821.2.1基于相对密度优化的密度峰值聚类算法 1126211.2.2基于核密度估计的密度峰值聚类算法 446221.3基于时空复杂度优化的密度峰值聚类算法 5234541.1.1基于自适应网格划分的密度峰值聚类算法 549021.1.2算法的缺点分析 71.1引言 针对密度峰值聚类算法的改进方向可以总结为两大类，面向聚类精度的优化和面向计算效率优化ADDINNE.Ref.{48587825-2C62-4567-8145-23591813C34B}[7]，其中面向聚类精度的优化方法主要研究方向集中于局部密度计算方式的优化。在上一章中完成了密度峰值聚类算法的基础理论部分的介绍和缺点分析，本章将会介绍和实现两种局部密度计算方法优化和一种时空复杂度优化的算法，其中对于时空复杂度优化算法额外做缺点分析，以便于下一章中优化算法的展开。1.2基于局部密度计算方式优化的密度峰值聚类算法 该类优化算法通过修改原算法中局部密度ρi1.2.1基于相对密度优化的密度峰值聚类算法 在理解并实现该算法的思想之前需要先了解一种新的决策图表示方法。通过前文所述，易知越靠近于决策图右上角的样本点越容易被选择为聚类质心。已知靠近于右上角的样本点具有更高的局部密度ρi和相对距离δi，则 使用新的决策图表示方法，当数据集情况较为复杂，直观上难以确定质心的选择时，可以使用新决策图，从左往右选择具有明显断层的样本点作为质心，相比于原决策图，选择右上角的离群点的做法，新决策图可以帮助主观选择出更好的结果，也更适合由程序进行自动选择。图3-1由图2-2变换的新决策图 在了解了新的决策图和选择方法之后，则易发现原算法存在的一个问题，原算法的局部密度计算方式使得低密度的簇质心的ρi（a）Synthesis数据集（b）截断距离设置为2%的决策图（c）变换之后的新决策图（取样本前20）（d）根据新决策图选择后的聚类结果图3-2DPC算法对于Synthesis的聚类过程 可以发现，DPC算法在处理Synthesis数据集时，由于数据集中的两个簇具有较小的密度，在生成决策图时，真实的簇类中心（点17和点18）在原决策图中反而靠近左上，而在新决策图中，由于密度较低，无法被识别为质心，导致分类原算法在该数据集上的决策点选择错误并使得聚类结果较差。 为了解决此类问题，使得算法能够在密度不匀数据集上生成更好的决策图，ZHANGADDINNE.Ref.{2FB0DF71-729E-4F47-BFCD-E9C7ECD72BFF}[14]在研究中提出了基于相对密度优化的密度峰值聚类算法（简称RDO-DPC算法）。 算法在局部密度的基础上重新定义了相对局部密度ρiρ 其中，Ni(a)RDO-DPC的决策图（b）变换后的新决策图图3-3RDO-DPC算法对于Synthesis生成的决策图 使用相对密度计算产生的决策图观察效果更好，可以更好地帮助研究人员在密度不均匀样本上选择正确的聚类质心，也可以简单地设置让程序根据ρi图3-4RDO-DPC的聚类结果 相比于原算法，RDO-DPC聚类算法在密度不均匀数据集上对主观选择的帮助可以取得更好的聚类结果，但据原文所述，该算法的时间复杂度要略高于原算法。1.2.2基于核密度估计的密度峰值聚类算法 该算法由金志刚等人ADDINNE.Ref.{875D2FA9-5F7D-49F1-A81B-BBA7837DF94F}[15]借鉴Mehmood的改进算法之后提出，使用Gaussian核函数对样本点进行核密度估计，使用样本点之间的相互影响程度代替局部密度ρi，可以避免截断距离选取导致的聚类错误，使算法更具有鲁棒性，本文中称为KDE-DPC。核密度计算公式如下： k 局部密度ρi ρi=1njkd,dj;h#3−3

在实验中发现，该算法当带宽趋于0时，可以很好地对流形数据集实现聚类，聚类过程如图3-5所示：（a）spiral数据集（b）带宽接近0时算法产生的决策图（c）算法的聚类结果图3-5KDE-DPC算法在数据集spiral上的聚类过程 相比于原算法，KDE-DPC算法在流形数据集上有更好的效果，同时时空复杂度与原算法相差不多。1.3基于时空复杂度优化的密度峰值聚类算法 该类优化算法降低原算法的时空复杂度以提高算法在大数据集上的应用价值，而使用网格替代原数据点的方法，是比较常见的优化方法。但在使用网格划分时，往往需要面对步长划分的问题，如何确定网格的大小，使得划分时能在保留原数据集特点的同时使用尽可能少的网格对原数据集进行描述。1.1.1基于自适应网格划分的密度峰值聚类算法 HONG等人ADDINNE.Ref.{9E2E5C2D-C739-474F-9438-D8F95ECF6214}[16]在网格划分优化的基础上使用了固定步长划分和扩展质心网格两个概念，确立了自适应网格划分优化的算法（本文称为G-DPC）。该算法能够较好地保留原算法的聚类精度，同时在大数据集上取得了较好的时空复杂度优化效果。 算法首先扫描整个数据空间，确定网格的步长step，计算公式如下：step= 其中，floor()表示向下取整函数，hi表示样本空间在i维数据上的最大值，l 在基于该步长对于数据空间作划分之后，数据点将会落入网格之中，之后的计算过程将会使用网格属性替代原数据属性。已知DPC算法中样本属性为局部密度和相对距离，则替换为网格后面临的问题为网格密度和质心的确定。 G-DPC算法认为网格之间存在相互影响，在计算网格质心和密度时应该同时考虑到相邻网格中的数据点，算法采用影响函数来描述数据点之间的影响，样本点xi和xEff 其中，distxi,xj为x 已知算法初始网格质心计算方式为：Cen 其中，num为网格空间内样本点的数量。 加入影响函数之后的扩展网格质心计算方式：Cen 其中，t表示初始质心半径为√22step的领域内样本点的数量，𝐸𝑗= 同时，网格密度计算方式为：ρ 至此，局部密度和质心的计算方法都已给出，以质心为坐标即可计算出网格间的相对距离，为了便于直观地理解算法的时空复杂度优化原理，图3-6展示了网格划分后样本与原数据样本的对比。从图可知，网格划分的非空网格（数量为m）相比于原样本数据集（数量为n），有m<< 通过用非空网格来替代原样本的方法，可以使数据集的样本数量大大减少，时空复杂度的计算方式仍然不变，但基数获得了减少，从而实现了算法耗时的降低。（a）原Iris数据集样本（b）G-DPC算法网格划分后样本图3-6G-DPC网格划分后的样本与原样本对比1.1.2算法的缺点分析 G-DPC相比于原算法对于参数的敏感度有所降低，但在某些数据集上的决策图相比于原算法要更难以选择，例子见图3-7。（a）d=2%时DPC决策图（b）G-DPC决策图图3-7G-DPC与DPC在Aggregation上的决策图比较 相比于G-DPC算法，DPC算法可以更好地观察到7个离群点，而G-DPC的决策图则显得区分度不足，有待改进。 同时G-DPC算法对于密度不均匀数据集会表现得更差，例子见图3-8。 G-DPC算法错误地将右上角地小簇和右下角合并到一起，经过分析，是因为G-DPC算法在做网格划分时步长会参考数据集的样本数n，见公式（3-4），Synthesis数据集