[發(fā)明專利]一種基于并行化主成分分析算法的數(shù)據(jù)降維方法

在審

• 申請?zhí)枺?/td>: 201710384662.7
• 申請日: 2017-05-26
• 公開（公告）號(hào): CN107273917A
• 公開（公告）日: 2017-10-20
• 發(fā)明（設(shè)計(jì)）人: 王勇;楊曉東;陳炬光;楊晨;張應(yīng)福
• 申請（專利權(quán)）人: 電子科技大學(xué)
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 成都金英專利代理事務(wù)所(普通合伙)51218
• 代理人: 袁英

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

本發(fā)明涉及高維數(shù)據(jù)線性降維技術(shù)，具體地涉及一種基于主成分分析算法的數(shù)據(jù)降維方法。

背景技術(shù)

隨著網(wǎng)絡(luò)信息技術(shù)和移動(dòng)互聯(lián)網(wǎng)的不斷發(fā)展，企業(yè)不同業(yè)務(wù)垂直領(lǐng)域的數(shù)據(jù)量越來越大，如何從這些數(shù)據(jù)中發(fā)掘出有價(jià)值的信息，為企業(yè)提供重要決策支撐，成為企業(yè)制勝的關(guān)鍵。這些數(shù)據(jù)往往具有兩個(gè)特點(diǎn)：一是數(shù)據(jù)規(guī)模大；二是數(shù)據(jù)的維數(shù)很高。大規(guī)模的高維數(shù)據(jù)給數(shù)據(jù)的傳輸、存儲(chǔ)以及數(shù)據(jù)模式的發(fā)掘提出了挑戰(zhàn)，如何對大規(guī)模的高維數(shù)據(jù)進(jìn)行高效的處理和有效的模式發(fā)掘顯得尤為重要。這些高維數(shù)據(jù)中各個(gè)維數(shù)之間通常具有某種聯(lián)系，過高的維數(shù)不僅造成了數(shù)據(jù)的冗余，也增大了數(shù)據(jù)處理的時(shí)間開銷，隱藏了數(shù)據(jù)的本質(zhì)特征，因此研究一種數(shù)據(jù)降維方法具有重要的實(shí)際應(yīng)用價(jià)值。

數(shù)據(jù)降維是將樣本從原始空間通過某種線性或非線性變換投影到一個(gè)低維的子空間，可發(fā)掘出隱藏在高維數(shù)據(jù)中的能解釋原始數(shù)據(jù)的低維結(jié)構(gòu)，這種低維結(jié)構(gòu)保持了原始數(shù)據(jù)的主要信息。典型的線性降維算法有主成分分析(PCA)和線性判別分析(LDA)。PCA主要是把原始數(shù)據(jù)中線性相關(guān)的隨機(jī)變量轉(zhuǎn)換為幾個(gè)線性無關(guān)的新隨機(jī)變量，且保留了原始數(shù)據(jù)的主要信息。LDA的目標(biāo)是使得降維后的低維空間中，同類數(shù)據(jù)盡可能靠近，非同類數(shù)據(jù)盡可能的分離。相比于LDA，PCA的應(yīng)用范圍更廣。線性降維算法由于具有完備的理論體系，且在各種應(yīng)用中都表現(xiàn)出了良好的適用性，正在廣泛地應(yīng)用于模式識(shí)別、統(tǒng)計(jì)學(xué)分析、數(shù)字圖像處理以及計(jì)算機(jī)視覺等領(lǐng)域。

