王 忠，王春麗，劉 莉

(1.武漢工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430074;2.湖北水利水電職業(yè)技術(shù)學(xué)院,湖北 武漢 430070)

0 引 言

支持向量機(jī)(Support Vector Machine,簡稱SVM)[1-3]算法的研究起源于對數(shù)據(jù)分類問題的處理，是統(tǒng)計學(xué)習(xí)理論的一種實現(xiàn)方法，它建立在樣本數(shù)量有限的基礎(chǔ)之上，能在現(xiàn)有訓(xùn)練文本包含的信息下得到最佳分類效果.同時，SVM源于統(tǒng)計學(xué)習(xí)理論中的VC維理論和結(jié)構(gòu)風(fēng)險最小化(Structure Risk Minimization, 簡稱SRM)原理[4]，有效地解決了其它機(jī)器學(xué)習(xí)算法中的過學(xué)習(xí)問題，即SVM在數(shù)量有限的訓(xùn)練樣本上，由訓(xùn)練誤差最小化可以確保測試誤差最小化.然而，標(biāo)準(zhǔn)的SVM算法只能解決兩類分類問題，雖然分類精度高，但通常不能滿足現(xiàn)實中多類分類問題的需要.將SVM算法推廣到多類分類問題中，具有重要的意義，引起了人們的廣泛關(guān)注.

多類分類問題可用數(shù)學(xué)語言描述為：給定訓(xùn)練庫

TR={(xi,yi)|xi∈Rn,yi∈Y,i=1,2,…,n}

(1)

和測試文本集合X∈Rn.需要求解分類函數(shù)f(x)，使得

f(x)∶X→Y

(2)

xi為文本向量，yi為類別標(biāo)記，Y類別集合，|Y|>2.在目前的研究中，常用的SVM多類分類方法有一對多、一對一、決策有向無環(huán)圖、二叉樹方法和一次性求解函數(shù)參數(shù)的方法[5-7]等.其中，基于二叉樹的多類SVM分類算法在訓(xùn)練時不需要總在整個訓(xùn)練庫上進(jìn)行，其訓(xùn)練子庫規(guī)模逐步減小，而在測試時也不必要總是遍歷整個二叉樹[8]，所以其訓(xùn)練和測試速度都比較快，并且解決了不可分區(qū)域問題.目前為止，已有很多對它的改進(jìn)和應(yīng)用，但主要集中在對訓(xùn)練庫的處理和二叉樹的結(jié)構(gòu)的改進(jìn)上，取得了不少成果.本文在深入研究基于二叉樹的多類SVM分類算法的基礎(chǔ)上，從分類階段出發(fā)，對它提出了改進(jìn).

1 基于二叉樹的多類SVM分類算法分析

首先給出標(biāo)準(zhǔn)的基于二叉樹的多類SVM分類算法描述如下[9]：

(1)計算訓(xùn)練庫TR中類別數(shù)k.

(2)若k>2轉(zhuǎn)至(3)，若k≤2轉(zhuǎn)至(6).

(3)將訓(xùn)練庫隨機(jī)分成兩個子集A和B，以A(或B)為正類，B(或A)為負(fù)類構(gòu)造分類函數(shù)f(x).

(4)以f(x)為根結(jié)點構(gòu)造二叉樹.

(5)對子集A和B重復(fù)步驟(1)、(2)、(3)，并將以A(或B)為訓(xùn)練庫生成的分類函數(shù)為左子樹，以B(或A)為訓(xùn)練庫生成的分類函數(shù)為右子樹，構(gòu)造分類函數(shù).

(6)若k=2轉(zhuǎn)至(7)，若k=1轉(zhuǎn)至(8).

(7)以其中一類為正樣本，另一類為負(fù)樣本構(gòu)造分類函數(shù)f(x)，并以f(x)為父結(jié)點，正(或負(fù))樣本編號為左子樹，負(fù)(或正)樣本編號為右子樹構(gòu)造子二叉樹，將此子二叉樹加入到相應(yīng)的內(nèi)部結(jié)點中作為孩子結(jié)點.

(8)以該樣本編號為葉子結(jié)點，加入到相應(yīng)的內(nèi)部結(jié)點中作為其孩子結(jié)點.

(9)將測試數(shù)據(jù)xc輸入到已建好的二叉樹根結(jié)點中.

(10)若f(xc)≥0轉(zhuǎn)至(11)，若f(xc)<0轉(zhuǎn)至(12).

(11)進(jìn)入左子樹，若該結(jié)點為葉子結(jié)點輸出xc類別，否則轉(zhuǎn)至(10).

