劉鵬飛,，何良華

　　(同濟(jì)大學(xué) 電子與信息工程學(xué)院,，上海 201804)

       摘要： 樣本不平衡問(wèn)題已經(jīng)成為機(jī)器學(xué)習(xí)領(lǐng)域的研究熱門(mén)。虛擬樣本生成方法是一種重要的解決樣本不平衡問(wèn)題的方法,，它通過(guò)線性生成少數(shù)類(lèi)樣本來(lái)實(shí)現(xiàn),。在以往的大多數(shù)研究工作中，虛擬樣本的生成是在原始的特征空間中進(jìn)行的,，樣本通常處于線性不可分的狀態(tài),，將會(huì)導(dǎo)致生成的虛擬樣本丟失幾何特性。因此,，文章提出了一種基于核方法的虛擬樣本構(gòu)造方法,，虛擬樣本在線性可分的核空間中生成。

　　關(guān)鍵詞：樣本不平衡,；支持向量機(jī),；虛擬樣本；核方法

　　中圖分類(lèi)號(hào)：TP181文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.03.016

　　引用格式：劉鵬飛,，何良華.基于核方法的虛擬樣本構(gòu)造［J］.微型機(jī)與應(yīng)用,，2017,36（3）：52-54,58.

0引言

　　對(duì)不平衡樣本的學(xué)習(xí)一直是機(jī)器學(xué)習(xí)領(lǐng)域的熱點(diǎn)問(wèn)題,。樣本不平衡問(wèn)題的主要難點(diǎn)在于以往的分類(lèi)算法大多以樣本分布平衡為前提，導(dǎo)致了分類(lèi)結(jié)果往往偏向于多數(shù)類(lèi)樣本［1］,。

　　為解決樣本不平衡條件下的分類(lèi)問(wèn)題,，人們提出了很多應(yīng)對(duì)方法。其中,，構(gòu)造虛擬樣本作為基于數(shù)據(jù)層面的一種策略已經(jīng)成為一種主流的處理方法［2］,。構(gòu)造虛擬樣本方法通過(guò)生成少數(shù)類(lèi)虛擬樣本來(lái)平衡樣本分布，從而減少因樣本分布不平衡帶來(lái)的影響,。CHAWLA N V等人提出了Synthetic Minority Oversampling Technique (SMOTE)［3］,利用相鄰樣本的特征相似性,，通過(guò)對(duì)相鄰少數(shù)類(lèi)樣本進(jìn)行插值構(gòu)造的方法生成虛擬樣本。SMOTE在很多領(lǐng)域表現(xiàn)出了出色的性能,，很多研究者在SMOTE的基礎(chǔ)上提出了改進(jìn),，如HAN H等人提出了BorderlineSMOTE［4］，只選取分界面邊界附近的少數(shù)類(lèi)樣本進(jìn)行SMOTE生成,。HE H等人提出了Adaptive synthetic sampling approach for imbalanced learning(ADASYN)［5］，根據(jù)不同的分布密度對(duì)不同區(qū)域的少數(shù)類(lèi)樣本生成不同數(shù)量的虛擬樣本,。

　　然而,，如SMOTE等以往的工作，對(duì)少數(shù)類(lèi)樣本的構(gòu)造都是在原始的低維空間中進(jìn)行的,。構(gòu)造少數(shù)類(lèi)樣本通常使用線性組合其他的少數(shù)類(lèi)樣本進(jìn)行生成,，而低維空間中的樣本往往處于線性不可分的狀態(tài)，這可能導(dǎo)致新生成的虛擬樣本丟失該類(lèi)的幾何特性,。因此,，在線性可分的空間中對(duì)樣本進(jìn)行線性生成是一種更加適合的選擇，一方面線性可分的條件使得分類(lèi)學(xué)習(xí)更加容易,，另一方面,，線性可分空間保證了新生成的樣本的幾何分布更加契合原始的樣本空間。支持向量機(jī)（Support Vector Machine,，SVM）［6］算法將線性不可分的樣本映射到線性可分的更高維空間中進(jìn)行分類(lèi),。因此，本文結(jié)合SVM,，通過(guò)在高維線性可分空間中構(gòu)造虛擬樣本,，從而提高分類(lèi)器在樣本不平衡條件下的分類(lèi)性能。

