結合信息論改進的并行深度森林算法

毛伊敏，耿俊豪，陳 亮

1.江西理工大學 信息工程學院，江西 贛州 341000

2.江西理工大學 應用科學學院，江西 贛州 341000

近年來，深度學習技術在充足的計算能力之下得到飛速的發展，它通過對大量數據的訓練，學習人類的認知與行為模式，從而部分或完全地取代人類重復機械的勞動[1]。如今，常見的深度學習算法都是基于深度神經網絡[2]的，作為一種監督式的學習算法，深度神經網絡能夠在訓練中通過逆向傳播來反饋計算誤差，具有自組織學習的特點。雖然，深度神經網絡因其強大的學習能力已被廣泛的應用于信用評估[3]、故障診斷[4]、自動駕駛[5]、金融[6]等領域，但模型的訓練卻需要大量數據做支撐，并且其學習性能嚴重依賴于對大量超參數的調整[7]。

針對深度神經網絡的現狀，Zhou等人[8]提出了一種新型的深度學習算法——深度森林gcForest（multigrained cascade forest），它是一種基于決策樹的多層分類器，主要由多粒度掃描和級聯森林兩部分構成。多粒度掃描層用來提取原始數據的特征，級聯森林用來不斷地精煉分類，每一層結構都是隨機森林和完全隨機森林的組合，通過接收前一層處理過的特征信息訓練該層模型，并將處理結果輸入至下一層，以此方式逐步提升模型的學習能力。深度森林的出現，為深度學習在深度神經網絡之外的方法打開了一扇門。

然而，隨著信息技術和網絡技術的發展使得大數據成為了研究熱點，相較于傳統數據，大數據具有了4V特性：volume（數量大）、variety（種類多）、velocity（速度快）、value（價值密度低）[9]，這使得深度森林算法在處理大數據時所需運行時間較長、內存容量較多，且僅通過提升計算機硬件水平來滿足人們對大數據分析與處理的需求，顯得尤為困難。此時并行化的計算思想顯得十分重要，因此，通過改進深度森林算法，并與分布式計算模型相結合成為當前研究的主要方向。

面對大數據規模龐大且計算復雜等問題，Google開發的MapReduce[10]并行編程模型由于其操作簡單、自動容錯、擴展性強等優點深受廣大學者和企業的青睞，同時，以Hadoop[11]、Spark[12]、Ray[13]為代表的分布式計算架構也受到了越來越多的關注[14]。目前基于并行化計算模型的深度森林算法已成功應用到大數據的分析與處理領域中。其中，Zhu等人[15]提出了一種基于Ray的并行化深度森林算法ForestLayer，該算法基于細粒度子森林優化了任務并行算法，提高了計算并發性，降低了通信開銷；同時，設計了一種統一任務分割機制，保證了訓練結果與原方法的一致性，降低了總訓練時間成本；此外，ForestLayer更進一步提出了延遲掃描、預池、部分傳輸三種系統級技術用于優化算法性能。從實驗結果可以看出，ForestLayer在運行時間以及準確度上都要優于傳統的深度森林算法。但是該算法依然存在以下不足：算法沒有考慮到大數據集中冗余與不相關特征過多及多粒度掃描不平衡的問題，且算法的并行化效率較低。

針對以上問題本文提出了大數據下基于信息論改進的并行深度森林算法——IPDFIT（improved parallel deep forest based on information theory）。首先，該算法基于信息論設計了一種混合降維策略DRIT（dimension reduction based on information theory）以獲得降維后的數據集，有效減少了冗余及不相關特征數；其次，提出了一種改進的多粒度掃描策略IMGSS（improved multi-grained scanning strategy）對樣本進行掃描，保證每個特征在掃描后以同頻率出現在數據子集中，避免了因多粒度掃描不平衡對深度森林模型的影響；最后，結合MapReduce框架，對深度森林模型每層級聯結構中的隨機森林進行并行化訓練，同時提出了一種樣本加權策略TSWS（the sample weighting strategy），根據級聯中隨機森林對樣本的評估，選取評估結果較差的樣本進入下一層訓練，減少了層級中樣本的數量，從而提高了算法的并行效率。實驗結果表明，該算法在大數據環境下，尤其是針對特征數較多的數據集有著更好的分類效果。

