支持向量機(jī)與哈夫曼樹實(shí)現(xiàn)多分類的研究

滕少華，胡 俊，張 巍，劉冬寧

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣東廣州510006)

0 引言

分類是人們認(rèn)識(shí)事物的基礎(chǔ)，人們認(rèn)識(shí)事物時(shí)往往先把被認(rèn)識(shí)的對(duì)象進(jìn)行分類，以便尋找其中同與不同的特征，因而分類學(xué)是人們認(rèn)識(shí)世界的基礎(chǔ)科學(xué)［1］.對(duì)于分類，人們已開展了大量研究，目前主要的分類方法包括貝葉斯分類器、決策樹(DT，decision tree)、支持向量機(jī)(SVM，support vectormachine)、K近鄰(KNN)等，其中SVM在分類中體現(xiàn)了突出的優(yōu)勢(shì)，并取得了大量的研究成果，已經(jīng)在很多領(lǐng)域得到廣泛應(yīng)用，如在回歸學(xué)習(xí)、入侵檢測(cè)［2-3］、文本分類、手寫識(shí)別、圖像分類、生物信息學(xué)等領(lǐng)域［4］.

支持向量機(jī)是建立在統(tǒng)計(jì)學(xué)習(xí)理論VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上的機(jī)器學(xué)習(xí)方法，在解決分類預(yù)測(cè)問題上有突出的優(yōu)點(diǎn)，尤其適合于解決小樣本、非線性和高維模式識(shí)別問題，并在很大程度上克服了“維數(shù)災(zāi)難”和“過學(xué)習(xí)”等問題［4］.標(biāo)準(zhǔn)的支持向量機(jī)學(xué)習(xí)算法可以歸結(jié)為求解一個(gè)受約束的2 次型規(guī)劃(QP，quadratic programming)問題［5］.隨著訓(xùn)練數(shù)據(jù)集規(guī)模增大，將出現(xiàn)訓(xùn)練速度慢、效率降低、算法復(fù)雜等問題.通常的訓(xùn)練算法是將原有大規(guī)模的QP問題分解成一系列小的QP問題，按照某種迭代策略，反復(fù)求解小的QP問題，構(gòu)造出原有大規(guī)模的QP問題的近似解，并使該近似解逐漸收斂到最優(yōu)解.但是如何對(duì)大規(guī)模的QP問題進(jìn)行分解以及如何選擇合適的工作集是當(dāng)前訓(xùn)練算法所面臨的困難，也是各個(gè)算法優(yōu)劣之所在.

本文嘗試使用SVM和DT解決上述問題.通過構(gòu)建一種基于支持向量機(jī)和決策樹的多分類器，將一個(gè)大的多分類問題分解成多個(gè)小的2分類問題，然后利用2分類SVM一一解決，最終解決搜索所帶來的多分類問題.決策樹的每個(gè)非葉子結(jié)點(diǎn)是一個(gè)2分類SVM分類器，葉子結(jié)點(diǎn)對(duì)應(yīng)所有類別，分類路徑到達(dá)葉子結(jié)點(diǎn)，表明本次分類結(jié)束.本文提出訓(xùn)練模型的構(gòu)造過程是自下而上的，以此構(gòu)造的分類模型具有減少錯(cuò)誤積累、避免局部最優(yōu)解、平衡錯(cuò)誤和分類速度快等優(yōu)點(diǎn).

1 支持向量機(jī)與分類

1.1 支持向量機(jī)

支持向量機(jī)是一種建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上的數(shù)據(jù)挖掘方法，能處理回歸(時(shí)間序列分析)和模式識(shí)別(分類問題、判別分析)等諸多問題，可推廣到預(yù)測(cè)和綜合評(píng)價(jià)等領(lǐng)域［4］.SVM的分類原理是尋找一個(gè)滿足分類要求的最優(yōu)分類超平面，使得該超平面在保證分類精度的同時(shí)，能夠使其分類間隔最大化.

以2類數(shù)據(jù)分類為例，對(duì)于線性可分，給定訓(xùn)練樣本集(xi，yi)，i=1，2，3，…，l，x∈Rn，y∈{±1}，超平面記作(w·x)+b=0，為使分類面對(duì)所有樣本正確分類并且具備分類間隔，就要求它滿足約束

