汪力純，劉水生

（1.南京工程學(xué)院信息與通信工程學(xué)院，江蘇 南京 211167 2.江蘇省煙草專賣局信息中心，江蘇 南京 210018）

隨著信息全球化以及數(shù)字信息急速地增長，數(shù)據(jù)挖掘領(lǐng)域［1］受到了人們的廣泛關(guān)注。其中，該領(lǐng)域的分類算法是研究的重點，分類主要是對獲取到的數(shù)據(jù)運用一定的算法規(guī)則預(yù)測未知數(shù)據(jù)的對應(yīng)類別，通常在分類預(yù)測問題上常用隨機森林算法來建立分類模型，實現(xiàn)分類結(jié)果的預(yù)測［2］。

隨機森林［3］主要是由多棵決策樹組合而成的一種集成分類模型，與其他傳統(tǒng)的單分類器相比有更高的分類精度和更低的泛化誤差，對異常值有較好的容忍度。但是，在信用貸款［4］、電信欺詐［5］和醫(yī)療診斷［6］等實際生活中產(chǎn)生的數(shù)據(jù)一般都具備高維不平衡的特征，而原始隨機森林算法在針對高維不平衡數(shù)據(jù)［7］做分類預(yù)測時，構(gòu)建的分類模型復(fù)雜，容易發(fā)生過擬合現(xiàn)象，導(dǎo)致預(yù)測結(jié)果偏向于多數(shù)類，分類精度顯著降低，且算法訓(xùn)練時間變長，計算過程變得更為復(fù)雜。

當下，業(yè)界關(guān)于對高維不平衡數(shù)據(jù)的分類問題，主要從數(shù)據(jù)的高維度及不平衡性等兩方面作為切入點，憑借數(shù)據(jù)與算法兩個層面來盡可能改善模型的分類精度。其中，在數(shù)據(jù)層面上，主要憑借過采樣或欠采樣等方式來處理不平衡數(shù)據(jù)。例如 Ha等［8］提出了基于遺傳算法的欠采樣GAUS算法來均衡數(shù)據(jù)集和楊毅等［9］提出了Borderline?SMOTE算法只對分布在邊界的少數(shù)類進行過采樣以達到數(shù)據(jù)的均衡。算法層面主要是對現(xiàn)有的算法進行改進優(yōu)化，使改進后的算法可以更好地處理高維數(shù)據(jù)，即對高維數(shù)據(jù)進行降維處理，主要包括特征選擇和特征提取兩種。例如Guo等［10］提出的特征選擇與 Adaboost相結(jié)合的集成學(xué)習(xí)算法，通過篩選出重要特征組成新的特征子集，以此達到降維的目的。因此，針對高維不平衡數(shù)據(jù)的分類問題，結(jié)合數(shù)據(jù)和算法兩個層面對原始隨機森林進行優(yōu)化與改進，提出了改進的隨機森林算法HF_RF。首先通過SMOTE算法和隨機欠采樣相結(jié)合的方式對高維不平衡數(shù)據(jù)集進行預(yù)處理，同時引入聚類算法對SMOTE算法進行改進，提高對負類樣本的處理性能；然后通過Relief F算法對平衡后的高維數(shù)據(jù)進行特征加權(quán)，遞歸地剔除不相關(guān)和冗余特征，篩選出有效的維度較低的子集以提高分類精度和效率；最后采用加權(quán)投票原則進一步提高算法的分類性能。

1 相關(guān)工作

根據(jù)相關(guān)研究文獻可以看出，隨機森林算法具備很多其他機器學(xué)習(xí)算法沒有的優(yōu)點，它能處理大規(guī)模數(shù)據(jù)，預(yù)測精度不受數(shù)據(jù)丟失的影響，輸入特征可以是離散數(shù)據(jù)，也可以是連續(xù)數(shù)據(jù)。算法的精度高于單一的決策樹分類算法，一定程度上避免了過擬合問題，同時能夠較好地處理噪聲和異常值。但是隨機森林仍然存在著許多不足之處：一方面，在處理有較多特征冗余和不平衡的數(shù)據(jù)集時，算法會將少數(shù)類樣本錯分為多數(shù)類，此時選用不恰當?shù)脑u價標準就會導(dǎo)致假高分類精度的情況，同時會降低單棵決策樹的分類精度，導(dǎo)致算法整體性能下降；另一方面，預(yù)測投票階段為每棵決策樹都賦予相同的權(quán)重，導(dǎo)致分類性能差的決策樹影響最終整體的分類結(jié)果。

