基于Spark的標(biāo)準(zhǔn)化PCA算法

董建華， 王國胤， 雍 熙， 史曉雨， 李慶亮

(1.中國科學(xué)院重慶綠色智能技術(shù)研究院 電子信息技術(shù)研究所，重慶 400714； 2.中國科學(xué)院大學(xué)，北京 100049； 3.水利部 水利信息中心，北京 100053； 4.西昌衛(wèi)星發(fā)射中心，海南 文昌 571300)

基于Spark的標(biāo)準(zhǔn)化PCA算法

董建華1, 2， 王國胤1， 雍 熙3， 史曉雨1， 李慶亮4

(1.中國科學(xué)院重慶綠色智能技術(shù)研究院 電子信息技術(shù)研究所，重慶 400714； 2.中國科學(xué)院大學(xué)，北京 100049； 3.水利部 水利信息中心，北京 100053； 4.西昌衛(wèi)星發(fā)射中心，海南 文昌 571300)

主成分分析(PCA)是數(shù)據(jù)挖掘中常用的數(shù)據(jù)降維技術(shù)，它將原來多個變量轉(zhuǎn)化為少數(shù)的幾個綜合指標(biāo)，介紹了主成分分析的原理、Spark的分布式架構(gòu)以及Spark 的MLlib分布式矩陣PCA算法，通過改進(jìn)設(shè)計提出了一種帶有標(biāo)準(zhǔn)化處理的SNPCA算法，并在多核CPU環(huán)境下進(jìn)行了測試驗證，實驗結(jié)果證明了該算法的有效性.

主成分分析；Spark；分布式；標(biāo)準(zhǔn)化處理

0 引言

主成分分析(principal component analysis，PCA)作為一種常用的多指標(biāo)統(tǒng)計方法，是由Karl parson[1]1901年提出的，它將原來多個變量轉(zhuǎn)化為少數(shù)幾個綜合指標(biāo).從數(shù)學(xué)的角度看，它是一種降維處理技術(shù)，能夠最大限度地保留原始數(shù)據(jù)信息，對高維變量進(jìn)行綜合和簡化，并客觀地確定各個指標(biāo)的權(quán)重，從而避免了降維過程中的主觀隨意性.

隨著大數(shù)據(jù)量計算任務(wù)的需求，多核處理下的PCA并行計算逐漸成為數(shù)據(jù)挖掘中必不可少的分析方式，比較著名的方法是Hadoop的Mahout[2]和Spark的MLlib庫[3]實現(xiàn)的并行PCA算法.近幾年，以降低時間復(fù)雜度和通信復(fù)雜性為目的，在分布式平臺上設(shè)計可擴(kuò)展的PCA算法模型，成為多核處理下PCA算法研究的重點[4-5].

Apache Spark于2009年誕生AMPLab，其官方的定義為“Spark是一個通用的大規(guī)模數(shù)據(jù)快速處理引擎”[6].2013年推出的Spark 0.8在全面兼容Hadoop[7](包括Hadoop的HDFS文件系統(tǒng)和存儲數(shù)據(jù)庫)的基礎(chǔ)上，利用更多的內(nèi)存處理機(jī)制大幅提高了系統(tǒng)性能，進(jìn)而提高了在大數(shù)據(jù)環(huán)境下數(shù)據(jù)處理的實時性，同時保證了高容錯性和高擴(kuò)展性. 依靠Scala強(qiáng)有力的函數(shù)式編程、Actor通信模式、閉包、容器、泛型，借助統(tǒng)一資源分配調(diào)度框架Mesos和YARN[8]，并融合了MapReduce和Dryad[9]，Spark最后成了一個簡潔、直觀、靈活、高效的大數(shù)據(jù)分布式處理框架.