1SVM算法

　　本文期望在一個(gè)線性可分的空間中構(gòu)造虛擬樣本,，而現(xiàn)實(shí)生活中大多數(shù)數(shù)據(jù)都是線性不可分的,，因此需要將數(shù)據(jù)從原始空間映射到線性可分空間中。而SVM正是這種算法,，通過(guò)核方法將原始空間中樣本映射到一個(gè)高維空間中,，在這個(gè)高維空間中樣本是線性可分的,。下面將介紹所涉及到的SVM相關(guān)知識(shí)。

　　1.1SVM基本公式

　　當(dāng)樣本處于線性可分的情況時(shí),，SVM的決策公式如下：

　　從式(2)中可以得知,，w僅僅由那些αi>0的項(xiàng)組成。這些αi>0的樣本xi對(duì)應(yīng)到SVM中被稱(chēng)為支持向量(Support Vector),，它們對(duì)SVM分界面的構(gòu)建起到了決定性的作用,。因此對(duì)于樣本不平衡的分析問(wèn)題，更多地關(guān)注于作為支持向量的樣本,。

　　1.2SVM中的核函數(shù)

　　當(dāng)樣本處于線性不可分的情況時(shí),，SVM首先使用核函數(shù)將樣本映射到一個(gè)高維線性可分的空間，然后再利用上述公式進(jìn)行分類(lèi),。

　　核函數(shù)與樣本特征之間的關(guān)系表達(dá)式如下：

　　<zi,zj>F=<φ(xi),φ(xj)>F=K(xi,xj)H(4)

　　其中φ是映射函數(shù),，它將處于原始特征空間H（Hilbert，希爾伯特空間）的樣本映射到高維空間F,，在高維空間中樣本線性可分程度更大,。通過(guò)φ，一個(gè)低維空間中xi被映射到高維空間中的zi=φ(xi),。同時(shí),，在映射之后內(nèi)積的計(jì)算復(fù)雜度并沒(méi)有增加，通過(guò)核函數(shù)的技巧計(jì)算仍然可以在低維空間中進(jìn)行,。

　　將核函數(shù)應(yīng)用到1.1節(jié)中,，SVM的決策函數(shù)將變?yōu)椋?/p>

　　從式(6)中可以得知，求解一個(gè)SVM模型只需輸入樣本兩兩之間的核函數(shù)值,。這些兩兩的核函數(shù)值可以用矩陣的形式來(lái)表示,，并且稱(chēng)之為核矩陣。

2基于核方法的虛擬樣本構(gòu)造

　　核方法有效地將低維空間中的線性不可分的樣本映射到高維空間中,，使得樣本線性可分程度大大增加,。在線性可分的高維空間中構(gòu)建決策面更加簡(jiǎn)單，同時(shí)對(duì)于樣本的線性生成也能保持相關(guān)的幾何特性,，因此本文的虛擬樣本構(gòu)造方法是基于這樣的核空間,。同時(shí)SVM算法作為利用核方法的典型代表，本文選取SVM算法對(duì)樣本進(jìn)行分類(lèi),。

　　2.1虛擬樣本的表示

　　在SVM映射后的核空間（即高維空間）中的樣本通常形式會(huì)比較復(fù)雜,，甚至在常用的高斯核映射后的樣本具體特征都不可知（高斯核將樣本映射至無(wú)窮維度），所以構(gòu)建虛擬樣本不能基于具體的單獨(dú)的樣本,。

　　從1.1節(jié)中的式(6)得知,，求解一個(gè)SVM模型只需關(guān)注樣本兩兩之間的核函數(shù)值。所以對(duì)于高維空間中具體的單獨(dú)樣本過(guò)于復(fù)雜的問(wèn)題,，可以把高維空間中具體的虛擬樣本替換為該虛擬樣本與其他所有樣本的核函數(shù)值,。

