基于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 st sea rc h a n d fin d o f d en sit y pea k sQj,Sc ien c e,2014,344(6191):1492-1496.86 第2期何婷霭，李 秦 基于f-SNE降维的密度峰值聚类算法7 WOLD S,ESBENSEN K,GELADI P.Prin c ipa l c o mpo n en t a n a l ysisJ.Ch emo met ric s a n d in t el l igen t l a bo ra t o ry syst ems,1987,2(1)：37-52.8 BALAKRISHNAMA S,GANAPATHIRAJU A.Lin ea r d isc rimin a n t a n a l ysis:a brief t u t o ria l QJ In st it u t e fo r sign a l a n d in fo rma t io n pro c essin g,199818：1-8.9 TENENBAUM J B,SILVA V,LANGFORD J C.A gl o ba l geo met ric fra mew o rk fo r n o n l in ea r d imen sio n a l it y red u c t io n J.Sc ien c e,2000,290(5500)：2319-2323.10 陈俊芬，张明，赵佳成复杂高维数据的密度峰值快速搜索聚类算法Jl计算机科学,2020,47(3)：79-86.11 HINTON G E,ROWEIS S St o c h a st ic n eigh bo r embed d in g J.Ad v a n c es in n eu ra l in fo rma t io n pro c essin g syst ems,2002(15)：857-864.口 2 VAN DER MAATEN L,HINTON G.Visu a l izin g d a t a u sin g z-SNEEJl Jo u rn a l o f ma c h in e l ea rnin g resea rc h,2008,9(11)：2579-2605.13 徐秀芳，徐森，花小朋，等.一种基于廿分布随机近邻嵌入的文本聚类方法J.南京大学学报(自然 科学版),2019,55(2)-264-271.口4 AMELIO A,PIZZUTI C.Co rrec t io n fo r c l o sen ess:a d ju st in g n o rma l ized mu t u a l in fo rma t io n mea su re fo r c l u st erin g c o mpa riso n EJ.Co mpu t a t io n a l in t el l igen c e,2017,33(3)：579-601.15 STEINLEY D.Pro pert ies o f t h e Hu bert-Ara bl e a d ju st ed ra n d in d ex J.Psyc h o l o gic a l met h o d s,2004,9(3):386-396.16 杜明晶.密度峰值聚类算法研究DI徐州：中国矿业大学，201&Density Peak Clustering Algorithm Based on 卜SNE Dimensionality ReductionHE Tin g-a i,LI Qin(Sch o o l o f Mat h emat ics and Ph ysics 9Lanzh o u Jiao t o ng Universit y Lanzh o u 730070,Ch ina)Abstract:In o rd er t o impro v e t h e a bil it y o f Den sit y Pea k Cl u st erin g(DPC)a l go rit h m t o d ea l w it h c o mpl ex h igh-d imen sio n a l d a t a,a d en sit y pea k c l u st erin g a l go rit h m is pro po sed ba sed o n i-SNE d imensio n a l it y red u c t io n(t-SNE-DPC).Th e a l go rit h m u ses t h e z-SNE a l go rit h m t o pre-pro c ess t h e d a t ama ps t h e rel a t io n sh ip bet w een h igh-d imen sio n a l d a t a po in t s t o t h e l o w-d imen sio n a l spa c e w it h pro ba bil it y d ist ribu t io n,ma x imizes t h e ret en t io n o f t h e essen t ia l c h a ra c t erist ic s o f t h e d a t a by min imizin g t h e rel a t iv e en t ro py,a n d fin a l l y u ses t h e d en sit y pea k c l u st erin g.Th e a l go rit h m perfo rms c l u st erin g o pera t io n s.Th e simu l a t io n resu l t s sh o w t h a t Z-SNE-DPC c a n effic ien t l y c l u st er h igh-d imen sio n a l d a t a,a n d t h e c l u st erin g resu l t s o f t-SNE-DPC o n t h e AMI in d ex c a n be a s h igh a s 0.82&Keywords：c l u st er a n a l ysis；d en sit y pea k c l u st erin g；Z-SNE a l go rit h m；effec t iv en ess mea su remen t(责任编辑：贾晶晶)87