基于特征選擇的SVM選擇性集成學(xué)習(xí)方法

文/扈曉君 康寧

1 引言

支持向量機(jī)（SVM）是一種基于統(tǒng)計(jì)學(xué)習(xí)方法中結(jié)構(gòu)風(fēng)險(xiǎn)最小化以及VC維理論基礎(chǔ)上的機(jī)器學(xué)習(xí)方法[1]。SVM在解決過擬合和小樣本學(xué)習(xí)分類方面具有良好的性能，SVM的一個(gè)主要特點(diǎn)是它可以克服機(jī)器學(xué)習(xí)領(lǐng)域的維數(shù)災(zāi)難問題。

在近些年來的機(jī)器學(xué)習(xí)領(lǐng)域中，集成學(xué)習(xí)也成為了研究熱點(diǎn)之一?；驹瓌t是使用多個(gè)單獨(dú)的分類器通過投票的方式來綜合分析判斷。其中的基分類器類型又可以分為兩類：異質(zhì)類型和同質(zhì)類型。其中生成同質(zhì)類型分類器的方法主要有：Bagging(bootstrap aggregating)算法[2]和Boosting算法[3]。Bagging是一種可以并行執(zhí)行的方法，其產(chǎn)生的訓(xùn)練子集通過有放回的數(shù)據(jù)抽樣產(chǎn)生，最后將由訓(xùn)練數(shù)據(jù)產(chǎn)生的各個(gè)基分類器進(jìn)行集成組合。而Boosting方法構(gòu)成最終分類器的方式，則是給各個(gè)分類器賦予不同的權(quán)重來集合完成。

之前為了進(jìn)一步提高SVM的泛化能力，部分研究已將集成學(xué)習(xí)技術(shù)集成到SVM中。然而由于集成學(xué)習(xí)是由多個(gè)基分類器進(jìn)行合成，因而訓(xùn)練速度相比單分類器要慢，而且其中包含的基分類器規(guī)模越大，其計(jì)算復(fù)雜度和運(yùn)行需要的資源也就越多。本文通過從集成學(xué)習(xí)的輸入變量中提取特征子集來處理數(shù)據(jù)，獲得較大差異化的訓(xùn)練子集，根據(jù)預(yù)測(cè)精度對(duì)所獲得的基分類器進(jìn)行選擇組合。既可以讓訓(xùn)練集和基分類器的差異增加，又可以讓基分類器數(shù)量在一定程度上減少。

2 基于特征選取的選擇性集成學(xué)習(xí)

一般的集成學(xué)習(xí)方法比較適合于不穩(wěn)定的分類器，但SVM同其他分類器相比則屬于比較穩(wěn)定的算法。為了產(chǎn)生不穩(wěn)定的差異化結(jié)果，可以通過在輸入數(shù)據(jù)中構(gòu)造特征子集的方式進(jìn)行前期的數(shù)據(jù)處理，之后根據(jù)訓(xùn)練精度，通過排序獲得部分選取的基分類器以形成最終的分類器集合。

2.1 SVM及選擇性集成

支持向量機(jī)（SVM）通過確定分類的最優(yōu)決策邊界來使得類之間的間距最大化。SVM決策超平面可以表示為：

SVM的決策函數(shù)：

以下是引入核函數(shù)后SVM的超平面方程，以此解決非線性問題：

其中ai是為求得帶約束的最優(yōu)化問題而得到的拉格朗日因子。在引入核函數(shù)后，SVM分類模型為：

集成學(xué)習(xí)一般是應(yīng)用多個(gè)基分類器，對(duì)其結(jié)合加權(quán)或簡(jiǎn)單投票的方式來分類。多項(xiàng)研究表明，集成學(xué)習(xí)框架同泛化能力不穩(wěn)定的分類器進(jìn)行結(jié)合會(huì)有比較好的作用。而對(duì)于選擇性集成來說，有訓(xùn)練集T，驗(yàn)證集V，分類器h，其基本工作原理有：首先，初始化分類器集合S為空集，定義最終得到的分類器數(shù)量n；其次，通過迭代計(jì)算在T上得到子集ST，并使用ST分別獲得hi，并將其放入S中；最后，在V上對(duì)S中的hi進(jìn)行評(píng)估，按照一定的評(píng)估準(zhǔn)則構(gòu)成新的集合S*集成分類器。

2.2 特征以及數(shù)據(jù)集的選取

Bagging算法主要通過隨機(jī)有放回抽樣方法形成子數(shù)據(jù)集，然后生成差異化的子訓(xùn)練集。然后將通過這些訓(xùn)練子集獲得的子分類器組合成集成分類器集合。本文也主要采用了此種方式選取數(shù)據(jù)。

在本文中，使用Bagging中的bootstrap方法用于選擇訓(xùn)練數(shù)據(jù)，以便生成的基分類器在泛化能力方面產(chǎn)生較大的差異。同時(shí)，在特征集規(guī)模為F的樣本數(shù)據(jù)集S中，隨機(jī)的選擇規(guī)模為f的子特征集，f

2.3 子分類器的選擇

算法需要通過一定的評(píng)估標(biāo)準(zhǔn)，從之前的基分類器集合C中獲得滿足條件的子分類器形成新的子分類器集合C*。本文將使用基分類器的預(yù)測(cè)精度作為度量和選取標(biāo)準(zhǔn)。其中主要的過程是從集合C中按照基分類器的泛化能力大小來選擇新的基分類器子集。

在分類器集合C中，通過驗(yàn)證集V對(duì)q個(gè)分類器進(jìn)行測(cè)試，|V|代表驗(yàn)證集的樣本數(shù)量，分類器ht的錯(cuò)誤率：

