基于隸屬度分離測度ＳＶＭ決策樹層次結構設計方法

摘要：從樣本的類空間分布和隨機測試樣本對每個類別的隸屬度兩方面考慮，對現有的分離測度進行了改進，并給出了一種基于隸屬度分離測度的SVM決策樹多類分類算法。實驗表明，對于隨機測試樣本屬于每個類別的概率均不相同的多類分類問題，基于隸屬度分離測度的SVM決策樹在與傳統的SVM決策樹有著基本相同的分類精度情況下，具有更快的分類速度。

關鍵詞：層次結構; 決策樹; 支持向量機

中圖分類號：TP181

文獻標志碼：A

文章編號：1001-3695（2007）09-0162-02

支持向量機(support vector machine， SVM)是V. Vapnik等人[1]提出的一種基于統計學習理論的新一代學習機器，它建立在結構風險最小化原則基礎之上，在解決有限樣本的數據分類時具有很強的學習能力和泛化能力，成為國內外機器學習領域新的研究熱點。將支持向量機由二分類情形有效地推廣到多分類情形成為當前的研究熱點之一。已有的SVM多類分類方法可以分成兩類：一類是組合方法，通過組合多個二分類支持向量機來構造多分類支持向量機，這種方法對解決大規模多類別分類問題非常有效；另一類是直接方法，對所有的樣本使用同一個二次規劃，在構造決策函數時同時考慮所有的類別，只需一次就可以決定分類[2]。這類方法的目標函數過于復雜，適用于樣本數量規模較小的多類分類問題。

1基于組合方法的多類分類支持向量機

常見的基于組合方法的多類分類支持向量機有以下幾種：

a）一對多(oneagainstrest)[1] 該方法分別針對不同的k個類別，構造k個支持向量機。第i個支持向量機是將第i類訓練數據從其他類別中分離出來，在判斷測試樣本的類別時，把測試樣本分別代入上面的k個支持向量機，最后取決策函數輸出值最大的類別為測試樣本類別。

b）一對一(oneagainstone)[3]該方法對訓練樣本集中的任意兩個類別構造一個二分類支持向量機，僅識別這兩個類別，結果共需構造k(k-1)/2個二分類支持向量機。在判斷測試樣本的類別時，把測試樣本分別代入上面的k(k-1)/2個二分類支持向量機，使用投票法，最后取得票最多的類別為測試樣本點所屬的類別。

一對一和一對多這兩種方法，當類別數目較多時，分類速度均比較低，而且均存在拒分區域。后來出現了幾種改進算法，其中有糾錯輸出編碼支持向量機(errorcorrecting output codes，ECOCSVMs)[4]、有向無環圖支持向量機(directed acyclic graph，DAGSVMs)[5]。機選擇合適的碼本非常較困難；DAGSVMs是針對一對一方法存在誤分、拒分現象提出的，當類別數目較多時，分類速度也比較低。

c）SVM決策樹[6]該決策樹首先將所有類別分成兩個子類，再將子類進一步分成兩個次級子類，如此循環下去，直到得到一個單獨的類別為止。這樣就得到一棵倒立的二叉樹，然后對每個決策節點的二類分類問題用SVM解決。SVM決策樹方法對于k類分類問題，只需構造k-1個SVM分類決策函數，具有較高的分類效率，也不存在拒分區域。

當類別數目較多時，SVM決策樹是一種比較有效的方法。但是，SVM決策樹存在錯分累積問題，分類錯誤在越靠近樹根的地方發生，其分類性能越差。為構造分類性能良好的決策樹，可以考慮將容易分(不易產生錯分)的類先分離出來，然后再分不容易分的類。這樣就能夠使可能出現的錯分盡可能遠離樹根，即在設計SVM決策樹時，應使每個決策節點的類間隔盡可能大。SVM決策樹的層次結構設計是一個非常關鍵的問題，目前主要是通過使用分離測度來劃分各級子類的方法以設計SVM決策樹的層次結構。

2分離測度

2.1類間的分離測度

類間的分離測度是對類與類之間的可分程度大小的一個度量，它表示類與類的遠離程度。分離測度大，說明這兩類比較容易分開。在設計SVM決策樹時，要使每個決策節點的類間隔盡可能大，首先要根據訓練樣本集估計各類間的分離測度。

通常采用類中心間的距離作為類間分離性測度[7]，即若用k表示類別數目，訓練樣本集X由類Xi組成； i=1，2，…，k;用ni表示Xi包含的樣本數目;用ci表示根據訓練樣本計算出的類i的類中心，ci=(1/ni)∑x∈Xix；用smij表示類i與類j之間的分離測度，則類i與類j之間的分離測度為smij=‖ci-cj‖2。

