[發明專利]基于分布式環境的張量CP分解實現方法

有效

• 申請號: 201711426277.0
• 申請日: 2017-12-26
• 公開（公告）號: CN108170639B
• 公開（公告）日: 2021-08-17
• 發明（設計）人: 周維;麥超;蔡莉;何靖;姚紹文
• 申請（專利權）人: 云南大學
• 主分類號: G06F17/15
• 分類號: G06F17/15
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 溫利平;陳靚靚

本發明公開了一種基于分布式環境的張量CP分解實現方法，基于ALS算法，對每次迭代過程中因子矩陣A⁽ⁿ⁾的更新，首先通過拆分Khatri?Rao乘積的方式計算Y＝X_(n)(A^(N)⊙…⊙A⁽ⁿ⁺¹⁾⊙A^(n?1)⊙…⊙A⁽¹⁾)，然后采用并行計算外積的方式計算最后將矩陣Y和矩陣V進行分塊，采用Map操作將矩陣Y和矩陣V中對應的分塊矩陣分發到Spark集群的主機上，采用Reduce操作進行矩陣乘法，然后再將乘法結果采用Map操作發送到一臺主機上采用Reduce操作進行合并，得到A⁽ⁿ⁾＝YV。本發明基于MapReduce和Spark技術來實現張量CP分解，可以有效提高張量CP分解的效率。

技術領域

本發明屬于張量分解技術領域，更為具體地講，涉及一種基于分布式環境的張量CP分解實現方法。

背景技術

近年來，在社交網絡、計算廣告和電商等領域，數據規模增長迅速。為了描述復雜關系，例如：社交網絡中好友關系、計算廣告和電商中每個人的特征，基于高維度空間建模的數據大量出現。這些高階數據的出現，使得傳統用矩陣以二維的方式來描述數據的方法逐漸不適用，因此迫切需要一種能夠描述高維數據中的高階關系的工具。

張量作為矩陣在高維度空間的泛化，是描述多個變量之間的高階關系更好的工具。早在1940年，張量就在心理測量學中被提出了，后來張量被廣泛應用于物理、數值分析、信號處理和理論計算機科學等理論領域。由于張量本身是高維數組，而基于張量的算法在時間復雜度上往往是指數級別的，計算時需要很多次的迭代，早期的計算機根本無法完成這樣的計算。

隨著硬件和軟件技術的發展，大型服務器由于成本和維護等因素，逐漸不再是工業界的首選，由普通PC搭建的集群逐漸成為了主流的數據處理平臺。繼理論領域的發展之后，因為張量描述和分析高階數據的能力，張量再次在工程領域受到了大量的關注。MapReduce等編程模型的出現，把單臺機器獨立運行的算法變為了分散到多臺機器上運行的算法，利用多臺機器并行計算的能力提高計算效率。分布式存儲和計算這樣的大數據技術的興起，則使處理大規模數據成為了可能。目前常用的分布式計算框架有Hadoop和Spark，基于MapReduce編程模型的Hadoop是最廣泛使用的分布式計算框架，但Hadoop的每個MapReduce任務在執行前后都需要讀寫磁盤，大量的磁盤I/O使得Hadoop并不適用于迭代很多的場景。Spark中的分布式彈性數據集(RDD)是存儲在內存當中的，每次迭代避免了訪問磁盤帶來的開銷，大大提升了迭代的效率。

張量的計算是易于并行化的，通過分布式處理的方式，現在能夠完成早期無法處理的問題。而張量的CP分解(Canonical Polyadic Decomposition)作為張量研究中的關鍵，也在逐漸被越來越廣泛的使用，CP分解能夠提取出數據中隱含的主題、去除噪聲數據、降低數據維度。傳統的CP分解算法是單機運行的，雖然通過提升機器的配置可以使程序處理更大規模的數據，但是這樣的提升畢竟有限。

發明內容

本發明的目的在于克服現有技術的不足，提供一種基于分布式環境的張量CP分解實現方法，基于MapReduce和Spark技術提高張量CP分解的效率。

為了實現以上發明目的，本發明基于分布式環境的張量CP分解實現方法，對于秩為R的N階張量初始化N個因子矩陣A⁽ⁿ⁾，每次迭代時輪流更新的每個因子矩陣，計算時固定其他的因子矩陣不變，重復迭代直到目標函數的值為零或小于給定的閾值為止，此時的N個因子矩陣A⁽ⁿ⁾即為張量的CP分解結果，其中因子矩陣A⁽ⁿ⁾的更新公式為：

因子矩陣A⁽ⁿ⁾的更新采用以下方法：