結(jié)合PCA的t-SNE算法的并行化實現(xiàn)方法

徐旸， 王佳斌， 彭凱

(華僑大學 工學院， 福建 泉州 362021)

大數(shù)據(jù)可視化是大數(shù)據(jù)研究領(lǐng)域的核心內(nèi)容之一[1]，其中，高維數(shù)據(jù)可視化尤為關(guān)鍵，降維可視化方法[2]是高維數(shù)據(jù)可視化的一種重要技術(shù)，它將高維數(shù)據(jù)轉(zhuǎn)換為二維或三維的低維數(shù)據(jù)，并可視化于散點圖中[3].數(shù)據(jù)降維[4]的目標是在低維空間映射數(shù)據(jù)內(nèi)部結(jié)構(gòu)，并充分地保留原來高維數(shù)據(jù)的重要信息.梁京章等[5]提出核主成分分析(KPCA)法，通過核函數(shù)的作用，將數(shù)據(jù)映射至高于現(xiàn)存的維度中，再通過線性降維的手段進行處理. Roweis等[6]提出的局部線性嵌入(LLE)和Tenenbaum等[7]提出的等距離特征映射(ISOMAP)是流行學習中的代表算法，這兩種算法在高維空間中觀察數(shù)據(jù)的最潛層特征后，根據(jù)兩個維度空間的映射關(guān)系，將數(shù)據(jù)的主要特征關(guān)系映射于低維空間.Maaten等[8]提出基于t分布的隨機近鄰嵌入(t-SNE)算法，通過高維空間和低維空間中的條件概率關(guān)系，采用長尾t分布實現(xiàn)降維效果.基于此，本文提出一種結(jié)合主成分分析(PCA)的t-SNE算法的并行化實現(xiàn)方法.

1 相關(guān)工作

1.1 主成分分析法

主成分分析法的目的是在盡可能減小原始信息損失的同時壓縮、簡化數(shù)據(jù)，去除冗余的噪聲數(shù)據(jù).主成分分析法提取數(shù)據(jù)的主要特征，將原有數(shù)據(jù)重構(gòu)為新的相互無關(guān)的綜合變量集，新變量集的數(shù)據(jù)量小于等于原數(shù)據(jù)量.主成分分析法能夠有效地展示各變量的映射關(guān)系和內(nèi)部結(jié)構(gòu).

主成分分析法主要有以下3個計算步驟.

1) 建立初始關(guān)系數(shù)據(jù)矩陣X，有

(1)

2) 標準化初始關(guān)系數(shù)據(jù)矩陣元素為

(2)

(3)

(4)

使用奇異值分解(SVD)法求解相關(guān)系數(shù)矩陣R的特征值(λ1，λ2，…，λm)和相應的特征向量αj，αj=(αj，1，αj，2，…，αj，m)，j=1，2，…，m.

3) 選擇重要的主成分分量.方差貢獻率cj為

(5)

式(5)中：λj為第j個主成分分量的特征值.

累積貢獻率δj為

δj=c1+c2+…+cj.

(6)

主成分分量的篩選標準為δj≥85%，可得主成分分量為

(7)

式(7)中：x1，x2，…，xm為標準化后的矩陣向量元素.

1.2 t-SNE算法

t-SNE算法是對稱隨機近鄰嵌入(SNE)算法的改進[9-10]，t-SNE算法利用條件概率分布替換傳統(tǒng)的距離表示，映射數(shù)據(jù)點在高維和低維空間之間的距離相似關(guān)系，在更好地維持初始數(shù)據(jù)結(jié)構(gòu)的前提下，展示其內(nèi)部的聚類特點.t-SNE算法有以下5點計算思想.

1) 在高維空間中，高斯分布pv|u表示點xv，xu互為鄰近點的概率.當xv與xu之間的距離越近，pv|u越大；當xv與xu之間的距離越遠，pv|u越小.pv|u為

(8)

式(8)中：定義pu|u=0；σu為高斯分布的方差；xk為高維數(shù)據(jù).

2) 在對稱SNE中，高維空間中的離群點xu與其他數(shù)據(jù)點xv的距離都很遠，則xu的聯(lián)合概率分布pu，v均較小.pu，v為

(9)

式(9)中：s為數(shù)據(jù)點的總數(shù).

3) 同理，在低維空間中，用t分布定義數(shù)據(jù)點之間的關(guān)系，則xu的低維表示形式y(tǒng)u的聯(lián)合概率分布qu，v為

(10)

式(10)中：yv，yk，yl分別為數(shù)據(jù)點xv，xk，xl的低維表示形式；t分布的自由度設為1.

