田一明，陳 偉，單新穎

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

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

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

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

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

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

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

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

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

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

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

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

2.1.1 巴氏距離

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

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

2.1.2 樣本選擇算法具體步驟

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

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

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

2.2 基于相對(duì)熵的特征選擇

2.2.1 相對(duì)熵

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

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

上式中的單個(gè)元素：

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

2.2.2 特征的選擇

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

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

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

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

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

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

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

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

3.2 分類實(shí)驗(yàn)

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

3.2.1 樣本選擇結(jié)果

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

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

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

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

3.2.2 特征選擇結(jié)果

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

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

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

3.2.3 本文方法與SVME的性能對(duì)比

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

表1 實(shí)驗(yàn)結(jié)果

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

4 結(jié)語

本文通過對(duì)Adaboost的迭代過程進(jìn)行改進(jìn)，在每次迭代的過程中加入了對(duì)樣本選擇和特征選擇的部分來構(gòu)造SVM集成算法，最后通過加權(quán)投票法對(duì)基分類器進(jìn)行集成，從而得到最終的綜合分類器。采用4種來自UCI的數(shù)據(jù)集對(duì)本文方法進(jìn)行分類試驗(yàn)，結(jié)果表明，本文方法對(duì)不同種類的數(shù)據(jù)集均能實(shí)現(xiàn)有效的樣本選擇和特征選擇，從而能夠去除一部分噪音樣本和冗余特征，選擇可靠樣本進(jì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]付忠良.多標(biāo)簽代價(jià)敏感分類集成學(xué)習(xí)算法[J].自動(dòng)化學(xué)報(bào)，2014（6）：40-42.

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

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

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

[6]楊立.基于均值近鄰的樣本選擇算法[J].微型機(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ù)機(jī)器人，專業(yè)化養(yǎng)老。