羅計根，杜建強，聶 斌，李 歡，聶建華，陳裕鳳

1.江西中醫(yī)藥大學 計算機學院，南昌330004

2.江西中醫(yī)藥大學 中醫(yī)學院，南昌330004

1 引言

不平衡數(shù)據(jù)集一般是指不同類別下的數(shù)據(jù)量有較大的差異，小類樣本的數(shù)量非常少，或者相對大類樣本來說，小類樣本的數(shù)量較少。不平衡數(shù)據(jù)的分類問題具有非常重要的現(xiàn)實意義，在銀行信用卡欺詐檢測、醫(yī)學癌癥檢測等方面都有重要應(yīng)用[1]，是機器學習和數(shù)據(jù)挖掘領(lǐng)域的研究熱點。目前，常用的分類算法大多數(shù)是基于平衡數(shù)據(jù)考慮的，面對不平衡數(shù)據(jù)的分類時，這些分類算法可能有較高的分類準確率，但對小類樣本的識別能力相對較差。

為了能夠在不平衡的數(shù)據(jù)集上有較好的分類效果，國內(nèi)外的學者主要從數(shù)據(jù)預處理、分類算法改進等方面展開了研究[2]。數(shù)據(jù)預處理主要是對不平衡數(shù)據(jù)進行處理，使類別之間的數(shù)據(jù)樣本達到某種平衡，采用的策略包括過采樣（Over-Sampling）[3]和欠采樣（Under-Sampling）[4]兩種方法。

在過采樣方法中，較為成熟的是Chawla等人[5]提出的小類樣本合成重采樣技術(shù)（Synthetic Minority Oversampling Technique，SMOTE）算法。該方法通過在相同類的連線上隨機構(gòu)造不重復的樣本，減少分類器的過擬合，但SMOTE算法很難有效控制樣本數(shù)據(jù)和樣本類別。對此，學者相繼進行了改進，Han 等人[6]提出Borderline-SMOTE 算法，該方法的主要思想是尋找邊界區(qū)域后插值，使生成的樣本更有效，但無法找出全部的邊界點。Bunkhumpornpat 等人[7]在Borderline-SMOTE 基礎(chǔ)上進行改進，提出計算小類樣本的安全水平（Safe-level-SMOTE），但該方法容易過擬合。國內(nèi)學者提出利用空間結(jié)構(gòu)信息的N-SMOTE 過抽樣算法[8]、核SMOTE[9]等。文獻[10]提出根據(jù)聚類獲得的樣本中心進行插值的算法。文獻[11]提出將模糊最近鄰和SMOTE算法結(jié)合，分類效果有所改善。近期，文獻[12]提出噪聲濾波SMOTE算法，加入馬氏距離的MDO算法等[13]。馬驪等人[14]提出CURE-SMOTE，針對SMOTE 的缺點進行改進。SMOTE 算法的改進較多，但是至今沒有較為完善的方法。

欠采樣是隨機性減少大類樣本數(shù)量，該方法思想簡單，操作容易，但存在去除樣本的盲目性和去除樣本比例參數(shù)不確定性等問題，并且由于代表性樣本的丟失而影響分類精度。其中，Tomek[15]提出了Tomek Links 方法，能夠去除噪音數(shù)據(jù)和邊緣數(shù)據(jù)，但是該方法計算復雜度較大。Wilson等人[16]提出了改進的Tomek Links方法，使用歐氏距離來計算類間距離，減少計算量，并且生成新的數(shù)據(jù)集。Hart[17]提出壓縮近鄰法來精簡多數(shù)類樣本。郭穎婕等人[18]提出了一種利用隨機森林分類器和K-Means 聚類降采樣方法的抗性基因識別算法。該方法通過將大量樣本聚類，從每個簇中選擇單個樣本與小類樣本合并形成平衡樣本集，但該方法僅使用每個簇的聚類中心，一定程度上降低了訓練樣本的多樣性，且只能針對連續(xù)型樣本。

