基于稀疏表示的不平衡數據集過采樣算法

訾壯壯 何 濤 趙 停

1(南京郵電大學電子與光學工程學院 江蘇 南京 210023) 2(南京郵電大學工程訓練中心 江蘇 南京 210023)

0 引 言

不平衡數據作為數據挖掘中最具挑戰性的問題之一[1]，越來越受到人們的重視。不平衡數據是指不同類別樣本數量存在比例失衡的數據集。盡管大多數據具有多類屬性，但是許多情況下仍然可以轉換為二分類問題，因此本文主要研究二分類問題。在只有兩個類別的數據集中，多數類是指樣本數量相對較多的類，少數類是指樣本數量相對較少的類。不平衡數據集在欺詐檢測、文本分類、醫療診斷、推薦系統和其他實際應用中非常普遍。在上述應用中，人們通常對少數類樣本更感興趣，然而傳統的分類器通常偏向多數類，無法對少數類樣本進行正確分類，因此性能較差。

有兩種方法可以用于解決類不平衡問題，它們分別是數據層面的解決方案和算法層面的解決方案。數據層面的解決方案是通過欠采樣和過采樣或二者的組合來平衡少數類樣本和多數類樣本的分布。算法層面的解決方案是通過改進傳統的分類算法或優化學習算法的性能來提高少數類樣本的識別率[2]。數據層面解決方案由于其獨立于分類算法，可與任何傳統的分類算法相結合而更受歡迎。

大多數不平衡數據集過采樣方法通過生成新的少數類樣本以減輕類不平衡問題，這些方法通常依賴于歐幾里得特征空間中少數類樣本的空間位置，收集少數類樣本的局部信息以生成新的少數類樣本。使得新生成的樣本不遵循原始少數類樣本的分布，因此含有較少的信息量。而更好的想法是利用少數類樣本的全局信息，這可以在生成新樣本的同時考慮稀疏表示來實現。

本文提出一種基于稀疏表示的不平衡數據集過采樣算法KSOS。在樣本生成階段，使用少數類樣本來構造稀疏字典，通過求解L1范數最小化來獲得當前點的稀疏解，然后使用稀疏解中的非零項所對應的少數類樣本來生成新樣本。在樣本確認階段,計算每一個新生成樣本的置信度，然后將所有新生成樣本按其置信度排序，從中選取符合要求的新生成樣本。

1 相關工作

不平衡主要有三種：類間不平衡、類內不平衡和類重疊。幾乎所有的過采樣方法都可以通過重復原始少數類樣本或生成新的少數類樣本來解決類間不平衡問題。對于類內不平衡問題，常見方法是首先使用聚類技術來發現少數類子群，然后應用過采樣方法來處理這些子群，或者在用其局部分布衡量學習難度后，對難以學習的少數群體樣本進行加權。而當原始非重疊區域被噪聲和錯誤的生成樣本入侵時，就會出現類重疊問題。

隨機過采樣通過簡單重復部分少數類樣本的方式來達成少數類和多數類樣本在訓練規模上的平衡。然而隨機過采樣技術可能導致過擬合問題，因為它可能創建比原始數據集更小且更具特異性的決策區域。

使用基于樣本生成的過采樣技術來解決類不平衡問題也很普遍。SMOTE[3]被提出用于生成少數類樣本，以擴大少數類樣本的原始決策區域。SMOTE隨機選擇一個少數類樣本x，使用KNN在其余所有少數類樣本中選出x的K個近鄰樣本，并取出其中任意一個x′，然后在x和x′之間連線的任一位置生成新的少數類樣本。SMOTE雖然在減少過擬合方面取得了進展，但卻引發了過度泛化的問題。許多SMOTE的擴展算法也相繼被提出，例如B-SMOTE[4]、Safe-Level-SMOTE[5]、Random-SMOTE[6]，實驗表明生成的樣本比簡單復制的樣本更具信息量。

自適應技術也被廣泛用于不平衡數據集過采樣。自適應合成采樣ADASYN[7]考慮到難以學習的少數類樣本，并根據其局部分布自動合成少數類樣本。自適應半無監督加權過采樣A-SUWO[8]，應用半無監督分層聚類方法對少數類樣本進行聚類，并根據其特定大小自適應地對每個子聚類進行過采樣。

2 算法設計

2.1 壓縮感知和稀疏表示

壓縮感知(也稱為壓縮感測、壓縮采樣或稀疏采樣)是通過尋找欠定線性系統的解，來有效地獲取和重建信號的信號處理技術。奈奎斯特-香農采樣定理表明：如果信號x(t)不包含高于B赫茲的頻率，那么其可以通過一系列間隔1/2B的點處的值來完全確定。過去幾十年中該定理一直被應用于數字信號處理。然而壓縮感知定理指出信號帶寬不是采樣的基本要求，信號采樣率僅取決于采樣系統的稀疏性和非相干性，該理論可以同時實現信號的壓縮和采樣，在學術界和工業界得到了廣泛的應用。