近年來研究人員針對原有的隨機森林算法存在的缺點和在實際應(yīng)用中的不足進行了相關(guān)改進。Zhu等［11］提出一種基于隨機森林的類權(quán)重投票算法（CWsRF），該算法為每個類賦予單個權(quán)重，以充分區(qū)分少數(shù)類和多數(shù)類，但是會導(dǎo)致數(shù)據(jù)過度冗余。Mashayekhi等［12］提出一種基于爬山策略的貪婪方法，該方法選擇一組精度高、相似度低的決策樹來改進隨機森林算法，實驗證明改進算法的分類精度得到大幅提高，但在處理高維不平衡數(shù)據(jù)方面依然存在缺陷。Gregorutti等［13］提出一種遞歸特征消除（RFE）算法，利用隨機森林的置換重要性測量算法計算決策樹之間的相關(guān)性對特征置換的影響，計算特征權(quán)重，遞歸刪除權(quán)重低的特征。胡瑋［14］針對隨機森林建立分類模型時間較長的缺點，在改進的領(lǐng)域粗糙集屬性約簡算法的基礎(chǔ)上，對隨機森林算法進行了改進，該方法有效減輕過擬合問題，但會導(dǎo)致結(jié)果產(chǎn)生偏向性。黃青平等［15］利用模糊聚類對隨機森林進行改進，用相似度高的樣本訓(xùn)練隨機森林預(yù)測模型，提高了算法的預(yù)測精度。房曉南等［16］采用SMOTE算法計算出一批少數(shù)類樣本，降低了數(shù)據(jù)的不平衡程度，然而該方法不能保證偽樣本的類型正確性。

以上的改進算法大多都是從算法或數(shù)據(jù)的單一層面出發(fā)來提高算法的分類性能，不能同時兼顧數(shù)據(jù)高維和不平衡的特征。本文提出的基于混合采樣和特征選擇的改進隨機森林算法主要結(jié)合數(shù)據(jù)和算法兩個層面對原始隨機森林算法進行優(yōu)化改進，使改進后的算法可以更好地處理生活中最常出現(xiàn)的高維不平衡數(shù)據(jù)。雖然改進后的算法提高了針對高維不平衡數(shù)據(jù)的分類精度，但是因為改進算法的時間復(fù)雜度增加，使得算法的整體計算效率一定程度的降低，今后的研究方向?qū)槍δ壳按嬖诘牟蛔阕龀鲞M一步改進。

2 隨機森林算法

隨機森林是一種集成學(xué)習(xí)算法［17］，它是一個由多棵決策樹共同參與的集成分類器。隨機森林中的每棵決策樹都是基于Bootstrap抽樣得到的，然后將多棵決策樹組合之后通過投票由得票多的類別作為最終分類結(jié)果。隨機森林的構(gòu)建過程如下：

假設(shè)原始訓(xùn)練數(shù)據(jù)集D中，n為樣本數(shù)量，M為特征總數(shù)，所需構(gòu)建的決策樹數(shù)量為k。

（1）抽取訓(xùn)練子集。從原始訓(xùn)練集D中有放回地隨機選取n個樣本，并重復(fù)n次，其他的則構(gòu)成袋外數(shù)據(jù)集OOB。

（2）構(gòu)建決策樹。先在M個特征中隨機抽取m個組成特征子集（m＜M），然后利用相關(guān)準則選擇最佳分割點，將其劃分為子節(jié)點，同時將訓(xùn)練集劃分到相應(yīng)節(jié)點中，重復(fù)地逐層劃分，最終得到所有節(jié)點。

（3）隨機森林生成。循環(huán)執(zhí)行步驟（2），直至建立 k棵決策樹，以構(gòu)成隨機森林｛ti，i＝1，2，…，k｝。

（4）通過借助隨機森林中k棵決策樹來分類預(yù)測測試集，最終得到 k 個預(yù)測結(jié)果 ｛t1（x），t2（x），…，tk（x）｝。

