改進SMOTE的非平衡數(shù)據(jù)集分類算法研究

趙清華，張藝豪，馬建芬，段倩倩

太原理工大學 信息工程學院&新型傳感器和智能控制教育部（山西）重點實驗室 微納系統(tǒng)研究中心，太原 030600

1 引言

隨機森林通過自助采樣[1]獲得數(shù)據(jù)子集構(gòu)建決策樹得到很好的分類預測效果，被廣泛應用于數(shù)據(jù)挖掘各個領域中。在數(shù)據(jù)挖掘?qū)嶋H應用中，數(shù)據(jù)采集后的數(shù)據(jù)集樣本通常是不平衡的。所謂不平衡樣本數(shù)據(jù)集是指某一類的樣本數(shù)量明顯少于另一類樣本數(shù)量，在二分類問題中，數(shù)量占優(yōu)勢的類別通常稱為負類或多數(shù)類，數(shù)量稀少的分類通常稱為正類或少數(shù)類。Weiss通過大量實驗總結(jié)了不平衡數(shù)據(jù)集異常點、噪聲和某一類樣本數(shù)量稀少等問題[2]，得出了隨機森林分類器在分類預測不平衡數(shù)據(jù)集時，結(jié)果傾向于多數(shù)類，造成很大的預測誤差。實際數(shù)據(jù)集如癌癥診斷、血液樣本中心、網(wǎng)絡信息安全等數(shù)據(jù)集通常是不平衡的，所以如何改進傳統(tǒng)算法解決數(shù)據(jù)集不平衡分類問題是機器學習與大數(shù)據(jù)挖掘的研究熱點。

Chawla等人以隨機向上抽樣為核心思想提出了SMOTE算法[3]，通過人為構(gòu)造正類樣本使得數(shù)據(jù)集中負類樣本和正類樣本的數(shù)量趨于平衡。文獻[4]中提出一種基于SVM調(diào)參的算法來處理不平衡數(shù)據(jù)集，性能較SVM算法有所提升。吳洪興在文獻[5]中提出將遺傳算法的遺傳算子與支持向量機算法進行組合，較好地解決了支持向量機傾向性預測問題。針對文獻[3]，文獻[6]提出了一種將boost機器學習思想與樣本構(gòu)造結(jié)合起來，對原始正類樣本中錯誤分類的樣本加大權(quán)值，將訓練的許多弱分類器組合成強分類器，減少了對正類樣本的預測誤差。文獻[7]中提出代價敏感學習算法，其核心思想是賦予正類樣本錯判更大的懲罰。正類較負類錯判代價高迫使模型對稀少的正類具有更高的預測正確率[8]。文獻[3]無法控制正類樣本生成區(qū)域和樣本生成個數(shù)，樣本分布容易邊緣化。文獻[4-7]采用增加模型正類樣本的權(quán)值，加大誤判懲罰的方法處理問題，算法計算復雜度大，時間效率較低。

綜上所述，目前多數(shù)算法優(yōu)化研究重點關注正類樣本的權(quán)重與誤判懲罰兩個方面，在算法復雜度，數(shù)據(jù)集分布等方面研究力度不足。本文從限制樣本生成區(qū)域著手，提出兩種改進算法，TSMOTE算法和MDSMOTE算法。改進算法與隨機森林的組合模型在6種不平衡數(shù)據(jù)集上進行大量仿真實驗，實驗結(jié)果表明改進算法進一步提高了隨機森林在不平衡數(shù)據(jù)集上G-mean值、F-value值和AUC值，同時減少了算法時間復雜度。

2 傳統(tǒng)算法與原理

2.1 隨機森林

