趙桂儒

摘要：PCA是一種常用的線性降維方法，但在實際應(yīng)用中，當(dāng)數(shù)據(jù)規(guī)模比較大時無法將樣本數(shù)據(jù)全部讀入內(nèi)存進行分析計算。文章提出了一種針對較大規(guī)模數(shù)據(jù)應(yīng)用PCA進行降維的方法，該方法在不借助Hadoop云計算平臺的條件下解決了較大規(guī)模數(shù)據(jù)不能直接降維的問題，實際證明該方法具有很好的應(yīng)用效果。

關(guān)鍵詞：主成分分析；降維；大數(shù)據(jù)

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2014）08-1835-03

現(xiàn)實生活中人們往往需要用多變量描述大量的復(fù)雜事物和現(xiàn)象，這些變量抽象出來就是高維數(shù)據(jù)。高維數(shù)據(jù)提供了有關(guān)客觀現(xiàn)象極其豐富、詳細的信息，但另一方面，數(shù)據(jù)維數(shù)的大幅度提高給隨后的數(shù)據(jù)處理工作帶來了前所未有的困難。因此數(shù)據(jù)降維在許多領(lǐng)域起著越來越重要的作用，通過數(shù)據(jù)降維可以減輕維數(shù)災(zāi)難和高維空間中其他不相關(guān)屬性。所謂數(shù)據(jù)降維是指通過線性或非線性映射將樣本從高維空間映射到低維空間，從而獲得高維數(shù)據(jù)的一個有意義的低維表示的過程。

主成分分析（Principal Component Analysis，PCA）是通過對原始變量的相關(guān)矩陣或協(xié)方差矩陣內(nèi)部結(jié)構(gòu)的研究，將多個變量轉(zhuǎn)換為少數(shù)幾個綜合變量即主成分，從而達到降維目的的一種常用的線性降維方法。這些主成分能夠反映原始變量的絕大部分信息，它們通常表示為原始變量的線性組合。在實際應(yīng)用中當(dāng)數(shù)據(jù)規(guī)模超過計算機內(nèi)存容量（例如16G）時就無法將樣本數(shù)據(jù)全部讀入內(nèi)存來分析原始變量的內(nèi)部結(jié)構(gòu)，這成為PCA在實際應(yīng)用中存在的一個問題。該文從描述PCA變換的基本步驟出發(fā)，提出了一種不需要Hadoop等云計算平臺即可對較大規(guī)模數(shù)據(jù)進行降維的一種方法，實際證明該方法具有很好的應(yīng)用效果。

1 PCA變換的基本步驟

PCA是對數(shù)據(jù)進行分析的一種技術(shù)，主要用于數(shù)據(jù)降維，方法是利用投影矩陣將高維數(shù)據(jù)投影到較低維空間。PCA降維的一般步驟是求取樣本矩陣的協(xié)方差矩陣，計算協(xié)方差矩陣的特征值及其對應(yīng)的特征向量，由選擇出的特征向量構(gòu)成這個投影矩陣。

[cov（x1，x1），cov（x1，x2），cov（x1，x3），…，cov（x1，xN）cov（x2，x1），cov（x2，x2），cov（x2，x3），…，cov（x2，xN） ?cov（xN，x1），cov（xN，x2），cov（xN，x3），…，cov（xN，xN）] （1）

假設(shè)[XM×N]是一個[M×N（M>N）]，用PCA對[XM×N]進行降維分析，其步驟為：

1）將矩陣[XM×N]特征中心化，計算矩陣[XM×N]的樣本的協(xié)方差矩陣[CN×N]，計算出的協(xié)方差矩陣如式（1）所示，式中[xi]代表[XM×N]特征中心化后的第[i]列；

2）計算協(xié)方差矩陣[CN×N]的特征向量[e1，e2...eN]和對應(yīng)的特征值[λ1，λ2...λN]，將特征值按從大到小排序；

3）根據(jù)特征值大小計算協(xié)方差矩陣的貢獻率及累計貢獻率，計算公式為：

4）根據(jù)累計貢獻率[Θr]的大小確定投影矩陣的維數(shù)[r]，其中[r≤n]；

5）按從大到小取前[r]個特征值對應(yīng)的特征向量作為投影矩陣[SN×r]，將需要降維的矩陣[XM×N]與投影矩陣[SN×r]相乘，得到降維后的矩陣[TM×r].