為了解決這個(gè)約束最優(yōu)化問題，引入Lagrange函數(shù)來實(shí)現(xiàn)對(duì)偶變量的優(yōu)化求解，最終得到最優(yōu)分類超平面(w*·x)+b*=0，其中w*是最優(yōu)權(quán)值向量，b*是最優(yōu)偏置，而最優(yōu)分類函數(shù)為

對(duì)于線性不可分情況，SVM的主要思想是將輸人向量映射到一個(gè)高維的特征向量空間，并在該特征空間中構(gòu)造最優(yōu)分類面.將x從輸入空間Rn到特征空間H的變換φ，得:x→φ(x)以特征向量φ(x)代替輸入向量x，則可以得到最優(yōu)分類函數(shù)為

為了避免直接在高維空間中進(jìn)行計(jì)算，引入核函數(shù)機(jī)制，其中K(xi，x)為核函數(shù)，上式變換為

1.2 多分類支持向量機(jī)

SVM本質(zhì)上是2值分類，最初是針對(duì)2類分類問題提出的，不能直接用于多分類問題，而在實(shí)際應(yīng)用中，往往需要解決多類分類問題，通常采用“分治”策略，即將多分類問題分解成多個(gè)2分類問題，然后構(gòu)造一系列SVM 2值分類器與它們對(duì)應(yīng).目前主要有一對(duì)多、一對(duì)一、SVM決策樹等方法，前兩者分別需要構(gòu)造N和N(N-1)/2個(gè)分類器.而SVM決策樹方法是將SVM和二叉決策樹結(jié)合起來，僅需要構(gòu)造N-1個(gè)SVM分類器，其分類性能優(yōu)于一對(duì)多和一對(duì)一組合方法［8］.決策樹層次結(jié)構(gòu)的設(shè)計(jì)是影響SVM決策樹多類分類器性能的關(guān)鍵之一.

2 基于哈夫曼樹和SVM的多類分類器

基于SVM和決策樹的多類分類問題轉(zhuǎn)換為構(gòu)造分類模型與應(yīng)用該模型進(jìn)行分類2個(gè)階段，其中構(gòu)造過程是構(gòu)建SVM決策樹模型，分類就是利用該模型對(duì)未知類別的樣本數(shù)據(jù)進(jìn)行類別判斷，或?qū)σ阎悇e的樣本數(shù)據(jù)進(jìn)行預(yù)測(cè)驗(yàn)證.本文分類器應(yīng)用的數(shù)據(jù)是網(wǎng)絡(luò)用戶搜索行為的原始記錄，該數(shù)據(jù)是不規(guī)則的、非數(shù)值的，并且存在噪聲，通過數(shù)據(jù)預(yù)處理將其轉(zhuǎn)化規(guī)范的數(shù)據(jù)集，然后劃分為訓(xùn)練集和測(cè)試集兩部分，其中訓(xùn)練集用來構(gòu)造分類模型，測(cè)試集用來實(shí)現(xiàn)分類應(yīng)用.分類器模型如圖1所示.

圖1 分類器模型

2.1 多分類器構(gòu)造過程

分類模型的構(gòu)造過程是自下而上的，如圖2所示，訓(xùn)練從決策樹的葉子結(jié)點(diǎn)出發(fā)，依據(jù)某種決策方法來區(qū)分類間的可分性，每次都將最不好分的2類作為訓(xùn)練樣本的正負(fù)類.訓(xùn)練完畢后，得到的一個(gè)2分類SVM作為決策樹模型的一個(gè)非葉子結(jié)點(diǎn)，合并其對(duì)應(yīng)的正負(fù)2類成為一個(gè)新的類簇(一個(gè)或多個(gè)類組成)［12］，參與下一次訓(xùn)練.如此循環(huán)，直到剩下最后2個(gè)類簇(或類)作為訓(xùn)練的正負(fù)類，訓(xùn)練后得到的2分類SVM作為決策樹的根結(jié)點(diǎn).至此，基于SVM和決策樹的多分類器訓(xùn)練模型構(gòu)造完成.

圖2 分類器的構(gòu)造過程

2.2 多分類器測(cè)試與分類