傳統(tǒng)的單機(jī)主成分分析算法在進(jìn)行數(shù)據(jù)降維時(shí)會(huì)存在以下缺點(diǎn)：1、計(jì)算機(jī)內(nèi)存不足以放下整個(gè)大規(guī)模的待降維數(shù)據(jù)集，樣本數(shù)據(jù)集過大將限制后續(xù)對數(shù)據(jù)模式發(fā)掘的準(zhǔn)確性，若只升級計(jì)算機(jī)硬件，當(dāng)數(shù)據(jù)集的需求繼續(xù)增大時(shí)，將導(dǎo)致擴(kuò)展性較差；2、即使單機(jī)計(jì)算機(jī)硬件滿足內(nèi)存的需要，傳統(tǒng)的主成分分析需要多次遍歷數(shù)據(jù)樣本集，這時(shí)的磁盤I/O必將成為限制主成分分析效率的瓶頸，導(dǎo)致主成分分析計(jì)算效率較低。這兩個(gè)主要缺點(diǎn)限制了主成分分析在大規(guī)模高維數(shù)據(jù)降維技術(shù)領(lǐng)域的應(yīng)用潛力。

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

本發(fā)明針對現(xiàn)有技術(shù)中的不足，提供一種利用MapReduce并行計(jì)算框架的主成分分析方法，解決傳統(tǒng)單機(jī)主成分分析算法的由于數(shù)據(jù)規(guī)模太大而無法一次加載到內(nèi)存的問題，有利于減少I/O操作，提高數(shù)據(jù)降維的處理效率。

為實(shí)現(xiàn)上述目的，本發(fā)明的技術(shù)方案包括以下步驟：

S1：把待降維的高維數(shù)據(jù)構(gòu)造成樣本數(shù)據(jù)矩陣D_n×m；

S2：計(jì)算樣本數(shù)據(jù)矩陣D_n×m的協(xié)方差矩陣C_m×m；

S3：計(jì)算協(xié)方差矩陣C_m×m的m個(gè)特征值和對應(yīng)的m個(gè)特征向量；

S4：根據(jù)特征值和特征向量確定主成分?jǐn)?shù)量k；

S5：利用前k大特征值對應(yīng)的特征向量得出主成分矩陣。

其中，步驟S2進(jìn)一步包括步驟：

S21：分配N個(gè)Mapper；

S22：分配一個(gè)Reducer，Reducer的輸入是步驟S21中每個(gè)Mapper的輸出結(jié)果；

S23：將步驟S22中Reducer的匯總結(jié)果通過協(xié)方差矩陣公式得到協(xié)方差矩陣C_m×m。

步驟S4進(jìn)一步包括步驟：

S41：對特征值和其對應(yīng)的特征向量進(jìn)行排序；

S42：計(jì)算主成分?jǐn)?shù)量k。

步驟S5進(jìn)一步包括步驟：

S51：根據(jù)步驟S41中得到的排序后的特征值和其對應(yīng)的特征向量，取前k大特征值對應(yīng)的特征向量構(gòu)造變換矩陣TransMat；

S52：若待降維樣本數(shù)據(jù)矩陣D_n×m能夠一次性加載到內(nèi)存，則將樣本數(shù)據(jù)矩陣D_n×m與變換矩陣TransMat相乘得到主成分矩陣。

若待降維樣本數(shù)據(jù)不能一次加載到內(nèi)存，則處理流程包括步驟：

S61：把樣本數(shù)據(jù)矩陣D_n×m按照步驟S2中的分塊方式進(jìn)行分塊；

S62：把每個(gè)數(shù)據(jù)塊與變換矩陣TransMat進(jìn)行相乘，得到該塊的主成分矩陣；

S62：合并每一塊步驟S62得出的主成分矩陣以構(gòu)建整個(gè)樣本數(shù)據(jù)的主成分矩陣。

本發(fā)明的有益效果是：克服了傳統(tǒng)單機(jī)主成分分析算法的由于數(shù)據(jù)規(guī)模太大而無法一次加載到內(nèi)存的問題，并減少了I/O操作，提高了數(shù)據(jù)降維的處理效率。

附圖說明

圖1為本發(fā)明的數(shù)據(jù)降維方法流程圖；

圖2為本發(fā)明的基于MapReduce實(shí)現(xiàn)的并行化主成分分析處理過程圖；