陳青鋒，秦 拯,何 流，陳 麟

(1.湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙 410082;2.武漢大學(xué)國際軟件學(xué)院，湖北 武漢 430079;3.湖南省氣象技術(shù)裝備中心，湖南 長沙 410007)

一種高準(zhǔn)確度多分類結(jié)構(gòu)選擇方法*

陳青鋒1，秦 拯1,何 流2，陳 麟3

(1.湖南大學(xué)信息科學(xué)與工程學(xué)院，湖南 長沙 410082;2.武漢大學(xué)國際軟件學(xué)院，湖北 武漢 430079;3.湖南省氣象技術(shù)裝備中心，湖南 長沙 410007)

支持向量機SVM是目前最流行的二分類算法之一。現(xiàn)實生活中數(shù)據(jù)集大多要求能夠進行多分類，而有向無環(huán)圖DAG方法是將SVM應(yīng)用擴展到多分類的用得最多的方式之一,它調(diào)用分類器次數(shù)較少，執(zhí)行速度快，但是由于有錯誤向下累積和分類偏向性等情況存在，會影響DAG分類結(jié)果的準(zhǔn)確度。在使用DAG-SVM的時候，對于k種類別有k！種不同的備選結(jié)構(gòu)，根據(jù)數(shù)據(jù)集特性選擇合適的DAG結(jié)構(gòu)能夠有效提高結(jié)果的準(zhǔn)確度。提出使用估計準(zhǔn)確度的方法，從備選結(jié)構(gòu)中用窮舉法選擇出最高準(zhǔn)確度估計值的DAG結(jié)構(gòu)，以此作為測試集的結(jié)構(gòu)進行分類。實驗結(jié)果表明，相較其它方法，測試數(shù)據(jù)集采用該方法選擇的DAG結(jié)構(gòu)后的分類準(zhǔn)確性得到顯著提高，在對類別數(shù)量不太多的數(shù)據(jù)集進行多類分類時有較好的效果。

支持向量機；多分類；DAG-SVM；結(jié)構(gòu)選擇

1 引言

隨著機器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域的發(fā)展，越來越多的復(fù)雜分類問題需要人們來處理，例如金融市場、天氣預(yù)報等等都需要大量包含多個特征的互相關(guān)聯(lián)的數(shù)據(jù)來進行正確地判斷。需要正確的將這些數(shù)據(jù)分類才能用于實際問題的分析。針對不同的模型，有不同的分類器可以選擇，現(xiàn)在較流行的有：Bayes分類器、BP神經(jīng)網(wǎng)絡(luò)分類器、決策樹、支持向量機SVM(Support Vector Machine)算法等。

支持向量機[1]由Vapnik V N在1998年提出，是一種基于結(jié)構(gòu)風(fēng)險最小化的分類方法。由于其不會陷入局部極小值、對高維度的適應(yīng)性強、且在統(tǒng)計樣本量較少的情況下也能獲得良好統(tǒng)計規(guī)律的特點，使得SVM倍受學(xué)者們的青睞，從而迅速地發(fā)展起來。文獻[2]對支持向量機算法和相關(guān)理論進行了綜述。SVM最初設(shè)定為一種二分類模型，基本模型定義為特征空間上間隔最大的線性分類器，而實際情況中經(jīng)常需要針對多類進行分類，因此出現(xiàn)了一對一、一對其余、決策樹和有向無環(huán)圖DAG(Directed Acycline Graph)等SVM的擴展方法。文獻[3，4]對主要的SVM多分類方法進行了研究，得出了一對一和DAG的方式分類精度較高，比其它的方式更適合實際應(yīng)用的結(jié)論。

目前提出了有多種針對多類分類的SVM改進方法。Chen P等人[5]提出了一種基于二分決策圖表和Huffman編碼的DAG結(jié)構(gòu)。易輝等人[6]提出了根據(jù)樣本數(shù)據(jù)的空間分布來優(yōu)化結(jié)構(gòu)的方法。文獻[7]從誤分成本出發(fā)提出了一種對分類成本敏感的模型，降低了誤分成本，使得即使出現(xiàn)一些誤分結(jié)果也能把壞的影響降低到最小，但是沒有提高準(zhǔn)確度。文獻[8]定義類的相似度為類別之間的距離，只對距離超過閾值的兩個類別之間訓(xùn)練分類器，從而降低了需要訓(xùn)練的分類器個數(shù)，簡化了DAG結(jié)構(gòu)。蔡軍等人[9]提出了一種改進的DAG拓?fù)浣Y(jié)構(gòu)構(gòu)成的DAG-SVM多分類器，用于機器人的手勢識別。

