結合信息論和范數的并行隨機森林算法

毛伊敏，耿俊豪

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

分類算法是一種有監督的學習算法，它能夠根據有標記的信息發現分類規則、構造分類模型，從而預測未含標記的數據屬性特征。在分類算法中，隨機森林（random forest，RF）以其具有穩定性強、對噪聲和異常值有較好容忍性等特點，近年來已被應用于文本分類、環境預測、信用評估、生物信息、醫療診斷等領域，受到人們的廣泛關注。

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

近年來在大數據處理方面，Google 開發的Map-Reduce 并行編程模型由于操作簡單、自動容錯、擴展性強等優點深受廣大學者和企業的青睞。同時，以Hadoop、Spark 為代表的分布式計算架構也受到了越來越多的關注。目前許多基于MapReduce 計算模型的隨機森林算法已成功應用到大數據的分析與處理領域中。其中，基于MapReduce 的并行化隨機森林算法MR_RF，采用分而治之的思想，調用Map-Reduce 模型將數據分區后傳遞給多個計算節點構建基分類器，匯聚每個計算節點輸出的基分類器得到隨機森林模型。接著，再次調用MapReduce 模型，利用構建好的隨機森林對測試集進行預測得到分類準確度，實現了隨機森林算法的并行化，但該算法前后調用兩次并行化框架，中間結果多次的讀出和寫入，消耗了大量的時間。為了降低MR_RF 算法的時間復雜度，錢雪忠等人提出了一種改進的MR_RF算法，利用袋外數據直接計算出分類模型的泛化誤差，以此判斷隨機森林的分類準確率，減少了調用并行框架的次數。然而在大數據環境下，數據集中大量的冗余以及不相關特征降低了構建隨機森林模型時決策樹所選特征的質量，進而影響了隨機森林模型整體的分類準確度。

為降低大數據集中的冗余與不相關特征對模型的影響，Chen 等人提出了一種并行隨機森林算法（parallel random forest，PRF），通過計算特征信息增益率的方式，選出最優的個訓練特征與其余訓練特征隨機搭配，對訓練特征降維，并利用袋外數據作為訓練集計算出每棵決策樹對應的分類準確度作為權重，用于模型預測階段。雖然PRF 算法優化了訓練特征，提升了隨機森林的分類準確度，但沒有減少數據集本身冗余與不相關特征的個數，故生成的訓練特征集依然還有較多的冗余與不相關特征；針對以上情況，Hu 等人提出了一種基于最大信息系數的并行隨機森林算法PRFMIC，通過計算最大信息系數將特征分為三個區間，刪除低相關區間的特征，選取高相關區間和中相關區間內的特征組成特征子集，并行構建隨機森林模型，算法雖然考慮到了不相關特征對隨機森林模型的影響，但數據中存在的冗余特征在隨機森林建模階段非但不能提供有效的信息，而且增加了決策樹與決策樹之間相關性，影響隨機森林模型整體的準確度；此外，上述算法在生成訓練特征集時未考慮到訓練特征的信息量，由低信息量的訓練特征集訓練出的決策樹影響了隨機森林整體的準確度；同時，算法在預測分類階段，由于負載不平衡造成該階段所需時間過多，影響了隨機森林整體的并行化效率。如何減少大數據集中冗余與不相關特征，如何提高訓練特征信息量以及如何提升算法的并行效率等仍然是目前亟待解決的問題。針對這些問題，本文提出了基于信息論和范數的并行隨機森林算法（parallel random forest algorithm based on information theory and norm，PRFITN）。首先，該算法基于信息增益和Frobenius 范數設計了一種混合降維策略DRIGFN（dimension reduction based on information gain and Frobenius norm），獲得降維后的數據集，有效減少了冗余及不相關特征數；此外，算法提出了一種基于信息論的特征分組策略（feature grouping strategy based on information theory，FGSIT），根據FGSIT 策略將特征分組，采用分層抽樣方法，保證了隨機森林中決策樹構建時特征子集的信息量，提高了分類結果的準確度；最后，考慮到集群負載對并行算法效率的影響，在Reduce 階段提出了一種鍵值對重分配策略（redistribution of key-value pairs，RSKP），獲取全局的分類結果，實現了鍵值對的快速均勻分配，從而提高了集群的并行效率。實驗結果表明，該算法在大數據環境下，尤其是針對特征數較多的數據集有更好的分類效果。