為解決隨機森林分類效果受樣本集類間不平衡、類內(nèi)不規(guī)則的影響，并提高訓練樣本的多樣性，本文提出一種聚類欠采樣策略的隨機森林優(yōu)化方法（Random Forest Optimization Method Based on Cluster Under-Sampling Strategy，CUSRF）。該方法利用聚類方法對大類樣本聚類，形成與小類樣本個數(shù)相同的簇類數(shù)，從每個簇中有放回隨機抽取單個樣本與小類樣本形成平衡樣本集，再利用有放回抽樣方法從平衡樣本集中抽取單棵決策樹的訓練集；重復該過程多次，直至構(gòu)建完隨機森林。該方法利用K-Modes和K-Means聚類方法分別對離散型和連續(xù)型數(shù)據(jù)聚類，并結(jié)合隨機森林強大的分類能力，解決樣本類間不平衡與類內(nèi)不規(guī)則的問題，使得訓練樣本集更具多樣性，提高算法的分類能力。

2 基于聚類欠采樣策略的隨機森林優(yōu)化方法

本文提出的基于聚類欠采樣策略的隨機森林優(yōu)化方法一共分成兩部分：

（1）利用聚類算法對原始大類樣本聚類。針對離散型和連續(xù)型數(shù)據(jù)的非平衡數(shù)據(jù)集，分別采用K-Modes聚類方法[19]和K-Means 聚類方法[20]對其聚成k 個子類簇，從每個子類簇中有放回地隨機抽取1 個樣本，則共抽取k 個樣本，將這k 個樣本與小類樣本合并形成平衡樣本集。為了使大類樣本和小類樣本數(shù)量達到平衡，這里的k 為小類樣本數(shù)量。此時平衡樣本集中的樣本個數(shù)為2k 個，大類樣本和小類樣本的樣本比例為1∶1。

（2）對平衡樣本集的隨機森林構(gòu)建。對平衡樣本集采用有放回抽樣方法抽取2k 次，將抽取到的數(shù)據(jù)作為單棵決策樹的訓練樣本集，并完成決策樹的構(gòu)建。

通過上述兩部分的介紹，本文提出的聚類欠采樣策略的隨機森林優(yōu)化方法有兩處隨機，從而提高了訓練樣本的多樣性，能有效解決樣本不平衡給分類帶來的準確率低下的問題。

2.1 聚類算法

針對不同的數(shù)據(jù)類型，聚類算法在選擇上也存在差異。對離散型數(shù)據(jù)而言，采用K-Modes聚類方法，先確定聚類個數(shù)k；然后隨機選擇k 個聚類中心；計算每個樣本與這k 個聚類中心的距離，將樣本劃分到與之距離最近的一個聚類中心所在類別中；當所有樣本劃分完成之后，重新計算每個簇中的聚類中心，不斷重復，直到每個聚類中心不再改變?yōu)橹?。在K-Modes 聚類中，樣本到聚類中心的距離不再使用普通的歐式距離，而是采用相異度公式來計算距離，具體計算公式如下所示：

其中，n 表示樣本特征個數(shù)，x 表示任意待聚類樣本，y表示任意聚類中心。

對連續(xù)型數(shù)據(jù)而言，采用K-Means聚類方法，該方法跟K-Modes 聚類方法極為相似，只是在計算樣本到聚類中心的距離使用的是歐式聚類，計算公式如下所示：

兩種聚類算法思想如下所示。

輸入：數(shù)據(jù)集D，聚類個數(shù)k。

輸出：k 個聚類集合。

If 數(shù)據(jù)集為離散型

步驟1 隨機初始化k 個聚類中心，分別為Ci(1,2,…,k)；

步驟2 對于樣本xi(i=0,1,…,n-1)，利用式（1）計算它到每個聚類中心Ci的距離，將xi劃分到距離最小的簇；

步驟3 待數(shù)據(jù)集D 中樣本全部劃分完成之后，重新確定簇中心，向量Ci中的每一個分量都更新為簇i 中的眾數(shù)；

步驟4 重復步驟2和步驟3，直到總距離（各個簇中樣本與各自簇中心距離之和）不再降低，返回最后的聚類結(jié)果。

Else

步驟5 隨機初始化k 個聚類中心，分別為Ci(1,2,…,k)；

