一種改進(jìn)型的不平衡數(shù)據(jù)欠采樣算法

魏 力,張育平

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211100)

1 引 言

在機(jī)器學(xué)習(xí)中,不平衡數(shù)據(jù)集是指不同類別的樣本分布不均衡,即會(huì)出現(xiàn)某一類別的樣本遠(yuǎn)遠(yuǎn)多于另一類別的樣本[1].這在各個(gè)研究領(lǐng)域也是很常見的,比如信用欺詐檢驗(yàn)[2],信用不合格的客戶往往是占少數(shù)的；又如醫(yī)院疾病檢測(cè),生病的人較正常人也是少數(shù)的.然而,如果直接使用這種數(shù)據(jù)集進(jìn)行分類研究,會(huì)因?yàn)轭悇e不平衡問題對(duì)算法的學(xué)習(xí)過程造成干擾,使得分類結(jié)果不盡如人意[3].

Wessi[4]的研究表明,不平衡數(shù)據(jù)集分類困難的主要原因有如下幾點(diǎn)：1.傳統(tǒng)的分類器性能評(píng)價(jià)標(biāo)準(zhǔn)失效.在很多情況下,我們會(huì)將精度(Accuracy)作為評(píng)價(jià)分類器好壞的依據(jù),但有些時(shí)候精度并不能很好的反映模型的好壞.例如,100個(gè)人中有10個(gè)人生病,分類器即使將所有個(gè)例都預(yù)測(cè)為正常人也能獲得90%的精度.但這不是我們想要的預(yù)測(cè)模型,能將患者預(yù)測(cè)出來才是研究的目標(biāo).因此,在不平衡數(shù)據(jù)集中,以精度為評(píng)價(jià)標(biāo)準(zhǔn)的分類學(xué)習(xí)會(huì)使分類器更偏向于預(yù)測(cè)為多數(shù)類.2.少數(shù)類樣本過于少.從Wessi的文獻(xiàn)[5]可以知道,在一些應(yīng)用下,多類樣本與少類樣本比例過高時(shí)就會(huì)使分類變得困難.說明分類器的性能與樣本類別比例有關(guān).3.數(shù)據(jù)碎片問題.不少分類算法采用了分治思想,即將原來的大規(guī)模數(shù)據(jù)空間劃分成若干個(gè)小規(guī)模子空間,而這些子空間會(huì)包含更少的少數(shù)類樣本,導(dǎo)致少數(shù)類信息的匱乏,那么預(yù)測(cè)模型也較難建立.4.歸納偏置問題.在預(yù)測(cè)任務(wù)中,未知樣本可以是任意的,而如果沒有額外假設(shè)來約束的話,任務(wù)完成不了.這些假設(shè)約束條件就稱為歸納偏置.為了獲得更好的性能并能避免過度擬合,很多學(xué)習(xí)算法不利于少數(shù)類樣本的預(yù)測(cè),即這類算法會(huì)更偏向于將樣本預(yù)測(cè)為多數(shù)類.

2 相關(guān)技術(shù)

對(duì)于處理不平衡數(shù)據(jù)集給學(xué)習(xí)任務(wù)造成的困擾,目前研究主要從兩方面著手：從算法設(shè)計(jì)層面改進(jìn)算法；從數(shù)據(jù)層面改變樣本分布.

為了解決上文提到的不平衡數(shù)據(jù)集對(duì)傳統(tǒng)分類算法性能的影響,從算法設(shè)計(jì)著手是一種思路,主要包括：

