基于遺傳理論的改進數據過采樣方法①

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

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

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

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

1 相關工作

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

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

使用傳統的SMOTE 算法會增加子集群的大小,生成的每個數據實例都屬于指定的集群,加劇了類內的數據不平衡.該方法中對實例點A和B進行過采樣,生成的點會落到各自的簇中,估計的決策邊界會向實例密集的群靠近,而不是向實際邊界靠近.正如Barua的結論:這些問題的出現是因為這些方法選擇了所有k個最近的鄰居,而忽略了數據點與這些鄰居間的位置關系和距離關系.

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

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

2 基于遺傳理論的不平衡數據過采樣方法

2.1 染色體遺傳理論

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

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

圖1 生物遺傳理論染色體結合圖解

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

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

算法1.基于遺傳理論的過采樣算法(1) 將數據集按照少數類與多數類進行劃分獲得集合Nmin、Nmaj;(2) 計算可使數據集達到平衡的所需合成的少數類樣本數T,并記k為少數類樣本集樣本數;Xnew(3) 建立容納合成數據的集合,初始化為空;Xnewc(4) 建立記錄合成數據數量的數據集,初始化為空;(5)計算Nmin 中樣本的馬氏距離D2;(6)創建馬氏距離矩陣Nmindist,將數據按照遞減順序進行存儲;(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)為和中的樣本按次序分配標簽,;i=1,2,3,···,mid(10) for (11)1)選擇和中標簽相同的樣本,如;xa,xb 2)通過取 均值生成少數類樣本x Nbin1 Nbin2 lixa(li)==xb(li)3)將x 添加到 中,增加(12) end for Xnewc

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

圖2 圖解少數類樣本生成過程

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

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

圖3 GOS 算法流程圖

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

3 實驗分析

3.1 實驗設置

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

表1 實驗數據

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

表2 混淆矩陣

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

3.2 實驗結果分析

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

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

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

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

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

4 總結與展望

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