步驟6 對于樣本xi(i=0,1,…,n-1)，利用式（3）計算它到每個聚類中心Ci的距離，將xi劃分到距離最小的簇；

步驟7 待數(shù)據(jù)集D 中樣本全部劃分完成之后，重新確定簇中心，向量Ci中的每一個分量都更新為簇i 中的平均數(shù)；

步驟8 重復步驟6和步驟7，直到總距離（各個簇中樣本與各自簇中心距離之和）不再降低，返回最后的聚類結(jié)果。

End

2.2 隨機森林

隨機森林（Random Forest，RF）是一種經(jīng)典的集成學習模型，由多棵決策樹（Decision Tree，DT）{h(x,Θk),k=1,2,…}構(gòu)成，其中參數(shù)集Θk是獨立并且同分布的隨機變量。隨機森林對數(shù)據(jù)采取有放回隨機抽樣方法產(chǎn)生訓練樣本，假設(shè)數(shù)據(jù)集D 的樣本量為N，采用Bootstrap有放回抽樣時，每個樣本沒有被抽取到的概率則為1-1/N ，通過抽取N 之后，單個樣本沒有被抽取到的概率為(1-1/N)N。只要樣本量N 足夠大，數(shù)據(jù)集D會留下約37%的樣本未被抽中，這部分稱為袋外數(shù)據(jù)（Out Of Bag，OOB），其作用是模型評估。接著，訓練樣本采用隨機抽樣的方法抽取特征子集，特征抽取個數(shù)一般為為數(shù)據(jù)維度。構(gòu)建完多棵決策樹后形成隨機森林，通過投票的方式得到測試樣本的最終結(jié)果。隨機森林算法思想如下所示。

輸入：數(shù)據(jù)集D。

輸出：袋外數(shù)據(jù)的類別。

步驟1 對于第i 棵決策樹，采用Bootstrap抽樣方法抽取樣本N 次，N 為數(shù)據(jù)集D 的樣本量大小，抽到的數(shù)據(jù)為訓練集樣本，未抽取到的數(shù)據(jù)作為第i 棵決策樹的OOBi；

步驟2 利用訓練集數(shù)據(jù)構(gòu)建決策樹，每個節(jié)點分裂之前隨機選擇特征生成特征子集；

步驟3 構(gòu)建第i 棵決策樹；

步驟4 利用第i 棵決策樹對OOBi進行預測，得到預測結(jié)果；

步驟5 重復步驟1到步驟4，直到構(gòu)建完隨機森林；

步驟6 采用投票的形式得到所有袋外數(shù)據(jù)的預測結(jié)果。

2.3 基于聚類欠采樣策略的隨機森林優(yōu)化模型

在隨機森林隨機抽取樣本時，由于非平衡樣本中大類樣本和小類樣本數(shù)量相差較多，以致得到的訓練樣本嚴重偏向大類樣本，甚至沒有小類樣本參與模型的訓練，忽略了小樣本對模型的貢獻率，這樣訓練出來的模型對小類樣本的識別效果較差。為了能讓參與模型訓練的樣本盡可能得平衡，需要從大類樣本中抽取出能涵蓋大類樣本所有信息的樣本數(shù)據(jù)。

聚類方法通過距離計算的方式，將數(shù)據(jù)集中相近或者相似的樣本聚在同一個簇群中，從每個簇中隨機抽取一個樣本，該樣本既可以代替該簇中樣本，又可以平衡大類和小類樣本，使訓練樣本達到平衡。具體樣本平衡過程如圖1所示。

通過聚類方法得到平衡樣本集之后，建立隨機森林模型，設(shè)該隨機森林模型的規(guī)模為S。隨機森林優(yōu)化算法過程如下所示。

輸入：數(shù)據(jù)集D，隨機森林樹棵數(shù)S。

輸出：樣本測試結(jié)果y_pred。

步驟1 劃分大類樣本A(a1,a2,…,an)和小類樣本B(b1,b2,…,bk)，小類樣本總數(shù)k；

步驟2 大類樣本共聚成k 簇{K1,K2,…,Kk}；

