基于集成算法的SVM訓練數據選擇

魏灑灑，楊有龍，趙偉衛

（西安電子科技大學 數學與統計學院，西安 710126）

0 引言

支持向量機（SVM）是由Vapnic等在1995年提出的，主要致力于小樣本的研究[1]。由于它較高的泛化能力和較強的分類性能，近年來已經引起了不同領域研究者的廣泛關注。但是，眾所周知，SVM有一個缺點，就是當訓練數據集非常大的時候，訓練所需的空間及時間復雜度分別為O(n2)和O(n)3[2]，其中n為訓練數據的條數，限制了SVM的使用。因此，降低SVM的訓練的時間及空間復雜度是非常必要的。

為了降低SVM訓練的時間及空間復雜度，不同領域的研究者提出了多種方法，大致可以歸納為以下兩種：第一種方法就是選擇支持向量候選，然后用選出來的數據來訓練SVM；第二種方法是通過將一個大問題分解成多個小問題來加速SVM的訓練過程。雖然第二種方法減小了優化問題的困難，但是它所需的空間復雜度依然是相當大的。本文的方法是屬于第一種的。因為在分類和回歸問題中，決策函數完全是由支持向量決定的。因此，用支持向量和用所有的訓練集作為訓練數據來訓練模型的結果是一樣的。由于支持向量僅占訓練數據集很少的一部分，因此，如果用選出的支持向量作為SVM的訓練數據，那么SVM訓練任務的時間和空間復雜度問題就可以解決。

以相關研究為基礎[3-11]，本文基于RF模型提出一種新型高效的數據選擇方法，隨機分組抽樣集成法（RPSE）。該方法是利用隨機分組抽樣技術來選擇基分類器的訓練數據，然后用訓練出的基分類器創建一個集成，最后根據集成規則來選擇SVM的訓練數據。這種算法與RF算法的主要區別在于，它是用隨機分組抽樣法來選擇基分類器的訓練數據。這種抽樣技術不僅能夠保證選出的基分類器的訓練數據是沒有重復的，而且還能保證抽出的訓練數據的隨機性。

本文提到的數據選擇方法對大數據集來說非常有用，它不僅可以準確地選出支持向量，而且還能夠準確地找出決策邊界附近的數據。通過實驗結果可以看出用RPSE算法來選擇SVM的訓練數據是非常有效的。甚至對某些數據集來說，它的分類精度比用所有訓練集訓練出的SVM模型的分類精度還要高。與RF算法相比，RPSE算法的時間優勢是非常明顯的。并且在分類精度沒有下降的前提下，訓練數據集越大，RPSE算法的時間優勢就越明顯。

1 基礎知識

1.1 支持向量機

線性SVM是尋找具有最大邊緣的超平面，所以它也被稱為最大邊緣分類器。因為決策邊界越小，泛化能力越差。因此，需要設計最大化決策邊界的線性分類器，以確保在最壞的情況下泛化誤差最小。

考慮一個包含N個訓練樣本的二元分類問題。

每個樣本可以表示為一個二元組(xi，yi)(i=1，2，...,N)，其中xi表示第i個樣本的屬性集，為方便記，令yi∈{- 1，1}表示它的類標號。一個線性分類器的決策邊界可以表示為如下形式：

（1）其中w和b是模型的參數。優化的分離超平面可以表示為下面形式：

它是通過解決下面的二次優化問題獲得的:

其中C是用戶指定的參數，表示對誤分訓練實例的懲罰，ξi≥0是松弛變量。由此被約束的優化問題的拉格朗日函數可以記為如下形式：

其中前面兩項是需要最小化的目標函數，λi，μi≥0，根據函數L需要滿足的極值條件，可以得到優化問題的對偶問題：

滿足約束條件是一個函數必須要滿足Mercer條件，則最終的優化決策函數被定義為：

其中xi是要輸入的數據，λi和yi是Lagrangian乘子。其中那些λi＞0的訓練實例位于超平面上，成為支持向量，不在這些超平面上的實例滿足λi=0。所以支持向量僅占訓練集很少的一部分。

1.2 隨機森林

隨機森林（RF）是一類專門為決策樹分類器設計的組合方法。它組合多棵決策樹做出的預測，其中每棵樹都是基于隨機向量的一個獨立集合的值產生的，如圖1所示。與AdaBoost使用的自適應方法不同，Adaboost中的概率分布是變化的，關注的是難分類的樣本，而隨機森林采用的是一個固定的概率分布來產生隨機向量。使用決策樹裝袋是隨機森林的特例，通過隨機地從原始訓練集中選取N個樣本，將隨機性加入到模型的構建過程中。

圖1 隨機分組抽樣過程

已經理論上證明，當樹的數目非常大時，隨機森林的泛化誤差的上界收斂于下面的表達式[13]：

其中是樹之間的平均相關系數，s是度量樹型分類器的“強度”量。

2 提出的方法