測(cè)試與分類過程是訓(xùn)練過程的逆過程，自上而下，如圖3所示.首先，從分類模型的根結(jié)點(diǎn)開始，使用根結(jié)點(diǎn)對(duì)應(yīng)的2分類SVM，對(duì)分類樣本進(jìn)行分類預(yù)測(cè);根據(jù)預(yù)測(cè)的中間結(jié)果，分類到達(dá)決策樹的下一層某個(gè)分支結(jié)點(diǎn)，然后使用該結(jié)點(diǎn)對(duì)應(yīng)的2分類SVM對(duì)樣本進(jìn)行分類預(yù)測(cè).重復(fù)此過程，分類最終到達(dá)決策樹的某一個(gè)葉子結(jié)點(diǎn)，該葉子結(jié)點(diǎn)對(duì)應(yīng)的類別就是本次分類的結(jié)果，本次樣本分類結(jié)束.

圖3 多分類器分類過程

測(cè)試過程是構(gòu)造多分類器的一部分，其目的是驗(yàn)證分類器的分類準(zhǔn)確率性能.測(cè)試過程用到的測(cè)試集樣本的分類標(biāo)簽為已知，測(cè)試樣本被分類器分類之后得到的分類標(biāo)簽與已知標(biāo)簽相同時(shí)，表示分類正確，此時(shí)正確分類樣本數(shù)加1.所有樣本測(cè)試結(jié)束之后，分類準(zhǔn)確率=(正確分類樣本數(shù) /測(cè)試集樣本數(shù))×100%.分類過程的樣本分類標(biāo)簽未知，不用求解分類準(zhǔn)確率.

2.3 相異度計(jì)算

SVM分類對(duì)于線性可分，各類樣本間距離反映了它們的可分性.距離越大，越容易正確分類，距離越小，分類誤差越大.對(duì)于訓(xùn)練樣本在原始空間線性不可分的情況，在原始空間直接計(jì)算樣本類間的距離很難反映樣本間的可分性.支持向量機(jī)通過變換核函數(shù)將樣本映射到特征空間，而樣本在特征空間是被視為線性可分的.往往支持向量機(jī)的這種映射是非線性的，不能保證映射前后樣本間的歐氏距離不變，也不能保證距離是成比例變化.因此，能反映可分性的樣本間的距離度量應(yīng)該在特征空間進(jìn)行［12］.

類間相異度是在特征空間計(jì)算的，用來度量2個(gè)類的差別程度，值越大，表示2個(gè)類差別越大越好分;值越小，表示2個(gè)類差別越小越難分.類間相異度矩陣在優(yōu)先選擇最不好分的2類進(jìn)行訓(xùn)練時(shí)，起到了決策作用.

定義 1 給定 N類訓(xùn)練樣本集{X1，X2，…，XN}，其中第i類樣本為，分別為每類的訓(xùn)練樣本構(gòu)造一超球面，得到球面集合，類間相異度矩陣D為

其中Dij為2個(gè)類Xi和Xj之間的相異度，其中i，j=1，2，…，N;dij為Xi的所有樣本到Xj對(duì)應(yīng)超球體中心的平均歐氏距離;Nij(dij)表示Xi中的訓(xùn)練樣本到Xj的超球體中心的歐氏距離大于dij的所有樣本數(shù)量;d(i，j)為 Xi和 Xj的超球體中心之間的歐氏距離;ni、nj分別為Xi和Xj的樣本數(shù).

在(7)式中，Dij表達(dá)式的前半部分(Nij(dij)+Nji(dji))(ni+nj)體現(xiàn)了各類內(nèi)樣本的總體分布情況，該值越大，對(duì)應(yīng)2個(gè)類的樣本趨于分散在2個(gè)類中心的兩邊空間，反之樣本趨于聚集在2個(gè)類對(duì)應(yīng)超球體的中心之間的空間;Dij表達(dá)式的后半部分d(i，j)在一定程度體現(xiàn)了2個(gè)類對(duì)應(yīng)超球體之間的分離特性.歸根到底Dij的值越大，說明Xi和Xj的特征差別越大，即類間分離性越好;反之，2個(gè)類的特征差別越小，越不好分.

分析相異度公式可知，相異度矩陣是對(duì)稱的，減少了一部分計(jì)算時(shí)間.

2.4 基于正態(tài)樹的SVM多分類器

根據(jù)二叉樹的結(jié)構(gòu)，可以將決策樹分為2種類型:偏態(tài)樹和正態(tài)樹［8］，如圖4所示.

圖4 偏態(tài)樹(左)和正態(tài)樹(右)

