尚旭

摘要：不平衡數(shù)據(jù)集中，由于某類(lèi)別數(shù)量的不平衡，使得類(lèi)別數(shù)量少的容易被誤分，導(dǎo)致其分類(lèi)準(zhǔn)確率不高。處理不平衡數(shù)據(jù)集的方法，可以分為算法方面和數(shù)據(jù)方面，在數(shù)據(jù)方面中，主要分為兩種方法：過(guò)采樣和欠采樣，但是對(duì)于將這兩種方法結(jié)合的研究不是很多，過(guò)采樣和欠采樣都具有一定的優(yōu)勢(shì)，因此設(shè)想將這兩種方法結(jié)合起來(lái)，希望可以找到更好的方法。提出兩種混合采樣方法：Random-SMOTE+ENN和Random-SMOTE+TNS，并與幾種典型的抽樣方法在數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)結(jié)果表明提出的兩種方法是可行有效的。

關(guān)鍵詞：不平衡數(shù)據(jù)集 過(guò)采樣 欠采樣

中圖分類(lèi)號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）12-0068-04

引言

不平衡數(shù)據(jù)集[1-2]是指在一個(gè)數(shù)據(jù)集中，有些類(lèi)別的樣本數(shù)量很多，有些類(lèi)別的樣本數(shù)量很少，這就形成了數(shù)據(jù)集各類(lèi)別樣本的不均衡，一般稱(chēng)樣本數(shù)量少的一類(lèi)為少數(shù)類(lèi)，有時(shí)也可稱(chēng)為正類(lèi)，樣本數(shù)量多的一類(lèi)為多數(shù)類(lèi)，有時(shí)也稱(chēng)為負(fù)類(lèi)[3]。在許多不平衡數(shù)據(jù)集的實(shí)際分類(lèi)中，樣本數(shù)量少的一類(lèi)往往對(duì)分類(lèi)來(lái)說(shuō)更重要。在現(xiàn)實(shí)生活中，存在著許多數(shù)據(jù)不平衡的例子，如醫(yī)療診斷[4]，垃圾信息的識(shí)別，客戶(hù)信譽(yù)識(shí)別[5]。例如在醫(yī)療診斷中，一個(gè)沒(méi)有病的人被醫(yī)生診斷為有病，這會(huì)使人承受精神的壓力，然而假如醫(yī)生把一個(gè)有病的患者診斷為沒(méi)有病可能就會(huì)耽誤治療，有可能會(huì)危及病人的生命。正如這些實(shí)例，少類(lèi)數(shù)據(jù)所擁有的信息往往是所需要的，因此怎樣能在分類(lèi)過(guò)程中正確識(shí)別這些數(shù)據(jù)是應(yīng)該關(guān)注和解決的問(wèn)題。

目前，已經(jīng)有很多這方面的處理方法[6]可以從兩方面考慮：算法方面和數(shù)據(jù)處理方面。算法方面就是不斷完善已有的算法和提出新的分類(lèi)算法[7]，如代價(jià)敏感學(xué)習(xí)、Bagging算法[8]等。數(shù)據(jù)方面的方法有兩種[9]：過(guò)采樣方法和欠采樣方法[10-11]。常用的采樣方法是隨機(jī)過(guò)采樣、隨機(jī)欠采樣、Tomeklinks[12]、壓縮最近鄰（CNN）[13]、鄰域清理（NCL）[14]、（Synthetic Minority Over-Sampling Techique）SMOTE[15]、Borderline-Smote（BSM）[16]、one-sided selection（OSS）[17]等，還有一些組合算法，如Gustavo[18]等人提出的SMOTE+ENN和SMOTE+Tomeklink。

文中主要研究了過(guò)采樣和欠采樣相結(jié)合的方法，分別將過(guò)采樣方法Random-SMOTE和欠采樣ENN方法、（Total under sampling）TNS方法結(jié)合，即Random-SMOTE+ENN方法和Random-SMOTE+TNS方法。將過(guò)采樣和欠采樣這兩種方法相結(jié)合是因?yàn)樵跇颖緮?shù)較少的數(shù)據(jù)集，這兩種方法都有不足，過(guò)采樣或欠采樣的效果不好，過(guò)采樣會(huì)使樣本數(shù)據(jù)集的少數(shù)類(lèi)過(guò)擬合，而欠采樣方法會(huì)丟許多樣本的信息，組合方法能夠有效的解決這兩種問(wèn)題，其次，已經(jīng)有人研究過(guò)將這兩種采樣方法結(jié)合，實(shí)驗(yàn)結(jié)果表現(xiàn)出良好的效果，最后，這幾種方法在單獨(dú)執(zhí)行時(shí)就表現(xiàn)出了較好的效果，所以將這兩種采樣方法組合起來(lái)，希望會(huì)使不平衡數(shù)據(jù)集的分類(lèi)效果好。

