張 濤，劉長(zhǎng)旺

(南陽(yáng)師范學(xué)院 軟件學(xué)院，河南 南陽(yáng)473061)

1 多類分類支持向量機(jī)算法

支持向量機(jī)算法最初是針對(duì)二類別的分類而提出的，如何將其有效地推廣到多類分類是當(dāng)前支持向量機(jī)算法研究的重要內(nèi)容之一.目前，多類分類支持向量機(jī)算法主要有2種:第1種方法是構(gòu)造多個(gè)二類分類器并將它們組合起來(lái)，從而實(shí)現(xiàn)多類分類，例如 one-against-rest，one-against-one，DAGSVM 等;第2種方法是直接在1個(gè)優(yōu)化公式中同時(shí)考慮所有子分類器的參數(shù)優(yōu)化.

one-against-rest是多類分類支持向量機(jī)算法中最簡(jiǎn)單的1種.它的具體步驟為［1］:

a.設(shè)已知訓(xùn)練集

b.對(duì) j=1，2，…，M 進(jìn)行運(yùn)算，把第 j類看作正類，把其余的M－1類看作負(fù)類，用某種二類分類支持向量機(jī)算法求出決策函數(shù)

c.判定輸入 x屬于第 J類，其中 J是(g1(x)，g2(x)，…，gM(x))中最大者的上標(biāo).

這種算法遇到的問(wèn)題是:①可能存在2個(gè)J值(J1或J2)使得gJ1(x)和gJ2(x)都達(dá)到最大，此時(shí)無(wú)法推斷x的歸屬;②算法中構(gòu)造的那些二類分類問(wèn)題不對(duì)稱.要處理這種不對(duì)稱，可以對(duì)不同類別使用不同的處罰因子，對(duì)較少的類采用較大的處罰因子.

one-against-one算法的基本思想是為訓(xùn)練集中的任二類構(gòu)造1個(gè)二類SVM分類器.在構(gòu)造類別i和類別j的SVM子分類器時(shí)，在訓(xùn)練集中選取屬于類別i和類別j的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，并將屬于類別i的數(shù)據(jù)作為正類，將屬于類別j的數(shù)據(jù)作為負(fù)類.測(cè)試時(shí)，使用所有的子分類器處理所有的測(cè)試數(shù)據(jù)，比如1個(gè)子分類器判定x屬于第i類就意味著第i類獲得1票，最后票數(shù)最多的類別就是最終判定x所屬的類別［2］.這種方法需要構(gòu)造很多的二類分類器，對(duì)M類問(wèn)題就需要構(gòu)造2－1M(M－1)個(gè)子分類器.這樣就會(huì)使算法的訓(xùn)練時(shí)間較長(zhǎng)，而且實(shí)際上可能并不需要求解2－1M(M－1)個(gè)子分類器.比如在數(shù)字識(shí)別問(wèn)題中，計(jì)算了若干二類分類器之后，發(fā)現(xiàn)數(shù)字“7”和“8”的票都很少，已經(jīng)不可能成為勝出者，這時(shí)候再計(jì)算“7－8”分類器就成了一種浪費(fèi)［1］.

有向無(wú)環(huán)圖DAG(Directed Acyclic Graph)SVM算法在訓(xùn)練階段和one-against-one算法相同，也是采用任意兩兩組合的訓(xùn)練方式，同樣也需要2－1M(M－1)個(gè)子分類器.

但是在分類過(guò)程中，DAGSVM算法將所用的子分類器構(gòu)成有向無(wú)環(huán)圖，如圖1所示.圖中包括2－1M(M－1)個(gè)節(jié)點(diǎn)和M個(gè)葉子，其中每個(gè)節(jié)點(diǎn)是1個(gè)子分類器.當(dāng)處理未知數(shù)據(jù)時(shí)，從根節(jié)點(diǎn)開始分類，只需M－1步即可完成分類.因?yàn)閷?duì)于i－j分類器，如果判定某個(gè)數(shù)據(jù)屬于類i，那么它就不可能屬于類j，只可能屬于類j以外的類.和one-against-one算法相比，在分類過(guò)程中減少了重復(fù)操作，大大提高了分類速度［3］.這種分類方法的缺點(diǎn)是未考慮樣本不平衡數(shù)據(jù)對(duì)分類速度的影響，而且沒(méi)有考慮分類錯(cuò)誤傳遞對(duì)后續(xù)產(chǎn)生的影響［4］.

圖1 采用DAG實(shí)現(xiàn)5類分類

上面幾種算法都是構(gòu)造多個(gè)二類分類器并將它們組合起來(lái)，而第2種方法是直接在1個(gè)優(yōu)化公式中同時(shí)考慮所有子分類器的參數(shù)優(yōu)化.

初始問(wèn)題為［5］

其對(duì)偶問(wèn)題為

決策函數(shù)為

嚴(yán)格的講，其思想類似于one-against-rest方法，只不過(guò)是把k個(gè)二值SVM優(yōu)化問(wèn)題放在1個(gè)最優(yōu)化公式中同時(shí)優(yōu)化，所以它也存在與one-against-rest方法相同的缺點(diǎn).另外，這種思想盡管看起來(lái)簡(jiǎn)潔，但在最優(yōu)化問(wèn)題求解過(guò)程中，變量遠(yuǎn)遠(yuǎn)多于第1種，訓(xùn)練速度不及第1種，且分類精度也不占優(yōu)［2］.

