王文劍，梁志，郭虎升

（1.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006;2.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006）

基于數(shù)據(jù)關(guān)系的SVM多分類(lèi)學(xué)習(xí)算法

王文劍1，2，梁志2，郭虎升2

（1.山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，山西 太原 030006;2.山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，山西 太原 030006）

提出一種基于數(shù)據(jù)關(guān)系（Data Relationship，DR）的多分類(lèi)支持向量機(jī)（Support Vector Machine，SVM）學(xué)習(xí)算法（Multi-Classification SVM Algorithm Based on Data Relationship，DR-SVM）.DR-SVM 算法根據(jù)每類(lèi)數(shù)據(jù)的關(guān)系（如向量積等）獲取子學(xué)習(xí)器的冗余信息，從而優(yōu)化多分類(lèi)器組，然后通過(guò)經(jīng)典的SVM算法訓(xùn)練分類(lèi)器組.算法在簡(jiǎn)化分類(lèi)器組的同時(shí)可對(duì)多類(lèi)數(shù)據(jù)分類(lèi)問(wèn)題獲得滿意的泛化能力，在標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與經(jīng)典的SVM多分類(lèi)方法相比，DR-SVM具有更好的泛化性能，尤其對(duì)單個(gè)類(lèi)別精度要求較高的數(shù)據(jù)尤其有效.

支持向量機(jī);多分類(lèi);數(shù)據(jù)關(guān)系;泛化能力

0 引言

支持向量機(jī)是Vapnik等人提出的一種通用高效機(jī)器學(xué)習(xí)方法［1］，遵循結(jié)構(gòu)風(fēng)險(xiǎn)極小化原理，將問(wèn)題的求解轉(zhuǎn)化為一個(gè)凸二次規(guī)劃問(wèn)題的求解，由于支持向量機(jī)具有堅(jiān)實(shí)的理論基礎(chǔ)、簡(jiǎn)潔的表示方式及成熟的求解方法，目前已在時(shí)間序列預(yù)測(cè)、圖像識(shí)別、文本分析等諸多領(lǐng)域得到成功的應(yīng)用.最初提出的支持向量機(jī)模型用以求解兩類(lèi)分類(lèi)問(wèn)題，然后擴(kuò)展到求解回歸問(wèn)題，近年來(lái)盡管也有將其拓展至多類(lèi)分類(lèi)問(wèn)題的研究，但目前取得的研究成果相對(duì)還比較少.另外分類(lèi)器的訓(xùn)練原則、支持向量的選取、訓(xùn)練模型的推廣等都是多分類(lèi)SVM亟待解決的問(wèn)題.

目前，基于SVM 的多分類(lèi)方法主要有Knerr等人提出的一對(duì)多（One-against-rest）算法［2］，Botton等提出的一對(duì)一（one-against-one）方法［3］，Platt等在一對(duì)一方法的基礎(chǔ)上進(jìn)行改進(jìn)，提出的基于有向無(wú)環(huán)圖（Directed Acyclic Graph）的SVM多分類(lèi)算法（DAG-SVM）［4］，Weston等提出了全局優(yōu)化多分類(lèi)SVM分類(lèi)算法［5］.此外，模糊的SVM多分類(lèi)算法［6］以及決策樹(shù)算法［7－10］等幾年來(lái)也得到了廣泛關(guān)注.盡管目前提出了一些基于SVM的多分類(lèi)方法，但這些方法大多是將一個(gè)多分類(lèi)問(wèn)題拆解為多個(gè)二分類(lèi)問(wèn)題，從而在不同的數(shù)據(jù)區(qū)域進(jìn)行SVM的二分類(lèi)問(wèn)題求解，最后再把訓(xùn)練得到的多個(gè)SVM二分類(lèi)器進(jìn)行組合.這種方法得到的子分類(lèi)器往往冗余度較高，且分類(lèi)模型復(fù)雜，但多分類(lèi)器的泛化能力卻不一定強(qiáng).除采用分解策略之外，還可以直接求解一個(gè)多分類(lèi)全局優(yōu)化問(wèn)題，雖能避免子分類(lèi)器模型冗余問(wèn)題，但其時(shí)間復(fù)雜度往往太高，難以實(shí)際應(yīng)用.