隨機森林是一種性能較好，預測分類準確率較高的組合分類器，是Bagging集成機器學習方法中最典型的算法[9]。隨機森林模型在構(gòu)造的時候具有兩個隨機性。第一個隨機性是采用自助采樣法從樣本數(shù)據(jù)集隨機有放回地采樣，構(gòu)造出n個數(shù)據(jù)子集。第二個隨機性是運用上一步得到的n個數(shù)據(jù)子集進行n個決策樹模型的構(gòu)建[10]。隨機森林構(gòu)建決策樹模型時隨機選擇若干個屬性，然后選擇最佳屬性作為分裂節(jié)點。決策樹對分類任務采用簡單投票法決定最終分類的類別。以上所述的兩個隨機性使得隨機森林很好地避免了一般決策樹所具有的過擬合問題，很好地提高了預測分類準確率。定義樣本集A={(Xi,Yi),i=1,2,…,n}，每個樣本有d個屬性，決策樹數(shù)目為N。隨機森林算法詳細步驟如下：

算法1隨機森林

輸入：樣本集A={(Xi,Yi),i=1,2,…,n}，每個樣本d個屬性，待測樣本Xtest。

1.Forj=1,2,…,N，訓練集自助采樣生成數(shù)據(jù)子集Si(i=1,2,…,N)。

2.選擇數(shù)據(jù)子集Si作為構(gòu)造第i個決策樹的樣本集合。

