基于Spark 和三路交互信息的并行深度森林算法

毛伊敏，周展，陳志剛

（1.江西理工大學(xué)信息工程學(xué)院，江西 贛州 341000；2.韶關(guān)學(xué)院信息工程學(xué)院，廣東 韶關(guān) 512026；3.中南大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410083）

0 引言

深度森林是Zhou 等[1]提出的一種基于決策樹(shù)結(jié)構(gòu)的深度學(xué)習(xí)模型，其包含多粒度掃描和級(jí)聯(lián)森林兩大組成部分，因其超參數(shù)少、參數(shù)敏感度低及模型深度自適應(yīng)等優(yōu)點(diǎn)，已被廣泛應(yīng)用于網(wǎng)絡(luò)流量分類[2]、文本分類[3]、故障診斷[4]、目標(biāo)識(shí)別[5]、惡意代碼分類[6]等領(lǐng)域。然而，隨著新一代信息技術(shù)的革新和大數(shù)據(jù)時(shí)代的來(lái)臨，各領(lǐng)域?qū)a(chǎn)生亟待處理的海量數(shù)據(jù)，這些數(shù)據(jù)通常表現(xiàn)出數(shù)據(jù)量大、數(shù)據(jù)價(jià)值密度低等特性，深度森林難以有效處理這類數(shù)據(jù)，因此如何設(shè)計(jì)出適合處理大數(shù)據(jù)問(wèn)題的深度森林算法已成為一大研究熱點(diǎn)。

Spark[7]作為專門處理大規(guī)模數(shù)據(jù)問(wèn)題開(kāi)發(fā)的并行計(jì)算框架，因其出色的計(jì)算能力和良好的通用性，被廣泛應(yīng)用于企業(yè)項(xiàng)目開(kāi)發(fā)和學(xué)術(shù)研究中。文獻(xiàn)[8]提出了用于退網(wǎng)用戶預(yù)測(cè)的并行深度森林（PDF-OGUP,parallel deep forest for off-grid user prediction）算法，為節(jié)省多粒度掃描階段的空間占用，設(shè)計(jì)了基于下標(biāo)的掃描算法，并以隨機(jī)采樣構(gòu)建隨機(jī)森林的方式減少所需內(nèi)存空間。針對(duì)網(wǎng)絡(luò)入侵問(wèn)題，文獻(xiàn)[9]設(shè)計(jì)了基于特征分割和深度并行隨機(jī)森林（FS-DPRF,feature segmentation and deep structure of parallelized random forest）檢測(cè)模型，提出了RDD（resilient distributed datasets）層次替換策略解決了RDD 重用問(wèn)題，提高了作業(yè)效率。為進(jìn)一步提高并行深度森林算法的計(jì)算能力，文獻(xiàn)[10]結(jié)合Spark 框架設(shè)計(jì)了一種全新的并行深度森林BLB-gcForest（bag of little bootstraps-gcForest）算法。首先，該算法使用BLB（bag of little bootstrap）自助采樣法替換傳統(tǒng)采樣法，減少了大量特征在級(jí)聯(lián)森林各層級(jí)中的傳輸，提高了計(jì)算效率和通信效率；其次，提出自適應(yīng)子森林劃分算法，以確保每個(gè)子森林并行計(jì)算的資源利用率最大化；最后，利用輪詢機(jī)制來(lái)實(shí)現(xiàn)節(jié)點(diǎn)的負(fù)載均衡。以上列舉的3 種并行深度森林算法雖然在訓(xùn)練效率上有了一定的提升，但仍然存在以下不足。1) 在特征選擇階段，無(wú)法有效去除原始數(shù)據(jù)攜帶的大量冗余和無(wú)關(guān)特征，導(dǎo)致后續(xù)模型訓(xùn)練過(guò)程中存在冗余及無(wú)關(guān)特征問(wèn)題。2) 在多粒度掃描階段，輸入的原始特征經(jīng)過(guò)滑動(dòng)窗口掃描后，將產(chǎn)生大量的特征子序列，拼接多個(gè)輸出的類向量將導(dǎo)致類向量過(guò)長(zhǎng)問(wèn)題。3) 在級(jí)聯(lián)森林訓(xùn)練階段，級(jí)聯(lián)森林的每一層都將拼接原始特征和上層特征作為本層輸入，但相對(duì)于原始特征的維度，每層轉(zhuǎn)化后的增廣特征的維度則要小得多，這將導(dǎo)致增廣特征被淹沒(méi)[11]，使模型收斂速度緩慢。4) 在模型并行化訓(xùn)練階段，子森林的劃分粒度不能依據(jù)模型訓(xùn)練效果自適應(yīng)確定，加之異構(gòu)節(jié)點(diǎn)情況下存在中間數(shù)據(jù)傾斜，將導(dǎo)致模型并行訓(xùn)練效率低下。

針對(duì)上述問(wèn)題，本文提出了基于Spark 和三路交互信息的并行深度森林（PDF-STWII,parallel deep forest algorithm based on spark and three-way interactive information）算法，其主要工作如下。

1) 提出基于特征交互的特征選擇（FSFI,feature selection based on feature interaction）策略，通過(guò)消除原始特征中存在的大量冗余及無(wú)關(guān)特征，解決了冗余及無(wú)關(guān)特征過(guò)多的問(wèn)題。

2) 提出多粒度向量消除（MGVE,multi-granularity vector elimination）策略，通過(guò)將多粒度掃描產(chǎn)生的任意2 個(gè)相似類向量融合為一個(gè)向量，解決了多粒度掃描過(guò)程中產(chǎn)生的類向量過(guò)長(zhǎng)問(wèn)題。

