結(jié)合信息論和范數(shù)的并行隨機(jī)森林算法

毛伊敏，耿俊豪

江西理工大學(xué) 信息工程學(xué)院，江西 贛州341000

分類算法是一種有監(jiān)督的學(xué)習(xí)算法，它能夠根據(jù)有標(biāo)記的信息發(fā)現(xiàn)分類規(guī)則、構(gòu)造分類模型，從而預(yù)測未含標(biāo)記的數(shù)據(jù)屬性特征。在分類算法中，隨機(jī)森林（random forest，RF）以其具有穩(wěn)定性強(qiáng)、對噪聲和異常值有較好容忍性等特點，近年來已被應(yīng)用于文本分類、環(huán)境預(yù)測、信用評估、生物信息、醫(yī)療診斷等領(lǐng)域，受到人們的廣泛關(guān)注。

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

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

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

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

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

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

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

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

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

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

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

1.2 相關(guān)算法介紹

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

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

2 PRFITN 算法

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

2.1 數(shù)據(jù)降維

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

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

特征選擇

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

（1）參數(shù)的初始化與特征矩陣的重構(gòu)

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

其中，″是由PCA 降維后得到的特征矩陣，與標(biāo)簽按列合并后得到轉(zhuǎn)換后的數(shù)據(jù)集DB″。

其次，采用支持向量機(jī)（SVM）算法以數(shù)據(jù)集DB″中所有樣本作為訓(xùn)練集獲得關(guān)于″的分類矩陣∈R，據(jù)此可以計算出″的預(yù)測標(biāo)簽為：

接著，為了評估在特征提取過程時信息的損失量，采用轉(zhuǎn)換矩陣對特征矩陣″進(jìn)行重構(gòu)，″的重構(gòu)矩陣X可以表示為：

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

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

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

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

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

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

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

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

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

（3）全局優(yōu)化函數(shù)

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

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

其中，和分別為和的權(quán)重參數(shù)。

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

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

特征提取

2.2 特征分組

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

（1）特征-標(biāo)簽、特征-特征間的影響程度

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

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

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

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

（2）特征評判函數(shù)

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

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

其中，為函數(shù)(x;)的權(quán)重參數(shù)。

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

（3）特征分組

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

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

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

③迭代執(zhí)行步驟②，直到中特征個數(shù)達(dá)到閾值時為止，其余特征自行組成特征集。

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

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

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

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

FGSIT 策略的執(zhí)行過程如下所示：

FGSIT 策略

2.3 并行構(gòu)建隨機(jī)森林

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

（1）RSKP 策略

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

圖1 RSKP 策略Fig.1 RSKP strategy

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

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

（2）并行構(gòu)建隨機(jī)森林、預(yù)測數(shù)據(jù)集分類

通過RSKP 策略得到了優(yōu)化后的MapReduce 模型，結(jié)合該模型，并行構(gòu)建隨機(jī)森林具體分為四步，由圖2 所示。

圖2 并行構(gòu)建隨機(jī)森林Fig.2 Construct random forests in parallel

①調(diào)用Hadoop 默認(rèn)的數(shù)據(jù)塊策略，將數(shù)據(jù)集DB劃分成大小相同的數(shù)據(jù)塊Block 并將其作為輸入數(shù)據(jù)傳輸?shù)組apper節(jié)點中。

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

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

④將Mapper 節(jié)點中預(yù)測得到的鍵值對由主節(jié)點分配后傳入相應(yīng)的Reducer 節(jié)點再次合并，得到全局分類結(jié)果，并與標(biāo)簽比較得到模型的準(zhǔn)確度。

至此，并行構(gòu)建隨機(jī)森林的執(zhí)行過程如下所示：

并行構(gòu)建隨機(jī)森林

2.4 PRFITN 算法步驟

PRFITN 算法的具體實現(xiàn)步驟如下：

通過Hadoop 默認(rèn)的文件塊策略，將原始數(shù)據(jù)集劃分成大小相同的文件塊Block，調(diào)用一次MapReduce 任務(wù)并行計算原始數(shù)據(jù)特征的信息增益，在此基礎(chǔ)上對特征進(jìn)行選擇。

調(diào)用FEKFN 策略以迭代的方式對特征選擇后的數(shù)據(jù)集進(jìn)行新特征的提取。

調(diào)用FGSIT 策略對降維后的數(shù)據(jù)集進(jìn)行特征分組。

啟動新的MapReduce 任務(wù)，調(diào)用Map 函數(shù)，采用bootstrap 和分層抽樣的方法抽取建模所用的訓(xùn)練樣本及特征，構(gòu)建決策樹，匯總所有決策樹得到隨機(jī)森林；采用RSKP 策略均勻分配Reducer 節(jié)點任務(wù)，調(diào)用Reduce 函數(shù)得到全局分類結(jié)果，并評估模型分類準(zhǔn)確率。

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

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

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

在數(shù)據(jù)降維的特征提取階段，時間復(fù)雜度主要取決于迭代優(yōu)化轉(zhuǎn)換矩陣以及分類矩陣的過程，已知為×階矩陣，為×1 階矩陣，假設(shè)該階段需要迭代計算次，則時間復(fù)雜度為：

因此，數(shù)據(jù)預(yù)處理的時間復(fù)雜度為：

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

在并行構(gòu)建隨機(jī)森林階段，主要調(diào)用MapReduce任務(wù)并行構(gòu)建隨機(jī)森林模型以及預(yù)測全部數(shù)據(jù)的分類從而評估準(zhǔn)確率。假設(shè)隨機(jī)森林模型包含棵決策樹，且執(zhí)行MapReduce 任務(wù)時對應(yīng)的Mapper 節(jié)點個數(shù)為，Reduce 節(jié)點個數(shù)為，則該階段的時間復(fù)雜度為：

因此，PRFITN 算法的時間復(fù)雜度為：

3 實驗結(jié)果及比較

3.1 實驗環(huán)境

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

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

3.2 實驗數(shù)據(jù)

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

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

3.3 PRFITN 算法的性能分析

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

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

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

3.4 PRFITN 算法的性能比較

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

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

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

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

圖5 四種算法在不同數(shù)據(jù)集上的準(zhǔn)確度Fig.5 Accuracy of four algorithms on different datasets

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

4 總結(jié)

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