代價(jià)敏感學(xué)習(xí).代價(jià)敏感學(xué)習(xí)主要考慮在分類任務(wù)中,不同類別錯(cuò)分時(shí)如何通過此時(shí)的“錯(cuò)誤代價(jià)”來調(diào)整分類器.比如在疾病診斷一例中,將正常人誤分為病人和將病人誤分為正常人的“代價(jià)”是不同的.很明顯,將病人誤分為正常人很可能會(huì)讓患者錯(cuò)過最佳治療時(shí)機(jī)而導(dǎo)致比較嚴(yán)重的后果.那么在代價(jià)敏感學(xué)習(xí)中,會(huì)先設(shè)計(jì)一個(gè)C×C的Cost代價(jià)矩陣,用以表明將某一類別錯(cuò)分時(shí)的代價(jià).所以代價(jià)敏感學(xué)習(xí)任務(wù)追求的不是總體的錯(cuò)誤率最低,而是完成分類后的總“代價(jià)”最小.

單分類方法.與二分類或多分類任務(wù)不同,單分類方法是去確定唯一類別的邊界條件.這樣做的結(jié)果就是,該方法只能識(shí)別一個(gè)類別,而不包含在邊界內(nèi)的都屬于“其它”.劉敬[19]等人對(duì)基于單分類支持向量機(jī)和主動(dòng)學(xué)習(xí)的異常檢測(cè)進(jìn)行了研究,利用原始數(shù)據(jù)采用無監(jiān)督方式建立單分類支持向量機(jī)模型,然后結(jié)合主動(dòng)學(xué)習(xí)找出能夠提高異常檢測(cè)性能的樣本并標(biāo)記,所提方法能夠利用少量標(biāo)記數(shù)據(jù)獲取性能提升.常用的單分類SVM在處理不平衡數(shù)據(jù)問題是有較好的效果,文獻(xiàn)[6]也證明,因?yàn)橹灰?xùn)練某一類別的數(shù)據(jù),這無論是在時(shí)間開銷還是空間開銷上都節(jié)省了很多.

重劃分.重劃分就是將多數(shù)類通過聚類算法劃分為若干個(gè)與少數(shù)類均衡的子類,以此來達(dá)到類別平衡.鄔長安[18]等人提出了基于 k-mean的數(shù)據(jù)預(yù)處理的邏輯回歸學(xué)習(xí)方法ILKL提高邏輯回歸在不平衡類中的分類性能.不同于傳統(tǒng)的邏輯回歸方法,該方法采用k-means聚類進(jìn)行了數(shù)據(jù)預(yù)處理,將多數(shù)類實(shí)例劃分為一個(gè)個(gè)子簇,然后用ILKL學(xué)習(xí)到的模型在重平衡的數(shù)據(jù)集上進(jìn)行分類.

其它諸如改進(jìn)集成學(xué)習(xí)算法Adaboost的Ada-Cost[8],基于核函數(shù)的學(xué)習(xí)方法[9],主動(dòng)學(xué)習(xí)[10],遺傳算法[11]等等.

從根本上說,導(dǎo)致不平衡數(shù)據(jù)集學(xué)習(xí)問題的原因還是不同類別的樣本分布不均.那么,減少多類樣本數(shù)目,增加少類樣本數(shù)目,也就是從數(shù)據(jù)層面入手自然成為另一種思路.通過增加少數(shù)類樣本來降低不平衡度的方法叫做過采樣(over-sampling),減少多數(shù)類樣本的方法叫做欠采樣(under-s-ampling).迄今為止,不少學(xué)者在這兩個(gè)方法上已有建樹.

