基于PowerGraph的并行Tucker分解及应用

论文摘要

张量分解是一种经典而基础的数据分析方法,被应用于各个热门的研究领域,业界积累了丰富的研究理论和经验。随着信息时代的不断发展,由于数据规模的急剧增加,传统的单机环境下的张量分解算法已经无法适应大数据时代的要求。因此,对张量分解的并行化研究有其非常重要的现实意义。张量分解的两种主要的分解方式是CP分解和Tucker分解,两者应用都很广泛,各有侧重,并且CP分解从某种角度可以视为Tucker分解的一种特殊形式。针对Tucker分解算法的并行化研究很多,但各有优势,不一而足。目前,许多现实的数据集表现出网状式图结构特征,业内对于图结构数据的研究愈演愈烈。由于图结构数据和张量数据可以相互转换,两者之间存在密切的联系,所以许多研究人员考虑将张量和张量分解引入到图结构数据的研究领域中,旨在挖掘图结构数据的潜在知识。通过分析多种并行计算框架,本文采用并行图处理框架PowerGraph作为实验的物理环境,同时基于PowerGraph框架对Tucker分解及其应用做了些许尝试,主要工作分为以下几个部分:1.设计并实现了截断SVD(TRSVD)的并行算法。矩阵的奇异值分解(SVD)在机器学习、数据挖掘等领域有着很重要的研究价值和实际意义,并且经常作为交替最小二乘法(ALS)的更新方法。而TRSVD是SVD的一种改进策略。本文通过分析TRSVD的基本原理,采用行向量的拆分方式将TRSVD算法的核心步骤进行拆分,并设计与之相适应的图数据结构,从而在PowerGraph框架上实现TRSVD算法的并行化。经实验结果验证,并行后的TRSVD算法可以处理更大规模的矩阵,且计算时间较小。同时将其应用到后续的Tucker分解算法的并行化中,提高了整体算法的计算效率。2.设计并实现了Tucker分解的并行算法。通过仔细分析Tucker分解算法的基本原理以及算法的可行性,采用TRSVD的并行算法的拆分方式,重新设计了与之相适应的图数据结构,在PowerGraph框架上实现Tucker分解算法的并行化,并从不同角度对该算法进行了多次的对比实验和分析。经实验结果验证,并行后的Tucker分解算法可以处理更大规模的张量,且计算效率较高。3.设计并实现了基于Tucker分解的两个应用算法。第一,引用RESCAL分解模型和隐因子矩阵等概念,并将Tucker分解并行算法应用到多关系网络数据,在PowerGraph框架上实现了多关系网络的社团发现算法;第二,将彩色图片表示成张量形式,并将Tucker分解并行算法应用到彩色图片数据,在PowerGraph框架上实现了彩色图片的数据压缩算法。通过上述两个应用实验验证了Tucker分解并行算法的正确性和实际意义。

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 研究背景及意义
•   1.2 国内外研究现状
•     1.2.1 Tucker分解的研究现状
•     1.2.2 并行图处理框架研究现状
•   1.3 论文主要工作与创新点
•   1.4 论文组织结构
• 2 预备知识
•   2.1 PowerGraph框架的搭建
•     2.1.1 PowerGraph框架简介
•     2.1.2 环境搭建
•   2.2 数据集的预处理
•   2.3 小结
• 3 TRSVD的并行化
•   3.1 SVD与TRSVD
•   3.2 SVD的计算方法
•   3.3 TRSVD的并行化
•     3.3.1 TRSVD的并行可行性分析
•     3.3.2 TRSVD的并行化实现
•   3.4 实验
•   3.5 小结
• 4 Tucker分解并行化
•   4.1 Tucker分解的基础知识
•     4.1.1 相关符号
•     4.1.2 相关定义
•   4.2 Tucker分解的基本原理
• Tucker分解的基本原理'>    4.2.1 ALS_Tucker分解的基本原理
•     4.2.2 分析HOOI算法的并行可行性
•   4.3 Tucker分解的并行化
•     4.3.1 数据结构的分析与设计
•     4.3.2 并行HOOI算法的时间复杂度
•   4.4 实验
•     4.4.1 评价指标
•     4.4.2 实验结果和分析
•   4.5 小结
• 5 Tucker分解的应用实例
•   5.1 基于Tucker分解的多关系网络社团发现
•     5.1.1 多关系网络
•     5.1.2 RESCAL分解模型和隐因子矩阵
•     5.1.3 社团发现算法
•     5.1.4 评价指标和实验
•   5.2 基于Tucker分解的数据压缩
•   5.3 小结
• 6 总结与展望
• 参考文献
• 致谢

文章来源

类型: 硕士论文

作者: 刘佳

导师: 郭瑞强

关键词: 分解,并行化,多关系网络,数据压缩

来源: 河北师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 河北师范大学

分类号: O183.2

总页数: 67

文件大小: 2644K

下载量: 51