Hadoop環境下基于隨機森林的特征選擇算法

張 鑫，吳海濤，曹雪虹

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003；2.南京工程學院 通信工程學院，江蘇 南京 211167；3.南京工程學院 康尼機電研究院，江蘇 南京 211167)

0 引 言

隨著網絡數據存儲和數據收集能力的快速發展，從海量數據中提取有價值信息成為近年來的研究熱點之一。隨機森林作為一種常見的機器學習算法[1]，在數據挖掘領域中得到了廣泛的應用。而隨著數據規模的增大，基于單機的隨機森林算法無法滿足高維大數據的需求，Google公司的MapReduce分布式計算模型成為一個不錯的選擇[2]，該模型由Hadoop開源實現。MapReduce分布式計算模型使用簡便，具備高擴展、高容錯等特點[3-4]，計算架構與隨機森林的設計要求相符合，可以方便地實現隨機森林算法的并行操作，從而滿足對海量大數據快速的計算、分類，相比于傳統算法具有良好的加速比和可擴展性。

高維海量的大數據中一個突出的問題就是“維數災難”，即特征過多的問題。如何從高維的數據中篩選出有用的特征，并利用這些有用的特征進行分類和預測已經成為當今信息技術面臨的一大熱點問題[5]。特征選擇是指從所有特征中評估出最佳的特征子集，使得該特征子集所構建的分類模型達到更好的預測精度[6]。早在1998年，Ho T K提出的隨機森林本身就有特征選擇這一過程，但是其特征子集是隨機選取的，不能保證特征子集里面沒有一些冗余的特征對分類產生干擾[7]。2001年，Breiman L在隨機森林的闡述中夾雜了內置的特征選擇算法[8]，即通過人為改變袋外數據集特征，根據測試集測試準確率變化得到特征的重要性度量，在此基礎上選擇特征。這種方法相比單純隨機地選擇特征，能夠獲取更佳的特征子集和更好的預測精度，奠定了隨機森林特征選擇的基礎。文獻[9]提出的方法從隨機森林內置的特征選擇出發，采樣交叉驗證方式獲取每棵決策樹的特征重要性度量，再根據決策樹和集體隨機森林預測的一致性得出每棵樹的權重，然后加權求和得出最終的特征重要性序列。該算法得出的特征重要性比較準確，但是每一棵樹都進行k折交叉驗證，對于高維大數據集，計算量太大。

Davies等認為從全部特征中得到最佳特征子集是NP完全問題[10]，要在運算效率和特征子集質量之間把握平衡。特征選擇常用的方法主要有Filter方法和Wrapper方法[11]。Filter方法通過給特征賦予一個權重，根據特征的權重對特征進行排序，基于一些準則選取閾值，保留權重大于閾值的特征，淘汰剩余特征，其突出優點是運算效率高，尤其對大數據集，缺點是選出的特征子集質量并不高。Wrapper方法相比Filter方法就復雜了，通過迭代從一個給定的局部最優解出發，不斷逼近全局最優解，直接用所選特征子集來訓練分類器，根據分類器的性能評估特征子集的優劣，該算法可以選出更恰當的特征子集，缺點是計算效率低。文獻[12]在隨機森林內置的特征選擇基礎上融入了Wrapper方法，得到特征重要性排序之后，每次消除最后一個特征重新進行訓練分類，直至測試的準確率達到最大值為止。該算法在分類和特征子集選擇方面性能良好，但是每次只淘汰一個特征，對于高維大數據集，運算量也是太大。

文中提出的特征選擇綜合考慮了運算效率和特征選擇質量的問題，結合隨機森林內置的特征選擇算法和文獻[9]的算法，并在其基礎上進行改進，特征選擇的過程在Hadoop的MapReduce計算框架下進行，通過改變袋外數據的每一列特征，根據測試準確率的變化得到每棵樹的特征重要性度量，再根據每棵樹的可信度得到樹的權重，將其與前面的特征重要性度量加權求和，最終得到每個特征的重要性度量。最后在特征重要性排序的基礎上選特征時要引入一定的隨機性，整個過程在MapReduce計算框架下并行實現，無論是連續型特征還是離散型特征均可使用。

1 隨機森林預備知識

