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

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

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

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

1 相關(guān)工作

解決數(shù)據(jù)不平衡問題時,在數(shù)據(jù)處理方面,采樣的方式分為非啟發(fā)式采樣和啟發(fā)式采樣,本文提出的合成少數(shù)類樣本是典型的啟發(fā)式方法.此外,啟發(fā)式過采樣方法還結(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ī)過采樣方法不同,它是通過在少數(shù)類樣本與其k個最近鄰居連線上合成新樣本,合成公式如下:

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

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

上述研究中,各種改進(jìn)過采樣的方法改善了類間的數(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ù)過采樣方法

2.1 染色體遺傳理論

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

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

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

2.2 基于遺傳理論的過采樣原理

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

算法1.基于遺傳理論的過采樣算法(1) 將數(shù)據(jù)集按照少數(shù)類與多數(shù)類進(jìn)行劃分獲得集合Nmin、Nmaj;(2) 計算可使數(shù)據(jù)集達(dá)到平衡的所需合成的少數(shù)類樣本數(shù)T,并記k為少數(shù)類樣本集樣本數(shù);Xnew(3) 建立容納合成數(shù)據(jù)的集合,初始化為空;Xnewc(4) 建立記錄合成數(shù)據(jù)數(shù)量的數(shù)據(jù)集,初始化為空;(5)計算Nmin 中樣本的馬氏距離D2;(6)創(chuàng)建馬氏距離矩陣Nmindist,將數(shù)據(jù)按照遞減順序進(jìn)行存儲;(7)確定中間實例Nmid;(8)將Nmindist 以Nmid為界分為兩個子集,分別記為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)通過取 均值生成少數(shù)類樣本x Nbin1 Nbin2 lixa(li)==xb(li)3)將x 添加到 中,增加(12) end for Xnewc

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

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

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

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

圖3 GOS 算法流程圖

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

3 實驗分析

3.1 實驗設(shè)置

為驗證本文遺傳過采樣算法的表現(xiàn),探究分類預(yù)測模型能否借助本文采樣方法提升預(yù)測精度,實驗部分將本文方法(GOS)同SMOTE、Borderline-SMOTE、隨機(jī)過采樣(ROS),和非采樣方法(None)進(jì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ù)據(jù)

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

表2 混淆矩陣

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

3.2 實驗結(jié)果分析

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

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

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

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

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

4 總結(jié)與展望

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