摘要：支持向量機（Support Vector Machine， SVM）是一種基于統(tǒng)計學(xué)習(xí)理論的機器學(xué)習(xí)方法，由于其出色的學(xué)習(xí)性能，早已成為當(dāng)前機器學(xué)習(xí)界的研究熱點；而決策樹是一種功能強大且相當(dāng)受歡迎的分類和預(yù)測工具。本文重點介紹支持向量機與決策樹結(jié)合解決多分類問題的算法，并對其進行評析和總結(jié)。

關(guān)鍵詞：支持向量機；決策樹；多分類；SVMDT

中圖法分類號：TP39文獻標識碼：A 文章編號：1009-3044(2008)08-10ppp-0c

1 引言

基于數(shù)據(jù)的機器學(xué)習(xí)是現(xiàn)代智能技術(shù)中的重要方面。通過對已知事實的分析總結(jié)出規(guī)律，預(yù)測不能直接觀測的事實，即利用學(xué)習(xí)得到的規(guī)律，不但可以較好地解釋已知的實例，而且能夠?qū)ξ磥憩F(xiàn)象或無法觀測的現(xiàn)象做出正確的預(yù)測和判斷，我們把這種能力叫做推廣能力。在人們對機器智能的研究中，一直希望能夠用機器（計算機）來模擬這種學(xué)習(xí)能力，就是我們所說的基于數(shù)據(jù)的機器學(xué)習(xí)，或簡單的稱為機器學(xué)習(xí)問題 。機器學(xué)習(xí)這門學(xué)科所關(guān)注的問題是：計算機程序如何隨著經(jīng)驗積累自動提高性能 。統(tǒng)計學(xué)在解決機器學(xué)習(xí)問題中起著基礎(chǔ)性的作用。傳統(tǒng)統(tǒng)計學(xué)研究的是樣本數(shù)目趨于無窮大時的漸近理論 ，現(xiàn)有的學(xué)習(xí)方法也多是基于此假設(shè)。但在實際問題中，樣本數(shù)往往是有限的，因此一些理論上很優(yōu)秀的學(xué)習(xí)方法實際中表現(xiàn)卻可能不盡人意。與傳統(tǒng)統(tǒng)計學(xué)相比，統(tǒng)計學(xué)習(xí)理論(Statistical Learning Theory，SLT)是一種專門研究小樣本情況下機器學(xué)習(xí)規(guī)律的理論 。Ｖ.Vapnik 等人從六、七十年代開始致力于此方面研究，為解決有限樣本學(xué)習(xí)問題提供了一個統(tǒng)一的框架；同時，在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)上發(fā)展了一種新的通用學(xué)習(xí)方法——支持向量機(Support Vector Machine，SVM)3，它已初步表現(xiàn)出很多優(yōu)于已有方法的性能。曾有學(xué)者認為，SLT和SVM 正成為繼神經(jīng)網(wǎng)絡(luò)研究之后新的研究熱點，并將有力地推動機器學(xué)習(xí)理論和技術(shù)的發(fā)展。

決策樹通過把樣本從根結(jié)點排列到某個葉子結(jié)點來分類，葉子結(jié)點即為樣本所屬的分類類別。其思路是找出最有分辨力的屬性，把樣本集劃分為許多子集（對應(yīng)樹的一個分枝），構(gòu)成一個分枝過程，然后對每一個子集遞歸調(diào)用分枝過程，直到所有子集包含同一類型的樣本。最后得到的決策樹能對新的樣本進行分類。

本文通過對支持向量機在多分類方面的推廣，引入決策樹的研究，闡述SVM與決策樹相結(jié)合解決多分類問題的方法。本文內(nèi)容安排如下：第二節(jié)支持向量機，概述支持向量機，探討SVM在多分類方面的推廣，分析現(xiàn)有算法；第三節(jié)決策樹的研究，介紹決策樹的歷史與發(fā)展；第五節(jié)支持向量機決策樹，重點討論將SVM與決策樹結(jié)合的算法；最后總結(jié)。

