基于優化Adaboost迭代過程的SVM集成算法

田一明，陳 偉，單新穎

（1.國家康復輔具研究中心（北京市老年功能障礙康復輔助技術重點實驗室，民政部神經功能信息與康復工程重點實驗室），北京1001761；2.河北工業大學 控制科學與工程學院，天津 300130）

基于優化Adaboost迭代過程的SVM集成算法

田一明1,2，陳 偉1，單新穎1

（1.國家康復輔具研究中心（北京市老年功能障礙康復輔助技術重點實驗室，民政部神經功能信息與康復工程重點實驗室），北京1001761；2.河北工業大學 控制科學與工程學院，天津 300130）

為提高Adaboost算法迭代過程中生成基分類器的分類精度以及簡化整個集成學習系統的復雜度，文章提出了一種優化Adaboost迭代過程的SVM集成算法。該算法提出了一種在其迭代過程中加入樣本選擇和特征選擇的集成方法。通過均值近鄰算法對樣本進行選擇，并利用相對熵法進行特征選擇，最后利用優化得到的特征樣本子集對基分類器SVM進行訓練，并用加權投票法融合各個SVM基分類器的決策結果進行最終判決。通過對UCI數據集的仿真結果表明，本算法與支持向量機集成算法相比，能夠在更少的樣本以及特征的基礎上，實現較高的識別正確率。

集成學習；均值近鄰；支持向量機

1 集成學習出現背景

在處理復雜模式識別的問題時，傳統的機器學習方法所得到的識別結果往往不能使人滿意。集成學習是目前應對復雜模式識別問題的一種有效方法。一些國際上的知名學者認為集成學習有著巨大的潛力，它將會是21世紀機器學習最為重要的研究方向[1]。近年來各國學者針對集成學習方法的研究做了大量的工作，但是集成學習也同樣面臨著許多問題，如增加了處理問題的時間以及增大了計算機的存儲開銷，并且由于不能很好地對分類器的性能進行差異性度量，造成集成學習的優勢不明顯等問題。付忠良[2]利用自適應提升的思想設計了一種多標簽代價敏感分類集成學習算法。孫博等[3]對集成學習中基分類器之間的多樣性度量方法從不同角度進行了分析，并展望了多樣性度量進一步的研究方向。韓敏等[4]使用最大相關和最小冗余準則對基分類器進行選擇，這種方法能夠在一定程度上到達各分類器之間的冗余性最小而實現分類器與實際輸出之間的相關性最大，從而實現準確性和差異性的平衡。唐煥玲等[5]提出了一種基于投票信息熵的Adaboost樣本權重維護策略，考慮基分類器之間的差異性對基分類器的信任度的影響。

本文提出一種對Adaboost迭代過程進行改進的支持向量機（Support Vector Machine，SVM）集成算法。本算法在Adaboost迭代過程中加入對樣本的選擇和特征的選擇，去除訓練集中的相似樣本，提高樣本和特征的差異性。通過使用UCI公共數據庫中的數據集對本算法進行驗證，實驗結果表明，本算法能夠去除訓練集中的冗余信息，減少SVM的訓練時間，以少量訓練樣本獲得較高的識別率。

2 優化Adaboost迭代過程的SVM集成算法

2.1 基于均值近鄰的樣本選擇算法

基于均值近鄰的樣本選擇算法[6]首先通過計算待選擇訓練樣本的均值，之后將距離該均值最近的樣本作為選中樣本，通過迭代過程，不斷選擇新的樣本，直到訓練集中的樣本數滿足預定閾值要求。

2.1.1 巴氏距離

樣本之間關系的量化可以通過類似于信息熵的指標作為衡量的標準，同時也可以用巴氏距離來衡量。巴氏距離的定義如下：

式中μ1和μ2分別代表兩個樣本在樣本集中表達水平的均值，σ1和σ2為這兩個樣本在樣本集中表達水平的標準差。巴氏距離可以更全面地考慮樣本之間的關系。