3) 提出了級(jí)聯(lián)森林增強(qiáng)（CFFE,cascade forest feature enhancement）策略，密集連接所有級(jí)聯(lián)層輸出的增廣特征的同時(shí)動(dòng)態(tài)縮減部分原始特征，解決了模型收斂速度慢的問(wèn)題。

4) 提出了多級(jí)負(fù)載均衡（MBL,multi-level load balancing）策略，通過(guò)自適應(yīng)子森林劃分（ASFS,adaptive sub-forest splitting）算法控制森林劃分粒度和異構(gòu)傾斜數(shù)據(jù)劃分（HSDP,heterogeneous skew data partition）算法平衡異構(gòu)數(shù)據(jù)的傾斜，提高了模型的并行化訓(xùn)練效率。

1 相關(guān)概念介紹

定義1互信息[12]常用來(lái)衡量變量之間的相關(guān)性程度，互信息越大，變量間的相關(guān)性越強(qiáng)，反之，則相關(guān)性越弱。反映隨機(jī)變量fi和fj相關(guān)性的互信息I(fi;fj)可定義為

其中，H(fi)為變量fi的信息熵，表示變量不確定性程度；H(fi|fj)為變量fj確定時(shí)fi的條件熵I(fi;fj) ＜min{H(fi),(fj)}。

定義2對(duì)稱不確定性[13]常用于相關(guān)特征選取，其通過(guò)歸一化互信息修正了互信息在選取特征時(shí)存在的偏置。2 個(gè)隨機(jī)變量fi和fj的對(duì)稱不確定性SU(fi,fj)可定義為

從式(2)可知，SU(fi,fj)∈[0,1]。

定義3三路交互信息[14]作為互信息的擴(kuò)展可用來(lái)度量特征之間的交互性，其值可為正數(shù)、零和負(fù)數(shù)。當(dāng)三路交互信息為正數(shù)時(shí)，2 個(gè)特征共同對(duì)標(biāo)簽提供的信息大于它們單獨(dú)對(duì)標(biāo)簽提供信息的和，此時(shí)2 個(gè)特征存在互補(bǔ)性；當(dāng)三路交互信息為負(fù)數(shù)時(shí)，2 個(gè)特征對(duì)標(biāo)簽提供的信息存在冗余；當(dāng)三路交互信息為零時(shí)，2 個(gè)特征提供給標(biāo)簽的信息是獨(dú)立的。對(duì)于特征fi和fj及標(biāo)簽C，三路交互信息I(fi;fj;C)可表示為

其中，p(fi)p(fj)p(C)為三者的聯(lián)合概率。

定義4近似馬爾可夫毯[15]可用于冗余特征的檢驗(yàn)，如果特征fj是特征fi的近似馬爾可夫毯，則2 個(gè)特征之間存在冗余，SU(fj,C) ≥SU(fi,C)和SU(fj,fi) ≥SU(fi,C)同時(shí)成立。

定義5皮爾遜相關(guān)系數(shù)常用來(lái)衡量2 個(gè)向量之間的相似程度，取值范圍為[-1,1]，其絕對(duì)值越大，相關(guān)性越強(qiáng)。當(dāng)取值為正時(shí)，2 個(gè)向量呈正相關(guān)，當(dāng)取值為負(fù)時(shí)，2 個(gè)向量呈負(fù)相關(guān)；當(dāng)取值為零時(shí)，2 個(gè)向量無(wú)關(guān)。皮爾遜相關(guān)系數(shù)定義為

其中，cov(X,Y)表示2 個(gè)向量之間的協(xié)方差，σX和σY分別表示向量X和向量Y的標(biāo)準(zhǔn)差，μ表示向量均值，E 表示數(shù)學(xué)期望值。

2 PDF-STWII 算法說(shuō)明

PDF-STWII 算法主要包括4 個(gè)階段：特征選擇、多粒度掃描、級(jí)聯(lián)森林訓(xùn)練、模型并行化訓(xùn)練。各階段的主要任務(wù)如下。

1) 特征選擇。提出FSFI 策略，通過(guò)度量特征的相關(guān)性和冗余度，消除大量冗余及無(wú)關(guān)特征，同時(shí)挖掘出存在交互作用的特征，過(guò)濾大量冗余及無(wú)關(guān)特征。

2) 多粒度掃描。提出MGVE 策略，融合任意2 個(gè)相似類向量，縮短類向量長(zhǎng)度。

3) 級(jí)聯(lián)森林訓(xùn)練。提出CFFE 策略，密集連接各層增廣特征，同時(shí)逐層削減部分特征，防止增廣特征被淹沒(méi)，加快模型收斂速度。

4) 模型并行化訓(xùn)練。提出了MBL 策略，其包含兩方面內(nèi)容。在算法并行處理層面，提出ASFS算法，通過(guò)分析子森林訓(xùn)練效果，自適應(yīng)確定森林的劃分粒度，提高算法并行度。在數(shù)據(jù)并行化處理方面，提出了HSDP 算法，分析分布式異構(gòu)環(huán)境中各計(jì)算節(jié)點(diǎn)的性能差異，將中間數(shù)據(jù)合理分配到各節(jié)點(diǎn)，以平衡中間數(shù)據(jù)傾斜，最終從算法和數(shù)據(jù)兩方面提高模型并行化訓(xùn)練效率。

2.1 特征選擇

針對(duì)原始數(shù)據(jù)集包含大量冗余及無(wú)關(guān)特征問(wèn)題，提出的FSFI 策略從特征相關(guān)性、冗余度和特征交互三方面綜合考慮特征選取，高效剔除冗余無(wú)關(guān)特征。FSFI 包括無(wú)關(guān)特征過(guò)濾、冗余特征消除和特征綜合評(píng)分。

2.1.1無(wú)關(guān)特征過(guò)濾