1 算法及相關概念介紹

1.1 相關概念介紹

定義1（信息增益）[16]已知離散變量X和其對應的類別Z，則信息增益IG(Z;X)由下式計算：

其中，H(Z)為關于類別Z的信息熵，H(Z|X)為關于變量X和類別Z的條件熵。

定義2（條件互信息）[17]已知離散變量X、Y以及它們對應的類別Z，則條件互信息I(X;Y|Z)由下式計算：

其中，H(Z|X)為關于變量X和類別Z的條件熵，H(X|Y,Z)為關于變量X、Y和類別Z的條件熵。

1.2 相關算法介紹

1.2.1 凝聚層次聚類

凝聚層次聚類[18]是一種以自底向上為策略的聚類算法，它首先將每個對象作為一個簇，并根據給定的簇間距離度量準則合并這些原子簇為越來越大的簇，直到所有的對象都在一個簇中，或者某個終結條件被滿足為止，構造和維護一棵由簇和子簇形成的聚類樹。

1.2.2 主成分分析算法

主成分分析算法（PCA）[19]是一種降維的多元統計方法，其主要目的是在保持最大變異條件下，尋找到一個轉換矩陣W，降低數據集的維度。PCA算法主要分為4個步驟：（1）建立數據矩陣，對原始數據集進行標準化處理；（2）建立相關系數矩陣并計算各主成分的特征值λ與對應的特征向量個數；（3）依據特征值和累計貢獻率，確定所需主成分的個數；（4）組合主成分對應的特征向量，得到轉換矩陣W對原數據降維。

2 IPDFIT算法

2.1 算法思想

IPDFIT算法主要包括三個階段：數據降維、多粒度掃描和并行構建級聯森林。

（1）在數據降維階段：提出DRIT策略，準確的識別和刪除數據集中的冗余和不相關特征，獲得降維后的數據集DB*。

（2）在多粒度掃描階段：提出IMGSS策略用于掃描降維后的數據集DB*，得到數據子集，經過兩個不同的隨機森林對數據子集分類后，將拼接得到的類向量集作為級聯森林的輸入樣本傳送到下一階段。

（3）在并行構建深度森林階段：提出TSWS策略用于評估每層級聯所用到的樣本，選取評估結果較差的樣本進入下一層訓練，以此逐步減少每層級聯上樣本的數目，并結合MapReduce框架實現深度森林模型的并行化訓練。

2.2 數據降維

目前，降維算法主要包括特征選擇和特征提取兩個方向，然而在大數據環境下，數據集中存在大量冗余與不相關特征，故單獨使用特征選擇或特征提取方法，都無法獲得較優的特征集合。針對這一問題，本文提出DRIT策略用于識別和過濾大數據環境下的冗余和不相關數據。該策略首先結合MapReduce模型，并行計算特征信息增益值，以此篩選并刪除不相關特征；接著，結合條件互信息提出特征相關性函數用于評估特征間的相似程度，在此基礎上，以凝聚層次聚類的方式聚類相似特征，并結合MapReduce框架與主成分分析算法并行的對每個簇中的特征進行降維。假設?n×d表示原始數據集DB的d維特征空間中的n個樣本，Y∈?n×1表示特征矩陣X所對應的標簽向量，則DRIT策略如下：

2.2.1 特征選擇

對于數據集DB，特征選擇的主要目的是減少不相關特征的數量。其具體過程為：首先，使用Hadoop中默認的數據塊策略，將原始數據集的特征空間劃分為大小相同的數據塊Block；接著，數據塊Block作為輸入數據，根據定義1，Mapper節點通過調用Map函數以鍵值對＜key,value＞的形式統計出每個特征的信息增益（key為特征名稱，value為對應特征的信息增益），組合每個鍵值對得到特征信息增益集合A={＜key1,value1＞,＜key2,value2＞…＜keyd,valued＞}；最后，根據特征對應的信息增益值對集合A中元素降序排列，移除集合A中排序較為靠后的特征，重新組合得到新的特征矩陣X′=[x1,x2,…,x m]∈?n×m(1≤m≤d)，并將處理后得到的特征矩陣X′與標簽向量Y按列合并后得到的數據集DB′傳入到下一階段。