（5）把各決策樹預(yù)測結(jié)果的眾數(shù)作為各樣本最終的預(yù)測結(jié)果。

3 算法改進

然而需要指出的是，借助隨機森林算法來處理高維不平衡數(shù)據(jù)時，主要具有以下不足：（1）在處理高維數(shù)據(jù)時稍顯冗余，且極易忽略一部分類強相關(guān)特征，同時還會加大算法的時間復(fù)雜度；（2）在處理不平衡數(shù)據(jù)時，分類結(jié)果較偏向于多數(shù)類，使得算法分類精度降低。因此，為了解決特征之間的冗余且數(shù)據(jù)分布不均衡問題，提高算法的分類精度，本文提出了基于混合采樣和特征選擇相結(jié)合的改進隨機森林算法HF_RF。首先通過改進的SMOTE算法和隨機欠采樣相結(jié)合的方式對高維不平衡數(shù)據(jù)集進行預(yù)處理，達到均衡原始數(shù)據(jù)集的目的；然后通過Relief F算法對均衡后的高維數(shù)據(jù)進行特征加權(quán)和維度約簡，篩選出有效的維度較低的子集訓(xùn)練決策樹；最后采用加權(quán)投票原則進一步提高算法的分類性能。

3.1 基于改進的SMOTE算法的混合采樣

SMOTE算法［18］主要是在少數(shù)類樣本中隨機插入人造的正類樣本使類間分布平衡，提高分類器在測試集上的分類性能。SMOTE算法大致執(zhí)行過程如下：在處理正類樣本X時，確定最接近正類樣本X的k個近鄰樣本，再從此k個近鄰樣本中隨機選擇m個樣本，然后針對這m個樣本中的每一個樣本Xi（i＝1，2，…，m），按照式（2） 生成新的人造樣本點。

式中，rand（0，1）表示產(chǎn)生一個0到1的隨機數(shù)。

雖然SMOTE算法之前的采樣方法可以均衡數(shù)據(jù)集，但因為隨機采樣缺乏原則，不能考慮到邊緣數(shù)據(jù)的分布狀態(tài)，容易產(chǎn)生邊界模糊的問題［19］，導(dǎo)致采樣效果不理性。針對以上問題，在此次研究中，引入了聚類算法［20］來改進SMOTE算法，大致實現(xiàn)流程如下：先借助聚類算法對少數(shù)類實施聚類操作，以確定少數(shù)類中各簇的分布狀態(tài)，然后計算各個簇的簇心，在簇內(nèi)簇心與簇內(nèi)樣本的連線上根據(jù)式（3）進行插值增加人造樣本數(shù)據(jù)，這樣能很好地解決邊界模糊問題。

式中，Xnew為新插值的樣本，ci為簇心，X是以ci為簇心聚類中的原始樣本。

基于改進SMOTE算法的混合采樣具體步驟如下：

（1）依次計算多數(shù)類與少數(shù)類樣本的采樣數(shù)量，假設(shè)樣本集D中的多數(shù)與少數(shù)類樣本數(shù)分別為M與N，混合比列系數(shù)為?，則混合采樣數(shù)量Pmix的計算公式為

其中欠采樣的數(shù)量PM＝Pmix??，過采樣的數(shù)量 PN＝Pmix?（1-?）。

（2）針對多數(shù)類與少數(shù)類，分別采取欠采樣與過采樣的方式進行處理，從而分別得到全新數(shù)據(jù)集Mnew與Nnew。

（3）合并以上新得到的兩數(shù)據(jù)集Mnew與Nnew，從而得到平衡數(shù)據(jù)集Dnew。

3.2 Relief F算法與隨機森林結(jié)合

在已有的特征選擇［21］方法中，Relief算法［22］避免使用全局搜索方法，僅根據(jù)特征間的關(guān)聯(lián)性來賦予對應(yīng)的權(quán)重，根據(jù)權(quán)重的大小來排列對應(yīng)特征，并把權(quán)重值高于閾值的特征作為特征子集，為一種簡單高效的Filter型特征選擇算法［23］。正因為如此，使得Relief算法被廣泛應(yīng)用于海量高維數(shù)據(jù)中。但是Relief算法只能處理二分類問題，當數(shù)據(jù)存在缺失以及噪聲時，Relief不能對其進行良好的處理，因此為解決上述問題，學(xué)者們提出了ReliefF算法。該算法可以更好地處理多分類問題。

