基于SVM一對一多分類算法的二次細(xì)分法研究*

陳中杰，蔣 剛，蔡 勇

（1．西南科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川綿陽 621010;2．西南科技大學(xué)制造科學(xué)與工程學(xué)院，四川綿陽 621010）

0 引言

目前，對于支持向量機(jī)（SVM）分類算法［1］中的一對一多分類算法，許多學(xué)者都進(jìn)行了多方面的研究。例如:肖榮，李金鳳，覃?。?］以及康維新，彭喜元［3］提出了基于快速粗分類的一對一多分類算法。安欣，王韜，張錄達(dá)［4］闡述了基于SVM一對一多分類方法的應(yīng)用前景。趙有星，李琳［5］通過對構(gòu)成分類邊界的超平面的研究，引入了“核空間距離”。

對SVM一對一多分類算法的上述研究，均忽略了樣本出現(xiàn)不可分區(qū)域的問題，而是粗略地選擇其中序號最小的那一類作為測試數(shù)據(jù)的類別或者是根據(jù)決策函數(shù)實(shí)際值的大小分到與之距離最近的類中［3～6］。本文針對一對一多分類算法出現(xiàn)不可分區(qū)域的問題，提出了基于SVM一對一多分類算法的二次細(xì)分方法，并通過實(shí)驗(yàn)仿真驗(yàn)證該方法的優(yōu)勢。

1 SVM多分類算法

SVM分類算法最初是為二值分類問題設(shè)計(jì)的，目前，常用的有一對多方法、一對一方法。

1．1 一對多算法

一對多方法（one-versus-rest）:訓(xùn)練時(shí)依次把某個(gè)類別的樣本歸為一類，其他剩余的樣本歸為另一類，這樣N個(gè)類別的樣本就構(gòu)造出了N個(gè)SVM分類器，分類時(shí)將未知樣本分類為具有最大分類函數(shù)值的那類。流程如下:

假定將第j類樣本看作正類（j=1，2，…，k），將其他k－1類樣本看作負(fù)類，通過兩類SVM方法求出一個(gè)決策函數(shù)

這樣的決策函數(shù)一共有k個(gè)。給定一個(gè)測試樣本x，將其分別帶入k個(gè)決策函數(shù)并求出函數(shù)值，若在k個(gè)f（x）中fs（x）最大，則判定樣本x屬于第s類。

1．2 一對一算法

一對一方法（one-versus-one）:其解決方法是在k類問題中進(jìn)行兩兩組合，使用每兩類的訓(xùn)練樣本，構(gòu)建類對間的最優(yōu)超平面。給定樣本集（x1，y1），…，（xi，yi），xi∈Rn，i=1，…，k，yi∈{1，…，k}類對 ij的決策函數(shù)定義如下

該決策函數(shù)可通過以下二次規(guī)劃問題求解

上式針對所有n個(gè)樣本求解，由于fij（x）=fji（x），因而對于一個(gè)k類問題，共有k（k－1）/2個(gè)不同的決策函數(shù)，將k類問題劃分為多個(gè)兩類分類子問題進(jìn)行求解，最終可直接求得任意兩類之間的分類邊界。

在一對一方法中，分類的方法是:“投票機(jī)制”，即多數(shù)獲勝，每個(gè)分類器為它的首選類投出一票，最終結(jié)果就是擁有票數(shù)最多的類別，也就是樣本x屬于類i，當(dāng)且僅當(dāng)

其中，Cx為樣本x屬于類i時(shí)的票數(shù)，sgn fij是符號函數(shù)，即當(dāng)fij值為正數(shù)時(shí)，函數(shù)值為1;否則，為0。

當(dāng)多于一個(gè)類別具有相同數(shù)目的最多票數(shù)時(shí)，即出現(xiàn)不可分區(qū)域的問題。那么，不可分區(qū)域中的樣本點(diǎn)就會(huì)選擇其中序號最小的那一類作為測試數(shù)據(jù)的類別或者是根據(jù)決策函數(shù)實(shí)際值的大小分到與之距離最近的類中

其中，Vx為樣本 x屬于類i時(shí)決策函數(shù)的實(shí)際輸出值［6］。

通過對一對一多分類算法的描述，可以看出:由于該算法的“投票機(jī)制”會(huì)出現(xiàn)“平局”現(xiàn)象，即出現(xiàn)了不可分區(qū)域問題，從而降低了分類的準(zhǔn)確率。

原始一對一分類算法，如圖1所示。

2 基于SVM一對一多分類算法的二次細(xì)分方法

根據(jù)第1節(jié)對一對一多分類算法的介紹，該算法會(huì)出現(xiàn)不可分區(qū)域的問題，從而降低了分類的準(zhǔn)確率。

圖1 原始一對一分類算法Fig 1 Original one-versus-one classification algorithm

