基于支持向量機的改進分類算法①

李亦滔

(寧德海關,寧德 352100)

引言

支持向量機(Support Vector Machine,SVM)是建立在統計學習理論的VC維理論和結構風險最小原理基礎上的,根據有限的樣本信息在模型的復雜性(即對特定訓練樣本的學習精度)和學習能力(即無錯誤地識別任意樣本的能力)之間尋求最佳折中,以期獲得最好的推廣能力.目前,支持向量機分類技術已經廣泛應用于機器學習、模式識別、模式分類、計算機視覺、工業工程應用、航空應用等各個領域中,其分類效果可觀,具有很好的發展前景[1].

SVM最初在線性可分情況下尋求最優分類面,為解決二類分類問題而提出來的,不能直接運用于多類分類.業內專家提出One-Versus-Rest (1-v-r)[2],One-Versus-One (1-v-1)[3],Directed Acyclic Graph (DAG)[4,5],決策樹[6-8]等方法能夠將它擴展到多分類問題,取得較好的分類精度,但是這些方法尚存在“決策盲區”、“不平衡類”等缺陷,分類器性能的優劣主要由分類精度和分類速度來確定,其推廣能力受到一定影響.隨著分類問題復雜性的增加,類別數量、訓練樣本、特征維數均有所增加,分類速度也越來越受到重視,學者不斷深入研究改進二叉樹算法,取得了較顯著成果,陳柏志等[9]通過帕累托原則建立類間差異性估計策略對二叉樹分類算法進行了改進,在一定程度上縮減了分類盲區;趙海洋等[10]則從類型間距方面對BT-SVM的層次結構進行改進,提高了BT-SVM的分類精度;權文等[11]為改善分類效果采用了聚類算法對BT-SVM進行了改進,提高分類精度;冷強奎等[12]提出通過計算兩個距離最遠的類的質心獲得超平面,建立混合二叉樹結構,取得較好效果.因此提高SVM多類分類的快速性和準確性成為機器學習領域研究的熱點和難點[13].

本文在對現有主要的SVM多類分類算法作簡單介紹和分析的基礎上,提出一種改進的二叉樹多類分類算法,達到又快又好地解決多類分類問題的預期.在二叉樹結構的基礎上,根據訓練樣本對最優分類超平面的貢獻程度,引入概率計算方法,為每個二類分類器賦值不同的權重系數,從而建立一個推廣性較高的多類SVM分類模型.通過采用標準數據集對比分析各種算法的性能,結果表明基于二叉樹的改進分類算法有效,提高分類精度,擴大推廣能力.

1 支持向量機理論簡介[14]

Vapnik[15]等人根據統計學習理論提出的一種新的學習方法——支持向量機,堅持結構風險最小化原則,盡量提高學習機器的泛化能力,即由有限的訓練集樣本得到小的誤差能夠保證對獨立的測試集仍保持小的誤差.在線性可分的情況下,定義分類超平面f(x)

當輸入的樣本值x屬于正類時,f(x)≥0;當輸入的樣本值x屬于負類時,f(x)＜0.

式中,W是分類面的權系數向量;b為分類的域值.W·X是W和X的內積.如果要求得到W和b的值,通過樣本與最佳超平面的最近距離為1/‖W‖,W和b的優化條件應是使兩類樣本到超平面最小的距離之和2/‖W‖為最大.因此最佳超平面應滿足約束:

假設a的最優解為a*,然后W和b的最優解分別為w*和b*,這樣可以得到:

式中,sgn(·)代表符號函數,w*表示權值,是最優拉格朗日系數,b*為最優閾值.通過求解,可得最優分類決策函數為:

核函數是一種特定的高維特征空間的線性學習算法,實現非線性映射的目的.典型的核函數有三種:多項式核函數、徑向基核函數、Sigmoid核函數.

SVM在解決小樣本、非線性及高維數等模式識別問題中表現出許多特有的優勢,克服人工神經網絡學習結構難以確定和存在局部最優等缺點,這些優勢能夠被推廣應用到分類預測等問題中,這使它成為機器學習領域的研究熱點,并被成功應用到很多領域.但是經典的SVM算法只能解決二類分類問題,如何有效地擴展到多分類問題仍未很好的解決,特別是標準SVM的判決輸出為硬判決,在多分類中更需要一個具有軟判決輸出的SVM.利用標準SVM的判決輸出與類后驗概率的映射關系[16],即將SVM的判決輸出f(x)通過Sigmoid函數映射到0與1之間,構造概率輸出的數學表達式,其簡化形式如下:

式中,參數A和B控制Sigmoid函數的形態,A和B是通過最小化已知的訓練數據和它們的決策值f的負的對數似然函數得到.

2 多類分類器算法[17]

在實際應用中的分類問題都是多類的,經典SVM無法直接解決,為將支持向量機技術更好應用于實際中,目前國內外學者提出了許多途徑,歸納為兩類[18]:一是構造多類分類數學模型,考慮所有情況,這種方法在經典SVM分類的基礎上,優化SVM的目標函數和參數,通過決策實現多類分類.但是這種方法目標函數的表達式十分復雜,難于求解,在工程應用領域很少被采用;二是按照將多類問題歸結為多個兩類問題的思路,通過優化組合多個二分類支持向量機實現多類分類,即將一個復雜問題轉化若干個簡單問題,得到較好推廣.基于第二種算法思想,經典方法有:One-Versus-Rest (1-v-r),One-Versus-One (1-v-1),Directed Acyclic Graph (DAG),二叉樹等.

2.1 1-v-r算法

基本思想[19]:構造一個二類分類器,將其中的一類作為一大類,其余各類作為另外一大類,分類時把那一類同其他類中分開.對于N(N≥2)類的分類問題,需構造N個二類分類器,采用“比較法”.對測試樣本x進行識別.將樣本輸入到已構造的N個二類分類器,得到相應的N個輸出結果,綜合比較這些結果,明確輸出最大的那一類,其分類器的序號就是樣本所屬的類別號,如圖1所示.

圖1 1-v-r構造示意圖

決策函數中輸出最大值的類別為x的類別,判定規則的公式

1 -v-r算法的優點是簡單、直接.主要缺點是:1)訓練樣本需要先通過構造的每個二類分類器進行訓練;而已構造的所有二類分類器都要對測試樣本進行分類后,才能確定測試樣本的類別,所以,一旦訓練樣本數和類別數較大,那么訓練和測試分類的速度就會比較慢;2)假如N類中所有的類型沒有測試樣本的類型,這樣就找不到正確的類別,按照“比較法”的方法,表明N個輸出結果中總有輸出最大的一個,就會將本來找不到類別的測試樣本誤判為N類中的一類,出現分類的錯誤.

2.2 1-v-1算法

基本思想:構造N(N≥2)個類別中所有存在的二類分類器,一共建立N(N-1)/2個,如圖2所示.采用“投票法”對測試樣本進行識別,將樣本輸入到已構造的任何一個二類分類器,當所有的分類器都對測試樣本進行分類后,最后確定哪一類的票數最多,那么該測試樣本就屬于這一類別.

圖2 1-v-1構造示意圖

假設已有第i類和第j類訓練樣本構造的二類分類器,算法解決如下優化問題:

構造N(N-1)/2個二類分類器的決策函數,“投票法”判決 max((wij)TΦ(xi)+bij),若屬于i類,則i的票數增加一,否則j的票數增加一,哪類統計得票最多,即為所屬類別.

1 -v-1算法的優點是每個SVM只考慮兩類樣本,易訓練,且其訓練速度較“1-v-r算法”方法快,其分類精度也較“1-v-r算法”方法高.主要缺點是:1)二類分類器的數目N(N-1)/2隨著類別數N的增加而增加,運算量也隨之變得很大,導致訓練和測試分類的速度變得非常慢.2)測試分類的結果,一旦出現某兩類的得票相同時,無法找到正確的類別,可能出現分類的錯誤.3)假如N類中所有的類型沒有測試樣本的類型,這樣就找不到正確的類別,按照“投票法”的方法,N類中總有某一類得票最多,表明N類中總有某一類所得的票數最多,就會將本來找不到類別的測試樣本誤分為N類中的一類,造成分類的錯誤.

2.3 有向無環圖(DAG)算法

基本思想[20]:構造所有的二類分類器,作為一種雙向的有向無環圖的節點,底層的“葉”是由N個類別組成的,最底層含有N個葉節點,如圖3所示.按照“自上而下”的原則,分類時從頂部分類器開始,依據頂部的分類器分類結果,判定采用下一層的左節點還是右節點進行分類,直到底層的某個“葉”為止,對樣本所屬的類別進行編號,對應該“葉”的序號.采用“排除法”對測試樣本進行識別,將樣本輸入到已構造的子二類分類器中,每通過一個,都能排除掉最不可能的類別,最終得到底層的某個“葉”所對應的類別.