Hadoop/MapReduce依靠HDFS來實現(xiàn)分布式環(huán)境下中間數(shù)據(jù)的交互，Spark則通過共享的虛擬內(nèi)存來實現(xiàn)中間數(shù)據(jù)的快速交換[10].相比而言，Spark具有更好的擴(kuò)展性，同時Spark需要更強(qiáng)的CPU以及苛刻的I/O等條件來支持它的運(yùn)行環(huán)境. Spark現(xiàn)有PCA存在的問題是：在Spark的MLlib組件中，分布式矩陣PCA算法的計算是直接對樣本矩陣讀入后轉(zhuǎn)換為分布式矩陣來處理的，并沒有對樣本矩陣進(jìn)行標(biāo)準(zhǔn)化操作. 筆者提出一種帶標(biāo)準(zhǔn)化處理的PCA算法SNPCA(Spark’s normalized principal component analysis)來實現(xiàn)對Spark分布式矩陣的標(biāo)準(zhǔn)化操作，該算法借助Spark的分布式計算平臺，提高了大數(shù)據(jù)環(huán)境下主成分分析的實時處理能力.

1 主成分分析方法

主成分分析的目的是減少數(shù)據(jù)集的維數(shù)，把原有高維的數(shù)據(jù)變量集重新組合為相互無關(guān)的綜合變量集，這些不相關(guān)的綜合變量的數(shù)量小于或等于原始變量的數(shù)量，綜合變量所表征“信息量”的大小用方差來衡量. 通常情況下，主成分分析算法可以看作是一種揭露數(shù)據(jù)的內(nèi)部結(jié)構(gòu)、從而更好地解釋其綜合變量之間關(guān)系的方法，主要計算步驟如下[11].

(1)建立原始變量觀測數(shù)據(jù)構(gòu)成的矩陣.

(1)

(2)對原始變量數(shù)據(jù)構(gòu)成的矩陣進(jìn)行標(biāo)準(zhǔn)化處理來消除不同量綱的影響.

(2)

var(xj)為第j個列向量的方差，即

(3)計算標(biāo)準(zhǔn)化數(shù)據(jù)的相關(guān)系數(shù)矩陣，求相關(guān)系數(shù)矩陣R的特征值(λ1,λ2,…,λp)和相應(yīng)的特征向量ai=(ai1,ai2,…,aip),i=1,2,…,p，用雅克比方法、SVD分解法[12]等.

(4)選擇重要的主成分分量.主成分分量的方差貢獻(xiàn)率ci定義如下：

(3)

第i個主成分分量Fi的累積貢獻(xiàn)率為：

δi=c1+c2+…+ci.

(4)

通常選擇使累積貢獻(xiàn)率達(dá)到85%的主成分變量，計算出主成分變量的表達(dá)式為：

(5)

式中：x1、x2、…、xp表示變量矩陣經(jīng)過標(biāo)準(zhǔn)化處理的值.主成分變化后新的主成分變量彼此不相關(guān)，且方差依次遞減.

2 Spark Mlib庫中的分布式矩陣PCA算法

本節(jié)將以Spark中RowMatrix類型的分布式矩陣為例來研究MLlib中的分布式PCA算法，Spark中，其它兩個分布式矩陣類型indexedRowMatrix、CoordinateMatrix與之類似，在此從略. RowMatrix中求解PCA的函數(shù)方法為：

computePrincipalComponents(k: Int): Matrix[6].

其具體過程是通過先求RowMatrix類型矩陣(標(biāo)識為矩陣A)的格拉姆矩陣，進(jìn)而求得矩陣A的協(xié)方差矩陣，再使用ScalaNLp的SVD方法求解特征值、特征向量，得到分布式矩陣A的主成分分量，其算法流程如圖1所示.

圖1 Spark的MLlib組件中PCA算法流程Fig.1 Flow chart of PCA from Spark’s MLlib component

在Spark MLlib庫中的分布式矩陣PCA算法中，通過對矩陣A進(jìn)行不斷迭代來實現(xiàn)協(xié)方差矩陣求解，其余部分則是串行算法(在提交的計算節(jié)點上串行處理完成).協(xié)方差矩陣的求解是直接對矩陣A進(jìn)行的操作，通過將讀入的數(shù)據(jù)轉(zhuǎn)換為RowMatrix類型矩陣來實現(xiàn)，并沒有對樣本矩陣進(jìn)行標(biāo)準(zhǔn)化操作，鑒于此，我們將引入SNPCA算法來實現(xiàn)對Spark分布式矩陣的標(biāo)準(zhǔn)化操作.

