柳長(zhǎng)源， 畢曉君， 韋琦

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

0 引言

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

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

1 基于向量機(jī)的二分類算法

對(duì)于二分類問(wèn)題，設(shè)訓(xùn)練樣本集合為(xn，tn)(n=1，2，…，N，x∈Rd，t∈{0，1}是類別標(biāo)號(hào))，向量機(jī)的分類函數(shù)定義［13］為

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

2 “一對(duì)一”多模式分類器

“一對(duì)一”方法可利用二分類的機(jī)器學(xué)習(xí)算法實(shí)現(xiàn)多類模式識(shí)別［14］。此多分類算法每次只考慮兩類樣本，即對(duì)各模式類中每?jī)深悩颖径荚O(shè)計(jì)一個(gè)二分類向量機(jī)模型，這樣區(qū)分k個(gè)類別共需要設(shè)計(jì)k(k－1)/2個(gè)二分類器。當(dāng)需要對(duì)一個(gè)新測(cè)試樣本進(jìn)行分類時(shí)，首先要利用訓(xùn)練樣本對(duì)所有k(k－1)個(gè)二分類向量機(jī)模型進(jìn)行訓(xùn)練，每一個(gè)二分類模型訓(xùn)練后立即對(duì)測(cè)試樣本進(jìn)行判別，對(duì)它所隸屬的類別進(jìn)行投票。若待測(cè)試樣本屬于第i個(gè)類別，則第i類將獲得最多的票數(shù)，最終將票數(shù)最多的類判斷為此測(cè)試樣本的類別。

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

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

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

3 改進(jìn)后的新分類器設(shè)計(jì)

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

圖2以5個(gè)類別的模式識(shí)別為例，給出了所提出的多類別分類器的結(jié)構(gòu)原理圖。

圖2 改進(jìn)的5類別分類器結(jié)構(gòu)原理Fig.2 The schematic of improved 5 kinds classifier

圖2(a)是傳統(tǒng)的“一對(duì)一”循環(huán)方式，每?jī)蓚€(gè)類別都需要一個(gè)向量機(jī)分類器，訓(xùn)練識(shí)別次數(shù)為k(k－1)/2。為了減少運(yùn)算量，提出的方法采取“最低票淘汰”的方式，每一輪不是把所有每一對(duì)類別都兩兩比較，而是各類單循環(huán)相鄰比較，去掉每輪中得票最低的模式類別，然后進(jìn)行下輪比較。

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

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 多維目標(biāo)函數(shù)不同類別數(shù)量的數(shù)據(jù)分類識(shí)別仿真實(shí)驗(yàn)

所有實(shí)驗(yàn)在硬件配置為Intel Centrino Duo，CPU:T7250、2G內(nèi)存、2.70GHZ主頻的計(jì)算機(jī)上進(jìn)行，程序采用Matlab R2008a編寫。

采用SVM算法，改變不同的類別數(shù)k值，每個(gè)k值經(jīng)過(guò)50次這樣的仿真實(shí)驗(yàn)，分類時(shí)間取每次程序運(yùn)行平均值，并統(tǒng)計(jì)出分類正確的百分比。比較傳統(tǒng)的“一對(duì)一”分類器和改進(jìn)后的分類器得出的實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 基于SVM算法的分類器實(shí)驗(yàn)數(shù)據(jù)Table 1 The experimental data of classifier based onSVM algorithm

上述實(shí)驗(yàn)條件不變，改用RVM算法，再對(duì)比做不同k值得仿真實(shí)驗(yàn)，得到的數(shù)據(jù)如表2所示。

表2 基于RVM算法的分類器實(shí)驗(yàn)數(shù)據(jù)Table 2 The experimental data of classifier based on RVM algorithm

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

圖3 分類器改進(jìn)前后程序運(yùn)行時(shí)間比較Fig.3 The comparison of program running time pre and post improving classifier

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

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

從圖4中的數(shù)據(jù)不難發(fā)現(xiàn)，改進(jìn)算法的分類正確率雖略低于原始算法，但兩者的差別不大。當(dāng)k＞20時(shí)，改進(jìn)后的新方法與“一對(duì)一”分類正確率相差不超過(guò)1%，當(dāng)類別數(shù)足夠多時(shí)，二者識(shí)別正確率幾乎相同。

4.2 不同目標(biāo)函數(shù)40組類別數(shù)據(jù)分類識(shí)別仿真實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證改進(jìn)方法的可推廣性，選擇幾個(gè)有代表性的標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行分類實(shí)驗(yàn)。函數(shù)的自變量及其對(duì)應(yīng)的函數(shù)值為一個(gè)數(shù)據(jù)樣本，在每個(gè)函數(shù)的定義范圍內(nèi)隨機(jī)產(chǎn)生400個(gè)數(shù)據(jù)樣本，按函數(shù)值的范圍不同區(qū)分把這400個(gè)數(shù)據(jù)分成40個(gè)區(qū)間，每個(gè)區(qū)間內(nèi)的10個(gè)樣本形成一個(gè)數(shù)據(jù)類別。這樣每個(gè)函數(shù)都可以產(chǎn)生40類數(shù)據(jù)樣本，把每一類數(shù)據(jù)的前5個(gè)樣本作為向量機(jī)學(xué)習(xí)算法的訓(xùn)練樣本，后5個(gè)樣本用來(lái)測(cè)試訓(xùn)練后向量機(jī)模型的分類識(shí)別正確率。

4個(gè)測(cè)試目標(biāo)函數(shù)如下:

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

實(shí)驗(yàn)結(jié)果如表3所示。

表3 用標(biāo)準(zhǔn)函數(shù)測(cè)試改進(jìn)的分類器Table 3 Testing improved classifier using the standard function

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

5 結(jié)語(yǔ)

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

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

［2］VAPNIC.統(tǒng)計(jì)學(xué)習(xí)理論的本質(zhì)［M］.張學(xué)工，譯.北京:清華大學(xué)出版社，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的軸承故障檢測(cè)方法［J］.振動(dòng)與沖擊，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的二叉樹多類分類算法及其在故障診斷中的應(yīng)用［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］盧迪，竇文娟.遺傳優(yōu)化支持向量機(jī)在失火故障診斷中的應(yīng)用［J］.哈爾濱理工大學(xué)學(xué)報(bào)，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ī)的人臉識(shí)別方法［J］.計(jì)算機(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］聶會(huì)星，梁坤，徐樅巍.基于小波變換和支持向量機(jī)的人臉識(shí)別研究［J］.合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，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］楊成福，章毅.相關(guān)向量機(jī)及在說(shuō)話人識(shí)別應(yīng)用中的研究［J］.電子科技大學(xué)學(xué)報(bào)，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］高爭(zhēng)艷，張玉雙，王慕坤.基于核K－均值聚類和支持向量機(jī)結(jié)合的說(shuō)話人識(shí)別方法［J］.哈爾濱理工大學(xué)學(xué)報(bào)，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.