《電子技術應用》
您所在的位置:首頁 > 通信與網(wǎng)絡 > 設計應用 > 基于二叉樹的SVM多類分類的研究與改進
基于二叉樹的SVM多類分類的研究與改進
來源:微型機與應用2013年第12期
周愛武,溫春林,王 浩
(安徽大學 計算機科學與技術學院,安徽 合肥230039)
摘要: 支持向量機(SVM)是一種兩類分類算法,如何將SVM算法應用于多類分類問題,目前已衍生出多種方法。其中“二叉樹”方法應用比較廣泛,但分類支持向量機在樹中中間節(jié)點位置的不同,直接關系到該方法的分類準確性。基于二叉樹方法提出了“類間相異度”的策略,根據(jù)類間相異程度來決定多類的分類順序。
Abstract:
Key words :

摘  要: 支持向量機(SVM)是一種兩類分類算法,如何將SVM算法應用于多類分類問題,目前已衍生出多種方法。其中“二叉樹”方法應用比較廣泛,但分類支持向量機在樹中中間節(jié)點位置的不同,直接關系到該方法的分類準確性。基于二叉樹方法提出了“類間相異度”的策略,根據(jù)類間相異程度來決定多類的分類順序。
關鍵詞: 支持向量機;二叉樹;超球體;相異度

    支持向量機SVM(Support Vector Machine)[1]是一種基于統(tǒng)計學的VC維理論[2]和結構風險最小化原理基礎之上的兩類分類算法。目前,該算法已廣泛應用于諸多領域,如人臉檢驗、文字/手寫體識別、圖像處理[3]等。支持向量機屬于一種機器學習算法,核函數(shù)則是其中的核心部分。對于難以分類的低維空間向量集,通常的做法是向高維空間集轉化,但這也增加了計算的復雜度,即維數(shù)災難[4]問題。而核函數(shù)[4]卻可以很好地解決這個問題,只要選取合適的核函數(shù),即可得到高維空間的向量機(也稱超平面[2])。
    當使用向量機進行多類分類時,需要將多類問題轉化為兩類問題。常用的有“一對多”(One Versus Rest)[5]、“一對一”(One Versus One)[6]、“二叉樹”(Binary Tree)[7]和“有向無環(huán)圖”(Directed Acyclic Graph)[8]等方法,本文將對多類分類支持向量機[9]的這些方法作概略介紹和比較,同時對基于偏二叉樹多類分類向量機提出一些改進意見。
1 SVM多類分類方法
1.1 SVM多類分類方法介紹

    現(xiàn)有一個多類分類問題,其中類別數(shù)為k。當使用支持向量機對此問題進行分類時,需假設一類為正樣本,另一類為負樣本。
    “一對多”方法將類i樣本作為正樣本,而除該類以外的所有類作為負樣本,在這兩類樣本間訓練出向量機,該方法總共構造了k個分類支持向量機。在對某向量進行測試時,取計算出最大值的向量機所對應的類別作為該向量的類別。
    “一對一”方法是從分類問題中選取類別i和類別j中的樣本數(shù)據(jù)訓練兩類間的分類向量機,這樣構造出的向量機的總數(shù)為k(k-1)/2。雖然“一對一”分類方法產生的分類向量機的數(shù)目是“一對多”方法的(k-1)/2倍,但“一對一”方法的訓練規(guī)模要比“一對多”方法小很多。對向量的測試采取計分的方式,通過k(k-1)/2個分類機的計算以后,選取得分最高的類別作為該測試數(shù)據(jù)的類別。
    二叉樹方法是將兩類之間的k-1個向量機作為中間節(jié)點,葉子節(jié)點對應k個類別樣本,以這樣的方式構建一棵分類二叉樹,常用的方式包括滿二叉樹和偏二叉樹。在對樣本進行訓練時,根節(jié)點的向量機在全部樣本空間上進行訓練,而子節(jié)點向量機則在根節(jié)點的負樣本類或正樣本類上訓練,依次類推,直至k-1個分類機在k-1類和k類樣本上進行訓練。
    有向無環(huán)圖方法與“一對一”方法一樣,也是在任意兩類之間訓練分類向量機,也即具有相同的分類向量機數(shù)目。k(k-1)/2個分類向量機作為圖的中間節(jié)點,圖中葉子節(jié)點為k類樣本。但在測試向量數(shù)據(jù)所屬類別時,僅需經(jīng)過k-1個分類向量機節(jié)點即可判斷測試數(shù)據(jù)的類別。
1.2 基于二叉樹的SVM多類分類方法
    在SVM多類分類算法中,分類樹是一種應用十分廣泛的多類分類策略。但分類向量機在樹中所處的節(jié)點位置,直接影響到分類的準確性和推廣的性能。不同的二叉樹結構,會使得測試數(shù)據(jù)得到不同的分類結果。隨著節(jié)點分類層次的深入,可能會產生分類“誤差累積”的現(xiàn)象[10]。因此,生成合適的二叉樹結構顯得異常重要。
    生成多類分類二叉樹通常包括兩種思路:第一種是依據(jù)類中樣本點的分布情況,優(yōu)先分出分布區(qū)域較大的類;第二種是依據(jù)類間距離作出判斷,優(yōu)先分出離其他類較遠的類。而衡量類分布情況的一個有效方法是計算各個類的超球體的體積,體積越大,類的分布區(qū)域也就越大。類的超球體體積定義如下:
    
    本文對于構造偏二叉樹提出了類間相異度的方法,有效解決了上述問題。