ReliefF算法的大致流程如下：先把訓(xùn)練集D中各樣本的所有特征權(quán)值設(shè)為0，再從訓(xùn)練集樣本D中隨機選取樣本R，依次選擇R的k個同類與不同類最近鄰樣本，得出對應(yīng)特征的權(quán)重值，最后重復(fù)m次后通過求取平均值的方法計算最終的權(quán)重值，求出各個特征與類的相關(guān)性權(quán)重W后，將其按降序排列。Relief F算法的權(quán)重計算公式為

式中，W（Aj）表示特征Aj的權(quán)重，p（C）表示第C類目標的概率；diff（Aj，R，Hi） 為兩個樣本 R 與 Hi在特征Aj上的差，其計算公式為

式中，R［Aj］表示樣本 R在特征 Aj下的樣本值，Hi［Aj］表示樣本Hi在特征Aj下的樣本值。

diff（Aj，R，Mi（C）） 是兩個樣本R與Mi（C） 在特征Aj上的差，其中Mi（C）表示類C中與樣本R的第i個最近鄰樣本，C表示與R所在類不同的類；class（R）表示樣本R所在類；p（class（R））表示R所在類的概率。

由于隨機森林算法在構(gòu)建決策樹時會隨機選擇部分特征值，最終導(dǎo)致過多冗余特征被選中，降低單棵決策樹的精度。因此本文通過Relief F算法剔除樣本集中的無用特征，按照權(quán)值大小將剩余特征均勻分到高、中、低3個區(qū)域中，最終通過獲取的3個特征區(qū)域來訓(xùn)練決策樹，得到隨機森林分類模型，達到提高分類精度的目的。具體流程如圖1所示。

圖1 Relief F算法結(jié)合隨機森林流程圖

3.3 加權(quán)隨機森林

隨機森林算法在分類問題的預(yù)測方面采用的是眾數(shù)投票法［24］，即統(tǒng)計每種分類標簽得到各棵決策樹的相應(yīng)票數(shù)，將投票數(shù)最多的作為最終的預(yù)測結(jié)果。該投票法忽略了不同決策樹之間的強弱差異，無法增強隨機森林中分類性能優(yōu)秀的決策樹對投票結(jié)果的影響，最終導(dǎo)致具備優(yōu)秀分類性能的決策樹被分類性能較差的決策樹所影響使算法的分類效果降低。因此，為了進一步提高隨機森林算法的分類預(yù)測性能，本文在構(gòu)建決策樹時，利用OOB袋外數(shù)據(jù)判斷決策樹分類精度，為各棵決策樹賦予不同的權(quán)重，增強分類性能優(yōu)秀的決策樹在投票時的比重，同時降低分類性能較差的決策樹的比重，以此提高隨機森林分類模型的分類精度。

加權(quán)隨機森林的具體步驟如下：

（1）憑借Bagging算法，隨機抽樣均衡處理后的數(shù)據(jù)集N，以得到樣本子集。同時會存在未被抽取的OOB數(shù)據(jù)，OOB中每個樣本沒有被抽到的概率約等于0.368，如式（7）所示。

當 N→∞時，P≈0.368。

（2）設(shè)T為訓(xùn)練完成的K棵決策樹分類器集合，通過OOB數(shù)據(jù)得到每棵決策樹對OOB數(shù)據(jù)的正確分類的比率。

（3）計算各棵決策樹的權(quán)重值，計算公式為

（4）選出權(quán)重最高的作為最終分類結(jié)果。

3.4 混合采樣和特征選擇結(jié)合的改進隨機森林算法HF_RF

相較于原始隨機森林算法，HF_RF算法主要有效以下優(yōu)點：第一，從數(shù)據(jù)層面出發(fā)，針對原始隨機森林算法在處理不平衡數(shù)據(jù)集方面，分類結(jié)果較偏向于多數(shù)類，算法分類準確率不高等問題，憑借結(jié)合改進的SMOTE算法和隨機欠采樣，來預(yù)處理數(shù)據(jù)集，以確保數(shù)據(jù)集達到均衡狀態(tài)；第二，從算法層面出發(fā)，針對高維數(shù)據(jù)集中存在特征冗余，原始隨機森林在處理時增加了算法的時間復(fù)雜度等問題，引入了Relief F算法與隨機森林相結(jié)合，對高維數(shù)據(jù)進行特征約減；第三，利用OOB數(shù)據(jù)對決策樹賦予不同的權(quán)重，進一步提高改進算法的分類性能。HF_RF算法的流程如圖2所示。