特征選擇的流程圖如圖1所示。

圖1 特征選擇流程圖Fig.1 Flowchart of feature selection

特征選擇的執行過程如下所示：

算法1特征選擇

輸入：原數據集DB

輸出：特征矩陣X′、數據集DB′

1.For each featurexkinXdo//1≤k≤d

2.key k←feature name

3.valuek←information gain of featurex k//根據定義1計算特征信息增益

4.A←＜keyk,valuek＞//將特征xk對應的鍵值對＜key k,valuek＞放入集合A中

5.End for

6.Sorted(A)//將A按照value值遞減順序排序

7.Delete the later features in setA//刪除A中排列靠后元素

8.ReturnX′//此時X中所剩特征即為特征矩陣X′

9.DB′←CombineX′andYby column

10.Return DB′

2.2.2 特征提取

在特征提取階段，為進一步優化特征選擇后的數據集DB′，首先，提出了一種特征相關性函數用于評估數據集DB′中特征的相似度；其次，采用凝聚層次聚類的方式對評估后的特征進行聚類，將相似度較高的特征歸為相同簇；最后，結合MapReduce框架，并行對每個簇中的特征進行提取。特征提取的具體過程如下：

（1）特征相關性函數

該部分將基于條件互信息提出一種特征相關性函數對DB′中的特征進行相似度評估，具體定義如下：

定義3（特征相關性函數FC(x a,xb)）已知特征矩陣X′，x i和x j是X′中的特征，則根據定義2，對于X′中任意兩個不同特征x a、x b，特征相關性函數FC(x a,xb)可以表示為：

證明根據條件互信息的定義可知，I(x a;Y|x b)表示在特征xb的條件下特征x a與標簽Y之間的相關性，即xb的存在對xa與標簽Y之間相關性的影響程度；同理，I(xb;Y|xa)表示在特征x a的條件下特征x b與標簽Y之間的相關性，故利用兩者之和可以反映特征x a和x b的相似性，且為了簡化計算，利用特征矩陣X′中所有特征兩兩之間的條件互信息之和使FC(xa,x b)∈[0,1]。證畢。

（2）凝聚層次聚類

由定義3可知，函數FC(x a,x b)值越小，則代表特征x a與特征xb之間的相似程度越大；反之，函數FC(x a,xb)值越大，則代表特征xa與特征xb之間的相似程度越小。因此，根據凝聚層次聚類的定義，將相似特征聚集在相同簇中，得到C={C1,C2,…,C K}為聚類后返回的簇的集合。

（3）特征提取

對于簇集合C，為并行化提取每個簇中特征，算法再次調用MapReduce框架，根據框架中Mapper節點的個數均勻分配簇，對于每個簇，Mapper節點通過調用Map函數利用PCA算法對簇中特征進行提取，并以鍵值對＜key′,value′＞的形式返回簇的特征提取結果（key′為簇的標號，value′為簇中對應特征提取后的結果），待所有Mapper節點執行完畢后，通過解析每個節點中的鍵值對便可得到經特征提取后的特征矩陣X*=[x1,x2,…,x o]∈?n×o，并與標簽向量Y按合并后即可得到降維數據集DB*。

特征提取的流程圖如圖2所示。

圖2 特征提取流程圖Fig.2 Flowchart of feature extraction

特征提取的執行過程如下所示：

算法2特征提取

輸入：數據集DB′

輸出：特征矩陣X*、數據集DB*

1.For each featurex ainX′do//1≤a≤o

2.Calculating the correlation betweenx aand other features respectively byFC(x a,x b)

//通過FC(xa,xb)函數計算x a與其他特征的相關性

3.End for

4.Using hierarchical clustering to cluster features based on the similarity between features//對相似特征利用凝聚層次聚類的方式聚類

5.Get(C={C1,C2,…,C K})//得到聚類結果簇集合

6.Executing the MapReduce framework

7.For each clusterCiinCdo

8. Feature extraction by using PCA algorithm

9.key′←Ci

10.value′←The feature extraction result of the clusterCi

11.End for

12.Parsing each key-value pair

13.ReturnX*