傳統(tǒng)的基于正態(tài)樹的SVM決策樹多分類方法為了使決策樹的層次最少，以追求最大的平衡錯(cuò)誤效果，采用的是自上而下的訓(xùn)練方式，總是將當(dāng)前認(rèn)為最好分的2類作為優(yōu)先訓(xùn)練的目標(biāo)，這種做法會(huì)產(chǎn)生局部最優(yōu)解，但不一定是整體最好分的目標(biāo)，因此容易進(jìn)入貪心算法的陷阱.另外，為了得到一個(gè)好的訓(xùn)練結(jié)果，首先將整個(gè)訓(xùn)練集劃分為2個(gè)部分，如圖5所示，分離面1分別將類1、類2和類1、類3劃分開來，其中類1對(duì)應(yīng)的樣本集被劃分成了2個(gè)子集，最終導(dǎo)致類1有2條不同的分類路徑.如圖6所示，類1有SVM1→SVM2→類1和SVM1→SVM3→類1共2條分類路徑，相當(dāng)于增加了總的分類路徑，在某種程度上影響了分類速度.

圖5 傳統(tǒng)決策樹分類

圖6 包含重復(fù)路徑的正態(tài)樹

2.5 改進(jìn)的偏態(tài)樹SVM多分類器

為了克服貪心算法的缺點(diǎn)，在此基礎(chǔ)上本文構(gòu)造了以偏態(tài)樹結(jié)構(gòu)為基礎(chǔ)的SVM決策樹多分類器.其思路是，首先計(jì)算N個(gè)類之間的相異度，從決策樹最底層的葉子結(jié)點(diǎn)開始，根據(jù)相異度矩陣，將訓(xùn)練集中相異度最小的2類劃分為正負(fù)類，并且作為決策樹的2個(gè)葉子結(jié)點(diǎn)，進(jìn)行SVM 2值分類，對(duì)應(yīng)的SVM為決策樹的1個(gè)非葉子結(jié)點(diǎn)，將它們合并為1個(gè)新的類簇，作為下一次SVM訓(xùn)練的負(fù)類.然后，重新計(jì)算剩下N-2個(gè)類與該負(fù)類的相異度，選擇與之相異度最小那個(gè)類作為正類，再次進(jìn)行SVM 2值分類.重復(fù)以上過程，直到將原訓(xùn)練集中的所有類別訓(xùn)練結(jié)束，最后一次訓(xùn)練的SVM作為決策樹的根結(jié)點(diǎn).

以偏態(tài)樹結(jié)構(gòu)為基礎(chǔ)的SVM決策樹多分類和傳統(tǒng)的以正態(tài)樹結(jié)構(gòu)為基礎(chǔ)的SVM決策樹多分類在訓(xùn)練過程的區(qū)別是，前者得到的當(dāng)前最不好分的2類是局部最優(yōu)解;后者得到的當(dāng)前最不好分的2類是全局最優(yōu)解.它們都要構(gòu)造N-1個(gè)SVM 2值分類器，其分類都是從根結(jié)點(diǎn)開始，結(jié)束于葉子結(jié)點(diǎn).

對(duì)比圖4和圖5發(fā)現(xiàn)，對(duì)于4類分類問題，基于偏態(tài)樹的多分類模型和基于正態(tài)樹的多分類模型都構(gòu)造了3個(gè)SVM 2值分類器，前者為4層樹，后者為3層樹.在決策樹每層的分類中，若在上層的某個(gè)結(jié)點(diǎn)發(fā)生了分類錯(cuò)誤，則會(huì)把錯(cuò)誤延續(xù)到該結(jié)點(diǎn)后續(xù)的下一層結(jié)點(diǎn)上.尤其離根結(jié)點(diǎn)越近的地方發(fā)生錯(cuò)誤，最終的分類誤差累積越大，若類別N較大時(shí)，這種錯(cuò)誤累積是致命的.為了獲得好的泛化性能，應(yīng)由可分性強(qiáng)的類作為決策樹的上層結(jié)點(diǎn)定義分類子任務(wù).正態(tài)樹能有效的減少?zèng)Q策樹的層數(shù)，因此在構(gòu)建決策樹模型時(shí)，正態(tài)樹結(jié)構(gòu)是優(yōu)先考慮的方法.

2.6 基于哈夫曼樹的SVM構(gòu)建

為此，本文進(jìn)一步改進(jìn)，提出了基于哈夫曼樹的決策樹分類器.