2.2類的分離測度

3基于隸屬度分離測度的SVM決策樹層次結構

當隨機測試樣本x對每個類別的隸屬度不同時，往往傾向于判斷x是否屬于隸屬度較高的那一類。劃分各級子類時，在考慮各類空間分布的同時，最好也考慮到隨機測試樣本x對每個類別隸屬度。尤其當隨機測試樣本x對每個類別的隸屬度存在較大差別時，這樣做是非常必要的。

設ρi為隨機測試樣本x屬于類i的概率，把它和類i對應的分離測度結合在一起，得到一個帶有隨機測試樣本隸屬度的分離測度序列{(sm1，ρ1，(sm2，ρ2)，…，(smk，ρk)}，并設類i的分離測度：smi=minj=1，2，…，k，j≠i(ρismij)。對于非線性可分問題，同樣可以把新定義的分離測度推廣到特征空間H中，此時smHi=minj=1，2，…，kj≠i(ρismHij)。

下面使用本文給出的隸屬度分離測度對SVM決策樹的層次結構進行設計，并給出相應的SVM決策樹多分類算法。為了便于算法描述，設在各樹節點生成的決策函數是將一類與其余類分開。假設要進行k類分類，訓練樣本集X由類Xi（i=1，2，…，k）組成，基于隸屬度分離測度的SVM決策樹的算法設計如下：

a)計算特征空間中類i與其他每一個類的類間分離測度;

b)計算類i的隸屬度分離測度，并對所有類別按隸屬度分離測度從大到小進行排序;

c)選擇當前類集合X中最易分的類，假設類號為s;

d)將當前最易分的類與剩余類分開，即訓練SVM，得到最優判別函數，構成樹節點;

e) X=X-Xs，k=k-1;

f)若k＞1，轉c);否則，結束。

4仿真實驗

用Iris標準數據集中的一部分進行仿真實驗。實驗樣本集X包含174個樣本。其中類1包含的樣本數為24，類2包含的樣本數為60，類3包含的樣本數為90。實驗分三次進行，每次隨機選取每類樣本數的2/3作為訓練集，剩余的作為測試集，訓練SVM決策樹在相同的條件下進行，分類精度取三次實驗的平均值。用ni表示類i包含的樣本數目;n表示數據集X包含的樣本數目。在這里，取ρi=ni/n對傳統的SVM決策樹與本文改進的SVM決策樹從分類精度和分類時間上進行了比較，結果如表1所示。

5結束語

現有的分離測度大多只考慮了訓練樣本集的類空間分布，本文從訓練樣本的類空間分布和隨機測試樣本對每個類別的隸屬度兩方面考慮，對現有分離測度進行了改進，給出了一種帶隸屬度的分離測度，并用這種分離測度設計SVM決策樹的層次結構。實驗表明，對于隨機測試樣本屬于每個類別的概率均不相同的多類分類問題，基于隸屬度分離測度的SVM決策樹在與傳統的SVM決策樹具有基本相同的分類準確率情況下，具有更快的分類速度。 如何針對實際問題設計出更加合理、有效劃分各級子類的方法，是下一步的研究方向。

參考文獻：

［1］VAPNIK V N. The nature of statistical learning theory[M].New York:Springer， 1999.

[2]WESTON J， WATKINS C. Support vector machines for multiclass pattern recognition[C]//Proc ofthe 7th European Symposium on Artificial Neural Networks. Brussels:[s.n.]， 1999:219-224.

[3]KREBEL U. Pairwise classification and support vector machines[C]//Advance in Kernel Methods. Cambridge:MIT Press， 1999:255-268.

[4]DIETTERICH T G， BAKIRI G. Solving multiclass learning problem via errorcorrecting output codes[J].Journal of Artificial Intelligent Research， 1995(2):263-286.

[5]PLATT J C， CRISTIANINI N， TAYLOR J S. Large margin DGAs for multiclass classification advances in neural information[C]//Advances in Neural Information Processing System. Cambridge:MIT Press，2000:547-553.

[6]GUO G D， LI S E， CHAN K. Face recognition by support vector machines[C]//Proc of the International Conferences on Automatic Face and Gesture Recognition.2000：196-201.

[7]TAKAHASHI F， ABE S. Decisiontreebased multiclass support vector machines[C]//Proc of the 9th International Conference on Neural InformationProcessing. Singapore:IEEE Press， 2002:1419-1422.

[8]史朝輝，王曉丹，趙士敏，等. 改進的SVM決策樹分類算法[J].空軍工程大學學報：自然科學版， 2006，7(2):32-35.

[9]趙暉，榮麗麗，李曉.一種設計層次支持向量機多類分類器的新方法[J].計算機應用研究，2006，23(6):34-37.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”