基于遺傳理論的改進(jìn)數(shù)據(jù)過(guò)采樣方法①

丁勝奪,趙 剛,閻紅巧,劉洪太

(中國(guó)石油集團(tuán) 安全環(huán)保技術(shù)研究院有限公司,北京 102206)

不平衡數(shù)據(jù)是指在一個(gè)數(shù)據(jù)集中,某一類別數(shù)據(jù)的樣本數(shù)量遠(yuǎn)遠(yuǎn)大于其他類別樣本的數(shù)量,其中,樣本數(shù)量較少的類別被稱為少數(shù)類(或稱為正類),類別數(shù)量較多的類被稱為多數(shù)類(或稱為負(fù)類).類不平衡是一個(gè)現(xiàn)實(shí)生活中普遍存在的現(xiàn)象,如故障檢測(cè)、醫(yī)學(xué)診斷、信用卡欺詐檢測(cè)、軟件缺陷檢測(cè)、互聯(lián)網(wǎng)攻擊識(shí)別等.傳統(tǒng)的分類方法如感知機(jī)[1]、決策樹(shù)[2]、樸素貝葉斯模型[3]、Logistic 回歸[4]、支持向量機(jī)[5]等,眾多的方法都是為了提高分類模型的性能而設(shè)計(jì)提出,但是不平衡數(shù)據(jù)的出現(xiàn)會(huì)導(dǎo)致訓(xùn)練得到的分類器對(duì)多數(shù)類的感知能力強(qiáng)于對(duì)少數(shù)類的感知能力,這對(duì)諸如醫(yī)學(xué)診斷、信用卡欺詐檢測(cè)等應(yīng)用場(chǎng)景是十分不利的,因此,如何提高不平衡數(shù)據(jù)集的分類器性能已經(jīng)成為機(jī)器學(xué)習(xí)領(lǐng)域的熱點(diǎn)問(wèn)題,眾多解決不平衡數(shù)據(jù)問(wèn)題的新方法也不斷被提出.

目前,解決非平衡數(shù)據(jù)集的方式主要有兩種:一種是從算法的改進(jìn)入手,該方式從生成新的分類策略、分類器集成[6]、代價(jià)敏感[7]、特征選擇[8]等方面進(jìn)行改進(jìn);另一種是從數(shù)據(jù)集的處理入手,這也是重要的處理不平衡問(wèn)題的方式,主要采用包括欠采樣[9]、過(guò)采樣[10]、訓(xùn)練集劃分等降低數(shù)據(jù)集的不平衡程度.其中,欠采樣方法容易造成有用信息的丟失,過(guò)采樣方法容易造成分類器的過(guò)擬合[11].本文由此出發(fā),從生物遺傳理論[12]中得到啟發(fā),利用“近親”(同類臨近數(shù)據(jù))生成有相似特性而又和“父類”不完全相同的少數(shù)類數(shù)據(jù),在平衡兩類數(shù)據(jù)的同時(shí)又極大降低傳統(tǒng)方法中過(guò)擬合的現(xiàn)象.

1 相關(guān)工作

解決數(shù)據(jù)不平衡問(wèn)題時(shí),在數(shù)據(jù)處理方面,采樣的方式分為非啟發(fā)式采樣和啟發(fā)式采樣,本文提出的合成少數(shù)類樣本是典型的啟發(fā)式方法.此外,啟發(fā)式過(guò)采樣方法還結(jié)合了K 近鄰準(zhǔn)則(K-nearest neighbor,KNN)[13]、鄰域清理準(zhǔn)則(neighborhood cleaning rule,NCL)[14]、OSS(one-sided selection)[15]和IRUS (inverse random under sampling)[16]等.

Chawla 等在2002年提出了少數(shù)類樣本合成技術(shù),即SMOTE (synthetic minority over-sampling technique)[17].此方法與隨機(jī)過(guò)采樣方法不同,它是通過(guò)在少數(shù)類樣本與其k個(gè)最近鄰居連線上合成新樣本,合成公式如下:

使用傳統(tǒng)的SMOTE 算法會(huì)增加子集群的大小,生成的每個(gè)數(shù)據(jù)實(shí)例都屬于指定的集群,加劇了類內(nèi)的數(shù)據(jù)不平衡.該方法中對(duì)實(shí)例點(diǎn)A和B進(jìn)行過(guò)采樣,生成的點(diǎn)會(huì)落到各自的簇中,估計(jì)的決策邊界會(huì)向?qū)嵗芗娜嚎拷?而不是向?qū)嶋H邊界靠近.正如Barua的結(jié)論:這些問(wèn)題的出現(xiàn)是因?yàn)檫@些方法選擇了所有k個(gè)最近的鄰居,而忽略了數(shù)據(jù)點(diǎn)與這些鄰居間的位置關(guān)系和距離關(guān)系.

隨后,Freund 等提出了AdaBoost 算法[18],是一種經(jīng)典的集成算法,該算法相對(duì)傳統(tǒng)算法具有更好的泛化能力,更高的分類精度.Chawla 等將SMOTE 方法和AdaBoost.M2 算法相結(jié)合,在每次迭代中引入合成樣本,提出SMOTEBoost 分類算法[17].Kinoshita 等提出了聯(lián)合隨機(jī)降采樣與Boosting的RUSBoost 算法[19],是SMOTEBoost的變形.李克文等[20]提出基于 RSBoost的不平衡數(shù)據(jù)分類方法,該方法采取 SMOTE 過(guò)采樣和隨機(jī)降采樣,再將其與Boosting 算法相結(jié)合對(duì)數(shù)據(jù)進(jìn)行分類:李雄飛等提出一種新的不平衡數(shù)據(jù)學(xué)習(xí)算法PCBoost[21],每次迭代初始,考慮屬性特征,合成新的少數(shù)類樣本,平衡訓(xùn)練信息.

上述研究中,各種改進(jìn)過(guò)采樣的方法改善了類間的數(shù)據(jù)不平衡,一定程度上提高了分類器的性能,雖然較原生AdaBoost 方法取得了較大的進(jìn)步,但仍然需要繼續(xù)關(guān)注和改進(jìn),進(jìn)一步提高不平衡數(shù)據(jù)的分類精度.本文提出的改進(jìn)方法充分考慮了類間和類內(nèi)的不平衡,使少數(shù)類邊界最大化,更好地模擬數(shù)據(jù)的分布,提高樣本的總體質(zhì)量.

2 基于遺傳理論的不平衡數(shù)據(jù)過(guò)采樣方法

2.1 染色體遺傳理論

根據(jù)基礎(chǔ)生物學(xué)和遺傳學(xué),位于染色體上的基因是遺傳的基本單位,受精卵形成過(guò)程中,有父母雙方各一半染色體等量組合,這就是染色體遺傳理論.

引入集合M=(m_1,m_2,m_3,…,m_q)和F=(f_1,f_2,f_3,…,f_q)分別代表來(lái)自父母雙方的一對(duì)染色體,A、B為控制個(gè)體性狀的等位基因,新個(gè)體產(chǎn)生過(guò)程中同源染色體上的等位基因彼此分離,非同源染色體上的非等位基因自由組合,如圖1所示.生物遺傳理論的發(fā)現(xiàn)對(duì)生物學(xué)、農(nóng)業(yè)等領(lǐng)域都掀起了巨大的轟動(dòng),對(duì)該理論的應(yīng)用取得了重大的成果.生物學(xué)家通過(guò)基因工程得到了更高產(chǎn),抵抗災(zāi)害能力更強(qiáng)的作物極大促進(jìn)了人類社會(huì)生產(chǎn)力的發(fā)展.從中得到啟發(fā),我們可以通過(guò)相似性度量來(lái)分離數(shù)據(jù)樣本,合理的對(duì)有缺陷的類進(jìn)行過(guò)采樣.與遺傳理論不同的是:遺傳理論強(qiáng)調(diào)基因?qū)€(gè)體性狀的影響,而用于采樣方法中的遺傳理論強(qiáng)調(diào)個(gè)體的多樣性;遺傳理論中,生成新的個(gè)體后父類個(gè)體逝去,而該采樣方法中,父類數(shù)據(jù)個(gè)體和子數(shù)據(jù)個(gè)體會(huì)同時(shí)存在于集合中.

圖1 生物遺傳理論染色體結(jié)合圖解

2.2 基于遺傳理論的過(guò)采樣原理

