结合GPU技术的并行张量分解算法的研究与应用

发布时间：2020-10-10 17:33

　　 张量分解的方法不仅能够保留高维数据中潜在的结构关系,同时能够实现高维数据的降维和特征提取,因此广泛的用于高维数据的数据挖掘研究中。但在实际应用场景中,张量分解算法的时效性较差。因此,研究高效的张量分解算法对于处理现实场景中的应用问题具有重要意义。本文以提高张量分解在实际应用场景中的计算效率为目的,以GPU并行技术为基础,首先针对算法中常用的矩阵运算,给出一种省去冗余计算步骤的改进算法;然后针对现实中高维数据稀疏性的特点,采用稀疏的数据结构进行存储和计算,提高GPU并行计算过程中的内存使用效率;最后设计适当的线程划分方式,设计实现并行算法,最大程度的提高并行算法的计算效率。本文的主要工作如下:第一,总结分析数据挖掘中张量分解相关领域的研究现状,阐明高效的张量分解算法所具有的现实意义,对比现有研究学者对于提高张量分解算法效率的研究思路。第二,介绍张量和张量分解的基本概念,研究CP张量分解的原理,分析了CP-ALS算法的时间与空间复杂度,为后续研究工作奠定基础。第三,研究现有的并行开发环境和并行技术,包含GPU的硬件特性和CUDA计算平台的并行计算模型特点。分析了现有基于GPU的并行张量分解算法的不足,例如算法并行程度不高,计算任务庞大等。第四,针对张量分解CP-ALS算法中包含复杂矩阵运算的步骤,如Khaki-Rao乘积,提出一种改进的计算思路。同时,采用稀疏的数据结构,给出改进方法的基于GPU的并行化方案。最后,设计实现完整的结合GPU技术的并行CP张量分解算法,并通过CUDA并行计算平台在模拟数据集和真实数据集DBLP与Movielens上进行了算法的性能对比的实验分析。第五,对张量分解算法在实际中的应用做了进一步的研究。在时序网络的社区发现研究中,针对基于张量分解的社区发现算法的理论分析的证明不足,首先论证模块度张量在分解后得到系数与社区模块度之间存在正比关系,建立社区发现算法的优化目标函数与社区模块度之间的等价关系,进而提出一种基于模块度张量的社区发现算法。在模拟数据集和真实数据集PSTN与DBLP上,验证算法的有效性。
【学位单位】：兰州交通大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP311.13;O183.2
【部分图文】：

的上下文感知推荐算法，用于社会网络中的精准推荐。杨秋勇针）三元关系，提出了基于张量分解的最优评分推荐 LORTF 算法，并证了该算法相比协同过滤等算法具有更高的推荐准确度。在多关系网研究中，于乐[32]通过构造（节点-节点-时间）的相似性网络张量，提分解的社区演化分析模型，并提出了社团结构凝聚度和社团演化活跃构演化规律的评价指标。李旭涛[33]针对多关系网络提出了基于马尔k 算法，设计了一种合理计算节点间关系重要性的计算方法；同时，关的多关系网络提出了基于张量的 MultiComm 社区发现算法，还针系网络，以 MeraFac 社区发现模型为基础进行改进，提出了一种考TV 社区发现算法。的主要研究工作及创新点以 CP 张量分解的经典 CP-ALS 算法为研究对象，对当前的研究成果，总结了张量和张量分解相关领域的研究现状，阐明了高效的张量分。总结研究了现有的并行平台与并行计算技术，分析了已有的并行张方案的优劣，为提出更高效的并行张量分解算法做铺垫。

兰州交通大学硕士学位论文 dim，也可称为阶（order）或者模（mode）。例如，可以称三维张量为三量的模为 3。此，我们对本文中使用的不同维度的张量的符号进行声明和区分。本文中向量使用小写字母表示，例如向量a ；二阶张量或矩阵用大写字母表示，高阶张量使用花体大写字母表示，例如三阶张量X 。向量a 的第n 个元素阵A 的第 i ,j 个元素表示为Aij，三阶张量X 的第 i , j ,k 元素表示为ijkx 。张量划分矩阵中，行（Row）或者列（Column）中的元素可以用一些特定顺序的点集阵a 的第i 行表示为i:A 或者 i ,: A 。对于高维张量，可以将张量按照不同方大小的不同纤维（Fiber），每个纤维都可以看作一个向量。如图 2.2 所示个三阶张量进行模-1 方向上的纤维划分，则可得到模-1 纤维:jkX 。

行（Row）或者列（Column）中的元素可以用一些特定顺序的点集表阵a 的第i 行表示为i:A 或者 i ,: A 。对于高维张量，可以将张量按照不同方向大小的不同纤维（Fiber），每个纤维都可以看作一个向量。如图 2.2 所示个三阶张量进行模-1 方向上的纤维划分，则可得到模-1 纤维:jkX 。(a) Mode-1(column)fibers: x:jk(b) Mode-2 (row) fibers: xi:k(c) Mode-3 (tube) fibers: xij:图 2.2 张量的纤维划分时，高维张量还可以划分为切片（Slice）的形式，每个切片可以看作一个
【参考文献】

相关期刊论文 前2条

1 邹本友;李翠平;谭力文;陈红;王绍卿;;基于用户信任和张量分解的社会网络推荐[J];软件学报;2014年12期

2 杨博;刘大有;金弟;马海宾;;复杂网络聚类方法[J];软件学报;2009年01期

相关博士学位论文 前4条

1 蒋朦;社交媒体复杂行为分析与建模[D];清华大学;2015年

2 于乐;社会网络中社团发现及网络演化分析[D];北京邮电大学;2014年

3 刘亚楠;基于图和低秩表示的张量分解方法及应用研究[D];安徽大学;2014年

4 李旭涛;基于张量的多关系图挖掘关键技术研究[D];哈尔滨工业大学;2013年

相关硕士学位论文 前2条

1 杨秋勇;应用张量分解法学习最优评分的推荐系统研究[D];华南理工大学;2012年

2 武南南;时变网络的链接预测研究[D];重庆大学;2012年

本文编号：2835375