在特征選擇過(guò)程中，由于相對(duì)于特征的冗余度和交互性計(jì)算，特征的相關(guān)性計(jì)算更快，所以在特征選擇的初始階段，提出特征相關(guān)性系數(shù)（FRC）過(guò)濾大量無(wú)關(guān)特征，刪除小于相關(guān)性閾值的特征，并利用FRC 對(duì)特征排序。

定理1特征相關(guān)性系數(shù)（FRC）。已知數(shù)據(jù)集D∈Rn×m，其中n和m分別為數(shù)據(jù)的樣本量和特征，則fi與標(biāo)簽C的相關(guān)性系數(shù)FRCi定義為

其中，fsi表示樣本s中fi的值。

證明對(duì)標(biāo)簽具有較強(qiáng)區(qū)分度的特征，通常存在較大的方差，可用標(biāo)準(zhǔn)差反映特征fi對(duì)類別的區(qū)分能力。D為特征fi的標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差越大，特征區(qū)分標(biāo)簽類別的能力越強(qiáng)；由互信息定義可知I(fi;C) ＜min{H(fi),H(C)}，互信息的大小受特征和標(biāo)簽信息熵的限制，直接使用互信息來(lái)衡量相關(guān)性時(shí)，具有越大信息熵的特征越有可能被選取，因此將互信息I(fi;C)除以特征fi和標(biāo)簽C的最小信息熵以消除偏置，最終將反映特征區(qū)分度的標(biāo)準(zhǔn)差和消除偏置的互信息相乘獲得特征相關(guān)性系數(shù)FRC，證畢。

2.1.2冗余特征消除

經(jīng)過(guò)無(wú)關(guān)特征初步過(guò)濾過(guò)程，特征的維度大幅縮減，但冗余特征并未消除，為此，在特征消除階段提出冗余度指標(biāo)R來(lái)衡量特征之間的冗余程度。冗余消除過(guò)程如下。首先，利用近似馬爾可夫毯快速判斷冗余特征并消除；然后，利用冗余度指標(biāo)R計(jì)算特征間的冗余度，對(duì)比冗余度指標(biāo)和冗余度閾值，進(jìn)一步消除冗余特征。

定理2冗余度指標(biāo)R。已知存在特征fi和特征fj，則計(jì)算特征間的冗余度指標(biāo)R可表示為

證明SU(fi,C)為特征fi與標(biāo)簽C的對(duì)稱不確定性，根據(jù)對(duì)稱不確定性定義可知，SU(fi,C)可度量特征fi與標(biāo)簽C的相關(guān)信息量，同理，SU(fi,fj)可度量2 個(gè)特征之間的相關(guān)信息量，反映特征信息重疊大小。H(fi)為fi的信息熵，表示特征自身信息量的大小。當(dāng)越大時(shí)，在一個(gè)確定信息空間中的特征fi和特征fj的信息重疊概率也就越大，即越可能存在信息冗余。綜上，P可表示冗余概率，SU(fi,fj)可表示冗余信息量，冗余概率和冗余信息量聯(lián)立獲得冗余度指標(biāo)R，證畢。

2.1.3特征綜合評(píng)分

經(jīng)過(guò)無(wú)關(guān)特征過(guò)濾和冗余特征消除過(guò)程，剩余的特征都具有較高質(zhì)量，為了進(jìn)一步挖掘出更高質(zhì)量的特征子集，從特征相關(guān)性、冗余度和特征交互性出發(fā)，設(shè)計(jì)特征綜合評(píng)估函數(shù)JFSFI，獲取更優(yōu)特征子集。

定理3特征綜合評(píng)估函數(shù)JFSFI。假設(shè)候選特征fi與標(biāo)簽C的相關(guān)性為I(fi;C)，與已選特征fj的冗余度為I(fi;fj)，候選特征fi和已選特征fj對(duì)標(biāo)簽的交互性為I(fi;fj;C)，特征綜合評(píng)估函數(shù)JFSFI可表示為

其中，F(xiàn)′表示候選特征集，F(xiàn)s表示已選特征集。

綜上，特征評(píng)估函數(shù)JFSFI在選擇特征時(shí)能夠有效挖掘出高相關(guān)性、低冗余度且具有交互作用的候選特征，證畢。

FSFI 的偽代碼如算法1 所示。

算法1FSFI

2.2 多粒度掃描

多粒度掃描[16]利用多種尺寸的滑動(dòng)窗口對(duì)原始特征進(jìn)行切片，隨后將切片得到的多個(gè)窗口尺寸大小的特征子序列傳入隨機(jī)森林中進(jìn)行訓(xùn)練，最后將訓(xùn)練得到的類向量拼接傳入級(jí)聯(lián)森林中訓(xùn)練。然而由于滑動(dòng)窗口掃描得到的特征子序列存在大量相同特征，訓(xùn)練得到的大量類向量也相似，拼接大量相似類向量將使傳入級(jí)聯(lián)森林的類向量過(guò)長(zhǎng)，增加級(jí)聯(lián)森林訓(xùn)練開(kāi)銷。

針對(duì)多粒度掃描過(guò)程中產(chǎn)生的類向量過(guò)長(zhǎng)問(wèn)題，本節(jié)設(shè)計(jì)了MGVE 策略將相似類向量融合。其具體過(guò)程如圖1 所示。

圖1 MGVE 過(guò)程

定理4相似類向量判定函數(shù)S(P(A,B),δ)。已知在多粒度掃描階段隨機(jī)森林輸出類向量A和B，則2 個(gè)向量的相似性判定表示為

其中，P(A,B)為向量A和B的皮爾遜相關(guān)系數(shù)，δ為設(shè)定的相似度閾值。當(dāng)P(A,B)＞δ時(shí)，S(P(A,B),δ)=1表明2 個(gè)向量相似，反之不相似。