4) 利用相對熵(KL)距離可得代價函數(shù)C，有

(11)

式(11)中：P，Q分別為高維空間和低維空間中所有數(shù)據(jù)點的聯(lián)合概率分布.

5) 使用梯度下降法進行優(yōu)化，有

(12)

t-SNE算法的具體執(zhí)行步驟如下.

輸入：s個D維的向量χ={x1，x2，…，xs}映射到二維或三維空間，定值困惑度為Prep，迭代次數(shù)為T，學習率為η，momentum項系數(shù)為β(t)

輸出：低維數(shù)據(jù)y={y1，y2…，ys}

步驟：

步驟1點xu的方差σu使用二分查找進行計算；

步驟2通過式(8)，(9)計算成對數(shù)據(jù)點的pv|u和pu，v；

步驟3初始化低維數(shù)據(jù)y1，y2，…，ys；

步驟4通過式(10)計算低維數(shù)據(jù)的qu，v；

步驟7重復步驟4～6，完成初始設置的迭代次數(shù)T.

2 結(jié)合PCA的t-SNE算法及其并行化實現(xiàn)

隨著數(shù)據(jù)體量和數(shù)據(jù)維數(shù)的增長，t-SNE算法使用梯度下降法進行反復迭代，計算低維空間中數(shù)據(jù)點的分布情況，此時，產(chǎn)生的中間結(jié)果快速增多，內(nèi)存壓力逐漸變大，當內(nèi)存不足時，只能將結(jié)果存儲在磁盤中，這將大幅降低算法的效率.

由于Spark平臺[11-13]是開源的通用分布式內(nèi)存計算框架，通過驅(qū)動主節(jié)點程序?qū)崿F(xiàn)任務的分發(fā)、調(diào)度執(zhí)行和聚合結(jié)果，可解決內(nèi)存壓力過大導致的算法效率低下問題.

2.1 結(jié)合PCA法的數(shù)據(jù)并行化預處理

由于原始數(shù)據(jù)的維度較高，數(shù)據(jù)特征值過多，計算數(shù)據(jù)點之間成對距離的時間復雜度很高，導致算法的整體運行時間增加.而主成分分析法由于輕量化，收斂速度快，能夠快速地找到噪聲點，在盡可能減少數(shù)據(jù)損失的情況下壓縮和簡化數(shù)據(jù)，節(jié)約內(nèi)存，從而減少可視化結(jié)果受噪聲點的干擾，去除冗余信息[14].因此，在數(shù)據(jù)預處理階段使用Spark平臺的Mllib機器學習庫[15]中的分布式主成分分析法減少數(shù)據(jù)維度，既不會嚴重扭曲數(shù)據(jù)點之間的距離，又可以去除噪聲數(shù)據(jù).

首先，數(shù)據(jù)被分塊存儲于不同的分區(qū)上，對矩陣A(RowMatrix類型)的格拉姆矩陣進行求解，矩陣中行和列的提取由Map回調(diào)函數(shù)執(zhí)行，再發(fā)送給各執(zhí)行節(jié)點，其結(jié)果由Reduce回調(diào)函數(shù)獲得；然后，使用SVD法求解協(xié)方差矩陣W[16]，再用特征值、特征向量生成主成分分量；最后，完成的數(shù)據(jù)再重新分發(fā)并保存到分布式文件系統(tǒng)中.

數(shù)據(jù)預處理流程圖，如表1所示.

圖1 數(shù)據(jù)預處理流程圖Fig.1 Data preprocessing flow chart

2.2 高維空間中點的相似性的K-NN圖表示

K最鄰近(K-NN)圖是基于K-NN算法構(gòu)造的多節(jié)點關(guān)系圖[17].對于空間中的s個節(jié)點，找出與任一節(jié)點xs距離最小的K個鄰居x1，x2，…，xK，這里的距離度量方式可以自行設定，找到鄰居節(jié)點后，將其與xs進行連接.空間中其他節(jié)點同理，由此可得K-NN圖.

，

(13)

由此大幅降低了計算量.文中構(gòu)建K-NN圖的算法是制高點(VP)樹方法，時間復雜度為O(UNlgN).

2.3 多節(jié)點并行執(zhí)行t-SNE算法

