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

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

0 引言

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

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

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

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

1 基礎(chǔ)知識(shí)

1.1 支持向量機(jī)

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

考慮一個(gè)包含N個(gè)訓(xùn)練樣本的二元分類問(wèn)題。

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

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

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

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

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

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

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

1.2 隨機(jī)森林

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

圖1 隨機(jī)分組抽樣過(guò)程

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

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

2 提出的方法

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

2.1 隨機(jī)分組抽樣集成法（RPSE）

一般用來(lái)訓(xùn)練基分類器的抽樣方法是bootstrap抽樣，它是一種根據(jù)均勻概率分布從數(shù)據(jù)集中有放回的抽樣技術(shù)。每個(gè)自助樣本集都和原數(shù)據(jù)集一樣大。由于抽樣過(guò)程是有放回的，因此一些樣本可能在同一個(gè)訓(xùn)練數(shù)據(jù)集中出現(xiàn)多次，而其他的一些可能被忽略。當(dāng)原始訓(xùn)練集很大時(shí)，每一個(gè)自助樣本集大約包含63%的原始數(shù)據(jù)集，剩余部分是這些數(shù)據(jù)的重復(fù)。因?yàn)楸疚牡哪康氖墙oSVM選擇訓(xùn)練數(shù)據(jù)，所以這些自助樣本集對(duì)于訓(xùn)練一個(gè)基分類器來(lái)說(shuō)足夠了。但是如果用這些樣本創(chuàng)建一個(gè)集成分類器，將會(huì)有許多重復(fù)樣本，從而加大基分類器訓(xùn)練的時(shí)間復(fù)雜度。因此，本文提出用隨機(jī)分組抽樣方法來(lái)選擇基分類器的訓(xùn)練數(shù)據(jù)。不僅能夠移除重復(fù)樣本，降低每一個(gè)基分類器訓(xùn)練的時(shí)間復(fù)雜度，而且保證每一個(gè)基分類器的訓(xùn)練數(shù)據(jù)集的隨機(jī)性。由于當(dāng)訓(xùn)練集比例大于50%時(shí)才能使分類錯(cuò)誤率達(dá)到相對(duì)平穩(wěn)。因此，本文選擇66%的訓(xùn)練集以確?；诸惸塬@得一個(gè)相對(duì)平穩(wěn)的結(jié)果。

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

（1）隨機(jī)地將訓(xùn)練集分成個(gè)互不相交的子集

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

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

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

（4）用Dj來(lái)訓(xùn)練基分類器，分類和回歸樹(shù)（CART）。

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

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

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

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

2.2 參數(shù)選擇

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

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

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

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

2.3 復(fù)雜度分析

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

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

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

實(shí)驗(yàn)數(shù)據(jù)如表1所示，本文采用9個(gè)不同容量的UCI數(shù)據(jù)集和一個(gè)人工合成的數(shù)據(jù)集Globle來(lái)報(bào)告實(shí)驗(yàn)結(jié)果。將RF算法和SVIS算法與本文提出的RPSE算法進(jìn)行性能對(duì)比。在算法運(yùn)行時(shí)間上本文又加入了比較成功的K近鄰方法NPPS[9]和統(tǒng)計(jì)方法BEPS[11]?；诸惼鰿ART的數(shù)量設(shè)為100。整個(gè)實(shí)驗(yàn)過(guò)程采用十折交叉驗(yàn)證法。

表1 實(shí)驗(yàn)數(shù)據(jù)集

3.2 分類結(jié)果

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

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

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

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

表2 四種算法實(shí)驗(yàn)結(jié)果表

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

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

表3 四種算法的運(yùn)行時(shí)間

4 結(jié)束語(yǔ)

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

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

參考文獻(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.