1 绪论
1.1 研究背景及意义
张量[1]这一概念最早用于数学（如“张量场”）和物理学（如“应力张量”）等领域，而引入到计算机科学领域中，含义有所变化，即一个 N 阶张量就是 N 个向量空间张量积的一个元素，其中每个向量空间都有自己的坐标系。简言之，一个张量就是一个多维数组。一阶张量就是一维数组（或者向量），二阶张量就是二维数组（或者矩阵），三阶以及三阶以上的张量则统称为高阶张量[1]（如图 1.1所示）。对张量这种高维度的数据分析来说，张量分解[1]是一个非常有力的数学工具。它通过把原始的张量分解成几个小的张量相乘的形式，可以挖掘出数据的潜在信息，从而帮助人们更深层次的理解原始张量数据。张量分解起源于 1927年 Hitchcock，最早应用于统计心理学和化学计量学，之后又被引入到许多热门研究领域中，例如信号处理[2-4]，计算机视觉[5-7]，数值分析[8,9]，数据挖掘[10-14]，网络图分析[15-19]，神经科学[20,21]等等。在这些应用领域中，张量分解主要目的是发现数据之间的潜在关系，同时，通过其低秩逼近的结构来预测缺失值。张量分解有两种经典的分解方式：CP 分解（CANDECOMP/PARAFAC）[22]和 Tucker 分解[23]，如图 1.2 所示。CP 分解的公式是由有限个秩一张量的和来表示原始张量，Tucker 分解的公式是由一个较小的核心张量沿每一个模乘上相应的因子矩阵来表示原始张量。两种方式都有着很广泛的应用，前者更侧重于理解语义的潜在知识[24,25]，后者更侧重于数据压缩和降维[26-31]，识别因素之间的关系[32-34]和预测缺失值[35-37]。如果 Tucker 分解中的核心张量是超对角的，那么 Tucker 分解就退化成了 CP 分解，因此，CP 分解也可以视为 Tucker 分解的一种特殊形式[38]。张量分解算法也对应有 CP 分解算法和 Tucker 分解算法两种，但是张量分解算法的计算过程需要大量的迭代（无论是 CP 分解还是 Tucker 分解），本身的计算效率不高。随着数据量的急剧增加，传统的单机环境下的张量分解算法无法适应大数据时代的需求，因此，对张量分解并行化的研究有着非常重要的现实意义。
...........................
1.2 国内外研究现状
1.2.1 Tucker 分解的研究现状
传统的张量分解的研究和实现都是基于 Matlab 或相似环境的 toolboxes（如文献[39-43]），但是由于在计算过程中要将数据全部调入内存参与计算，所以难以适应大规模张量数据。在 2012 年，U Kang[44]等人对张量 CP 分解算法的并行化进行了深入研究，实现了首个较为成熟的并行 CP 分解计算框架 GigaTensor。在 2015 年，U Kang[45]的团队又基于 Tucker 分解的研究设计并实现了并行 Tucker分解计算框架 Ha Ten2。这两个框架都是基于 MapReduce，但是在张量分解过程中，需要进行大量的迭代更新, MapReduce 框架的优势在于处理无依赖关系的计算，在迭代过程中会引起大量的系统 I/O 操作，使得算法的运行效率并不高。鉴于 MapReduce 框架本身的局限性，使得张量分解的并行化并不理想[35]。为了避免在计算过程中由于反复迭代引起大量的系统I/O操作而导致算法的运行效率不高的问题，新的研究思路（如文献[46-51]）采用了基于分布式共享内存的处理环境，提高了张量分解的计算效率，从而缓解了处理海量张量数据的困境。但就共享内存处理环境而言，需要处理的数据量越大，所面临的计算成本也随之增大。考虑到成本问题，一些研究（如文献[26,52-54]）又将目光转移到了分布式内存处理环境，值得注意的一点是，这些工作都是开始于 CP 分解的并行化实现。显然，较于 CP 分解而言，Tucker 分解的计算更为复杂，较难实现。就目前为止，并没有非常高效的并行化的 Tucker 分解算法出现。HaTen2[45]虽然是并行化实现了 Tucker 分解，但是受限于 MapReduce 框架，计算效率不高。Li[55]等人基于共享内存并行化实现了张量与矩阵的链乘运算，但并没有完全实现 Tucker 分解算法的并行化。Austin[26]等人提出了一种基于分布式内存的 HOOI 算法，实现了 Tucker 分解的并行化，但主要针对的是稠密张量数据。Oguz Kaya[52,56,57]等人对并行张量分解算法进行了系统研究，基于维度树（Dimension tree）在超图（Hypergraph）模型上实现了 CP 分解和 Tucker 分解,并且主要针对的是稀疏张量数据。近年来，对图结构数据的研究愈演愈热。很多研究者（如文献[15-19]）将张量和张量分解引入到图结构数据的领域，使用张量来表示更为复杂的图结构数据，试图挖掘图结构数据之间的潜在信息。而文献[35]以张量元素在各个维度上的索引为结点，张量元素值为边，构造了张量分解算法的图模型，打开了基于并行图处理框架研究张量分解并行化的新思路。
............................
2 预备知识
2.1 PowerGraph 框架的搭建
2.1.1 PowerGraph 框架简介
PowerGraph 框架是由 Joseph E. Gonzalez[60]等人于2012年首次提出的针对自然图的并行图处理框架，在计算性能上同比其他分布式图计算框架有一定的优势。其主要特点是采用 GAS 计算模式和切点法的图划分方法。
（1）GAS 计算模式
GAS 计算模式是指将结点程序划分成 Gather（收集），Apply（应用）和 Scatter（分发）三个步骤。具体而言，Gather 阶段，收集结点的邻居结点的数据和邻边的数据，并根据用户提供的 sum 函数处理这些数据；Apply 阶段，用 Gather 阶段得到的结果更新结点的数据；Scatter 阶段，将 Apply 阶段结点更新后的数据更新邻边上的数据。在 Gather?Apply 的阶段，使用“同步”的概念，只有当参与Gather 阶段的所有结点都完成各自的 sum 操作时，才能进入到下一步的 Apply阶段；而在 Apply?Scatter 的阶段，由于结点之间不涉及读写冲突，可以采用“异步”的概念，任意一个结点执行完自身的 Apply 更新操作，即可进入下一步的Scatter 阶段，并不需要考虑其他结点的执行状态。
对比而言，Pregel 的每一个“superstep”都需要“同步”机制来维护数据一致，而 GraphLab 则必须采用加锁机制才能实现“异步”概念，GAS 这种设计模式既符合并行图处理框架的并行约束，同时综合了 Pregel 的“同步”概念和 GraphLab 的“异步”概念，体现了“折中取优”的思想。
（2）切点法图划分方法
切点法的图划分方法原理跟切边法是类似的。究其本质而言，图结构的数据本身就包括结点和边两个组成部分，在面临将整张图划分到各个计算节点的任务时，显而易见的两种划分策略：切边法就是将图的所有结点均分，切点法则是将图的所有边均分。当图的结点度数分布不均衡时，切边法会造成大量的存储空间的浪费和通信开销，而切点法刚好可以避免这一缺陷，保证负载均衡。由于目前大部分的图计算任务都是基于自然图，而自然图的特点之一便是“结点度数分布严重不均”，这也是导致后续并行图处理研究更倾向于切点法的直接原因。
..........................
由于 PowerGraph 框架在加载图数据时需要重写加载函数 load，因此在实现具体某一算法时，需要根据具体情况设计合适的数据加载格式。目前，大部分的公开数据集的格式并不满足需求，所以根据本文的具体实验要求，对本文实验所有用到的数据集都进行了格式和部分内容的预处理工作。
本文的实验主要分布在第 3 章、第 4 章和第 5 章三个部分，由于第 3 章中需要的实验数据是随机生成的，因此无需预处理，此处不再介绍。
第 4 章中的实验数据集主要采用的是 Netflix(Nasdaq NFLX)公司于 2006 年10 月公开发布的数据集 Netflix[62]。该公司成立于 1997 年，是一家提供在线影片租赁的网站。Netflix 数据集包含了随机抽取的 480K 个用户对 18K 部影片的超过100M 个评分数据，同时给出了相对应的评分时间。其中，评分范围为 1-5 分，评分时间从 1998 年 10 月到 2005 年 12 月，共约 2K 个时间数据。因此构成480K×18K×2K 的三阶张量数据，可以用于数据挖掘、机器学习等相关领域的学习和研究。
............................
3 TRSVD 的并行化 .................................... 18 3.1 SVD 与 TRSVD ........................................ 18
3.2 SVD 的计算方法 .................................... 20
3.3 TRSVD 的并行化 ................................. 23
4 Tucker 分解并行化................................... 28
4.1 Tucker 分解的基础知识 ....................... 28
4.1.1 相关符号 ......................................... 28
4.1.2 相关定义 .................................. 28
5 Tucker 分解的应用实例 .................................. 44
5.1 基于 Tucker 分解的多关系网络社团发现......................... 44
5.1.1 多关系网络 ................................ 44
5.1.2 RESCAL 分解模型和隐因子矩阵 ............................... 45
5 Tucker 分解的应用实例
5.1 基于 Tucker 分解的多关系网络社团发现
5.1.1 多关系网络
多关系网络[65]是指在一个复杂的社会网络中，实体之间都包含着多种不同类型的关系。事实上，在现实世界中，绝大部分的社会网络都属于多关系网络，即网络中的节点之间的连接类型并非是单一的。例如 Twitter 或微博等社交网络中，用户之间有好友、阅读、转发、提及等不同的连接关系；QQ 或微信等社交网络中，用户之间有好友、亲属、同事、同学等不同的连接关系；在一个学术的网络中，作者和论文之间存在合作、引用等关系。因此，在这种网络中，各种类型的关系既相互联系，又相互制约，传统的单一连接网络模型已经无法将其完整的描述，故而对于多关系网络的研究，成为复杂网络领域的一个研究热点。多关系网络数据本身就可以用张量表示，即“结点-结点-关系”的元组结构，如图 5.1所示。
.........................
6 总结与展望
张量分解是一个经典而基础的数据分析方法，被应用于各个热门的研究领域，同时有其丰富的研究理论和经验。然而随着大数据时代的到来，数据量的规模急剧增加，传统的单机环境下的张量分解算法已经无法满足人们的实际需求，因此，对于张量分解的并行化研究有着极其重要的现实意义。Tucker 分解是张量分解的一种经典的分解方式，有着广泛的应用场景。针对 Tucker 分解算法的并行化研究很多，但都各有优劣，效果不甚理想。目前，对于图结构数据的研究愈演愈烈，由于图结构数据与张量数据之间存在天然的联系，许多研究人员考虑将张量和张量分解引入到图结构数据的研究领域中，旨在挖掘图结构数据的潜在知识。本文基于并行图处理框架 PowerGraph 对此也做了些许尝试，主要总结为以下几点：
（1）设计并实现了 Tucker 分解的并行算法，并从不同角度的对该算法进行了多次的对比实验和分析；
（2）设计并实现了 TRSVD 的并行算法，并将其应用到 Tucker 分解算法的并行化中，提高了整体算法的计算效率；
（3） 将 Tucker 分解并行算法应用到多关系网络数据和彩色图片数据，分别进行了多关系网络的社团发现和彩色图片的数据压缩两组实验，并且对各自的实验结果进行分析和总结。
参考文献（略）