實現(xiàn)Spark平臺的連接和訪問，任務控制節(jié)點Driver Program創(chuàng)建SparkConf和Spark Context對象，再對分布式文件系統(tǒng)(HDFS)上預處理完成的數(shù)據(jù)創(chuàng)建彈性分布式數(shù)據(jù)集(RDD)，并分發(fā)至每個工作節(jié)點，讀取分區(qū)中的數(shù)據(jù)集，并有序選擇數(shù)據(jù)點xu，xv作為起始點，生成RDD1，通過Map回調(diào)函數(shù)計算pu，v，生成RDD2，觸發(fā)Cache緩存算子，通過Map回調(diào)函數(shù)計算低維分布qu，v，生成RDD3.進入Combline階段，優(yōu)化成本函數(shù)，更新qu，v，生成RDD4，判斷是否繼續(xù)迭代.達到預先設定的迭代次數(shù)后，RDD4啟動ReduceByKey算子，將所有結(jié)果匯聚到同一分塊，輸出最終的低維空間中所有數(shù)據(jù)點的矩陣Z，完成降維目標.在這些執(zhí)行步驟中，各工作節(jié)點的中間結(jié)果保存在內(nèi)存中，完成后的數(shù)據(jù)集中到任務控制節(jié)點，觸發(fā)SaveAsTextFile算子，并將最終結(jié)果寫入HDFS.

并行執(zhí)行算法流程圖，如圖2所示.

圖2 并行執(zhí)行算法流程圖Fig.2 Parallel execution algorithm flow chart

在進行并行計算時[18]，Spark平臺將RDD分發(fā)到不同的工作節(jié)點上，觸發(fā)緩存機制可以在內(nèi)存中實現(xiàn)RDD顯式持久化，使中間數(shù)據(jù)重復使用，并將結(jié)果緩存到內(nèi)存中；在計算低維空間中的數(shù)據(jù)分布時，存儲在內(nèi)存中的數(shù)據(jù)發(fā)揮作用，減少了讀取時間，加快迭代過程.因此，對于需要反復迭代計算的算法，內(nèi)存計算可有效地優(yōu)化時間成本.在Spark平臺中，各任務共同使用廣播發(fā)送變量，變量在每個計算節(jié)點上運行和備份，減少了各數(shù)據(jù)在傳輸過程中的消耗，提升了算法的效率.

3 實驗結(jié)果與分析

為測試文中算法的性能，從運行效率、加速比、擴展比、可視化效果和精確度5個方面進行分析.

3.1 實驗環(huán)境

基于Vmware虛擬平臺，搭建Spark平臺集群環(huán)境.創(chuàng)建3臺虛擬機，其中，1臺虛擬機為主要節(jié)點，其他兩臺虛擬機為從節(jié)點.每個節(jié)點CPU信息為Intel○RCoreTMi7-9750，運行內(nèi)存為2 GB，硬盤讀寫速度為1 TB·s-1，集群操作系統(tǒng)為Centos7，Hadoop軟件版本為2.8.3，Spark平臺的版本為2.3.0.t-SNE算法的單機實驗環(huán)境如下：CPU信息為Intel○RCoreTMi7-9750，運行內(nèi)存為16 GB，硬盤數(shù)據(jù)讀寫速度為1 TB·s-1.

實驗采用的數(shù)據(jù)集為BREAST CANCER，MNIST和CIFAR-10[19-20].根據(jù)數(shù)量級，將MNIST數(shù)據(jù)集分為訓練集和測試集，其中，測試樣本10 000個，訓練樣本60 000個，每個樣本均為1個784維度的高維數(shù)據(jù).

3.2 運行效率

將MNIST數(shù)據(jù)集分別運行于單機環(huán)境和Spark平臺，通過處理時間(tc)衡量文中算法的運行效率.不同數(shù)量級的數(shù)據(jù)集在單機環(huán)境和Spark平臺的運行效率對比，如圖3所示.圖3中：w為節(jié)點數(shù).

圖3 單機環(huán)境和Spark平臺的運行效率對比Fig.3 Comparison of operational efficiency between stand-alone environment and spark platform

由圖3可知：當使用同一數(shù)據(jù)集在集群中進行實驗時，在Spark平臺中單個節(jié)點的運行效率遠高于單機下的運行效率；數(shù)據(jù)的處理時間隨著集群中的節(jié)點數(shù)的增加而減少，表明算法的執(zhí)行速度隨著節(jié)點數(shù)的增加而提高，同時，大規(guī)模數(shù)據(jù)集的處理速度隨集群中節(jié)點數(shù)的增加而提高.

3.3 加速比和擴展比

加速比(S)和擴展比(E)是衡量算法并行化的指標.并行化性能的優(yōu)劣由單個節(jié)點運行的時間與多個節(jié)點并行的時間的比值進行量化，并行化性能與加速比成正比.加速比的計算公式為