RPSE算法的目標是選擇SVM的訓練數據，并在保證SVM分類精度的前提下大大降低SVM訓練的時間和空間復雜度。該算法利用改進的RF算法，在算法運行過程中根據多個基分類器的投票結果來計算集成間隔，然后利用集成間隔來選擇SVM的訓練數據。

2.1 隨機分組抽樣集成法（RPSE）

一般用來訓練基分類器的抽樣方法是bootstrap抽樣，它是一種根據均勻概率分布從數據集中有放回的抽樣技術。每個自助樣本集都和原數據集一樣大。由于抽樣過程是有放回的，因此一些樣本可能在同一個訓練數據集中出現多次，而其他的一些可能被忽略。當原始訓練集很大時，每一個自助樣本集大約包含63%的原始數據集，剩余部分是這些數據的重復。因為本文的目的是給SVM選擇訓練數據，所以這些自助樣本集對于訓練一個基分類器來說足夠了。但是如果用這些樣本創建一個集成分類器，將會有許多重復樣本，從而加大基分類器訓練的時間復雜度。因此，本文提出用隨機分組抽樣方法來選擇基分類器的訓練數據。不僅能夠移除重復樣本，降低每一個基分類器訓練的時間復雜度，而且保證每一個基分類器的訓練數據集的隨機性。由于當訓練集比例大于50%時才能使分類錯誤率達到相對平穩。因此，本文選擇66%的訓練集以確保基分類能獲得一個相對平穩的結果。

根據上述分析，如圖1所示，隨機分組抽樣的大致過程為：

（1）隨機地將訓練集分成個互不相交的子集

N1，N2....，每個子集中訓練樣本的數目相等，均為3個；如果N不能被3整除，將剩余的數據集劃分到子集中。

（2）從每個子集Ni，i=1，2，...，中選出2個訓練數據。

（3）將選出的訓練集組合到一起組成一個新的數據集Dj，j=1，2，...，X。

（4）用Dj來訓練基分類器，分類和回歸樹（CART）。

（5）重復以上步驟X次創建一個集成分類器，N是初始訓練樣本的數量，X是基分類器的數量。

下面用Guo等[12]提出的集成規則：

來選擇支持向量機的訓練數據。其中c1是數據xi得票最多的類，vc1是c1類得的票數，c2是得票次多的類，vc2是c2類得的票數。將等式（8）的結果按降序排列，選出前M個作為SVM的訓練數據，其中M為選出的訓練數據的條數。這個規則不僅簡單，還能正確的選出決策邊界附近的樣本。

Guo等[12]提出對于獲得一個相對穩定的SVM分類結果來說基分類器的數量X=100和訓練數據的抽樣比63%已經足夠了，可以選擇更小的抽樣比和X，因此提出了一種新的訓練數據選擇方法SVIS。這種方法雖然高效，但是從SVM訓練的時間復雜度和分類損失度來看，它用51.01%的訓練集損失了0.7%的分類精度。

2.2 參數選擇

在整個數據選擇算法中僅有一個參數需要調整，那就是根據等式（8）選出來的支持向量候選的數目M，它直接影響了SVM的訓練速度和分類精度。因此本文用一個例子來解釋怎樣選擇參數M。

從圖2中可以看出，隨著訓練數據的增大，SVM的分類精度也在提高。訓練比例為5%時是一個拐點。當從5%開始增加訓練比例時，雖然分類精度仍在提高，但趨勢明顯放緩。這說明，當訓練樣本達到一定的比例后，繼續增加訓練樣本對改善分類錯誤率的幫助不大。因此本文選擇M是根據圖3中的第一個拐點。它在保證SVM分類精度的前提下，大大降低SVM訓練的時間復雜度。

圖2 Globle數據集的分類精度

圖3 選出的SVs占真正的SVs的百分比

2.3 復雜度分析

RPSE算法通過減少基分類器的訓練數據來減少整個SVM數據選擇過程的時間。RF算法選擇支持向量的時間復雜度為O(XNlog(N) )[12]，N為訓練集的條數，X為基分類器的數量。一般來說，當訓練數據非常大時，X＜＜N。而RPSE算法用訓練集的做為基分類器的訓練數據，所以說時間復雜度約為O(XNlog(N) )。整個訓練過程的時間復雜度為O(XNlog(N) )+O()，其中Ns為選出的訓練數據的條數，僅占整個訓練集很少的一部分。這與SVM的時間復雜度相比，是一個很大的優化。并且該算法與RF算法相比，在數據選擇的過程中，時間優勢也非常明顯。

SVM在訓練階段的空間復雜度為O(N2)。RPSE算法僅需要存儲一個N*X矩陣，因此空間復雜度為O(N*X)。由于X＜＜N，故空間復雜度為O(N)。該算法在SVM訓練階段的空間復雜度是依賴于Ns的，所以說整個訓練過程的空間復雜度為O(N)+O()，又由于Ns＜N，遠遠小于用所有訓練集訓練SVM的空間復雜度。

3 實驗分析

3.1 實驗設計