本文提出一種基于向量?jī)?nèi)積關(guān)系的一對(duì)一支持向量機(jī)學(xué)習(xí)算法DR-SVM.DR-SVM算法根據(jù)多維空間每類(lèi)數(shù)據(jù)的內(nèi)積獲取子學(xué)習(xí)器的冗余信息，確定需要在哪些類(lèi)樣本之間構(gòu)造子學(xué)習(xí)器，然后通過(guò)SVM算法訓(xùn)練子分類(lèi)器組，使SVM在簡(jiǎn)化分類(lèi)器組的同時(shí)可獲得滿意的泛化能力.

1 經(jīng)典的多分類(lèi)支持向量機(jī)

1.1 支持向量機(jī)簡(jiǎn)介

SVM最早是針對(duì)二分類(lèi)問(wèn)題提出的，其基本思想是尋找兩類(lèi)樣本的最優(yōu)分類(lèi)面，使得兩類(lèi)樣本的分類(lèi)間隔最大.根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化（SRM）原理，SVM解決分二分類(lèi)問(wèn)題的過(guò)程即求解以下約束最優(yōu)化問(wèn)題：

1.2 一對(duì)多的SVM算法

對(duì)于N類(lèi)數(shù)據(jù)集，一對(duì)多方法就是利用SVM構(gòu)造N個(gè)兩類(lèi)子分類(lèi)器，將每類(lèi)數(shù)據(jù)與其它類(lèi)數(shù)據(jù)分開(kāi).構(gòu)造方法如下：第i個(gè)子分類(lèi)器是將第i類(lèi)數(shù)據(jù)作為正類(lèi)，其余N－1類(lèi)數(shù)據(jù)作為負(fù)類(lèi)，將多分類(lèi)問(wèn)題轉(zhuǎn)化為二分類(lèi)問(wèn)題，相應(yīng)的，優(yōu)化問(wèn)題轉(zhuǎn)化為：

1.3 一對(duì)一的SVM算法

1.4 有向無(wú)環(huán)圖的SVM算法

1.5 全局優(yōu)化的SVM多分類(lèi)算法

全局優(yōu)化的SVM多分類(lèi)方法通過(guò)修改目標(biāo)函數(shù)，把多分類(lèi)問(wèn)題轉(zhuǎn)換為解決單個(gè)優(yōu)化問(wèn)題.這種方法需求解以下約束優(yōu)化問(wèn)題：

這一問(wèn)題有理論上的最優(yōu)解，但求解極其困難.

圖1 五類(lèi)數(shù)據(jù)的DAG-SVM示意圖Fig.1 DAG-SVM for five-class data classification

2 DR-SVM 學(xué)習(xí)算法

在實(shí)際的多類(lèi)問(wèn)題求解中，一對(duì)一和一對(duì)多方法使用得最為普遍.對(duì)于同一個(gè)數(shù)據(jù)集，雖然一對(duì)一方法和一對(duì)多方法得到的分類(lèi)器組完全不同，都可以對(duì)數(shù)據(jù)進(jìn)行分類(lèi)，但由于一對(duì)一方法得到的支持向量較少，因而分類(lèi)時(shí)間也就更少.圖2為兩種分類(lèi)方法獲得的超平面示意圖，但無(wú)論是一對(duì)一方法還是一對(duì)多方法都有可能產(chǎn)生冗余分類(lèi)的情況（如圖2中陰影部分），即有些數(shù)據(jù)可能被分為幾類(lèi)（由不同的分類(lèi)器確定）或者被拒絕分類(lèi)（不屬于所有類(lèi)別）.因此，簡(jiǎn)化分類(lèi)器組合模型是提高多分類(lèi)支持向量機(jī)泛化能力的關(guān)鍵因素.

