王文劍，梁志，郭虎升

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面對(duì)DR-SVM算法需構(gòu)造的子分類器數(shù)目進(jìn)行說明.在最好情況下，即數(shù)據(jù)集X＝X1∪X2∪…∪XN的N類數(shù)據(jù)在m（m＞2）維空間排成一個(gè)線性陣列，此時(shí)根據(jù)DR-SVM方法只需要N－1個(gè)子分類器（即只需在相鄰兩類數(shù)據(jù)之間構(gòu)造子分類器）.而在最壞情況下，令包含所有數(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)代表一類，共有N類，見圖4（a）所示.其中每一個(gè)分類器都由兩個(gè)類所共用.取其中基本立方體為最小單位進(jìn)行分析.

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

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

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

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

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

為方便描述，設(shè)D為N類數(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中的每類數(shù)據(jù)在原數(shù)據(jù)空間里找到其種子C1，C2，…，CN.

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

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

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

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

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

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

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

為驗(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)來衡量多類學(xué)習(xí)器的性能，即總體分類精度accuracy和單類分類精度correcti，式中Ti表示第i類樣本正確分類的數(shù)目，F(xiàn)i表示第i類樣本錯(cuò)誤分類的數(shù)目.

（1）總體分類精度accuracy.其定義為：

對(duì)于特殊數(shù)據(jù)集，對(duì)單類分類精度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ù)集中幾種多分類算法對(duì)應(yīng)的子分類器數(shù)目如表3（P229）所示.

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

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

表4 總體分類精度Table 4 Totality classification accuracy（%）

表5為幾種方法在單類最低分類率方面的比較.可以看到在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 單類最低分類精度Table 5 Minimum classification accuracy on individual class（%）

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

4 結(jié)論與展望

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

［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］李昆侖，黃厚寬，田盛豐.模糊多類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 決策樹多分類策略研究［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é)合特征選擇的二叉樹SVM 多分類算法［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