基于SVM的多類分類算法改進

王 忠，王春麗，劉 莉

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

0 引 言

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

多類分類問題可用數學語言描述為：給定訓練庫

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

(1)

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

f(x)∶X→Y

(2)

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

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

首先給出標準的基于二叉樹的多類SVM分類算法描述如下[9]：

(1)計算訓練庫TR中類別數k.

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

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

(4)以f(x)為根結點構造二叉樹.

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

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

(7)以其中一類為正樣本，另一類為負樣本構造分類函數f(x)，并以f(x)為父結點，正(或負)樣本編號為左子樹，負(或正)樣本編號為右子樹構造子二叉樹，將此子二叉樹加入到相應的內部結點中作為孩子結點.

(8)以該樣本編號為葉子結點，加入到相應的內部結點中作為其孩子結點.

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

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

(11)進入左子樹，若該結點為葉子結點輸出xc類別，否則轉至(10).

(12)進入右子樹，若該結點為葉子結點輸出xc類別，否則轉至(10).

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

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

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

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

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

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

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

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

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

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

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

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

2 基于二叉樹的多類SVM分類算法的改進

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

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

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

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

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

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

圖1 測試文本聚類示意圖

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

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

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

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

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

(1)計算訓練庫TR中類別數k：

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

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

(4)以f(x)為根結點構造二叉樹：

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

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

(7)以其中一類為正樣本，另一類為負樣本構造分類函數f(x)，并以f(x)父結點，正(或負)樣本編號為左子樹，負(或正)樣本編號為右子樹構造子二叉樹，將此子二叉樹加入到相應的內部結點中作為孩子結點.

(8)以該樣本編號為葉子結點，加入到相應的內部結點中作為其子結點.

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

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

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

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

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

算法2 改進后的基于二叉樹的多類SVM分類算法描述

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

3 改進后算法性能分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結 語

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

參考文獻：

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

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

[3]付香英,王春麗.非線性可分文本的SVM算法研究及改進[J].九江學院學報,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]黃瓊英.支持向量機多類分類算法的研究及應用[D].河北:河北工業(yè)大學,2005.

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

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

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

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

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

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

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