圖2 （a）一對(duì)多分類(lèi)示意圖 （b）一對(duì)一分類(lèi)示意圖Fig.2 （a）One-against-rest （b）One-against-one

本文主要研究基于一對(duì)一策略的多分類(lèi)支持向量機(jī)學(xué)習(xí)方法，針對(duì)一對(duì)一SVM分類(lèi)方法所訓(xùn)練的分類(lèi)器組合模型較為復(fù)雜、子分類(lèi)器個(gè)數(shù)較多及可能存在冗余分類(lèi)等問(wèn)題，提出一種基于向量?jī)?nèi)積運(yùn)算的SVM多分類(lèi)算法，以簡(jiǎn)化分類(lèi)器模型并提高分類(lèi)器的泛化能力.本文提出的DR-SVM方法根據(jù)不同類(lèi)別數(shù)據(jù)之間的關(guān)系構(gòu)造子分類(lèi)器，為使構(gòu)造的子分類(lèi)器個(gè)數(shù)最少而不影響分類(lèi)能力，首先在原空間中找到各類(lèi)數(shù)據(jù)的種子（可以是類(lèi)心等具有代表性的原始數(shù)據(jù)），通過(guò)各種子之間的向量積，確定各類(lèi)之間的分類(lèi)器是否需要構(gòu)造.如果種子之間的向量積不大于0，說(shuō)明這兩類(lèi)數(shù)據(jù)可能離得較遠(yuǎn)，這兩類(lèi)數(shù)據(jù)之間的子分類(lèi)器可以由其他的子分類(lèi)器代替，因而就不需要構(gòu)造這兩類(lèi)數(shù)據(jù)之間的子分類(lèi)器;否則子分類(lèi)器不能被約減，需構(gòu)造該子分類(lèi)器.如此循環(huán)迭代直到所有種子之間的向量積都大于0，即可構(gòu)造最簡(jiǎn)SVM多分類(lèi)器組合模型.

圖3（P227）為本文方法的示意圖.圖中A，B，C分別為三類(lèi)數(shù)據(jù)的種子，在（a）中，AB·AC＜0，這種情況下B，C兩類(lèi)數(shù)據(jù)之間子分類(lèi)器fBC可以由A，C之間的子分類(lèi)器fAC和A，B之間的子分類(lèi)器fAB表征，因此B，C之間的子分類(lèi)器不需要構(gòu)造.在（b）中，AB·AC＞0，僅用fAC和fAB無(wú)法將所有的B，C兩類(lèi)數(shù)據(jù)完全分開(kāi)，因此需要構(gòu)造B，C之間的子分類(lèi)器fBC.

圖3（a） 無(wú)需構(gòu)造子分類(lèi)器fBC （b）需要構(gòu)造子分類(lèi)器fBCFig.3（a）fBC can be omitted （b）fBC should be constructed

表1為幾種典型的多分類(lèi)學(xué)習(xí)方法需要構(gòu)造的子分類(lèi)器數(shù)目.其中DR-SVM算法在最好情況下需要構(gòu)造N－1個(gè)子分類(lèi)器，最壞情況下需要構(gòu)造9N個(gè)子分類(lèi)器，一般都小于一對(duì)一方法和有向無(wú)環(huán)圖方法.

表1 子分類(lèi)器數(shù)目Table 1 Number of subclassifiers

下面對(duì)DR-SVM算法需構(gòu)造的子分類(lèi)器數(shù)目進(jìn)行說(shuō)明.在最好情況下，即數(shù)據(jù)集X＝X1∪X2∪…∪XN的N類(lèi)數(shù)據(jù)在m（m＞2）維空間排成一個(gè)線性陣列，此時(shí)根據(jù)DR-SVM方法只需要N－1個(gè)子分類(lèi)器（即只需在相鄰兩類(lèi)數(shù)據(jù)之間構(gòu)造子分類(lèi)器）.而在最壞情況下，令包含所有數(shù)據(jù)的最小超球?yàn)镚，外接超立方體為H.將H網(wǎng)格化，為計(jì)算簡(jiǎn)單，設(shè)數(shù)據(jù)集X在m維空間均勻分布，則有X?G?H.在H內(nèi)，每個(gè)交叉點(diǎn)代表一類(lèi)，共有N類(lèi)，見(jiàn)圖4（a）所示.其中每一個(gè)分類(lèi)器都由兩個(gè)類(lèi)所共用.取其中基本立方體為最小單位進(jìn)行分析.