圖2 HF_RF算法的流程圖

4 實驗與結(jié)果分析

4.1 評價指標

正確率通常為評估傳統(tǒng)分類算法分類性能最重要的指標。但是，在高維不平衡數(shù)據(jù)集中，正確率不能準確提供少數(shù)類的精度，而高維不平衡數(shù)據(jù)的重點在于對少數(shù)類的處理上，所以需要引入其他評價指標來判斷算法的分類性能。因此對于高維不平衡數(shù)據(jù)一般采用查全率 Recall、F?measure、AUC值等作為評價標準，這些評價標準都是在混淆矩陣的基礎(chǔ)上建立的?；煜仃嚾绫?所示。

表1 混淆矩陣

其中，TP、FN分別表示的含義是正確與錯誤預(yù)測的正類，F(xiàn)P、TN分別表示錯誤與正確預(yù)測的負類，進而可得樣本總數(shù)N＝TP+FP+FN+TN。

（1）Recall查全率，其含義為被正確預(yù)測的少數(shù)類樣本占比。其中，正確預(yù)測少數(shù)類的樣本的識別率與查全率之間成正比關(guān)系，因此Recall可以用來評價分類算法對少數(shù)類的性能，公式為

（2）F?measure為一個全新的評價指標，其綜合了查全率和查準率兩種標準，算法對于少數(shù)類的分類精度和F?measure的值同樣成正比關(guān)系，公式為

4.2 實驗數(shù)據(jù)集

此次研究所涉及的數(shù)據(jù)集，來自于美國加州大學(xué)UCI所公開的數(shù)據(jù)集。其中，糖尿病導(dǎo)致的視網(wǎng)膜病變數(shù)據(jù)集與甲狀腺疾病數(shù)據(jù)集為特征數(shù)少且分布較均衡的數(shù)據(jù)集；而衛(wèi)星與麝香區(qū)分數(shù)據(jù)集為特征數(shù)多且分布不均衡的數(shù)據(jù)集；最后頁面塊分類數(shù)據(jù)集為分布極不平衡的數(shù)據(jù)集。以上5個數(shù)據(jù)集可以充分展現(xiàn)HF_RF算法在處理高維不平衡數(shù)據(jù)上的分類性能。具體參數(shù)如表2所示。

表2 數(shù)據(jù)集的具體參數(shù)

4.3 實驗過程

此次實驗環(huán)境的硬件方面配置如下：Intel（R）Core（MT） i7?4600U CPU@2.10 GHz處理器、8 GB內(nèi)存、64位Windows 10企業(yè)版操作系統(tǒng)。而軟件環(huán)境如下：Java環(huán)境，WEKA開放源碼包。

實驗時隨機森林決策樹個數(shù)初始定為N＝100，取樣次數(shù)m，少數(shù)類個數(shù)為k；改進SMOTE算法對于數(shù)據(jù)集中的少數(shù)類過采樣時，將聚類算法的迭代次數(shù)最大值設(shè)置為50，隨機選取5個點作為簇心開始聚類和插值操作。

本次實驗主要是為了驗證本文提出的HF_RF改進算法在處理高維不平衡數(shù)據(jù)時的分類性能，因此利用目前常見的從數(shù)據(jù)層面出發(fā)的基于改進混合采樣的隨機森林算法HSRF和從算法層面出發(fā)的基于改進Relief F的隨機森林算法R_RF這兩種算法與本文提出的HF_RF算法分別對5個高維不平衡數(shù)據(jù)集進行分類，對比各自的查全率、F?measure和AUC指標以及相關(guān)參數(shù)來驗證分類性能。

4.4 實驗結(jié)果分析

實驗對比了3種算法關(guān)于以上5個數(shù)據(jù)集的評價指標，最終實驗結(jié)果如表3所示。

表3 3種算法在5個數(shù)據(jù)集上的評價指標 %