14.DB*←CombineX*andYby column

15.Return DB*

2.3 多粒度掃描

目前，大數據環境下的并行深度森林算法中，數據子集是通過多粒度掃描數據集獲得的。雖然，多粒度掃描對于空間上有關聯的特征具有顯著效果，但對于在空間上無關聯的特征將可能丟失重要信息，這是因為對于在空間上無關聯的特征，靠近兩端的特征被掃到的次數較少，而靠近中心的特征被掃到的次數較多，故多粒度掃描在一定程度上降低了兩端特征的重要性。為了解決上述問題，本階段提出了一種改進的多粒度掃描策略IMGSS，該策略首先對降維后的數據做出了組合處理；接著，在規定了多粒度掃描的范圍的前提下，對拼接后的數據進行掃描產生數據子集，并對數據子集訓練、分類，將得到的分類結果拼接為類向量作為輸入樣本傳送至級聯森林。IMGSS策略的具體過程如下：

（1）數據組合

已知X*和DB*是經數據降維后得到的特征矩陣和數據集，針對數據集DB*中的任一數據樣本，作如下的數據組合處理，如圖3所示。

圖3 數據組合Fig.3 Data combination

①若數據為序列數據，則采用一段相同的數據與其首尾組合，獲得組合后的數據如圖3（a）所示。

②若數據為圖像數據，則采用三部分相同的數據在右、下以及對角處與其組合，獲得組合后的數據如圖3（b）所示。

（2）類向量集的獲取

根據上一步中得到的組合數據，該部分將采用多粒度掃描獲取數據子集，并利用數據子集訓練模型、預測分類，將得到的分類結果拼接獲得類向量。具體過程可分為以下四步，如圖4所示。

圖4 類向量的獲取Fig.4 Class vector acquisition

①多粒度掃描：對于拼接的序列數據而言，窗口掃描范圍為數據起始至數據[o+L-1]處結束，如圖4（a）所示；對于拼接的圖像數據而言，窗口掃描的范圍為數據模塊左上角[o+L-1]×[o+L-1]，如圖4（b）所示。根據設定范圍對拼接數據進行掃描得到數據子集。

②訓練模型：將得到的數據子集分別輸入到1個完全隨機森林和1個隨機森林中學習訓練。

③分類預測：根據建立的完全隨機森林和隨機森林模型對數據子集做出預測，假設所預測數據含有c個類別，則可得到2o(2o2)個長度為c的類向量α。

④類向量獲取：拼接所有長度為c的類向量α得到長度為2co(2co2)的類向量ωi，將所有類向量的集合ω其作為輸入樣本傳送至級聯森林。

多粒度掃描的流程圖如圖5所示。

圖5 多粒度掃描流程圖Fig.5 Flowchart of multi-grained scanning

多粒度掃描的執行過程如下所示：

算法3多粒度掃描

輸入：數據集DB*

輸出：類向量集ω

1.For each pieceofdata in DB*do

2. Combinatorial processing of data

3.End for

4.Specifying the range of multi-grained scanning//規定多粒度掃描的范圍

5.For eachcombineddatado

6. Multi-grained scanning

7. Output sub-data

8.End for

9. Training complete random forest and random forest using sub-data obtained by multi-grained scanning

10.Predicting the category of sub-data using the established model

11.Jointing the prediction results of the sub-data from the same original combined data to get the class vectorωi

12.ω←The set of all class vectorsωi

13.Returnω

2.4 并行構建級聯森林

在數據降維和多粒度掃描之后，需要根據多粒度掃描后得到的類向量集ω構建級聯森林，從而更進一步地精煉分類。目前，大數據環境下的并行構建級聯森林過程是通過類向量集并行訓練各個森林中的每棵子樹，并通過構建好的森林對每個樣本給出一個預測的類概率向量，將所有森林的類概率向量與樣本原始類向量拼接后作為下一級森林的輸入樣本，每級結束后，該級會對預測結果進行評估，以決定是否擴展下一級。然而，此類方法在每層級聯中的訓練時均使用了所有樣本進行，這種做法不僅降低了每層模型的訓練效率，而且不易針對預測準確率較低的樣本進行訓練。為了應對上述問題，本節首先提出了TSWS策略評估樣本，根據評估結果選取樣本進入下一級；然后結合MapReduce框架并行構建級聯森林。

