基于t-SNE降维的密度峰值聚类算法.pdf
《基于t-SNE降维的密度峰值聚类算法.pdf》由会员分享,可在线阅读,更多相关《基于t-SNE降维的密度峰值聚类算法.pdf(5页珍藏版)》请在咨信网上搜索。
1、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
2、-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
3、 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)可以去除部分噪声并发现数据中的部分数据结构,但对
4、于非线性 数据,并不能很好地发现数据的隐含信息;线性判别分析(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-
5、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。心点的局部密度较高,且比其密度高的点
6、之间的距离相对较远的情况。假设有数据集合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聚类中心,一般选择决策图右上方的点,这些 点既有较高的局部密度,也有较大的相对距离。最后采用一步分配策略进行非聚类中心点的分配:若数据 点巧不是中心点,则
7、将其归入密度比列大且距离最近的数据点九所在的类,该过程只执行一次,不用 进行迭代更新匸讪。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-S
8、NE 算法在低维空间中用分布代替原来的高斯分布表示两点间的相似度,独有的长尾特征有效地解决了 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是以为中心的高斯分布的方差,它反映了中心竝周围的样本分布密度,此参数的值由复杂度因 子通过执行二元搜索来确定,复杂度因子定义为per
9、p(勿)=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)表示学习
10、率。综上所述,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
11、-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个特征。
12、图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-D
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 SNE 密度 峰值 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。