步驟3 循環(huán)i,構(gòu)建S 棵決策樹：從k 個簇{K1,K2,…,Kk}各自有放回隨機抽取一個樣本，形成具有k 個樣本的數(shù)據(jù)集(k1,k2,…,kk)，剩下k 個簇未被抽中的樣本為OOB1*；

步驟4 將小類樣本B(b1,b2,…,bk)和(k1,k2,…,kk)混合后將其順序打亂，使整個平衡樣本集的樣本個數(shù)為2k 個(b1,b2,…,bk,k1,k2,…,kk)；

步驟5 對平衡樣本集(b1,b2,…,bk,k1,k2,…,kk)采用Bootstrape 抽樣方法一共抽取2k 次，抽中的樣本為單棵決策樹訓練集train_datai，未抽中的為單棵決策樹的OOB2*，所形成的單棵決策樹的袋外數(shù)據(jù)OOBi=OOB1*+OOB2*；

圖1 樣本平衡過程

步驟6 隨機抽取訓練集train_datai的特征子集，完成第i 棵treei的構(gòu)建；

步驟7 定義兩個臨時空間變量y_pred=[]和result=[]；

步驟8 循環(huán)遍歷所有樣本，并且遍歷所有決策樹的隨機森林：如果樣本i 不在袋外數(shù)據(jù)OOBj中，則利用該棵決策樹測試該條樣本，得到預測結(jié)果resulti；

步驟9 遍歷隨機森林中所有決策樹之后得到result 集合，通過投票的方式得到樣本i 的預測結(jié)果y_predi；

步驟10 將所有的y_predi添加到預測的分類結(jié)果中；

End

3 實驗結(jié)果及分析

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

為了驗證本文提出的基于聚類欠采樣策略的隨機森林優(yōu)化方法對非平衡數(shù)據(jù)集的有效性，選取了KEEL數(shù)據(jù)集（https：//sci2s.ugr.es/keel/datasets.php）中10 組不平衡數(shù)據(jù)進行實驗驗證。10 組數(shù)據(jù)的具體信息如表1所示。

表1 10組數(shù)據(jù)的具體信息

由表1 看出，poker-9 數(shù)據(jù)集的不平衡率最高，達到29.50，反映了該數(shù)據(jù)集大類樣本和小類樣本相差懸殊，按正常的隨機抽樣方法建立隨機森林會導致模型嚴重偏向大類樣本。

3.2 評價指標

針對不平衡數(shù)據(jù)的分類任務(wù)來講，不能單純地從分類精度去衡量一個模型的好壞。如一個100 條數(shù)據(jù)的樣本集，其中正類樣本為90，負類樣本僅為10，不平衡率達到9.0，如果某分類模型將這100個樣本全部劃分成為正類，則此時的分類精度高達90%，顯然這種評價方式極不合理。因此本文選用分類任務(wù)中的其他評價指標對算法的有效性進行驗證，分別為精確率（Precision）、召回率（Recall）、F 值和AUC值，為了更直觀地給出這些評價指標的計算公式，需要用到的混淆矩陣如表2所示。

基于表2的混淆矩陣，各評價指標的計算公式如下所示：

表2 混淆矩陣

AUC值（Area Under Curve）通常是指曲線下的面積，這里的曲線指的是受試者操作曲線（Receiver Operating Characteristic，ROC）。AUC 常常被用作模型排序好壞的指標，原因在于AUC 值可以看作隨機從正負樣本中選取一對正負樣本，其中正樣本的得分大于負樣本的概率，AUC值越大，表示模型的分類能力越好。

3.3 實驗結(jié)果及分析

為驗證本文提出的基于聚類欠采樣隨機森林優(yōu)化模型對非平衡數(shù)據(jù)有較好的分類效果，設(shè)置了其他三種對比算法：（1）傳統(tǒng)隨機森林算法（Traditional Random Forest，TRF），該算法對非平衡數(shù)據(jù)不做任何處理，直接采用Bootstrap隨機抽樣形成訓練樣本；（2）經(jīng)典欠采樣隨機森林（Classic Under-Sampling Random Forest，CURF），該方法對大類樣本隨機抽樣，形成與小類樣本數(shù)量相同的數(shù)據(jù)集，和小類樣本混合形成訓練樣本；（3）文獻[18]算法思想，利用K-Means聚類對大類樣本聚類，選擇每個聚類中心作為樣本與小類樣本合并形成平衡數(shù)據(jù)，以此為訓練集構(gòu)建隨機森林（Random Forest based on K-Means clustering to Balanced Sample，KMRF）。