2 支持向量機相關(guān)介紹

2.1 支持向量機（Support Vector Machine，SVM）

V. Vapnik提出的支持向量機理論因其堅實的理論基礎(chǔ)和諸多良好特性在近年獲得了廣泛的關(guān)注。已經(jīng)有許多事實證明，作為支持向量機最基本思想之一的結(jié)構(gòu)化風(fēng)險最小化原則（Structural Risk Minimization， SRM ）要優(yōu)于傳統(tǒng)的經(jīng)驗風(fēng)險最小化原則（Empirical Risk Minimization， ERM）。不同于ERM試圖最小化訓(xùn)練集上誤差的做法，SRM試圖最小化VC維的上界，從而使其學(xué)習(xí)機獲得了更好的推廣性能，這恰恰是統(tǒng)計學(xué)習(xí)理論最重要的目標之一。

SVM的優(yōu)勢在于其方法是建立在統(tǒng)計學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜性(即對特定訓(xùn)練樣本的學(xué)習(xí)精度，Accuracy)和學(xué)習(xí)能力(即無錯誤地識別任意樣本的能力)之間尋求最佳折衷，以期獲得最好的推廣能力(Generalizatin Ability) 2。支持向量機方法的幾個主要優(yōu)點是：可以解決小樣本情況下的機器學(xué)習(xí)問題；可以提高泛化性能；可以解決高維問題；可以解決非線性問題；可以避免神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)選擇和局部極小點問題 。

2.2 多類支持向量機

然而，最初研究的SVM是用來解決二分類問題，并不能直接運用在多分類方面，如何有效地將其推廣到多類分類問題還是一個正在研究的問題。當(dāng)前已經(jīng)有算法將SVM推廣到多類分類問題，這些算法統(tǒng)稱為“多類支持向量機”(Multi-Category Support Vector Machines，M-SVMs) 。它們可以大致分為兩大類：其一，是Weston 在1998年提出的基于改進目標函數(shù)的多類分類算法，即將多個分類面的參數(shù)求解合并到一個最優(yōu)化問題中，通過求解該最優(yōu)化問題“一次性”地實現(xiàn)多類分類；其二，通過某種方式構(gòu)造一系列的兩類分類器并將它們組合在一起來實現(xiàn)多類分類。第一類方法盡管看起來簡潔，但是在最優(yōu)化問題求解過程中的變量遠遠多于第二類方法，訓(xùn)練速度不及第二類方法，而且在分類精度上也不占優(yōu)勢。當(dāng)訓(xùn)練樣本數(shù)非常大時，這一問題更加突出。正因如此，第二類方法更為常用。這類方法目前主要有四種分支算法：1對多算法、1對1算法、DAGSVM有向無環(huán)圖以及ECOC糾錯碼。

這些方法雖然具有理論依據(jù)，但存在一個最優(yōu)化問題，導(dǎo)致在訓(xùn)練過程中會耗費大量的時間，所以并沒有得到很好的應(yīng)用，只有1對1算法和DAGSVM有向無環(huán)圖在實際中應(yīng)用較多。由于1對多SVMs和1對1 SVMs對未知樣本分類時需要使用所有的分類器，且分類結(jié)果與分類器使用順序無關(guān)，因此它們的組合方式是唯一的。DAGSVM中的有向無環(huán)圖的組合方式有很多種，但實驗證明組合變化對分類結(jié)果影響不大。并且DAGSVM和ECOC的測試次數(shù)至少是N次，所以當(dāng)類別很多時將不能很好的應(yīng)用。

