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

摘要

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

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章绪论

1.1 研究背景及意义

1.2 研究现状

1.3 本文工作概述及论文结构

第二章数学模型建立

2.1 问题抽象及符号定义

2.2 相关算法分析

2 .3 全局结构信息提取策略

2 .4 综合各阶结构信息

第三章算法设计

3 .1 优化目标函数建立

3 .2 解析求解方法

3 .3 深度祌经网络与数据降维

3 .4 算法流程

3.5 GraRep数学本质

第四章实验验证

4 .1 数据集

4 .2 基线算法

4 .3 参数设定

4 .4 实验结果分析

4 .5 参数敏感性分析

第五章总结与展望

参考文献

致谢

作者简介