(12)進(jìn)入右子樹，若該結(jié)點為葉子結(jié)點輸出xc類別，否則轉(zhuǎn)至(10).

算法1 標(biāo)準(zhǔn)的基于二叉樹的多類SVM分類算法

對于有k個類別的問題而言，基于二叉樹的多類SVM分類算法需要構(gòu)造k-1個分類函數(shù)，其中第i個分類函數(shù)以第i類為正訓(xùn)練樣本，以i+1到k類為負(fù)訓(xùn)練樣本，1≤i≤k.然后將k-1個兩類分類函數(shù)作為內(nèi)部結(jié)點組合成二叉樹形式，并以k個類別標(biāo)記為葉子結(jié)點.測試時，從根結(jié)點開始計算分類函數(shù)，根據(jù)值的正負(fù)決定下一步的走向，如此下去，直到到達(dá)某一葉結(jié)點為止，此葉結(jié)點所代表的類別就是測試樣本的類別.在此過程中，可能使用到的分類函數(shù)數(shù)目介于1和二叉樹的深度之間.

可以看出，基于二叉樹的多類SVM分類算法具有層次結(jié)構(gòu)，每個層次的分類函數(shù)的級別和重要性不同，在構(gòu)造二叉樹的過程中可以考慮各個類別的先驗知識.由于在訓(xùn)練時它不需要總在整個訓(xùn)練庫上進(jìn)行，其訓(xùn)練子庫規(guī)模逐步減小，而在測試時也不必要總是遍歷整個二叉樹，所以其訓(xùn)練和測試速度都比較快，并且解決了不可分區(qū)域問題[5].相對于其它基于SVM的多類分類算法而言，基于二叉樹的多類SVM分類算法主要有如下特點：

(1)針對k類分類問題，只需構(gòu)造k-1分類函數(shù)，數(shù)目相對較少，訓(xùn)練速度較快.

(2)訓(xùn)練分類函數(shù)時，不需要總是在整個訓(xùn)練庫上進(jìn)行，二次規(guī)劃問題的規(guī)模隨著訓(xùn)練過程的進(jìn)行逐漸減小.

(3)測試時不需要總是遍歷整個二叉樹，而是沿著從根結(jié)點到文本類別的方向前進(jìn)，可能使用到的SVM分類函數(shù)數(shù)目介于1到二叉樹的深度之間，分類速度相對較快.

(4)解決了其它方法中的不可分問題.

雖然基于二叉樹的多類SVM分類算法具有良好的分類性能，然而，在測試過程中，大量的測試文本都必須從二叉樹的根結(jié)點開始，逐步判斷，帶有一定的盲目性.例如，如果將二叉樹內(nèi)部結(jié)點按照前序遍歷的順序，依次編號為i到k-1，這樣這k-1個分類函數(shù)對應(yīng)的類別也被從1標(biāo)記到k-1.當(dāng)測試文本x屬于二叉樹中第i類時，在某些情況下測試文本必須依次計算f0(x),f1(x),……，直到fi-1(x)為止，0≤i≤k-2.在此過程中，前面的i次計算都不能確定x的類別，從某種意義上說是無用的計算.并且在實際情況中，屬于二叉樹中第一個類別的測試文本總是有限的，它們在測試文本集合中僅占一定的比重，甚至僅僅占很小的比重，那么其它不屬于該類別的文本都從第一個類別開始進(jìn)行計算，是沒有必要的.對于二叉樹中其它類別，也是如此.可以發(fā)現(xiàn)，如果測試文本數(shù)量越大，訓(xùn)練庫中類別數(shù)越多，則由于盲目計算所浪費(fèi)的資源越多.將上述問題總結(jié)如下：

(1)所有的測試文本都必須從二叉樹的根結(jié)點開始，逐步判斷，帶有一定的盲目性.這種盲目性會造成很多無用的計算，浪費(fèi)大量資源.

(2)測試文本數(shù)量越多時，無用的計算越多.

(3)訓(xùn)練庫中類別數(shù)越多時，分類函數(shù)越多，無用的計算越多.

因此，有必要尋找一種能減少這種盲目性的方法，提高基于二叉樹的多類SVM分類算法的分類效率.本文提出，當(dāng)測試文本數(shù)量龐大，訓(xùn)練庫類別較多時，可以先對測試文本進(jìn)行聚類，然后分類，使得分類帶有一定的指導(dǎo)性.具體步驟將在下文中給出.

2 基于二叉樹的多類SVM分類算法的改進(jìn)