證明由于P(A,B)能直接反映2 個(gè)向量之間的線性相關(guān)程度，同時(shí)每個(gè)隨機(jī)森林輸出的類向量為各個(gè)類別的概率，這使每個(gè)向量的內(nèi)部概率值的和為1。當(dāng)用皮爾遜相關(guān)系數(shù)測(cè)得2 個(gè)向量相關(guān)性越大時(shí)，2 個(gè)向量方向越趨于一致，此時(shí)2 個(gè)向量?jī)?nèi)對(duì)應(yīng)的各數(shù)值就越接近，2 個(gè)向量相似度越高，因此用皮爾遜相關(guān)系數(shù)與設(shè)定的閾值δ相比可判定2 個(gè)向量是否相似，證畢。

MGVE 的偽代碼如算法2 所示。

算法2MGVE

2.3 級(jí)聯(lián)森林訓(xùn)練

針對(duì)級(jí)聯(lián)森林訓(xùn)練過(guò)程中模型收斂速度慢的問(wèn)題，本節(jié)提出了CFFE 策略，其主要過(guò)程如下。首先，密集連接每一層級(jí)聯(lián)森林產(chǎn)生的增廣特征；其次，為維持總的輸入特征的維度不變，每一層級(jí)聯(lián)森林訓(xùn)練后都根據(jù)訓(xùn)練效果給原始特征賦予不同的特征重要性權(quán)重w，去除部分權(quán)重低的特征。具體過(guò)程如圖2 所示。

圖2 CFFE 過(guò)程

定理5特征j重要性權(quán)重w(j)。假設(shè)表示特征j是級(jí)聯(lián)森林中第i個(gè)隨機(jī)森林RFi中的權(quán)重，m個(gè)隨機(jī)森林訓(xùn)練使用了特征j，則特征j在本層的重要性權(quán)重w(j)為

證明假設(shè)在構(gòu)建決策樹(shù)時(shí)，決策樹(shù)τ內(nèi)部的節(jié)點(diǎn)i被預(yù)測(cè)為類別c的概率為p(c)，則節(jié)點(diǎn)i的信息熵E(i)可表示為

特征j將節(jié)點(diǎn)i劃分為左右子節(jié)點(diǎn)，左右子節(jié)點(diǎn)的信息熵分別為El(i)和Er(i)，則節(jié)點(diǎn)i被j劃分的效果Q(i,j)可表示為

決策樹(shù)τ總共有N個(gè)節(jié)點(diǎn)，特征j在決策樹(shù)τ中的局部權(quán)重wτ(j)可表示為

為評(píng)估決策樹(shù)權(quán)重，使用袋外誤差δ作為評(píng)估標(biāo)準(zhǔn)。設(shè)決策樹(shù)τ的袋外誤差為δτ，則隨機(jī)森林中決策樹(shù)τ的歸一化權(quán)重γτ可表示為

通過(guò)式(14)和式(15)，獲得特征j在決策樹(shù)τ中的局部權(quán)重wτ(j)和決策樹(shù)權(quán)重γτ，則特征j在單個(gè)隨機(jī)森林RF 中的權(quán)重wRF(j)可表示為

證畢。

2.4 模型并行化訓(xùn)練

針對(duì)模型并行化訓(xùn)練效率低的問(wèn)題，本節(jié)提出了MLB 策略，從算法和數(shù)據(jù)2 個(gè)層面提升模型的并行化訓(xùn)練效率，包含算法層面的ASFS 算法和數(shù)據(jù)層面的HSDP 算法。

2.4.1自適應(yīng)子森林劃分

在算法層面，為提高模型的并行化訓(xùn)練效率，本節(jié)提出了ASFS 算法，其主要過(guò)程為如下。首先，采用自助采樣法將采樣特征分配到子森林中；然后，根據(jù)各個(gè)子森林的訓(xùn)練結(jié)果給每個(gè)子森林設(shè)定子森林權(quán)重系數(shù)WSF；最后，利用子森林的權(quán)重WSF計(jì)算出整個(gè)森林劃分得分因子 scoreF以確定森林劃分粒度。具體過(guò)程如圖3 所示。

圖3 子森林劃分

定理6子森林權(quán)重系數(shù)WSF(r)。設(shè)第r個(gè)子森林中包含Q個(gè)決策樹(shù)，利用OOB 數(shù)據(jù)集驗(yàn)證獲得第i個(gè)決策樹(shù)的袋外誤差errOOBi，則第r個(gè)子森林的權(quán)重系數(shù)WSF(r)可表示為

定理7 森林劃分得分因子 scoreF(s)。將第s個(gè)森林劃分為r個(gè)子森林，則第s個(gè)森林的森林劃分得分因子為

證明為第i個(gè)子森林的平均預(yù)測(cè)準(zhǔn)確率，準(zhǔn)確率越高，子森林整體的分類能力越強(qiáng)。WSF(i)為子森林權(quán)重系數(shù)，權(quán)重越大，子森林的穩(wěn)定性越強(qiáng)、準(zhǔn)確率越高，一個(gè)森林包含多個(gè)子森林，每個(gè)子森林的預(yù)測(cè)效果又包含準(zhǔn)確率和穩(wěn)定性兩方面特性，因此結(jié)合兩方面特性的 scoreF(s)可表示子森林的整體預(yù)測(cè)效果，證畢。

ASFS 的偽代碼如算法3 所示。

算法3ASFS

輸入級(jí)聯(lián)層數(shù)T，每層森林?jǐn)?shù)S，預(yù)設(shè)最大子森林?jǐn)?shù)R，子森林中樹(shù)的數(shù)量Q

輸出子森林劃分矩陣P[][]

2.4.2異構(gòu)傾斜數(shù)據(jù)劃分

