面向非平衡數(shù)據(jù)分類的概率過抽樣過濾方法

孟慶鵬，田開嚴，張 恒

(1.海軍裝備部駐南京地區(qū)第二軍事代表室，南京 211153；2.中國船舶集團有限公司第八研究院，南京 211153)

0 引 言

非平衡數(shù)據(jù)分類問題是機器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的一個重要研究方向，近年來越來越受到研究者的關(guān)注，如自然災(zāi)害、癌癥基因表達、虛假信用卡交易、電信詐騙、雷達干擾識別、雷達孤立雜波點剔除等。非平衡數(shù)據(jù)集中某些類樣本數(shù)量顯著多于另外一些類樣本數(shù)量，在二分類問題中常把數(shù)據(jù)量較多的類稱作多數(shù)類數(shù)據(jù)(負類)，數(shù)據(jù)量較少的類稱作少數(shù)類數(shù)據(jù)(正類)。這類問題有一個共同的特點，即少數(shù)類樣本信息才是關(guān)注的重點。關(guān)于類不平衡問題的解決方法可以分為3類，它們分別是數(shù)據(jù)預(yù)處理方法、代價敏感方法和算法級方法。

本文提出面向非平衡數(shù)據(jù)分類的概率過抽樣過濾方法。通過概率過抽樣方法處理非平衡數(shù)據(jù)集，考慮數(shù)據(jù)真實概率分布，使得重抽樣的數(shù)據(jù)更具代表性，符合數(shù)據(jù)規(guī)律。再通過基于非合作博弈理論的過濾方法將獲得的少數(shù)類合成數(shù)據(jù)進行預(yù)識別，使其獲得最可能的類標簽，進而去除非本類數(shù)據(jù)，消除數(shù)據(jù)重疊，獲得更高質(zhì)量的少數(shù)類合成數(shù)據(jù)。最后，建立模型的分類性能得到有效提高。

1 快速收斂吉布斯抽樣

快速收斂吉布斯[1](RApidy COnverging Gibbs ，RACOG)抽樣通過Chow-Liu[2]算法近似少數(shù)類數(shù)據(jù)的概率分布，使用吉布斯(Gibbs)抽樣生成新的少數(shù)類數(shù)據(jù)。RACOG通過賦值隨機變量的初始值來加強標準的吉布斯抽樣。一般情況下，吉布斯抽樣的隨機變量初始值是從屬性的狀態(tài)空間隨機選擇。RACOG將少數(shù)類數(shù)據(jù)點作為初始樣本的集合，然后為每個少數(shù)類數(shù)據(jù)執(zhí)行吉布斯抽樣。它產(chǎn)生多個馬爾科夫鏈(Markov Chains)。每個鏈由不同的少數(shù)類樣本開始，不像傳統(tǒng)的吉布斯抽樣產(chǎn)生一個很長的馬爾科夫鏈。它的初始值從少數(shù)類樣本直接選擇，在產(chǎn)生新數(shù)據(jù)時實現(xiàn)更快的收斂。

(1)

吉布斯抽樣取決于兩個重要因素，一個是為了實現(xiàn)穩(wěn)定的分布來生成樣本的迭代數(shù)量，另一個是從馬爾科夫鏈丟棄的連續(xù)樣本的數(shù)量。

2 面向非平衡數(shù)據(jù)分類的概率過抽樣過濾方法

博弈理論是關(guān)于策略決策或相互作用的決策研究。博弈分為多種類型，如合作的和非合作的、對稱的和非對稱等類型。非合作類型的博弈用于處理單個理性決策者之間的相互作用。博弈包括玩家(Players)的集合，對于每個玩家可用策略集合以及每個組合策略的收益(Payoffs)。

(2)

(3)

其中，α是控制增長率的常量，將具有最高概率的策略作為其類標簽。