同時，在將多類問題轉(zhuǎn)化為兩類問題求解時，往往會出現(xiàn)無法分類區(qū)(未知區(qū)或重疊區(qū))，可以用一個簡單的三類例子來說明，如圖1所示。圖1(a)中使用1對多算法分類，每次判定全部樣本集中的模式屬于或不屬于某一類；圖1(b)中采用1對1算法分類，每次只取樣本集中兩類模式樣本進行分類。這兩種方法都會產(chǎn)生圖1(a)、 圖1(b)所示的陰影區(qū)，在這個區(qū)域中的模式樣本，要么無法確定它們的類別，要么屬于多個類別，總之，無法將其唯一判至某類，從而出現(xiàn)拒識。

圖1 無法分類區(qū)域示意圖

3 決策樹簡介

決策樹起源于概念學(xué)習(xí)系統(tǒng)（Concept Learning System，CLS）的研究 ，但CLS的不足是它處理的學(xué)習(xí)問題不能太大。為此，20世紀70年年代末期Quinlan 提出了著名的ID3學(xué)習(xí)算法，它采用信息增益作為啟發(fā)策略，通過選擇窗口來形成決策樹 。ID3算法的核心是：在決策樹各級結(jié)點上選擇屬性時，用信息增益（information gain）作為屬性的選擇標準，以使得在每一個非葉結(jié)點進行測試時，能獲得關(guān)于被測試記錄最大的類別信息。其具體方法是：檢測所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點，由該屬性的不同取值建立分支，再對各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點的分支，直到所有子集僅包含同一類別的數(shù)據(jù)為止。最后得到一棵決策樹，它可以用來對新的樣本進行分類，如圖2所示。ID3算法的優(yōu)點是：算法的理論清晰，方法簡單，學(xué)習(xí)能力較強。其缺點是：只對比較小的數(shù)據(jù)集有效，且對噪聲比較敏感，當(dāng)訓(xùn)練數(shù)據(jù)集加大時，決策樹可能會隨之改變。

圖2 一棵判斷星期六上午是否適合打網(wǎng)球的樹

在Quinlan提出ID3的同時，Breiman和Friedman開發(fā)出分類與回歸樹（Classification And Regression Tree ， CART），方法類似于ID3。80年代末，對噪聲、連續(xù)屬性、數(shù)據(jù)缺失、改善分割條件等進行研究，相繼于1986年，Schlimmer 和Fisher 設(shè)計了ID4 遞增式學(xué)習(xí)算法；1988年 Paul E. Utgoff 在前者基礎(chǔ)上提出ID5 。

在1993年Quinlan又再次提出改進決策樹歸納包C4.5 ，目前被普遍采用。C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進行了改進：用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；在樹構(gòu)造過程中進行剪枝；能夠完成對連續(xù)屬性的離散化處理；能夠?qū)Σ煌暾麛?shù)據(jù)進行處理。

C4.5與CART之間的差異有兩點：1) 首先CART在每一個節(jié)點都呈現(xiàn)二分法，因此產(chǎn)生二分式?jīng)Q策樹，而C4.5則在每一個節(jié)點產(chǎn)生不同數(shù)目的分支。這是因為C4.5對持續(xù)性變項的處理方式和CART相當(dāng)相似，但對類別變項的處理就相當(dāng)不同。2) 在修剪決策樹方面，CART使用決策樹的分散度為度量，來標記不同的分支樹，然后以沒有見過的預(yù)先分類好的資料（測試組）來測試這些分支樹。相反，C4.5并不參考其他資料，而是嘗試以只用訓(xùn)練資料的情況下來修剪決策樹。因此，C4.5使用構(gòu)建決策樹相同的資料來決定該如何加以修剪。

另外，C4.5算法與其它分類算法如統(tǒng)計方法、神經(jīng)網(wǎng)絡(luò)等比較起來有如下優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準確率較高。其缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。

4 支持向量機決策樹

決策樹雖然應(yīng)用較多，但沒有很好的理論基礎(chǔ)，我們說沒有比一個好的理論更讓人感到欣慰的了；加之支持向量機在解決拒識區(qū)域問題上沒有得到很好的解決，于是國內(nèi)外的一些專家學(xué)者相繼提出了將支持向量機與決策樹相結(jié)合的算法，取得了很好的效果。但我們知道，沒有一種分類方法在對所有數(shù)據(jù)集上進行分類學(xué)習(xí)均是最優(yōu)的，對不同的分類方法都有著許多對比研究成果。

