基于優(yōu)化Adaboost迭代過程的SVM集成算法

田一明，陳 偉，單新穎

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

基于優(yōu)化Adaboost迭代過程的SVM集成算法

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

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

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

集成學(xué)習(xí)；均值近鄰；支持向量機

1 集成學(xué)習(xí)出現(xiàn)背景

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

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

2 優(yōu)化Adaboost迭代過程的SVM集成算法

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

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

2.1.1 巴氏距離

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

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

2.1.2 樣本選擇算法具體步驟

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

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

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

2.2 基于相對熵的特征選擇

2.2.1 相對熵

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

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

上式中的單個元素：

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

2.2.2 特征的選擇

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

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

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

2.3 集成學(xué)習(xí)系統(tǒng)

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

3 實驗及分析

3.1 實驗數(shù)據(jù)

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

3.2 分類實驗

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

3.2.1 樣本選擇結(jié)果

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

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

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

圖1 不同特征集下樣本重要性指數(shù)

3.2.2 特征選擇結(jié)果

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

圖2 特征選擇數(shù)目與識別率之間關(guān)系

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

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

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

表1 實驗結(jié)果

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

4 結(jié)語

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

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

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

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

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

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

[6]楊立.基于均值近鄰的樣本選擇算法[J].微型機與應(yīng)用，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— ），男，河北唐山，博士研究生；研究方向：康復(fù)機器人，專業(yè)化養(yǎng)老。