過采樣方面,最基礎(chǔ)的方法就是復(fù)制已經(jīng)存在的少數(shù)類樣本個(gè)例,這樣做的好處是簡單,但是復(fù)制操作在沒有給出額外信息的情況下,不僅會(huì)增加訓(xùn)練器學(xué)習(xí)的時(shí)間,更會(huì)導(dǎo)致過擬合問題.Chawa-la[12]等人提出的SMOTE算法簡單高效地模擬產(chǎn)生相似的少數(shù)類樣本數(shù)據(jù).算法為每一個(gè)少數(shù)類樣本根據(jù)K-Nearest算法選擇與其近鄰的其它樣本,然后在與這些樣本的連線上隨機(jī)產(chǎn)生人造樣本.盡管在一些實(shí)驗(yàn)中,SMOTE算法有較優(yōu)異的表現(xiàn),但它存在著兩個(gè)很明顯的問題,由于該算法在每個(gè)少數(shù)類樣本上都產(chǎn)生若干個(gè)近鄰相似樣本,所以在擴(kuò)展少數(shù)類樣本方面只能是成倍的,另外也不可避免的會(huì)產(chǎn)生過于重疊的樣本.針對(duì)這些問題,后人提出了一些改進(jìn)算法.比如Han[13]等人提出的Bordline-SMOTE算法,該算法首先在整個(gè)樣本空間中為每個(gè)少數(shù)類樣本生成K-Nearest近鄰樣本集Si,如果Si中屬于多數(shù)類的大于屬于少數(shù)類的,則將這個(gè)Si放入Danger集中,之后只在Danger集中根據(jù)SMOTE算法產(chǎn)生新樣本.Bordline-SMOTE算法只為那些處于邊界的少數(shù)類樣本產(chǎn)生新樣本會(huì)有更好的效果.王超學(xué)等人[16]提出了一種改進(jìn)的SMOTE算法GA-SM-OTE.該算法在傳統(tǒng)的SMOTE算法中引入遺傳算法的三個(gè)基本算子,利用選擇算子實(shí)現(xiàn)對(duì)少數(shù)類樣本有區(qū)別的選擇,使用交叉、變異算子實(shí)現(xiàn)對(duì)合成樣本質(zhì)量的控制.最后結(jié)合SVM算法來處理不平衡數(shù)據(jù)的分類問題.

欠采樣方面,很容易想到隨機(jī)去掉若干個(gè)多數(shù)類樣本,但這樣做會(huì)去除掉富有信息量的樣本,不利于后面的學(xué)習(xí)過程.針對(duì)這一缺陷,熊冰研等人[15]提出了一種基于樣本權(quán)重的欠抽樣方法KAcBag(K-means AdaCost bagging),該方法通過樣本權(quán)重來刻畫多數(shù)類樣本所處的區(qū)域,在多次聚類后確定各樣本的權(quán)重,然后根據(jù)權(quán)重從多數(shù)類中抽取樣本以平衡數(shù)據(jù)集.最后結(jié)合集成學(xué)習(xí)思想,通過投票集成提升分類效果.楊杰明等人[17]提出一種基于數(shù)據(jù)密度分布的欠采樣方法US-DD.該算法通過某個(gè)數(shù)據(jù)樣本點(diǎn)在一定半徑內(nèi)包含的樣本個(gè)數(shù)來定義數(shù)據(jù)密度概念,并以此來區(qū)分高密度數(shù)據(jù)和低密度數(shù)據(jù),再通過閾值參數(shù)來提出低密度數(shù)據(jù)樣本.Mani[14]等人根據(jù)數(shù)據(jù)分布特征,給出了4種基于KNN(K Nearest Neighbour)欠采樣方案.分別是NearMiss-1,NearMiss-2,NearMiss-3和Most Distant.其中NearMiss-1選擇到最近的三個(gè)少數(shù)類樣本平均距離最小的那些多數(shù)類樣本,屬于局部最近.NearMiss-2選擇到最遠(yuǎn)的三個(gè)少數(shù)類樣本平均距離最小的那些多數(shù)類樣本,屬于全局最近.而NearMiss-3讓每個(gè)少數(shù)類樣本都選擇給定數(shù)量的最近多數(shù)類樣本,使得每一個(gè)少數(shù)類樣本附近都有足夠多的多數(shù)類樣本,這會(huì)使得模型的精確度高、召回率低.Most Distant選擇那些與最近的三個(gè)少數(shù)類樣本平均距離最遠(yuǎn)的多數(shù)類樣本,這可以用作比較.實(shí)驗(yàn)結(jié)果表明,NearMiss-2擁有較好的不平衡數(shù)據(jù)學(xué)習(xí)能力.然而,在論文中Mani也提到即使是NearMiss-2與隨機(jī)欠抽樣相比提升也比較有限.

