基于GAS计算模型的张量分解算法并行化研究与应用

发布时间：2020-08-04 07:41

【摘要】：张量(Tensor)是多维数据最自然的表现形式,是矩阵的多维延伸,张量数据广泛的出现在社交网络、推荐系统等多个领域。对张量数据的分析,一般是通过张量分解的方法,来挖掘原始数据中的隐含信息,通过张量分解可以进行主成分分析、数据压缩、缺失值补全等。目前的张量分解算法,一般是基于单机版MATLAB实现的,是典型的集中式处理方式,当处理大规模张量数据时,数据量的规模超出了单机的内存,使得传统的单机张量分解算法无法满足实际计算需求。分布式处理方法可以将海量数据分散到若干节点中参与运算,节省了计算时间同时也降低了运算成本。图(Graph)是一种基本的数据结构,能够表示实体之间的交互作用和复杂关系,在社会网络等很多领域常用图表示复杂的数据集。本文主要研究了张量数据的图结构表示,并基于GAS并行计算模型在图结构上实现张量分解算法的并行化。本文的创新点与主要工作如下:1)基于GAS计算模型的并行矩阵分解算法矩阵作为二阶张量,广泛的出现社会网络分析和推荐系统中,本文根据矩阵分解基本原理,设计了矩阵分解的图模型,在图结构上基于GAS并行计算模型,实现了并行矩阵分解SGD算法和ALS算法,并在PowerGraph平台上验证了算法的有效性和可扩展性。2)基于GAS计算模型的并行张量分解算法张量数据作为矩阵的高维延伸,存储着原始数据中更多的信息,本文将矩阵分解算法,向高维数据进行延伸,设计张量分解的图模型,基于GAS并行计算模型,实现了并行张量分解CP-ALS算法,并在PowerGraph平台上验证了算法的有效性和可扩展性。3)基于并行张量分解的缺失值补全算法在实际问题中获得的原始数据,并不总是非常完整的,经常存在缺失值,无法直接对原始数据进行分析,需要根据原始数据中的现有值将缺失信息进行补全。本文基于矩阵分解和张量分解算法,设计张量数据的缺失值补全算法,并在图结构上,基于GAS并行计算模型,实现了补全算法的并行化。通过推荐算法经典数据集MovieLens,验证了算法的有效性和可扩展性。
【学位授予单位】：河北师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O183.2
【图文】：

2 张量基本运算与并行计算模型简介2.1 张量的表示与基本运算张量（Tensor）是多维数组（Multidimensional, or N-way array）的表示方式，是和矩阵的推广。多维数组的维度称为张量的阶（Order）。零阶张量表示常数，一阶表示向量，二阶张量表示矩阵，三阶及以上张量称为高阶张量（Higher Order Tensor节主要对文中用到的符号和基本运算进行简要描述[42,43,44]。2.1.1 张量的表示本文中零阶张量用小写字母表示，即常数表示为 a；一阶张量用粗体的小写字母，即向量表示为 x；二阶张量用粗体大写字母表示，即矩阵表示为 X；高阶张量用欧拉字母表示，即1 2 NI I I ，N 为张量的阶（或模），表示多维数组的维度

张量,矩阵

1 2 2 k k的 Hadamard 乘积两个矩阵，I J ，他11 11 1 11 1J JI I IJ IJa b a ba b a b ，结果为一个I J的矩阵。本运算与张量的秩量 n 模矩阵化张量的矩阵化是指将张量中的元素按照一程。将 N 阶张量1 2 NI I I 按 n 模展开，记为 N 阶列为矩阵中的列，形成矩阵1 2 1 1( ( )n n n NI I I I I In 中的位置为( , )ni j ，且1, 1 ( 1) ,Nk k kk k n j i J J 开如图 2.2 所示。

张量,三阶

量如果 N 阶张量1 2 NI I I ，可以被表示为 N ( N)x，则称张量为秩 1 张量，张量( )NNix 。三阶张量的秩 1 分解如图 2.3 所示。

【相似文献】