(14)

式(14)中：t1為算法單個節(jié)點運行的時間；tw為算法多個節(jié)點并行的時間.

擴展比是加速比和節(jié)點數(shù)的比值，其計算公式為

E=S/w.

(15)

文中算法在MNIST數(shù)據(jù)集的加速比和擴展比，如圖4，5所示.由圖4，5可知：在Spark平臺中，隨著參與計算節(jié)點的增多，加速比隨之逐漸增大，擴展比隨之逐漸減小；隨著數(shù)據(jù)集的增大，加速比的增長隨之變快，而擴展比隨之趨于平穩(wěn)，算法的并行化的優(yōu)勢也愈發(fā)明顯.

圖4 文中算法在MNIST數(shù)據(jù)集的加速比 圖5 文中算法在MNIST數(shù)據(jù)集的擴展比 Fig.4 Speedup ratio of proposed algorithm in MNIST data set Fig.5 Expansion ratio of proposed algorithm in MNIST data set

3.4 可視化效果和精確度

對高維數(shù)據(jù)集進行降維處理，最終將其可視化于二維空間，點的顏色對應不同的對象類別.通過準確率、召回率和相對準確率衡量算法的精確度.

準確率ξP和召回率ξR的計算公式分別為

(16)

(17)

式(16)，(17)中：Ng，h為屬于g類，但被劃歸到h類中的數(shù)據(jù)數(shù)量；Ng為g類中的全部數(shù)據(jù)數(shù)量；Nh為h類中的全部數(shù)據(jù)數(shù)量.

由此可得精確度的評價指標相對準確率ξF為

(18)

為了驗證文中算法的可視化效果和精確度，采用t-SNE算法(單機環(huán)境)，基于Spark平臺的t-SNE算法(和文中算法環(huán)境相同)、文中算法在BREAST CANCER，MNIST和CIFAR-10數(shù)據(jù)集上進行實驗，其可視化效果對比，如圖6～8所示.圖6～8中：Ex，Ey分別表示原始數(shù)據(jù)的兩個特征值.

(a) t-SNE算法 (b) 基于Spark平臺的t-SNE算法 (c) 文中算法圖6 3種算法在BREAST CANCER數(shù)據(jù)集上的可視化效果對比Fig.6 Comparison of visualization effects of three algorithms in BREAST CANCER data set

(a) t-SNE算法 (b) 基于Spark平臺的t-SNE算法 (c) 文中算法圖7 3種算法在MNIST數(shù)據(jù)集上的可視化效果對比Fig.7 Comparison of visualization effects of three algorithms in MNIST data set

(a) t-SNE算法 (b) 基于Spark平臺的t-SNE算法 (c) 文中算法 圖8 3種算法在CIFAR-10數(shù)據(jù)集上的可視化效果對比Fig.8 Comparison of visualization effects of three algorithms in CIFAR-10 data set

由圖6～8可知：原始BREAST CANCER數(shù)據(jù)集是30維的向量，有效映射到二維散點圖被分為2類；原始MNIST數(shù)據(jù)集是784維的向量，有效映射到二維散點圖被分為10類；原始CIFAR-10數(shù)據(jù)集是1 024維的向量，有效映射到二維散點圖被分為10類.

不同數(shù)據(jù)集的精確度對比，如表1所示.

表1 不同數(shù)據(jù)集的精確度對比Tab.1 Accuracy comparison of different data sets

由以上分析可知：文中算法在降維后的可視化效果、準確率、召回率和相對準確率均明顯優(yōu)于其他兩種算法.

4 結(jié)束語

提出一種結(jié)合PCA的t-SNE算法的并行化方法.在MNIST數(shù)據(jù)集中，對文中算法進行實驗，驗證了文中算法在大規(guī)模數(shù)據(jù)集中可以在提高運行效率和精確度的前提下，高效地完成降維可視化.然而，降維會使數(shù)據(jù)被映射到低維空間時產(chǎn)生錯誤位置，導致其附近信息的丟失，原始高維空間中一些特征未能得到較好的保留.此外，通過保留數(shù)據(jù)的周圍信息，將數(shù)據(jù)從高維空間映射至低維空間，并未考慮全局數(shù)據(jù)之間的關(guān)系.雖然文中算法能夠在Spark平臺下對大規(guī)模數(shù)據(jù)集進行處理，但由于文中算法是將低維數(shù)據(jù)作為變量進行迭代，一旦更新數(shù)據(jù)，需要重新啟動算法，因此，在靈活性和開銷方面仍有不足，今后將針對該問題開展相關(guān)研究.