1 算法及相關概念介紹

1.1 相關概念介紹

（信息增益）已知離散變量和其對應的類別，則信息增益(;)由下式計算：

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

（互信息）已知離散變量、，則互信息(;)由下式計算：

（條件互信息）已知離散變量、以及它們對應的類別，則條件互信息(;|)由下式計算：

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

（Frobenius 范數）已知=(a)∈R為一個×維的矩陣，a為矩陣中的元素，則Frobenius范數||||可以由下式計算：

1.2 相關算法介紹

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

支持向量機算法（support vector machine，SVM）是建立在統計學理論基礎上的數據挖掘算法，主要通過選擇一個滿足分類要求的最優分類超平面，使得該超平面在保證分類精度的同時，能夠使超平面兩側的空白區域最大化。SVM 算法主要分為3 個步驟：（1）構建分類超平面()=，其中是超平面的權值，是數據向量矩陣；（2）利用核函數求解分類超平面，得到超平面權值；（3）利用超平面權值預測數據分類。

2 PRFITN 算法

PRFITN 算法主要包括三個階段：數據降維、特征分組和并行構建隨機森林。（1）在數據降維階段，提出DRIGFN 策略，準確地識別和刪除數據集中的冗余和不相關特征，獲得降維后的數據集DB；（2）在特征分組階段，提出FGSIT 策略用于度量特征的重要性，并在此基礎上循環分配特征，以此獲得兩組特征子集、；（3）在并行構建隨機森林階段，提出RSKP策略用于優化MapReduce 計算模型，提升其并行化效率，并利用優化后的MapReduce模型并行構建隨機森林、預測數據集分類，得到隨機森林的準確度。

2.1 數據降維

目前，降維算法主要包括特征選擇和特征提取兩個方向，然而在大數據環境下，由于數據集中存在大量冗余與不相關特征，故單獨使用特征選擇或特征提取方法，都無法獲得較優的特征集合。針對這一問題，本文提出DRIGFN 策略用于識別和過濾大數據環境下的冗余和不相關數據。首先結合MapReduce模型，并行計算特征信息增益值，以此刪除不相關特征；接著利用Frobenius 范數評估信息損失量、分類誤差以及控制分類器過擬合，并在此基礎上提出全局優化函數用于迭代優化降維參數。假設=[,,…,x]∈R表示原始數據集DB 的維特征空間中的個樣本，數據集DB 包含個不同類別，∈R表示特征矩陣所對應的標簽，則DRIGFN 策略如下：

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

特征選擇

在特征提取階段，為進一步優化特征選擇后的數據集DB′，首先，利用主成分分析以及支持向量機算法獲取初始參數，并利用得到的參數對特征矩陣進行重構；其次，采用Frobenius 范數對信息損失量、分類誤差以及分類器過擬合程度進行估計；最后，為了使信息損失量、分類誤差以及過擬合程度總和達到最小，提出了全局優化函數對轉換矩陣和分類矩陣進行優化。特征提取的具體過程描述如下：

（1）參數的初始化與特征矩陣的重構

已知特征矩陣′和數據集DB′，首先采用主成分分析（PCA）獲取初始的轉換矩陣∈R（1 ≤≤），即：

其中，″是由PCA 降維后得到的特征矩陣，與標簽按列合并后得到轉換后的數據集DB″。

其次，采用支持向量機（SVM）算法以數據集DB″中所有樣本作為訓練集獲得關于″的分類矩陣∈R，據此可以計算出″的預測標簽為：