本文實驗分成兩部分：一部分是通過對比其他三種算法，驗證CUSRF算法對非平衡數(shù)據(jù)的分類能力；另一部分是CUSRF跟其他三種算法的穩(wěn)定性比較。本文利用算法過程中定義的OOB計算模型的精確率、召回率、F 值和AUC值，統(tǒng)一構(gòu)建具有50棵決策樹的隨機森林，在10組非平衡數(shù)據(jù)集上的實驗結(jié)果見表3，其結(jié)果是經(jīng)過10次實驗后取到的平均值。

為了能更加直觀地展示上述的實驗效果，繪制出如圖2所示的AUC對比折線圖。

由表3 和圖2 的實驗結(jié)果可以看出，本文提出的CUSRF 算法與其他三種對比算法相比，對非平衡數(shù)據(jù)有明顯的提升效果，在10 組非平衡數(shù)據(jù)集上均有更好的實驗效果，各項指標都有一定程度提高。其中，在dermatology、german、poker-9、yeast1、pima、glass1、shuttle這7個數(shù)據(jù)集上，和傳統(tǒng)RF相比，本文提出的優(yōu)化算法有更加明顯的實驗效果。在剩下的3個數(shù)據(jù)集vehicle、wisconsin、segment0上，本文提出的優(yōu)化算法和傳統(tǒng)RF算法相比，實驗效果均有所提升，但是幅度不大。這是因為這3組數(shù)據(jù)的不平衡率僅為2左右，小類樣本較多，傳統(tǒng)RF對其有一定的分類能力。

表3 四種算法在10個數(shù)據(jù)集上的綜合表現(xiàn)

圖2 四種算法在10組非平衡數(shù)據(jù)集上的AUC對比曲線圖

和經(jīng)典的欠采樣隨機森林算法（CURF）相比，本文提出的CUSRF算法實驗效果有所提升。其中，在vehicle、wisconsin、german、poker-9、yeast1、pima、segment0、glass1這8組實驗數(shù)據(jù)上，CUSRF算法的4個評價指標均高于CURF算法。但在shuttle數(shù)據(jù)集上，CUSRF算法的AUC值比CURF的AUC值低0.4個百分點，在dermatology數(shù)據(jù)集上，兩個算法的實驗效果一致。兩個算法都是通過隨機抽取大類中的樣本使訓練樣本達到平衡，但是CUSRF 算法是隨機抽取每個分類簇中的樣本，使得抽取的樣本更加具備代表性，進而會影響模型的實驗效果。總體來看，本文提出的CUSRF 算法的實驗效果依舊優(yōu)于CURF算法。

和KMRF 算法相比，本文提出的CUSRF 算法在這10 組非平衡數(shù)據(jù)集上的實驗效果均有所提升，其中在german和yeast1兩個數(shù)據(jù)集上，實驗效果提升得更加明顯，AUC 值提升的幅度達到12 個百分點。這是因為KMRF 算法每次都選擇每個簇的聚類中心作為訓練集樣本，導致隨機森林訓練樣本的多樣性不足，而本文提出的改進算法在每個簇中都隨機抽取樣本，會使得構(gòu)建隨機森林的樣本更加具備多樣性，實驗效果更好。

綜上所述，本文提出的CUSRF 算法具有更好的分類結(jié)果，在上述10組非平衡數(shù)據(jù)集中，評價指標AUC值都有一定的提高，具有更強的分類能力。并且針對不平衡率不同的數(shù)據(jù)集，模型的實驗效果提升程度不等，對于不平衡率較大的數(shù)據(jù)集，分類能力提升更為顯著。尤其是在poker不平衡數(shù)據(jù)集上，分類結(jié)果的AUC值和傳統(tǒng)RF 相比，提高了近40 個百分點，忽略在平衡數(shù)據(jù)過程中聚類及兩次隨機抽樣帶來的偶然性，依舊可以看出，CUSRF 算法的分類效果比其他三種算法的分類效果要好。