除了上述這些基于SVM的多分類學(xué)習(xí)方法之外，還提出很多其他多分類學(xué)習(xí)方法。Rokach L等人[10]提出了使用包含所有類別的最小子集集合覆蓋問題的多分類估計算法；Jesse R等人[11]提出構(gòu)造超類分隔區(qū)域并且以此訓(xùn)練分類器，將超類作為原始類來決定各個類別的歸屬；Ricardo N等人[12]給出使用固定大小內(nèi)存處理實際上大小無限的序列的數(shù)據(jù)流應(yīng)用的多分類標(biāo)記的文本文件的方法；Nicolas R等人[13]給出了基于實例推論的MICBR系統(tǒng)，綜合算法時間復(fù)雜度和準(zhǔn)確度在現(xiàn)有方法中具有優(yōu)勢。Montanes E等人[14]提出增強的二叉樹分類模型，有針對性地將配對的二分類器配置在二叉樹的相應(yīng)位置，從而提高多分類效率。

由于在前面已有的各個多分類方法中最終分類準(zhǔn)確度受到目標(biāo)數(shù)據(jù)集特性的影響較大，以及臨場采用方法的隨機性影響，分類結(jié)果準(zhǔn)確性難以保持在較高的程度。本文提出基于DAG-SVM多分類結(jié)構(gòu)準(zhǔn)確度的估算方法，從備選結(jié)構(gòu)中用窮舉法逐一估算準(zhǔn)確度，選擇出最高準(zhǔn)確度估計值的DAG結(jié)構(gòu)作為結(jié)果。實驗結(jié)果顯示，本方法具有一定的可行性。

本文的結(jié)構(gòu)如下：第2節(jié)介紹DAG-SVM及分類偏見問題；第3節(jié)介紹模型準(zhǔn)確度計算方法與原則;第4節(jié)給出實驗結(jié)果；最后一節(jié)給出結(jié)論。

2 基本概念

2.1 有向無環(huán)圖支持向量機DAG-SVM

DAG方法最初是由Platt J C等人[15]提出的，DAG-SVM訓(xùn)練階段采用一對一的方式，在判別階段采用有向無環(huán)圖方式，它的優(yōu)點在于能夠避免冗余決策、樣本失衡及盲區(qū)問題，因此經(jīng)常在多分類中被使用。但是，對于k類分類問題，使用DAG-SVM方法會存在k!種不同的結(jié)構(gòu)，有可能導(dǎo)致不同的分類結(jié)果。因此，使用DAG-SVM時的關(guān)鍵在于如何根據(jù)需要選擇合適的結(jié)構(gòu)。

有向無環(huán)圖支持向量機(DAG-SVM)是由Platt J C提出的決策導(dǎo)向的無環(huán)圖DAG導(dǎo)出，是針對一對一SVM存在誤分、拒分現(xiàn)象而提出的。該方案在訓(xùn)練階段訓(xùn)練(k(k-1))/2個分類器，在預(yù)測階段構(gòu)造一個具有(k(k-1))/2個節(jié)點和k個葉子節(jié)點的有向無環(huán)圖結(jié)構(gòu)，圖中每個普通節(jié)點代表一個SVM分類器，每個葉子表示一個類別。當(dāng)對測試樣本預(yù)測時，從根節(jié)點開始預(yù)測，根據(jù)結(jié)果選擇下一層中的左節(jié)點和右節(jié)點繼續(xù)預(yù)測，直到到達葉子節(jié)點，得出預(yù)測結(jié)果。

與一對一方法不同，DAG-SVM預(yù)測時一共只需要k-1步，比一對一的(k(k-1))/2步次數(shù)少，因此分類速度較快。但是，DAG-SVM作為層次型結(jié)構(gòu)，若在分類的某個高層節(jié)點中出現(xiàn)錯誤，則在低層無法得到糾正，因此選擇合適的DAG結(jié)構(gòu)、提高DAG-SVM的準(zhǔn)確度，是一個值得研究的問題。

2.2 DAG分類偏見問題

