【《密度峰值聚类算法在社区发现上的应用分析案例》2500字】_第1页
【《密度峰值聚类算法在社区发现上的应用分析案例》2500字】_第2页
【《密度峰值聚类算法在社区发现上的应用分析案例》2500字】_第3页
【《密度峰值聚类算法在社区发现上的应用分析案例》2500字】_第4页
【《密度峰值聚类算法在社区发现上的应用分析案例》2500字】_第5页
已阅读5页,还剩3页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

密度峰值聚类算法在社区发现上的应用分析案例目录TOC\o"1-3"\h\u16390密度峰值聚类算法在社区发现上的应用分析案例 1190791.1引言 1185391.2度量方式和局部密度的等效 1157981.2.1度量方式的等效 1315811.2.2度量方式的局限性 2272621.2.3局限的分析与验证 2252871.2.4改进方法 4120571.3实验与分析 51.1引言 密度峰值聚类算法已经证明在人工数据集、人脸识别、图像处理等有特定形状的数据集上具有良好的聚类效果和应用价值。在本章中将对算法在社区发现的应用方法和应用手段进行总结与研究,并同时对于密度的等效使用新的描述方法,也能够实现峰值聚类算法在社区发现上的应用。1.2度量方式和局部密度的等效 要将密度峰值聚类算法应用于社区发现,首先要面临的问题就是欧式距离的替换,社区发现中的数据集往往通过点与点的连接来表示,而不是样本点的坐标。从前面的章节可以知道密度峰值聚类算法依赖于样本的坐标以计算相对距离和局部密度,所以如何实现这两个重要参数的等效,是将其应用于社区发现时存在的主要问题。 本节将由4个部分构成,第一部分介绍度量方式的等效方法,第二部分阐述该方法存在的局限性,第三部分分析局限性存在的原因,第四部分提供一个改进方法。1.2.1度量方式的等效 本文实现一种基于信任度的度量方式,由JIN等ADDINNE.Ref.{24D23466-2A5D-4BAF-BE79-1C6335560B85}[15]提出以替代原算法的欧氏距离。 替换方法如下: D αβC 其中,Ni表示样本点i的邻居,Ci,j为样本点i和样本点j的公共邻居个数,ECi,j为公共邻居的连边数,βi,j1.2.2度量方式的局限性 原文中使用该度量在基于核密度估计的密度峰值聚类算法中获得了十分成功的社区划分,但是在将其运用了基于截断距离的密度峰值聚类算法时,却无法生成令人满意的决策图,如图4-1所示。(a)d=1%算法在dolphin上的决策图(b)d=1%算法在karate上的决策图 图5-1算法在各数据集上产生的决策图 观察算法在两个决策图上的表现,可以发现算法更倾向于认为整个样本数据集属于同一个社区结构,无法很好地完成社区结构的划分。1.2.3局限的分析与验证 密度峰值聚类算法的算法思想在于选择质心之后将剩余样本分配到最近的质心,以图5-2为例。图5-2为手工生成的具有简单社区结构的无向图,图中的两个社区结构分别以0和13为社区中心。图5-2手工构造的简单社区无向图 依据上述度量方法计算,节点0与13反而表现为低密度点。以0与3之间和1与3之间的度量计算为例。 通过上述公式易算得: C0,3=2,β0,3=1 C1,3=2,β1,3=1 可知作为中心点并且直接与节点3相连的节点0反而表现出与节点3更远的距离,导致在使用截断距离时,1相比于0更易获得3的信任,从而表现为更高的密度,使得其在决策图上更有优势。 会产生此现象的原因是在计算αi,j,度数高的点(图中0的度数为6,1的度数为3)分母更大,值更小,点关系表现得更为疏远。而在计算表示边关系的β图5-3算法于图5-2样本产生的决策图 可以观察到中心点0与13出现于决策图的左下角,而节点4和节点10表现更佳,由于样例简单的社区结构,算法仍然可以实现划分,但同样的问题会使得算法在karate数据集和dolphin数据集无法完成社区划分。1.2.4改进方法 对于以上问题,本文提出一种简易的改进方法,在进行度量替换时,为高度数点提供补偿,为低度数点施加惩罚,同时对于不直接相连的节点进行距离惩罚,公式如下:N D αβ 其中,degreei为节点i 公式(5-5)的修改原理:直接相连的两点相比于间接相连的两个节点应具有更短的信任度距离,对于原文中会出现的间接相连反而会得到更短的距离的情况,本文中对间接相连的点乘一个惩罚系数,使得直接相连的点拥有更近的信任度距离。 公式(5-6)的修改原理:修改前的度量方式可以很好地使高度数节点之间呈现较远的距离关系,低度数节点之间表现出较近的距离关系,但使得高度数点和低度数点表现出的距离关系较差,在计算距离时,引入两个节点的比值,可以在保持原方式的特点基础上,平衡度数差异较大节点之间的距离度量。 公式(5-7)的修改原理:Ci,j 公式(5-5)与(5-8)所设置的系数为反比关系,目的是使得最差情况下的直接相连节点间的信任度度量距离,仍然可以小于间接相连的最优节点。 使用新度量方式计算图5-2产生的决策图与划分结果如图5-4所示。(a)改进后算法的决策图(b)决策图的变换形式(c)划分结果图5-4改进之后的算法决策图与划分结果 可以得知,改进后的度量方式正确地选择了社区中心并完成了社区结构的划分。1.3实验与分析 为了验证修改后的度量方式的有效性,本文使用社区发现中常见的测试数据集对其进行测试,测试数据集的特征如表5-1所示。对于测试结果,社区发现之中,常用模块度QADDINNE.Ref.{97DFF5A8-E701-4943-B2E0-BAE735A42661}[17]和标准化互信息NMI[18]ADDINNE.Ref.{95532ABE-4E0D-4700-81F4-D7E15499C3D5}对结果做评价,Q用来反应社区结构的稳定性,NMI用来反应划分结果与实际社区结构的相似性,本文中Q和NMI均由python库community函数计算完成。表5-1常用社区划分数据集数据集节点数边数Karate3478Dolphin62158Polbooks105441Football115612(a)karate初始社区结构(b)dolphin初始社区结构(c)polbooks初始社区结构(d)football初始社区结构 图5-5数据集的初始社区结构(a)改进后算法在karate上的决策图(b)改进后算法在dolphin上的决策图(c)改进后算法在polbooks上的决策图(d)改进后算法在football上的决策图图5-6改进后算法在各数据集上的决策图(a)改进后算法对karate的划分结果(b)改进后算法对dolphin的划分结果(c)改进后算法对polbooks的划分结果(d)改进后算法对football的划分结果图5-7改进后算法在各数据集上的划分结果表5-2算法在各数据集上的评价指标数据集QNMIKarate0.3711.0Dolphin0.3790.881Polbooks0.4560.492Football

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论