（1）TSWS策略

給定一級聯森林，為了篩選出每級中預測準確率較低的樣本進入下一級訓練，提出樣本評分函數SF(ωi)，具體定義如下所示：

定義4（樣本評分函數SF(ωi)）已知樣本ωi對應的標簽為yi，設級聯森林共擴展了D級，則根據d(1＜d＜D)級中各個森林對樣本ωi預測出的類概率向量可以計算出樣本ωi在d級上預測準確度為ACCdωi，則樣本評分函數S F(ωi)可表示為：

證明由SF(ωi)的定義可知，該函數結合了樣本ωi在d級的預測準確度相對于d-1的預測準確度的提升率作為評分的依據，不僅反映了樣本ωi在d級上的預測準確度，而且SF(ωi)評分可作為推測樣本ωi在d+1級上準確度提升的依據。證畢。

根據樣本評分函數提出了樣本加權函數WR(ωi)，具體定義如下所示。

定義5（樣本加權函數WR(ωi)）已知樣本ωi的評分為SF(ωi)，在d i級上預測準確度為ACC dωi，且由級聯森林的定義可計算出d級上所有樣本的預測準確度為ACC d，則樣本加權函數WR(ωi)可表示為：

證明由SF(ωi)的定義可知，SF(ωi)可能為正可能為負，當S F(ωi)≤0時，可知在該級中ωi的準確度產生了負增長，且若該級樣本總體的準確度ACC d大于上一級ACCd-1，樣本ωi在該級的準確度ACC dωi大于該級樣本總體準確度ACC d，則說明樣本不適合進入下一級訓練，標記為1；否則，則代表樣本ωi訓練不足，標記為0。證畢。

根據定義5，對樣本進行加權，級聯森林在每級結束后對樣本進行遍歷，將權重為1的樣本輸出。

（2）并行構建級聯森林

通過TSWS策略對級聯森林中的樣本加權后，為了進一步加快級聯森林的構建效率，結合MapReduce模型，并行的對級聯森林的每一級進行構建，具體分為以下六步：

①調用Hadoop默認的數據塊策略，將數據集劃分成大小相同的數據塊Block，并將其作為輸入數據傳輸到Mapper節點中。

②每個Mapper節點對應訓練一個森林，調用Map函數通過K折交叉驗證的方式訓練森林中的各棵子樹，并以鍵值對＜keyT,valueT＞的形式返回構建好的子樹模型（keyT為子樹所在的森林編號，value T為該子樹模型），所有Mapper節點執行完畢，解析出同一Mapper節點下的所有子樹形成森林，所有森林的集合即為該級模型。

③利用Mapper節點中的子樹對樣本進行預測并形成新的鍵值對＜key″,value″＞（key″為樣本ID與森林編號的組合數組，value″為樣本的類概率向量）。

④將Mapper節點中預測得到的鍵值對由主節點分配后傳入相應的Reducer節點合并，得到每個森林對每個樣本的類概率向量。

⑤根據key″值查找相同ID樣本下不同森林的類概率向量求其平均值，并在此基礎上求解該級模型的準確度，根據TSWS策略篩選進入下一級訓練的樣本。

⑥將標記為0的樣本從每個森林得到的類概率向量與原始類向量拼接作為輸入樣本S傳送到下一級。

并行構建級聯森林的流程圖，如圖6所示。

圖6 并行構建級聯森林流程圖Fig.6 Flowchart of building cascade forest in parallel

至此并行構建級聯森林的執行過程如下所示：

算法4并行構建級聯森林

輸入：類向量集ω

輸出：該級級聯森林模型Model以及下一級輸入樣本S

（a）Map階段

1.For each Blockcorrespondingtoeach Mappernodedo

2. Trainthe tree model throughK-fold cross-validation//K折交叉驗證訓練樹模型

3.key T←The number of the forest where the tree model is located

4.value T←The model of the tree

5.End For

6.Forest Model←Collection of all tree model from the same Mapper//獲取森林模型

7.Model←Collection of all forest model//獲取該級級聯模型

8.Return model

9.For each tree model in each Mapper do

