張加建

【摘 要】支持向量機算法是90年代由 Vapnik 等人在統(tǒng)計學習理論的基礎上提出的一種新式的機器學習算法，由于其卓越的學習能力，尤其是泛化能力，從而引起了人們對這一領域的極大關注。傳統(tǒng)支持向量機是做二元分類的，而現(xiàn)實中更多的是多類分類?，F(xiàn)有的多類分類算法中，二叉樹支持向量機整體性能優(yōu)于“一對一”、“一對多”等其它多類分類方法，但是二叉樹支持向量機由于存在“差錯積累”問題，使得分類準確率較低。本文針對二叉樹支持向量機分類精度較低的缺點，將模糊支持向量機與二叉樹支持向量機相結合，將模糊技術應用到支持向量機中，從而提高了分類準確率。

【關鍵詞】支持向量機；二叉樹；模糊理論

【Abstract】The support vector machine algorithm based on statistical learning theory is a new kind of machine learning algorithm proposed by Vapnik et al， Because of its excellent learning performance， especially the generalization ability， it has aroused great concern in this field. Traditional support vector machine is to do two yuan classification， and more in fact is a multi class classification. Existing multi class classification method， the binary tree support vector machine overall performance is better than that of “a”， “a pair of many” other multi class classification method， but binary tree support vector machine due to the presence of “error accumulation” problem， the classification accuracy rate is low. In this paper， for binary tree support vector machine classification accuracy lower shortcomings， fuzzy support vector machine and the binary tree support vector machine and the fuzzy techniques are applied to support vector machine ， so as to improve the classification accuracy.

【Key words】Support vector machine； Binary tree； Fuzzy theory

0 引言

支持向量機（support vector machine，SVM）是在統(tǒng)計學習理論[1]的基礎上發(fā)展起來的一種新的學習算法，是 AT&T Bell 實驗室的 Vapnik 等[2]人在90年代提出來的針對分類和回歸問題的新型機器學習算法。統(tǒng)計學習理論是一種在小樣本情況下研究其規(guī)律的機器學習算法，支持向量機作為一種近幾年發(fā)展起來的數(shù)據挖掘技術，由于它基于結構風險最小化原則，能有效地避免過學習問題，具有良好的泛化能力[1]。這些優(yōu)良特性使支持向量機成為了繼神經網絡、模式識別之后的又一研究熱點。最有代表性的是美國郵政手寫數(shù)字庫識別研究成功地應用了支持向量機[3]，在其它應用領域，比如人臉檢測與識別[4]、文本分類[5]、回歸分析[6]等方面也取得了許多研究成果。

支持向量機算法是近幾年研究分類問題較為典型的方法，它提供了一種實現(xiàn)自動、主動學習分類的途徑。在實際應用中，多類分類問題更加常見，對于支持向量機多類分類方法的研究具有很大的實際應用價值，是支持向量機研究中的重要方向。在多類分類問題中，常見的“一對一”和“一對多”算法存在不可識別區(qū)域，訓練速度慢，分類效率不高等缺點。二叉樹支持向量機多類分類方法的主要優(yōu)點是需要訓練的支持向量機數(shù)目和各支持向量機的訓練樣本數(shù)目都較少，并且分類時也不必遍歷所有的支持量機分類器，具有較高的訓練速度和分類速度，對于類別數(shù)目多的分類問題，它具有更大的優(yōu)勢[7]。但是，二叉樹支持向量機存在“差錯積累”問題，使得分類準確率較低。針對這一問題，將模糊支持向量機與二叉樹支持向量機相結合，將模糊理論應用于支持向量機中，對每個樣本采用不同的懲罰系數(shù)，從而在構造目標函數(shù)時，不同的樣本存在不同的貢獻值，對含有噪聲或野值的樣本點賦予較小的懲罰系數(shù)，從而降低噪聲與野值點的影響，以此來提高分類準確率。

1 二叉樹支持向量機

二叉樹支持向量機[8]（Binary tree support vector machine， BT-SVM）是先將全部類別劃分為兩個子類，然后又將之前的每個子類劃分為兩個子類，循環(huán)下去，直到劃分出最終類別時停止。通過這種方法將一個多分類問題變成了求解多個二分類問題，在每個節(jié)點處采用二分類支持向量機進行機器學習，并且每學習一次，二分類問題的規(guī)模隨之下降。圖1描述了一個五分類問題的一種二叉樹結構圖，其它的二叉樹結構與之類似。