2 較大規(guī)模數(shù)據(jù)應(yīng)用PCA降維的方法

在實際應(yīng)用中，一般的計算機平臺的內(nèi)存容量有限（例如16G），但當(dāng)數(shù)據(jù)規(guī)模往往比較大（幾十、上百G），這時無法將樣本數(shù)據(jù)全部讀入內(nèi)存來進行計算，這成為PCA降維方法在實際應(yīng)用中存在的一個問題。通過分析第1部分的PCA降維步驟可以發(fā)現(xiàn)，對數(shù)據(jù)進行降維時最關(guān)鍵的步驟是計算樣本數(shù)據(jù)的協(xié)方差矩陣，該文設(shè)計了一種應(yīng)用PCA對較大規(guī)模數(shù)據(jù)降維時求取協(xié)方差矩陣的方法，具體方法是：將特征中心化后的樣本數(shù)據(jù)[XM×N]按列（[x1，x2...xN]）分別存放在不同文件中，分別讀取文件[xi]和文件[xj]計算第[i]列[xi]和第[j]列[xj]的協(xié)方差[cov（xi，xj）]。因為[CN×N]為對稱矩陣，也即[cov（xi，xj）]與[cov（xj，xi）]相等，因此只需計算[CN×N]的上三角矩陣，對應(yīng)填充下三角矩陣即可。一個循環(huán)遍歷計算協(xié)方差的算法描述如下：

程序需要$1和$2兩個輸入?yún)?shù)，分別是需要分割文件的列數(shù)和和文件名，分割后將按列存放為1.txt、2.txt等等。

2）算法性能

文中第2部分提出的算法主要針對數(shù)據(jù)增長到一定規(guī)模（例如幾十G）的時候，無法將全部數(shù)據(jù)一次性讀入內(nèi)存從而計算協(xié)方差矩陣的情況而提出的。算法采取分批讀取數(shù)據(jù)的方式分別計算協(xié)方差，需要[N]次遍歷，其中[k]值取1時運行時間最長，需要讀取[N]個文件和計算[N]次協(xié)方差，[k]值取[N]時運行時間最短，只需讀取一次文件和計算一次協(xié)方差。算法的缺點是運行的時間比直接讀取數(shù)據(jù)計算協(xié)方差要長，優(yōu)點是解決了較大規(guī)模數(shù)據(jù)不能直接降維的問題。為了提高運算速度可在服務(wù)器上提交[N]個進程或在超算平臺中提[N]個任務(wù)的方法并行執(zhí)行[N]次遍歷程序。

4 結(jié)束語

當(dāng)樣本數(shù)據(jù)達到一定規(guī)模（幾十、上百G）時，無法將數(shù)據(jù)全部讀入內(nèi)存直接對數(shù)據(jù)將進行降維。該文提出了一種在不借助Hadoop等云計算平臺對數(shù)據(jù)進行降維的方法。在實際工作中筆者利用文中第2部分提出的降維方法應(yīng)用到圖像特征數(shù)據(jù)（例如SIFT和STIP）的降維中，實驗證明該方法解決了較大規(guī)模數(shù)據(jù)不能直接降維的問題。但是當(dāng)數(shù)據(jù)量繼續(xù)增大（例如T級）時，數(shù)據(jù)每一列的大小就可能超過計算機內(nèi)存容量，這時就需要考慮借助Hadoop等云計算平臺解決大數(shù)據(jù)降維的問題。

參考文獻：

[1] 謝楓平.聚類分析中的高維數(shù)據(jù)降維方法研究[J].閩西職業(yè)技術(shù)學(xué)院學(xué)報，2009，11（4）：124-128.

[2] 吳曉婷，閆德勤.數(shù)據(jù)降維方法分析與研究[J].計算機應(yīng)用研究，2009，26（8）.

[3] 姚勁勃，余宜誠，于卓爾，等.基于 PCA 降維協(xié)同過濾算法的改進[J].吉林大學(xué)學(xué)報：信息科學(xué)版，2011， 29（5）：494-497.

[4] 蔣博文.基于 PCA 變換的多光譜圖像降維方法研究[J].信息技術(shù)，2012（8）：98-101.

[5] 胡永剛，吳翊.基于加權(quán) PCA 的聲音指紋降維技術(shù)[J].計算機應(yīng)用，2006（9）.