哈夫曼樹定義:給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長(zhǎng)度達(dá)到最小或最大，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman tree).

哈夫曼樹它是由n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹中帶權(quán)路徑長(zhǎng)度最短的二叉樹.哈夫曼算法是一種非貪心算法，實(shí)驗(yàn)證明哈夫曼樹比偏態(tài)及正態(tài)樹分類更優(yōu)越，是相對(duì)更理想的選擇，另外哈夫曼樹采用自下而上的順序構(gòu)造，避免產(chǎn)生1個(gè)類對(duì)應(yīng)多條分類路徑的情況.

以哈夫曼樹結(jié)構(gòu)為基礎(chǔ)的SVM決策樹多分類的訓(xùn)練思路是，首先計(jì)算N個(gè)類之間的相異度矩陣，從決策樹的葉子結(jié)點(diǎn)開始，選擇訓(xùn)練集中相異度最小的2類，進(jìn)行SVM 2值分類訓(xùn)練，對(duì)應(yīng)的SVM為決策樹的1個(gè)非葉子結(jié)點(diǎn).然后，將這2類合并為1個(gè)新的類簇，與剩下的N-2個(gè)類組成包含N-1個(gè)類(或類簇)的訓(xùn)練集.重新計(jì)算這N-1個(gè)類(或類簇)之間的相異度矩陣，再次選擇相異度最小的2類進(jìn)行SVM 2值分類訓(xùn)練.重復(fù)該過程，直到將原訓(xùn)練集中的所有類別訓(xùn)練結(jié)束，最后一次訓(xùn)練的SVM 2值分類器為決策樹分類模型的根結(jié)點(diǎn).

本文中哈夫曼樹結(jié)構(gòu)的帶權(quán)路徑是用類間相異度來度量的.2個(gè)類間相異度越小，說明2個(gè)類的特征越相近，表示這2類越不容易分類，因此優(yōu)先將相異度最小的2個(gè)類合并為1個(gè)類簇，作為決策樹當(dāng)前SVM結(jié)點(diǎn)的訓(xùn)練集.這樣一來，該次訓(xùn)練離決策樹根結(jié)點(diǎn)相對(duì)最遠(yuǎn)，其對(duì)應(yīng)的分類過程產(chǎn)生的誤差積累對(duì)最終分類結(jié)果的影響將減少到最小.具體過程如下:

(i)計(jì)算出訓(xùn)練集中N個(gè)類的類間相異度矩陣.

(ii)根據(jù)類間相異度矩陣，在所有N個(gè)類中選擇Dij最小的2類Xi和Xj，并對(duì)Xi和Xj進(jìn)行2類支持向量機(jī)訓(xùn)煉，構(gòu)建關(guān)于Xi和Xj的2類SVM分類器，作為決策樹的一個(gè)結(jié)點(diǎn).

(iii)將Xi和Xj對(duì)應(yīng)的集合合并作為一個(gè)新的類簇，與剩下的N-2個(gè)類組成包含N-1個(gè)類簇的訓(xùn)練集，計(jì)算出這N-1個(gè)類的相異度矩陣.

(iv)依照上述方法，在剛才得到的N-1個(gè)類簇中選擇類間相異度最小的2個(gè)類進(jìn)行SVM 2分類訓(xùn)練.

(v)重復(fù)以上過程，直到剩下最后2個(gè)類簇，構(gòu)建關(guān)于它們的SVM 2分類器，并將該分類器作為最終決策樹的根結(jié)點(diǎn)，訓(xùn)練結(jié)束后合并2類得到一個(gè)包含所有類的類簇，基于SVM和決策樹的多分類的訓(xùn)練模型構(gòu)建完畢.圖7是構(gòu)建模型過程中訓(xùn)練集的合并過程，每合并一次就有一個(gè)2分類SVM與其對(duì)應(yīng).

對(duì)于N類訓(xùn)練集，每一次訓(xùn)練過程將具有類間最小相異度的2個(gè)類簇進(jìn)行2分類SVM訓(xùn)練，訓(xùn)練得到的SVM作為決策樹的一個(gè)非葉子結(jié)點(diǎn)，參與訓(xùn)練的兩個(gè)類簇合并成一個(gè)新類簇.經(jīng)過N-1次訓(xùn)練后，將得到一個(gè)倒置的最優(yōu)二叉樹，樹中葉子結(jié)點(diǎn)對(duì)應(yīng)的是每個(gè)類，非葉子結(jié)點(diǎn)是2分類SVM，如圖8所示.