3 基于Spark的標(biāo)準(zhǔn)PCA算法—SNPCA

在數(shù)據(jù)預(yù)處理階段，通常將數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化(normalization)處理后再進(jìn)行數(shù)據(jù)分析. 數(shù)據(jù)的標(biāo)準(zhǔn)化是指將數(shù)據(jù)按比例縮放，調(diào)節(jié)不同的尺度測量值到一個公共的范圍，使數(shù)據(jù)值落入一個小的特定區(qū)間(將不同范圍的數(shù)據(jù)統(tǒng)一到同一個區(qū)間參考系下進(jìn)行比較才有意義[13]). 數(shù)據(jù)的標(biāo)準(zhǔn)化在處理某些指標(biāo)的比較和評價中也經(jīng)常涉及到，通過去除數(shù)據(jù)的范圍和單位量綱的限制，以便不同量級或單位的指標(biāo)能夠進(jìn)行比較和加權(quán)，在許多情況下使用標(biāo)準(zhǔn)化后的變量進(jìn)行主成分分析會顯著地改善分析效果. 對數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理的常見方法有“按小數(shù)定標(biāo)標(biāo)準(zhǔn)化”、“Z-score標(biāo)準(zhǔn)化”和“min—max標(biāo)準(zhǔn)化”等[14].

文獻(xiàn)[15]的研究表明，對于樣本矩陣(n×p型，p遠(yuǎn)小于n)，計算PCA的最好方法是先計算出所有的統(tǒng)計量(時間復(fù)雜度為O(p2n))，再對相關(guān)系數(shù)矩陣或協(xié)方差矩陣(p×p型)進(jìn)行SVD分解[16](時間復(fù)雜度為O(p3)). 在第1章求解PCA的步驟中，依照公式(2)中數(shù)據(jù)標(biāo)準(zhǔn)化進(jìn)行求解需要對樣本數(shù)據(jù)讀入的矩陣進(jìn)行3次掃描，即求出列向量的均值和方差值再代入公式(2)進(jìn)行標(biāo)準(zhǔn)化.在大數(shù)據(jù)量的情況下，事物的觀察數(shù)據(jù)量動輒上萬，這種操作顯然是不可接受的，要盡量提高數(shù)據(jù)的掃描效率，才能適應(yīng)快速分析大數(shù)據(jù)任務(wù)的需要. 鑒于此，我們以Spark的MLlib庫和開源的數(shù)值計算庫ScalaNLP為基礎(chǔ)，設(shè)計改進(jìn)了基于Spark的標(biāo)準(zhǔn)化PCA算法—SNPCA算法來實現(xiàn)對大數(shù)據(jù)樣本矩陣進(jìn)行標(biāo)準(zhǔn)化的PCA操作，算法的的主要步驟如圖2所示.

圖2 改進(jìn)的SNPCA算法流程圖Fig.2 Flow chart of improved SNPCA algorithm

在SNPCA算法中，讀入的數(shù)據(jù)將轉(zhuǎn)換為DenseMatrix類型的矩陣A1，矩陣A1的各個列向量L1,L2, …,Lp鏈接在一個數(shù)組上從而構(gòu)造成“向量數(shù)組”結(jié)構(gòu)，再放入RDD中對每個列向量并行地求解公式(2)所表征的列向量均值、方差等統(tǒng)計量，進(jìn)而對每一個列向量進(jìn)行標(biāo)準(zhǔn)化處理，這些存在于RDD中的列向量將會被重構(gòu)成RowMatrix類型的矩陣A2，再依照圖1的流程求解相關(guān)系數(shù)矩陣、特征值、特征向量，最后根據(jù)這些統(tǒng)計參數(shù)和各個列向量L1,L2, …,Lp求出主成分分量. 下面列出算法的具體步驟及其所需時間.

