模糊二叉樹支持向量機(jī)算法研究

張加建

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

【關(guān)鍵詞】支持向量機(jī)；二叉樹；模糊理論

【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 引言

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

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

1 二叉樹支持向量機(jī)

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

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

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

2 模糊支持向量機(jī)

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

3 模糊二叉樹支持向量機(jī)

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

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

（2）采用基于類距離法的模糊二叉樹支持向量機(jī)，將距離最遠(yuǎn)的類先分離出來，如果只含有一個(gè)類，則將其標(biāo)志為與初始類相同，學(xué)習(xí)算法結(jié)束，否則轉(zhuǎn)第（3）步。

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

4 仿真實(shí)驗(yàn)

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

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

【參考文獻(xiàn)】

[1]鄧乃揚(yáng)，田英杰.支持向量機(jī)一理論、算法與拓展[M].北京：科學(xué)出版社，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]馬潛云，張學(xué)工.支持向量機(jī)函數(shù)擬合在分形插值中的應(yīng)用[N].清華大學(xué)學(xué)報(bào)（自然科學(xué)版），2000，40（3）：76-78，103.

[7]孟媛媛.模糊支持向量機(jī)的研究與應(yīng)用[D].濟(jì)南：山東師范大學(xué)，2006.

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

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

[責(zé)任編輯：朱麗娜]