10. Predict the class probability of each sample//獲取樣本的類概率向量

11.key″←Combine sample ID with the number of the forest

12.value″←Class probability vector of the sample

13.End for

（b）Reduce階段

1.Sorted(＜key″,value″＞)//鍵值對＜key″,value″＞排序

2.Combine the values of the sameke y″to get the class probability vector of each forest for each sample//獲取森林的類概率向量

3.Marking samples according to TSWS strategy

4.S←Combining the class probability vector and the original class vector of the samples which marked as 0//獲取下一階段需要訓練的樣本

5.ReturnS

2.5 IPDFIT算法步驟

IPDFIT算法的具體實現步驟，如圖7所示。

圖7 IPDFIT算法總體示意圖Fig.7 Overall diagram of IPDFIT algorithm

步驟1通過Hadoop默認的數據塊策略，將原始數據集劃分成大小相同的數據塊Block，調用一次MapReduce任務并行計算原始數據特征的信息增益，在此基礎上對特征進行選擇。

步驟2調用特征相關性函數評估特征選擇后的數據集，采用凝聚層次聚類的方式將相似度高的特征聚為一簇，并結合MapReduce框架，并行提取每個簇中特征。

步驟3調用IMGSS策略對降維后的特征進行組合、多粒度掃描。

步驟4調用TSWS策略篩選樣本進入下一級訓練，并調用MapReduce框架并行訓練每一級森林模型。

2.6 算法時間復雜度分析

IPDFIT算法主要包括三個階段：數據降維、多粒度掃描和并行構建級聯森林，因此該算法的時間復雜度主要有三部分組成，分別記為T1、T2和T3。

在數據降維的特征選擇階段，時間復雜度主要取決于計算每個特征的信息增益值，它需要遍歷數據集中的每個特征對應的樣本下的每條數據。已知數據集的樣本數目為n，特征數為d，且執行MapReduce任務時對應的Mapper節點個數為b，則該階段的時間復雜度為：

在數據降維的特征提取階段，時間復雜度主要取決于特征的凝聚層次聚類過程。已知經選擇后的特征數為m，則時間復雜度為：

因此，數據降維的時間復雜度為：

在多粒度掃描階段，時間復雜度主要取決于在多粒度掃描后，根據得到的數據子集建立樹模型的過程。已知經數據降維后的特征個數為o，多粒度掃描的粒度為L，樣本數目為n，假設森林中樹的個數為N，則時間復雜度為：

在并行構建級聯森林階段，主要是調用MapReduce任務并行構建每一級森林。已知樣本的個數為n，特征數為2co，假設森林中樹的個數為F，Mapper節點的個數與森林的個數相同，且共有W層，則時間復雜度為：

因此，IPDFIT算法的時間復雜度為：

3 實驗結果及比較

3.1 實驗環境

為了驗證IPDFIT算法的性能，本文設計了相關實驗。在硬件方面，實驗包括5個計算節點，其中1個Master節點，4個Slaver節點。所有節點的CPU均為AMD Ryzen 7，每個CPU都擁有8個處理單元，其內存均為16 GB。實驗環境中的5個節點處于同一個局域網中，通過200 Mb/s以太網相連。在軟件方面，每個節點安裝的Hadoop版本為2.7.4，Java版本為1.8.0，操作系統均為Ubuntu 16.04。各個節點的具體配置如表1所示。

表1 實驗中節點的配置Table 1 Configuration of nodes in experiments

3.2 實驗數據

IPDFIT算法所使用的實驗數據為3個來自UCI公共數據庫（https://archive.ics.uci.edu/ml/index.php）的真實數據集，分別是Farm Ads、Susy和APS Failure at Scania Trucks，如表2所示。Farm Ads數據集是從12個網站上的文字廣告中收集的各種與農場動物相關的話題，該數據集包含了4 143條樣本，共有54 877種屬性，具有樣本量少、屬性數多的特點；Susy是一個記錄使用粒子加速器探測粒子的數據集，該數據集包含5 000 000條樣本，共有18種屬性，具有樣本量多，屬性數少的特點；APS Failure at Scania Trucks數據集是一個記錄斯堪尼亞卡車APS故障和操作數據，該數據集包含了60 000條樣本，共有171種屬性，具有樣本量、屬性數適中的特點。