2.1.2 樣本選擇算法具體步驟

（1）初始化。設定所選樣本個數θ，以及選擇閾值τ，初始的樣本均值向量為μ0，初始樣本集為S，初始的待定級為空集G。

（2）計算樣本集中樣本與μ0的巴氏距離Bi，在樣本集中搜索最小距離Bmin，將所對應的第k個樣本記為選中樣本Xs。計算選中樣本與其余樣本的巴氏距離Bki，將Bki與選擇閾值進行比較來決定是否將樣本移動到待定集G。

（3）如果無任何樣本使得Bki＜τ，或者待定集中的樣本為空，則退出，否則重復第二步。

2.2 基于相對熵的特征選擇

2.2.1 相對熵

為了選出更有類別區分度的特征，本文提出一種相對熵特征選擇方法。針對特征t和類別Ci，將特征空間分為屬于類別Ci的和不屬于類別Ci的。此時，特征t相對熵為：

式中，P（Ci）為樣本屬于類別Ci的概率，P（Ci|t）為在出現特征t的前提下樣本屬于類別Ci的條件概率。為樣本不屬于類別的概率，為在出現特征t的前提下樣本不屬于類別Ci的條件概率。

上式中的單個元素：

衡量了特征t對類別Ci和Ci的鑒別信息，其值與類別的相關程度成正比，表明特征對類別的區分能力越好。

2.2.2 特征的選擇

利用相對熵法進行特征選擇，就是對特征計算其RE，然后按照值RE從大到小對特征進行排序，最終特征維數的選擇一般有兩種方法。

（1）指定特征維數M，按照從大到小順序選取前M個特征構成特征空間。

（2）指定一個衰減幅度Ψ，選擇RE值大于RE（t0）×Ψ的前M個特征，其中RE（t0）為排序第一個特征所對應的RE值。

2.3 集成學習系統

本文采用加權多數投票法對每次循環生成的個體SVM分類器進行集成。每一個基分類器對樣本類別作出決策，綜合所有基分類器的投票結果作出對樣本類別的綜合決策，最終票數最多的類別被確定為這個樣本的類別，直到所有樣本的類別被全部預測，所得到的分類結果即為分類器集成的最終分類結果。

3 實驗及分析

3.1 實驗數據

實驗采用UCI數據庫中的數據集Wine和Zoo對本文算法進行了測試，其中這兩種數據集的特征均為數值類型。

3.2 分類實驗

應用本文算法對兩種數據集進行測試，通過樣本選擇性能和識別正確率等指標對所提算法進行分析。

3.2.1 樣本選擇結果

使用均值近鄰對樣本進行選擇，不能完全體現樣本的重要性和差異性。因此，引入樣本重要性指數來定義其在樣本集中的重要性，如公式所示：

式中：Vi是第i個樣本的重要性指數，Z為訓練個體分類器的個數，ui是第i個樣本在Z次迭代中被選擇的次數。樣本的重要性指數越高，對分類就越有效。兩種測試集中樣本的歸一化重要性指數如圖1所示。

從圖1可知，兩種不同的數據集，其中不同樣本的重要程度是不同的。如果這些樣本都用來訓練分類器，這顯然是會影響效率的。本文選擇重要性指數高于0.6的樣本作為樣本子集，用優化過的樣本集對基分類器進行訓練，有利于提高基分類器的分類性能。

圖1 不同特征集下樣本重要性指數

3.2.2 特征選擇結果

依據本文算法測試當對兩種數據集選擇不同的特征時，所對應的平均正確分類率，如圖2所示。

圖2 特征選擇數目與識別率之間關系