從得到的分類器中依據(jù)各個(gè)分類器錯(cuò)誤率的大小選取符合要求的基分類器進(jìn)行組合。部分研究表明，對(duì)于分類器數(shù)量的選取上，當(dāng)集合C中的分類器較少[4]時(shí)，選取40%左右會(huì)比較理想，而當(dāng)集合中分類器較多[5]時(shí)，選取15%～30%的成員較好。確定所選擇的規(guī)模大小之后，集合C*的成員由C中的分類器按精度排序并等間隔的選取構(gòu)成，之后C*中的多個(gè)基分類器用簡(jiǎn)單投票法對(duì)數(shù)據(jù)進(jìn)行分類。在樣本集X中，h(x)i表示一組子分類器，kj表示第j類的標(biāo)記。每類的得票數(shù)目如下：

該樣本的為得票最多的那一類：

在二分類問題中，可以設(shè)置基分類器的數(shù)目為奇數(shù)個(gè)，以避免出現(xiàn)投票數(shù)一樣多的問題。

2.4 執(zhí)行步驟

有樣本數(shù)據(jù)集合S：{(x1,y1),…(xn,yn)}，xi∈X，yi∈{+1，-1}，i=1,2,3…n，S=R∪V，S劃分為訓(xùn)練集R和驗(yàn)證集V，h是子學(xué)習(xí)器，T為循環(huán)次數(shù)。R用于訓(xùn)練最初的基分類器集合，V用于在初始集中選取符合要求的基分類器。

步驟1.初始基分類器集合E=?；

步驟2.迭代次數(shù)t=1…T，然后進(jìn)行以下循環(huán)：

步驟2.1.為產(chǎn)生數(shù)據(jù)集Rt，在R上使用bootstrap算法進(jìn)行抽樣選??；

步驟2.2.在Rt上得到規(guī)模為M的特征集合F，再隨機(jī)選取規(guī)模為m=|M/2|的特征集合f。Rt在f上投影得到子數(shù)據(jù)集Rt*；

步驟2.3.以Rt*作為訓(xùn)練集獲得分類器ht，并放入集合E中；

步驟3.得到t個(gè)基分類器的集合E；

步驟4.通過V對(duì)E中的各個(gè)基分類器進(jìn)行泛化評(píng)估，并對(duì)評(píng)估的分類器從大到小排序；

步驟5.將錯(cuò)誤率大于0.5的基分類器去除，之后從E中剩余的分類器中選出一定的ht作為最終組合。

以上過程在2個(gè)方面得到了改善：首先，隨機(jī)選取基分類器后再次對(duì)數(shù)據(jù)樣本的特征集進(jìn)行了隨機(jī)選取，以此加大樣本間的差異，進(jìn)一步使得SVM的穩(wěn)定性降低；其次，為了縮小基分類器最終的規(guī)模，在原集合中依據(jù)錯(cuò)誤率再次對(duì)其中的基分類器進(jìn)行了篩選。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)選取了4組來自UCI的數(shù)據(jù)集，并隨機(jī)劃分出各自相應(yīng)的訓(xùn)練集、驗(yàn)證集和測(cè)試集。SVM在遇到多分類問題時(shí)，可以使用一對(duì)一[6]或者一對(duì)多的方式將問題轉(zhuǎn)換為二分類問題。文中為便于處理非線性問題使用了高斯核函數(shù)，設(shè)置其參數(shù)σ為0.2，C為2。同時(shí)用一般的Bagging算法作為對(duì)比項(xiàng)，以往的驗(yàn)證表明其抽取的樣本子集約包含63.2%的原數(shù)據(jù)。試驗(yàn)中的循環(huán)次數(shù)T為1000，基分類器的規(guī)模均設(shè)為291。實(shí)驗(yàn)所用數(shù)據(jù)的相關(guān)信息如表1所示。

3.2 實(shí)驗(yàn)結(jié)果及分析

表1

表2

實(shí)驗(yàn)所使用的是4個(gè)UCI數(shù)據(jù)集，實(shí)驗(yàn)前已對(duì)其中的缺失數(shù)據(jù)和無效數(shù)據(jù)予以剔除，并使用一般的Bagging算法作為參照，對(duì)比后的準(zhǔn)確率如表2所示。

實(shí)驗(yàn)迭代次數(shù)均設(shè)為1000，本文算法與傳統(tǒng)的Bagging算法相比較在4個(gè)數(shù)據(jù)集的結(jié)果上均有所提升，獲得了相對(duì)于傳統(tǒng)的Bagging算法較好的泛化性能和效果。

4 結(jié)語

本文將SVM和集成學(xué)習(xí)框架進(jìn)行結(jié)合，其中通過對(duì)訓(xùn)練數(shù)據(jù)的子集和特征集進(jìn)行選取使基分類器的泛化能力和結(jié)果產(chǎn)生較大的差異和不通，間接的將SVM分類器從穩(wěn)定變?yōu)椴环€(wěn)定的狀態(tài)，以便于更加適合當(dāng)前的集成學(xué)習(xí)理論。通過在數(shù)據(jù)集上比較，本SVM集成分類效果要好于傳統(tǒng)的Bagging集成算法。由于SVM可以通過調(diào)整不同的核參數(shù)來得到不同泛化能力的分類器，因而對(duì)于文中的算法還可以通過調(diào)參方式使得基分類器之間產(chǎn)生差異，這也是一個(gè)可以進(jìn)一步研究和學(xué)習(xí)的方面。