本文利用聚類簇中心的信息概括能力結(jié)合Ne-arMiss-2在欠抽樣過程中的優(yōu)先權(quán)重,提出了一種基于K-Means聚類的欠抽樣方法——CCNM.

3 算法設(shè)計(jì)

K-Means算法是很典型的基于距離的聚類算法,采用距離作為相似性的評(píng)價(jià)指標(biāo),即認(rèn)為兩個(gè)對(duì)象的距離越近,其相似度就越大.由K-Means算法聚類得出的簇中心點(diǎn)可以認(rèn)為是各個(gè)簇內(nèi)樣本點(diǎn)的信息概括.以簇中心點(diǎn)作為代表,根據(jù)Near-Miss距離去賦予各個(gè)簇選擇權(quán)重,讓權(quán)重最高的簇按照距離中心點(diǎn)近優(yōu)先原則選擇K個(gè)樣本,權(quán)重次之的選擇樣本數(shù)目遞減.

CCNM算法的步驟如下：

記多數(shù)類樣本集為S,樣本數(shù)目為M,少數(shù)類樣本集為T,樣本數(shù)目為N.

1)按照公式(1),根據(jù)少數(shù)類樣本數(shù)目N確定K值；

K=?(2N+0.25)1/2-0.5」

(1)

2)對(duì)少數(shù)類樣本進(jìn)行確定后K值的聚類,得出K個(gè)簇及其中心點(diǎn)；

3)按照NearMiss距離(NearMiss-1,NearMi-ss-2,NearMiss-3)對(duì)K個(gè)簇中心點(diǎn)進(jìn)行排序,并賦予權(quán)重,權(quán)重最高的簇即選擇K個(gè),接下來的選擇K-1個(gè)；

4)在各個(gè)簇內(nèi)依照權(quán)重選擇那些離簇中心點(diǎn)最近的樣本,如果當(dāng)前簇的樣本點(diǎn)少于應(yīng)該選擇點(diǎn)的數(shù)目,則將不夠的選擇數(shù)目交予權(quán)重次之的簇；

5)整理各簇選擇的樣本,構(gòu)建欠采樣后的多數(shù)類樣本S′.

圖1 不同類型的NearMiss算法示例Fig.1 Examples of different types of NearMiss algorithm

聚類采樣可以保證在以距離為相似性的評(píng)價(jià)標(biāo)準(zhǔn)下,比較多的保留樣本信息.從步驟3)可以看到,在不同簇內(nèi)的采樣個(gè)數(shù)是根據(jù)當(dāng)前簇的權(quán)重遞減的,呈等差數(shù)列態(tài),那么為了平衡樣本數(shù)的差異,公式(1)就通過確立K值,并約定最高權(quán)重簇的采樣個(gè)數(shù)為K,來完成最終采樣數(shù)約等于少數(shù)類樣本個(gè)數(shù)的目的.應(yīng)用NearMiss距離也可以在縱觀整個(gè)數(shù)據(jù)空間下,選出那些易于分類的數(shù)據(jù).圖1給出三種NearMiss的典型示例.

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

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

傳統(tǒng)的學(xué)習(xí)任務(wù)采用精度作為分類器性能好壞的評(píng)價(jià)標(biāo)準(zhǔn),但由于不平衡數(shù)據(jù)集的特殊性,分類器更偏向?qū)⒔Y(jié)果預(yù)測(cè)為多數(shù)類從而獲得較高的精確度.但是在一些情況下,不能識(shí)別少數(shù)類的分類并不是我們想要的,所以將精度作為不平衡數(shù)據(jù)集中分類器的評(píng)價(jià)標(biāo)準(zhǔn)是不合適的.為此,一些學(xué)者提出了更完善的解決方案,如F-Measure[9],G-Mean[10].這些指標(biāo)都基于分類評(píng)價(jià)中常用的混淆矩陣(confusion matrix),根據(jù)分類器預(yù)測(cè)結(jié)果與實(shí)際情況劃別4類組合,真正例(true positive),假正例(false positive),真反例(true negative),假反例(false negative).混淆矩陣如表1所示.