圖4 網(wǎng)格化后求子分類(lèi)器的數(shù)目Fig.4 Number of subclassification in the gridding hypercube

（1）若此基本立方體位于超立方體H的角上（如圖4（b）），按照DR-SVM算法每一類(lèi)則需要3個(gè)子分類(lèi)器，N類(lèi)數(shù)據(jù)需要N個(gè)子分類(lèi)器.

（2）若此基本立方體位于超立方體H的棱上（如圖4（c）），按照DR-SVM算法每一類(lèi)則需要4個(gè)子分類(lèi)器，N類(lèi)數(shù)據(jù)需要2N個(gè)子分類(lèi)器.

（3）若此基本立方體位于超立方體H內(nèi)（如圖4（d）），按照DR-SVM算法每一類(lèi)則需要18（6個(gè)面心、12個(gè)棱心）個(gè)子分類(lèi)器，N類(lèi)數(shù)據(jù)需要9N個(gè)子分類(lèi)器.

若數(shù)據(jù)集中的數(shù)據(jù)全部在超立方體H內(nèi)，即最壞情況下子分類(lèi)器數(shù)目是9N，一般都小于這一數(shù)目.

為方便描述，設(shè)D為N類(lèi)數(shù)據(jù)集，D＝X∪TE，X為訓(xùn)練集，X＝X1∪X2∪…∪XN，TE為測(cè)試集，TE＝TE1∪TE2∪…∪TEN.

DR-SVM學(xué)習(xí)算法的主要步驟如下：

Step 1：給定數(shù)據(jù)集D.

Step 2：對(duì)X中的每類(lèi)數(shù)據(jù)在原數(shù)據(jù)空間里找到其種子C1，C2，…，CN.

Step 3：通過(guò)歐式空間的向量關(guān)系計(jì)算出C1，C2，…，CN中每?jī)蓚€(gè)種子的內(nèi)積，將種子的數(shù)據(jù)關(guān)系記為R.

Step 4：按照數(shù)據(jù)關(guān)系R，確定需要在哪些類(lèi)數(shù)據(jù)之間需構(gòu)造子分類(lèi)器.

Step 5：根據(jù)訓(xùn)練集X，構(gòu)造相應(yīng)的子分類(lèi)器組合模型.

Step 6：在簡(jiǎn)化后的多分類(lèi)器組合模型上對(duì)TE進(jìn)行預(yù)測(cè).

DR-SVM學(xué)習(xí)算法通過(guò)在SVM訓(xùn)練之前進(jìn)行子學(xué)習(xí)器的約減，不僅可簡(jiǎn)化組合模型、提高預(yù)測(cè)速度，而且可以在一定程度上消除數(shù)據(jù)被分為多類(lèi)或數(shù)據(jù)拒絕分類(lèi)的問(wèn)題.

3 實(shí)驗(yàn)結(jié)果及分析

3.1 數(shù)據(jù)集說(shuō)明

為驗(yàn)證DR-SVM算法的效率，實(shí)驗(yàn)采用表2所示的UCI數(shù)據(jù)庫(kù)中5個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集［11］，每個(gè)數(shù)據(jù)集兩等分，其中任意一份作為訓(xùn)練集，另一份作為測(cè)試集，實(shí)驗(yàn)采用線性核函數(shù).

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Datasets used in experiments

3.2 算法評(píng)價(jià)指標(biāo)

