基于向量機學習算法的多模式分類器的研究及改進

柳長源， 畢曉君， 韋琦

(1.哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱 150001;2.哈爾濱理工大學電氣與電子工程學院，黑龍江哈爾濱 150080)

0 引言

支持向量機(support vector machine，SVM)是上九十年代中期由Vapnik提出的一種基于統計學習理論的一種機器學習算法［1－2］，該方法比神經網絡具有更好的泛化能力，在小樣本模式識別中也優于神經網絡。相關向量機(relevance vector machine，RVM)是Tipping在2000年最早提出的一種基于貝葉斯估計理論的機器學習方法，適用于函數回歸和模式分類問題［3］。該方法與SVM算法類似，但比后者解空間更稀疏，魯棒性也更好［4］。這兩種方法的共同目標是通過對樣本數據進行機器學習和訓練，找到一個最優的“超平面”方程作為分類面(實際就是求超平面方程的各階次系數)，把待識別樣本數據分化在超平面兩側，從而實現兩類別模式識別。

然而，在科學研究和工程技術中經常遇到需要將待識別模式分成多類別的情形。比如，在故障檢測中通常不只是判斷系統是否存在故障，還需要判斷出存在哪一類故障［5－7］;在人臉識別中要判斷待識別的圖像來自哪個人的面孔［8－9］;在語音識別中要判斷待識別的聲音信號來自哪個人的聲音［10－11］。為此有人提出用多個分類器組合的方式實現數據的多類別分類［12］，其中最著名的有“一對一”法、“一對多”法和“二叉樹”法3種。這3種方法中，目前應用最廣泛的方法，也是分類正確率最高、魯棒性和泛化能力最好的方法是“一對一”投票法，這種方法在訓練樣本較少時依然有效，但由于需要k(k－1)/2個RVM二分類器，該方法在類別數很多的情況下運算量很大。為此本文提出了一種可用于SVM或RVM機器學習算法的多類別模式識別方法該方法能夠在保證分類精度的前提下，解決了“一對一”分類方法中運算量大、分類速度慢的問題，使其在實時性方面有了大幅度的提高。

1 基于向量機的二分類算法

對于二分類問題，設訓練樣本集合為(xn，tn)(n=1，2，…，N，x∈Rd，t∈{0，1}是類別標號)，向量機的分類函數定義［13］為

式中:K(x，xi)是核函數;wi是模型的權值。SVM和RVM分類方法都是通過一組訓練樣本求得權值wi。經過多次迭代更新，大多數訓練樣本相應的wi為零，不為零的wi所對應的訓練樣本稱為支持向量(support vector，SV)或相關向量(relevance vector，RV)。相應的基函數因此可以“修剪”，實現稀疏性。由相關向量確定的分類函數是一個高維“超平面”，求得超平面方程，該平面把待測樣本劃分成兩個區域，從而實現二類別模式識別問題。

2 “一對一”多模式分類器

“一對一”方法可利用二分類的機器學習算法實現多類模式識別［14］。此多分類算法每次只考慮兩類樣本，即對各模式類中每兩類樣本都設計一個二分類向量機模型，這樣區分k個類別共需要設計k(k－1)/2個二分類器。當需要對一個新測試樣本進行分類時，首先要利用訓練樣本對所有k(k－1)個二分類向量機模型進行訓練，每一個二分類模型訓練后立即對測試樣本進行判別，對它所隸屬的類別進行投票。若待測試樣本屬于第i個類別，則第i類將獲得最多的票數，最終將票數最多的類判斷為此測試樣本的類別。

設分類函數fij(x)用來判別i，j兩類樣本，若fij(x)＜0，則判x屬于第i類，記i類得一票，否則判x屬于第j類，記j類得一票，最后在決策時，比較哪一類得到的票多，則將測試樣本劃歸為該類。該算法的基本結構如圖1所示。

圖1 基于RVM的“一對一”算法Fig.1 “one against one”algorithm based on RVM

因為每個類別都參與了k－1次比較，從理論上講，如果每次判別結果都正確沒有誤差，那么待測試樣本所在的模式類應該得到k－1票。其他類別在與正確類比較時得不到票數，但與其它不相關的類別比較時，得票被分散在各類中，任意兩不相關類得票概率相同，每類平均得票數應該在(k－2)/2左右，當k比較大的時候，即使有一小部分二分類器輸出錯誤結果，也能使正確類別得到最多的投票數，所以這種方法的分類精度高，魯棒性也很好。唯一的缺點是二分類器個數比較多，運算速度比較慢。

3 改進后的新分類器設計