隨機森林是一種組合分類器，利用bootstrap重采樣方法從原始樣本中抽取多個樣本，對每個采樣得到的樣本集進行訓練，建立決策樹，然后把這些決策樹組合在一起，形成隨機森林，將每一棵決策樹的分類結果通過投票進行組合從而最終完成分類預測[13]。大量的理論和實驗都證明了隨機森林算法具有較高的預測準確率，能夠容忍一定的異常值和噪聲，因為隨機采樣和隨機特征選擇兩個隨機性的引入不易過擬合。

1.1 決策樹

決策樹是典型的單分類器，首先對訓練集進行遞歸分析，生成一棵如同倒立的樹狀結構。在根節點上產生子節點，每棵子節點繼續遞歸產生新的子節點，直到產生節點為葉子節點為止。節點分裂通過比較不同屬性分裂后的結果的優劣來選擇最優屬性分裂產生子樹。比較規則的不同產生了多種決策樹生成算法，這些算法包括CLS、ID3、C4.5、CART等。

ID3決策樹算法通過信息增益準則來選擇劃分屬性，使用信息熵(entropy)來度量樣本集合純度，計算公式如下：

(1)

Ent(D)的值越小，D的純度越高。利用屬性a劃分樣本集D所獲的信息增益(gain)為：

(2)

Gain(D,a)越大，意味著屬性a劃分帶來的純度提升越大。

然而信息增益準則對屬性值較多的屬性有所偏好。為了克服這種偏好帶來的不利影響，著名的C4.5算法使用增益率選擇最優屬性，增益率的定義公式如下：

(3)

CART決策樹用來選擇劃分屬性的是基尼指數(gain)，用基尼值來度量數據集D的純度：

(4)

Gain(D)反映了從數據集D中隨機抽取兩個樣本，其結果不一樣的概率。因此，Gain(D)越小，表示數據集D的純度越高。屬性a的基尼指數定義為：

(5)

所以最優的劃分屬性應該選擇基尼指數最小的屬性。

1.2 隨機森林生成過程

隨機森林生成的過程如下：

(1)用bootstrap重采樣方法從原始訓練數據集中有放回地隨機抽取k個新的訓練子集，構成k棵決策樹，其中未抽到的樣本構成袋外數據集。

(2)假設一共有n個屬性，在樹的每個節點隨機抽取m(m≤n)個屬性，計算每個屬性的信息增益或基尼值，在m個屬性中選擇分類能力最強的屬性來分裂節點。

(3)每棵決策樹生長不受限制，也不要做剪裁。

(4)生成的多棵樹構成隨機森林，使用每棵樹的投票對新的樣本進行分類[14]。

1.3 隨機森林衡量標準

隨機森林算法主要用于分類和預測，分類精度accuracy用來衡量隨機森林對測試集的總體分類精度，一般而言總體分類精度越高，算法分類效果越好。以二分類問題為例：

(6)

其中，TP表示正確的肯定；TN表示正確的否定；FP表示錯誤的肯定；FN表示錯誤的否定。

在隨機森林算法中，OOB估計用來估計泛化誤差。隨機森林在bagging抽樣生成訓練子集的過程中，一些樣本一直沒有被抽取，這些樣本所占初始數據集的比例為(1-1/N)N。當N取得足夠大時，(1-1/N)N收斂于1/e≈0.368，這些樣本構成袋外數據集(outside-of-bag data，OOB)。將每一棵決策樹的誤分率求平均得到隨機森林的OOB誤分率，就可以得到一個OOB誤差估計[15]。

1.4 隨機森林內嵌的特征選擇算法

Breiman提出過一種隱式的特征選擇算法，作為其隨機森林算法的一個副產品。該算法認為，當一個重要特征出現噪聲時，隨機森林分類的準確率會發生很大的變化；而當一個無關緊要的特征發生變化時，分類器預測的精度變動不大。所以通過人為地對測試集中的每一列特征值進行擾動，計算出原始袋外數據與修改后袋外數據預測準確率的差值，即可得出各個特征的重要性度量。假設有B棵樹，袋外數據為Loob，特征xj的特征重要性度量基于分類準確率的變化量計算，具體過程如下：

(1)B棵決策樹對應B個訓練子集，第b棵樹記為Tb。

(4)對于b=2,3,…,B,重復步驟1～3。

