郭亞偉,白治江

　　(上海海事大學 信息工程學院,上海 201306)

　　摘要：針對傳統的SVM算法在非平衡數據分類中分類效果不理想的問題，提出一種基于分類超平面和SMOTE過采樣方法(HB_SMOTE)。該方法首先對原始訓練樣本集使用WSVM算法找到分類超平面，然后按一定標準剔除負類中被錯分的樣本、靠近分類超平面的樣本以及遠離分類超平面的樣本。在UCI數據集上的實驗結果表明：與RU_SMOTE等重采樣方法相比，HB_SMOTE方法對正類樣本和負類樣本都具有較高的分類準確率。

　　關鍵詞：非平衡數據集；SMOTE；分類超平面；SVM；混合重采樣

0引言

　　支持向量機(SVM)［1］因其能夠有效地避免維數災難，實現全局最優，具有嚴謹的理論基礎和良好的泛化能力，現已成為機器學習領域的熱點問題。傳統的SVM方法需要其各類樣本集的規模相同。然而在現實生活中，往往會遇到一些非平衡數據分類問題，如入侵檢測、文本分類、醫療診斷等。使用這些數據對SVM方法進行訓練建模時，分類決策面會向少數類偏移，導致少數類的分類準確率降低。國內外學者針對此類問題進行了深入的研究，提出了許多不同的處理方案。

　　目前，針對非平衡數據下SVM分類問題的研究主要集中在算法層面和數據重采樣兩個方面。算法層面主要是代價敏感性方法。這種方法雖然增加了少數(正)類的分類準確率，但卻犧牲了多數(負)類的分類準確率，總的分類效果也受到了極大的影響［2］。數據重采樣技術主要是過采樣和欠采樣。過采樣主要包括隨機過采樣、SMOTE［2］算法、BorderlineSMOTE［3］技術等。這些過采樣方法雖然可以確保原始分類信息的完整性，但是由于新合成的正類樣本不能準確表達原始樣本集的信息，從而導致過擬合，同時也會增加計算復雜度。欠采樣主要包括隨機欠采樣、基于聚類欠采樣的極端學習機［4］等。單一的欠采樣技術雖然可以降低計算復雜度，但是在刪除樣本時通常會導致負類樣本中部分信息缺失，影響分類準確性。

　　參考文獻［5］表明相較于單一的采樣方法，混合重采樣方法往往能夠得到更好的分類效果。參考文獻［6］表明對于分類來說最重要的數據是位于邊界的樣本，噪聲樣本和距離分類邊界較遠的樣本對數據信息的貢獻不大。據此，本文提出了一種基于混合重采樣和分類超平面的分類方法并在UCI數據集上進行建模訓練，驗證算法的有效性。

1基本的分類方法

　　1.1SMOTE算法

　　SMOTE算法［2］是由CHAWLA N V等人提出的一種過采樣方法。該算法步驟如下。

　?。?)對正類中的每一個樣本x，計算它到該類中其他每個樣本的歐氏距離，獲取其k個最近鄰樣本，并記錄近鄰下標。

　?。?)按照兩類數據集不均衡的比率設置正類的采樣倍率N,對所有正類樣本x，從k個最近鄰中隨機選取xi(i=1，…，N)。

　　（3)對每一個近鄰xi，分別與原始樣本x按照xnew=x+rand(0,1)×(xi－x)合成新樣本。

　　（4)把合成的新樣本與原始訓練樣本集并為新的訓練集，并在該樣本集上學習。

　　1.2SVM與WSVM

　　SVM是在統計學習理論中結構風險最小化原則基礎上提出的機器學習方法［1］。其原理是尋找一個最優分類超平面，使得該超平面在保證分類精度的同時，能夠使超平面兩側的空白區域最大化。此外，它還能通過核函數將低維空間中的線性不可分問題轉化為高維空間中的線性可分問題。設訓練樣本集為(xi,yi),i=1,2,…,l,x∈Rn,y∈{±1}，超平面記作(w·φ(x))+b=0，其中φ(x)為x從輸入空間Rn到特征空間H的變換。將構造最優超平面問題轉化為求解二次凸規劃問題，即：

　　為解決由于樣本集失衡導致的分類決策面偏移問題，引入了基于代價敏感的WSVM，主要思想是對錯分的正類和負類樣本分別賦予不同的懲罰系數C+和C-，約束表達式變為：

2混合重采樣方法

　　2.1RU_SMOTE算法

　　許多學者綜合考慮了過采樣與欠采樣的弊端和優點，提出兩類采樣方法同時使用的混合重采樣方法［5］。RU_SMOTE算法［7］是一種使用隨機欠采樣與SMOTE相結合的混合重采樣方法。算法思想為：先確定合成樣本的比例γ，利用SMOTE算法增加相應比例的正類樣本；然后使用隨機欠采樣刪除負類樣本，使數據達到平衡；通過改變γ調整合成樣本的數量和數據規模；最后使用SVM分類。該算法既能去除負類樣本降低數據規模，又能增添新的樣本信息，緩解由于樣本集失衡而帶來的分類決策面的偏移。

　　2.2HB_SMOTE(Hyperplane Based SMOTE)算法