為解決“一對一”分類器運算量大的問題，對其算法結構進行了改進，提出了一種新的基于向量機算法的多類別分類器。原分類方法比較次數與類別數的關系按k(k－1)增長，而新分類方法比較次數近似與類別數k呈線性增加。類別越多，新方法優勢越明顯。當k比較大的時候，即使有一小部分RVM分類器輸出錯誤結果，也能使正確類別得到最多的投票數，所以這種方法不僅運算量小，分類精度可保證，魯棒性也很好。

圖2以5個類別的模式識別為例，給出了所提出的多類別分類器的結構原理圖。

圖2 改進的5類別分類器結構原理Fig.2 The schematic of improved 5 kinds classifier

圖2(a)是傳統的“一對一”循環方式，每兩個類別都需要一個向量機分類器，訓練識別次數為k(k－1)/2。為了減少運算量，提出的方法采取“最低票淘汰”的方式，每一輪不是把所有每一對類別都兩兩比較，而是各類單循環相鄰比較，去掉每輪中得票最低的模式類別，然后進行下輪比較。

圖2(b)是改進算法的第一輪比較，設D為得票最少的模式類，這樣第二輪比較只需要對CE兩類進行單獨訓練識別，其余類別數據沿用上一輪結果，如圖2(c)。各類兩輪票數相加后，假設C為本輪后得票最少的模式類，圖2(d)是去掉C后的下一輪分類，只需要對BE兩類別再判別，其它類別票數也是沿用原來結果。假設本輪累計統計票數后A又被淘汰，如圖2(e)所示，此時無需再進行新的比較，只需要留下之前BE分類中得票高的模式類，即是模式識別結果。這樣例子中的5類識別只需要7次二分類判別(當然考慮到每輪淘汰的不確定性，也可能為8次)，而“一對一”法需要(5×4)/2=10次。當類別數k更多時，二者差異更加明顯。如k=40時，“一對一”法需要(40×39)/2=780個分類器，而新方法在實驗中得到的平均數據是53.4個，運算量比前者減少了一個數量級。

4 仿真實驗與結果分析

4.1 多維目標函數不同類別數量的數據分類識別仿真實驗

所有實驗在硬件配置為Intel Centrino Duo，CPU:T7250、2G內存、2.70GHZ主頻的計算機上進行，程序采用Matlab R2008a編寫。

采用SVM算法，改變不同的類別數k值，每個k值經過50次這樣的仿真實驗，分類時間取每次程序運行平均值，并統計出分類正確的百分比。比較傳統的“一對一”分類器和改進后的分類器得出的實驗數據如表1所示。

表1 基于SVM算法的分類器實驗數據Table 1 The experimental data of classifier based onSVM algorithm

上述實驗條件不變，改用RVM算法，再對比做不同k值得仿真實驗，得到的數據如表2所示。

表2 基于RVM算法的分類器實驗數據Table 2 The experimental data of classifier based on RVM algorithm

為了更清楚比較分類器改進前后的模式分類效果，把程序運行平均時間和識別正確率分別用圖3和圖4表示。

圖3 分類器改進前后程序運行時間比較Fig.3 The comparison of program running time pre and post improving classifier

圖4 分類器改進前后分類正確率比較Fig.4 The comparison of accuracy pre and post improving classifier

從圖3可以直觀看出，無論采用SVM還是RVM算法，改進算法的程序運行時間都有顯著縮短，而且類別數越多，這種效率的提升越明顯。改進后的運行時間與類別數近似線性增加，增加速率比改進前大大提高。

從圖4中的數據不難發現，改進算法的分類正確率雖略低于原始算法，但兩者的差別不大。當k＞20時，改進后的新方法與“一對一”分類正確率相差不超過1%，當類別數足夠多時，二者識別正確率幾乎相同。

4.2 不同目標函數40組類別數據分類識別仿真實驗

為了進一步驗證改進方法的可推廣性，選擇幾個有代表性的標準測試函數進行分類實驗。函數的自變量及其對應的函數值為一個數據樣本，在每個函數的定義范圍內隨機產生400個數據樣本，按函數值的范圍不同區分把這400個數據分成40個區間，每個區間內的10個樣本形成一個數據類別。這樣每個函數都可以產生40類數據樣本，把每一類數據的前5個樣本作為向量機學習算法的訓練樣本，后5個樣本用來測試訓練后向量機模型的分類識別正確率。

4個測試目標函數如下:

1)sqr(x):平方根函數，實驗變量范圍取0＜x＜10;2)lg(x):常用對數，實驗變量范圍取0＜x＜10;3)exp(x):以e為底的指數函數，實驗變量范圍取－5＜x＜5;4)th(x)雙曲正切函數，實驗變量范圍取－1＜x＜1。

實驗結果如表3所示。