本文在研究了目前學(xué)者處理此問題的方法之上，提出了基于SVM一對一多分類算法二次細(xì)分方法。該方法的思想如下:

1）首先，也是對N類樣本構(gòu)造N（N－1）/2個(gè)SVM子分類器。例如:對于第i類和第j類，構(gòu)造第i類和第j類的SVM子分類器。

2）對測試樣本x在第i類和第j類構(gòu)造的子分類器上進(jìn)行分類預(yù)測。根據(jù)決策函數(shù)（2）:若樣本x屬于第i類，則第i類投票數(shù)加1;若樣本x屬于第j類，則第j類投票數(shù)加1，累計(jì)各類的得分。

3）統(tǒng)計(jì)每一個(gè)測試樣本的得票數(shù)，從而得到的各個(gè)樣本的最高的票數(shù)，獲取各個(gè)樣本的最高得票數(shù)。根據(jù)最后的得票數(shù)，若樣本有單個(gè)最高得票數(shù)，則把該樣本分為所相應(yīng)的類別。

4）若對同一樣本有多個(gè)最高得票數(shù)，則把這幾個(gè)最高得票數(shù)相對應(yīng)的類別的訓(xùn)練數(shù)據(jù)組成新的訓(xùn)練集，對該測試樣本在新組成的訓(xùn)練集上重新進(jìn)行分類預(yù)測，最后得出測試樣本的類別。

一對一多分類算法的二次細(xì)分方法，如圖2所示。

圖2 一對一多分類算法的二次細(xì)分方法Fig 2 The secondary subdivision method for one-versus-one multi-classification algorithm

3 應(yīng)用實(shí)例與結(jié)果分析

本次仿真實(shí)驗(yàn)的數(shù)據(jù)來源于2種不同彈性系數(shù)的彈簧組合下的彈性應(yīng)力變化值。本次實(shí)驗(yàn)構(gòu)建10組不同的彈簧模型，每組采集10個(gè)樣本，每個(gè)樣本201個(gè)特征。

實(shí)驗(yàn)以每組組合的前7個(gè)樣本作為訓(xùn)練集，共10×7=70的訓(xùn)練樣本，后3個(gè)樣本作為測試樣本，共10×3=30個(gè)測試樣本。本次仿真實(shí)驗(yàn)選取RBF作為核函數(shù)，實(shí)驗(yàn)過程如下:

1）首先對所有樣本數(shù)據(jù)進(jìn)行小波包去噪，并對去噪后數(shù)據(jù)進(jìn)行歸一化處理。

2）利用主成分分析法（PCA）對所有數(shù)據(jù)進(jìn)行降維和特征提取。

3）采用基于SVM一對一算法對訓(xùn)練樣本進(jìn)行分類建模，并對測試樣本進(jìn)行分類預(yù)測，最后獲得各個(gè)樣本的投票統(tǒng)計(jì)數(shù)據(jù)，如表1所示。

4）根據(jù)第（3）步的投票統(tǒng)計(jì)結(jié)果，若同一樣本有單個(gè)最高得票數(shù)，則把該樣本分為所相應(yīng)的類別。若同一測試樣本有多個(gè)最高得票數(shù)，則采用改進(jìn)后的方法，把最高得票數(shù)對應(yīng)的訓(xùn)練數(shù)據(jù)組成新的訓(xùn)練集，從而對該測試樣本在新組成的訓(xùn)練集上重新進(jìn)行分類預(yù)測，最后得出測試樣本的類別。

因樣本眾多，現(xiàn)只將第一組彈簧模型的第七個(gè)樣本數(shù)據(jù)的原始圖像（如圖3），小波包去噪后圖像（如圖4），PCA降維和特征提取后圖像（如圖5）列出。

圖3 樣本原始圖像Fig 3 Original image of sample

圖4 樣本小波包去噪圖像Fig 4 Wavelet packet denoising image of sample

圖5 樣本PCA降維特征提取后圖像Fig 5 Feature extraction and dimensionality reduction image with PCA of sample

表1 投票后出現(xiàn)不可分區(qū)域的樣本在原始方法與改進(jìn)方法后的分類結(jié)果Tab 1 Classification results after original and improved methods of sample about inseparable area after voting

由上表可知:第5個(gè)樣本在第二類、第八類和第九類獲得同樣的最高得分8分;第12個(gè)樣本在第三類、第四類和第六類獲得同樣的最高得分8分;第22樣本在第二類、第八類獲得同樣的最高得分8分。因此，如果按原始方法進(jìn)行分類，即選擇小序號類作為測試數(shù)據(jù)的類別，則第5個(gè)樣本被正確分類，而第12個(gè)樣本被錯(cuò)分為第三類，第22個(gè)樣本會(huì)被錯(cuò)分為第二類。