本文采用兩個(gè)指標(biāo)來(lái)衡量多類(lèi)學(xué)習(xí)器的性能，即總體分類(lèi)精度accuracy和單類(lèi)分類(lèi)精度correcti，式中Ti表示第i類(lèi)樣本正確分類(lèi)的數(shù)目，F(xiàn)i表示第i類(lèi)樣本錯(cuò)誤分類(lèi)的數(shù)目.

（1）總體分類(lèi)精度accuracy.其定義為：

對(duì)于特殊數(shù)據(jù)集，對(duì)單類(lèi)分類(lèi)精度correcti較為敏感.

3.3 實(shí)驗(yàn)結(jié)果分析

為測(cè)試本文提出的DR-SVM算法的有效性，實(shí)驗(yàn)中將DR-SVM算法所得到的結(jié)果同一對(duì)一SVM算法、一對(duì)多SVM算法進(jìn)行了比較.在實(shí)驗(yàn)數(shù)據(jù)集中幾種多分類(lèi)算法對(duì)應(yīng)的子分類(lèi)器數(shù)目如表3（P229）所示.

表3 子分類(lèi)器數(shù)目Table 3 Number of classifiers

表4為幾種方法在實(shí)驗(yàn)數(shù)據(jù)集上的總體分類(lèi)率比較.從表中可以看到在wine、iris、glass、letter數(shù)據(jù)集上DR-SVM方法比一對(duì)一SVM方法的總體分類(lèi)率分別高出20.0%、2.0%、4.1%、2.8%，比一對(duì)多SVM方法分別高出7.1%、1.8%、8.4%、3.0%，在vovel數(shù)據(jù)集上，DR-SVM 方法分類(lèi)率介于一對(duì)一SVM 方法與一對(duì)多SVM方法之間.在大部分實(shí)驗(yàn)數(shù)據(jù)集上，DR-SVM算法的總體分類(lèi)率具有明顯優(yōu)勢(shì).

表4 總體分類(lèi)精度Table 4 Totality classification accuracy（%）

表5為幾種方法在單類(lèi)最低分類(lèi)率方面的比較.可以看到在wine、glass、letter數(shù)據(jù)集上，DR-SVM方法比一對(duì)一SVM 方法分別高出20.3%、17.1%、0.4%，比一對(duì)多SVM 方法分別高出12.2%、15.6%、1.4%;在iris數(shù)據(jù)集上DR-SVM方法比一對(duì)一SVM方法高2.0%，比一對(duì)多SVM方法低2.0%;在vovel數(shù)據(jù)集上DR-SVM方法比一對(duì)一SVM方法、一對(duì)多SVM方法分別低4.6%，15.1%.

表5 單類(lèi)最低分類(lèi)精度Table 5 Minimum classification accuracy on individual class（%）

實(shí)驗(yàn)結(jié)果表明，在絕大部分?jǐn)?shù)據(jù)集上，DR-SVM算法的總體分類(lèi)率明顯好于其它多分類(lèi)方法，且子分類(lèi)器數(shù)目較少，分類(lèi)模型簡(jiǎn)單.在大部分?jǐn)?shù)據(jù)集上，DR-SVM算法的單類(lèi)最低分類(lèi)率也明顯高于傳統(tǒng)的幾種多分類(lèi)算法.因此，本文提出的DR-SVM多分類(lèi)算法在簡(jiǎn)化訓(xùn)練模型提高多分類(lèi)器泛化能力方面是有效的.

4 結(jié)論與展望

本文根據(jù)向量?jī)?nèi)積數(shù)據(jù)關(guān)系提出一種一對(duì)一多分類(lèi)學(xué)習(xí)方法，通過(guò)約減子分類(lèi)器的數(shù)目，簡(jiǎn)化了多分類(lèi)組合模型，提高了分類(lèi)器的泛化能力.與經(jīng)典的一對(duì)一方法、多對(duì)一方法及有向無(wú)環(huán)圖方法相比，本文提出的方法在總體分類(lèi)準(zhǔn)確率、單類(lèi)分類(lèi)準(zhǔn)確率、訓(xùn)練模型等各方面有較大改進(jìn)，尤其是對(duì)單類(lèi)分類(lèi)率不能過(guò)低的問(wèn)題具有明顯優(yōu)勢(shì).在以后的研究工作中，將進(jìn)一步研究多種數(shù)據(jù)關(guān)系以簡(jiǎn)化多分類(lèi)器模型，以提高預(yù)測(cè)速度和分類(lèi)能力，同時(shí)將進(jìn)行更多的仿真實(shí)驗(yàn)，并將研究成果應(yīng)用于文本分類(lèi)、電子郵件過(guò)濾等實(shí)際問(wèn)題中.