表1 混淆矩陣Table 1 Confusion matrix

在此基礎(chǔ)上,查準(zhǔn)率precision如公式(2)所示,查全率recall定義如公式(3)所示.

(2)

(3)

F-Measure是不平衡數(shù)據(jù)分類評(píng)價(jià)中最為常見的標(biāo)準(zhǔn),其定義如下：

(4)

基于調(diào)和平均定義的F度量標(biāo)準(zhǔn)的一般形式取β為1,本文也按此進(jìn)行試驗(yàn).綜合考慮查全率和查準(zhǔn)率的F-Measure只有當(dāng)precision和recall都較高時(shí)才會(huì)有比較出色的表現(xiàn),更適合不平衡數(shù)據(jù)分類評(píng)價(jià).

當(dāng)考慮有多少正例被成功預(yù)測(cè)出來(Positive-Accuracy),多少負(fù)例被成功預(yù)測(cè)出來(NegativeA-ccuracy)時(shí),就有了G-Mean的定義：

(5)

(6)

(7)

G-Mean的定義同時(shí)考慮正、負(fù)類的預(yù)測(cè)結(jié)果,在那些偏向預(yù)測(cè)為多數(shù)類的情況下,G-Mean不會(huì)有好的分?jǐn)?shù),能夠完成不平衡數(shù)據(jù)分類評(píng)價(jià)的任務(wù).

表2 數(shù)據(jù)集Table 2 Data set

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

本文從UCI上選取10個(gè)數(shù)據(jù)集,如表2所示.以少數(shù)類與樣本總數(shù)的比例作為數(shù)據(jù)集的稀有度,先將前6個(gè)數(shù)據(jù)集用作在本文中三類NearMiss距離效果的比較,確定最佳的一種NearMiss距離,后續(xù)補(bǔ)充4個(gè)數(shù)據(jù)集與其它方法比較.

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

實(shí)驗(yàn)先要將多數(shù)類樣本和少數(shù)類樣本按照一定比例歸入訓(xùn)練集和測(cè)試集,為了讓實(shí)驗(yàn)結(jié)果更加客觀,在采用不同欠采樣策略時(shí),都使用“10折交叉驗(yàn)證”.即將數(shù)據(jù)集劃分為10個(gè)互斥子集,然后將9個(gè)子集的并集作為訓(xùn)練集,剩下的作為測(cè)試集,從而可以進(jìn)行10次訓(xùn)練和預(yù)測(cè).欠采樣后的訓(xùn)練集分別調(diào)用樸素貝葉斯(NaiveBayes)和支持向量機(jī)算法(SVM)完成對(duì)測(cè)試集的預(yù)測(cè).預(yù)測(cè)結(jié)果對(duì)比實(shí)際情況,得出F-Measure和G-Mean的值,評(píng)估模型好壞.

首先比較在6個(gè)訓(xùn)練集上應(yīng)用三類不同Near-Miss距離后CCNM的表現(xiàn),分別稱之為CCNM-1、CCNM-2和CCNM-3.

表3 應(yīng)用不同NearMiss距離CCNM在SVM上的F-Measure(G-Mean)Table 3 SVM′s F-Measure(G-Mean)applied with different NearMiss distance CCNM