表3 用標準函數測試改進的分類器Table 3 Testing improved classifier using the standard function

從表中數據可以看到，針對不同的測試函數，算法改進前后識別率變化不大，程序運行時間均有顯著提高。這表明改進后的方法對目標函數不敏感，魯棒性很好。因此該方法具有可推廣性，能滿足不同應用中提高模式識別軟件實時性的需要。

5 結語

本文提出了一種可用于SVM或RVM機器學習算法的多類別模式識別方法，該方法在現有的泛化性能、分類精度和魯棒性最好的“一對一”投票法基礎上進行了新的改進，并按照“最低票數輪次淘汰”的方式逐步逼近正確解。仿真實驗表明，該方法在基本不降低分類精度的前提下，運算量有明顯下降，特別是在類別較多的模式識別問題中，這種方法更是顯著地節約了程序的運行時間，提高了多類識別的工作效率。在模式類別數很多的實際應用中，該方法可以大大提高分類識別效率，具有一定的應用價值。

［1］VAPNIK V.The Nature of Statistical Learning Theory［M］.New York:Springer，1998.

［2］VAPNIC.統計學習理論的本質［M］.張學工，譯.北京:清華大學出版社，2000.

［3］TIPPING M E.Sparse Bayesian Learning and the relevance vector machine［J］.Machine Learning Research，2001:211－244.

［4］IOANNIS Psorakis，DAMOULAS Theodoros，MARK A，et al.Multiclass relevance vector machines:sparsity and accuracy［C］//IEEE Transactions on neural networks，2010，21(10):1588－1598.

［5］陶新民，徐晶，杜寶祥，等.基于相空間RVM的軸承故障檢測方法［J］.振動與沖擊，2007，25(12):1－7.

TAO Xinmin，XU Jing，DU Baoxiang，et al.Bearing fault detection based on RVM using phase space［J］.Journal of Vibration and Shock，2007，25(12):1－7.

［6］馬笑瀟，黃席褪，柴毅.基于SVM的二叉樹多類分類算法及其在故障診斷中的應用［J］.控制與決策，2003，18(3):272－276.

MA Xiaoxiao，HUANG Xitui，CHAI Yi.2PTMC classification algorithm based on support vector machines and its application to fault diagnosis［J］.Control and Decision，2003，18(3):272－276.

［7］盧迪，竇文娟.遺傳優化支持向量機在失火故障診斷中的應用［J］.哈爾濱理工大學學報，2012，17(1):36－38.

LU Di，DOU Wenjuan.Fault diagnosis of engine misfire based on genetic optimized support vector machine［J］.Journal of Harbin University of Science and Technology，2012，17(1):36－38.

［8］謝賽琴，沈福明，邱雪娜.基于支持向量機的人臉識別方法［J］.計算機工程，2009，35(16):186－188.

XIE Saiqin，SHEN Fuming，QIU Xuena.Face recognition method based on support vector machine［J］.Computer Engineering，2009，35(16):186－188.

［9］聶會星，梁坤，徐樅巍.基于小波變換和支持向量機的人臉識別研究［J］.合肥工業大學學報:自然科學版，2011，34(2):208－211.

NIE Huixing，LIANG Kun，XU Zongwei.Face recognition based on wavelet transform and support vector machine［J］.Journal of Hefei University of Technology:Natural Science Edition，2011，34(2):208－211.

［10］楊成福，章毅.相關向量機及在說話人識別應用中的研究［J］.電子科技大學學報，2010，39(2):311－315.

YANG Chengfu，ZHANG Yi.Study on speaker recognition using RVM［J］.Journal of University of Electronic Science and Technology of China，2010，39(2):311－315.

［11］高爭艷，張玉雙，王慕坤.基于核K－均值聚類和支持向量機結合的說話人識別方法［J］.哈爾濱理工大學學報，2008，13(5):40－42.

GAO Zhengyan，ZHANG Yushuang，WANG Mukun.Speaker recognition using kernel K-mean clustering and SVM［J］.Journal of Harbin University of Science and Technology，2008，13(5):40－42.

［12］KREBEL U.Pairwise classification and support vector machines［C］//Advances in Kernel Methods:Support Vector Learning.Cambridge，MA:The MIT Press，1999:255－268.

［13］BOTTOU L，CORTES C，DENKER J S，et al.Comparison of classifier methods:a case study in handwriting digit recognition［C］//International Conference on Pattern Recognition.Newyork:IEEE Computer Society Press，1994:77－87.

［14］SCJWEMLER F.Hierarchical support vector machines for multiclass pattern recognition［C］//Fourth International conference on Knowledge-Based Intelligent Engineering Systems＆Allied Technologies.Brighton，UK:IEEE Press，2000，2:561－565.