基于集成算法的SVM訓練數(shù)據(jù)選擇

魏灑灑，楊有龍，趙偉衛(wèi)

（西安電子科技大學 數(shù)學與統(tǒng)計學院，西安 710126）

0 引言

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

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

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

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

1 基礎(chǔ)知識

1.1 支持向量機

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

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

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

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

它是通過解決下面的二次優(yōu)化問題獲得的:

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

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

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

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

1.2 隨機森林

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

圖1 隨機分組抽樣過程

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

其中是樹之間的平均相關(guān)系數(shù)，s是度量樹型分類器的“強度”量。

2 提出的方法

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 參數(shù)選擇

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

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

圖2 Globle數(shù)據(jù)集的分類精度

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

2.3 復(fù)雜度分析

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

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

3 實驗分析

3.1 實驗設(shè)計

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

表1 實驗數(shù)據(jù)集

3.2 分類結(jié)果

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

圖4 Globle數(shù)據(jù)集的分類損失度

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

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

表2 四種算法實驗結(jié)果表

3.3 時間復(fù)雜度分析

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

表3 四種算法的運行時間

4 結(jié)束語

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

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

參考文獻：

[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.數(shù)據(jù)挖掘?qū)д揫M].北京：人民郵電出版社，2006.