接著，為了評估在特征提取過程時信息的損失量，采用轉換矩陣對特征矩陣″進行重構，″的重構矩陣X可以表示為：

（2）信息損失量、分類誤差以及分類器過擬合程度的估計

根據上一步中得到的轉換矩陣、分類矩陣以及重構矩陣X，該部分將采用Frobenius 范數對信息損失量、分類誤差以及分類器過擬合程度進行估計。

因重構矩陣X由特征矩陣′通過矩陣轉換得到，故與′的元素間會存在或多或少的差異，從而利用Frobenius 范數對兩矩陣中各個元素的差異處理后求和，得到的結果便可反映出降維后矩陣″與矩陣′相比的信息損失量，具體定義如下：

（信息損失量）已知特征矩陣′和重構矩陣X，則根據定義4，信息損失量可以表示為：

同理，預測標簽(″)與標簽之間的差異也可利用Frobenius范數對其度量，具體定義如下：

（分類誤差）已知為特征矩陣所對應的標簽，(″)是由支持向量機預測得到的預測標簽，則根據定義4，分類誤差可以表示為：

最后，根據Frobenius 范數，設計，通過值控制分類的過擬合程度，具體定義如下：

（過擬合程度）已知為特征矩陣″的分類矩陣，則根據定義4，過擬合程度可以表示為：

根據Frobenius 范數的定義可以推斷出，的元素分布越均勻，的值越小；反之，中個別元素值越大，的值越大。

（3）全局優化函數

為了獲取全局最優轉換函數，需要同時滿足、以及總體最小化，故結合式（8）～（10）三式提出關于轉換矩陣和分類矩陣的全局優化函數(,)的定義，如下所示：

（全局優化函數(,)）已知特征矩陣′和標簽，對應的轉換矩陣和分類矩陣分別為和，由此可得到關于′的信息損失量、分類誤差以及過擬合程度為、和，則全局優化函數(,)可表示為：

其中，和分別為和的權重參數。

考慮到全局優化函數(,)中分類矩陣受到轉換矩陣的影響，故在利用梯度求解函數最小值時將其分為兩步：（1）將分類矩陣視為常數求解轉換矩陣；（2）將轉換矩陣代入求解分類矩陣。根據、和的相關定義，對函數(,)求關于的梯度為?(,)，令?(,)=0，可求解出轉換矩陣′，且對于?∈(={|∈R，≠′}) 都有(,)≥(′,)，故′為 使(,) 最小的局部最優轉換矩陣；同理，將′代入(,)，對(′,)關于的梯度為?(′,)，令?(′,)=0，可求得分類矩陣′，且對于?∈(={|∈R，≠′})都有(′,)≥(′,′)，故′為使(′,)最小的局部最優分類矩陣。

根據定義8 及其求解過程可以得到局部最優轉換矩陣′以及分類矩陣′。為獲取全局最優轉換矩陣，將求解得到的局部最優轉換矩陣′以及分類矩陣′依次代入函數(,)對轉換矩陣以及分類矩陣迭代求解直到其收斂，此時返回得到的轉換矩陣即為全局最優轉換矩陣。最后將全局最優轉換矩陣代入式（5）便可得到經特征提取后的特征矩陣=[,,…,x]∈R，并與標簽按列合并后即可得到降維數據集DB。特征提取的執行過程如下所示：

特征提取

2.2 特征分組

目前大數據環境下的并行隨機森林算法中，訓練特征的形成是通過隨機選取數據集的特征獲得的，雖然DRIGFN 策略通過數據降維的方式減少了數據集中存在的冗余和不相關特征，但仍存在大量低信息量特征，由于它們的存在，導致生成的訓練特征所含信息量低。為了解決上述問題，提出基于信息論的特征分組策略FGSIT，該策略首先利用信息論的相關知識衡量特征-標簽、特征-特征間的影響程度；其次，在獲取特征-標簽、特征-特征影響程度的基礎上提出特征評判函數；最后，以迭代的方式將特征劃分為兩組。特征分組的具體過程描述如下：