　　上述混合重采樣方法雖然取得了比單一采樣方法更好的分類效果，但并沒有克服隨機欠采樣的盲目性。對于分類來說位于邊界的樣本為重要樣本［6］，噪聲樣本和距離分類邊界較遠的樣本則是次要樣本，剔除這些樣本不會引起太多的信息損失?；谶@種思想，本文提出了一種改進的混合重采樣算法：首先采用WSVM算法尋找分類邊界，亦即分類超平面；然后按一定標準將被錯分的和靠近分類超平面以及遠離超平面的負類樣本刪除，再對正類利用SMOTE方法進行過采樣使正負類數據達到平衡并且引入新的樣本信息；最后使用SVM建模訓練。

　　算法的具體實現步驟如下。

　?。?）使用WSVM算法對原始數據集進行訓練，尋找分類超平面，即:f(x)=∑li=1α*yiK(Xi,X)+b*=0。

　　（2）確定SMOTE合成新樣本的比率γ。對正類樣本進行相應比率的合成過采樣，組成新的正類樣本集。

　?。?）對步驟（1）訓練集中的每一個負類樣本xi，計算xi到分類邊界f(x)的距離di，并對di進行排序。

　?。?）對于排好序的di，選取n個最大的dj(j=1,2，…，n)和m個最小的dj(j=1,2，…，m)，分別從原訓練集中刪除與dj對應的這些n+m個點。將剩下的負類樣本與步驟（2）中新正類樣本一起作為新的訓練集。

　?。?）對新的訓練集使用SVM算法進行分類。

　　（6）可以選取不同γ、n和m重復步驟（4）以獲取合適的新負類樣本集。其中n和m決定于γ的變化。

3實驗分析

　　3.1評價標準

　　許多傳統的分類學習算法主要采用準確率(正確分類的樣本數目占所有樣本總數目的比率)作為分類學習的評價指標，它所對應的混淆矩陣［8］見表1。真實負類FPTN對于非平衡數據集而言，用準確率來評價分類器的性能是不合理的。因為很多情況下雖然總的分類精度很高，但實際上正類的分類精度卻可能很低。如果正類樣本數占總樣本數的1%，即使正類樣本全部分錯，分類精度還是會達到99%。但這卻是無意義的。因此需要采用新的評價方法。定義如下指標：

　　Acc+=TP/(TP+FN)

　　Acc－=TN/(FP+TN)

　　Precision=TP/(FP+TP)

　　Recall=TP/(TP+FN)

　　本文中，使用G_mean和F_measure作為評價準則:

　　G_mean=Acc+·Acc－

　　F_measure=2×Recall×PrecisionRecall+Precision

　　G_mean性能指標同時兼顧了正負類樣本的分類性能，只有二者的值都大時，G_mean才會大，因此G_mean主要是代表了非平衡數據集的總體的分類性能。性能指標F_measure則綜合考慮正類樣本的查全率和查準率，只有二者的值都大時，F_measure才會大，所以它主要是度量分類器對正類的分類效果。

　　3.2實驗

　　本文所采用的實驗數據都來自于UCI機器學習數據庫，分別為Glass數據集、Vowel數據集和Segment數據集。由于這3個數據集都是多類數據集，為簡化起見，先將數據集都變為二類分類問題。對Glass數據集選取類標為“7”的數據作為正類，將其余的類合并作為負類。而對Vowel和Segment數據集分別選取類標為“hed”和“brickface”的數據作為正類。這3個數據集的詳細描述詳見表2。

　　實驗設計如下：使用MATLAB作為仿真環境并使用LIBSVM工具箱作為實現工具。本文采用10折交叉驗證的方法對數據集進行驗證，在實驗中將本文的HB_SMOTE與SMOTE、隨機欠采樣、RU_SMOTE方法作對比，通過改變SMOTE新樣本的比率得到不同比率下的分類結果，如表3~表6所示。

　　由表3~表5可以看出，SMOTE算法性能優于隨機欠采樣，主要因為隨機欠采樣算法隨機刪除樣本的同時也將有用信息刪除。而RU_SMOTE算法要優于SMOTE算法和隨機欠采樣算法，主要因為作為混合采樣其綜合了SMOTE算法和隨機欠采樣的優點。HB_SMOTE算法的G_mean和Acc－比其他3種算法高，表明其總體效果要優于其他3種算法，這是因為該算法剔除了負類樣本集中的噪聲樣本和無用樣本，從而增加了有效樣本的比率。結合表3~表5可以看出，SMOTE合成新樣本的比率不同，優化結果也不盡相同，通過改變SMOTE合成新樣本的比率可以尋求更優的結果。由表6可以看出HB_SMOTE的值要優于其他3種方法，這表明該分類器在一定程度上能夠提升正類的分類效果。

4結論

　　SVM在解決小樣本、非線性分類問題上具有顯明的優勢，更重要的是其具有良好的泛化能力。但是在現實生活中廣泛存在著非平衡數據分類的問題，傳統的SVM算法對于少數類樣本的識別準確率較低。本文基于SMOTE過采樣技術提出了一種改進的混合重采樣方法(HB_SMOTE)：首先通過WSVM找到分類超平面，據此刪除那些負類樣本集中越界和靠近超平面的樣本以及那些遠離超平面的樣本，從而減少負類樣本集中的噪聲點和無效點。而通過SMOTE算法所合成的正類樣本點則能夠增加少數類樣本集的信息量和密度。在UCI數據集上對比4種算法的實驗結果表明，HB_SMOTE算法性能明顯優于其他3種算法，表明該分類器在相對較少的增加運算規模的基礎上能夠提升少數類的分類精度。

參考文獻

　?。?］ VAPNIK V N.The nature of statistical learning theory［M］.New