利用染色體遺傳理論,將缺陷模塊的特征指標(biāo)作為染色體.改進(jìn)的過(guò)采樣方法分為3 個(gè)階段:首先,分離出少數(shù)類與多數(shù)類樣本,并按照少數(shù)類樣本相對(duì)本類樣本的馬氏距離進(jìn)行降序排列;將已排序少數(shù)類樣本從中心點(diǎn)分割為兩份數(shù)據(jù)集,并依次為相應(yīng)數(shù)據(jù)集中的每個(gè)實(shí)例分配唯一標(biāo)簽;最后,從兩個(gè)分區(qū)中選擇有相同唯一標(biāo)簽的實(shí)例求均值生成新的實(shí)例.算法1列出了整個(gè)過(guò)程.

算法1.基于遺傳理論的過(guò)采樣算法(1) 將數(shù)據(jù)集按照少數(shù)類與多數(shù)類進(jìn)行劃分獲得集合Nmin、Nmaj;(2) 計(jì)算可使數(shù)據(jù)集達(dá)到平衡的所需合成的少數(shù)類樣本數(shù)T,并記k為少數(shù)類樣本集樣本數(shù);Xnew(3) 建立容納合成數(shù)據(jù)的集合,初始化為空;Xnewc(4) 建立記錄合成數(shù)據(jù)數(shù)量的數(shù)據(jù)集,初始化為空;(5)計(jì)算Nmin 中樣本的馬氏距離D2;(6)創(chuàng)建馬氏距離矩陣Nmindist,將數(shù)據(jù)按照遞減順序進(jìn)行存儲(chǔ);(7)確定中間實(shí)例Nmid;(8)將Nmindist 以Nmid為界分為兩個(gè)子集,分別記為Nbin1={x1,x2,x3,…,xmid}和Nbin2={xmin+1,xmin+2,xmin+3,…,xk},其中;xi∈Nbin1 xi∈Nbin2 lii=1,2,3,···,mid xi∈Nmidist(9)為和中的樣本按次序分配標(biāo)簽,;i=1,2,3,···,mid(10) for (11)1)選擇和中標(biāo)簽相同的樣本,如;xa,xb 2)通過(guò)取 均值生成少數(shù)類樣本x Nbin1 Nbin2 lixa(li)==xb(li)3)將x 添加到 中,增加(12) end for Xnewc

圖解(圖2)過(guò)程如下:第1 步,根據(jù)數(shù)據(jù)點(diǎn)的馬氏距離找到起始雙親即S1和S2,合成新樣本C01,為了防止傳統(tǒng)SMOTE 方法中的滲透現(xiàn)象,設(shè)定初始父節(jié)點(diǎn)作為邊界,將后續(xù)生成的子節(jié)點(diǎn)限定在父類的范圍內(nèi),如果需要更多的實(shí)例,在第2 代中,利用新生成的實(shí)例分別與父節(jié)點(diǎn)(S1、S2)繼續(xù)生成新的節(jié)點(diǎn).在第3 代中,如果子節(jié)點(diǎn)和直接父節(jié)點(diǎn)配對(duì)生成的樣本小于所需的樣本數(shù)量,則利用祖父節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)繼續(xù)配對(duì)生成新的節(jié)點(diǎn),當(dāng)前層級(jí)的所有配對(duì)情況均已完成后若仍不滿足樣本需求,則繼續(xù)按照此規(guī)則進(jìn)行下一層級(jí)新樣本的生成直至滿足所需樣本數(shù)量.從第1 代開(kāi)始,調(diào)用的是算法1的步驟(10)–(14).

圖2 圖解少數(shù)類樣本生成過(guò)程

實(shí)例點(diǎn)x=(x1,x2,x3,…,xn)T與實(shí)例點(diǎn)y=(y1,y2,y3,…,yn)T之間的馬氏距離可表示為:=(其中,M是多維隨機(jī)變量的協(xié)方差矩陣,它的冪為–1 表示求其逆矩陣),我們使用這個(gè)度量將數(shù)據(jù)點(diǎn)進(jìn)行降序排列,以便于我們區(qū)分出數(shù)據(jù)點(diǎn)離中心點(diǎn)的距離.將本文所提出的過(guò)采樣方法記為GOS (genetic over-sampling)算法,其執(zhí)行過(guò)程如下:

