多属性无向加权图上的聚类方法研究

论文摘要

随着社会信息化的推进和通讯技术以及网络技术的飞速发展,信息的流量越来越庞大,存储的数据量正在以指数速度迅速增长,图是一种广泛使用的数据结构,它能很好地表示数据对象之间的结构关系。在现实世界中,诸多系统以网络图的结构形式存在,如因特网、万维网、人际关系网、科学家协作网和电话网等等。同时用于描述真实世界网络结构的图的规模也具有较大的增长趋势。目前面对浩渺无际的数据,人们迫切需要从数据汪洋中去粗存精、去伪存真,通过技术手段分析得到有用的结果。图聚类是一个非常有趣和具有挑战性的研究课题,近年来已经引起众多研究者的广泛关注,并应用到多个领域。图聚类的目的是按照各种不同的标准把大型图的节点拆分成不同的簇,使得同一簇内的节点连接紧密,不同簇之间节点的连接稀疏。许多现有的图聚类方法主要关注图的拓扑结构,使得每个簇达到一个有凝聚力的内部结构。但是在实际应用中由于图结构数据集的异质性,图本身存在着诸多的潜在信息,如图节点的属性信息和节点间的权重信息等等。随着图结构数据集的日趋庞大和复杂,仅仅分析图的拓扑结构信息很难得到理想的聚类结果。为此本文在综合考虑图的拓扑结构、节点属性以及节点间权重的基础上提出了两种新的图聚类方法来解决上述问题。1.多属性网络图结构化凝聚层次聚类方法图聚类的目的是按照各种不同的标准把大型图的节点拆分成不同的簇。该方法综合考虑图的拓扑结构和节点属性信息,利用节点的属性信息辅以图的拓扑结构产生新的簇,避免了传统图聚类方法的单一性。该方法首先通过在原图上添加多个属性节点的方法来增强同属性节点间的紧密度,同时可以让非连通图变为连通图;再根据节点的直接邻居关系计算边的结构化相似度,为了提高新添加的属性节点的贡献,本文计算属性节点转移概率矩阵,由此得到相邻节点间的相似度值。该方法只访问图节点和边各一次、简单、高效。2.基于最大最小距离度量的加权网络图结构化聚类方法该方法统一考虑图的拓扑结构和节点间的权重,使具有较大权重边连接的两点不被分开、同时使聚类结果的拓扑结构划分明显,即从图的拓扑结构上讲同一簇内的节点连接密集,不同簇间的节点连接稀疏,避免了传统方法的单一性。为此我们提出基于最大最小距离度量的加权网络图结构化聚类方法,归一化处理每一条边上的权重,按照图的拓扑结构计算具有直接边相连的节点的结构化相似度,综合考虑图的拓扑结构和权重各自的贡献,以最小关联度原则选取新的聚类中心,再以最大关联度原则进行模式归类。

论文目录

• 中文摘要
• Abstract
• 第1章 绪论
• 1.1 聚类分析
• 1.1.1 聚类分析概述
• 1.1.2 聚类分析技术
• 1.2 图聚类分析
• 1.2.1 图聚类分析概述
• 1.2.2 图聚类研究现状
• 1.2.3 图聚类分析面临的问题和挑战
• 1.3 本文工作的目的及研究内容
• 1.4 本文组织结构
• 第2章 图聚类方法综述
• 2.1 图的基本概念和术语
• 2.2 基于优化的图聚类方法
• 2.2.1 基于局部搜索的图聚类方法
• 2.2.2 谱聚类方法
• 2.3 基于启发式的图聚类方法
• 2.4 其它图聚类方法
• 2.5 本章小结
• 第3章 多属性网络图结构化凝聚层次聚类方法
• 3.1 相关工作介绍
• 3.2 节点邻居关系定义
• 3.3 多属性图节点相似度测量
• 3.4 算法描述
• 3.5 实验分析
• 3.6 本章小结
• 第4章 基于最大最小距离度量的加权图聚类方法
• 4.1 相关工作介绍
• 4.2 权值与节点相似度的统一测量方法
• 4.2.1 加权无向图
• 4.2.2 权重归一化处理
• 4.2.3 节点相似度定义
• 4.2.4 节点关联度定义
• 4.3 多属性加权图上聚类算法描述
• 4.4 算法例证
• 4.5 实验分析
• 4.6 算法分析
• 4.7 本章小结
• 第5章 结论
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文