［1］Vapnik V.Statistical Learning Theory［M］.New York：Wiley，1998.

［2］Knerr U H G.Pairwise Classification and Support Vector Machines［M］.MA：MIT Press，1999：255-268.

［3］Hsu C W，Lin C J.A Comparison of Methods for Multi-class Support Vector Machines［J］.IEEETransactionsonNeural Networks，2002，13（2）：415-425.

［4］Platt J C，Cristianini N，Shawe Taylor J.Large Margin DAGs for Multiclass Classification［J］.AdvancesinNeuralInformationProcessingSystems，2000，12（3）：547-553.

［5］Weston J，Watkins C.Modeling Multi-class Support Vector Machines［R］.Technical Report CSD-TR-90-84，Department of Computer Science，University of London，1998：1-10.

［6］李昆侖，黃厚寬，田盛豐.模糊多類(lèi)SVM 模型［J］.電子學(xué)報(bào)，2004，32（5）：830-832.

［7］Takahashi F，Abe S.Decision Tree-based Multiclass Support Vector Machines［C］／／Proceedings of the Annual Conference of the Institute of Systems，Control and Information Engineers，Singapore，2002，3：1418-1422.

［8］連可，黃建國(guó)，王厚軍，等.一種基于遺傳算法的SVM 決策樹(shù)多分類(lèi)策略研究［J］.電子學(xué)報(bào)，2008，36（8）：1502-1507.

［9］Arun Kumar M，Gopal M.Reduced one-against-all Method for Multiclass SVM Classification［J］.ExpertSystemswith Applications，2011，38（11）：14238-14248.

［10］范柏超，王建宇，薄煜明.結(jié)合特征選擇的二叉樹(shù)SVM 多分類(lèi)算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，3（12）：2823-2825.

［11］UCI Machine Learning Repository［EB／OL］.2010，Available from：＜http：／／archive.ics.uci.edu／ml／＞.

A Multi-Classification SVM Algorithm Based on Data Relationship

WANG Wen-jian1，2，LIANG Zhi2，GUO Hu-sheng2
（1.KeyLaboratoryofComputationalIntelligenceandChinese InformationProcessingofMinistryofEducation，Taiyuan030006，China;2.SchoolofComputerandInformationTechnology，ShanxiUniversity，Taiyuan030006，China）

A multi-class support vector machine（SVM）algorithm was introduced based on data relationship（DR-SVM）.Through extracting redundant information of subclassifiers based on relationship between different class data（such as inner product of vectors and so on），the DR-SVM model can reduce the number of subclassifiers.Then the multi-classifiers can be trained by traditional SVM.In so doing，the obtained model can be simplified and the satisfactory generalization performance can be reached at same time.The experiment results on benchmark datasets demonstrate that comparing with several traditional multi-class SVM approaches，the DR-SVM possesses better performance.Especially，it is more efficient for some data processing problems like the predicting precision of individual class should be not under a threshold.

support vector machine;multi-classification;data relationship;generalization performance

TP18

A

0253-2395（2012）02-0224-07＊

2012-03-06

國(guó)家自然科學(xué)基金（60975035）;教育部博士點(diǎn)基金（20091401110003）;山西省自然科學(xué)基金（2009011017-2）;山西省研究生創(chuàng)新項(xiàng)目（20103021）

王文劍（1968－），女，山西太原人，博士，教授，主要從事機(jī)器學(xué)習(xí)，計(jì)算智能等方面的研究.Email：wjwang＠sxu.edu.cn