壓縮感知的核心問題是稀疏字典和測量矩陣的設計，以及信號重構算法的構造，其中信號重構算法的構造也被稱為稀疏表示。

觀測數據y是長度為M的列向量，即y∈RM×1，采樣信號A∈RM×N(M?N)為一組基向量。壓縮感知的目標是使用線性聯立方程y=Ax從觀測數據y中恢復被測信號x。由于未知數的數量大于方程組的個數使得欠定方程組是病態的，它的解不存在。

如果使被測信號x變得稀疏，可能意味著‖x‖0(x的L0范數)盡可能小，那么未知數的數量將會顯著下降，這使得信號重建成為可能。

因此，壓縮感知問題歸結為求解如下約束優化問題：

min‖x‖0s.t.y=Ax

(1)

2005年，Starck等[11]證明式(1)具有唯一解，但是L0范數最小化是非凸優化問題。由于在多項式時間內不能獲得可行解，因此式(1)的求解是個NP難問題。2006年，Tsaig等[12]證明L1范數最小化可以基于RIP條件替代L0范數最小化[12]。盡管兩種形式都具有相同的稀疏解，但壓縮感知的框架變為凸優化問題，其優化目標如下：

min‖x‖1s.t.y=Ax

(2)

使用它，形成了壓縮感知最初的框架。實際上，當考慮到噪聲問題時我們通常使用式(3)而不是式(2)。

min‖x‖1s.t. ‖Ax-y‖2≤ε

(3)

式中：ε表示大于0的很小的數;A表示稀疏字典;x為稀疏解。

重建算法的目的是找到解x，其中整個問題的核心是y的稀疏表示。

2.2 KSOS

稀疏字典的構造包括人工構造和訓練學習。前者包含各向同性Gabor字典、各向異性精化-高斯字典等；后者包含字典學習算法K-SVD。本文直接采用訓練樣本構造稀疏字典。

首先將所有少數類Smin從訓練集S中分離出來。其中Smin∈Rm×n，m為少數類樣本數目，n為少數類樣本的維度。對于當前采樣點xi，xi∈Smin，使用除xi之外的其余少數類樣本來構造系數字典D，D∈Rn×(m-1)。

接著，按照式(4)對每個樣本進行標準化并計算它們的L2范數。

i=1,2,…,m-1j=1,2,…,n

(4)

式中：yi,j是稀疏字典D的樣本點。在得到稀疏D之后，可以通過求解L1最小化問題來求解少數類樣本的稀疏解w。

優化目標如下：

(5)

s.t. ‖Dw-x‖2≤ε

通過使用同倫算法[9]來求解方程的解。為了降低噪聲，同倫算法考慮以下基本問題：

(6)

式中：λ是拉格朗日乘子。

在獲得稀疏解后，選擇w中非零項標識的樣本點與xi一起合成新樣本。例如，得到xi的非零稀疏解的下標，并將其索引保存在A中。然后選擇A中所有的元素，它代表數據點yk的下標，其中k代表A中元素個數。通過式(7)合成一個新樣本。

(7)

式中：

δ∈[0,1]

δ1∈[0,1-δ]

δ2∈[0,1-δ-δ1]

?

δk∈[0,1-δ-δ1-…-δk-1]

M為特征數,n為樣本維度。

在樣本確認階段，KNN模型中定義了一個樣本的置信度，這表明樣本最近鄰的分布。樣本的置信度定義如下：

(8)

式中：T是合成少數類樣本最近鄰的總數；M是K近鄰中屬于少數樣本的數目。例如，如果一個樣本的5個最近鄰中的4個屬于少數類，那么該樣本的置信度為3.2。然后將所有新生成樣本按置信度從大到小排序并從中選取樣本。

算法1KSOS算法

輸入：訓練集S={(xi,zi),i=1,2,…,N,zi∈{0,1}}；多數類樣本N-,少數類樣本N+,其中,N++N-=N；采樣率SR%。

輸出：過采樣后的訓練集S′={(xi,zi),i=1,2,…,N+N+×SR,zi∈{0,1}}。

1.從訓練集S中取出全部多數類樣本與少數類樣本，組成多數類訓練樣本集及少數類訓練樣本集S+

2.置新生成樣本集Snew為空

3.fori=1:N+

4.用除xi外的所有少數類訓練樣本構建稀疏字典D,其中xi∈S+

5.用同倫算法解決式(5)所示的L1優化問題得出非零稀疏解所對應D中的少數類樣本點，并將其置于稀疏解對應樣本集Snew中

6.fori=(SR/100)×2

7.在稀疏解對應樣本集Snew中取出對應的少數類樣本點yj,j=1,2,…,k,其中k為xi對應非零稀疏解的個數

