基于全局信息的图结点特征向量学习算法

发布时间：2017-10-29 18:04

  本文关键词：基于全局信息的图结点特征向量学习算法

  更多相关文章： 图结点特征向量 全局结构信息 矩阵分解 特征 学习 降维算法

【摘要】：随着互联网+时代的到来,数据的产生日益增多,如何从海量的数据中获取有价值的信息,已成为数据挖掘的使命。在实际中,数据经常会以图结构来组织,图挖掘便成为重要的研究课题。在诸多算法思路中,近两年新提出的图结点特征向量生成算法实现了业界最优水平,受到了众多学者的关注。本文提出了GraRep,一种新的算法可以利用图的结构信息生成具有语义、拓扑特性的图结点特征向量表示。与其他已有工作不同,本文提出的算法充分利用了图上的互补的局部结构信息,并综合在一起构成全局结构信息。本文从数学上形式化的证明了该算法相较于一些文献已有算法的优势所在,包括Perozzi et al.提出的DeepWalk模型,以及Mikolov et al.提出的skip-gram模型。从真实的实验数据中,本文再次验证了GraRe p在实验结果上达到业界最优水平。为了充分体现该算法的性能,本文的实验数据分别来自新闻文本网络,社交网络和文献引用网络三种不同性质的数据,包括有有权图与无权图、稀疏图与稠密图,图的结点数目差异也很大。同时,在三种不同的任务中进行测试,分别是聚类任务、分类任务以及可视化任务。在所有实验中,本文提出的GraRep算法在准确度上相对于若干已有的业界最优算法有显著的提升。然而,本文仍然存在不足之处。由于矩阵乘法和奇异值分解的高时间复杂程度,导致算法在数据规模较大时耗时较高。未来的工作中,会继续探究矩阵乘方的近似算法,以及将算法改为在线算法,用更好的方法去替代奇异值分解做数据降维等。
【关键词】：图结点特征向量 全局结构信息 矩阵分解 特征 学习 降维算法
【学位授予单位】：西安电子科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP181
【目录】：

• 摘要5-6
• ABSTRACT6-9
• 符号对照表9-10
• 缩略语对照表10-13
• 第一章 绪论13-21
• 1.1 研究背景及意义13-14
• 1.2 研究现状14-17
• 1.2.1 中心性度量14-15
• 1.2.2 图结点特征向量15-17
• 1.3 本文工作概述及论文结构17-21
• 第二章 数学模型建立21-33
• 2.1 问题抽象及符号定义21-23
• 2.1.1 图的概念21-22
• 2.1.2 问题的定义22-23
• 2.2 相关算法分析23-27
• 2.2.1 线性结构特征向量生成算法23-26
• 2.2.2 图结构特征向量生成算法26-27
• 2.3 全局结构信息提取策略27-29
• 2.3.1 各阶局部信息提取27-28
• 2.3.2 各阶局部信息保留28-29
• 2.4 综合各阶结构信息29-33
• 2.4.1 衰退函数29-30
• 2.4.2 衰减随机冲浪模型30-33
• 第三章 算法设计33-45
• 3.1 优化目标函数建立33-35
• 3.1.1 局部优化目标函数33-34
• 3.1.2 数值优化算法34-35
• 3.2 解析求解方法35-37
• 3.2.1 解析解矩阵35-36
• 3.2.2 基于矩阵分解的优化方法36-37
• 3.3 深度神经网络与数据降维37-39
• 3.3.1 深度学习37-38
• 3.3.2 栈式降噪自动编码器38-39
• 3.4 算法流程39-40
• 3.5 GraRep数学本质40-45
• 3.5.1 SGNS算法与GraRep的联系40-42
• 3.5.2 采样方法与转移概率42-45
• 第四章 实验验证45-55
• 4.1 数据集45-46
• 4.2 基线算法46-47
• 4.3 参数设定47-48
• 4.4 实验结果分析48-51
• 4.4.1 20-Newsgroup网络48-49
• 4.4.2 Blogcatalog网络49-50
• 4.4.3 DBLP网络50-51
• 4.5 参数敏感性分析51-55
• 第五章 总结与展望55-57
• 参考文献57-61
• 致谢61-63
• 作者简介63-64

【相似文献】

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

1 许锡春,胡运发,施伯乐;特征向量的获取[J];计算机应用;2000年09期

2 葛新;赵海;张昕;李超;;基于多维特征向量的网络社团划分方法[J];东北大学学报(自然科学版);2008年07期

3 高灵霞;李国敏;孙凤兰;;方阵广义特征向量的一种相似迭代算法[J];计算机应用与软件;2014年02期

4 夏慧明;周永权;;求解矩阵特征值及特征向量的新方法[J];计算机工程;2008年11期

5 邓广宏;曹万华;夏奕;蔡斌;池志强;程雄;;基于特征向量的基本口型分类[J];计算机应用与软件;2010年10期

6 刘青光,邹理和;信号特征向量分解与到达波方向估计[J];电子学报;1993年01期

7 张霖;吴麒;;设计鲁棒控制器的主导特征向量配正方法[J];自动化学报;1991年01期

8 邓晓刚;田学民;;基于特征向量提取的核回归建模方法研究[J];控制工程;2010年04期

9 李博涛;王之琪;王秀彩;;分支界定法在特征向量提取中的应用[J];山西电子技术;2011年02期

10 刘俊;黄秀玲;张智光;;基于产品特征向量的产品配置研究[J];制造业自动化;2008年12期

中国重要会议论文全文数据库 前5条

1 陈力奋;宋汉文;王文亮;;确定退化模态可导特征向量转换矩阵的一种新方法[A];振动工程学报（工程应用专辑）[C];2001年

2 戴琨;汪小帆;;根据特征向量判据优化网络的同步能力[A];第四届全国网络科学学术论坛暨研究生暑期学校论文集[C];2008年

3 刘增武;蔡悦斌;;基于K-L变换的船舶噪声特征向量的降维处理[A];中国声学学会1999年青年学术会议[CYCA'99]论文集[C];1999年

4 张新培;曹策慧;;随机结构特征值和特征向量统计特性的研究[A];第五届全国结构工程学术会议论文集（第二卷）[C];1996年

5 曹玉娟;牛振东;彭学平;江鹏;;一个基于特征向量的近似网页去重算法[A];中国索引学会第三次全国会员代表大会暨学术论坛论文集[C];2008年

中国博士学位论文全文数据库 前2条

1 陈晓s，

本文编号：1114050