基于特征選擇的SVM選擇性集成學習方法

文/扈曉君 康寧

1 引言

支持向量機（SVM）是一種基于統計學習方法中結構風險最小化以及VC維理論基礎上的機器學習方法[1]。SVM在解決過擬合和小樣本學習分類方面具有良好的性能，SVM的一個主要特點是它可以克服機器學習領域的維數災難問題。

在近些年來的機器學習領域中，集成學習也成為了研究熱點之一。基本原則是使用多個單獨的分類器通過投票的方式來綜合分析判斷。其中的基分類器類型又可以分為兩類：異質類型和同質類型。其中生成同質類型分類器的方法主要有：Bagging(bootstrap aggregating)算法[2]和Boosting算法[3]。Bagging是一種可以并行執行的方法，其產生的訓練子集通過有放回的數據抽樣產生，最后將由訓練數據產生的各個基分類器進行集成組合。而Boosting方法構成最終分類器的方式，則是給各個分類器賦予不同的權重來集合完成。

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

2 基于特征選取的選擇性集成學習

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

2.1 SVM及選擇性集成

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

SVM的決策函數：

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

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

集成學習一般是應用多個基分類器，對其結合加權或簡單投票的方式來分類。多項研究表明，集成學習框架同泛化能力不穩定的分類器進行結合會有比較好的作用。而對于選擇性集成來說，有訓練集T，驗證集V，分類器h，其基本工作原理有：首先，初始化分類器集合S為空集，定義最終得到的分類器數量n；其次，通過迭代計算在T上得到子集ST，并使用ST分別獲得hi，并將其放入S中；最后，在V上對S中的hi進行評估，按照一定的評估準則構成新的集合S*集成分類器。

2.2 特征以及數據集的選取

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

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

2.3 子分類器的選擇

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

在分類器集合C中，通過驗證集V對q個分類器進行測試，|V|代表驗證集的樣本數量，分類器ht的錯誤率：

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

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

在二分類問題中，可以設置基分類器的數目為奇數個，以避免出現投票數一樣多的問題。

2.4 執行步驟

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

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

步驟2.迭代次數t=1…T，然后進行以下循環：

步驟2.1.為產生數據集Rt，在R上使用bootstrap算法進行抽樣選取；

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

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

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

步驟4.通過V對E中的各個基分類器進行泛化評估，并對評估的分類器從大到小排序；

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

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

3 實驗及分析

3.1 實驗數據

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

3.2 實驗結果及分析

表1

表2

實驗所使用的是4個UCI數據集，實驗前已對其中的缺失數據和無效數據予以剔除，并使用一般的Bagging算法作為參照，對比后的準確率如表2所示。

實驗迭代次數均設為1000，本文算法與傳統的Bagging算法相比較在4個數據集的結果上均有所提升，獲得了相對于傳統的Bagging算法較好的泛化性能和效果。

4 結語

本文將SVM和集成學習框架進行結合，其中通過對訓練數據的子集和特征集進行選取使基分類器的泛化能力和結果產生較大的差異和不通，間接的將SVM分類器從穩定變為不穩定的狀態，以便于更加適合當前的集成學習理論。通過在數據集上比較，本SVM集成分類效果要好于傳統的Bagging集成算法。由于SVM可以通過調整不同的核參數來得到不同泛化能力的分類器，因而對于文中的算法還可以通過調參方式使得基分類器之間產生差異，這也是一個可以進一步研究和學習的方面。