(5)特征xj的特征重要性度量Dj通過式7計算：

(7)

2 Hadoop環境下基于隨機森林的特征選擇算法

2.1 算法描述

文中提出的算法是MapReduce計算框架下基于隨機森林的特征選擇算法，該算法在隨機森林本來隱式的特征選擇方法的基礎上進行了改進。因為每棵樹在建模過程中抽樣選用的訓練子集不一樣，樹與樹之間有一定的差異性，它們對袋外數據預測的準確率不是完全可信，只能說具備一定的可信度，因此可以根據各棵樹的預測與集成隨機森林的預測的差異計算出每一棵樹的權重，再以這些權重對以上各個特征xj進行加權求和，得到最終的特征重要性度量的排序，以便接下來特征選擇時更傾向重要的特征。算法步驟如下：

(1)對原始數據集進行bootstrap重采樣，有放回地隨機抽取k個新的訓練子集，在沒有特征選擇的前提下構成了k棵分類回歸樹，未抽到的樣本構成袋外數據。

(2)使用每一棵樹對袋外數據Loob進行預測，在對每個特征xj的特征值進行擾亂后再預測得出每個特征的特征重要性度量Aij(i表示每個特征，j表示每棵樹)，同時，計算出集體隨機森林預測準確率的變化量Bi。

(3)計算每棵樹的權重aj。

(5)將特征按重要性度量從高到低排序，前50%隨機選擇70%的特征，后50%選擇30%的特征，兩部分混合后進行節點分裂的特征選取。

算法流程如圖1所示。

圖1 算法流程

2.2 權重度量

各棵樹的權重度量也是由袋外數據集測出，具體表現為每棵樹對袋外樣本集的預測與集體隨機森林對袋外樣本集預測的一致性，并不是只看每棵樹對樣本集預測的準確性，這一點充分體現了該算法以集體隨機森林的效果作為最重要的衡量點。權重的具體公式如下：

(8)

其中，Treeij表示第j棵樹對第i個袋外樣本的預測；Foresti表示集體隨機森林對第i個袋外樣本的預測；S表示袋外樣本的個數。

通過表1的7*7一致性度量矩陣展現權重計算的過程。

由表1可得各棵樹的權重：a1=0.857，a2=0.571，a3=0.571，a4=0.714，a5=0.571，a6=0.571，a7=0.571。

表1 權重度量過程

綜上可得最后的特征重要性度量為：

(9)

2.3 算法的MapReduce并行化實現

文中算法的并行化分為兩個階段，一個是訓練階段，一個是測試階段。訓練階段分為三個步驟：

(1)將訓練集分割成一個個數據塊block，然后將這些數據塊復制并分發到不同的子節點上。

(2)每個子節點上運行的Mapper任務根據其分區Partition上的數據塊block建立部分決策樹，也就是隨機森林的子集，生成一個包含這些樹的文件。

(3)從每個子節點所提交的文件中解析出其中包含的決策樹，生成輸出文件，這些決策樹的集合構成了整體的隨機森林。

測試階段分為六個步驟：

根據調查發現，社會道德與自我觀、個人觀與群體觀之間存在明顯的既定關系。當社會道德程度越高時，自我觀對于價值觀與道德判斷能力之間的認知能力也將會越強。且當群體觀占據主導作用時，個體觀具備的認知能力將會受到群體觀整體形勢的影響而出現對應改變。由此可以發現，價值觀與道德判斷力之間存在某種特定關系，即自我觀與群體觀發展程度較高時，價值觀與道德判斷力基本上可以趨于穩定狀態。相對而言，個體自我價值感在此階段的存在感將會嚴重下降。在此，筆者建議教師在對青少年進行價值觀教育時，必須協調好自我觀與群體觀之間的關聯性與平衡性，盡量不要出現某種傾向性過強的情況。

(1)將袋外數據集的一列列特征值打亂，改變后的數據集與原始的袋外數據集拼裝在一起，形成一個大測試集。

(2)將這個大測試集分割成獨立的數據塊block，然后把這些數據塊復制并分發到不同的子節點上。

(3)各個子節點上運行的Mapper任務根據上一階段建立的隨機森林模型對測試集中數據的類型進行預測，由多數投票表決來預測類別。