在預(yù)處理階段采用了6種采樣方法，其中包括文章提出的兩種對(duì)不平衡數(shù)據(jù)預(yù)處理的方法，在選取的9種不同程度數(shù)據(jù)集上進(jìn)行預(yù)處理及分類(lèi)實(shí)驗(yàn)，最后給出6種采樣方法預(yù)處理后的分類(lèi)結(jié)果以及實(shí)驗(yàn)結(jié)論。

1 相關(guān)介紹

目前，在已有的處理不平衡數(shù)據(jù)分類(lèi)問(wèn)題的數(shù)據(jù)處理方法有兩方面，一方面是過(guò)采樣方法，另一方面欠采樣方法。隨機(jī)過(guò)采樣是對(duì)少數(shù)類(lèi)樣本進(jìn)行復(fù)制，這會(huì)引起樣本數(shù)據(jù)的重疊和過(guò)擬合現(xiàn)象，而隨機(jī)欠采樣方法，是隨機(jī)的刪除一些多數(shù)類(lèi)的數(shù)據(jù)，使各類(lèi)別的樣本數(shù)量平衡，然而這會(huì)使一些重要樣本數(shù)據(jù)信息丟失，會(huì)影響分類(lèi)時(shí)的判斷。2002年Chawla N V等人提出了一種啟發(fā)式方法：（Synthetic Minority Over-Sampling Techique）SMOTE，這種方法與隨機(jī)過(guò)采樣方法不同，人為的在同類(lèi)近鄰樣本間線(xiàn)性插值來(lái)生成新的樣本，有效的解決了數(shù)據(jù)重疊現(xiàn)象。針對(duì)SMOTE方法的提出，研究者們對(duì)SMOTE進(jìn)行了許多的改進(jìn)工作，取得了非常好的效果。

下面介紹幾種采樣方法：

1.1 SMOTE

SMOTE方法的基本思路是在近鄰少數(shù)類(lèi)樣本之間進(jìn)行線(xiàn)性插值，合成新的少數(shù)類(lèi)樣本。具體方案是：對(duì)數(shù)據(jù)集中少數(shù)類(lèi)的每一個(gè)樣本尋找其（通常取5）個(gè)同類(lèi)最近鄰樣本，根據(jù)采樣倍率，在其個(gè)同類(lèi)最近鄰樣本中隨機(jī)選擇個(gè)同類(lèi)樣本，記作，在少數(shù)類(lèi)樣本，之間連線(xiàn)上進(jìn)行隨機(jī)線(xiàn)性插值，生成少數(shù)類(lèi)樣本。

其中 是（0，1）內(nèi)一個(gè)隨機(jī)數(shù)，表示為新的生成的樣本。

1.2 （edited nearest neighbor）ENN

ENN[19]的基本意思是若樣本的3個(gè)最近鄰樣本中2個(gè)或以上的樣本類(lèi)別和它不一樣，則刪除此樣本。ENN方法是一種欠采樣算法，首先搜索多數(shù)類(lèi)樣本的3個(gè)最近鄰樣本，若該樣本的3個(gè)最近鄰樣本中有兩個(gè)或以上和該樣本類(lèi)別不一樣則刪除這個(gè)樣本，此算法意在刪除多數(shù)類(lèi)樣本，然而多數(shù)類(lèi)樣本附近往往都是多數(shù)類(lèi)樣本，因此ENN去掉的樣本非常有限的。

1.3 （Neighborhood Cleaning Rule）NCL

NCL方法是在ENN方法的基礎(chǔ)上提出的，以能夠刪除更多的多數(shù)類(lèi)樣本。其基本方案如下：對(duì)訓(xùn)練集中的每個(gè)樣本找出它的最近鄰的3個(gè)樣本，若該樣本是多數(shù)類(lèi)，且3個(gè)最近鄰樣本中有2個(gè)或以上與其類(lèi)別不一樣，則刪除；若屬于少數(shù)類(lèi)，且3個(gè)最近鄰樣本中有2個(gè)或以上與其類(lèi)別不同，則刪除3個(gè)最近鄰樣本中的多數(shù)類(lèi)樣本。

1.4 Random-SMOTE