（1）特征-標簽、特征-特征間的影響程度

已知特征x是特征矩陣中的任一特征，是特征矩陣對應的標簽，根據定義1 得到特征x的信息增益(x;)如下所示：

然而，信息增益只衡量了特征-標簽間的影響，忽略掉了特征-特征間的影響，考慮到特征分組過程中，備選特征對已選特征的影響，提出了一種計算特征-特征間影響程度的函數()，其定義如下所示：

（特征-特征影響函數()）已知為標簽，為已選特征集，x是中的元素，則根據定義2和定義3，備選特征x對中特征的影響程度()可表示為：

根據定義2 和定義3 可知，互信息(x;)表示已選特征x與標簽之間的相關性，條件互信息(x;|x)則表示在特征x的條件下特征x與標簽之間的相關性，因此利用條件互信息(x;|x)與互信息(x;)之差可表示特征x對特征x與標簽的影響，故在()函數中利用特征x對中所有特征的影響之和便可表示特征x對的整體影響程度。

（2）特征評判函數

為了在特征分組過程中同時考慮到特征-標簽、特征-特征間的影響程度，結合以上兩點，提出特征評判函數()，其定義如下所示：

（特征評判函數()）已知備選特征x、標簽向量以及已選特征集，則關于特征x的評判函數()可表示為：

其中，為函數(x;)的權重參數。

因信息增益可以用來衡量特征-標簽間的影響，函數()可以衡量特征-特征間的影響，故結合式（12）、式（13）得到的特征評判函數()可同時衡量特征-標簽、特征-特征間的影響程度。

（3）特征分組

由定義10 提出的特征評判函數()可將特征分組過程分為三步：

①將中信息增益值最大的特征放入中；

②依次計算備選特征的()值，將()最大值對應的特征放入中；

③迭代執行步驟②，直到中特征個數達到閾值時為止，其余特征自行組成特征集。

根據隨機森林的性質可以推斷出隨機森林的分類效果與森林中決策樹間的相關性以及每棵決策樹的分類能力兩個因素有關，相關性越強，隨機森林分類效果越差；決策樹分類能力越強，隨機森林分類效果越好。然而，閾值的選擇影響到了特征的分組，進而同時影響到決策樹的相關性以及決策樹的分類能力。因此，閾值的選擇尤為重要，故提出閾值函數()用來確定閾值，其定義如下所示：

（閾值函數()）假設隨機森林中有棵決策樹，中包含個特征，中包含個特征，按比例從中隨機抽取個特征作為高信息量特征，從中隨機抽取個特征與組合作為構建決策樹的訓練特征，則閾值函數()可表示為：

其中，是利用中特征占比反映出隨機森林中決策樹的整體分類能力，是利用兩棵決策樹所選特征的相似程度反映出隨機森林中決策樹的相關性。

根據定義11 可知可用來衡量隨機森林中決策樹整體的分類能力，可用來衡量隨機森林中決策樹間的相關性。因此，根據隨機森林的性質，隨機森林的分類效果可以利用-衡量，通過觀察式子可以發現當特征全部屬于時，/(+)=1，此時=1 且≈0，可取到其最大值，但此時失去了分組的意義故而舍去；當/(+)＜1，由于在大數據環境 下?/2，故≈0，此時可以得到當=，=，即=(+)/2 時，的取值最小，-可達到最大值。

FGSIT 策略的執行過程如下所示：

FGSIT 策略

2.3 并行構建隨機森林

在數據降維和特征分組之后，需要根據降維后的數據集DB以及特征集、并行化訓練分類器。目前大數據環境下的并行隨機森林算法大多根據訓練數據和訓練特征構建多棵決策樹作為輸出結果，并在此基礎上對樣本進行預測，獲得模型準確度。然而，此類方法在預測階段時，由于各個計算節點中決策樹的不同，進而對數據集得到的預測鍵值對也有所不同，故在合并之后，每個Mapper 節點上鍵值對的數量會有所差異，通常會導致下一階段中Reducer節點負載不平衡，影響算法的并行化效率。為了應對上述問題，本節首先提出RSKP 策略優化MapReduce計算模型，平衡Reducer 節點負載；然后，利用優化后的MapReduce 模型并行構建隨機森林，預測數據集分類，得到隨機森林的準確度。并行構建隨機森林的具體過程描述如下：