在DAG-SVM方法中，一個k類分類問題需要用到分布在有向無環(huán)圖中k層的(k(k-1))/2個二分類器。在這個結(jié)構(gòu)中，每個節(jié)點對應(yīng)一個SVM分類器，第i層有i個分類器。令“ai-aj”表示一個針對類別ai和aj的分類器，則DAG-SVM第一層節(jié)點為“a1-ak”,第k-1層的節(jié)點為“a1-a2”,“a2-a3”,…,“ak-1-ak”且i層的第j個節(jié)點(i,j)為“aj-ak+j-i”。如圖1所示。

Figure 1 DAG-SVM decision structure

測試樣本可以經(jīng)過k-1次分類后得到分類結(jié)果。但是，因為葉子節(jié)點ai(i=1，…，k)互相之間的位置可以變動，因此DAG-SVM的決策結(jié)構(gòu)并不是唯一的，不同的結(jié)構(gòu)可能導(dǎo)致不同的分類結(jié)果，稱之為決策偏見[4,6]。

令A(yù)(a,i,j)為類別a使用分類器SVM(i,j)分類正確的概率，p為SVM二分類器準(zhǔn)確度。給定如下定義：

則分類結(jié)果概率:

(1)

對于k=4，且樣本空間類別為a1的情況，路徑概率如圖2所示，可以計算對于類別1、2、3、4的分類準(zhǔn)確度。

R1=R4=p3

R2=A(2,1,4)*A(2,1,3)*p

R3=A(3,1,4)*A(3,2,4)*p

可見各個葉子節(jié)點之間存在分類偏見，使得不同位置分類的正確率一般情況下并不相同，在各類別分布不均的情況下，對總體的分類準(zhǔn)確性有較大影響。因此，需要進行適當(dāng)?shù)慕Y(jié)構(gòu)選擇，來平衡DAG的分類偏見，以獲取更高的分類準(zhǔn)確性。

Figure 2 Probability of the path when k=4,sample space type=a1

3 葉子節(jié)點正確率問題

3.1 DAG-SVM準(zhǔn)確率計算

3.2 算法實現(xiàn)

步驟2讀取路徑矩陣中的數(shù)值temp[x][y]，然后比較i和當(dāng)前m、n的值。若i不等于m和n中任一個，則E=E*A(i,m,n)，且若temp=0，m不變，則n=n-1。若temp=1,則m=m-1,n不變；若i=m且temp=0或者i=n且temp=1,則E=pE；若i=m且temp=1或者i=n且temp=1，則E=(1-p)E。無論屬于哪種情況，temp讀取的位置y=y+1。

4 實驗

為了評估本方法的實際作用，采用UCI庫中的數(shù)據(jù)集來進行實驗，分別為Iris、Wine、Poker-hand、Glass、Vehicle、Segment和Letter。實驗環(huán)境為PC機(CPU:I5-2520M,2.50 GHz,內(nèi)存4.00 GB),比較對象使用Matlab工具箱LIBSVM提供的1-v-1、1-v-r、DAG算法和文獻[17]中的MBSVM算法。MBSVM是一種通過提前避免為相似度低于規(guī)定閾值的兩個類別訓(xùn)練分類器，從而降低了訓(xùn)練時間的方法。在這三個數(shù)據(jù)集中使用高精確化方案進行準(zhǔn)確度估值處理，從所有結(jié)構(gòu)中選出具有最高精確度的備選項，然后與1-v-1、1-v-r，原始DAG-SVM方案及MBSVM作準(zhǔn)確性和運行時間的比較。

表1為各數(shù)據(jù)集的詳細(xì)情況，其中Attributes為具有的屬性個數(shù)，Instances是樣本集總數(shù)，Training是樣本集用于訓(xùn)練的樣本數(shù)，Class是樣本具有的類別個數(shù)。對于每個數(shù)據(jù)集，先產(chǎn)生相關(guān)類別數(shù)的全排列0-1矩陣，然后使用本文的方法計算加權(quán)準(zhǔn)確度，選出最高的估計分類正確數(shù)情況下的DAG結(jié)構(gòu)。

Table 1 Description of the dataset表1 數(shù)據(jù)集描述

表2和表3中的數(shù)據(jù)為測試集20次實驗結(jié)果的平均值。從表2可以觀察得到，對于實驗中的七個數(shù)據(jù)集，本方法和其它的方法相比都能夠提升分類結(jié)果的準(zhǔn)確度。對于本身分類性能較好的數(shù)據(jù)集來說，分類結(jié)果會得到略微的提升，而對于本身分類性能較差的Glass和Vehicle兩個數(shù)據(jù)集，使用Improved-DAG分類后對準(zhǔn)確度的提升較大。