在對基于二叉樹的多類SVM分類算法的改進(jìn)方法中，本文使用到了文本聚類算法[9]，其基本思想是指把一組對象集合根據(jù)其特征歸成若干類別，其目的是將一個大的集合分為若干小類別，使得屬于同一類別的對象之間相似程度最大，而不同類別之間的相似程度最小.在常用的聚類方法中，平面劃分方法簡單易行，且具有良好的性能.它的基本思想是：先從數(shù)據(jù)集中任意選取若干數(shù)據(jù)作為聚簇中心，然后依據(jù)一定規(guī)則將剩余數(shù)據(jù)歸入到與各聚簇中心距離最近的聚簇中去.在平面劃分方法中，結(jié)果依賴于聚簇中心的選擇，一般是先對樣本進(jìn)行歸類，求出各個類的均值向量(中心點)，再將各個樣本歸到與其最近的均值向量的類別中，如此反復(fù).k-means是一種比較流行的啟發(fā)式平面劃分聚類方法，它的每個聚簇中心用該聚簇中對象的平均值來表示.k-means算法的基本步驟是：在數(shù)據(jù)集合中任意選擇k個數(shù)據(jù)，分別代表k個聚簇的平均值，將剩余的數(shù)據(jù)根據(jù)它們與各個聚簇中心的距離歸入到最近的聚簇中，然后重新計算每個聚簇的平均值.重復(fù)該過程，直到準(zhǔn)則函數(shù)收斂為止.

本文在對測試文本進(jìn)行聚類時，使用訓(xùn)練庫中的文本作為初始聚簇中心.這樣做的目的是出于以下三點原因：

(1)本文對測試文本進(jìn)行聚類，是為了根據(jù)各個聚簇中心信息，將聚簇中文本輸入到與之最相似的訓(xùn)練文本類別所對應(yīng)的分類函數(shù)中進(jìn)行計算.這樣，測試文本能被最先代入到它最可能屬于的類別所對應(yīng)的分類函數(shù)中，能減少測試過程中文本類別判斷的盲目性.

(2)當(dāng)訓(xùn)練庫中類別數(shù)為k時，以訓(xùn)練庫中的文本作為聚簇中心，能將測試文本聚集成與訓(xùn)練庫對應(yīng)的k個類別，有利于測試文本的分類.

(3)以訓(xùn)練庫中的文本作為聚簇中心，能有效的減少聚類算法的迭代次數(shù).

根據(jù)上文聚類的思想，可以先對測試文本集進(jìn)行聚類，形成與訓(xùn)練庫對應(yīng)的聚簇，然后在聚簇中選擇聚簇中心，代入二叉樹分類算法中判斷其類別，再將該聚簇中的其它文本直接代入聚簇中心所在的類別的分類函數(shù)中，進(jìn)行類別判斷(如圖1所示).由于在聚類生成的類別中，同一類別的文本之間相似程度很大，且其聚簇中心特性最能代表類別的特性，所以能用聚簇中心信息來對同聚簇中的數(shù)據(jù)進(jìn)行判斷.

圖1 測試文本聚類示意圖

使用訓(xùn)練庫中的文本作為聚類的聚簇中心，則在文本聚類后形成的各個聚簇中，其聚簇中心的類別是已知的.屬于該聚簇的文本x直接代入聚簇中心所在類別對應(yīng)的分類函數(shù)ft(x)中進(jìn)行計算，根據(jù)聚簇的特性可知，此時函數(shù)值為正，即文本x屬于類別t的概率很大.可以認(rèn)為，經(jīng)過第一次判斷后，大部分的測試文本都可歸入到正確的類別中.當(dāng)然可能存在少數(shù)的文本，第一次不能確定其類別.對于這部分文本而言可能存在兩種情況：

(1)聚類時沒有被聚集到正確的類別中.

(2)它是不屬于聚簇中心所屬類別的文本，即聚類時發(fā)生誤差.

本文的處理辦法是，讓它們從根結(jié)點開始重新遍歷二叉樹，使用在標(biāo)準(zhǔn)算法中的方法來判定其類別.由于基于二叉樹的多類SVM分類算法的特性，測試文本不存在不可分情形，即分類后所有測試文本都可以被歸入到相應(yīng)的類別中.

本文對基于二叉樹的多類SVM分類算法的改進(jìn)，是對分類階段的改進(jìn).在改進(jìn)后的算法中，本文提出的改進(jìn)思想將在算法的分類階段體現(xiàn)出來.改進(jìn)后的基于二叉樹的多類SVM分類算法描述如下(設(shè)訓(xùn)練庫中類別數(shù)為k)：

(1)計算訓(xùn)練庫TR中類別數(shù)k：