(1)從Spark的nameNode節(jié)點驅(qū)動程序讀取數(shù)據(jù)文件/數(shù)據(jù)庫創(chuàng)建DenseMatrix類型的矩陣A1.A1存在于Spark驅(qū)動程序所在的nameNode節(jié)點上.

(2)把矩陣A1的列向量Li(i=1, 2,…,p)“掛載”到長度為p的數(shù)組上，使用該數(shù)組轉(zhuǎn)化為Spark的RDD(可以通過Sparkcontext類的def parallelize[T](seq: Seq[T], numSlices: Int): RDD[T]方法)，借助該RDD來并行計算列向量的均值、方差，進(jìn)而對每一個列向量進(jìn)行標(biāo)準(zhǔn)化處理. 假設(shè)資源池可以提供q個core，在Spark并行環(huán)境下，每個core對矩陣中每個元素進(jìn)行運(yùn)算平均時間消耗為Ti.則該步驟整體需要的計算時間為3(pn/q)Ti.

(3)計算列向量轉(zhuǎn)換成的RowMatrix矩陣A2的格拉姆矩陣，進(jìn)而計算A2的相關(guān)系數(shù)矩陣.對于矩陣A，求其格拉姆矩陣的公式為Q=AT*A[17].由于Spark的MLlib提供的API是以并行迭代的方式計算格拉姆矩陣，假設(shè)A2被分成d個分區(qū)，nameNode和dataNode可以提供q個core，格拉姆矩陣被并行處理需要的時間為(p2n/q)Ti. 注意：Spark在邏輯上是基于分區(qū)數(shù)并行的，實際的并行是基于核數(shù)的，并行度為min{d，q}，通常d為核數(shù)q的2.3倍，所以并行度就是核數(shù)q. 由格拉姆矩陣計算相關(guān)系數(shù)矩陣(表示為ρ)[18]，設(shè)Spark串行運(yùn)算條件下，每個core對矩陣中每個元素進(jìn)行運(yùn)算的平均時間消耗為Tc,則需要時間為(p2)Tc.

(4)在Spark的NameNode上對相關(guān)系數(shù)矩陣進(jìn)行SVD分解. 依據(jù)SVD公式[U,S,V]=SVD(ρ)，設(shè)SVD分解后由特征值組成的矩陣為S，由特征向量組成的矩陣為U[19]，該SVD分解需要時間(p3)Tc.

(5)求主成分. 根據(jù)公式(5)求主成分分量F=X*A，則得到主成分分量構(gòu)成的矩陣F為F=A2*U(當(dāng)然也可以根據(jù)特征值的貢獻(xiàn)率進(jìn)行篩選主成分分量)，該過程所需時間為(p2n/q)Ti.

在步驟(1)～(5)中，算法的并行是在A1求列和、列向量方差、標(biāo)準(zhǔn)化，以及由矩陣A2求解格拉姆矩陣和最后求解主成分分量這3個過程中. 由于p遠(yuǎn)小于n，所以在整個計算步驟中，算法的整體復(fù)雜度在性能方面的瓶頸還取決于算法的并行階段. 下面將對整體算法的效率進(jìn)行分析. 一般地，程序加速比的定義[20]如下：

(6)

式中:SN為加速比；T1為單處理器下程序運(yùn)行的時間；TN為有N個處理器并行運(yùn)行時的時間. 由于Spark的運(yùn)行調(diào)度是以核為粒度的，所以在Spark運(yùn)行環(huán)境下，對應(yīng)的加速比公式中T1是串行算法運(yùn)行時間消耗，TN是N核時并行運(yùn)行所消耗的時間. SNPCA算法的時間消耗是前面(1)～(5)過程中時間消耗的總和，所以核數(shù)為q時SNPCA總時間消耗為：

Tq=3(pn/q)Ti+(p2n/q)Ti+(p2)Tc+(p3)Tc+(p2n/q)Ti+k=2(p2n/q)Ti+3(pn/q)Ti+(p2)Tc+(p3)Tc+k.當(dāng)q為1時，SNPCA串行運(yùn)行的時間消耗為:

T1=2(p2n)Ti+3(pn)Ti+(p2)Tc+(p3)Tc+t.所以核數(shù)為q時并行加速比為：

Sq=(2(p2n)Ti+3(pn)Ti+(p2)Tc+(p3)Tc+t) /(2(p2n/q)Ti+3(pn/q)Ti+(p2)Tc+(p3)Tc+k).

(7)

因此，當(dāng)核數(shù)q比較大時，算法的并行優(yōu)勢會比較明顯.

4 仿真實驗

4.1 仿真實驗環(huán)境及數(shù)據(jù)集

4.1.1 SNPCA算法時間性能實驗

在Spark分布式運(yùn)行環(huán)境下，Spark的分區(qū)數(shù)一般為總核數(shù)的2～3倍，讀取的數(shù)據(jù)文件一般來源于HDFS，在讀取HDFS數(shù)據(jù)文件的時候每一個Block(128 M)為生成的RDD的一個分區(qū).考慮到虛擬機(jī)集群中通信和調(diào)度等因素影響，實驗效果會很差，為驗證算法的并行效率，我們選擇在一個DELL服務(wù)器(4核)環(huán)境下做仿真實驗，模擬的隨機(jī)數(shù)據(jù)構(gòu)成240 000×200的樣本矩陣(大小有286 MB)，通過控制不同的核數(shù)來看作業(yè)處理的仿真效果. 另外，為了增強(qiáng)對比試驗，使用ScalaNLP的線性代數(shù)包構(gòu)建的PCA串行算法(Breeze PCA，BPCA)和Spark1.3.0本身提供的PCA算法(Spark’s PCA，SPCA，該算法沒有進(jìn)行數(shù)據(jù)的標(biāo)準(zhǔn)化處理)一并進(jìn)行試驗對比. 在分配核數(shù)為q的時候，算法SPCA的時間消耗為(p2n/q)Ti+O(p2)Tc+(p3)Tc+k.由于p遠(yuǎn)小于n，所以其加速比為：

(8)

DELL服務(wù)器配置如下：

4 Cores

Inte(R) Core(TM) i7-4770

RAM: 16 G

OS: win8, 64bit

frequency: 3.4 GhZ

Dise size: 250 GB

Shared memory:2 559 MB

SNPCA、BPCA、SPCA算法在上述仿真實驗環(huán)境下的運(yùn)行時間對比如圖3所示.

圖3 SNPCA等3種算法的運(yùn)行時間對比Fig.3 Time consumption of the three Algorithms

4.1.2 SNPCA算法與SPCA算法內(nèi)存消耗量比較

一般地，分析某一程序在Spark運(yùn)行環(huán)境下的空間消耗是比較困難的，因為程序的運(yùn)行受分布式集群的運(yùn)行環(huán)境、資源共享、JVM GC效率、SWAP分區(qū)等因素的影響. 通常Spark集群中Driver所在的節(jié)點會具有較高的系統(tǒng)性能，而SNPCA算法在Driver端程序運(yùn)行的空間復(fù)雜度是一個多項式，下面將針對SNPCA算法在Spark集群的單個計算節(jié)點上的內(nèi)存消耗進(jìn)行試驗，并與SPCA算法進(jìn)行比較. 可以通過獲取在操作系統(tǒng)上運(yùn)行產(chǎn)生的RES (resident memory usage)與SHR (shared memory) 之差的平均值來計算SNPCA算法所消耗的內(nèi)存. 仿真數(shù)據(jù)為200維、條數(shù)依次為 [1,2,3,4,5,6,7,8,9,10] 萬條的10個數(shù)據(jù)集，大小依次為 [11.9, 23.7, 35.9, 47.7, 59.7, 71.4, 83.4, 95.1, 108.1, 119.2, 131.1] MB. 在Spark運(yùn)行環(huán)境下，SPCA算法和SNPCA算法在處理不同大小數(shù)據(jù)集時單個計算節(jié)點上所消耗的內(nèi)存量對比情況如圖4所示.