為了探究隨機森林規(guī)模對本文方法的性能影響，進行穩(wěn)定性比對實驗。本文設(shè)定隨機森林中決策樹的棵數(shù)從20 開始，以5 的倍數(shù)依次遞增，最高隨機森林的規(guī)模為50 棵決策樹。以AUC 為評價指標，將本文提出的CUSRF 算法和其他三種算法的實驗結(jié)果進行對比，在10組非平衡數(shù)據(jù)集的實驗表現(xiàn)如圖3～圖12所示。

圖3 yeast1數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

圖4 pima數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

圖5 segment0數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

圖6 glass1數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

圖7 shuttle數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

圖8 poker-9數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

圖9 german數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

圖10 vehicle數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

圖11 wisconsin數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

圖12 dermatology數(shù)據(jù)集上隨機森林規(guī)模對分類性能的影響

從圖3 中的10 組非平衡數(shù)據(jù)集的實驗對比可以看出，隨著隨機森林規(guī)模的增長，本文提出的CUSRF算法在其中8組數(shù)據(jù)集上隨著規(guī)模的增大，模型效果趨于穩(wěn)定。僅在shuttle 和german 兩組不平衡率較高的數(shù)據(jù)集上波動較大，實驗效果穩(wěn)定性不強。這是因為兩組數(shù)據(jù)的小類樣本數(shù)較少，使得抽取的訓練集樣本少，造成OOB 數(shù)據(jù)較多，測試數(shù)據(jù)明顯多于訓練數(shù)據(jù)。從實驗結(jié)果穩(wěn)定性來說，本文提出的CUSRF 算法和經(jīng)傳統(tǒng)欠采樣平衡樣本后的隨機森林算法穩(wěn)定性都相對較好，其次是KMRF算法，傳統(tǒng)隨機森林的穩(wěn)定性最差。由此可見，本文提出的優(yōu)化模型可以快速達到收斂狀態(tài)，并且模型的AUC值高于其他三種算法。

由分類能力對比實驗和穩(wěn)定性對比實驗可以看出，本文提出的CUSRF算法在分類能力及模型穩(wěn)定性上要優(yōu)于傳統(tǒng)RF 算法，并且分類能力優(yōu)于CURF 算法和KMRF算法。對于不平衡率較大的數(shù)據(jù)集，采用本文提出的優(yōu)化算法平衡數(shù)據(jù)，使得樣本多樣性增加并且更具代表性，模型的評價指標F 值和AUC 值提升得更加明顯。但是不平衡樣本數(shù)據(jù)集中的小類樣本較少時，會導致傳統(tǒng)隨機森林和本文提出的優(yōu)化模型的穩(wěn)定性不高。

4 結(jié)束語

針對隨機森林分類效果受到樣本集類間不平衡、類內(nèi)不規(guī)則的影響，本文結(jié)合聚類欠采樣算法，提出了一種隨機森林優(yōu)化方法——CUSRF算法。CUSRF算法利用聚類方法分別對離散型和連續(xù)型不平衡數(shù)據(jù)集中的大類樣本聚類，得到與小類樣本個數(shù)相同的子類簇，再從每個子類簇中隨機抽取一個樣本與小類樣本形成平衡樣本集；對平衡樣本集有放回抽樣形成單棵決策樹的訓練集樣本并完成建樹，重復上述過程，直至達到隨機森林的規(guī)模。兩次未被抽中的樣本作為模型測試的袋外數(shù)據(jù)。使用10 組非平衡數(shù)據(jù)集進行實驗驗證，結(jié)果表明，CUSRF算法在這10組不平衡數(shù)據(jù)集上的精確率、召回率、F 值以及AUC值均有所提高，并且該算法的穩(wěn)定性要高于其他兩種對比算法。今后的研究工作將主要集中在如何降低算法的時間復雜度上。