分布式的增量式张量Tucker分解方法

• 全文链接
• 请求原文

作   者：

杨克宇;  高云君;  陈璐;  葛丛丛;  沈怡峰; 

作者机构：

浙江大学计算机科学与技术学院; 

关键词：

增量式;  张量;  Tucker分解;  Spark;  分布式; 

期刊名称：

计算机学报

基金项目：

反Top-k空间关键字查询可用性研究

i s s n：

0254-4164

年卷期：

2021 年 008 期

页   码：

1696-1713

摘   要：

随着社交网络、电商系统、移动终端设备的快速发展,海量且高维的数据正以前所未有的速度不断地增长和积累。高维数据可以自然地表示为张量。张量的Tucker分解方法是一种常用且经典的高维数据分析机器学习方法,被广泛地应用于推荐系统、图像压缩、计算机视觉等多个领域。然而,传统的张量分解方法大多只能处理静态的数据,并不适用于动态增长的数据。当处理不断增长的数据时,传统方法大多只能低效地重新开始计算,以完成张量分解。针对增量式数据对传统张量分解方法带来的挑战,本文提出了一种分布式的增量式张量Tucker分解方法DITTD,首次解决了海量高维且动态增长数据上高效的分布式张量Tucker分解问题。该方法首先根据增量数据相对原始数据的位置关系对其进行分类处理。为了实现分布式节点的负载均衡,本文指出张量的最优划分是NP-难问题,并使用启发式方法以实现尽可能均匀的张量划分。为了避免张量Tucker分解的中间结果爆炸问题,本文提出了一种新颖的增量式张量Tucker分解计算方法。该方法减少了中间结果的计算和网络传输通信量,以提升分布式的增量式张量Tucker分解效率。最后,本文在真实与合成数据集上进行了大量的实验。实验结果验证了本文方法的运行效率比基准方法提升了至少1个数量级,并具有良好的可扩展性。