對于表3，總體上MBSVM由于需要訓(xùn)練的分類器比其它方案少，因此運行時間最快。而本方案需要在使用DAG-SVM方法前建立路徑概率矩陣及進行遍歷，因此比1-v-1、原始DAG和MBSVM方法耗時略多，比1-v-r方法速度要快。從類別數(shù)量看，類別數(shù)量較多的Letter數(shù)據(jù)集，可以看出實驗時間消耗較其他方法明顯要多，而同樣為樣本數(shù)較大的Poker-hand由于不同類別數(shù)僅有10個，所以由于構(gòu)建路徑矩陣所耗時的增加量相對于龐大的記錄條數(shù)反而不明顯，因此在類別數(shù)較少的數(shù)據(jù)集中，記錄數(shù)即使很大也不會對Improved-DAG方法有較大影響，而如果類別數(shù)過多則本方法不適用。

Table 2 Accuracy result of the experiment表2 實驗準(zhǔn)確度結(jié)果 %

Table 3 Executing time of the experiment表3 實驗時間結(jié)果 ms

實驗結(jié)果顯示，與其他三種方法相比，對于特性不同的七種實驗數(shù)據(jù)集，在使用本文提出的Improved-DAG方法后準(zhǔn)確度都得到了提升。對于本方法，最適合的應(yīng)用場景是類別數(shù)較少且數(shù)據(jù)集規(guī)模較大的情況，此時對整體準(zhǔn)確度的提升較大，且對時間的消耗增加不明顯。

5 結(jié)束語

DAG-SVM是目前最常使用的SVM多分類策略之一。作為一種k層k！種結(jié)構(gòu)的分類方法，它的性能則主要由對象數(shù)據(jù)集特性和本身的結(jié)構(gòu)來決定?？紤]到DAG-SVM的分類偏見問題，如何針對特定的需要來選擇合適的DAG結(jié)構(gòu)，是應(yīng)用DAG-SVM時面對的主要問題。本文以提高分類準(zhǔn)確率為目的，提出了一種新的DAG-SVM結(jié)構(gòu)選擇方法，通過計算DAG葉子節(jié)點的分類準(zhǔn)確度來估計整體分類準(zhǔn)確度，從而選擇出最優(yōu)DAG結(jié)構(gòu)。在UCI庫提供的七個數(shù)據(jù)集上的實驗表明，采用此方法能夠有效提升分類準(zhǔn)確率，在準(zhǔn)確度上領(lǐng)先于現(xiàn)有的其他結(jié)構(gòu)選擇方案。

雖然本方案已經(jīng)被證明可行，但是仍有可改進之處：訓(xùn)練階段需要生成類別相關(guān)個數(shù)的路徑矩陣，耗時受到類別數(shù)影響，以及訓(xùn)練樣本與測試樣本數(shù)據(jù)直接的特征差異會對本方案的效果有一定影響。接下來的工作是優(yōu)化路徑矩陣的產(chǎn)生與遍歷過程，減少訓(xùn)練過程的時間消耗，降低對訓(xùn)練樣本結(jié)果的依賴性。

[1] Vapnik V N.Statistical learning theory[M].New York:Wiley,1998.

[2] Ding Shi-fei, Qi Bing-juan, Tan Hong-yan. An overview on theory and algorithm of support vector machines[J]. Journal of University of Electronic Science and Technology of China, 2011,40(11):2-10.(in Chinese)

[3] Hsu C W,Lin C J. A comparison of methods for multiclass support vector machines[J].IEEE Transactions on Neural Networks,2002,13(2):415-425.

[4] Abe S.Analysis of multiclass support vector machines[C]∥Proc of CIMCA,2003:385-396.

[5] Chen P, Liu S.An improved DAG-SVM for multi-class classification[C]∥Proc of the 5th International Conference on Natural Computation, 2009:460-462.

[6] Yi H,Song X, Jiang B, et al.Support vector machine based on nodes refined decision directed acyclic graph and its application to fault diagnosis[J].Acta Automatic Sinica,2010,36(3):427-432.

[7] Yi Hui, Song Xiao-feng, Jiang Bin. Structure selection for DAG-SVM based on misclassification cost minimization[J].International Journal of Innovative Computing, Information and Control,2011,7(2):5133-5143.

[8] Luckner M,Szyszko K.RBF ensemble based on reduction of DAG structure[C]∥Proc of the 2013 Federated Conference on Computer Science and Information Systems,2013:99-105.