圖4 SPCA算法和SNPCA算法在集群的單個工作節(jié)點上內(nèi)存消耗量對比Fig.4 Memory consumption comparison between SPCA and SNPCA on single worker node

4.2 仿真實驗結(jié)果及分析

在仿真實驗中，BPCA算法是串行算法，SPCA算法是Spark提供的沒有進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化的PCA算法.從圖3我們發(fā)現(xiàn)，Spark 1.3.0提供的SPCA算法符合公式(8)的加速比，且基于Spark編程模型的SNPCA算法隨著核數(shù)的增加也實現(xiàn)了快速處理的目的.算法BPCA對多核表現(xiàn)并不敏感，因為它本身就是一個串行算法. 另外，可以看出SNPCA算法的性能介于BPCA算法和SPCA算法之間，SNPCA算法的性能通常比BPCA算法好，除非在單核的時候，因為Spark的分布式機(jī)制決定了即使在單核的時候仍然對數(shù)據(jù)進(jìn)行了分區(qū)，在不同分區(qū)上的迭代運(yùn)算產(chǎn)生不可避免的交互運(yùn)算、各個分區(qū)與資源管理器等的通信引起時間消耗. 總體來看，我們?nèi)匀豢梢酝茢喑?，SNPCA算法不僅實現(xiàn)了帶標(biāo)準(zhǔn)化的PCA功能，并且表現(xiàn)出不錯的算法性能，適用于大型數(shù)據(jù)集的PCA運(yùn)算.

從圖4容易看出，SNPCA算法在Spark集群的單個節(jié)點上的內(nèi)存消耗量要遠(yuǎn)大于SPCA算法，這是因為SNPCA算法涉及了幾個collect的操作，消耗了因分布式數(shù)據(jù)傳遞引起的大量內(nèi)存開銷，但是考慮到隨著數(shù)據(jù)量上升開銷幅度上升得不快，其算法仍在一定程度上提高了大數(shù)據(jù)下主成分分析的處理能力.

5 結(jié)論

提出了在Spark下具有數(shù)據(jù)標(biāo)準(zhǔn)化處理的SNPCA算法，通過“空間換時間”，實現(xiàn)了在時間上的節(jié)約，為Spark運(yùn)行環(huán)境下進(jìn)行大數(shù)據(jù)的PCA處理提供了解決途徑. 另外，如何繼續(xù)改進(jìn)算法使得在分布式RDD中直接進(jìn)行標(biāo)準(zhǔn)化處理(而不是通過collect機(jī)制)來進(jìn)一步提高效率，這一點還有待于進(jìn)一步研究.

[1] KARL P. On lines and planes of closest fit to systems of points in space[J]. Philosophical magazine, 1901, 2(6): 559-572.

[2] SEAN O, ROBIN A, TED D, et al. Mahout in action[M]. Vivgimia: Manning Publications, 2011.

[3] XIANGRUI M, JOSEPH B, BURAK Y, et al. Mllib: machine learning in apache spark[J]. JMLR, 2016, 17(34): 1-7.