表2 實驗數據集Table 2 Experimental datasets

3.3 實驗過程

以Farm Ads數據集為例，實驗過程可以具體闡述為：（1）數據降維。首先，結合MapReduce框架，并行計算出每個特征對應的信息增益值，排序后，篩選出信息增益值較低的特征將它們移除；其次，調用特征相關性函數FC(xa,xb)評估特征間的相關性，利用凝聚層次聚類算法將相似的特征聚集于相同的簇中，并再次調用MapReduce框架，通過主成分分析算法對每個簇中的特征進行提取。（2）多粒度掃描。針對數據降維得到的數據集，首先對其中的每一個樣本做數據組合處理；其次，通過多粒度掃描得到組合數據的數據子集；通過學習訓練數據子集建立隨機森林和完全隨機森林模型，并利用模型對數據子集進行預測；最后將預測得到的類向量進行拼接，所有拼接后的類向量作為輸入傳入下一階段。（3）并行構建級聯森林。在級聯森林的每一級中，利用上一級中得到的類向量作為訓練樣本（第一級利用多粒度掃描輸入的數據），調用MapReduce框架并行訓練該級森林模型，利用得到的森林模型對訓練樣本進行預測，并通過TSWS策略對訓練樣本進行評估加權，篩選出權重為0的訓練樣本進入下一級訓練。當級聯森林的準確度收斂時，并行構建級聯森林階段結束。

3.4 評價指標

大數據環境下，為驗證并行算法的挖掘性能，通常采用加速比作為衡量指標。加速比是指在并行計算下，降低運行時間從而獲得的性能提升，其定義為：

其中，T1表示算法在單個節點上的運行時間，T p表示并行計算時的運行時間，S p越大，則表示并行計算所耗費的相對時間較少，集群效率得到提升。

3.5 IPDFIT算法的性能分析

為驗證IPDFIT算法在大數據環境下的可行性，本文選取IPDFIT算法中森林所涉及的樹模型的棵數為50、100、150，分別將IPDFIT算法應用于Farm Ads、Susy、APS Failure at Scania Trucks這3個數據集中，通過對算法準確度和加速比的比較，從而實現對IPDFIT算法性能的總體評估。圖8為IPDFIT算法在3個大數據集的執行結果。

圖8 IPDFIT算法的性能分析Fig.8 Performance analysis of IPDFIT algorithm

從圖8中可以看出，當樹模型的數量從50變化到100再到150時，該算法在Farm Ads數據集的準確度分別增加了1.4個百分點和1.0個百分點，加速比分別增加了0.15和0.12；在Susy數據集的準確度分別增加了3.3個百分點和1.8個百分點，加速比分別增加了0.12和0.06；在APS Failure at Scania Trucks數據集的準確度分別增加了2.3個百分點和1.6個百分點，加速比分別增加了0.6和0.4。從圖片反映出的數據可以看出，IPDFIT算法在3種數據集上的準確度都逐漸增大，且準確度的增幅卻逐漸減小，其產生主要是由于隨著樹模型數量的增加，樹與樹之間的差異就會減小，進而對隨機森林分類結果的影響程度就會越來越小，所以準確度的增長幅度會隨著決策樹的增加而減少。此外，從圖8（b）中可以看出，算法在處理數據樣本數較多的Susy、APS Failure at Scania Trucks數據集時，其加速比整體要高于樣本數較少的Farm Ads數據集，這是由于在樣本數多的數據集下，算法能夠并行特征降維和構建級聯森林的優點被逐漸放大，算法的挖掘性能得到極大提高。同時這也表明IPDFIT算法適用于大數據集的處理，且具有較強的擴展性。

3.6 IPDFIT算法的性能比較

為驗證IPDFIT算法的時間復雜度以及準確度，本文基于Farm Ads、Susy、APS Failure at Scania Trucks數據集進行實驗，根據所得到的運行時間和準確度數據，與ForestLayer算法進行綜合比較，同時，為了探究IPDFIT算法性能與深度森林gcForest算法相比的提升程度，進一步結合MapReduce框架并行化運行gcForest算法，記為gcForest-MR。具體實驗如下所示。