在生成二叉樹的過程中， 應該讓最容易分割的類提前分割出來，基于這種思想，有兩種構造二叉樹的方法。類距離法：其基本思想是讓與其他類相隔最遠的類先分離出來，此時構造的超平面具有良好的推廣性；空間分布法：根據訓練樣本在屬性空間的幾何分布情況來生成二叉樹的方法。分割的順序不一樣，每個類的分割區(qū)域也是不同的，先分割出來的類更容易有較大的分割區(qū)域，為了讓一個范圍分布廣的類有更大的分割區(qū)域， 它應該第一個被分離出來。

二叉樹支持向量機解決了傳統(tǒng)的支持向量機存在的不可分區(qū)域問題，將一個k類分類問題轉化為求解k-1個二分類問題，減少了問題規(guī)模，當測試遍歷二叉樹時，沒有必要計算所有的分類判別函數(shù)，從而提高了分類速度。但是二叉樹支持向量機存在“差錯積累”問題，使得分類準確率較低[2]，如何提高其的分類準確率，是亟待解決的問題。

2 模糊支持向量機

傳統(tǒng)的支持向量機所能解決的是訓練集是一般集合的情形。但是，現(xiàn)實世界存在大量的不確定信息，即模糊信息，如果支持向量機的訓練集中含有模糊信息，那么傳統(tǒng)的支持向量機分類將出現(xiàn)差錯，所以人們提出了模糊支持向量機[9]的概念，來進一步完善支持向量機多類分類方法及滿足解決實際問題的需要。模糊支持向量的主要思想是：針對噪音和孤立點對支持向量機分類的影響，在支持向量機中引入模糊參數(shù)，以此來減弱噪音及孤立點對分類造成的影響。

3 模糊二叉樹支持向量機

由于二叉樹支持向量機存在“差錯積累”問題，我們可以在每個二分類處用一個模糊支持向量機來確定最優(yōu)分解面。使用模糊支持向量機可以在保證既定的分類器結構下，通過隸屬度函數(shù)有效減少孤立點和噪聲的影響，提高分類的準確性。具體分類過程如下：

（1）令初始狀態(tài)只含有一個類（X），其中X為訓練樣本的集合；

（2）采用基于類距離法的模糊二叉樹支持向量機，將距離最遠的類先分離出來，如果只含有一個類，則將其標志為與初始類相同，學習算法結束，否則轉第（3）步。

（3）標志新的兩類X■■和X■■為初始決策集，將輸入樣本的子集的隸屬度分別計算，并使用模糊支持向量機的學習算法，以獲得最佳的決策節(jié)點的分類面；

4 仿真實驗

將模糊支持向量機算法應用于酒類分類中，本次實驗的酒類數(shù)據是從UCI下載的5種酒類178*13的數(shù)據，將前100個數(shù)據作為訓練集，后78個數(shù)據作為測試集，采用Libsvm_3.21實驗平臺進行實驗。對二叉樹支持向量機和模糊二叉樹支持向量機的分類準確率進行比較如下：

上述實驗數(shù)據表明，模糊二叉樹支持向量機在數(shù)據分類上優(yōu)于二叉樹支持向量機，由此可見，模糊二叉樹支持向量機是一種切實可行的多類分類算法。

【參考文獻】

[1]鄧乃揚，田英杰.支持向量機一理論、算法與拓展[M].北京：科學出版社，2009：115-132.

[2]Cortes C， Vapnik V. Support-vector networks[J]. Machine Learning， 1995， 20（3）：273-297.

[3]Schrlkopf B.， Williamson R.，and Shawe-Taylor J. Single-class support vector machines[C].Unsupervised Learning， Dagstuhl Semianr Report 235， 1999： 19-20.

[4]Osuna E.，F(xiàn)reund R， Girosi F. An improved training algorithm for support vector machine[C]. Proceedings of 1997 IEEE workshop on neural networks for signal processing. Amelea Island， 1997： 276-285.

[5]Ostma E.，F(xiàn)reund R， Girosi F. Training support vector machines： An application to face detection[C]. Proceedings of CVPR， 97. NY， 1997： 130-136.

[6]馬潛云，張學工.支持向量機函數(shù)擬合在分形插值中的應用[N].清華大學學報（自然科學版），2000，40（3）：76-78，103.

[7]孟媛媛.模糊支持向量機的研究與應用[D].濟南：山東師范大學，2006.

[8]孟媛媛，劉希玉.一種新的基于二叉樹的 SVM 多類分類方法[J].計算機應用，2005，25（11）：2653-2657.

[9]楊志民.模糊支持向量機及其應用研究[D].北京：中國農業(yè)大學，2005.

[責任編輯：朱麗娜]