圖3 DAG構造示意圖

DAG算法的優點是在訓練階段,雖然與1-v-1算法相同,但在分類階段時,僅用N-1個分類器,分類效率明顯高于1-v-1算法和1-v-r算法,重復訓練樣本少,分類精度較高.采用“排除法”進行分類,降低誤分的可能性.主要缺點是:DAG結構相對于二叉樹,它具有冗余性,同一類別的分類個體,分類路徑可能不同,影響分類精度.

2.4 二叉樹分類算法

基本思想[21]:將N(N≥2)類中N/2(或(N+1)/2)類作為一大類,剩余的類看作另一大類,建立第一個二類分類器.然后再分別對那兩個多類單獨分類,各取出最相近的N/2-1類作為一大類,將那N/2類中余下的一類看作另一大類,再建立一個二類分類器.往下同理建立二類分類器,依次往下采取“直接法”直至完全分類,如圖4所示.

圖4 完全二叉樹構造示意圖

二叉樹分類算法的優點是簡單、直觀,重復訓練樣本少.對于N類,測試時僅需建立log2N二類分類器,都比前面的三種算法數量少,克服上面算法存在的無法識別的陰影區域,而且重復訓練的樣本量少,訓練和分類的時間可以減少.主要缺點是初始分類錯誤具有遺傳性,各子節點的劃分方法對結果有較大影響,在某個節點出現誤分類后,將無法糾正到正確的結果,因此具有較低的容錯率.

以上介紹4種常用的多類分類算法.其中,前3種方法在樣本數目及類別數目較多時,訓練和分類速度都比較慢,而且前兩種方法還存在不可分區域.二叉樹多類分類方法在識別速度上具有一定的優勢,不過,二叉樹分類器存在著“錯誤積累”的問題,對于N類分類問題,4種算法的對比見表1.

表1 4種算法的對比

3 改進的二叉樹多類分類算法

在多分類問題中,二叉樹分類算法表現出許多優良的性能,不僅可以有效解決了不可分問題,還能減少分類器的數量,但是也存在較突出問題:可能會導致“錯誤累積”現象,即若在上層節點處分類一旦錯誤分類,則這種錯誤會傳遞下去,后續節點將失去分類的意義,因此二叉樹分類算法越上層節點的分類性能對整個分類模型的推廣性影響越大.為了獲得最佳的分類效果,必須根據實際情況來構造二叉樹各內節點的最優超平面,在生成二叉樹的過程中,應該讓最易分割的類最早分割出來,即在二叉樹的上層節點處分割.但考慮到不同的訓練樣本對最優分類超平面的貢獻程度不同,為綜合考慮樣本信息,參考郭亞琴等人[22]提出的樣本分布度量方法,利用類間散布度量與類內散布度量的比值作為樣本分布情況的度量,構造樣本間的映射關系.在二叉樹分類的基礎上,構建SVM輸出模型,為二類分類器賦值不同的權重系數,求得各分類器的可信度.具體算法流程圖如圖5所示.

(1)將訓練樣本集輸入到支持向量機中學習,求得最優的參數w*、ai*、b*、A、B等,從而得到式(6),式(7)中的SVM輸出模型Si.

(2)假設 Θ 為識別框架,且 Θ ={q1,q2,···,qK},通過二叉樹分類,構造n=K-1個二類分類器,表示為 {c1,c2,···,cn}.

(3)將訓練樣本集輸入到SVM輸出模型進行訓練,求出分類器 {c1,c2,···,cn}所對應的權值p1,p2,···,pn(i=1,···,n),作為各分類器分類判定的可信度,可信度區間在0～1之間,“1”代表完全可信,即屬于該類;“0”代表完全不可信,即不屬于該類,可信度越接近1,說明分類判定的準確性越高.

(4)計算測試樣本分布情況的度量,采用類間分布度量與類內分布度量的比值作為分類依據,將比值相近的作為一大類,剩余的類看作另一大類,再根據分類器的可信度,將屬于第i類的樣本盡快從樣本集中識別出,屬于第i類別的樣本標記為正,而其它樣本標記為負.往下依次,直至完成分類.