GOS 算法的流程圖如圖3所示.基于Pfp的值,算法計(jì)算要生成的合成數(shù)據(jù)實(shí)例的數(shù)量,對(duì)已生成但不需要的數(shù)據(jù)進(jìn)行剔除.最后一層以上的合成數(shù)據(jù)點(diǎn)全部存儲(chǔ)至最終數(shù)據(jù)集中.冗余數(shù)據(jù)的刪除從所生成的最后一層數(shù)據(jù)開(kāi)始,方法是將完成所需最終集的剩余數(shù)據(jù)樣本量除以該層上的樣本總數(shù)得到選擇概率Pc.然后以概率值Pc在最后一層中選擇保留樣本,這意味著上一級(jí)別的每個(gè)樣本可為所需新生成數(shù)據(jù)作出相同貢獻(xiàn).

圖3 GOS 算法流程圖

基于所設(shè)定的兩個(gè)分區(qū),新生成的實(shí)例與其父實(shí)例是密切相關(guān)的,兩個(gè)分區(qū)之間的順序限定保證了子實(shí)例的遵循父實(shí)例的趨勢(shì),新的實(shí)例就被限制在了少數(shù)類樣本的邊界之內(nèi),同時(shí)避免了樣本的重疊現(xiàn)象.相對(duì)于KNN,改進(jìn)算法所生成的樣本分布更加均勻,攜帶的信息量更大.

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證本文遺傳過(guò)采樣算法的表現(xiàn),探究分類預(yù)測(cè)模型能否借助本文采樣方法提升預(yù)測(cè)精度,實(shí)驗(yàn)部分將本文方法(GOS)同SMOTE、Borderline-SMOTE、隨機(jī)過(guò)采樣(ROS),和非采樣方法(None)進(jìn)行比較.實(shí)驗(yàn)數(shù)據(jù)集采用UCI 公共數(shù)據(jù)集中的數(shù)據(jù),數(shù)據(jù)詳情如表1所示,其中Yeast 數(shù)據(jù)集中將EM1、EXC、VAC作為正類,CYT、NUC、MIT 作為負(fù)類;Ecoli 數(shù)據(jù)集中將第2、4、5、6 類作為正類,其余作為負(fù)類.

表1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)結(jié)果的評(píng)價(jià)指標(biāo)采用召回率及幾何平均值Gmean,其表達(dá)式如式(2)、式(3)所示,式中變量含義如表2所示.其中,召回率越高,則說(shuō)明分類器對(duì)少數(shù)類樣本的識(shí)別性能越好,可以反映出分類器對(duì)少數(shù)類樣本的識(shí)別敏感度;G-mean值彌補(bǔ)了召回率作為評(píng)價(jià)指標(biāo)的片面性,該評(píng)價(jià)公式將少數(shù)類的識(shí)別準(zhǔn)確率和多數(shù)類的識(shí)別準(zhǔn)確率同時(shí)考慮在內(nèi),可更加綜合的反映出算法的總體預(yù)測(cè)分類性能.

表2 混淆矩陣

對(duì)實(shí)驗(yàn)數(shù)據(jù)的準(zhǔn)備主要包括預(yù)處理、備份、數(shù)據(jù)劃分.具體為首先經(jīng)過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)執(zhí)行集成、規(guī)約、變換等預(yù)處理后將6 個(gè)數(shù)據(jù)集進(jìn)行復(fù)制備份至5 份,分別采用5 種采樣方式進(jìn)行采樣得到目標(biāo)實(shí)驗(yàn)數(shù)據(jù)集,對(duì)每個(gè)數(shù)據(jù)集按照4:1的比例劃分訓(xùn)練集和測(cè)試集,而后,分別在3 種分類模型(BP、SVM、決策樹(shù))的作用下進(jìn)行測(cè)試,以對(duì)比各采樣方式在不同分類模型中對(duì)最終結(jié)果的影響,其中每項(xiàng)最終實(shí)驗(yàn)數(shù)據(jù)均采用10 折交叉驗(yàn)證的方式產(chǎn)生.其中,采用3 種對(duì)比算法的目的是減小實(shí)驗(yàn)結(jié)果的偶然性,提升實(shí)驗(yàn)結(jié)果的說(shuō)服力.

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