在數(shù)據(jù)層面，由于Spark 在Shuffle 階段采用默認(rèn)的哈希分區(qū)策略極易引起中間數(shù)據(jù)傾斜，嚴(yán)重影響模型的并行化訓(xùn)練效率，為此本文提出HSDP 算法。平衡中間數(shù)據(jù)傾斜需進(jìn)行如下操作。

1) 傾斜評(píng)估。Spark 以哈希分區(qū)作為默認(rèn)的分區(qū)方式將產(chǎn)生2 種數(shù)據(jù)傾斜情況：同一鍵值包含大量鍵值對(duì)，經(jīng)過(guò)Shuffle 過(guò)程被分配到同一分區(qū)，導(dǎo)致這一分區(qū)數(shù)據(jù)量巨大；大量不同鍵值對(duì)應(yīng)同一分區(qū)索引，導(dǎo)致大量不同鍵對(duì)應(yīng)的鍵值對(duì)分配到同一分區(qū)。以上2 種數(shù)據(jù)傾斜情況在節(jié)點(diǎn)異構(gòu)環(huán)境下將更加嚴(yán)重，對(duì)此，本文提出異構(gòu)傾斜度量因子D來(lái)評(píng)估在節(jié)點(diǎn)異構(gòu)條件下中間數(shù)據(jù)的傾斜程度。

定理8異構(gòu)傾斜度量因子D。假設(shè)中間數(shù)據(jù)包含m個(gè)不同的key，且第i個(gè)key 對(duì)應(yīng)的數(shù)據(jù)容量為Qi，N個(gè)桶對(duì)應(yīng)N個(gè)計(jì)算節(jié)點(diǎn)，第j個(gè)桶包含的key 表示為 {K1,j,K2,j,…,Km,j}，每個(gè)桶的數(shù)據(jù)量依次表示為q1,…,qj,…,qN,qavg為所有桶的平均數(shù)據(jù)量，則異構(gòu)傾斜度量因子D可表示為

其中，RCj表示第j個(gè)計(jì)算節(jié)點(diǎn)的相對(duì)計(jì)算能力。

證明由于qavg和avg_capability 是實(shí)際環(huán)境中的固定值，于是可設(shè)定系數(shù)α表示兩者的比例，即qavg=αa vg_capability。qj-αc apabilityj為第j個(gè)桶的理論最大負(fù)載和實(shí)際負(fù)載的差值，D′為實(shí)際負(fù)載和理論負(fù)載的標(biāo)準(zhǔn)差，實(shí)際負(fù)載和理論負(fù)載越接近，異構(gòu)傾斜度量因子D越小，因此可用D作為異構(gòu)傾斜度量因子來(lái)衡量中間數(shù)據(jù)傾斜程度，證畢。

2) 中間數(shù)據(jù)預(yù)測(cè)。為降低數(shù)據(jù)統(tǒng)計(jì)耗時(shí)，采用主從整體采樣法預(yù)測(cè)中間數(shù)據(jù)。首先，從節(jié)點(diǎn)通過(guò)RDD操作計(jì)算所有Map 任務(wù)的mapPartitionsRddSize ；然后，設(shè)置采樣率r，通過(guò)sampleSize=rmapPartionsRddSize 計(jì)算總共的采樣大小，根據(jù)sampleSizePerPartion 計(jì)算每個(gè)Map任務(wù)采樣的樣本大小；其次，每個(gè)從節(jié)點(diǎn)利用sampleSizePartion 的大小調(diào)用RDD 的sample 函數(shù)對(duì)RDD 數(shù)據(jù)分區(qū)進(jìn)行采樣，統(tǒng)計(jì)出本地樣本中key 值記錄，隨后將(Ki,Qi)傳輸?shù)街鞴?jié)點(diǎn)；最后，主節(jié)點(diǎn)匯總每個(gè)Map 任務(wù)的所有樣本數(shù)量，根據(jù)采樣率得到中間數(shù)據(jù)集{(K1,Q1),(K2,Q2),…,(Km,Qm)}的整體分布情況。

3) 異構(gòu)傾斜數(shù)據(jù)劃分。通過(guò)整體采樣方法獲得中間數(shù)據(jù)的預(yù)測(cè)，根據(jù)節(jié)點(diǎn)的異構(gòu)情況采用貪心策略將中間數(shù)據(jù)合理分配到各個(gè)桶中。

HSDP 的偽代碼如算法4 所示。

算法4HSDP

2.5 算法時(shí)間復(fù)雜度分析

PDF-OGUP、FS-DPRF 和BLB-gcForest 等算法都基于Spark 框架設(shè)計(jì)，且各自采用不同的優(yōu)化策略提高算法性能，因此選取這3 種算法與本文算法進(jìn)行實(shí)驗(yàn)對(duì)比。

PDF-STWII 算法主要包括特征選擇、多粒度掃描、級(jí)聯(lián)森林訓(xùn)練、級(jí)聯(lián)森林并行化訓(xùn)練。各階段的時(shí)間復(fù)雜度分別標(biāo)記為T1、T2、T3、T4。

特征選擇包括無(wú)關(guān)特征過(guò)濾、冗余特征消除、特征綜合評(píng)分。已知數(shù)據(jù)樣本量為n，特征數(shù)目為m，無(wú)關(guān)特征過(guò)濾遍歷所有樣本和特征，其時(shí)間復(fù)雜化度為O(nm) ；冗余特征消除需要計(jì)算近似馬爾可夫毯和三路交互信息，需要的時(shí)間復(fù)雜度為O(m2)；特征綜合評(píng)分階段需要的時(shí)間復(fù)雜度為O(m2n)，因此特征選擇時(shí)間T1為

在多粒度掃描階段，時(shí)間復(fù)雜度主要取決于特征子集在隨機(jī)森林訓(xùn)練以及類向量融合的時(shí)間開(kāi)銷。假設(shè)經(jīng)過(guò)特征選擇后的特征個(gè)數(shù)為s，滑動(dòng)窗口大小為w，樣本數(shù)目為n，隨機(jī)森林的個(gè)數(shù)為N,則T2為

