陳中杰，蔣 剛，蔡 勇

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

0 引言

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

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

1 SVM多分類(lèi)算法

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

1．1 一對(duì)多算法

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

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

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

1．2 一對(duì)一算法

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

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

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

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

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

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

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

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

原始一對(duì)一分類(lèi)算法，如圖1所示。

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

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

圖1 原始一對(duì)一分類(lèi)算法Fig 1 Original one-versus-one classification algorithm

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

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

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

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

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

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

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

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

本次仿真實(shí)驗(yàn)的數(shù)據(jù)來(lái)源于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è)樣本作為測(cè)試樣本，共10×3=30個(gè)測(cè)試樣本。本次仿真實(shí)驗(yàn)選取RBF作為核函數(shù)，實(shí)驗(yàn)過(guò)程如下:

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

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

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

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

因樣本眾多，現(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)方法后的分類(lèi)結(jié)果Tab 1 Classification results after original and improved methods of sample about inseparable area after voting

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

［6］ 王 天，葉秀芬，劉曉陽(yáng)，等．基于SVM算法的碟形水下機(jī)器人姿態(tài)預(yù)測(cè)方法研究［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．