(2)若k>2轉(zhuǎn)至(3)，若k≤2轉(zhuǎn)至(6)：

(3)將訓(xùn)練庫隨機(jī)分成兩個子集A和B，以A(或B)為正類，B(或A)為負(fù)類構(gòu)造分類函數(shù)f(x)：

(4)以f(x)為根結(jié)點構(gòu)造二叉樹：

(5)對子集A和B重復(fù)步驟(1)、(2)、(3)，并將以A(或B)為訓(xùn)練庫生成的分類函數(shù)為左子樹，以B(或A)為訓(xùn)練庫生成的分類函數(shù)為右子樹，構(gòu)造分類函數(shù).

(6)若k=2轉(zhuǎn)至(7)，若k=1轉(zhuǎn)至(8).

(7)以其中一類為正樣本，另一類為負(fù)樣本構(gòu)造分類函數(shù)f(x)，并以f(x)父結(jié)點，正(或負(fù))樣本編號為左子樹，負(fù)(或正)樣本編號為右子樹構(gòu)造子二叉樹，將此子二叉樹加入到相應(yīng)的內(nèi)部結(jié)點中作為孩子結(jié)點.

(8)以該樣本編號為葉子結(jié)點，加入到相應(yīng)的內(nèi)部結(jié)點中作為其子結(jié)點.

(9)重復(fù)上述過程，直到訓(xùn)練庫為空，生成二叉樹SVMT.

(10)在已知的k個類中分別選取一個文本xi，1≤i≤k，以xi為聚類中心對測試文本聚類，在測試文本中得到k個聚簇ci,1≤i≤k.

(11)若ci中包含訓(xùn)練文本xi，則將ci中所有文本代入xi所在類別對應(yīng)的分類函數(shù)fi(x)中計算.

(12)若fi(cij)≥0，j-|ci|則文本cij屬于類i.

(13)否則，讓文本cij從根節(jié)開始遍歷二叉樹，直到確定其類別為止.

算法2 改進(jìn)后的基于二叉樹的多類SVM分類算法描述

在此算法中，針對k類分類問題，需要構(gòu)造k-1個分類函數(shù).與標(biāo)準(zhǔn)算法一樣，改進(jìn)后的算法也分為訓(xùn)練(1到9)和測試(10到13)兩個階段，其中分類器的訓(xùn)練與標(biāo)準(zhǔn)算法一致，本文對算法的改進(jìn)體現(xiàn)在測試階段.在測試階段，改進(jìn)后的算法先對測試文本集進(jìn)行聚類，然后根據(jù)聚簇的聚簇中心的類別信息來對該聚簇中其它文本進(jìn)行類別判斷.

3 改進(jìn)后算法性能分析

下面本文將使用具體數(shù)據(jù)對改進(jìn)前后的算法效率進(jìn)行分析.為此，收集10個類別的測試文本各1 000篇.并在由分類函數(shù)構(gòu)成的單邊二叉樹和完全二叉樹上進(jìn)行分析.

k-means聚類算法的平均準(zhǔn)確率可以達(dá)到75％以上[10-13].在此，不失一般性，假設(shè)聚類后每個類別的測試文本有75％被準(zhǔn)確聚類.在單邊二叉樹的情形下，原始算法完成全部測試文本的分類需要計算(1+2+…+9)×1 000，即45 000次分類函數(shù).而使用改進(jìn)后的算法時，至少有75％的測試文本能夠在第一次計算后確定其類別，而只有剩下的25％需要重新計算.則總的計算次數(shù)為：

10 000+1 000×25％×(1+2+…+9)=21 250次.

在完全二叉樹的情形下，原始算法完成全部測試文本的分類需要計算4 000×4+6 000×3次，即34 000次分類函數(shù).而使用改進(jìn)后的算法時，總次數(shù)為10 000+1 000×+1 500×=18 500次.

現(xiàn)將兩種情況下的分類函數(shù)計算次數(shù)統(tǒng)計如表1所示.

表1 分類函數(shù)計算次數(shù)統(tǒng)計

由表1可知，改進(jìn)后的基于二叉樹的多類SVM分類算法，在兩種情況下都可以使分類函數(shù)計算次數(shù)幾乎減少一半，從很大程度上提高了算法的分類效率.測試時分類函數(shù)的計算次數(shù)與二叉樹的深度有關(guān)，由數(shù)據(jù)結(jié)構(gòu)中相關(guān)知識可知，在結(jié)點數(shù)一定的情況下，單邊二叉數(shù)具有最大的深度，而完全二叉樹具有最小的深度，因此單邊二叉樹和完全二叉樹具有代表性.