Fumitake Takahashi等人曾在2003年提出基于決策樹的多類支持向量機 ，該算法在訓(xùn)練過程中，對于根節(jié)點，首先將所有類別分成兩個子類，再將子類進一步劃分成兩個次級子類，如此循環(huán)下去，直到所有的節(jié)點都只包含一個單獨的類別為止，這種方法可以克服傳統(tǒng)方法所遇到的不可分問題。但是新的問題又出現(xiàn)了，也即是特征空間的劃分依賴于決策樹的結(jié)構(gòu)，為了獲得高的推廣能力，最容易分割的類應(yīng)該在決策樹的上層節(jié)點中進行分割，基于這個觀點，文中提出了四類基于不同可分割性度量的決策樹：(1)在每一個節(jié)點上從該類別組中分離出一個類，用歐幾里得距離度量最佳可分性：用歐幾里得距離公式計算各類中心間的距離，遞歸分離出與余下所有類中心距離最大的類。(2)在每一個節(jié)點上從該類別組合中分離出多個類，用歐幾里得距離度量最佳可分性：用歐幾里得距離公式計算各類中心間的距離，重復(fù)合并距離最近的類，直到獲得兩個聚類，用超平面分離出這兩個聚類。(3)在每一個節(jié)點上從該類別組中分離出一個類，用Mahalanobis距離度量最佳可分性：用Mahalanobis距離公式計算各類間的距離，超平面能分離出最小錯誤分類。(4)在每一個節(jié)點上從該類別組合中分離出多個類，用Mahalanobis距離度量最佳可分性：用Mahalanobis距離公式計算各類間的距離，重復(fù)合并兩兩最小錯誤分類。

與此同時，Scott Selikoff等人對新提出的學(xué)習(xí)算法和分類算法進行了闡述 ，將基于樹結(jié)構(gòu)的SVM算法和傳統(tǒng)多分類SVM算法進行了對比，提出應(yīng)該怎樣構(gòu)造合適的SVM樹結(jié)構(gòu)：（1）類別之間有很大的相似性，應(yīng)用中如何處理類別之間的相關(guān)性因素很重要。（2）樹結(jié)構(gòu)多分類SVM和其它幾種多分類SVM的比較。相比1-v-r和1-v-1來講，SVM-Tree有如下兩個優(yōu)點：(1)1-v-r需要構(gòu)造n個二叉SVMs，1-v-1需要構(gòu)造n(n-1)/2個二叉SVMs，Tree-SVM構(gòu)造(n-1)個SVMs。(2)在不考慮并行情況下SVM-Tree的分類速度較快一些。

之后，Jin-Seon Lee等人也提出了一種二叉分類樹解決多類分類問題 ，樹的構(gòu)造方式是在一個節(jié)點上把該類分割為兩個子類；類分割實際上是個最優(yōu)化問題。該文提出了一種新的二叉分類樹，樹設(shè)計方式如下：用節(jié)點的二分類器將所有類別分成兩個不同的子類，再用和父節(jié)點一樣的二分類器將子類進一步劃分成兩個次級子類，為了獲得高的分類準確性，怎樣獲得最好的分類實際上是個最優(yōu)化問題，可以利用遺傳算法尋找最好的分類同樣的處理如此循環(huán)下去，直到所有的節(jié)點都只包含一個單獨的類別為止。經(jīng)過數(shù)字識別的實驗，在分類準確性和時間效率方面，基于二叉分類樹的分類相對于傳統(tǒng)的分類方式有明顯提高。