其中，O(s-w)為窗口掃描時(shí)間復(fù)雜度，O(s(s-w)nN)為特征子集訓(xùn)練時(shí)間復(fù)雜度，O(N2)為類向量融合的時(shí)間復(fù)雜度。

在級(jí)聯(lián)森林訓(xùn)練階段，假設(shè)傳入級(jí)聯(lián)森林的原始特征的個(gè)數(shù)為v，樣本數(shù)目為n，每一層森林的個(gè)數(shù)為N，每個(gè)森林包含Q棵樹(shù),級(jí)聯(lián)森林層數(shù)為L(zhǎng)，則T3為

在模型并行化訓(xùn)練階段中，時(shí)間復(fù)雜度主要由子森林劃分、異構(gòu)數(shù)據(jù)分區(qū)兩部分組成。假設(shè)每一層森林的個(gè)數(shù)為N，每個(gè)森林包含Q棵樹(shù)，級(jí)聯(lián)森林的層數(shù)為L(zhǎng)，每個(gè)森林可劃分為r子森林，并行節(jié)點(diǎn)數(shù)量同樣為r，則T4為

其中，O(NLQ)為自適應(yīng)子森林劃分的時(shí)間復(fù)雜度，O(r2)為異構(gòu)數(shù)據(jù)分區(qū)的時(shí)間復(fù)雜度。

綜上，PDF-STWII 算法的時(shí)間復(fù)雜度為

其中，r為單個(gè)森林劃分的子森林個(gè)數(shù)。

在大數(shù)據(jù)環(huán)境下，深度森林模型訓(xùn)練的時(shí)間復(fù)雜度主要取決于多粒度掃描階段中輸出的類向量長(zhǎng)度和級(jí)聯(lián)森林訓(xùn)練層數(shù)，即算法的時(shí)間復(fù)雜度T主要由T3中的v和L決定。由于算法PDF-OGUP、FS-DPRF 和BLB-gcForest 都沒(méi)在多粒度掃描階段對(duì)相似類向量進(jìn)行融合，從而使vPFG-OGUP＞vPDF-STWII，vFS-DPRF＞vPDF-STWII，vBLB-gcForest＞vPDF-STWII。又由于本文在級(jí)聯(lián)森林中使用了CFFE 策略加快了模型收斂，因此需要的訓(xùn)練層數(shù)相對(duì)更少，從而使LPFG-OGUP＞LPDF-STWII，LFS-DPRF＞LPDF-STWII，LBLB-gcForest＞LPDF-STWII。綜上，相較于PDF-OGUP、FS-DPRF 和BLB-gcForest 算法，PDF-STWII 算法具有更低的時(shí)間復(fù)雜度。

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

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

為驗(yàn)證本文算法的性能表現(xiàn)，本文設(shè)計(jì)了相關(guān)實(shí)驗(yàn)。在硬件方面，本文實(shí)驗(yàn)設(shè)置8 個(gè)計(jì)算節(jié)點(diǎn)，其中包括1 個(gè)主節(jié)點(diǎn)和7 個(gè)從節(jié)點(diǎn)。各個(gè)計(jì)算節(jié)點(diǎn)的硬件配置均為Intel(R) Core(TM) i7-11800H CPU、16 GB DDR4 RAM、1 TB SSD，實(shí)驗(yàn)中的計(jì)算節(jié)點(diǎn)處于同一局域網(wǎng)內(nèi)，通過(guò)1 GB/s 的以太網(wǎng)相連。在軟件方面，各計(jì)算節(jié)點(diǎn)配置均為Ubuntu16.04、Hadoop 2.7.4、JDK 1.8.0。各節(jié)點(diǎn)的詳細(xì)配置如表1 所示。

表1 節(jié)點(diǎn)詳細(xì)配置

3.2 實(shí)驗(yàn)數(shù)據(jù)與設(shè)置

實(shí)驗(yàn)數(shù)據(jù)。所有算法采用4個(gè)來(lái)自UC（Iuniversity of California Irvine）公共數(shù)據(jù)庫(kù)的數(shù)據(jù)集，分別為Farm Ads、Susy、Connect-4 和FMA，其中Farm Ads是從12 個(gè)網(wǎng)站文本中搜集的各種有關(guān)農(nóng)場(chǎng)動(dòng)物的話題；Susy 是記錄粒子在加速器條件下是否產(chǎn)生超對(duì)稱粒子信號(hào)過(guò)程的數(shù)據(jù)集；Connect-4 數(shù)據(jù)集記錄了四子棋游戲中所有合法的8 層位置信息；FMA 記錄了包括歌曲標(biāo)題、專輯、藝術(shù)家等眾多曲目信息。各數(shù)據(jù)集的詳細(xì)信息如表2 所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)設(shè)置。對(duì)于實(shí)驗(yàn)數(shù)據(jù)劃分，采用所有算法數(shù)據(jù)劃分一致性原則，即70%為訓(xùn)練集，30%為測(cè)試集；對(duì)于模型參數(shù)，設(shè)數(shù)據(jù)的特征長(zhǎng)度為d，在多粒度掃描階段中滑動(dòng)窗口大小依次設(shè)置為每個(gè)子森林中的決策樹(shù)的數(shù)量初始化為隨機(jī)森林中決策樹(shù)數(shù)量的開(kāi)方，每一層級(jí)聯(lián)森林包含2 個(gè)隨機(jī)森林和2 個(gè)完全隨機(jī)森林。

3.3 評(píng)價(jià)指標(biāo)

3.3.1加速比

