[發(fā)明專利]處理大規(guī)模矩陣數(shù)據(jù)的主成分分析方法

在審

• 申請?zhí)枺?/td>: 201611153472.6
• 申請日: 2016-12-14
• 公開（公告）號: CN106855918A
• 公開（公告）日: 2017-06-16
• 發(fā)明（設(shè)計）人: 喻文健;谷昱
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 北京清亦華知識產(chǎn)權(quán)代理事務(wù)所(普通合伙)11201
• 代理人: 張潤

技術(shù)領(lǐng)域

本發(fā)明涉及大數(shù)據(jù)分析技術(shù)領(lǐng)域，特別涉及一種處理大規(guī)模矩陣數(shù)據(jù)的主成分分析方法。

背景技術(shù)

主成分分析，即PCA(Principal Component Analysis)，是一種常用的數(shù)據(jù)分析方法。PCA通過矩陣計算提取出原始數(shù)據(jù)在線性空間中的一組主要基向量(即主要特征分量)，然后將原始數(shù)據(jù)在這組基上投影，實現(xiàn)高維數(shù)據(jù)的降維。對經(jīng)過降維后的數(shù)據(jù)，可進一步做聚類、分類等運算，實現(xiàn)特征提取、自動分類、識別等人工智能應(yīng)用。當前，主成分分析作為一種重要的無監(jiān)督學(xué)習方法，已廣泛用于數(shù)據(jù)挖掘、機器學(xué)習有關(guān)的各種應(yīng)用問題中。

在實際問題中，數(shù)據(jù)往往可以表示為一個矩陣。不失一般性，將每個數(shù)據(jù)看成矩陣A的一行，那么矩陣的列數(shù)就是每個數(shù)據(jù)的維度。主成分分析計算的目標是原始數(shù)據(jù)的若干個主要特征分量，可通過矩陣的特征值分解或奇異值分解得到。基于矩陣特征值分解的方法是先計算矩陣A^TA，然后對A^TA進行特征值分解，得到最大的若干特征值對應(yīng)的特征向量就是要求的“主成分”。基于矩陣奇異值分解的方法直接對矩陣A做奇異值分解：A＝UΣV^T，其中U和V均為正交陣，Σ為對角元從大到小排列的對角陣，得到的V矩陣的前若干列就是要求的“主成分”。若數(shù)據(jù)維度不太高，即A的列數(shù)遠小于行數(shù)，基于特征值分解的方法計算效率比較高，因為其處理的A^TA矩陣是一個階數(shù)較小的矩陣。

另一方面，隨著移動設(shè)備、互聯(lián)網(wǎng)、傳感器網(wǎng)絡(luò)、基因工程的迅速發(fā)展，產(chǎn)生數(shù)據(jù)的來源變得多樣化，同時數(shù)據(jù)量也呈現(xiàn)出指數(shù)級的增長趨勢。也就是說，當前正處在所謂的“大數(shù)據(jù)”時代。如何在可承受的時間空間限制下存儲、分析和管理日益增長的數(shù)據(jù)集成為傳統(tǒng)的數(shù)據(jù)處理手段面臨的一個難題。研究表明，目前85％的數(shù)據(jù)都可以直接或通過轉(zhuǎn)換后表示為數(shù)值型數(shù)據(jù)，即常見的整型、浮點型數(shù)據(jù)，而數(shù)據(jù)庫中存儲數(shù)值型數(shù)據(jù)構(gòu)造的“表”結(jié)構(gòu)通常被當作矩陣進行處理。因此，如何針對這些大數(shù)據(jù)在產(chǎn)生、存儲、應(yīng)用等方面的特點，研究出有效的“大矩陣”數(shù)據(jù)分析方法變得異常重要。具體來說，由于數(shù)據(jù)規(guī)模太大，它們可能是分布式存儲的(即在網(wǎng)絡(luò)上不同的計算機節(jié)點上)、或存儲在計算機硬盤上且無法完整地載入到內(nèi)存中(由于內(nèi)存容量限制)。在其他一些應(yīng)用場景中，這些數(shù)據(jù)也可能是按“數(shù)據(jù)流”的方式逐漸生產(chǎn)、獲取到的，不適合采用傳統(tǒng)的先存儲下來再計算的方式對它們進行處理。考慮到傳統(tǒng)的計算主成分分析的方法需對整個矩陣進行特征值分解或奇異值分解，其內(nèi)在算法需要反復(fù)的讀取、遍歷數(shù)據(jù)矩陣的元素(若要計算前k個主成分，至少要完整地讀取矩陣元素k遍)，顯然它們不適合對上述場景中讀取開銷巨大的大數(shù)據(jù)進行分析。

考慮到上述背景，基于隨機化的矩陣計算方法，包括特征值分解、奇異值分解的算法，在近年來備受人們關(guān)注。在文獻：N.Halko,P.-G.Martinsson and J.A.Tropp,Finding structure with randomness:Probabilistic algorithms for constructing approximate matrix decompositions,SIAM Review,53(2011),no.2,pp.217-288(以下簡寫作SIAM2011)中，提出了一種對矩陣數(shù)據(jù)遍歷次數(shù)較少的隨機奇異值分解算法。該方法通過將原始矩陣A乘以一個僅含k列的隨機矩陣，得到原始矩陣列空間的k維特征子空間，然后求出該子空間的正交基向量矩陣Q，以及A的近似分解：A≈QB，其中B為一個只有k行的矩陣。最后對B這個較小的矩陣進行傳統(tǒng)奇異值分解計算，可近似得到原始矩陣A的前k個奇異值和相應(yīng)的左、右奇異向量。在文獻SIAM2011中，還對上述近似算法的準確度進行了理論分析，結(jié)果表明它在很大的概率上能使誤差落在很小的限度內(nèi)，同時也提出了幾種提高結(jié)果準確度的技巧。

應(yīng)當指出，文獻SIAM2011所提方法雖然相比傳統(tǒng)的奇異值分解算法大大減少了對矩陣元素的遍歷次數(shù)，但它至少需要遍歷矩陣元素兩遍，從計算效率上仍有提升空間，并且無法適應(yīng)數(shù)據(jù)流式大數(shù)據(jù)的處理要求。

發(fā)明內(nèi)容

本發(fā)明旨在至少解決上述技術(shù)問題之一。

為此，本發(fā)明的目的在于提出一種處理大規(guī)模矩陣數(shù)據(jù)的主成分分析方法，該方法適合于多種大數(shù)據(jù)分析場景，具有較高的計算效率和實用性。