圖7 所有類對(duì)應(yīng)樣本集的合并過程

圖8 SVM決策樹多分類器

哈夫曼樹是最優(yōu)二叉樹，其結(jié)構(gòu)特征處于偏態(tài)樹和正態(tài)樹，在此基礎(chǔ)上構(gòu)造一種自下而上的基于SVM的多分類決策樹模型，不但可以避免陷入產(chǎn)生局部最優(yōu)解的貪心算法中，也能夠平衡分類錯(cuò)誤并減少錯(cuò)誤累積，提升總體分類精度和速度.

2.7 基于哈夫曼樹的SVM分類

上一節(jié)構(gòu)建的基于哈夫曼樹的SVM決策樹多分類器中，每一個(gè)非葉子結(jié)點(diǎn)對(duì)應(yīng)一個(gè)SVM 2值分類器，每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)一個(gè)類別.分類從決策樹的根結(jié)點(diǎn)開始，利用每一個(gè)非葉子結(jié)點(diǎn)對(duì)應(yīng)的SVM 2值分類器對(duì)經(jīng)過該結(jié)點(diǎn)的樣本進(jìn)行分類，根據(jù)分類的結(jié)果確定樣本是屬于左子樹還是右子樹，若所屬的子樹剛好為一個(gè)葉子結(jié)點(diǎn)，則本次分類結(jié)束，該葉子結(jié)點(diǎn)對(duì)應(yīng)的類別便是該樣本的最終分類結(jié)果.

3 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)數(shù)據(jù):選自第1屆勒卡斯數(shù)據(jù)挖掘競(jìng)賽［13］提供的第2題數(shù)據(jù)集，該數(shù)據(jù)集是基于搜索關(guān)鍵字的原始數(shù)據(jù)，其中存在一定數(shù)量的噪聲數(shù)據(jù)，經(jīng)過數(shù)據(jù)預(yù)處理之后，本文從中選取了8294條數(shù)據(jù)作為樣本數(shù)據(jù)集，該樣本數(shù)據(jù)集擁有10個(gè)類別，每類包含的樣本數(shù)在500條至1100條之間.將每類樣本數(shù)據(jù)按照3∶1的比例劃分為訓(xùn)練集和測(cè)試集.

本文采用了3種方法進(jìn)行實(shí)驗(yàn)，這3種方法分別為:普通的SVM多分類方法(方法1)、基于偏態(tài)樹的SVM決策樹多分類方法(方法2)和基于哈夫曼樹的SVM決策樹多分類方法(方法3).其中方法1是在matlab環(huán)境下使用libsvm工具包進(jìn)行的，其它方法2、方法3是在VC++6.0中使用libsvm工具包完成的.支持向量機(jī)使用的是RBF核，并且使用了libsvm提供的grid.py和easy.py做了關(guān)于(C，gamma)的交叉驗(yàn)證參數(shù)選擇.表1列出了所有類樣本數(shù)量及3種方法對(duì)應(yīng)各類的實(shí)驗(yàn)結(jié)果.

表1 各類樣本數(shù)量及對(duì)測(cè)試集正確分類的樣本數(shù)量表

從表1看出，基于SVM和決策樹的多分類方法較普通的SVM多分類方法，分類精度很大程度的提高;基于哈夫曼樹的SVM決策樹多分類方法較普通的SVM多分類方法和基于偏態(tài)樹的SVM決策樹多分類方法，能得到更高的分類精度.每類對(duì)應(yīng)的分類準(zhǔn)確率如圖9所示，更加形象地驗(yàn)證了這一點(diǎn).

圖9 3種多分類方法分類精度比較

表2列出了3種多分類方法的實(shí)驗(yàn)結(jié)果對(duì)比，包括總的分類精度、訓(xùn)練時(shí)間及測(cè)試時(shí)間.從表2可以看出，普通的SVM多分類方法的訓(xùn)練時(shí)間、分類測(cè)試時(shí)間遠(yuǎn)多于基于支持向量機(jī)和決策樹多分類方法，而且在分類精度上也遜色很多.另外，基于SVM和正態(tài)決策樹(本文用到的是哈夫曼樹)多分類方法和基于SVM和偏態(tài)決策樹多分類方法相比，在分類精度上，前者較后者提升了將近3.5個(gè)百分點(diǎn)，這說明基于正態(tài)樹結(jié)構(gòu)的分類模型能有效減少分類過程中的誤差積累;在訓(xùn)練速度上，前者比后者慢了8 s左右，這是因?yàn)榛谡龖B(tài)樹的SVM多分類方法中，每次計(jì)算相異度矩陣是多對(duì)多的，消耗了更多的時(shí)間.