9.添加xnew;k至Snew,Snew=Snew∪xnew

10.置Sner為空

11. end for

12.end for

13.計算每個新生成樣本的置信度，并將其從大到小排列，從中選取前N+×(SR/100)個置于Snew中

14.得到過采樣后的訓練集S′=S∪Snew

為對比KSOS算法與SMOTE和ADASYN的采樣效果，在一個合成數據集上進行實驗。為了方便可視化，該合成數據集的維度為2，其中少數類樣本20個，多數類樣本200個。少數類樣本以(2.5，2.5)為中心，分別以0.1和0.4作為第一維和第二維數據的標準差生成的高斯隨機變量，多數類樣本以(0.3，0.3)為中心，分別以0.2和0.2作為第一維和第二維數據的標準差生成的高斯隨機變量。圖1為在合成數據集上三種采樣算法的采樣結果。可以看出，ADASYN和SMOTE都一定程度上在位于多數類樣本區域的少數類樣本附近生成了新樣本，造成噪聲信息的傳播。而KSOS利用少數類樣本的全局信息進行樣本生成，新生成的樣本多位于少數類樣本及其邊緣，不僅能改善噪聲信息的傳播問題，也增強了少數類樣本的決策邊界。

圖1 三種采樣算法的效果對比圖

3 實 驗

3.1 數據集描述

為了測試本文提出方法的分類性能，實驗采用4組KEEL1(表1前4組)和2組HDDT2(表1后2組)類別不平衡數據集。這些數據集的不平衡比率范圍從9.29到28.1。表1列出了數據集的基本信息，每個數據集有6個屬性，即數據集的名稱、數據集的特征維度、數據集的大小、少數類和多數類樣數以及不平衡率。本文僅考慮含兩個類別的數據集，因此需要對含有多類屬性的數據集進行轉換，以得到二分類標簽。根據文獻[10]中的方法來修改數據標簽，即選取其中某一類作為少數類，并將其余所有的類合并為多數類。

表1 不平衡數據集的基本信息

3.2 評價指標

F-Measure：用于分類器查準率和召回率的性能度量，計算公式如下：

(9)

式中：precision表示查準率；recall表示召回率。

G-Mean：用于度量分類器在兩類數據上的平均性能，計算公式如下：

(10)

式中：TP是實際為少數類且預測正確的樣本個數；TN是實際為多數類且預測正確的樣本數量；FN是實際為少數類且預測錯誤的樣本數量；FP是實際為多數類且預測錯誤的樣本數量。

AUC：用于衡量分類器性能的指標，計算公式如下：

(11)

式中：M和N分別表示數據集中少數類樣本個數和多數類樣本個數。

3.3 結果分析

在實驗中使用C4.5決策樹作為基礎學習模型。為了考察本文算法的分類性能，將其與SMOTE和ADASYN過采樣算法進行對比，作為參考，給出基于原始的不平衡數據集的C4.5決策樹的學習性能。為保證對比算法的性能，其K近鄰的參數設置與原文保持一致，即SMOTE和ADASYN的K近鄰參數設置為5，本文算法在樣本確認階段的K近鄰參數設置為3。對于每一個數據集，均采用5折交叉驗證，每次選取其中4組作為訓練集，1組作為測試集，且每組數據中多數類與少數類樣本個數的比值，為原始數據集中多數類與少數類樣本數量的不平衡比率。采用G-Mean、F-Measure和AUC作為評估指標，為盡量保證實驗結果不受隨機因素的干擾與影響，實驗結果取100次5折交叉驗證的均值，并將每個評價指標下的最大值與本文算法的獲勝次數用粗體標出，如表2、表3所示。

表2 以C4.5決策樹為分類器的G-Mean、F-Measure和AUC結果

表3 算法獲勝次數

從各個算法在不同指標下的獲勝次數可以看出，本文的方法在AUC、G-Mean和F-Measure三種評價指標下的性能都優于其他兩種算法。其中F-Measure值在6個數據集上全都取得了最大值，而只有當查準率和查全率都比較高時，F-Measure值才比較高，說明KSOS算法在不損害多數類數據分類性能的情況下，對少數類樣本的查準率和查全率都有所提升。

4 結 語

為提高傳統分類器在不平衡數據集上的分類性能，針對大多數過采樣算法僅利用少數類數據的局部信息進行樣本少數類生成，使得新生成的少數類樣本不能很好地遵循原始少數類樣本的分布，具有較少的信息量等問題，提出一種基于稀疏表示不平衡數據的過采樣算法。首先利用少數類樣本分布的全局信息進行樣本合成，其次在樣本確認階段對合成的樣本進行清洗，剔除位于多數類樣本范圍內的合成樣本，防止噪聲信息的傳播。通過在6個不平衡數據集上與其他算法的性能比較，表明本文算法可以有效解決數據失衡問題，提高不平衡數據集的分類性能。