徐旸， 王佳斌， 彭凱

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

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

1 相關(guān)工作

1.1 主成分分析法

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

主成分分析法主要有以下3個(gè)計(jì)算步驟.

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

(1)

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

(2)

(3)

(4)

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

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

(5)

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

累積貢獻(xiàn)率δj為

δj=c1+c2+…+cj.

(6)

主成分分量的篩選標(biāo)準(zhǔn)為δj≥85%，可得主成分分量為

(7)

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

1.2 t-SNE算法

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

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

(8)

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

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

(9)

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

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

(10)

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

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

(11)

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

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

(12)

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

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

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

步驟：

步驟1點(diǎn)xu的方差σu使用二分查找進(jìn)行計(jì)算；

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

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

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

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

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

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

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

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

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

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

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

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

2.2 高維空間中點(diǎn)的相似性的K-NN圖表示

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

，

(13)

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

為測(cè)試文中算法的性能，從運(yùn)行效率、加速比、擴(kuò)展比、可視化效果和精確度5個(gè)方面進(jìn)行分析.

3.1 實(shí)驗(yàn)環(huán)境

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

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

3.2 運(yùn)行效率

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

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

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

3.3 加速比和擴(kuò)展比

加速比(S)和擴(kuò)展比(E)是衡量算法并行化的指標(biāo).并行化性能的優(yōu)劣由單個(gè)節(jié)點(diǎn)運(yùn)行的時(shí)間與多個(gè)節(jié)點(diǎn)并行的時(shí)間的比值進(jìn)行量化，并行化性能與加速比成正比.加速比的計(jì)算公式為

(14)

式(14)中：t1為算法單個(gè)節(jié)點(diǎn)運(yùn)行的時(shí)間；tw為算法多個(gè)節(jié)點(diǎn)并行的時(shí)間.

擴(kuò)展比是加速比和節(jié)點(diǎn)數(shù)的比值，其計(jì)算公式為

E=S/w.

(15)

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

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

3.4 可視化效果和精確度

對(duì)高維數(shù)據(jù)集進(jìn)行降維處理，最終將其可視化于二維空間，點(diǎn)的顏色對(duì)應(yīng)不同的對(duì)象類(lèi)別.通過(guò)準(zhǔn)確率、召回率和相對(duì)準(zhǔn)確率衡量算法的精確度.

準(zhǔn)確率ξP和召回率ξR的計(jì)算公式分別為

(16)

(17)

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

由此可得精確度的評(píng)價(jià)指標(biāo)相對(duì)準(zhǔn)確率ξF為

(18)

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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