一種基于樣本近鄰分類精度的支持向量機(jī)集成方法

呂曉燕， 陳立潮

(1. 山西醫(yī)科大學(xué) 計(jì)算機(jī)教學(xué)部， 山西 太原 030001； 2. 太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 山西 太原 030024)

0 引 言

隨著數(shù)據(jù)以及大數(shù)據(jù)價(jià)值的不斷發(fā)現(xiàn)， 機(jī)器學(xué)習(xí)、 深度學(xué)習(xí)方法被越來越多地應(yīng)用于數(shù)據(jù)處理. 其中， Support Vector Machine(SVM)， 即支持向量機(jī)方法， 更是備受推崇[1-3]. 已有的研究表明： 集合多個(gè)SVM分類器， 可以提高系統(tǒng)的泛化能力[4-6]. Zhou[3]等人在研究中進(jìn)一步發(fā)現(xiàn)， 選擇部分SVM分類器集成， 性能要優(yōu)于使用所有個(gè)體SVM分類器. 文獻(xiàn)[4]構(gòu)建了二級(jí)SVM分類器， 利用投票法集成. 文獻(xiàn)[6]提出了多級(jí)支持向量機(jī). 文獻(xiàn)[7]將灰色理論引入SVM的集成， 進(jìn)行預(yù)測(cè)等. 這些研究為SVM的集成學(xué)習(xí)提供了新的思路[8-10]. 但實(shí)際應(yīng)用中， 分類器常常需要隨著新樣本的特征， 能自動(dòng)調(diào)整， 以增加自適應(yīng)性.

基于此， 本文提出一種自適應(yīng)支持向量機(jī)集成方法. 通過對(duì)待定樣本的特征分析, 利用算法在樣本空間搜索其近鄰. 在此基礎(chǔ)上， 依據(jù)各個(gè)SVM分類器在近鄰的分類精度,擇優(yōu)挑選部分SVM組合. 集成過程中， 無論是分類器成員還是分類器在集成中所占的權(quán)重， 都能隨著待判別樣本的特征自動(dòng)調(diào)整， 實(shí)現(xiàn)了“私人定制”.

近鄰如何確定， 分類器如何選取， 集成時(shí)各分類器占的權(quán)重如何確定， 是本文重點(diǎn)闡述的內(nèi)容.

1 基于待定樣本的近鄰搜索

在模式特征空間劃分中， 待定樣本的近鄰， 是指與之特征相近的一組訓(xùn)練樣本. 如何獲取近鄰是本研究解決的首要問題.

1.1 相關(guān)理論

1.1.1 模糊C均值聚類(FCM)

設(shè)X={X1,X2,…,Xn}∈R, 為樣本空間的數(shù)據(jù)集， 將樣本集劃分為C類,V={V1,V2,… ,Vc}為C個(gè)聚類中心. FCM的義目標(biāo)函數(shù)為

(1)

約束于

?j=1,…,n,

式中：U為隸屬度矩陣；uij為隸屬度.

注意到， 式(1)的目標(biāo)函數(shù)中， 默認(rèn)樣本的各個(gè)特征對(duì)分類所起的作用相同， 有悖實(shí)際情況. 因此， 對(duì)式(1)進(jìn)行修正， 修正后的目標(biāo)函數(shù)為

(2)

式中：wk為樣本各屬性的權(quán)重.

1.1.2 模糊貼近度

設(shè)A和B是論域X={x1,x2,…,xn}上的兩個(gè)模糊集合，μA(x)，μB(x)為隸屬度函數(shù). 則A,B的海明加權(quán)相對(duì)距離為

(3)

式中：w(xi)為權(quán)重， 滿足

1.2 基于樣本特征的近鄰搜索

為了確定待分類樣本的近鄰， 基于改進(jìn)的FCM及模糊貼近度的近鄰搜索算法， 在MATLAB環(huán)境下， 完成程序的設(shè)計(jì).

首先， 通過改進(jìn)后的FCM算法， 將樣本特征空間：X={X1,X2,…,Xn}劃分為c個(gè)模式特征空間：A1,A2,…,Ac， 聚類中心分別為V1,V2,…,Vc.

然后， 根據(jù)待分類樣本B的特征， 據(jù)式(3)， 計(jì)算B與各類的模糊貼近度.

若δ(Vi,B)=max{δ(V1,B),δ(V2,B),…,δ(Vc,B)}, 則B最貼近Vi.

則Vi所在的模式特征空間上所有的樣本均為待定樣本B在特征空間上的近鄰.

基于改進(jìn)的FCM與模糊貼近度的樣本近鄰搜索算法如下：

Step 1 初始化： 樣本分類數(shù)為c(2≤c≤n)， 誤差精度為ξ,U(0)為初始矩陣.