（1）RSKP 策略

給定每個Mapper 節點中合并后得到的鍵值對集合,,…,P，RSKP 策略的過程描述如圖1 所示。

圖1 RSKP 策略Fig.1 RSKP strategy

①將所有的鍵值對集合,,…,P匯總到中間文件中，并根據鍵值對中的鍵對它們進行排序；

②根據鍵值對的數量以及Reducer 節點的個數將中間文件夾中的鍵值對均勻分配到各個節點。

（2）并行構建隨機森林、預測數據集分類

通過RSKP 策略得到了優化后的MapReduce 模型，結合該模型，并行構建隨機森林具體分為四步，由圖2 所示。

圖2 并行構建隨機森林Fig.2 Construct random forests in parallel

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

②根據主節點分配給每個Mapper 節點的任務，調用Map 函數通過bootstrap 自主抽樣方式抽取決策樹的訓練集，并從特征子集、中按比例隨機抽取特征作為訓練特征，基于訓練集和訓練特征以鍵值對＜key,value＞的形式構建決策樹（key為決策樹模型編號，value為該決策樹模型），所有Mapper 節點執行完畢，解析出所有決策樹合并得到隨機森林模型。

③利用Mapper 節點中的決策樹對數據集DB進行預測并形成新的鍵值對＜′,′＞（′為樣本ID 與對應類別的組合數組，′=1 表示該鍵值對出現的次數），合并具有相同′值的鍵值對（如本 地有三個′都為的鍵值對＜:1 ＞、＜:1 ＞、＜:1 ＞，則它們將會合并為一個鍵值對＜:3 ＞）。

④將Mapper 節點中預測得到的鍵值對由主節點分配后傳入相應的Reducer 節點再次合并，得到全局分類結果，并與標簽比較得到模型的準確度。

至此，并行構建隨機森林的執行過程如下所示：

并行構建隨機森林

2.4 PRFITN 算法步驟

PRFITN 算法的具體實現步驟如下：

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

調用FEKFN 策略以迭代的方式對特征選擇后的數據集進行新特征的提取。

調用FGSIT 策略對降維后的數據集進行特征分組。

啟動新的MapReduce 任務，調用Map 函數，采用bootstrap 和分層抽樣的方法抽取建模所用的訓練樣本及特征，構建決策樹，匯總所有決策樹得到隨機森林；采用RSKP 策略均勻分配Reducer 節點任務，調用Reduce 函數得到全局分類結果，并評估模型分類準確率。

2.5 算法時間復雜度分析

PRFITN 算法主要包括三個階段：數據降維、特征分組和并行構建隨機森林。因此，該算法的時間復雜度主要由三部分組成，分別記為、和。

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

在數據降維的特征提取階段，時間復雜度主要取決于迭代優化轉換矩陣以及分類矩陣的過程，已知為×階矩陣，為×1 階矩陣，假設該階段需要迭代計算次，則時間復雜度為：

因此，數據預處理的時間復雜度為：

在特征分組階段，主要采用FGSIT 策略劃分特征，每次篩選特征時都需要計算每個備選特征與已選特征之間的特征評判函數()。已知處理過后的特征個數為，樣本數為，則該階段的時間復雜度為：

在并行構建隨機森林階段，主要調用MapReduce任務并行構建隨機森林模型以及預測全部數據的分類從而評估準確率。假設隨機森林模型包含棵決策樹，且執行MapReduce 任務時對應的Mapper 節點個數為，Reduce 節點個數為，則該階段的時間復雜度為：

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

3 實驗結果及比較

3.1 實驗環境

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

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

3.2 實驗數據

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