經(jīng)過(guò)對(duì)比試驗(yàn),各分類算法在不同采樣方式的作用下產(chǎn)生的分類結(jié)果如表3、表4所示,表3為各算法在召回率(Recall)評(píng)價(jià)中的表現(xiàn).由表中數(shù)據(jù)可以看出,由于數(shù)據(jù)集Breast Cancer和Hepatitis 平衡率較高,采樣算法甚至無(wú)需執(zhí)行,GOS 采樣方式對(duì)其召回率的提升并不明顯,除了SMOTE 采樣方式下的BP 實(shí)驗(yàn)結(jié)果和Borderline-SMOTE 采樣方式下的SVM 實(shí)驗(yàn)結(jié)果外,本文采樣方式下的分類結(jié)果和相對(duì)應(yīng)的分類算法所獲取的次優(yōu)結(jié)果相比,仍然以最低1%,最高4%的優(yōu)勢(shì)取得最優(yōu)的召回率值;對(duì)于數(shù)據(jù)集Spambase和Steel Pastry,其不平衡率相對(duì)加劇,GOS 采樣方式對(duì)其召回率的提升相對(duì)明顯,和次優(yōu)結(jié)果相比平均提升了4.1%;Yeast和Ecoli 數(shù)據(jù)集的平衡率最低,GOS 采樣方法對(duì)各算法的召回率性能提升也最為明顯,達(dá)到了4.8%.表3數(shù)據(jù)表明采樣方法可以提升算法對(duì)正類樣本的錯(cuò)分概率,有效緩解不平衡數(shù)據(jù)對(duì)算法性能的影響.

表3 各算法在不同采樣方式下的Recall 值

表4為各分類算法在不同采樣方式的作用下取得的G-mean值,從表中數(shù)據(jù)可得,Breast Cancer和Hepatitis兩個(gè)較為平衡的數(shù)據(jù)集在SMOTE和Borderline-SMOTE采樣方法中以BP 分類算法和SVM 分類算法取得了1%優(yōu)勢(shì),這是由于采樣方法對(duì)數(shù)據(jù)集的改變較弱,實(shí)驗(yàn)結(jié)果主要取決于原始數(shù)據(jù),采樣對(duì)算法性能提升不明顯;除此之外,本文采樣法下的算法均取得了最優(yōu)的G-mean值.表4的實(shí)驗(yàn)結(jié)果進(jìn)一步印證了本文算法的有效性.

表4 各算法在不同采樣方式下的G-mean 值

對(duì)本文所提出方法的表現(xiàn)更為優(yōu)異的原因進(jìn)行簡(jiǎn)要分析,這可以歸因于該方法所生成的樣本在少數(shù)類邊界內(nèi)簡(jiǎn)潔且同原樣本的分布更為相似,擴(kuò)散更加均勻.從樣本多樣性角度考慮,通過(guò)計(jì)算重采樣數(shù)據(jù)樣本中少數(shù)類中每個(gè)度量的多樣性,每個(gè)指標(biāo)的多樣性計(jì)算使用香農(nóng)多樣性指數(shù)來(lái)評(píng)價(jià),通過(guò)該評(píng)價(jià)指標(biāo)我們發(fā)現(xiàn)GOS 對(duì)樣本多樣性的增加是最為明顯的.

4 總結(jié)與展望

本文針對(duì)現(xiàn)行分類算法對(duì)不平衡數(shù)據(jù)集的正類數(shù)據(jù)預(yù)測(cè)性能偏低的情況提出一種基于遺傳思想的過(guò)采樣方法,該方法在不改變數(shù)據(jù)分布的前提下,通過(guò)合成少數(shù)類數(shù)據(jù)實(shí)例來(lái)平衡數(shù)據(jù)集中的正負(fù)樣本成分.該采樣方式避免了常見(jiàn)合成方式會(huì)產(chǎn)生錯(cuò)誤或重復(fù)的數(shù)據(jù)導(dǎo)致高負(fù)類率的情形,馬氏距離的使用確保了合成數(shù)據(jù)不會(huì)跨越分類算法的決策邊界.通過(guò)在6 個(gè)公共數(shù)據(jù)集上使用3 種分類模型,將本文方法和其他4 種采樣方法進(jìn)行比較,經(jīng)90 個(gè)實(shí)驗(yàn)組合結(jié)果驗(yàn)證,本文采樣方式在召回率和G-mean兩個(gè)評(píng)價(jià)指標(biāo)上均取得了綜合最優(yōu)的結(jié)果,證明了本文采樣方式的有效性.在未來(lái)的研究中,對(duì)GOS 在多分類模型中的引入應(yīng)用可進(jìn)一步擴(kuò)展該采樣法方法的應(yīng)用價(jià)值.