表2 3種多分類方法的結(jié)果對(duì)比表

4 結(jié)論

本文利用類間相異度為決策依據(jù)，構(gòu)建了以哈夫曼樹結(jié)構(gòu)為基礎(chǔ)的SVM決策樹的多分類方法，克服了產(chǎn)生局部最優(yōu)解的缺點(diǎn)并削弱了錯(cuò)誤累積的影響，較普通的SVM多分類方法，在分類精度和分類速度上都有很大程度上的提高.另外，基于偏態(tài)樹結(jié)構(gòu)的SVM多分類方法擁有更快的訓(xùn)練速度，基于哈夫曼樹的SVM多分類方法擁有更高的分類精度.最后將本文中的方法應(yīng)用于網(wǎng)絡(luò)搜索數(shù)據(jù)上，證明了該結(jié)論.針對(duì)不同的應(yīng)用，如何選擇不同的決策樹型結(jié)構(gòu)構(gòu)造多分類模型來平衡訓(xùn)練時(shí)間和分類精度之間的關(guān)系，從而最大程度的發(fā)揮不同決策樹型結(jié)構(gòu)的優(yōu)點(diǎn)，這需要在后續(xù)的研究工作中繼續(xù)探討.

［1］王燕爽.分類能力與學(xué)習(xí)成績(jī)［D］.吉林:東北師范大學(xué)，2006.

［2］Teng Shaohua，Du Hongle，Wu Naiqi.A cooperative network intrusion detection based on fuzzy SVMs［J］.Journal of Networks，2010，5(4):475-483.

［3］ Zhang Wei，Teng Shaohua，Zhu Haibin.Fuzzymulti-class support vectormachines for cooperative network intrusion detection［C］//Proceedings of the 9thIEEEInternational Conferenceon CognitiveInformatics(ICCI)，Beijing，2010:811-818

［4］杜紅樂.基于支持向量機(jī)的協(xié)同入侵檢測(cè)［D］.廣州:廣東工業(yè)大學(xué)，2009.

［5］刁智華，趙春江，郭新宇.一種新的基于平衡決策樹的SVM多類分類算法［J］.控制與決策，2011，26(1):149-152.

［6］Lin Fuming，Guo Jun.Improving support vectormachine by preprocessing data with decision tree［C］//ComputerScience and Service System(CSSS)，Nanjin，2011:467-469.

［7］崔建，李強(qiáng)，劉勇.基于決策樹的快速SVM分類方法［J］.系統(tǒng)工程與電子技術(shù)，2011，33(11):2558-2563.

［8］趙天昀.一種改進(jìn)的SVM決策樹文本分類算法［J］.情報(bào)雜志，2010，29(8):1002-1965.

［9］厲小潤(rùn)，趙光宙，趙遼英.決策樹支持向量機(jī)多分類器設(shè)計(jì)的向量投影法 ［J］.控制與決策，2008，23(7):745-750.

［10］裘國(guó)永，張嬌.基于2分K-均值的SVM決策樹自適應(yīng)分類方法［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(10):3685-3687，3709

［11］張先武，郭雷.一種新的支持向量機(jī)決策樹設(shè)計(jì)算法［J］.火力與指揮控制，2010，35(10):31-35.

［12］喬增偉，孫衛(wèi)祥.一種基于支持向量機(jī)決策樹多類分類器 ［J］.計(jì)算機(jī)應(yīng)用與軟件，2009，26(11):227-230

［13］第一屆勒卡斯杯數(shù)據(jù)挖掘競(jìng)賽(上海站)［EB/OL］.［2012-05-12］.http://ledmclub.engagecloud.net/.

［14］柯麗，王明文，何世柱，等.基于頻率共現(xiàn)熵的跨語言網(wǎng)頁自動(dòng)分類研究［J］.江西師范大學(xué)學(xué)報(bào):自然科學(xué)版，2011，35(3):240-245.