3.樣本d個屬性中隨機選擇m(m

4.選擇信息熵增益率最大的屬性作為分裂結(jié)點進行決策樹的分裂，總共得到N個決策樹。

5.對于待測樣本Xtest，決策樹ti輸出為ti(Xtest)，隨機森林分類輸出為

2.2 SMOTE算法

SMOTE算法是先根據(jù)歐幾里德距離將正類樣本進行分組，假設一個樣本X為X={x1,x2,…,xn},x1,x2,…,xn為樣本X的n個維度值。同理樣本Y={y1,y2,…,yn}。那么樣本X與樣本Y的歐幾里德距離D為：

歐幾里德距離最近的6個樣本分為一組。根據(jù)聚類的思想[11]，正類樣本在空間上距離較近的樣本也是正類。SMOTE算法在每組6個樣本中，樣本兩兩之間連線上隨機人為構(gòu)造新的正類樣本。

其中i=1,2,…,6,X表示稀少正類樣本，Yi為X的第i個近鄰樣本，rand(0,1)表示0到1的一個隨機數(shù)。Xnew表示新生成的樣本。根據(jù)公式（2）進行多次迭代使得數(shù)據(jù)集平衡。SMOTE算法詳細步驟如下：

算法2 SMOTE算法

輸入：正類樣本集Xpositive，負類樣本集Xnegative。

1.對正類樣本集Xpositive進行分組，歐幾里德距離最近的6個樣本分為一組。

2.每組樣本兩兩之間連線上根據(jù)公式（2）隨機生成正類樣本，加入數(shù)據(jù)集。

3.While (Xpositive:Xnegative不等于1)

執(zhí)行步驟2

END

隨機森林與SMOTE算法組合較好地改善了分類結(jié)果傾向性的問題，使得模型對正類樣本的分類預測正確率有所提高。SMOTE不能解決數(shù)據(jù)集存在的樣本邊緣化問題且算法時間復雜度大。本文改進數(shù)據(jù)集自身分布的方法，克服上述算法的不足。

3 不平衡數(shù)據(jù)集分類算法的改進

3.1 三角質(zhì)心TSMOTE算法

SMOTE算法存在兩個明顯不足，無法解決數(shù)據(jù)集正類樣本分布的邊緣化問題[12]，計算復雜度大。本文針對其不足首先提出了TSMOTE（Triangle SMOTE）算法。TSMOTE算法重點關注新樣本產(chǎn)生的區(qū)域，避免新樣本使得數(shù)據(jù)集分布進一步邊緣化。TSMOTE算法首先將樣本集進行分組，每6個樣本為一組。然后在每組隨機抽出3個樣本如X1,X2,X3,Xi={Xi1,Xi2,…,Xin}。計算出3個樣本的質(zhì)心XT為：

3個樣本組成三角形，樣本本身為三角形的頂點。每個頂點與質(zhì)心的連線上隨機產(chǎn)生一個正類樣本，一個三角形產(chǎn)生3個新的正類樣本。新樣本向質(zhì)心靠攏，較好地改善了SMOTE算法新樣本分布進一步邊緣化的問題。每組新樣本的產(chǎn)生區(qū)域有一定的限制，新樣本好比受著引力的影響靠攏著質(zhì)心。TSMOTE算法詳細步驟如下：

算法3 TSMOTE算法

輸入：正類樣本集Xpositive，負類樣本集Xnegative。

1.對正類樣本集Xpositive進行分組，歐幾里德距離最近的6個樣本分為一組。

2.每組隨機抽取3個樣本點作為三角形頂點，依據(jù)公式（3）計算質(zhì)心。

3.三角頂點與質(zhì)心連線之間隨機產(chǎn)生新的樣本。

4.While (Xpositive:Xnegative不等于1)

執(zhí)行步驟3

END

3.2 最遠點MDSMOTE算法

TSMOTE算法較好地限制了新樣本產(chǎn)生的區(qū)域，改善了樣本數(shù)據(jù)集分布問題，計算復雜度仍然較高。實際應用中，樣本點一般是空間多維度，針對上百、上千甚至上萬維度，SOMTE算法、TSMOTE算法消耗時間會大幅增加。本文針對這個不足進一步提出MDSMOTE（Max Disatance SMOTE）算法。該算法只關注兩個樣本點，正類樣本質(zhì)心點和距離質(zhì)心最遠的正類樣本點。在最遠點和質(zhì)心點連線之間隨機產(chǎn)生新樣本點：

Xnew為新樣本點，Xc為所有樣本的質(zhì)心點，Xmax為距離質(zhì)心點最遠的正類樣本點。該算法首先摒棄了傳統(tǒng)SMOTE算法將正類樣本點分組的思想，只關注正類樣本質(zhì)心點和距離樣本質(zhì)心點最遠距離的樣本點，大大減輕了算法復雜度。而且MDSMOTE算法只需要迭代一次，根據(jù)公式（4）產(chǎn)生一批新樣本點直接使得整個數(shù)據(jù)集樣本達到平衡，算法簡單易實現(xiàn)。其算法詳細步驟如下：

算法4 MDSMOTE算法

輸入：正類樣本集Xpositive，負類樣本集Xnegative。

1.計算正類樣本的質(zhì)心，遍歷所有正類樣本找出距離質(zhì)心最遠的樣本點。

2.質(zhì)心與最遠點連線之間依據(jù)公式（4）一次成生大量正類樣本使得樣本數(shù)據(jù)集平衡。

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

實驗中采用不平衡數(shù)據(jù)集常用的F-value、G-mean和AUC這3個指標來評價分類算法的優(yōu)劣，這3個指標都是以混淆矩陣為基礎擴展的[13]，混淆矩陣定義如表1所示，表2給出了3個指標的計算公式。

表1 二分類的混淆矩陣

表2 評價標準的計算方法

TP、FN分別為真實類別為正類，預測結(jié)果為正類、負類的數(shù)目。FP、TN分別為真實類別為負類，預測結(jié)果為正類，負類的數(shù)目。查準率P與查全率R分別定義為：

其中，F(xiàn)-value綜合評價查全率與查準率，能很好評價模型對稀少樣本類的分類效果[14]，式中β=1時，F(xiàn)-value為查準率和查全率的調(diào)和平均數(shù)[15]。β＞1時，查全率有更大的影響，β<1時，查準率有更大的影響。G-mean值綜合考察正類預測分類準確率和負類預測準確率，只有正類預測正確率與負類預測正確率都高的時候，G-mean值才會增加。AUC式中，m+、m-為正例和反例個數(shù)，D+、D-分別表示正例集合和反例集合。f(x+)表示判別為正類樣本的概率，F(xiàn)(x)為指示函數(shù)，x為真時，F(xiàn)(x)值為1。正例的預測值比反例預測值小，給予模型值為1的懲罰。正例的預測值等于反例的預測值模型給予值為0.5的懲罰。對于不平衡數(shù)據(jù)集，AUC值越大模型分類效果越好。

4.1 實驗環(huán)境設置

為了檢驗文中改進算法的有效性與普適性，本實驗采用表3所示6組不平衡數(shù)據(jù)集作為檢驗集，采用Python語言，Jupyter notebook編程環(huán)境對改進算法進行仿真實驗。這6組不平衡數(shù)據(jù)集分別為血液捐助中心、糖尿病患者、酵母菌、汽車保險索賠、圖片分類和玻璃辨識數(shù)據(jù)集，其中酵母菌數(shù)據(jù)集不平衡率尤為突出。

表3 不平衡數(shù)據(jù)集特征與分布

每次實驗隨機劃分80%為訓練集，20%為測試集；隨機森林中用于生成隨機數(shù)發(fā)生器的種子置0；SMOTE算法與TSMOTE算法需要分組，設定每組的樣本均為6個；TSMOTE算法組內(nèi)每次隨機抽取3個樣本用于構(gòu)造新樣本；實驗評價指標F-value和G-mean是在隨機森林的決策樹個數(shù)為10時仿真100次求平均值來得到；為了更好地比較算法的計算復雜度和所消耗的時間，評價指標AUC值和實驗耗時是在特意仿真1 000次求平均得到的。

4.2 實驗結(jié)果分析

表4為6組不同數(shù)據(jù)集上3種算法的G-mean指標比較，決策樹個數(shù)均設置為10，可以看出，6組樣本集中SMOTE、TSMOTE和MDSMOTE算法的G-mean值均逐漸增加，其中，TSMOTE算法的G-mean指標較SMOTE算法大幅度提升，MDSMOTE算法的G-mean指標較TSMOTE算法小幅度提升。血液數(shù)據(jù)集中SMOTE算法的G-mean指標只有0.563 1，TSMOTE算法的G-mean指標達到0.761 4，MDSMOTE算法的G-mean指標達到0.831 0，說明血液數(shù)據(jù)集中正類樣本存在嚴重邊緣化，導致SMOTE算法表現(xiàn)較差。改進算法限制區(qū)域的思想使得樣本中正類樣本沒有邊緣化，而是圍繞著質(zhì)心中心化，更好地改善了樣本數(shù)據(jù)集分布，提高了分類器的性能。圖1給出3種算法在隨機選取的3組樣本集（酵母菌、糖尿病和圖片數(shù)據(jù)集）上隨著決策樹個數(shù)不同的G-mean指標，可以看出，3種算法的G-mean值均隨著決策樹個數(shù)增加而有所增加，并最終趨于平穩(wěn)。在各個決策樹參數(shù)上，本文改進的TSMOTE算法和MDSMOTE算法的G-mean指標均比傳統(tǒng)SMOTE算法大幅度提高，綜合比較，MDSMOTE算法表現(xiàn)最佳，平穩(wěn)值是模型的最佳表現(xiàn)，繼續(xù)增加決策樹參數(shù)模型會因為過擬合而性能下降。

表4 不同算法上的G-mean指標結(jié)果

圖1 3種算法在酵母菌、糖尿病和圖片數(shù)據(jù)集上隨著決策樹個數(shù)不同的G-mean比較

表5和圖2仿真得出算法的F-value指標比較，由表5可以看出，除了血液數(shù)據(jù)集，其他數(shù)據(jù)集上TSMOTE算法的F-value指標均得到提高。MDSMOTE算法的F-value指標在TSMOTE算法的基礎上進一步提高，說明改進算法對正類和負類樣本的預測準確率都有所提高。圖2是3種算法在酵母菌、糖尿病和圖片數(shù)據(jù)集上隨著決策樹個數(shù)不同的F-value比較，每種算法的F-value指標均隨著決策樹參數(shù)增加而增加。當決策樹為3時，糖尿病數(shù)據(jù)集上SMOTE算法的F-value約為0.75，MDSMOTE算法的F-value約為0.78，性能提升較小，而對于酵母菌和圖片數(shù)據(jù)集，SMOTE算法的F-value分別約為0.72和0.87，MDSMOTE算法的F-value約為0.95和0.97，性能大幅度提高。究其原因可知糖尿病數(shù)據(jù)集本身邊緣樣本較少，所以采用中心化思想優(yōu)化算法TSMOTE和MDSMOTE算法性能提升較小，而對于酵母菌和圖片數(shù)據(jù)集邊緣樣本較多，性能大幅提升，F(xiàn)-value均在0.95以上。

表5 不同算法上的F-value指標結(jié)果

圖3為算法復雜度對比實驗結(jié)果，隨機選取汽車保險數(shù)據(jù)集作為樣本集仿真運行1 000次計算AUC指標，由圖3（a）可知SMOTE算法 AUC值大多集中0.67左右，算法消耗時間44.7 s。由圖3（b）可知TSMOTE算法 AUC值大多位于0.92左右，算法消耗時間39.3 s。由圖3（c）MDSMOTE算法AUC值大多集中于0.935左右，算法消耗時間30.9 s。AUC值越大，說明模型對正類、負類的分類性能越好。顯然，改進算法TSMOTE和MDSMOTE的性能都優(yōu)于傳統(tǒng)算法SMOTE。由圖3（d）也可以看出在6種數(shù)據(jù)集上，SMOTE、TSMOTE和MDSMOTE算法消耗時間逐漸減少，SMOTE算法遍歷所有正類樣本，分組然后組內(nèi)成生新樣本時間復雜度為O(n2)，TSMOTE相當于減少組內(nèi)用來生成新樣本的原始正類樣本，時間復雜度為O(0.2n2)，MDSMOTE算法不采用分組直接生成樣本時間復雜度為O(n)。針對AUC指標實驗數(shù)據(jù)集規(guī)模較小，數(shù)據(jù)集維度較小，實際數(shù)據(jù)挖掘應用中數(shù)據(jù)樣本規(guī)模一般為十萬、百萬甚至更多，數(shù)據(jù)維度一般成千上萬，算法計算量呈指數(shù)型增長，本文針對減少算法時間復雜度提出的兩種算法在實際大規(guī)模數(shù)據(jù)集，海量樣本數(shù)據(jù)挖掘工程中可以有效減少工程時間，提高數(shù)據(jù)挖掘工程效率。

圖2 3種算法在酵母菌、糖尿病和圖片數(shù)據(jù)集上隨著決策樹個數(shù)不同的F-value比較

圖3 時間復雜度對比實驗

5 結(jié)束語

由于隨機森林和SMOTE算法組合存在樣本邊緣化、算法時間復雜度大的不足，本文提出了兩種基于SMOTE的改進算法TSMOTE和MDSMOTE。改進算法將產(chǎn)生的新樣本限制在一定區(qū)域中，使得模型對正類樣本，負類樣本的綜合分類準確率提升，改善了SMOTE算法樣本分布邊緣化的問題。實驗結(jié)果表明TSMOTE和MDSMOTE算法較SMOTE算法取得了較高的G-mean值、F-value值和AUC值，減小了算法時間復雜度，對于海量樣本實際數(shù)據(jù)挖掘工程中可以有效減少工程時間，提高數(shù)據(jù)挖掘工程效率，進一步提高了對于不平衡數(shù)據(jù)集的綜合分類性能。本文改進算法模型依然存在不少噪聲樣本，未來研究著重考慮將欠采樣技術(shù)與重采樣技術(shù)結(jié)合，使用過采樣技術(shù)使得數(shù)據(jù)集平衡，然后使用特定的欠采樣算法剔除樣本集中的噪聲樣本和異常點，進一步優(yōu)化模型。