　　通過(guò)插入給定兩個(gè)高維空間中樣本的中值來(lái)代表一個(gè)虛擬樣本的生成：

　　z* 表示由已知高維空間中的樣本z1和z2生成的虛擬樣本,，要知道在高維空間中這些樣本都是不可知的，因此本文使用z*與所有其他樣本的核函數(shù)值（也即高維空間中的內(nèi)積）來(lái)表示虛擬樣本：

　　Kz*,x=<z*,φ(x)>(8)

　　2.2虛擬樣本的構(gòu)造

　　2.1節(jié)中已經(jīng)將虛擬樣本的表示轉(zhuǎn)換成了虛擬樣本與其他樣本之間的核函數(shù)值,，因此虛擬樣本的構(gòu)造問(wèn)題也就轉(zhuǎn)換成了如何求解它們的核函數(shù)值,。

　　利用內(nèi)積空間中線性性質(zhì)，可以將式(8)計(jì)算如下：

　　對(duì)于樣本x1與樣本x2插值生成的新樣本z*,，使用其與其他所有樣本的核函數(shù)值來(lái)表示,。假設(shè)原本的輸入訓(xùn)練核矩陣為KM(KernelMartrix),N為訓(xùn)練樣本數(shù)量，KM1表示第一次的核矩陣,，經(jīng)過(guò)插入一個(gè) z*=12φ(x1)+12φ(x2)后,，新的核矩陣KM2為：

　　生成一個(gè)樣本時(shí)，核矩陣從N階矩陣KM1擴(kuò)展到N+1階矩陣KM2,。

　　2.3構(gòu)造源的選取

　　插值生成虛擬樣本所需要的兩個(gè)樣本稱(chēng)為構(gòu)造源,，生成不同的虛擬樣本需要不同的構(gòu)造源，本節(jié)主要討論對(duì)于構(gòu)造源的選取,?！?/p>

　　圖1中為SVM分類(lèi)后不同類(lèi)別的樣本分布示意，圖中有兩類(lèi)樣本,，中間實(shí)線表示SVM分類(lèi)決策面,，實(shí)線兩旁的虛線代表兩類(lèi)樣本的支撐界面。對(duì)于單獨(dú)的一類(lèi)樣本來(lái)說(shuō),，分類(lèi)后的樣本點(diǎn)可以分為三類(lèi)：第一類(lèi)介于支撐界面內(nèi)側(cè)，對(duì)應(yīng)到式(5)中該類(lèi)樣本點(diǎn)的αi=0,，這類(lèi)樣本點(diǎn)對(duì)于SVM分界面的構(gòu)建沒(méi)有任何影響,，甚至對(duì)該類(lèi)樣本進(jìn)行增減后都不會(huì)影響SVM分界面；第二類(lèi)處于支撐界面上,，其0<αi<C,；第三類(lèi)位于支撐界面之外，其αi=C,。

　　對(duì)這三類(lèi)樣本點(diǎn)都進(jìn)行了相應(yīng)的虛擬樣本的構(gòu)造,，得到的結(jié)論為：只有選取αi=C的第三類(lèi)樣本作為構(gòu)造源生成后才會(huì)改變SVM分界面。

3實(shí)驗(yàn)結(jié)果

　　本節(jié)將從兩個(gè)實(shí)驗(yàn)來(lái)驗(yàn)證本文所提出方法的有效性,。實(shí)驗(yàn)將使用本方法后的分類(lèi)結(jié)果與原始的SVM分類(lèi)結(jié)果進(jìn)行對(duì)比,。實(shí)驗(yàn)1使用人造數(shù)據(jù)集作為數(shù)據(jù)，實(shí)驗(yàn)2使用UCI真實(shí)數(shù)據(jù)集,。

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