[4] TAREK E, MAYSAM Y, ASHRAF A, et al. SPCA: scalable principal component analysis for big data on distributed platforms[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 2015: 79-91.

[5] SIDDHARTH MALHOTRA B. SPCA: scalable principle component analysis for big data[C]//Qatar Foundation Annual Research Conference. 2014 (1): ITSP0517.

[6] SPARK. APA CHE Spark[EB/OL].[2016-06-11]. http://spark.apache.org/.

[7] 蔡金收，陳鐵軍，郭麗.一種基于投票極限學(xué)習(xí)機(jī)的人臉識別混合算[J].鄭州大學(xué)學(xué)報(工學(xué)版), 2016, 37(2): 37-41.

[8] BENJAMIN H, ANDY K, MATEI Z, et al. Mesos: a platform for fine-grained resource sharing in the data center[C]. NSDI. 2011(11): 22-22.

[9] MICHAEL I, MIHAI B, YUAN Y, et al. Dryad: Distributed data-parallel programs from sequential building blocks[C]. ACM SIGOPS Operating Systems Review. ACM, 2007, 41(3): 59-72.

[10] TAREK E, MOHAMED H. Analysis of PCA algorithms in distributed environments[R]. Qatar foundation: Qatar computing research instistue, 2015.

[11] 江政，周勇.基于FPGA的電能質(zhì)量監(jiān)測裝置設(shè)計[J]. 鄭州大學(xué)學(xué)報(工學(xué)版), 2016, 37(2): 29-33.

[12] 王敏, 周樹道, 葉松. 基于小波變換方向信息的奇異值圖像去噪研究[J]. 鄭州大學(xué)學(xué)報(工學(xué)版), 2012, 33(3): 121-124.

[13] 馬立平. 現(xiàn)代統(tǒng)計分析方法的學(xué)與用(三)：統(tǒng)計數(shù)據(jù)標(biāo)準(zhǔn)化——無量綱化方法[J]. 北京統(tǒng)計，2000 (3): 34-35.

[14] CHAOSIMPLE.[EB/OL].[2016-04-19]. http://www.cnblogs.com/chaosimple/archive/2013/07/31/3227271.

[15] CARLOS O. Statistical model computation with UDFs[J]. Knowledge and data engineering, 2010, 22(12): 1752-1765.

[16] CARLOS O, NAVEEN M, CARLOS G-A, et al. Fast PCA computation in a DBMS with aggregate UDFs and LAPACK[C]. Proceedings of the 21st ACM international conference on Information and knowledge management. ACM, 2012: 2219-2223.

[17] GRAMIAN M. http://en.wikipedia.org/wiki/Gramian_matrix. Accessed July 2016

[18] CARLOS O, NAVEEN M, CARLOS G-A. PCA for large data sets with parallel data summarization[J]. Distributed and parallel databases, 2014, 32(3): 377-403.

[19] JAN J G. On the relationships between SVD, KLT and PCA[J]. Pattern recognition, 1981, 14(1): 375-381.

[20] JACK J D, IAIN S D, DANNY C S, et al. Numerical linear algebra for high-performance computers[M]. Siam, 1998.

Abstract: Principal Component Analysis (PCA) is a well known model for dimensionality reduction in data mining, it transforms the original variables into a few comprehensive indices. In this paper, we study the principle of PCA, the distributed architecture of Spark and PCA algorithm of distributed matrix from spark’s MLlib, then improved the design and present a new algorithm named SNPCA (Spark’s Normalized Principal Component Analysis), this SNPCA algorithm computes principal components together with data normalization process. We carried out benchmarking on multicore CPUs and the results demonstrate the effectiveness of SNPCA.

Keywords: PCA; Spark; distributed; normalization

NormalizedPCAAlgorithmBasedonSpark

DONG Jianhua1,2， WANG Guoyin1， YONG Xi3， SHI Xiaoyu1， LI Qingliang4

(1.Institute of Electronic Information & Technology, Chongqing Institutes of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing 400714, China; 2.University of Chinese Academy of Sciences, Beijing 100049, China;3.Water Information Center, Ministry of Water Resources, Beijing 100053, China;4.Xichang Satellite Launch Center, Wenchang 571300, China)

董建華(1987— )，男，中國科學(xué)院博士研究生，主要從事云計算技術(shù)、數(shù)據(jù)挖掘、人工智能等研究,E-mail:928991386@qq.com.

TU316.4

A

10.13705/j.issn.1671-6833.2017.05.001

2017-04-10；

2017-07-11

國家自然科學(xué)基金青年基金資助項目(61602434)；三峽庫區(qū)水生態(tài)環(huán)境感知系統(tǒng)及平臺業(yè)務(wù)化運(yùn)行(2014ZX07104-006)；重慶市基礎(chǔ)科學(xué)與前沿研究技術(shù)重點專項(cstc2015jcyjB0244)；中國科學(xué)院青年創(chuàng)新促進(jìn)會資助項目(No.2017393)

1671-6833(2017)05-0007-06