加速比是指同一任務(wù)在單處理器系統(tǒng)和在并行處理器系統(tǒng)中運(yùn)行消耗的時(shí)間的比率，常用來(lái)衡量并行系統(tǒng)或程序并行化的性能和效果，加速比越大，算法的并行化程度越高，其定義如下

其中，Ts表示在串行系統(tǒng)中的執(zhí)行時(shí)間，TP表示在并行系統(tǒng)中的執(zhí)行時(shí)間。

3.3.2準(zhǔn)確率

準(zhǔn)確率（Accuracy）是指在分類模型中正確分類的樣本數(shù)與總的樣本數(shù)的比值，能夠反映算法的分類能力，其定義為

其中，TP、TN、FP、FN 在混淆矩陣中分別表示真正例、真反例、假正例、假反例。

3.4 算法性能的比較分析

算法整體性能需考慮多方面指標(biāo)，為綜合衡量算法性能，利用算法運(yùn)行時(shí)間來(lái)度量算法訓(xùn)練速度，利用加速比來(lái)度量算法并行處理能力，利用準(zhǔn)確率來(lái)度量算法分類性能。

3.4.1算法運(yùn)行時(shí)間對(duì)比分析

為檢驗(yàn)4 種算法訓(xùn)練速度，將PDF-OGUP、FS-DPRF、BLB-gcForest 與本文算法（PDF-STWII）在上述4 個(gè)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，森林中決策樹(shù)數(shù)量為200，實(shí)驗(yàn)采用10 折交叉驗(yàn)證方式，實(shí)驗(yàn)結(jié)果如圖4 所示。

圖4 不同數(shù)據(jù)集上4 種算法的運(yùn)行時(shí)間

從圖4 中可知，在對(duì)4 個(gè)數(shù)據(jù)集的測(cè)試中，本文算法所需要的運(yùn)行時(shí)間最低，并且當(dāng)數(shù)據(jù)集的特征數(shù)量越多時(shí)，本文算法相對(duì)其他算法縮短的運(yùn)行時(shí)間比例也越大，在特征量最少的數(shù)據(jù)集Susy 中，本文算法相比PDF-OGUP、FS-DPRF、BLB-gcForest運(yùn)行時(shí)間分別減少了2.62%、10.41%、3.41%；在特征量最多的數(shù)據(jù)集Farm Ads 中，PDF-STWII 算法相比PDF-OGUP、FS-DPRF、BLB-gcForest 運(yùn)行時(shí)間分別減少了13.8%、19.12%、10.76%。產(chǎn)生以上結(jié)果的主要原因如下。1) 本文算法設(shè)計(jì)了FSFI策略，消除了大量冗余及無(wú)關(guān)的特征，在不影響分類精度的前提下極大地減少了后續(xù)多粒度掃描和級(jí)聯(lián)森林訓(xùn)練過(guò)程中輸入的特征量，加快了模型的訓(xùn)練速度；2) 本文算法設(shè)計(jì)了MGVE 策略，通過(guò)將2 個(gè)相似的類向量融合為一個(gè)類向量，減少了級(jí)聯(lián)森林訓(xùn)練過(guò)程中的特征維度，進(jìn)而減少級(jí)聯(lián)森林的訓(xùn)練開(kāi)銷。實(shí)驗(yàn)結(jié)果表明，PDF-FSIF 算法在處理高維大數(shù)據(jù)問(wèn)題時(shí)具有良好性能。

3.4.2加速比對(duì)比分析

為驗(yàn)證本文算法的并行計(jì)算能力，本文利用上述的4 個(gè)數(shù)據(jù)集分別對(duì)PDF-OGUP、FS-DPRF、BLB-gcForest 和本文算法在不同計(jì)算節(jié)點(diǎn)下進(jìn)行算法加速比實(shí)驗(yàn)，實(shí)驗(yàn)采用10 折交叉驗(yàn)證方式進(jìn)行，森林中決策樹(shù)數(shù)量設(shè)置為200，實(shí)驗(yàn)結(jié)果如圖5 所示。

圖5 不同數(shù)據(jù)集上4 種算法的加速比

從圖5 可知，各算法的加速比均隨著計(jì)算節(jié)點(diǎn)數(shù)量的增加而呈現(xiàn)不同程度的上升。當(dāng)節(jié)點(diǎn)個(gè)數(shù)為8 時(shí)，本文算法的加速比高于對(duì)比算法，在特征量最少的數(shù)據(jù)集Farms Ads 中，本文算法的加速比分別比PDF-OGUP、FS-DPRF、BLB-gcForest 高0.32、0.52、0.18；在特征量最大的數(shù)據(jù)集Susy 中，本文算法的加速比分別高0.88、1.18、0.465；本文算法取得最高加速比的原因在于設(shè)計(jì)了MLB 策略，從算法結(jié)構(gòu)劃分和中間數(shù)據(jù)合理分配2 個(gè)層面的同時(shí)提高了模型的并行化訓(xùn)練效率，從而使算法在處理數(shù)據(jù)時(shí)具有更高的加速比。實(shí)驗(yàn)結(jié)果表明，PDF-STWII 算法在處理大數(shù)據(jù)問(wèn)題時(shí)，具有較高加速比。

3.4.3準(zhǔn)確率對(duì)比分析

為驗(yàn)證本文算法的分類性能，實(shí)驗(yàn)選取準(zhǔn)確率作為評(píng)估指標(biāo)，將本文算法與對(duì)比的PDF-OGUP、FS-DPRF和BLB-gcForest 算法在4 個(gè)數(shù)據(jù)集上進(jìn)行10 折交叉驗(yàn)證實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖6 所示。

圖6 不同數(shù)據(jù)集上4 種算法的分類精確度