Step 2 計(jì)算各聚類中心Vi(i=1,2，…，c)

(4)

其中

i=1,2,…,c;j=1,2,…,n.

(5)

Step 3 修正劃分矩陣U(l)

(6)

Step 4 比較U(l)與U(l+1). 對(duì)取定的ξ>0， 若‖U(l+1)-U(l)‖≤ξ, 則迭代停止， 轉(zhuǎn)step 6. 否則，l=l+1， 轉(zhuǎn)step 2繼續(xù)迭代.

Step 5 據(jù)式(3), 計(jì)算待分類樣本與各個(gè)類的模糊貼近度， 最大值所在的類為其歸屬類.

Step 6 結(jié)束.

2 基于樣本近鄰分類精度的SVM集成

2.1 基于近鄰分類精度的分類器選擇

依據(jù)樣本近鄰的分類， 構(gòu)造混淆矩陣如式(7)所示.

(7)

設(shè)N為類別數(shù)， 定義分類精度

(8)

式中：rjj為分類器能正確分類的樣本數(shù)；rjl為誤將j類的樣本錯(cuò)分到l類的樣本數(shù).

由于樣本特征變化會(huì)影響SVM分類器的分類能力， 因此， 對(duì)待分類樣本確定以下分類器選取原則： 依據(jù)各分類器在其近鄰的分類精度值， 從高到低擇優(yōu)選取. 對(duì)于某個(gè)分類器SVMi， 當(dāng)其分類精度LAi大于精度閥值λ時(shí)， 該分類器被選擇集成.

2.2 基于樣本近鄰分類精度的分類器集成

假設(shè)有k個(gè)分類器被選中. 對(duì)于每個(gè)被選中的分類器， 設(shè)其在待分類樣本近鄰的分類精度為LAi， 則該分類器在集成時(shí)， 權(quán)重wi可用式(9)計(jì)算.

(9)

集成判決模型為

(10)

基于樣本分類精度的SVM集成算法， 部分代碼如下：

Fork=1 toK

利用混亂矩陣CM計(jì)算LALk(x)；

Do procedure_select()； 選擇l個(gè)分類器

Fork=1 tol

計(jì)算SVMk(x);

If 所有的SVMk都把x判給相同的類別

Thenx就屬于該類別

Else

End for

Procedure_ select()： 選擇過程:

Fork=1 toK

IfLAk(x)≥λ；λ為閾值

Then 第k個(gè)分類器被選中

Else

Goto 返回循環(huán)起始語句， 繼續(xù)循環(huán)

Endfor

集成判決流程圖如圖 1 所示.

圖 1 SVM集成方法流程圖Fig.1 Flowchart for support vector machine integration

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

3.1 數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境

選取UCI標(biāo)準(zhǔn)數(shù)據(jù)集中的2個(gè)醫(yī)學(xué)數(shù)據(jù)集Cardiotocography和 Liver disorder數(shù)據(jù)集， 在Matlab環(huán)境下， 進(jìn)行數(shù)據(jù)的分類及預(yù)測(cè). 數(shù)據(jù)集信息如表 1 所示.

表 1 數(shù)據(jù)集信息Tab.1 Data set information

3.2 數(shù)據(jù)的預(yù)處理及特征提取

為了提取對(duì)分類有影響的重要指標(biāo)， 在對(duì)數(shù)據(jù)歸一處理的基礎(chǔ)上， 利用Relief算法， 對(duì)兩個(gè)數(shù)據(jù)集， 提取重要的特征指標(biāo)， 并賦予相應(yīng)的權(quán)重. 結(jié)果如表 2 和表 3.

表 2 Cardiotocography數(shù)據(jù)集屬性及權(quán)重Tab.2 Cardiotocography data set

表 3 Liver disorder數(shù)據(jù)集屬性及權(quán)重Tab.3 Liver disorder data set

3.3 集成分類器成員的選擇

利用Bagging技術(shù)， 訓(xùn)練產(chǎn)生100個(gè)SVM分類器. 選用徑向基核函數(shù)， 設(shè)置參數(shù)為：σ2=0.06，C=10.

調(diào)整精度閾值λ， 可改變集成分類器的組合規(guī)模. 根據(jù)不同的λ取值， 分別確定不同數(shù)目的分類器組合， 觀察對(duì)分類結(jié)果的影響. 結(jié)果如圖 2 和圖 3 所示.

圖 2 λ取不同值在Cardiotocography上的分類結(jié)果Fig.2 Results on cardiotocography

圖 3 λ取不同值在Liver disorder上的分類Fig.3 Results on liver disorder