2 基于類半徑的多類分類SVM

現(xiàn)有多類分類支持向量機(jī)算法大多都有效率低或樣本不平衡影響分類精度等不足，而且它們都沒(méi)有在訓(xùn)練前分析訓(xùn)練集.筆者提出一種基于類半徑的多類分類支持向量機(jī)算法，這種算法在訓(xùn)練前首先對(duì)訓(xùn)練集進(jìn)行分析，然后使用one-class SVM進(jìn)行分類.該算法效率較高而且克服了樣本不平衡所帶來(lái)的影響.

在多類分類問(wèn)題中，每個(gè)類的訓(xùn)練樣本數(shù)以及它所占的區(qū)域不同，在分類時(shí)需要區(qū)別對(duì)待.如果將所占區(qū)域小的類先分出來(lái)，而將所占區(qū)域大的類后分出來(lái)，這樣就會(huì)減少誤差.

根據(jù)上述思想提出了基于類半徑的多類分類支持向量機(jī)算法，具體步驟如下:步驟1 設(shè)已知訓(xùn)練集

其中 xi∈Rn，yj∈{1，2，…，M}，i=1，…，l;

步驟2 計(jì)算各類訓(xùn)練數(shù)據(jù)的中心和所占區(qū)域的半徑

其中nk為屬于第k類的樣本的個(gè)數(shù).

步驟3 對(duì)于每一類，使用one-class算法構(gòu)造分類器，具體算法為:

其決策函數(shù)為

步驟4 在測(cè)試時(shí)，首先對(duì)Rk從小到大排序;然后根據(jù)Rk對(duì)所有的類從小到大排序;最后按類的順序用各類的決策函數(shù)處理數(shù)據(jù).若fj(x)=1，則輸入x屬于類 j，后面類的決策函數(shù)不再處理此數(shù)據(jù).

在多類分類問(wèn)題中，所占區(qū)域越小的類就越容易處理而且它包含其它類數(shù)據(jù)的概率也越小，而所占區(qū)域較大的類就容易包含其它的數(shù)據(jù).所以該算法首先根據(jù)類半徑對(duì)各類從小到大排序，然后再進(jìn)行分類，這樣不僅減少誤差而且簡(jiǎn)化了算法.該算法使用one-class SVM算法構(gòu)造子分類器，不僅避免了訓(xùn)練數(shù)據(jù)不平衡的問(wèn)題，而且提高了算法的效率.

3 仿真實(shí)驗(yàn)

使用機(jī)器學(xué)習(xí)UML標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中的數(shù)據(jù)集，對(duì)one-against-rest，one-against-one，DAG 等算法和新算法分別進(jìn)行實(shí)驗(yàn)測(cè)試.表1列出了所用數(shù)據(jù)集的一些信息.

表1 試驗(yàn)數(shù)據(jù)集統(tǒng)計(jì)表

試驗(yàn)中使用的各種算法均采用MatLab R2006a實(shí)現(xiàn)，其中的二值SVM是在LIBSVM工具包基礎(chǔ)上修改實(shí)現(xiàn)，試驗(yàn)中使用 RBF核函數(shù)，K(x，x')=exp(－γ‖x－x'‖2).試驗(yàn)平臺(tái)為 P4 3.0G，512M RAM的方正PC，操作系統(tǒng)為Windows Server 2003.試驗(yàn)結(jié)果見表2.

表2 試驗(yàn)結(jié)果

由結(jié)果可知，新算法的訓(xùn)練時(shí)間比其它幾種算法較少.該算法雖然在訓(xùn)練前要對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分析，計(jì)算各類所占區(qū)域的半徑并排序，但是由于算法只用正類進(jìn)行訓(xùn)練所以節(jié)省了時(shí)間.其它幾種算法要構(gòu)造很多的二類分類器，所以訓(xùn)練時(shí)間較長(zhǎng).

4 結(jié)語(yǔ)

提出了基于類半徑的多類分類支持向量機(jī)算法.試驗(yàn)結(jié)果說(shuō)明，該算法的分類精度較高，而且可以節(jié)省訓(xùn)練時(shí)間.同時(shí)也說(shuō)明，將預(yù)先分析訓(xùn)練集的思想用于多類分類支持向量機(jī)算法，會(huì)得到較好的效果.

［1］鄧乃揚(yáng)，田英杰.數(shù)據(jù)挖掘中的新方法——支持向量機(jī)［M］.北京:科學(xué)出版社，2004.

［2］ Hsu C，Lin C.A comparison of methods for multi-class Support Vector Machines［J］.IEEE Trans on Neural Networks，2002，13(2):415 －425.

［3］ Boonserm Kijsirkul，Nitiwut Ussivakul.Multiclass support Vector Machines using adaptive directed acyclic graph［C］//IEEE/INNS International Joint Conference on Neural Networks(IJCNN—2002).Honolulu Hawaiian USA:Department of Information Systems Science，F(xiàn)aculty of Engineering，Soka University，2002:980 －985.

［4］鄭勇濤，劉玉樹.支持向量機(jī)解決多分類問(wèn)題研究［J］.計(jì)算機(jī)工程與應(yīng)用，2005(23):190－192.

［5］ J Weston，C Watkins.Multi-class Support Vector Machines［M］.Brussels:D Facto Press，1999.