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

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

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

1 引言

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

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

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

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

2.1 隨機(jī)森林

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

算法1隨機(jī)森林

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

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

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

3.樣本d個(gè)屬性中隨機(jī)選擇m(m

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

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

2.2 SMOTE算法

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

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

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

算法2 SMOTE算法

輸入：正類樣本集Xpositive，負(fù)類樣本集Xnegative。

1.對(duì)正類樣本集Xpositive進(jìn)行分組，歐幾里德距離最近的6個(gè)樣本分為一組。

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

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

執(zhí)行步驟2

END

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

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

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

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

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

算法3 TSMOTE算法

輸入：正類樣本集Xpositive，負(fù)類樣本集Xnegative。

1.對(duì)正類樣本集Xpositive進(jìn)行分組，歐幾里德距離最近的6個(gè)樣本分為一組。

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

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

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

執(zhí)行步驟3

END

3.2 最遠(yuǎn)點(diǎn)MDSMOTE算法

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

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

算法4 MDSMOTE算法

輸入：正類樣本集Xpositive，負(fù)類樣本集Xnegative。

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

表1 二分類的混淆矩陣

表2 評(píng)價(jià)標(biāo)準(zhǔn)的計(jì)算方法

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

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

4.1 實(shí)驗(yàn)環(huán)境設(shè)置

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

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

圖3 時(shí)間復(fù)雜度對(duì)比實(shí)驗(yàn)

5 結(jié)束語

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