表2 實驗數據集Table 2 Experimental datasets

3.3 PRFITN 算法的性能分析

為驗證PRFITN 算法在大數據環境下的可行性，本文選取隨機森林中決策樹的棵樹為50、100、150，分別將PRFITN 算法應用于Farm Ads、Susy、APS Failure at Scania Trucks 3 個數據集中，獨立運行10次，取10 次運行結果的均值，通過對算法運行時間和準確度的比較，從而實現對PRFITN 算法性能的總體評估。圖3 為PRFITN 算法在3 個數據集下的執行結果。

從圖3 可以看出，當決策樹數量從50 變化到100再到150 時，算法在Farm Ads 數據集運行的時間分別增加了8 700 s 和9 000 s，準確度分別增加了3.8 個百分點和1.5 個百分點；在Susy 數據集運行的時間分別增加了4 250 s 和6 000 s，準確度分別增加了2.5 個百分點以及降低了0.7 個百分點；在APS Failure at Scania Trucks 數據集運行的時間分別增加了750 s 和4 500 s，準確度分別增加了3.0 個百分點和1.1 個百分點。從圖片反映出的數據可以看出，PRFITN 算法在三種數據集上的時間復雜度和準確度都逐漸增大，且時間復雜度的增幅逐漸增大，準確度的增幅卻逐漸減小。前者產生主要是由于隨著決策樹數量的增長，在建模階段中分配到計算節點的任務量增多，同時鍵值對的數量也會成倍增加，故需要消耗更多的時間處理它們；后者產生主要是由于隨著決策樹數量的增加，樹與樹之間的差異將會減小，進而對隨機森林分類結果的影響程度就會越來越小，因此準確度的增長幅度會隨著決策樹的增加而減少。

圖3 PRFITN 算法的性能分析Fig.3 Performance analysis of PRFITN algorithm

3.4 PRFITN 算法的性能比較

為驗證PRFITN 算法的時間復雜度，本文基于Farm Ads、Susy、APS Failure at Scania Trucks 3 個數據集進行實驗，根據所得到的運行時間，與改進的MR_RF 算法、PRF 算法以及PRFMIC算法進行綜合的比較。與此同時，為了探究負載均衡對PRFITN算法的影響，進一步運行了不使用RSKP 策略的PRFITN 算法，記為PRFITN-ER。具體的時間復雜度如圖4 所示。

圖4 五種算法在不同數據集上的運行時間Fig.4 Running time of five algorithms on different datasets

從圖4 中可以看出，在Farm Ads 數據集上，PRFITN 算法的運行時間比PRFMIC 算法、PRF 算法以及改進的MR_RF 算法的運行時間平均分別高出2 300 s、3 833.3 s 和8 666.7 s；在APS Failure at Scania Trucks 數據集上，PRFITN 算法的運行時間比PRFMIC算法、PRF 算法以及改進的MR_RF 算法的運行時間平均分別高出200 s、416.7 s 和733.3 s。出現上述兩種情況是由于在構建隨機森林模型時PRF 算法對訓練特征采取了數據降維處理，PRFMIC 算法對特征采取了分層處理，而PRFITN 算法對特征同時采取了數據降維及特征分層處理，且PRFITN 算法的降維及分層策略偏重于直接評估特征本身，因此在處理特征相對較多的Farm Ads 和APS Failure at Scania Trucks數據集時，PRFITN 算法明顯比PRFMIC、PRF 以及改進的MR_RF 算法所用時間多。相反，在處理樣本量較多、特征數較少的Susy 數據集時，PRFITN 算法的運行時間比PRFMIC 算法和PRF 算法的運行時間分別低6 783.4 s 和3 750 s。這是由于特征數量較少時，PRFITN 算法在數據降維以及特征分層階段所用時間較少，同時PRFMIC 算法使用了RSKP 策略，平衡了每個節點的負載量，降低了時間復雜度。此外，為了更直觀地判斷出負載均衡對模型的影響程度，即RSKP 策略對模型的優化效果，對比PRFITN 算法和PRFITN-ER 算法在三種數據集上的運行時間可以看出，在Farm Ads 數據集、Susy 數據集以及APS Failure at Scania Trucks 數據集上，PRFITN 算法的運行時間要比PRFITN-ER 算法平均節約1 733.33 s、1 583.33 s以及295 s，故RSKP 策略的采用將在一定程度上節約模型學習的時間。