從表3可以看出,應(yīng)用NearMiss-2后的CCNM有著更為出色的表現(xiàn),從選擇策略上也可以發(fā)現(xiàn),NearMiss-2會(huì)從全局角度考慮多數(shù)類與少數(shù)類的距離,通過這種方式選出的多數(shù)類會(huì)均勻的分布在少數(shù)類的周圍,從而更容易找出分類界限.NearMiss-1從局部著手,只考慮最近的那么三個(gè),選出的多數(shù)類不會(huì)均勻分布在少數(shù)類周圍.會(huì)出現(xiàn)某些少數(shù)類周圍有大量多數(shù)類,而某些周圍幾乎沒有.那么,大量多數(shù)類環(huán)繞著少數(shù)類就會(huì)導(dǎo)致很低的查全率(recall),相反則會(huì)導(dǎo)致很低的查準(zhǔn)率(pre-cision).NearMiss-3雖然會(huì)“刻意”使少數(shù)類周圍有一定量的多數(shù)類,但局部仍然會(huì)出現(xiàn)某一類樣本密集,導(dǎo)致少數(shù)類預(yù)測(cè)(PositiveAccuracy)、多數(shù)類預(yù)測(cè)(NegativeAccuracy)都不夠理想.

表4 各欠采樣方法在SVM上的F-Measure(G-Mean)表現(xiàn)Table 4 Different under-sampling methods′F-Measure(G-Mean)using SVM

表5 各欠采樣方法在NaiveBayes上的F-Measure(G-Mean)表現(xiàn)Table 5 Different under-sampling methods′F-Measure(G-Mean)using NaiveBayes

表4和表5可以看到應(yīng)用NearMiss-2后的CCNM算法與其它算法在10個(gè)數(shù)據(jù)集上F-Measure和G-Mean的表現(xiàn).隨機(jī)欠采樣是最簡單的方法,但如上表展示一樣,由于隨機(jī)性會(huì)去除大量的有用信息,R-andom算法無論在F-Measure還是G-Mean上都有著較低的分?jǐn)?shù).但值得注意的是,隨機(jī)欠采樣在le-tter、wine和balance數(shù)據(jù)集上有著尚可的表現(xiàn),原因是這兩個(gè)數(shù)據(jù)集是多類別的,將稀有類別作為少數(shù)類而其他類別作為多數(shù)類時(shí),隨機(jī)欠采樣后的多數(shù)類樣本在各個(gè)類別的分布可能是比較均勻的,利于后面的分類學(xué)習(xí).CCNM算法首先利用聚類將多數(shù)類樣本進(jìn)行歸類,再利用NearMiss-2對(duì)各個(gè)簇周圍少數(shù)類樣本個(gè)數(shù)進(jìn)行分析,這樣選出的多數(shù)類樣本不僅具有更豐富的信息,在樣本空間分布上也能圍繞著少數(shù)類.因此,CCNM在不平衡數(shù)據(jù)分類任務(wù)中有更好的性能,尤其在不平衡度較高的yeast和glass數(shù)據(jù)集上提升明顯,聚類在此處起到了很明顯的去噪聲的作用,同時(shí)保留了信息量高的多數(shù)類.

5 總 結(jié)

在各行業(yè)應(yīng)用領(lǐng)域中,不平衡數(shù)據(jù)問題是較為常見的,數(shù)據(jù)類別分布不均會(huì)直接影響學(xué)習(xí)過程,給最后的預(yù)測(cè)造成困擾.本文提出一種結(jié)合KMea-ns聚類和NearMiss距離的欠采樣算法CCNM,在應(yīng)用UCI數(shù)據(jù)集后,驗(yàn)證了該算法在處理不平衡數(shù)據(jù)集問題的有效性,提高了學(xué)習(xí)器的分類性能.CCNM欠采樣后的多數(shù)類樣本數(shù)目約等于少數(shù)類樣本數(shù)目,如何使得采樣后的數(shù)目更加接近或者等于少數(shù)類樣本,以及結(jié)合聚類和NearMiss距離的過采樣方法是今后工作的下一個(gè)目標(biāo).