基于稀疏表示的不平衡數(shù)據(jù)集過(guò)采樣算法

訾壯壯 何 濤 趙 停

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

0 引 言

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

有兩種方法可以用于解決類(lèi)不平衡問(wèn)題，它們分別是數(shù)據(jù)層面的解決方案和算法層面的解決方案。數(shù)據(jù)層面的解決方案是通過(guò)欠采樣和過(guò)采樣或二者的組合來(lái)平衡少數(shù)類(lèi)樣本和多數(shù)類(lèi)樣本的分布。算法層面的解決方案是通過(guò)改進(jìn)傳統(tǒng)的分類(lèi)算法或優(yōu)化學(xué)習(xí)算法的性能來(lái)提高少數(shù)類(lèi)樣本的識(shí)別率[2]。數(shù)據(jù)層面解決方案由于其獨(dú)立于分類(lèi)算法，可與任何傳統(tǒng)的分類(lèi)算法相結(jié)合而更受歡迎。

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

本文提出一種基于稀疏表示的不平衡數(shù)據(jù)集過(guò)采樣算法KSOS。在樣本生成階段，使用少數(shù)類(lèi)樣本來(lái)構(gòu)造稀疏字典，通過(guò)求解L1范數(shù)最小化來(lái)獲得當(dāng)前點(diǎn)的稀疏解，然后使用稀疏解中的非零項(xiàng)所對(duì)應(yīng)的少數(shù)類(lèi)樣本來(lái)生成新樣本。在樣本確認(rèn)階段,計(jì)算每一個(gè)新生成樣本的置信度，然后將所有新生成樣本按其置信度排序，從中選取符合要求的新生成樣本。

1 相關(guān)工作

不平衡主要有三種：類(lèi)間不平衡、類(lèi)內(nèi)不平衡和類(lèi)重疊。幾乎所有的過(guò)采樣方法都可以通過(guò)重復(fù)原始少數(shù)類(lèi)樣本或生成新的少數(shù)類(lèi)樣本來(lái)解決類(lèi)間不平衡問(wèn)題。對(duì)于類(lèi)內(nèi)不平衡問(wèn)題，常見(jiàn)方法是首先使用聚類(lèi)技術(shù)來(lái)發(fā)現(xiàn)少數(shù)類(lèi)子群，然后應(yīng)用過(guò)采樣方法來(lái)處理這些子群，或者在用其局部分布衡量學(xué)習(xí)難度后，對(duì)難以學(xué)習(xí)的少數(shù)群體樣本進(jìn)行加權(quán)。而當(dāng)原始非重疊區(qū)域被噪聲和錯(cuò)誤的生成樣本入侵時(shí)，就會(huì)出現(xiàn)類(lèi)重疊問(wèn)題。

隨機(jī)過(guò)采樣通過(guò)簡(jiǎn)單重復(fù)部分少數(shù)類(lèi)樣本的方式來(lái)達(dá)成少數(shù)類(lèi)和多數(shù)類(lèi)樣本在訓(xùn)練規(guī)模上的平衡。然而隨機(jī)過(guò)采樣技術(shù)可能導(dǎo)致過(guò)擬合問(wèn)題，因?yàn)樗赡軇?chuàng)建比原始數(shù)據(jù)集更小且更具特異性的決策區(qū)域。

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

自適應(yīng)技術(shù)也被廣泛用于不平衡數(shù)據(jù)集過(guò)采樣。自適應(yīng)合成采樣ADASYN[7]考慮到難以學(xué)習(xí)的少數(shù)類(lèi)樣本，并根據(jù)其局部分布自動(dòng)合成少數(shù)類(lèi)樣本。自適應(yīng)半無(wú)監(jiān)督加權(quán)過(guò)采樣A-SUWO[8]，應(yīng)用半無(wú)監(jiān)督分層聚類(lèi)方法對(duì)少數(shù)類(lèi)樣本進(jìn)行聚類(lèi)，并根據(jù)其特定大小自適應(yīng)地對(duì)每個(gè)子聚類(lèi)進(jìn)行過(guò)采樣。

2 算法設(shè)計(jì)

2.1 壓縮感知和稀疏表示

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

壓縮感知的核心問(wèn)題是稀疏字典和測(cè)量矩陣的設(shè)計(jì)，以及信號(hào)重構(gòu)算法的構(gòu)造，其中信號(hào)重構(gòu)算法的構(gòu)造也被稱(chēng)為稀疏表示。

觀測(cè)數(shù)據(jù)y是長(zhǎng)度為M的列向量，即y∈RM×1，采樣信號(hào)A∈RM×N(M?N)為一組基向量。壓縮感知的目標(biāo)是使用線(xiàn)性聯(lián)立方程y=Ax從觀測(cè)數(shù)據(jù)y中恢復(fù)被測(cè)信號(hào)x。由于未知數(shù)的數(shù)量大于方程組的個(gè)數(shù)使得欠定方程組是病態(tài)的，它的解不存在。

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

因此，壓縮感知問(wèn)題歸結(jié)為求解如下約束優(yōu)化問(wèn)題：

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

(1)

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

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

(2)

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

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

(3)

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

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

2.2 KSOS

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