實驗數據如表1所示，本文采用9個不同容量的UCI數據集和一個人工合成的數據集Globle來報告實驗結果。將RF算法和SVIS算法與本文提出的RPSE算法進行性能對比。在算法運行時間上本文又加入了比較成功的K近鄰方法NPPS[9]和統計方法BEPS[11]。基分類器CART的數量設為100。整個實驗過程采用十折交叉驗證法。

表1 實驗數據集

3.2 分類結果

圖3展示的是用RF和RPSE算法選出來的支持向量占全部支持向量的百分比。兩種算法選出的SVs數目差不多，都是用35%的訓練集選出了大約90%的支持向量。因為RPSE算法的數據選擇速度較快，所以從總體來看，RPSE算法取得了相對較好的結果。

圖4 Globle數據集的分類損失度

圖4展示的是隨著訓練數據的增長，數據集Globle的分類損失度的變化情況。和圖3一樣，也是RF和RPSE兩種算法對比的結果。與RF算法相比，本文的數據選擇方法獲得了較好的分類結果，同時在不降低SVM分類精度的前提下減少SVM的訓練時間。對數據集Balance來說，僅用50%的訓練集就得到了與SVM（用所有訓練集訓練得到的）相同的分類結果。

由表2的實驗結果可以看出，與另外兩種數據選擇方法對比：（1）在分類精度上，10條數據集中有6條RPSE算法取得了較好的分類結果；（2）在訓練數據選擇上,RPSE算法有7條數據選出的訓練數據集是最少的。因此，無論是在數據選擇還是在SVM的分類精度上，RPSE算法都取得了較好的結果。從這10條數據集總體的運行結果來看，與SVM相比，RPSE算法僅用43.9%的訓練集損失了約0.47%的分類精度。

表2 四種算法實驗結果表

3.3 時間復雜度分析

在相同的實驗環境下，運行四種數據選擇算法所需的最大最小時間如表3所示。其中最小最大時間分別是表1中的Iris數據集和shuttle數據集。運行速度最快的是RPSE算法。在Iris數據集上，RPSE算法僅比NPPS方法少了1s，但是在shuttle數據集上，RPSE算法比NPPS算法少了將近1700s，時間優勢非常明顯。所以說，訓練數據集越大，本文的算法的時間優勢就越明顯。

表3 四種算法的運行時間

4 結束語

提出了一種新的SVM訓練數據選擇算法，該算法在維持SVM分類精度的前提下降低了SVM的訓練的復雜度。并且訓練集的條數越多，時間優勢就越明顯。該算法用隨機分組抽樣法來訓練基分類器，保證了每個基分類器訓練樣本集中沒有重復數據，從而降低了SVM訓練數據選擇的時間復雜度。并且該算法在維持支持SVM分類精度的前提下，大大降低了其訓練的時間復雜度。

實驗用9個真實的數據集和一個人工合成的數據集驗證了RPSE算法無論是在選擇支持向量所需的時間上還是在SVM訓練的時間復雜度都表現出了較好的性能。

參考文獻：

[1] Vapnic V.The Nature of Statistical Learning Theory[J].Springer,1995.

[2] Guo L,Margin Framework for Ensemble Classifiers)[J].Application to Remote Sensing Data(Ph.D.thesis)University of Bordeaux,France,2011.

[3] Cervantes J,Lamont F,Mazahua L,et al,Data Selection Based on De?cision Tree for SVM Classification on Large Data Sets[J].Applied Soft Computing 2015,(37).

[4] Li X,Yu W.Data Selection Using Decision Tree for SVM Classifica?tion[J].International Conference on Tools With Artificial Intelli?gence,2013,1(4).

[5] Nghi D,Mai L.Training Data Selection for Support Vector Machines Model[C].International Conference on Information and Electronics Engineering 2011.

[6] Shilton A.Incremental Training of Support Vector Machines[J].Neu?ral Networks,IEEE Transactions on,2005,(16).

[7] Wang J,Neskovic P,Cooper L N.Selecting Data for Fast Support Vec?tor Machines Training[J].Springer，2007.

[8] Guo G,Zhang J S.Reducing Examples to Accelerate Support Vector Regression[J].Pattern Recogn.Lett,2007,(28).

[9] Shin H,et al,Neighborhood Property-Based Pattern Selection for Sup?port Vector Machines[J].Neural Comput,2007,(19).

[10] Wang J,Neskovic P,Cooper L.Selecting Data for Fast Support Vec?tor Machines Training[J].Springer,2007,(35).

[11] Li Y,Maguire L.Selecting Critical Patterns Based on Local Geomet?rical and Statistical Information[J].IEEE Trans.Pattern Anal，2011，33(6).

[12] Guo L,Boukir S.Fast Data Selection for SVM Training Using Ensem?ble Margin[J].Pattern Recognition Letters,2015,(51).

[13] Tan P N,Seinbach M,Kumar V.數據挖掘導論[M].北京：人民郵電出版社，2006.