為驗證PRFITN 算法的準確度，本文基于Farm Ads、Susy、APS Failure at Scania Trucks 3 個數據集進行實驗。根據分類結果，與改進的MR_RF 算法、PRF 算法以及PRFMIC 算法進行綜合的比較。具體的準確度如圖5 所示。

圖5 四種算法在不同數據集上的準確度Fig.5 Accuracy of four algorithms on different datasets

從圖5 中可以看出，PRFITN 算法在處理大數據集時具有很好的準確度。在特征較多的Farm Ads 數據集和APS Failure at Scania Trucks 數據集中，如圖5（a）、圖5（c）所示，PRFITN 算法的準確度比PRFMIC算法的準確度平均高出2.7 個百分點和2.8 個百分點，比PRF 算法的準確度平均高出3.0 個百分點和2.6個百分點，比改進的MR_RF 算法的準確度平均高出7.1 個百分點和4.5 個百分點。這是由于PRFITN 算法在建模前采用DRIGFN 策略，相比PRF 算法以及PRFMIC 算法的降維策略，DRIGFN 策略有效過濾掉了冗余與不相關特征，提高了特征的質量。同時，在模型的構建階段，算法采用了FGSIT 策略，該策略在考慮特征-特征與特征-類別影響的基礎上，對特征進行了分層處理，保證在生成決策樹的過程中訓練特征含有較高的信息量。然而，在特征數較少的Susy數據集中，如圖5（b）所示，PRFITN 算法的提升效果并不是很明顯，其準確度甚至低于PRFMIC 和改進的MR_RF 算法，并且當隨機森林中決策樹的數目由100 變化到150 時，PRFITN 和PRF 算法的準確度反而出現了下降。以上情況的出現是由于Susy 數據集特征本身質量較高且特征量較少，故PRFITN 和PRF 算法中的數據降維策略并不能達到優化特征的目的，反而會使特征集丟失部分信息量。即便如此，PRFITN算法的準確度還是優于PRF 算法，這是因為DRIGFN策略在降維時迭代對轉換矩陣進行優化，有效減少了在降維過程中所損失的信息量。故從以上實驗結果可以看出，PRFITN 算法對處理樣本規模較大且特征數量較多的數據集優勢較為明顯。

4 總結

為解決并行隨機森林算法在大數據環境下的不足，本文提出了一種基于信息論和范數的并行隨機森林算法PRFITN。首先，該算法充分考慮到大數據集中冗余與不相關特征較多的問題，提出了一種混合降維策略DRIGFN。該策略不僅能有效地降低數據集的維度，而且可以極大限度地降低數據降維時所損失的信息量。其次，為了提高隨機森林中訓練決策樹所用特征的信息量，提出了一種特征分組策略FGSIT，該策略充分考慮了特征-特征以及特征-標簽之間的關系，在此基礎上將特征劃分為兩組，按比例抽取訓練特征，保證了構建決策樹時所選特征的信息量。最后，考慮到集群負載對并行算法效率的影響，設計了鍵值對重分配策略RSKP，對并行算法得到的中間結果進行均勻分組，平衡了集群中reducer節點的負載量，減少了算法的時間復雜度。同時為了驗證PRFITN 算法的分類性能，本文在Farm Ads、Susy、APS Failure at Scania Trucks 三個數據集上與改進的MR_RF 算法、PRF 算法以及PRFMIC 算法三種算法進行對比分析。實驗結果表明，PRFITN 算法在大數據環境下，尤其是針對特征數較多的數據集的分類有著較高的準確度。