[發明專利]一種分布式高階SVD及其增量計算的方法

在審

• 申請號: 201610056751.4
• 申請日: 2016-01-27
• 公開（公告）號: CN107015946A
• 公開（公告）日: 2017-08-04
• 發明（設計）人: 楊天若;楊天楚;陳星宇;王曉康
• 申請（專利權）人: 常州普適信息科技有限公司
• 主分類號: G06F17/16
• 分類號: G06F17/16;G06F9/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及大數據的數據處理領域，尤其涉及一種分布式高階SVD及其增量計算的方法。

技術背景

隨著云時代的來臨，大數據(Big data)也吸引了越來越多人的關注。大數據具有多關聯，高維度，多變量的特點，而張量作為一種高維數據結構的表達形式，它能夠很好地適應于大數據的諸多特點，因此越來越多的大數據應用將數據用張量的形式組織起來，并利用高維數組理論來對其處理和分析。奇異值分解(SVD)是大數據處理中一種廣泛采用的矩陣分解技術，而高階SVD(HOSVD)是SVD映射到高維空間的針對張量的一種分解形式，它能有效地使用更少的數據近似表達原始張量，萃取核心數據和關聯關系,從而大大減少了數據的處理量。研究表明HOSVD在潛在語義分析、推薦、圖像處理等方面的應用往往能取得很好的效果。

從目前的研究方法以及應用來看，它們對張量的分解往往采用基于單機的HOSVD方法，例如，江南大學申請的專利“基于高階奇異值分解和模糊推理的多聚焦圖像融合方法”(申請號：CN201410057924.5，申請公開號：CN103985104A)的具體實施方式部分采用了單機的HOSVD分解方法。然而數據量巨大的張量無法由一般的計算機來處理，因為這些張量的數據總量超過了內存的大小限制并且處理這么多的數據需要相當長的時間，所以這些研究方法在大張量的環境下是效率低下的，這也導致了這些方法往往不能夠直接應用于現實的大數據場景。對一個大規模張量做HOSVD分解需要耗費大量的內存和較長的時間，如何有效地解決分解過程中因內存消耗而導致內存溢出的問題以及加快分解的速度，是我們所面臨的關鍵問題，因此對HOSVD更高效的計算方法的研究是重要且急迫的。

針對以上的問題，本發明了引入分布式框架及其設計理念，對傳統的基于單機的HOSVD分解算法進行了修改，實現了HOSVD分解算法的并行化，同時也實現了張量增量方式的HOSVD分解算法。

發明內容

本發明的目的在于針對上述現有技術中存在的不足，提供了一種分布式HOSVD的分解方法，以解決因單機內存限制而導致HOSVD分解過程中內存溢出以及單機處理時間過長的問題，同時本方法也適用于張量的增量方式的HOSVD分解，從而提高了張量分解的效率，使其能夠更好地應用于大數據中。

為了實現上述目的，本發明采用如下的技術方案：

1.一種樹形、環形結構融合的分布式系統框架，其主體部分由

PartitionWorker、OrderMaster、CalculateWorker和RoundRobinWorker四類節點構成。

a)在整個分布式系統中只存在一個PartitionWorker節點，它負責原始張量的切塊、分發的操作，即在PartitionWorker節點中將需要處理的原始張量切塊成最小單元的子張量塊，并將各個最小單元的子張量塊分發到不同的CalculateWorker中進行HOSVD分解處理。同時，PartitionWorker也是整個分布式系統的管理節點，當它完成原始張量的切塊、分發操作后，便開始監控整個分布式系統，若分布式系統有故障發生，故障會一級一級地往上匯報，若故障在下層節點中都得不到解決，則它最終會匯報到PartitionWorker節點上，并由PartitionWorker節點做出決策。

b)OrderMaster由PartitionWorker所創建。若原始張量的階(Order)的數目為N，則整個分布式系統中存在著N+1個OrderMaster(OrderMaster₀、OrderMaster₁、……、OrderMaster_N，它們負責生成CalculateWorker節點。CalculateWorker節點負責處理分發或還原過程中的矩陣的計算操作。OrderMaster節點同時管理著CalculateWorker，當CalculateWorker發生故障時，OrderMaster會對故障問題進行相應的處理，若OrderMaster無法處理，它會將故障上報到PartitionWorker中。當CalculateWorker節點計算完成時，對應的OrderMaster節點會停止該CalculateWorker任務，以釋放該任務所占用的內存資源。