基于邻域信息的聚类和社区发现算法研究

发布时间：2017-12-10 21:15

  本文关键词：基于邻域信息的聚类和社区发现算法研究

  更多相关文章： 聚类 社区发现 邻域信息 模糊关系

【摘要】：随着数据挖掘技术在各行各业的广泛应用,人们对这一领域的相关技术越来越关注。数据聚类和社区发现是数据挖掘领域中十分重要的两个课题,它们之间也有一些共性。聚类是指将数据对象分为若干个簇,使得簇内的对象关系紧密,而簇之间的对象关系疏远。社区发现可以认为是聚类思想在网络数据中的延伸,它是指将网络中的节点指派给若干个社区,使得同一个社区内的节点联系紧密,而来自不同社区的节点间联系比较疏远。目前已有大量的关于聚类算法和社区发现算法的研究工作。本文针对已有的经典聚类算法FDP中存在的不足,探索了邻域信息在聚类中的作用,然后提出了一种新的聚类算法NIDD。接着,将NIDD的思想推广到社交网络中,在引入基于邻域信息的模糊中心度和模糊隶属度的基础上,提出了一个新的社区发现算法FCFM。最后,将聚类算法FDP的核心思想推广到社区发现中,研究了基于邻域信息的模糊关系及其作用,提出了基于模糊关系的社区发现算法CDFR。具体来说,本文工作主要包括以下3个方面。(1)提出了基于邻域交集和密度差异的聚类算法NIDD。在分析聚类算法FDP的过程中,发现它在某些数据集上的效果并不理想。针对FDP的一些不足,提出了聚类算法NIDD。该算法的思想是:第一,在簇的扩展过程中会选择一个内部点作为参考点,然后考察参考点邻域内的所有点;如果参考点和待扩展点的密度变化较小,那么它们属于同一个簇,并且该待扩展点还可以继续扩展;反之,如果参考点和待扩展点的密度变化相对较大,那么该待扩展点被归为当前簇,但是该数据点不可以继续扩展。第二,如果参考点和待扩展点之间的k最近邻交集率很小,说明它们之间的公共邻居占据的比例很小,此时不管它们密度是否相似,它们会被划分在不同的簇中。实验结果表明了 NIDD算法的有效性。(2)提出了基于模糊中心度和模糊隶属度的非重叠社区发现算法FCFM。FCFM是一种无参数的社区发现算法,其主要思想是:第一,基于邻域信息的模糊中心度来组织网络中节点的处理顺序;第二,在一个社区中拥有最大的模糊中心度的节点被认为是这个社区的中心,社区从这个节点开始向外扩展;第三,在社区扩展的过程中,模糊隶属度被用来决定是否继续扩展当前社区。对比了FCFM和经典的社区发现算法在真实的网络数据集上的实验结果,实验结果验证了 FCFM算法的有效性。(3)提出了基于模糊关系的社区发现算法CDFR。首先,提出NGC(Nearest Greater Centrality)节点的概念。然后,引入了基于邻域信息的模糊关系的概念,并且给出了计算每个节点到其NGC节点的模糊关系的方法。这种模糊关系可以看做是节点对其NGC节点的依赖程度。依赖程度越小说明该节点的自治性越大,换句话说,该节点成为社区中心节点的可能性越大。最后,每个节点属于哪个社区取决于其NGC节点以及它们之间的模糊关系。实验结果表明,CDFR算法对于非重叠社区检测是有效的。本文工作不仅在聚类方法研究方面具有参考价值,而且对于社交网络中的社区发现研究也具有参考价值。
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13

【参考文献】

中国期刊全文数据库 前2条

1 WANG Shuliang;WANG Dakui;LI Caoyuan;LI Yan;DING Gangyi;;Clustering by Fast Search and Find of Density Peaks with Data Field[J];Chinese Journal of Electronics;2016年03期

2 武志昊;林友芳;Steve Gregory;万怀宇School of Computer and Information Technology,Beijing Jiaotong University;田盛丰;;Balanced Multi-Label Propagation for Overlapping Community Detection in Social Networks[J];Journal of Computer Science & Technology;2012年03期

，

本文编号：1275911