從圖6 中可知，隨著決策樹(shù)數(shù)量的增加，4 種算法模型的分類準(zhǔn)確率都有一定的提升，其主要原因在于隨著決策樹(shù)數(shù)量的增加，算法的泛化能力得到了增強(qiáng)，準(zhǔn)確率隨之提高。實(shí)驗(yàn)發(fā)現(xiàn)本文算法具有更高的準(zhǔn)確率，當(dāng)森林中決策樹(shù)數(shù)量為200 時(shí)，本文算法在 4 個(gè)數(shù)據(jù)集上的平均準(zhǔn)確率相比PDF-OGUP、FS-DPRF 和BLB-gcForest 分別提高了1.24%、1.43%、0.96%，產(chǎn)生以上結(jié)果的原因如下。1) 本文算法設(shè)計(jì)了 FSFI 策略，消除大量冗余和無(wú)關(guān)特征，同時(shí)挖掘出具有交互作用的特征，提高了算法分類準(zhǔn)確率；2) 本文算法設(shè)計(jì)了CFFE 策略，密集連接增廣特征，充分利用每一層級(jí)聯(lián)森林的分類貢獻(xiàn)，提高了模型的預(yù)測(cè)能力。實(shí)驗(yàn)結(jié)果表明，本文算法在大數(shù)據(jù)環(huán)境下具有優(yōu)良的分類性能。

3.5 消融實(shí)驗(yàn)

為驗(yàn)證算法各策略的有效性和對(duì)算法模型的貢獻(xiàn)，選取準(zhǔn)確率和加速比作為評(píng)價(jià)指標(biāo)，在上述4 個(gè)數(shù)據(jù)集上設(shè)計(jì)消融實(shí)驗(yàn)，實(shí)驗(yàn)采用8 個(gè)計(jì)算節(jié)點(diǎn)，森林中決策樹(shù)數(shù)量為200，實(shí)驗(yàn)結(jié)果由10 折交叉驗(yàn)證獲得，實(shí)驗(yàn)結(jié)果如表3 所示。

表3 消融實(shí)驗(yàn)結(jié)果

從表3 可知，各策略對(duì)加速比和準(zhǔn)確率具有不同影響，其中，MBL 策略對(duì)算法加速比提升最明顯，其次分別是FSFI、MGVE 和CFFE，在處理4 類數(shù)據(jù)集時(shí)，相比無(wú)任何策略，使用了MBL、FSFI、MGVE 和CFFE 策略可將算法的平均加速比分別提升19.04%、5.56%、3.64%和1.98%。產(chǎn)生以上結(jié)果的原因如下。1) MBL 策略對(duì)森林自適應(yīng)劃分和平衡中間數(shù)據(jù)傾斜，能有效提高模型并行計(jì)算能力；2) FSFI 策略消除了原始特征中大量冗余無(wú)關(guān)特征，從而提高各計(jì)算節(jié)點(diǎn)的訓(xùn)練效率；3) MGVE策略融合相似類向量，降低子森林訓(xùn)練開(kāi)銷，因此能一定程度提高加速比；4) CFFE 策略在級(jí)聯(lián)森林訓(xùn)練過(guò)程中能夠逐層削減少量特征，因此對(duì)加速比也有細(xì)微影響。

對(duì)算法準(zhǔn)確率提升最大的是 CFFE 策略和FSFI 策略，其次是MGVE 策略和MBL 策略，在處理4 個(gè)數(shù)據(jù)集時(shí)，使用CFFE、FSFI、MGVE和MBL 策略相比無(wú)任何策略，分別可將算法的平均準(zhǔn)確率提升1.98%、1.94%、0.45%和0.21%。產(chǎn)生以上結(jié)果的原因如下。1) CFFE 策略密集連接各層增廣特征，利用了每層森林的預(yù)測(cè)貢獻(xiàn)；2) FSFI策略消除了冗余無(wú)關(guān)特征并挖掘特征之間的交互信息；3) MGVE 策略將相似類向量融合對(duì)特征進(jìn)行了轉(zhuǎn)化，因此對(duì)準(zhǔn)確率的提升有一定影響；4) MBL 策略主要?jiǎng)澐稚纸Y(jié)構(gòu)和平衡中間數(shù)據(jù)傾斜，因此對(duì)準(zhǔn)確率影響不大。綜上，以上4 種策略能有效應(yīng)對(duì)大數(shù)據(jù)分類問(wèn)題，且能有效提高算法加速比和準(zhǔn)確率。

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

為解決深度森林算法在處理大數(shù)據(jù)存在的不足，本文提出了PDF-STWII 算法。首先，提出了FSFI 策略以消除原始特征中存在的大量冗余及無(wú)關(guān)特征；其次，提出了MGVE 策略，通過(guò)將相似的2 個(gè)類向量合并為一個(gè)類向量，解決了多粒度階段中產(chǎn)生的類向量過(guò)長(zhǎng)問(wèn)題；隨后，提出了CFFE策略，通過(guò)密集連接增廣特征，提高信息利用率，加快了模型收斂速度；最后，提出了MLB 策略，通過(guò)自適應(yīng)子森林劃分和異構(gòu)傾斜數(shù)據(jù)劃分，解決了模型并行化訓(xùn)練效率低的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，PDF-STWII 算法在處理大數(shù)據(jù)問(wèn)題時(shí)具有良好的并行化訓(xùn)練效率和分類性能。

雖然PDF-STWII 算法在并行化訓(xùn)練效率和分類精度上有了一定的提升，但仍存在以下不足：1)在多粒度向量消除策略中，利用求均值的方式將2 個(gè)向量融合為一個(gè)向量會(huì)丟失部分信息；2) 在大數(shù)據(jù)環(huán)境中，本文算法難以有效處理不平衡數(shù)據(jù)分類問(wèn)題。上述問(wèn)題將作為未來(lái)的重點(diǎn)研究對(duì)象。