Random-SMOTE[20]采樣方法的基本思想是：對(duì)于每個(gè)少數(shù)類(lèi)樣本，找其個(gè)同類(lèi)最近鄰樣本，從最近鄰少數(shù)類(lèi)樣本集中隨機(jī)選出兩個(gè)樣本、；以、、三點(diǎn)圍成一個(gè)三角形區(qū)域；若向上采樣倍率在該三角形區(qū)域內(nèi)隨機(jī)生成個(gè)新的少數(shù)類(lèi)樣本。

生成新的少數(shù)類(lèi)樣本具體步驟如下：

a）在兩個(gè)最近鄰樣本、之間生成個(gè)臨時(shí)樣本

b）然后在臨時(shí)樣本之間進(jìn)行隨機(jī)線(xiàn)性插值，生成新的少數(shù)類(lèi)樣本

其中：其中表示為（0，1）內(nèi)一個(gè)隨機(jī)數(shù)。

以上是基于數(shù)據(jù)采樣的幾種處理不平衡數(shù)據(jù)的基本方法，近幾年研究者們?cè)谶@些方法的基礎(chǔ)上提出了新的處理方法。如Gustaro等人將提出了兩種組合方法：SMOTE+Tomeklink和SMOTE+ENN方法，取得了不錯(cuò)的效果，但對(duì)于其他的算法組合研究的很少，所以文章就Random-SMOTE與ENN和TNS組合并驗(yàn)證此方法的可行性，通過(guò)研究工作發(fā)現(xiàn)將過(guò)采樣和欠采樣結(jié)合是可行的有意義的。

文中提出的兩種組合方法Random-SMOTE+ENN：首先利用Random-SMOTE對(duì)少數(shù)類(lèi)樣本進(jìn)行過(guò)采樣，然后利用ENN方法對(duì)多數(shù)類(lèi)數(shù)據(jù)進(jìn)行欠采樣處理，Random-SMOTE+TNS：首先利用Random-SMOTE對(duì)少數(shù)類(lèi)數(shù)據(jù)進(jìn)行過(guò)采樣，然后對(duì)少數(shù)類(lèi)樣本和多數(shù)類(lèi)樣本均實(shí)行欠采樣處理，方法：對(duì)數(shù)據(jù)集中的每個(gè)樣本，尋找其最近鄰的3個(gè)樣本，比較若3個(gè)最近鄰樣本中有兩個(gè)或以上的樣本和該樣本的類(lèi)別不同，則刪除該樣本，稱(chēng)之為T(mén)otal under sampling（TNS）。并且通過(guò)實(shí)驗(yàn)和其他幾種方法對(duì)比驗(yàn)證文中提出的方法是有效的。

2 評(píng)價(jià)標(biāo)準(zhǔn)度量

評(píng)價(jià)標(biāo)準(zhǔn)對(duì)分類(lèi)器的性能好壞和指導(dǎo)分類(lèi)器做出判斷有著重要的作用。對(duì)于不平衡數(shù)據(jù)分類(lèi)來(lái)說(shuō)，常用評(píng)價(jià)標(biāo)準(zhǔn)包括ROC曲線(xiàn)、基于混淆矩陣的若干度量，如查全率、查準(zhǔn)率、和等。

在兩分類(lèi)的情形下。將少數(shù)類(lèi)稱(chēng)為正類(lèi)。多數(shù)類(lèi)稱(chēng)為負(fù)類(lèi)。經(jīng)過(guò)分類(lèi)以后，數(shù)據(jù)的分類(lèi)為混淆矩陣中表示的4種情況[21]（見(jiàn)表1）。

利用混淆矩陣，可以派生出以下度量：

在信息檢索領(lǐng)域，將真實(shí)正類(lèi)率定義為查全率，表示在檢索到的相關(guān)對(duì)象所占的比例：

將正類(lèi)預(yù)測(cè)值定義為查準(zhǔn)率，表示相關(guān)對(duì)象占檢索出的所有對(duì)象的比例：

另一種評(píng)價(jià)標(biāo)準(zhǔn)是查全率和查準(zhǔn)率的調(diào)和均值：

上式中，表示和之間的相對(duì)重要程度，大于1時(shí)表示更重要，小于1時(shí)表示更重要。通常為1，表示兩者都重要。

是一個(gè)衡量整體分類(lèi)性能的評(píng)價(jià)指標(biāo)，為少數(shù)類(lèi)的分類(lèi)精度， 是多數(shù)類(lèi)的分類(lèi)精度，只有當(dāng)二者的值都大時(shí)，的值才會(huì)大，因此，能衡量不平衡數(shù)據(jù)集的整體分類(lèi)性能。

3 仿真實(shí)驗(yàn)

3.1 數(shù)據(jù)集