該改進分類算法為解決二叉樹的“錯誤累積”問題,根據樣本對最優分類超平面的貢獻程度不同,通過計算樣本分布情況的度量,利用有限樣本數據的分布來對真實分布做近似估計,同時根據SVM輸出模型計算分類器分類可信度,避免在上層節點處分類出現錯誤分類,繼續傳遞錯誤;同時搭建較優的二叉樹結構,如圖6所示,能讓最易分割的類最早分割出來,即在二叉樹的上層節點處分割,提高分類效果.

圖5 改進分類算法流程圖

圖6 改進二叉樹結構示意圖

4 實驗驗證

實驗仿真采用UCI機器學習公用數據庫[23]中Iris和Wine Quality Red數據集的實驗數據.為了驗證支持向量機的分類決策性能,首先利用Iris數據集:3種不同類型的花(Setosa、Versicolour和Virginica),以及Iris花的4種特征屬性:花瓣長度、花瓣寬度、萼片長度、萼片寬度,共150組數據,每種花50組數據,每組數據包含4種屬性,在Matlab上進行了仿真試驗.任取部分數據作為實驗樣本進行測試和分類,得到Fisher Iris數據集樣本分布圖和分類結果,可知支持向量機具有較好的分類性能,如圖7所示.

圖7 樣本分布圖

為了測試支持向量機多類分類器的準確性和快速性,再利用Wine Quality Red數據集:11種不同質量等級的葡萄酒,共1599組樣本,每組樣本含有11種葡萄酒的有效化學度量值(固定酸度、揮發酸度、檸檬酸、殘糖、氯化物、游離二氧化硫、總二氧化硫、密度、pH值、硫酸鹽、酒精),選取與質量等級相關性較大的5種量值(檸檬酸、pH值、酒精度、揮發酸以及硫酸鹽)作為特征屬性,支持向量機的結構是5個輸入變量,11個輸出變量.任取150組樣本,作為實驗樣本,1/2作為訓練樣本,其余1/2作為測試樣本,通過多類分類算法(1-vs-r、1-vs-1、DAG、二叉樹及改進的二叉樹)對樣本進行仿真試驗.分類測試對比結果見表3.

從表2,表3實驗結果來看:表2是針對類別數為3的多類分類實驗結果,表3是針對類別數為11的多類分類實驗結果,兩組實驗結果得到類似結果,說明改進二叉樹算法分類方法具有明顯的優勢.

從時間角度,時間與決策分類器的數量、求解分類參數的計算量相關,五種多類分類算法中,改進的二叉樹算法的訓練時間稍長于二叉樹算法,由于引入權值計算,優化問題求解計算量變大,但是分類器數量最少,得到分類最優參數后測試時間最短;而明顯短于其它3種算法,由于搭建分類器的數量少于其它3種算法.

表2 3種類別分類結果

表3 11種類別分類結果

從分類精度角度,分類精度與求解決策最優超平面的準確性、是否對樣本進行預處理有關,求解最優分類平面和有針對性地分類可以減少“誤分”、“錯分”、“不可分”等,提高了分類精度,改進的二叉樹算法的分類精度最高,對樣本進行預處理,為分類器賦值不同的權重,更具針對性,做到“能分先分,應分盡分,難分賦值分”,分類精度明顯高于其它四種算法.

綜上,改進二叉樹算法具有較明顯的時間優勢,較高的分類精度.驗證了改進二叉樹算法分類器的準確性和快速性,且整體性能稍優于其他4種算法.如果分類類別多時,從表1中可知分類器的數量遞增,除二叉樹外其他3種算法的分類時間會明顯增加,從表2、表3中可知改進二叉樹的分類精度明顯高于其他4種算法,并且類別越多優勢更凸顯.因此改進二叉樹算法分類方法適用于類別數較多,分類實時性要求較高的場合.

5 結論

本文從支持向量機的基本理論出發,通過對比分析了4種常見多分類器分類算法的構造原理和特點,為改進支持向量機的多類分類問題提供依據,引入二類分類器的權值,提出基于二叉樹的改進分類算法,實驗結果表明該算法可提高多類SVM分類器的效率,并有助于分類準確率的提升,使多類支持向量機能夠更好地解決工程實際問題.筆者認為改進二叉樹算法的分類器適用于類別數較多,分類實時性要求較高的場合,將發揮其優勢.再采用最大化樣本類間幾何距離的方法劃分各類別,可能會取得更好的效果,還有待于進一步的研究驗證.