3.6.1 IPDFIT算法時間復雜度比較

從圖9中可以看出，在Farm Ads數據集上IPDFIT算法的運行時間比gcForest-MR算法平均高出3 269.33 s，比ForestLayer算法平均低1 888 s；在Susy數據集上IPDFIT算法的運行時間比gcForest-MR算法平均高出275.33 s，比ForestLayer算法平均低2 308.67 s；在APS Failure at Scania Trucks數據集上IPDFIT算法的運行時間比gcForest-MR算法平均高出552 s，比ForestLayer算法平均低1 055.34 s，出現上述情況是由于在構建深度森林時ForestLayer算法對森林做出了優化，采用了分割機制，且使用了延遲掃描、預池、部分傳輸優化算法性能，IPDFIT算法則是使用了數據降維、改進的多粒度掃描以及樣本評估等手段。這些優化在一定程度上都會對運行時間有一定的影響，然而，IPDFIT算法平均所用運行時間少于ForestLayer算法，且在Susy數據集上當樹模型數量為150時運行時間少于gcForest-MR，是因為IPDFIT算法采用了DRIT策略降低了數據的復雜程度，并在TSWS的基礎上對并行構建級聯森林的過程進行了改進，既逐步降低了每層級聯中樣本的數目，又加快了整體級聯森林的收斂速度。

圖9 不同算法在不同數據集上的運行時間比較Fig.9 Comparison of running time of differentalgorithms on different datasets

3.6.2 IPDFIT算法準確度比較

從圖10中可以看出，IPDFIT算法在處理大數據時具有很好的準確度。在特征較多的Farm Ads和APS Failure at Scania Trucks數據集中，如圖10（a）、（c）所示，IPDFIT算法的準確度比ForestLayer算法的準確度平均高出1.44、3.04個百分點，比gcForest-MR算法的準確度平均高出2.94、3.37個百分點，這是由于IPDFIT算法在建立深度森林模型時采用了IMGSS以及TSWS策略，前者優化了多粒度掃描的過程，提高了數據子集的質量；后者對級聯森林中的訓練樣本進行逐層篩選，針對訓練較差的樣本提高了其訓練強度。然而，在特征數較少的Susy數據集中，如圖10（c）所示，IPDFIT算法的提升效果并不是很明顯，其準確率甚至低于gcForest-MR算法。以上情況的出現是由于Susy數據集特征本身質量較高且特征較少，所以IPDFIT算法中的數據降維策略并不能達到優化特征的目的，反而會使數據集丟失部分信息量，即便如此，IPDFIT算法的準確度還是優于ForestLayer算法，這歸功于IMGSS以及TSWS策略分別對多粒度掃描的過程和級聯森林訓練過程的改善。故從以上實驗結果可以看出，IPDFIT算法對處理樣本規模較大且特征數量較多的數據集的優勢較為明顯。

圖10 不同算法在不同數據集上的準確度比較Fig.10 Comparison of accuracy of different algorithms on different datasets

4 總結

為解決并行深度森林算法在大數據環境下的不足，本文提出了一種基于信息論改進的并行深度森林算法IPDFIT。該算法首先充分考慮到大數據集中冗余與不相關特征較多的問題，提出了一種混合降維策略DRIT，在考慮到特征-特征相關性的同時，有效地降低了數據集的維度；其次，為了改善多粒度掃描不平衡的問題，提出了IMGSS策略，該策略充分考慮到了多粒度掃描時的不足，通過數據組合的方法保證了每個特征在掃描后以同頻率出現在數據子集中；最后，為了提升級聯森林并行訓練的效率，設計了樣本加權策略TSWS，該策略逐級對樣本進行加權評估，選取評估結果較差的樣本進入下一層訓練，不僅減少了每級所需訓練樣本的個數，而且加快了模型的收斂速度。同時為了驗證IPDFIT算法的分類性能，本文在Farm Ads、Susy、APS Failure at Scania Trucks數據集上對ForestLayer、gcForest-MR以及IPDFIT這3種算法進行對比分析。實驗結果表明，IPDFIT算法在大數據環境下，尤其是針對特征數較多的數據集的分類有著較高的準確度。