實(shí)驗(yàn)驗(yàn)證的數(shù)據(jù)集來(lái)自UCI數(shù)據(jù)庫(kù)中的9個(gè)數(shù)據(jù)集，每個(gè)數(shù)據(jù)集的基本信息如表2所示。

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

不平衡數(shù)據(jù)的分類(lèi)學(xué)習(xí)中，標(biāo)準(zhǔn)的分類(lèi)精度準(zhǔn)則不適合評(píng)估不平衡數(shù)據(jù)集的分類(lèi)效果，本實(shí)驗(yàn)選取F-value準(zhǔn)則，G-mean準(zhǔn)則和少數(shù)類(lèi)的分類(lèi)準(zhǔn)確率acc+來(lái)對(duì)實(shí)驗(yàn)結(jié)果綜合分析。

在實(shí)驗(yàn)中，選擇了近鄰算法作為分類(lèi)算法，然后對(duì)選取6種不同的采樣方法進(jìn)行實(shí)驗(yàn)對(duì)比，分別是：隨機(jī)過(guò)采樣、SMOTE、Random-SMOTE、SMOTE+ENN、Random-SMOTE+ENN、Random-SMOTE+TNS，上述不平衡分類(lèi)方法所使用近鄰算法的近鄰選取5，在各個(gè)數(shù)據(jù)集上所有采樣方法所設(shè)置的采樣率相同，為實(shí)驗(yàn)客觀公正，實(shí)驗(yàn)通過(guò)五折交叉驗(yàn)證得到實(shí)驗(yàn)結(jié)果。

表3、表4列出個(gè)不平衡分類(lèi)方法在9個(gè)UCI數(shù)據(jù)集上的G-mean和F-value值。

從表3、表4給出的F-value值和G-mean值可以看出，對(duì)于組合方法的分類(lèi)效果在大多數(shù)數(shù)據(jù)集上優(yōu)于過(guò)采樣方法的分類(lèi)效果，尤其在于不平衡度較小的數(shù)據(jù)集上組合方法的效果更明顯，組合方法先通過(guò)過(guò)采樣對(duì)于少類(lèi)數(shù)據(jù)處理，然后對(duì)于多類(lèi)數(shù)據(jù)進(jìn)行欠采樣處理，不僅增加了少類(lèi)數(shù)據(jù)數(shù)目，而且盡可能的刪除處于邊界的多類(lèi)數(shù)據(jù)，大大提高了少類(lèi)分類(lèi)正確率，分類(lèi)效果明顯更好。文中提出的兩種分類(lèi)方法也具有很好的分類(lèi)效果，其中Random-smote+TNS的分類(lèi)效果在9個(gè)數(shù)據(jù)集上的表現(xiàn)均好于其他幾種分類(lèi)方法的表現(xiàn)。另一種組合方法Random-SMOTE+ENN的分類(lèi)效果低于SMOTE+ENN的分類(lèi)效果，但和其他三種方法分類(lèi)效果對(duì)比具有一定的優(yōu)勢(shì)，只在數(shù)據(jù)集glass-I比SMOTE和Random-SMOTE低，在數(shù)據(jù)集Balance-II上比隨機(jī)過(guò)采樣低。文中提出的分類(lèi)方法分類(lèi)效果良好。

不平衡數(shù)據(jù)集中，少數(shù)類(lèi)往往是我們感興趣的類(lèi)別，因此對(duì)于少數(shù)類(lèi)的分類(lèi)準(zhǔn)確率acc+是衡量不平衡分類(lèi)性能的重要指標(biāo)，圖1給出了各采樣方法的acc+圖，由圖可知，除了數(shù)據(jù)集Feritilty和Balance-II上，Random-smote+TNS的acc+值低于隨機(jī)過(guò)采樣，在其他數(shù)據(jù)集上Random-smote+TNS的acc+值均大于其他采樣方法，特別在Pima數(shù)據(jù)集和blood數(shù)據(jù)上，acc+值明顯高于其他采樣方法。另一種組合方法Random-smote+ENN的acc+和Somte+ENN表現(xiàn)持平，但好于過(guò)采樣方法Random-smote，可見(jiàn)組合方法的分類(lèi)率好于單純的過(guò)采樣方法。從整個(gè)實(shí)驗(yàn)數(shù)據(jù)的分析得出文中的兩種組合方法是可行有效的。

4 結(jié)語(yǔ)

