基于t-SNE降维的密度峰值聚类算法.pdf

2023年4月Apr.,2023第39卷第2期Vo l.39,No.2滨州学院学报Jo u rn a l o f Bin zh o u Un iv ersit y【工程与技术研究】基于廿SNE降维的密度峰值聚类算法何婷霭，李秦(兰州交通大学数理学院，甘肃兰州730070)摘要：为了提高密度峰值聚类(DPC)算法处理复杂高维数据的能力，提出了一种基于 z-SNE降维的密度峰值聚类算法OSNE-DPC)。该算法用f-SNE算法对数据进行预处理，将高 维数据点间的关系用概率分布映射到低维空间中，通过最小化相对爛最大化保留数据餉本质特 征，使用密度峰值聚类算法进行聚类操作。仿真实验结果表明,f-SNE-DPC可以高效地对高维 数据进行聚类，在A MI指标上的聚类结果可达0.828。关键词:聚类分析；密度峰值聚类比SNE算法；有效性度量中图分类号:TP 181 文献标识码：A DOI：10.13486/j.c n k i.1673-2618.2023.02.014聚类分析是数据挖掘技术的基础与核心，它能够在无监督的条件下探索数据背后潜在的关系。依据 原理的不同，将现有的聚类分为5类划分聚类、层次聚类、网格聚类、基于密度的聚类和模型聚类，每 种聚类方法都有其独特的优势。密度峰值聚类(Den sit y Pea k s Cl u st erin g,DPC)算法是2014年由意大利学者Al ex Ro d rigu ez和 Al essa n d ro La io提出的，该算法不仅简单易懂、参数少，而且不需要迭代，能够对任意形状的数据集进行 高效聚类。正是基于这些优势-DPC算法被广泛应用于机器学习、模式识别和图像处理等多个领域。但 该算法也有不足之处:高维数据集聚类效果不佳;算法中的唯一参数一截断距离需人工选取，对聚类结 果影响较大;不适用于大规模数据的聚类分析。在对高维数据进行聚类研究时发现，进行降维操作可以减少数据冗余，提高聚类效率。主成分分析(Prin c ipa l Co mpo n en t An a l ysis,PCA)可以去除部分噪声并发现数据中的部分数据结构,但对于非线性 数据，并不能很好地发现数据的隐含信息；线性判别分析(Lin ea r Disc rimin a n t An a l ysis,LDA)是一种 基于监督学习的数据降维方法，但可能过度拟合数据;等度量映射(Iso met ric Ma ppin g,Iso ma p)使用测 地线距离计算数据点间的距离，但对噪声敏感且它的拓扑结构不稳定。基于上述表述，将分布随机近 邻嵌入(/-d ist ribu t ed St o c h a st ic Neigh bo r Embed d in g,t-SNE)这一降维方法引入 DPC 算法中，提出了一-种基于f-SNE降维的密度峰值聚类算法(z-SNE-DPC).J-SNE-DPC将高维数据点通过概率分布映射到 低维空间中，随后用传统的DPC算法将其进行聚类，通过实验验证,t-SNE-DPC对高维数据有很强的实 用性。1 DPC算法密度峰值聚类算法是基于密度的聚类算法，它的核心在于对聚类中心的刻画。该算法适用于聚类中收稿日期：2022-04-12基金项目：国家自然科学基金地区科学基金项目(11262009)第一作者简介：何婷霭(1997),女，甘肃白银人，硕士研究生，主要从事机器学习研究。E-ma ih h 2398385335163.c o m 83 滨州学院学报第39卷1口0,(1)0,z$0。心点的局部密度较高，且比其密度高的点之间的距离相对较远的情况。假设有数据集合S=d,工2，北”=1,2,”是其指标集，右=d is t(m,巧)是数据点竝与之间的欧氏距离期。定义局部密度 Pi为Pi=%(场一力),尤(工)=其中，么是截断距离,需要人为指定，一般选取整个数据集的1%2%作为截断阈值。x(z)是指示函数。定义相对距离&为Si=min dij),(2)当数据点8的局部密度达到最大时,相对距离变为ft=ma x W,)o局部密度和相对距离确定完成后，通过绘制决策图选k聚类中心，一般选择决策图右上方的点，这些 点既有较高的局部密度，也有较大的相对距离。最后采用一步分配策略进行非聚类中心点的分配:若数据 点巧不是中心点，则将其归入密度比列大且距离最近的数据点九所在的类，该过程只执行一次，不用 进行迭代更新匸讪。DPC算法的具体步骤如下:(I)确定截断参数dc,根据公式(1)计算每个数据点的局 部密度p;(U)根据公式(2)计算每个数据点的相对距离&;(皿)以p为横坐标,d为纵坐标绘制决策图;(IV)根据决策图选取聚类中心，分配非聚类中心数据点，完成聚类。2 z-SNE算法J-SNE算法是基于流形学习的非线性降维方法。文献口提出了随机近邻嵌入(St o c h a st ic Neigh bo r Embed d in g,SNE)算法,文献口2在SNE算法的基础上进行了优化改进，提出了 t-SNE算法山。f-SNE 算法在低维空间中用分布代替原来的高斯分布表示两点间的相似度，独有的长尾特征有效地解决了 SNE算法存在的拥挤问题。假设:高维数据点集合为X=Xl,x2，工”,映射到低维空间后的数据点集合为Y=yi,y2，-,%；P与Q均为”X矩阵，分别表示高维空间和低维空间中的概率分布，为与g”是其各自的矩阵元 素.在Z-SNE方法中，联合概率分布为是对称条件概率Pa=2n(3)勿I；是点i相对于点j的概率分布PiM=ex p(-11-II2)ex p(匕尹?(4)其中,6是以为中心的高斯分布的方差，它反映了中心竝周围的样本分布密度，此参数的值由复杂度因 子通过执行二元搜索来确定，复杂度因子定义为perp(勿)=2皿竝，H(A)是分布Pi的爛=工的 Jo g?角“定义低维空间中y与兀之间的联合概率分布为=(1+H M 1 艺(1+N%M II 2)-1kl设两个分布间的相对爛为代价函数C,采用梯度下降法来最小化C,其计算过程为(5)(6)(7)84 第2期何婷霭，李 秦 基于f-SNE降维的密度峰值聚类算法C=KL(P|Q)=-(8)i 详 iM=4(為qv)Cyt 力)(1+|yi|2)-1。(9)o yi j为了避免优化过程陷入局部最优，在进行梯度计算时加入一个相对较大的动量项a(Z),则此时梯度更新为 Y=(1-1+备+&)(y-D-Y-),(10)其中表示第t次的迭代解,7)表示学习率。综上所述,t-SNE算法的主要步骤如下：(1)根据式(5)和式(6)计算复杂度因子perp(A)；(n)设置 参数迭代次数丁，学习率动量项();(ID)根据式(3)和式(4)计算并得到初始化结果Y(W=处，处，;(IV)从1=1到丁进行迭代更新,根据式(7)计算的，根据式(8)和式(9)计算梯度，根据式(10)进行梯度更新。3 Z-SNE-DPC如前所述,密度峰值聚类算法在聚类高维数据集时效果不佳，基于此将i-SNE算法引入DPC算法中，需要注意的是，在进行绘制决策图选取聚类中心时，横坐标采用公式 ft进行计算更新。故基于 z-SNE的Z-SNE-DPC设计思想如下:把待聚类的高维数据用Z-SNE算法进行降维处理;将降维后的数据 使用密度峰值聚类算法进行聚类。f-SNE-DPC算法具体步骤如下：(I)利用4-SNE算法进行高维数据预 处理；(口)确定截断距离根据降维后得到的数据利用式(1)和式(2)计算局部密度p；和相对距离8.;(JU)根据&绘制决策图，选取聚类中心；(IV)分配其他数据点，得到聚类结果。4实验验证及结果分析4.1实验验证为验证提出的聚类算法i-SNE-DPC,采用结构化数据的经典数据集一手写数字数据集MNIST来 进行仿真实验。此次实验使用MNIST手写数字数据集的t ra in训练集，选取手写数字06，共计1264个 数据样本，且每个样本都具有64个特征。图1为MNIST数据集在Iso ma p,f-SNE和f-SNE-DPC下的聚 类可视化结果。(a)Iso ma p(b)j-SNE(c)z-SNE-DPC图1 MNIST数据集在三种降维算法下的聚类可视化结果从图1(a)(b)可以看出,Iso ma p对高维数据不能进行很好的聚类,应属于不同类簇的点错误地归类到 T同一类簇洽SNE方法相对来说效果好了很多，类簇与类簇间的分离效果可以明显肉眼识别，但仍然出 现了同一类簇中混杂着其他数据点的情况。图1(c)是使用新算法f-SNE-DPC进行的聚类效果图，为了能 够更直观地看出其效果，采用不同的记号来刻画每一个类簇。从图中可以很明显看出-SNE-DPC可以 准确确定聚类个数且聚类效果很好。85 滨州学院学报第39卷4.2算法性能评估为验证算法的有效性，采用三种外部评价指标:准确率、调整互信息匸和调整兰德指数来进行算法 性能评估。记数据集X=皿，口”的真实类标记为U“,U2,U”，实验得到的类标记为VX,V2,，V”。定义1(准确率ACC)正确聚类的数据样本个数M占数据样本总数N的比率ACC=NJN。定义2(调整互信息AMI)皿 设函数FQi,竝)为ma x函数，则有AMI=MZ(U,V)EMZ(U,V)/ma x H(U),H(V)EM“U,V),其中,MI(U,V)是互信息,E是期望,H(U)与H(V)是爛。定义3(调整兰德指数ARI 设a为同属于U与V的数据对个数;&为在U中属在同类，在V中 属不同类的数据对个数;c为在U中属不同类，在V中属同类的数据对个数;d为在U与V中都属不同类 的数据对个数，则有ARI=2(a dZc)/(a+Z)(Z+c Z)+(a+c)(c+d)。表1是DPC算法.PCA-DPC算法诙以及本文所提出的J-SNE-DPC算法分别在三个聚类指标下 对MNIST数据集进行的性能对比结果。从表中数据可以看出,z-SNE-DPC的聚类效果远高于其他算法，在三个聚类指标上均有很大的提升，尤其在A MI指标上逼近于1,聚类性能很好。表1三种聚类算法在三个聚类指标上的计算结果算法ACCAMIARIDPC0.3550.2730.163PCA-DPC0.2490.1510.039i-SNE-DPC0.7440.8280.7155结语针对密度峰值聚类算法对高维数据聚类效果不理想这一问题，提出了一种基于z-SNE降维的密度峰 值聚类算法f-SNE-DPC,此算法把数据间的度量方式改用概率分布来表示，通过最小化相对爛将高维空 间的数据映射到低维空间,再而进行聚类操作。最后将算法应用到MNIST数据集上进行实验，并对算法 进行了有效性度量,实验结果表明新算法可以对高维复杂数据进行高效聚类，且在AMI指标上结果逼近 于1,证实了新算法的有效性与可用性。参考文献：口 HAN J,PEI J,TONG H.Da t a min in g:c o n c ept s a n d t ec h n iq u esEM,Sa n Fra n c isc o:Mo rga n Ka u fma n n Pu bl ish ers In c,2022.2 XU R,WUNSCH D.Su rv ey o f c l u st erin g a l go rit h msEJ,IEEE Tra n sa c t io n s o n n eu ra l n et w o rk s,2005,16(3):645-67&3 段明秀.层次聚类算法的研究及应用D.长沙：中南大学,2009.4 XU D,TIAN Y.A c o mpreh en siv e su rv ey o f c l u st erin g a l go rit h ms.An n a l s o f d a t a sc ien c e,2015,2(2)：165-193.5 张敏，于剑.基于划分的模糊聚类算法J.软件学报，2004,15(6):858-86&6 RODRIGUEZ A,LAIO A.Cl u st erin g by fa