改進(jìn)的方法:對于第12個(gè)樣本，把出現(xiàn)最高得分的第三類、第四類和第六類作為訓(xùn)練集，重新進(jìn)行訓(xùn)練，再進(jìn)行分類預(yù)測。同理，對于第22個(gè)樣本，把出現(xiàn)最高得分的第二類、第八類作為訓(xùn)練集，訓(xùn)練后再進(jìn)行分類預(yù)測。

在分類準(zhǔn)確率和花費(fèi)時(shí)間上，改進(jìn)的方法和傳統(tǒng)的一對一算法進(jìn)行比較。結(jié)果如表2所示。

表2 分析結(jié)果一覽表Tab 2 List of analyzed results

通過表2可以看出:改進(jìn)的方法與原始的方法相比，改進(jìn)的算法在多花費(fèi)了極短的時(shí)間（0．018 3 s）的前提下，顯著提高了分類的正確率。同時(shí)通過表1和表2的結(jié)果可以看出改進(jìn)的方法對樣本12和樣本22進(jìn)行了正確的分類，證明了該方法的可行性。

但是，該方法還存在一定的問題，即，若第二次細(xì)分之后還是出現(xiàn)同一樣本有多個(gè)最高得票數(shù)的情況，是否還需要進(jìn)行第三次細(xì)分，本文通過再進(jìn)行另外9次仿真實(shí)驗(yàn)進(jìn)行驗(yàn)證。10次實(shí)驗(yàn)仿真結(jié)果如表3所示。

通過表3可以看出:只有實(shí)驗(yàn)三和實(shí)驗(yàn)六在第三次細(xì)分之后在很小程度提高了分類準(zhǔn)確率;實(shí)驗(yàn)一、實(shí)驗(yàn)二、實(shí)驗(yàn)五、實(shí)驗(yàn)七、實(shí)驗(yàn)九在第三次細(xì)分之后的準(zhǔn)確率與二次細(xì)分方法保持一致，沒有提高，反而多消耗了一定的時(shí)間;實(shí)驗(yàn)四、實(shí)驗(yàn)八、實(shí)驗(yàn)十只通過二次細(xì)分方法就達(dá)到了100%的準(zhǔn)確率，不需要進(jìn)行第三次細(xì)分。

通過以上分析可以看出:只有很小一部分的數(shù)據(jù)（20%）提高了分類的準(zhǔn)確率，大多數(shù)的數(shù)據(jù)（80%）沒有提高分類的準(zhǔn)確率，反而大大增加了分類所需要的時(shí)間。因此，針對小樣本數(shù)據(jù)問題，只進(jìn)行二次細(xì)分方法就能達(dá)到理想的分類準(zhǔn)確率，沒有必要進(jìn)行繼續(xù)細(xì)分。

表3 10次實(shí)驗(yàn)結(jié)果一覽表Tab 3 List of ten times experimental results

4 結(jié)束語

本文針對一對一多分類算法中出現(xiàn)不可分區(qū)域的問題，提出了基于SVM的一對一多分類算法的二次細(xì)分方法。仿真證明:改進(jìn)的方法在處理小樣本數(shù)據(jù)有突出的優(yōu)勢，可以明顯提高分類的正確率。

［1］ Vapnik V．The nature of statistical leaning theory［M］．New York:Springer Press，1995．

［2］ 肖 榮，李金鳳，覃 俊．一種改進(jìn)的一對一多類支持向量機(jī)［J］．軟件導(dǎo)刊，2010，9（10）:109 －111．

［3］ 康維新，彭喜元．基于二層SVM多分類器的樁基缺陷診斷［J］．電子學(xué)報(bào)，2009，36（12A）:66 －70．

［4］ 安 欣，王 韜，張錄達(dá)．一種基于SVM分類的多類識(shí)別方法及應(yīng)用［J］．北京農(nóng)學(xué)院學(xué)報(bào)，2006，21（2）:20 －22．

［5］ 趙有星，李 琳．基于支持向量機(jī)的多類分類算法研究［J］．計(jì)算機(jī)與信息技術(shù)，2007，29（1）:129 －130．

［6］ 王 天，葉秀芬，劉曉陽，等．基于SVM算法的碟形水下機(jī)器人姿態(tài)預(yù)測方法研究［J］．傳感器與微系統(tǒng)，2012，31（4）:56 －59．

［7］ Hsu C W，Lin C J．A comparison of methods for multi-class support vector machines［J］．IEEE Tran on Neural Networks，2002，13（2）:415－425．

［8］ Agarwal K．Process knowledge-based multi-class support vector classification（PK-MSVM）approach for surface defects in hot rolling［J］．Expert Systems with Applications，2011，38（6）:7251－7262．

［9］ Debnath R，Takahid N，Takahashi H．A decision based on oneagainst-one method for multi-class support sector machines［J］．Pattern Anal Applic，2004，1（5）:164 －175．