將5個數(shù)據(jù)集在3種算法中的各性能指標繪制成折線圖，分別如圖3、圖4和圖5所示。

圖3 查全率

圖4 F?measure

圖5 AUC值

根據(jù)性能指標折線圖可以看出HSRF算法和HF_RF算法在查全率、F?measure和AUC值都高于R_RF算法，由此看出僅僅降低數(shù)據(jù)集中的特征數(shù)不對數(shù)據(jù)集進行均衡處理，分類性能提升并不明顯。其中DB、PG、TD數(shù)據(jù)集中的特征數(shù)相對較少，從結(jié)果可以看出HSRF算法雖然在不平衡數(shù)據(jù)的處理上有所提高，但沒有HF_RF算法在處理不平衡數(shù)據(jù)集上的性能好，而對于SL、MUSK這類特征數(shù)多的不平衡數(shù)據(jù)集，改進算法達到了很好的分類效果。

從圖3可以看出，隨著數(shù)據(jù)集不平衡程度的增加，對數(shù)據(jù)進行預(yù)處理的改進算法的查全率也有一定程度的提高，因此查全率可以很好地反映算法對少數(shù)類的分類性能，HSRF算法與R_RF算法相比，通過混合采樣來達到數(shù)據(jù)均衡，一定程度提高了算法的分類性能，而HF_RF算法對不平衡數(shù)據(jù)的整體分類性能更高。從圖4可以看出，PG數(shù)據(jù)集的不平衡度最高，R_RF算法對于該數(shù)據(jù)集的分來效果較差，F(xiàn)?measure值為79.3%，在通過改進算法HF_RF算法訓(xùn)練之后得到的分類模型的F?measure值提高到了92.3%，提高了 13%。結(jié)合表 4可以看出，HSRF算法對于數(shù)據(jù)集中的特征數(shù)沒有改進作用，不能達到特征約減的目的，只能一定程度地平衡數(shù)據(jù)集，而R_RF算法和HF_RF算法都能一定程度地刪除數(shù)據(jù)集中的冗余特征。

表4 3種算法特征數(shù)對比

從圖5的AUC值可以看出HF_RF算法在通過混合采樣和特征選擇對算法進行多層改進后，與其他兩種算法相比AUC值有明顯的提升，AUC曲線整體在其他算法之上，最高達到了95.6%。本文提出的HF_RF算法不僅可以很好地均衡數(shù)據(jù)集，還能進一步削減冗余特征，提高模型的分類性能。

綜上所述，相比于HSRF算法和R_RF算法，改進的HF_RF算法不論是在特征約減，還是在數(shù)據(jù)均衡方面的總體分類效果都有所提高，但是在算法的整體運行時間上，3種算法的時間差異表現(xiàn)不明顯，下一步可以在算法中引入并行化策略作為后面的主要研究方向，有效地降低算法的時間復(fù)雜度。

5 結(jié)束語

在此次研究中，針對隨機森林算法在分類預(yù)測特征維度高且不平衡的數(shù)據(jù)時，所表現(xiàn)出的低性能問題進行了一定的改進，最終建立了HF_RF算法。首先針對原始隨機森林算法在處理不平衡數(shù)據(jù)集方面，存在分類準確率低的問題，通過改進的SMOTE算法與隨機欠采樣相結(jié)合的混合采樣策略對數(shù)據(jù)集進行預(yù)處理；然后針對高維數(shù)據(jù)集中存在特征冗余，原始隨機森林在處理時增加了算法的時間復(fù)雜度等問題，引入了Relief F算法與隨機森林相結(jié)合，對高維數(shù)據(jù)進行特征約減；最后利用OOB數(shù)據(jù)對決策樹賦予不同的權(quán)重，進一步提高改進算法的分類性能。結(jié)果表明，改進的隨機森林算法HF_RF在處理高維不平衡數(shù)據(jù)方面的分類預(yù)測性能高于其他分類算法。然而HF_RF算法也存在一些缺陷，雖然對高維數(shù)據(jù)進行了特征約減一定程度上降低了時間復(fù)雜度，但是算法的整體運行時間與其他算法相比沒有顯著優(yōu)勢，所以下一步在不影響分類性能的前提下引入并行化策略進一步提高算法的運行效率。