[9] Cai Jun, Li Xiao-juan, Zhang Yi, et al. An improved DAGSVM hand gesture recognition approach and its application[J]. Control Engineering of China, 2013,41(5):957-959.(in Chinese)

[10] Rokach L,Schclar A,Itach E.Ensemble methods for multi-label classification[J].Expert Systems with Applications,2014,16(41):7507-7523.

[11] Jesse R,Concha B,Pedro L.Multi-dimensional classification with super-classes[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(7):1720-1733.

[12] Ricardo N,Ilias F, Nello C.Efficient classification of multi-labeled text strems by clashing[J].Expert Systems with Application,2014,41(11):5431-5450.

[13] Nicolas R,Sancho-Asensio A,Golobardes E,et al.Multi-label classification based on analog reasoning[J].Expert Systems with Applications,2013,40(15):5924-5931.

[14] Montanes E,Barranquero J,Diez J,et al.Enhancing directed binary trees for multi-class classification[J].Information Sciences,2013,223:42-55.

[15] Platt J C, Cristianini N, Shawe-Taylor J. Large margin DAG’s for multiclass classification[C]∥Proc of Advances in Neural Information Processing Systems,2000:547-553.

[16] Huang Zhen-long, Zheng Jun,Hu Wen-xin. Text classification based on inter-class separability DAG-SVM[J]. Journal of East China Nornal University(Natural Science),2013(3):209-218.(in Chinese)

[17] Zhi Xia-yang, Yuan Hai-shao, Xiang Sun-zhang. Multiple birth support vector machine for multi-class classification[J].Neural Computer & Application,2013,22(1):153-161.

附中文參考文獻：

[2] 丁世飛，齊丙娟，譚紅艷.支持向量機理論與算法研究綜述[J].電子科技大學(xué)學(xué)報,2011,40(1):2-10.

[9] 蔡軍，李曉娟，張毅，等.一種改進的DAGSVM手勢識別方法及其應(yīng)用[J].控制工程,2013,41(5):957-959.

[16] 黃振龍，鄭駿，胡文心.基于類間可分性DAG-SVM的文本分類[J].華東師范大學(xué)學(xué)報(自然科學(xué)版),2013(3):209-218.

陳青鋒(1988-),男，湖南長沙人，碩士生，研究方向為機器學(xué)習(xí)。E-mail:654603923@qq.com

CHEN Qing-feng,born in 1988,MS candidate,his research interest includes machine learning.

秦拯(1969-),男,湖南長沙人，博士，教授，研究方向為網(wǎng)絡(luò)與信息安全、大數(shù)據(jù)處理和云計算。E-mail:zqin@hnu.edu.cn

QIN Zheng,born in 1969,PhD,professor,his research interests include network and information security，big data processing，and cloud computing.

A highly accurate structure selection method for multi-class classification

CHEN Qing-feng1,QIN Zheng1,HE Liu2,CHEN Lin3

(1.School of Information Science and Engineering,Hunan University,Changsha 410082;2.International School of Software,Wuhan University,Wuhan 430079;3.Hunan Meteorological Equipment Center,Changsha 410007,China)

Support vector machine is one of the most popular binary classification algorithms,but data sets in the real world require multi-classification. Directed Acycline Graph (DAG) is one of the most used ways that expand SVM to support multi-class classification.DAG calls the classifiers less frequently and works faster than other methods.However,the accumulated mistakes cannot be cleared, and it has k! kinds of decision structures when dealing with k-class problems.Therefore structure selection becomes a key problem while using DAG-SVMs.In this paper we propose a highly accurate DAG structure selection method that uses the classificatory percentage in the training data sets to estimate the accuracy of the test data sets, and chooses the DAG structure with the highest accuracy. Experimental results show that compared with other methods,the proposed method can improve the classification accuracy of test data set dramatically and has a better effect in performing multi-class classification of the data sets without too many different types.

support vector machine;multi-classification;DAG-SVM;structure selection

1007-130X(2015)09-1777-06

2014-09-30;

2014-12-29基金項目：國家自然科學(xué)基金資助項目(61472131,61272546)

TP181

A

10.3969/j.issn.1007-130X.2015.09.029

通信地址：410082 湖南省長沙市湖南大學(xué)信息科學(xué)與工程學(xué)院

Address:School of Information Science and Engineering,Hunan University,Changsha 410082,Hunan,P.R.China