(4)對所有Mapper任務產生的預測進行匯總，生成最終的預測文件，預測文件包含各棵樹的預測結果，即形成一個i*k*(j+1)的矩陣，i為特征個數，j為樹的個數，k為袋外數據集的樣本個數，最后一列為隨機森林預測結果。

(5)將生成的大矩陣按照袋外數據集樣本個數k進行行的分割，從而得到每棵樹對應每個特征打亂后的測試集的預測情況。

(6)利用以上得到的值計算特征重要性度量，然后進行特征選擇。

3 仿真實驗

3.1 實驗環境

采用UCI數據庫中的KDD Cup99數據集，該數據集樣本數4 000 000個，特征個數為42，現在將其劃分為互不重疊的4組數據：D1、D2、D3、D4，如表2所示。

表2 實驗數據集

實驗中參數設置如下：maxDepth=unlimited，numFeatures=0.5NumAttrs，numTrees=80。其中maxDepth表示決策樹最大深度，numFeatures表示選擇特征的個數，numTrees表示隨機森林中決策樹的個數。

3.2 評估指標

accuracy用來衡量隨機森林對測試集的總體分類精度。實驗采用accuracy和加速比S來評估算法的性能，計算公式如下：

(10)

(11)

其中，TP表示正類被正確分為正類的數量；TN表示負類被正確分為負類的數量；FP表示負類被錯誤分為正類的數量；FN表示正類被錯誤分為負類的數量。Ts表示單機上實驗所花的時間；Tm表示Hadoop平臺m個節點上所花的時間。

3.3 實驗結果

表3展示了文中隨機森林算法、傳統隨機森林算法以及文獻[12]的Wrapper算法的分類精度對比。

表3 分類精度對比

從表3可以看出，文中隨機森林算法在D1、D2、D3、D4四個數據集上訓練和測試得到的分類準確性比傳統的隨機森林算法有了一定的提升，在D2數據集上分類精度的提升達到了7.2%。因為在建樹特征選擇的過程中，更傾向于選擇重要的特征，減輕了冗余特征對決策樹模型的干擾，從而提升了隨機森林的分類精度。此外，與Wrapper算法相比，發現文中算法除了在D3數據集上比Wrapper算法低了1.1%，其余都高于后者。因為文中算法在得出特征重要性排序的基礎上又引入了一定的隨機性，并不是完全選擇重要性排序靠前的那些特征，這樣可以減少決策樹之間的相關性，減少過擬合，從而一定程度上提高最終隨機森林的分類準確性。

文中算法的加速比曲線如圖2所示。

圖2 文中算法的加速比曲線

可以看出，當節點數為1時，加速比小于1，即Hadoop環境下的運行速度比單機運行的速度還慢。這是因為啟動Hadoop運行環境需要一定的時間，隨著節點數量的增加，對數據的處理速度加快，加速比提升。而當數據集較小時，加速比不是很理想，因為處理數據的時間較短，相對來說節點之間通信所花的時間較長。而隨著數據集漸漸增大，節點之間通信開銷的時間遠遠小于數據處理的時間，加速比得到大幅度提升，甚至接近線性增加，特別是在D4數據集上，加速比的增加量分別為0.75、0.74、0.73、0.65，基本上貼近線性增加。加速比實驗說明并行化的隨機森林更適合大數據量，相比于傳統單機模式下的隨機森林算法，文中算法在處理高維大數據上運行效率明顯提高。

4 結束語

提出了一種Hadoop環境下基于隨機森林的特征選擇算法，該算法在MapReduce計算框架下完成，對隨機森林算法中內置的特征選擇方法進行了改進。通過對袋外數據集每一列特征的干擾得到每棵樹對應每個特征的重要性度量，再將這些度量與各個決策樹的權重加權求和，得到最終各個特征的重要性度量。在特征選擇的過程中，一方面傾向重要性較大的特征，另一方面兼顧選擇的隨機性，減少決策樹之間的相關性，從而減少過擬合。實驗結果表明，該算法相比傳統的隨機森林算法或Wrapper特征選擇算法，分類性能得到了一定程度的提高；同時，由于MapReduce并行計算的應用，使得該算法對高維海量數據的處理有所提高，具備明顯的高效性和可擴展性。