2 改進的偏二叉樹SVM多類分類方法
    本文從類在空間中的分布情況和類間距離這兩方面著手,優(yōu)化分類偏二叉樹的結構。對于類的分布情況采用參考文獻[11]所提出的超球體的體積來度量,而類間距離采用超球體重心間的歐氏距離來度量,關于歐氏距離的概念見定義2。為綜合考慮以上這兩個方面,本文引入了類間相異度的概念,具體內容見定義3。
    

 


    輸入:包含n個樣本對象(含分類號)的數(shù)據(jù)集D。
    輸出:包含K個元素的優(yōu)先分類序列S。
    算法:
    (1)計算每個類的最小超球體的重心和半徑;
    (2)repeat;
    (3)根據(jù)定義3計算每個類相對D中其他剩余類的相異度之和;
    (4)選擇步驟(3)中相異度最大的類i,把類標號i添加到S中,刪除D中類標號為i的元素;
    (5)until D中只剩兩個類的元素;
    (6)把剩余的兩個類的類標號添加到序列S中。
    算法在步驟(5)返回步驟(3)循環(huán)執(zhí)行,當數(shù)據(jù)集中僅包含兩類樣本時算法結束。
    以生成分類偏二叉樹的根節(jié)點和左右孩子為例,取出分類序列S中第一個元素的類標號,將該類和其他類間訓練出的向量機作為根節(jié)點,該類作為左孩子,然后再從分類序列S中取出第二個元素的類標號,將該類和其他類間訓練出的向量機作為右孩子。以同樣的方式生成剩余的中間節(jié)點和葉子節(jié)點,最終構建出的多類分類偏二叉樹如圖2所示。

3 實驗分析
    本文所有算法均使用C++語言實現(xiàn),并使用VC6.0完成編譯。實驗平臺:Pentium?誖Dual-Core CPU 2.80 GHz、2 GB內存、Windows XP 操作系統(tǒng)。所有實驗數(shù)據(jù)均來自UCI數(shù)據(jù)庫中的多類別數(shù)據(jù)集vehicle和letter,具體樣本數(shù)量和維數(shù)如表1所示。

    由于取不同的核參數(shù)λ和懲罰系數(shù)C[12]對模型的推廣有很大的影響,為了能更好地比較出依據(jù)不同的策略生成的偏二叉樹的推廣性能,本實驗與參考文獻[12]類似,對相同數(shù)據(jù)集的每一種策略均采用多種(C,λ)參數(shù)進行實驗,其中C的取值為2、4、8、16、32、64,λ的取值為2、4、8、16,這樣總共有6×4=24種組合,每個實驗的KTT停止條件的容許誤差為0.001。取出最高的預測準確率所對應的(C,λ)參數(shù)及其準確率進行比較。
    從實驗數(shù)據(jù)的分析中可以看出,對于數(shù)據(jù)集vehicle,當訓練樣本的數(shù)量為600時,在預測準確率方面,使用本文提出的方法與其他方法相比,并沒有明顯的提高。而對于數(shù)據(jù)集letter,由于比vehicle數(shù)據(jù)集在訓練時多出300個樣本,本文提出的方法在準確率方面有了明顯的優(yōu)勢??傮w來講,本文提出的根據(jù)類間相異度的策略生成的偏二叉樹要比單獨根據(jù)類間距離或單獨根據(jù)類樣本的分布情況生成的偏二叉樹,在準確率方面有一定的改善。
    基于二叉樹多類分類方法是SVM算法在多類分類問題中的一個重要應用,但支持向量機節(jié)點在二叉樹中所處位置的不同對分類的準確性有較大影響。本文首先分析和比較了由SVM算法所產生的多類分類方法,然后提出了一種依據(jù)類間相異度的策略來生成基于偏二叉樹的多類分類支持向量機。實驗結果表明,改進的算法在準確性方面有很大的提高。
參考文獻
[1] VAPNIK V N.Statistical learning theory[M].New York:John Wiley and Sons,l998.
[2] 瓦普尼克.統(tǒng)計學習理論的本質[M].張學工,譯.北京:清華大學出版社,2000.
[3] 葉磊,駱興國.支持向量機應用概述[J].電腦知識與技術,2010,6(34):153-154.
[4] 顧亞祥,丁世飛.支持向量機研究進展[J].計算機科學,2011,38(1):14-17.
[5] BOTTOU L,CORTES C,DENKER J.Comparision of classifier methods:a case study in handwriting digit recognitiong[C].Proceedings of International Conference on Pattern Recognition,1994:77-87.
[6] KRELEL U.Pairwise classification and support vector  machines[M].Cambridge,MA:MIT Press,1999:255-268.
[7] 劉健,劉忠,熊鷹.改進的二叉樹支持向量機多類分類算法研究[J].計算機工程與應用,2010,46(33):117-120.
[8] PLATT J C,CRISTIANINI N,SHAWE-TAYLOR J.Large margin DAGs for multiclass classification[C].Advances in Neural Information Processing Systems,Cambridge,MA:MIT  Press,2000:547-553.
[9] HSU C W,LIN C J.A comparsion of method for multiclass support vector machine[J]. IEEE Transaction on Neural Networks,2002,13(2):415-425.
[10] 孟媛媛,劉希玉.一種新的基于二叉樹的SVM多類分類方法[J].計算機應用,2005,25(11):195-196,199.
[11] 唐發(fā)明,王仲東,陳錦云.支持向量機多類分類算法研究[J].控制與決策,2005,20(7):746-749.
[12] 單玉剛,王宏,董爽.改進的一對一支持向量機多分類算法[J].計算機工程與設計,2012,33(5):165-169.

此內容為AET網(wǎng)站原創(chuàng),未經(jīng)授權禁止轉載。