首先將所有少數(shù)類(lèi)Smin從訓(xùn)練集S中分離出來(lái)。其中Smin∈Rm×n，m為少數(shù)類(lèi)樣本數(shù)目，n為少數(shù)類(lèi)樣本的維度。對(duì)于當(dāng)前采樣點(diǎn)xi，xi∈Smin，使用除xi之外的其余少數(shù)類(lèi)樣本來(lái)構(gòu)造系數(shù)字典D，D∈Rn×(m-1)。

接著，按照式(4)對(duì)每個(gè)樣本進(jìn)行標(biāo)準(zhǔn)化并計(jì)算它們的L2范數(shù)。

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

(4)

式中：yi,j是稀疏字典D的樣本點(diǎn)。在得到稀疏D之后，可以通過(guò)求解L1最小化問(wèn)題來(lái)求解少數(shù)類(lèi)樣本的稀疏解w。

優(yōu)化目標(biāo)如下：

(5)

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

通過(guò)使用同倫算法[9]來(lái)求解方程的解。為了降低噪聲，同倫算法考慮以下基本問(wèn)題：

(6)

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

在獲得稀疏解后，選擇w中非零項(xiàng)標(biāo)識(shí)的樣本點(diǎn)與xi一起合成新樣本。例如，得到xi的非零稀疏解的下標(biāo)，并將其索引保存在A中。然后選擇A中所有的元素，它代表數(shù)據(jù)點(diǎn)yk的下標(biāo)，其中k代表A中元素個(gè)數(shù)。通過(guò)式(7)合成一個(gè)新樣本。

(7)

式中：

δ∈[0,1]

δ1∈[0,1-δ]

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

?

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

M為特征數(shù),n為樣本維度。

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

(8)

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

算法1KSOS算法

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

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

1.從訓(xùn)練集S中取出全部多數(shù)類(lèi)樣本與少數(shù)類(lèi)樣本，組成多數(shù)類(lèi)訓(xùn)練樣本集及少數(shù)類(lèi)訓(xùn)練樣本集S+

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

3.fori=1:N+

4.用除xi外的所有少數(shù)類(lèi)訓(xùn)練樣本構(gòu)建稀疏字典D,其中xi∈S+

5.用同倫算法解決式(5)所示的L1優(yōu)化問(wèn)題得出非零稀疏解所對(duì)應(yīng)D中的少數(shù)類(lèi)樣本點(diǎn)，并將其置于稀疏解對(duì)應(yīng)樣本集Snew中

6.fori=(SR/100)×2

7.在稀疏解對(duì)應(yīng)樣本集Snew中取出對(duì)應(yīng)的少數(shù)類(lèi)樣本點(diǎn)yj,j=1,2,…,k,其中k為xi對(duì)應(yīng)非零稀疏解的個(gè)數(shù)

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

10.置Sner為空

11. end for

12.end for

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

14.得到過(guò)采樣后的訓(xùn)練集S′=S∪Snew

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

圖1 三種采樣算法的效果對(duì)比圖

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

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

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

表1 不平衡數(shù)據(jù)集的基本信息

3.2 評(píng)價(jià)指標(biāo)

F-Measure：用于分類(lèi)器查準(zhǔn)率和召回率的性能度量，計(jì)算公式如下：

(9)

式中：precision表示查準(zhǔn)率；recall表示召回率。

G-Mean：用于度量分類(lèi)器在兩類(lèi)數(shù)據(jù)上的平均性能，計(jì)算公式如下：

(10)

式中：TP是實(shí)際為少數(shù)類(lèi)且預(yù)測(cè)正確的樣本個(gè)數(shù)；TN是實(shí)際為多數(shù)類(lèi)且預(yù)測(cè)正確的樣本數(shù)量；FN是實(shí)際為少數(shù)類(lèi)且預(yù)測(cè)錯(cuò)誤的樣本數(shù)量；FP是實(shí)際為多數(shù)類(lèi)且預(yù)測(cè)錯(cuò)誤的樣本數(shù)量。

AUC：用于衡量分類(lèi)器性能的指標(biāo)，計(jì)算公式如下：

(11)

式中：M和N分別表示數(shù)據(jù)集中少數(shù)類(lèi)樣本個(gè)數(shù)和多數(shù)類(lèi)樣本個(gè)數(shù)。

3.3 結(jié)果分析

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

表2 以C4.5決策樹(shù)為分類(lèi)器的G-Mean、F-Measure和AUC結(jié)果

表3 算法獲勝次數(shù)

從各個(gè)算法在不同指標(biāo)下的獲勝次數(shù)可以看出，本文的方法在AUC、G-Mean和F-Measure三種評(píng)價(jià)指標(biāo)下的性能都優(yōu)于其他兩種算法。其中F-Measure值在6個(gè)數(shù)據(jù)集上全都取得了最大值，而只有當(dāng)查準(zhǔn)率和查全率都比較高時(shí)，F(xiàn)-Measure值才比較高，說(shuō)明KSOS算法在不損害多數(shù)類(lèi)數(shù)據(jù)分類(lèi)性能的情況下，對(duì)少數(shù)類(lèi)樣本的查準(zhǔn)率和查全率都有所提升。

4 結(jié) 語(yǔ)

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