Hadoop環(huán)境下基于隨機森林的特征選擇算法

張 鑫，吳海濤，曹雪虹

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

0 引 言

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

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

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

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

1 隨機森林預(yù)備知識

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

1.1 決策樹

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

所以最優(yōu)的劃分屬性應(yīng)該選擇基尼指數(shù)最小的屬性。

1.2 隨機森林生成過程

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

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

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

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

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

1.3 隨機森林衡量標(biāo)準(zhǔn)

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

(6)

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

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

1.4 隨機森林內(nèi)嵌的特征選擇算法

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

(1)B棵決策樹對應(yīng)B個訓(xùn)練子集，第b棵樹記為Tb。

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

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

(7)

2 Hadoop環(huán)境下基于隨機森林的特征選擇算法

2.1 算法描述

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

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

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

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

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

算法流程如圖1所示。

圖1 算法流程

2.2 權(quán)重度量

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

(8)

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

通過表1的7*7一致性度量矩陣展現(xiàn)權(quán)重計算的過程。

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

表1 權(quán)重度量過程

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

(9)

2.3 算法的MapReduce并行化實現(xiàn)

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

(1)將訓(xùn)練集分割成一個個數(shù)據(jù)塊block，然后將這些數(shù)據(jù)塊復(fù)制并分發(fā)到不同的子節(jié)點上。

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

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

測試階段分為六個步驟：

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

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

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

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

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

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

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

3 仿真實驗

3.1 實驗環(huán)境

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

表2 實驗數(shù)據(jù)集

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

3.2 評估指標(biāo)

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

(10)

(11)

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

3.3 實驗結(jié)果

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

表3 分類精度對比

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

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

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

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

4 結(jié)束語

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