此外，國內(nèi)的很多學(xué)者也對決策樹多分類這方面也提出了自己的觀點，如唐發(fā)明，王仲東等人在2005年采用聚類分析中的類距離思想 ，利用最短距離法（如下圖）進行聚類分析，讓與其他類相隔最遠的類最先分割出來，此時構(gòu)造的最優(yōu)超平面也應(yīng)具有較好的推廣性。

圖3 類距離法示意圖

5 總結(jié)

目前支持向量機已經(jīng)得到普遍的認識和廣泛的應(yīng)用，而決策樹算法也已經(jīng)有了廣泛的應(yīng)用， 并且有了許多成熟的系統(tǒng)， 這些系統(tǒng)廣泛應(yīng)用于各個領(lǐng)域， 如語音識別， 模式識別， 專家系統(tǒng)等。但是， 解決一個復(fù)雜的數(shù)據(jù)挖掘問題的任何算法都要面臨以下問題： 從錯誤的數(shù)據(jù)中學(xué)習(xí)、從分布的數(shù)據(jù)中學(xué)習(xí)、從有偏的數(shù)據(jù)中學(xué)習(xí)、學(xué)習(xí)有彈性的概念、學(xué)習(xí)那些抽象程度不同的概念、整合定性與定量的發(fā)現(xiàn)等， 歸納學(xué)習(xí)當(dāng)中還有很多未開發(fā)的課題等待我們?nèi)パ芯俊?/p>

并且我們始終要牢記一點，沒有一個分類方法在對所有數(shù)據(jù)集上進行分類學(xué)習(xí)均是最優(yōu)的，所以怎樣使得算法盡可能的提高訓(xùn)練速度，減少分類錯誤，增加泛化性能是我們下一步的工作。

參考文獻：

[1]V.Vapnik，著.張學(xué)工，譯.統(tǒng)計學(xué)習(xí)理論的本質(zhì)[M].北京:清華大學(xué)出版社，2000.

[2]Tom M.Mitchell，著.曾花軍，張銀奎，等.譯.機器學(xué)習(xí)[M].北京:機械工業(yè)出版社，2003.

[3]V.Vapnik，著.許建華，張學(xué)工，譯.統(tǒng)計學(xué)習(xí)理論[M].北京:電子工業(yè)出版社，2004.

[4]張學(xué)工.關(guān)于統(tǒng)計學(xué)習(xí)理論與支持向量機[J].自動化學(xué)報，2000，26(1):32-42．

[5]張浩然，汪曉東.支持向量機的學(xué)習(xí)方法綜述[J].浙江師范大學(xué)學(xué)報（自然科學(xué)版），2005，28(3):283-287.

[6]劉志剛，李德仁，秦前清，等.支持向量機在多類分類問題中的推廣[J].計算機工程與應(yīng)用，2004，40(7):10-13.

[7]Weston J，Watkins C.Multi-class support vector machines. Royal Holloway College， Tech Rep: SCD-TR-98-04，1998.

[8]Earl B．Hunt， Janet Marin， Philip J．Stone. Experiments in Induction[M].Academic Press，New York，1966.

[9]J.Ross Quinlan.Induction of decision trees[J].Machine Learning，1986，(1):81-106.

[10]Paul E，Utgoff.Incremental induction of decision trees[J]Machine Learning，1989，4(2):161-186.

[11]J.Ross Quinlan. C4.5: Programs for Machine Learning[M].Academic Press，New York，1993.

[12]Fumitake Takahashi，Shigeo Abe. Decision-Tree-Based Multi-class Support Vector Machines [A].Proceeding of ICONIP'02[C]， Singapore:IEEE Press，2002.1419-1422.

[13]Scott Selikoff，The SVM-Tree Algorithm: A New Method for Handling Multi-Class SVMs. Cornell University，2003.

[14]Jin-Seon Lee， II-Seok Oh. Binary classification trees for multi-class classification prooblems[M].IEEE， 2003: 770-774.

[15]唐發(fā)明，王仲東，陳綿云.一種新的二叉樹多類支持向量機算法[J].計算機工程與應(yīng)用，2005，41(7):24-26.