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

(廣東工業(yè)大學計算機學院，廣東廣州510006)

0 引言

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

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

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

1 支持向量機與分類

1.1 支持向量機

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

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

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

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

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

1.2 多分類支持向量機

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

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

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

圖1 分類器模型

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

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

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

2.2 多分類器測試與分類

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

圖3 多分類器分類過程

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

2.3 相異度計算

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

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

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

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

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

分析相異度公式可知，相異度矩陣是對稱的，減少了一部分計算時間.

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

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

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

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

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

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

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

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

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

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

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

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

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

(i)計算出訓練集中N個類的類間相異度矩陣.

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

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

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

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

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

圖7 所有類對應樣本集的合并過程

圖8 SVM決策樹多分類器

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

2.7 基于哈夫曼樹的SVM分類

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

3 實驗及結(jié)果分析

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

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

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

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

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

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

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

4 結(jié)論

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

［1］王燕爽.分類能力與學習成績［D］.吉林:東北師范大學，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］杜紅樂.基于支持向量機的協(xié)同入侵檢測［D］.廣州:廣東工業(yè)大學，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］崔建，李強，劉勇.基于決策樹的快速SVM分類方法［J］.系統(tǒng)工程與電子技術(shù)，2011，33(11):2558-2563.

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

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

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

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

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

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

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