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

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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

2 基本概念

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

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

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

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

2.2 DAG分類(lèi)偏見(jiàn)問(wèn)題

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

Figure 1 DAG-SVM decision structure

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

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

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

(1)

對(duì)于k=4，且樣本空間類(lèi)別為a1的情況，路徑概率如圖2所示，可以計(jì)算對(duì)于類(lèi)別1、2、3、4的分類(lèi)準(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àn)各個(gè)葉子節(jié)點(diǎn)之間存在分類(lèi)偏見(jiàn)，使得不同位置分類(lèi)的正確率一般情況下并不相同，在各類(lèi)別分布不均的情況下，對(duì)總體的分類(lèi)準(zhǔn)確性有較大影響。因此，需要進(jìn)行適當(dāng)?shù)慕Y(jié)構(gòu)選擇，來(lái)平衡DAG的分類(lèi)偏見(jiàn)，以獲取更高的分類(lèi)準(zhǔn)確性。

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

3 葉子節(jié)點(diǎn)正確率問(wèn)題

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

3.2 算法實(shí)現(xiàn)

步驟2讀取路徑矩陣中的數(shù)值temp[x][y]，然后比較i和當(dāng)前m、n的值。若i不等于m和n中任一個(gè)，則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。無(wú)論屬于哪種情況，temp讀取的位置y=y+1。

4 實(shí)驗(yàn)

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

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

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

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

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

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

Table 3 Executing time of the experiment表3 實(shí)驗(yàn)時(shí)間結(jié)果 ms

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

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

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

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

[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.

附中文參考文獻(xiàn)：

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

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

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

陳青鋒(1988-),男，湖南長(zhǎng)沙人，碩士生，研究方向?yàn)闄C(jī)器學(xué)習(xí)。E-mail:654603923@qq.com

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

秦拯(1969-),男,湖南長(zhǎng)沙人，博士，教授，研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、大數(shù)據(jù)處理和云計(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基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61472131,61272546)

TP181

A

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

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

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