在上面的分析中，僅選取了10個類別，每個類別也只有1 000篇文本.當(dāng)多類分類問題的類別數(shù)更多，每個類別測試文本數(shù)量更大時，改進(jìn)后的算法比原算法分類效率更高.同時，測試文本聚類后，同一聚簇的測試文本之間具有很強(qiáng)的相似性，能在一定程度上指導(dǎo)二叉樹分類器的分類，提高分類精度.現(xiàn)在將改進(jìn)后算法的特點總結(jié)如下：

(1)本文關(guān)于基于二叉樹的多類SVM算法的改進(jìn)是在測試階段，因此改進(jìn)后的算法在分類函數(shù)的訓(xùn)練階段保持了原算法的特性，具有較高的訓(xùn)練效率.

(2)改進(jìn)后的算法在測試階段對測試文本先聚類再分類，然后使用聚簇中心信息來指導(dǎo)文本分類，使得測試文本的第一次類別判斷是有目的性的，增大了快速將測試文本歸類的概率，有效的減少了計算分類函數(shù)的次數(shù).

(3)多類分類問題類別數(shù)越多，減少的分類函數(shù)計算次數(shù)越多.

(4)測試文本數(shù)量越多，減少的分類函數(shù)計算次數(shù)越多.

(5)聚類算法的準(zhǔn)確性越大，減少的分類函數(shù)計算次數(shù)越多.因為高準(zhǔn)確性的聚類算法將屬于同一類別的測試文本都聚集在一個聚簇中，使得測試文本被快速分類的概率增大.

(6)改進(jìn)后的算法能在一定程度上指導(dǎo)二叉樹分類器的分類，提高分類精度.

4 結(jié) 語

以上在系統(tǒng)研究了基于SVM的多類分類算法的基礎(chǔ)上，深入地描述了基于二叉樹的多類SVM分類算法.并針對其不足之處提出了改進(jìn)，即當(dāng)測試文本集規(guī)模較大，類別數(shù)較多時，對其先聚類，再分類，增大分類效率，提高分類精度.作為改進(jìn)的準(zhǔn)備知識，本章對聚類算法作了簡要分析.最后給出了改進(jìn)后的算法描述，并將其與標(biāo)準(zhǔn)的算法相比較，分析了改進(jìn)后算法的性能.

參考文獻(xiàn)：

[1]Vapnik V.The Nature of Statistical Learning Thery[M].New York:Springer-Verlag，2000.

[2]方輝,王倩.支持向量機(jī)的算法研究[J].長春師范學(xué)院學(xué)報:自然科學(xué)版,2007,26(3):90-91.

[3]付香英,王春麗.非線性可分文本的SVM算法研究及改進(jìn)[J].九江學(xué)院學(xué)報,2008,(3):69-61.

[4]Shawe-Taylor J,Bartlet P L,Williamson R C.Structural risk minimization over data dependent hierarchies.IEEE Transactions on Information Theory,1998,44(5):1926-1940.

[5]Hsu Chih-Wei,Lin Chih-Jen.A comparison of methods for multi-class support vector machines[J].IEEE Transactions on Neural Networks,2002,13(2):415-425.

[6]黃瓊英.支持向量機(jī)多類分類算法的研究及應(yīng)用[D].河北:河北工業(yè)大學(xué),2005.

[7]Kunchheva L.Combining classifiers by clustering, selection and decision templates[D].Technical report:University of Wales,2000.

[8]杜圣東.基于多類支持向量機(jī)的文本分類研究[D].重慶:重慶大學(xué),2007.

[9]Jiawei Han,Micheline amber.數(shù)據(jù)挖掘概念與技術(shù)[M].范明, 孟曉峰,譯.北京:機(jī)械工業(yè)出版社,2001.

[10]趙毓高.核聚類算法及其應(yīng)用研究[D].成都:西華大學(xué),2007.

[11]胡學(xué)軍，騰達(dá)，胡林文.基于MATLAB的時滯對擦控制算法仿真分析[J].武漢工程大學(xué)學(xué)報，2010，32(3)：92-95.

[12]陳偉亞，徐佳彬，李偉波.基于技術(shù)線路圖的循環(huán)經(jīng)濟(jì)發(fā)展規(guī)劃技術(shù)研究[J].武漢工程大學(xué)學(xué)報，2010，32(5)：53-56.

[13]崔士杰，汪建華.基于MATLAB的單相全控整流電路功率因數(shù)測試[J].武漢工程大學(xué)學(xué)報，2010，32(1)：90-92.