　　為了驗(yàn)證提出方法的有效性,，實(shí)驗(yàn)將在人造數(shù)據(jù)集上對(duì)比原始SVM分類(lèi)結(jié)果與構(gòu)造虛擬樣本后的分類(lèi)結(jié)果。構(gòu)造虛擬樣本時(shí),，樣本生成數(shù)量為多數(shù)類(lèi)樣本與少數(shù)類(lèi)樣本數(shù)量的差值,，構(gòu)造源選取αi=C的樣本,，同時(shí)，生成方式為隨機(jī)生成,。

　　實(shí)驗(yàn)使用的數(shù)據(jù)集由兩個(gè)高斯分布構(gòu)成,，分別代表兩類(lèi)樣本的分布，以其中一類(lèi)為少數(shù)類(lèi)樣本,，另一類(lèi)為多數(shù)類(lèi)樣本,。不同不平衡率的數(shù)據(jù)集是以少數(shù)類(lèi)為基數(shù)，按照比例增加多數(shù)類(lèi)樣本形成的,。圖2為訓(xùn)練樣本的分布,，圖3為不同不平衡率情況下SVM與本文方法的對(duì)比。圖3橫軸表示不平衡率,，縱軸表示性能指標(biāo),，其中f代表Fvalue指標(biāo)，g代表Gmean指標(biāo),，這兩個(gè)指標(biāo)都能比較好地考量不平衡條件下地分類(lèi)性能,。

　　從圖3中可以看到隨著不平衡率的上升，SVM在Fvalue和Gmean下的性能顯著下降,，而本文的方法在1~8的不平衡率下性能只有輕微下降,，并且高于SVM。

　　3.2UCI數(shù)據(jù)集

　　本節(jié)實(shí)驗(yàn)采用UCI中部分?jǐn)?shù)據(jù)集作為真實(shí)數(shù)據(jù)集,，每個(gè)數(shù)據(jù)集的詳細(xì)信息如表1所示,。Np、Nn分別代表少數(shù)類(lèi)樣本和多數(shù)類(lèi)樣本的數(shù)量,，n代表樣本的特征數(shù),，IR表示數(shù)據(jù)集的不平衡率。

　　實(shí)驗(yàn)結(jié)果見(jiàn)表2和圖4,。表2中列出了SVM與本文方法的Fvalue和Gmean值,，而圖4對(duì)比了它們的性能。從圖4可以看出,，本文方法相比于SVM在Fvalue和Gmean兩個(gè)指標(biāo)下都有明顯的提升,。

4結(jié)論

　　本文提出了一種新的在核空間中構(gòu)造虛擬樣本的方法來(lái)解決樣本不平衡問(wèn)題。在SVM的理論中分析了構(gòu)造

　　虛擬樣本的原理,，同時(shí)在試驗(yàn)中對(duì)所提出的方法的有效性進(jìn)行了驗(yàn)證,。在具有不同不平衡率的人造數(shù)據(jù)集以及現(xiàn)實(shí)生活中的真實(shí)數(shù)據(jù)集中，基于核方法的虛擬樣本構(gòu)造方法的表現(xiàn)均優(yōu)于原始的SVM,。

參考文獻(xiàn)

　?。?］ BORDES A, ERTEKIN S, WESTON J, et al. Fast kernel classifiers with online and active learning［J］. Journal of Machine Learning Research, 2012, 6(6):15791619.

　　［2］ HE H, BAI Y, GARCIA E A, et al. ADASYN: adaptive synthetic sampling approach for imbalanced learning［C］. 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence). IEEE, 2008: 13221328.

　　［3］ CHAWLA N V, BOWYER K W, HALL L O, et al. SMOTE: synthetic minority oversampling technique［J］. Journal of Artificial Intelligence Research, 2011, 16(1):321357.

　?。?］ HAN H, WANG W Y, MAO B H. BorderlineSMOTE: a new oversampling method in imbalanced data sets learning［C］.International Conference on Intelligent Computing, Springer Berlin Heidelberg, 2005: 878887.

　?。?］ HE H, GARCIA E A. Learning from imbalanced data［J］. IEEE Transactions on Knowledge & Data Engineering, 2009, 21(9):12631284.

　　［6］ VAPNIK V. The nature of statistical learning theory［M］. Springer Science & Business Media, 2013.