算法1 RACOG+F算法Input: 非平衡數(shù)據(jù)集D,迭代的數(shù)量hOutput: 非平衡數(shù)據(jù)集分類指標1 初始化相關(guān)參數(shù);2 通過Chow-Liu算法構(gòu)建相依樹來近似少數(shù)類樣本DI的離散概率分布;3 while{t

將近似概率分布中抽樣合成的新少數(shù)類數(shù)據(jù)合并到DN中。為了實現(xiàn)對合成數(shù)據(jù)DN的進一步過濾故將其作為未帶標簽數(shù)據(jù)。將未帶標簽數(shù)據(jù)DN和原始數(shù)據(jù)D作為兩種不同類型的玩家，數(shù)據(jù)的類標簽作為每個玩家的可用策略Si={I,A}。對于DN中的i玩家來說，通過歐氏距離從數(shù)據(jù)集{D∪DN}中計算它的k個最近鄰居Dk。為了既不丟失算法精度又使算法快速執(zhí)行，本文將最近鄰數(shù)量k設(shè)定為5，即每個玩家的5個鄰居玩家。將i和它的5個鄰居玩家相互作用通過公式(2)計算收益ui(x)，收益為i與每個鄰居玩家作用收益的總和是玩家i的總體收益。

(4)

將具有最高概率的策略作為i玩家選擇的策略，即最可能的類標簽。將此過程迭代進行，找到DN中所有樣本的最可能類標簽，將非本類樣本去除，以此來過濾合成數(shù)據(jù)DN，得到高質(zhì)量的合成數(shù)據(jù)。將過濾后的DN合并到原始數(shù)據(jù)集D={DI∪DA∪DN}，分別通過CART和SVM為D建立模型獲得分類性能。基于非合作博弈理論的過濾方法可以對合成少數(shù)類數(shù)據(jù)進行預(yù)識別，進化學(xué)習(xí)獲得合成少數(shù)類數(shù)據(jù)最可能的類標簽，找到合成數(shù)據(jù)中的非本類數(shù)據(jù)，將其去除獲得“純凈”的合成少數(shù)類數(shù)據(jù)DN，減少數(shù)據(jù)重疊。

3 實驗設(shè)計與結(jié)果分析

為了評估提出的RACOG+F與原始過抽樣方法的分類性能，實驗采取了CART和SVM作為基分類器。全部的實驗采取5折交叉驗證作為驗證和測試方法，每個數(shù)據(jù)集的分類結(jié)果用這5次的均值和標準差表示。

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

實驗所用數(shù)據(jù)來自KEEL數(shù)據(jù)庫。表1展示了實驗所用數(shù)據(jù)集的特征，包括數(shù)據(jù)集名稱、樣本數(shù)、屬性數(shù)、少數(shù)類樣本數(shù)和非平衡率。

表1 數(shù)據(jù)集

3.2 評價標準

為了在評價性能時更多地關(guān)注少數(shù)類數(shù)據(jù)，本文使用F-measure(精度和召回率的調(diào)和均值)、G-mean(靈敏度和特效性積的平方根)、AUC(真正率相對于假正率的差異)3個評價指標來驗證和比較各個算法。通過表2展示的混淆矩陣可以得到正確或錯誤分類某類數(shù)據(jù)的情況。

表2 二分類問題混淆矩陣

3.3 實驗結(jié)果及分析

表3和表4展示了以CART和SVM作為基分類器各個算法在不同數(shù)據(jù)集上的不同性能值，性能評價指標為F-measure、G-mean、AUC(分別簡寫為F.、G.、A.)。提出的方法RACOG+F的最好結(jié)果用粗體表示，每張表最后一列Filter展示了通過過濾方法過濾掉新生成的少數(shù)類數(shù)據(jù)的數(shù)量。

表3是以CART作基分類器，RACOG+F相比于RACOG在F-measure、G-mean、AUC平均性能上分別提高了2.6%、2.8%、3%。RACOG+F方法除了在數(shù)據(jù)集haberman上都獲得了最高的性能值，優(yōu)于原始的RACOG和Baseline。而對于數(shù)據(jù)集haberman來說，RACOG+F方法的F-measure、G-mean弱于原始的RACOG方法，但AUC結(jié)果高于RACOG。在此數(shù)據(jù)集上RACOG+F雖然過濾掉了噪聲數(shù)據(jù)，但也丟失了更好地建立決策樹的樣本導(dǎo)致分類結(jié)果F-measure、G-mean不好。

表4是以SVM作基分類器，RACOG+F相比于RACOG在F-measure、G-mean、AUC平均性能上分別提高了2.6%、2.6%、2.6%。相比于原始的RACOG和Baseline, RACOG+F方法在所有的8個數(shù)據(jù)集上都獲得了最高的性能值。而對于數(shù)據(jù)集haberman來說，RACOG+F方法以SVM作為基分類器，各項指標也都高于RACOG。相比于以CART做基分類器，經(jīng)過過濾處理的數(shù)據(jù)集haberman使得SVM更能獲得較好的分類超平面來分類此數(shù)據(jù)集。

表3 CART做基分類器的不同性能值

圖1和圖2展示了以RACOG進行過抽樣不同方法在不同數(shù)據(jù)集上的AUC分類性能圖。從圖中可以看出，本文提出的方法RACOG+F相比于其他方法取得了較好的分類結(jié)果，是一種處理非平衡分類問題的有效方法。

圖3展示yeast4數(shù)據(jù)集的原始散點圖：RACOG過抽樣方法處理數(shù)據(jù)的散點圖以及過濾方法RACOG+F處理數(shù)據(jù)的散點圖。通過散點圖可以明顯看出，原始數(shù)據(jù)集通過概率過抽樣方法近似其概率分布，抽樣增加了少數(shù)類數(shù)據(jù)數(shù)量，使得數(shù)據(jù)傾斜情況得到較大改善，同時也使得數(shù)據(jù)產(chǎn)生了一些“噪聲”，如少數(shù)類數(shù)據(jù)重疊在多數(shù)類數(shù)據(jù)上，使得分類邊界變得模糊。再將新的合成數(shù)據(jù)進行過濾后，可以明顯發(fā)現(xiàn)數(shù)據(jù)分類的邊界更加清晰，類之間重疊減少。實驗也證實，用CART和SVM建立模型，過濾方法RACOG+F相比于基分類器分類和RACOG過抽樣方法明顯提高了F-measure、G-mean、AUC性能值。圖3從數(shù)據(jù)形態(tài)層面可以得出，使用過濾的概率過抽樣方法可以較為明顯地獲得高質(zhì)量的分類邊界，提高分類性能，這在數(shù)據(jù)指標評價層面也得到了很好的驗證。

圖1 CART作基分類器的AUC值

圖2 SVM作基分類器的AUC值

圖3 各方法處理yeast4數(shù)據(jù)集的散點圖

4 結(jié)束語

將概率過抽樣方法合成的新少數(shù)類數(shù)據(jù)進一步過濾，去除其中“噪聲”數(shù)據(jù)(非本類數(shù)據(jù))，得到高質(zhì)量的分類邊界，提高了非平衡數(shù)據(jù)的分類性能。概率過抽樣方法RACOG雖然近似了少數(shù)類數(shù)據(jù)原始概率分布，使得新生成的數(shù)據(jù)更能反映其真實數(shù)據(jù)規(guī)律，優(yōu)于通過簡單復(fù)制或樣本特征空間相似性來增加少數(shù)類數(shù)據(jù)數(shù)量的方法。但是，新合成的少數(shù)類數(shù)據(jù)依然存在數(shù)據(jù)重疊現(xiàn)象，將其通過基于非合作博弈理論的方法進行預(yù)識別，去除非本類數(shù)據(jù)，與原始概率過抽樣方法相比得到了更高質(zhì)量的合成數(shù)據(jù)，有效提高了非平衡數(shù)據(jù)集分類性能。此方法不僅使數(shù)據(jù)集數(shù)據(jù)形態(tài)上獲得了高質(zhì)量的分類邊界，在數(shù)據(jù)結(jié)果上也得到了很好的驗證。