圖 2 和圖 3 顯示， 隨著集成中分類器個(gè)數(shù)的增加， 準(zhǔn)確率開始上升， 直至最高. 此時(shí)， 圖 2 對(duì)應(yīng)的分類器個(gè)數(shù)為26(λ為0.527)， 圖3對(duì)應(yīng)的分類器個(gè)數(shù)為21(λ為0.431). 繼續(xù)增加分類器個(gè)數(shù)， 發(fā)現(xiàn)準(zhǔn)確率反而下降， 說明集成中選擇的分類器并非越多越好. 實(shí)踐中， 可以通過不斷調(diào)整精度閥值λ的值， 以獲得最佳的組合分類器個(gè)數(shù).

3.4 不同集成方法分類結(jié)果的比較

將本文方法構(gòu)建的分類器與其它分類器從分類性能方面比較， 結(jié)果如表 4 所示.

其中， Bagging和Boosting集成， 采用的算法分別為RF(Random Forest)算法和Adaboost算法.

表 4 幾種方法的分類結(jié)果Tab.4 Classification results of several methods

表 4 顯示， 本文方法構(gòu)建的分類器與其它常見的分類器相比， 無論是準(zhǔn)確度， 還是靈敏度或者或特異度， 都有明顯的優(yōu)勢(shì). RF算法與Adaboost算法分類， 分類效果接近， 均高于全部分類器集成.

進(jìn)一步在兩個(gè)數(shù)據(jù)集的測(cè)試集上比較幾種集成分類器的判決時(shí)間， 結(jié)果如圖 4 所示.

圖 4 不同分類器判決時(shí)間Fig.4 Decision time of different classifiers

圖 4 顯示， 本文方法構(gòu)建的分類器可顯著縮短判別時(shí)間. 這與本文在個(gè)體分類器選擇時(shí)使用的策略有關(guān). 由于無需考慮各分類器在整體樣本的分類精度， 所以減少了計(jì)算的工作量， 縮短了判別時(shí)間. RF算法在數(shù)據(jù)分類時(shí)花費(fèi)時(shí)間最長， 原因在于該算法依賴的是決策樹， 復(fù)雜度增加時(shí)， 決策樹不可避免增加， 導(dǎo)致低效率.

3.5 集成分類器的穩(wěn)定性實(shí)驗(yàn)

分別從Cardiotocography和Liver disorder兩個(gè)數(shù)據(jù)集中， 選取不同規(guī)模的數(shù)據(jù)進(jìn)行測(cè)試， 結(jié)果如圖 5 和圖 6 所示.

圖 5 Cardiotocography數(shù)據(jù)集上的穩(wěn)定性Fig.5 Stability on Cardiotocography

圖 6 Liver disorder數(shù)據(jù)集上的穩(wěn)定性Fig.6 Stability on Liver disorder

圖 5 和圖 6 表明， 本文方法構(gòu)建的SVM集成分類器的準(zhǔn)確度始終高于其它兩種方法. 進(jìn)一步擴(kuò)大數(shù)據(jù)規(guī)模， 準(zhǔn)確率始終高于其它三種分類器的判別效果， 說明了該分類器的性能具有一定的可靠性.

4 結(jié) 論

SVM集成的關(guān)鍵是如何擇優(yōu)選取個(gè)體分類器. 本文從分類性能、 判別時(shí)間及穩(wěn)定性方面， 將建立的分類器與其它常用集成分類器進(jìn)行實(shí)驗(yàn)對(duì)比.

結(jié)果顯示， 本文提出的方法， 在UCI的兩個(gè)醫(yī)學(xué)數(shù)據(jù)集的分類中， 無論在分類的準(zhǔn)確度還是靈敏度及特異度方面， 均高于其它的集成方法. 選取不同規(guī)模的數(shù)據(jù)進(jìn)行穩(wěn)定性實(shí)驗(yàn)， 本文方法構(gòu)建的分類器始終具有一定的優(yōu)勢(shì)， 說明本文提出的方法在實(shí)踐中具有一定的穩(wěn)定性和可靠性.

比較幾種方法的分類判別時(shí)間， 結(jié)果顯示， 本文提出的方法所需的時(shí)間最短， 利用Bagging中的RF算法判決時(shí)， 時(shí)間最長， 反應(yīng)了該算法在解決復(fù)雜問題時(shí)， 因決策樹增多而導(dǎo)致的低效率.

另外， 本文提出的方法最大的優(yōu)勢(shì)還在于動(dòng)態(tài)性和自適應(yīng)性. SVM集成中的各個(gè)分類品成員， 以及各成員分類器在集成判別中的權(quán)重， 都不是一成不變的， 而是隨著待定樣本特征的變化動(dòng)態(tài)調(diào)整.