從圖2可以看出，并不是特征越多，所得到的分類正確率越高。剛開始，分類正確率曲線隨著特征選數的增加而升高，當達到某一個數量值時，特征選擇數的增加對分類正確率沒的積極的作用不明顯了?？傮w來看，過少的特征不足以起到對樣本充分表達的效果，導致正確分類率不能達到理想的效果，而冗余的特征也會導致分類率變差。因此本文提出的算法不僅能夠降低冗余特征的影響，同時能夠保證有充分的特征對樣本進行表達。

3.2.3 本文方法與SVME的性能對比

通過將本文算法與SVME算法分別對兩個數據集的實驗測試，從平均正確分類率、樣本選擇數與特征選擇數量3個方面比較這兩種算法的性能。實驗結果如表1所示。

表1 實驗結果

從表1可以看出，對于不同的數據集，本文算法選擇的特征數與樣本數都少于SVME算法。對于離散型數據集Zoo，本文方法只用了SVME算法的46%特征數量和29%的樣本數對基分類器進行訓練，正確率也比SVME算法提高了3%。同時本算法對連續型數據集Wine也起到了不錯的效果，能夠在提高連續型數據集識別率的前提下，特征數分別只有SVME算法的83%，樣本選擇數分別只有SVME算法的31%，起到了對樣本集和特征優化的作用。

4 結語

本文通過對Adaboost的迭代過程進行改進，在每次迭代的過程中加入了對樣本選擇和特征選擇的部分來構造SVM集成算法，最后通過加權投票法對基分類器進行集成，從而得到最終的綜合分類器。采用4種來自UCI的數據集對本文方法進行分類試驗，結果表明，本文方法對不同種類的數據集均能實現有效的樣本選擇和特征選擇，從而能夠去除一部分噪音樣本和冗余特征，選擇可靠樣本進行訓練，提高每次迭代過程中訓練出基分類器的性能，本算法訓練出的集成分類器比較傳統方法訓練出的集成分類器具有更好的分類性能。

[1]DIETTERICH T G.Machine learning research：Four curren directions[J].AI Magazine，1997（4）：97-136.

[2]付忠良.多標簽代價敏感分類集成學習算法[J].自動化學報，2014（6）：40-42.

[3]孫博，王建東，陳海燕，等.集成學習中的多樣性度量[J].控制與決策，2014（3）：385-395.

[4]韓敏，呂飛.基于互信息的選擇性集成核極端學習機[J].控制與決策，2015（11）：2089-2092.

[5]唐煥玲，魯明羽，鄔俊.基于投票信息熵的Adaboost改進算法[J].控制與決策，2010（4）：487-492.

[6]楊立.基于均值近鄰的樣本選擇算法[J].微型機與應用，2014（17）：80-82.

SVM integration algorithm based on optimized Adaboost iterative process

Tian Yiming1,2, Chen Wei1, Shan Xinying1
（1. National Rehabilitation Aids Research Center（Key Laboratory of Beijing Elderly Dysfunction Rehabilitation Assistive Technology, Ministry of Civil Affairs Neurological Rehabilitation Engineering Key Laboratory）, Beijing 1001761, China; 2. Control Science and Engineering College of Hebei University of Technology, Tianjin 300130, China）

In order to improve the classi fi cation accuracy of generating base classi fi er in Adaboost algorithm iterative process and simplify the complexity of the whole integrated learning system, this paper puts forward an integrated algorithm of SVM to optimize Adaboost iterative process. An integrated approach of adding sample selection and feature selection is proposed during its iteration process. The mean nearest neighbor algorithm is adopted to select the samples, and relative entropy method is used for feature selection, fi nally the optimized feature sample set is used for training the base classi fi er SVM, the weighted voting method is fi nally decided by fusing the decision results of each SVM based classi fi er. Through the simulation result of UCI data sets, compared with the algorithm integrated with support vector machine algorithm, the algorithm can achieve a high correct recognition rate based on fewer samples as well as features.

ensemble learning; mean nearest neighbor; support vector machines

田一明（1988— ），男，河北唐山，博士研究生；研究方向：康復機器人，專業化養老。