文章通過(guò)在多個(gè)數(shù)據(jù)上使用多種數(shù)據(jù)采樣方法，進(jìn)行仿真實(shí)驗(yàn)對(duì)比得到兩種較好混合采樣方法和有效的結(jié)果，通過(guò)實(shí)驗(yàn)數(shù)據(jù)分析得出這兩種混合采樣方法在試驗(yàn)中大多數(shù)據(jù)集上具有良好的分類(lèi)效果，然而也可以看出所提出的方法并不是在所有的數(shù)據(jù)集上具有好的效果。其次，沒(méi)有研究其他采樣方法組合的合理性，希望在下一步研究中能將過(guò)采樣和欠采樣方法進(jìn)行不同的組合嘗試，希望能夠找到更好的處理方法在保證整體正確率的前提下提高少數(shù)類(lèi)的分類(lèi)正確率。

參考文獻(xiàn)

[1]Han Jiawei， KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機(jī)械工業(yè)出版，2001.

[2]楊明，尹軍梅，吉銀林.不平衡數(shù)據(jù)分類(lèi)方法綜述[J].南京師范大學(xué)學(xué)報(bào)：工程技術(shù)版，2008，8（4）：7-12.

[3]Paolo S. A multi-objective optimization approach for class imbalance learning [J]. Pattern Recognition， 2011， 44（8）：1801-1810.

[4]Li DC，Liu CW，Susan CH.A learning method for the class imbalance problem with medical data sets [J]. Computers in biology and medicine， 2010， 40（5）：509-518.

[5]徐麗麗，閆德勤，高晴.基于聚類(lèi)欠采樣的極端學(xué)習(xí)機(jī)[J].微型機(jī)與應(yīng)用，2015（17）：81-84.

[6]王和勇，范泓坤，姚正安，等.不平衡數(shù)據(jù)集分類(lèi)方法研究[J]計(jì)算機(jī)應(yīng)用研究，2008，25（5）：1301-1308.

[7]胡小生，張潤(rùn)晶，鐘勇.一種基于聚類(lèi)提升的不平衡數(shù)據(jù)分類(lèi)算法[J].集成技術(shù)，2014（2）：35-41.

[8]李明方，張華祥.針對(duì)不平衡數(shù)據(jù)的Bagging改進(jìn)算法[J].計(jì)算機(jī)工程應(yīng)用，2013，49（2）：40-42.

[9]吳磊，房斌，刁麗萍，等.融合過(guò)抽樣和欠抽樣的不平衡數(shù)據(jù)重抽樣方法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（21）：172-176.

[10]丁福利，孫立民.處理不平衡樣本集的欠采樣算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（12）：4345-4350.

[11]林舒楊，李翠華，江戈，等.不平衡數(shù)據(jù)的降采樣方法研究[J].計(jì)算機(jī)研究與發(fā)展，2011，48（2）：47-53.

[12]TOMEK I. Two modifications of CNN[J].IEEE Trans on Systems， Man and Communications， 1976， 6：769-772.

[13]HART P E. The condensed nearest neighbor rule[J]. IEEE Trans on Information Theory， 1968，14（3）：515-516.

[14]LAURIKKALA J. Improving identification of difficult small classes by balancing class distribution[C]. Proc of the 8th Conference on AI in Medicine. Europe， Artificial Intelligence Medicine， 2001：63-66.

[15]Chawla N V， Bowyer K W， Hall L O， et al. SMOTE： Synthetic Minority Over-sampling Technique[J]. Journal of Artificial Intelligence Research， 2002， 16：321-357.

[16]Han H， Want W Y， Mao B H. Borderline-SMOTE： a new over-sampling method in imbalanced data sets learning[C]//LNCS 3644：ICIC 2005，Part I，2005：878-887.

[17]KUBAT M， MATWIN S. Addressing the course of imbalanced training sets： one-sided selection[C]. Proc of the 14th International Conference on Machine learning. San Francisco， Morgan Kaufmann， 1997：179-186.

[18]Gustavo E A， Batista P A， Ronaldo C，et al A study of the behavior of several methods for balancing machine learning training data[J]. SIGKDD Explorations， 2004，6（1）：20-29.

[19]WISON D L. Asymptotic properties of nearest neighbor rules using edited data [J].IEEE Trans on Systems， Man and Communications， 1972，2（3）：408-421.

[20]Dong Yanjie，WangXuehua. A new over-sampling approach：Random-SMOTE for learning from imbalanced data sets [C]//LNCS 7091： Proceedings of the 5th International Conference on Knowledge Science， Engineering and Management（KSEM11）. Berlin，Heidelberg：Springer-Verlag 2011：343-352.

[21]董元方，李雄飛，李軍.一種不平衡數(shù)據(jù)漸進(jìn)學(xué)習(xí)算法[J].計(jì)算機(jī)工程，2010，36（24）：161-163.