侯小麗，王建國(guó)，王佳麗

（1.太原城市職業(yè)技術(shù)學(xué)院，太原030027；2.北方自動(dòng)控制技術(shù)研究所，太原030006）

基于支持向量機(jī)的多目標(biāo)分類和識(shí)別

侯小麗1，王建國(guó)2，王佳麗2

（1.太原城市職業(yè)技術(shù)學(xué)院，太原030027；2.北方自動(dòng)控制技術(shù)研究所，太原030006）

支持向量機(jī)（SVM）算法廣泛應(yīng)用于模式識(shí)別等領(lǐng)域，但是SVM最初是針對(duì)二類別分類提出，在多分類識(shí)別中稍顯遜色。對(duì)將SVM由二分類擴(kuò)展到多分類的算法進(jìn)行了研究，發(fā)現(xiàn)有向無(wú)環(huán)圖（DAG-SVM）是其中用的最多的算法之一。因此，針對(duì)軍事領(lǐng)域圖像的多目標(biāo)分類，選擇有向無(wú)環(huán)圖算法來(lái)實(shí)現(xiàn)軍事圖像中單兵、裝甲、低空等多目標(biāo)的分類識(shí)別。

支持向量機(jī)，多分類，傳感器技術(shù)

0　引言

隨著傳感器技術(shù)的不斷發(fā)展和信息化程度的提高，圖像處理技術(shù)在民用和軍用領(lǐng)域發(fā)揮了越來(lái)越重要的作用。在軍用領(lǐng)域，很多裝備都已經(jīng)安裝有CCD、紅外等圖像傳感器，實(shí)時(shí)捕捉戰(zhàn)場(chǎng)圖像進(jìn)行處理，提高了裝備的搜索和識(shí)別能力，縮短了作戰(zhàn)反應(yīng)時(shí)間。對(duì)圖像中提取的目標(biāo)進(jìn)行分類的速度和精度直接影響著后續(xù)的決策和作戰(zhàn)的成敗，在圖像處理環(huán)節(jié)具有重要的作用。目前，用于分類的方法很多，有Bayesian方法、距離判別、Fisher判別、k-近鄰分類以及分段線性分類、神經(jīng)網(wǎng)絡(luò)分類和支持向量機(jī)（SVM）等。

SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論（SLT，Statistical Learning Theory）的分類器，它以統(tǒng)計(jì)學(xué)習(xí)理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理作為理論依據(jù)，克服了傳統(tǒng)分類方法“過(guò)學(xué)習(xí)”和局部最小值等缺點(diǎn)，SVM的另一個(gè)重要的優(yōu)點(diǎn)是可以處理線性不可分的情況，首先要從原始空間中抽取特征，將原始空間中的樣本向量映射到線性可分的高維特征空間中，以解決原始空間中線性不可分問(wèn)題，是一種優(yōu)秀的二分類器。而現(xiàn)實(shí)生活中往往遇到的是多分類問(wèn)題，如字符識(shí)別，在軍事目標(biāo)的識(shí)別中，面臨的也是多類別的分類和識(shí)別問(wèn)題，如坦克、單兵和低空目標(biāo)等。

1　基于SVM的多分類器方法介紹

多分類問(wèn)題用數(shù)學(xué)語(yǔ)言可以描述為：

其中xi∈X=Rn，yi∈Y=｛1，2，…，M｝，i=1，…，l，尋找一個(gè)決策函數(shù)f（x）：X=Rn→Y。

從公式可以看出，求解多分類問(wèn)題，就是尋找把Rn上的點(diǎn)分成M部分的規(guī)則。

SVM分類器是一種典型的二分類器，如果把SVM推廣，使得它能夠處理多分類問(wèn)題，是一個(gè)值得研究的方向，現(xiàn)有的擴(kuò)展算法主要采用構(gòu)造和組合多個(gè)二類分類器進(jìn)行實(shí)現(xiàn)，其原理如圖1所示。目前擴(kuò)展算法主要包括兩個(gè)關(guān)鍵步驟：①將多分類問(wèn)題轉(zhuǎn)換為多個(gè)二類別分類問(wèn)題；②將多個(gè)二類分類器的輸出進(jìn)行組合，實(shí)現(xiàn)多類分類。

圖1　SVM擴(kuò)展為多分類算法

目前比較流行常用的算法主要包括：“一對(duì)多”算法（One Versus Rest，1-v-r）、“一對(duì)一”算法（One Versus One，1-v-1）、決策二叉樹(shù)算法（Binary Tree，BT）、有向無(wú)環(huán)圖算法（Directed Acyclic Graph，DAG）等。下面對(duì)這幾種算法分別進(jìn)行簡(jiǎn)單介紹。

1.11-V-R（One versus Rest）算法

假設(shè)輸入的數(shù)據(jù)共有K類，“一對(duì)多”算法需要構(gòu)造K個(gè)SVM分類器，第i（i＜K）個(gè)SVM分類器以第i類的樣本為正類，其余樣本為負(fù)類進(jìn)行訓(xùn)練?，F(xiàn)給定l條訓(xùn)練樣本：｛（x1，y1），（x2，y2），…，（xl，yl）｝，其中X為輸入數(shù)據(jù)，Y為分類標(biāo)記，那么第i個(gè)分類器的需要求解的問(wèn)題如下。

對(duì)K個(gè)分類器分別進(jìn)行計(jì)算，可得到K個(gè)決策函數(shù)，其中第i個(gè)決策函數(shù)為：fi（x）=（wi）Tφ（x）+bi，（i=1，2，…，K）；

對(duì)于未知樣本x，計(jì)算可得K個(gè)輸出值，然后對(duì)這K個(gè)值進(jìn)行判斷，以決定其分類。若只有一個(gè)+1出現(xiàn)，則可直接確定輸入樣本的類別；若輸出值不止一個(gè)+1，或者無(wú)+1的輸出值，則需判斷當(dāng)前輸出值的最大值，所對(duì)應(yīng)的類別為輸入樣本的類別。

該算法的優(yōu)點(diǎn)：只需要訓(xùn)練K個(gè)二類分類器，分類函數(shù)個(gè)數(shù)較少，分類速度較快；該算法的缺點(diǎn)：①每個(gè)二類分類器均需要全部樣本作為訓(xùn)練樣本，造成訓(xùn)練速度隨樣本數(shù)增加而減慢；②容易出現(xiàn)測(cè)試樣本同時(shí)屬于多類，或者不屬于任何類的情況；③不同分類器的判斷標(biāo)準(zhǔn)不同，可比性較差。

1.21-V-1（One versus One）算法

與“一對(duì)多”分類算法不同，“一對(duì)一”算法在進(jìn)行多類分類時(shí)，要構(gòu)造所有可能的二類分類器，因而共需要K（K-1）/2個(gè)分類器。例如，第i類和第j類的二類分類器的決策函數(shù)為：fi，j（x）=（wi，j）Tφ（x）+ bi，j，（i，j=1，2，…，K；i≠j）；

使用l個(gè)訓(xùn)練樣本，對(duì)第i類和第j類的分類器進(jìn)行訓(xùn)練，需要解決如下問(wèn)題。

所有二類別分類器構(gòu)造完成后，通常采用“投票法”對(duì)測(cè)試樣本進(jìn)行分類。首先將所有類別的票數(shù)初始化為0，然后將測(cè)試樣本通過(guò)決策函數(shù)計(jì)算，進(jìn)行二分類的類別判斷，若判斷當(dāng)前類別為i，則類別i的票數(shù)加1；在測(cè)試樣本經(jīng)過(guò)所有的二分類判別之后，對(duì)所有類別的票數(shù)進(jìn)行統(tǒng)計(jì)，票數(shù)最高的類別即為測(cè)試樣本的類別。

該算法優(yōu)點(diǎn)：訓(xùn)練速度相比于“一對(duì)多”算法較快；缺點(diǎn)：①分類器數(shù)目隨類別K增加而增大，隨之計(jì)算量增加，導(dǎo)致決策速度降低；②存在多個(gè)類別投票相同的情況，無(wú)法對(duì)測(cè)試樣本進(jìn)行分類的情況。

1.3BT-SVM（Binary Tree SVM）算法

決策二叉樹(shù)算法采用二叉樹(shù)方式，對(duì)多分類問(wèn)題進(jìn)行二分類問(wèn)題劃分，具體步驟如下：先將所有類別劃分為兩個(gè)子類，每個(gè)子類分別繼續(xù)劃分為兩個(gè)子類，以此類推，直到K個(gè)類別被劃分完畢。下頁(yè)圖2給出一個(gè)4類問(wèn)題的決策二叉樹(shù)分類原理，通過(guò)劃分，原來(lái)的多分類問(wèn)題被分解為一系列的二分類問(wèn)題，二分類問(wèn)題可采用SVM進(jìn)行分類實(shí)現(xiàn)。

圖2　二叉樹(shù)分類原理

該算法的優(yōu)點(diǎn)：①解決了前面兩種算法存在無(wú)法分類情況的問(wèn)題；②對(duì)于K類，只需要構(gòu)造K-1個(gè)二分類分類器；③對(duì)測(cè)試樣本進(jìn)行決策時(shí)，并不需要經(jīng)過(guò)所有分類器的判別，因而可以提高決策速度；

該算法缺點(diǎn)：①分類模型隨二叉樹(shù)結(jié)構(gòu)不同而變化，因而推廣性能較差；②誤差具有累積效應(yīng)，靠近二叉樹(shù)根部的誤差，將嚴(yán)重影響分類性能。

1.4DAG-SVM（Directed Acyclic Graph SVM）

DAG-SVM叫作有向無(wú)環(huán)圖SVM，是由Platt針對(duì)“一對(duì)一”算法存在誤分、拒分的問(wèn)題而提出的多分類方法。該算法在樣本訓(xùn)練階段，采用的方法與“一對(duì)一”算法相同，均需要訓(xùn)練K（K-1）/2個(gè)二類分類器；但與兩種算法在決策階段采用的方式不同，“一對(duì)一”在決策階段采用“投票法”對(duì)測(cè)試樣本進(jìn)行分類，而有向無(wú)環(huán)圖算法則需要構(gòu)造一個(gè)有向無(wú)環(huán)圖，該圖共有K（K-1）/2個(gè)節(jié)點(diǎn)和K個(gè)葉子節(jié)點(diǎn)，其中，每個(gè)節(jié)點(diǎn)代表一個(gè)二類別分類器，每個(gè)葉子節(jié)點(diǎn)代表一個(gè)類別。在進(jìn)行決策時(shí)，首先使用根節(jié)點(diǎn)的分類器進(jìn)行二分類判斷，根據(jù)分類結(jié)果選擇下一層的左節(jié)點(diǎn)或右節(jié)點(diǎn)繼續(xù)進(jìn)行決策，直至到達(dá)的最終葉子節(jié)點(diǎn)即為測(cè)試樣本所屬類別。

可以看出，DAG-SVM算法在決策時(shí)，所用到的二類分類器只有K-1個(gè)，相比“一對(duì)一”算法，決策速度有很大提高，且不存在誤分、拒分的情況。但也存在類似決策二叉樹(shù)分類算法的缺點(diǎn)：誤差累積效應(yīng)，靠近根節(jié)點(diǎn)的決策誤差會(huì)隨著后續(xù)判斷而增大，因此，開(kāi)始階段的決策尤其重要。

圖3為DAG SVM解決一個(gè)四類問(wèn)題（A、B、C和D）的示意圖。

2　4種多分類算法比較

本文對(duì)4種SVM多分類算法進(jìn)行了仿真試驗(yàn)，采用的仿真軟件為Matlab R2012b，使用Libsvm工具箱中的庫(kù)函數(shù)對(duì)數(shù)據(jù)集進(jìn)行訓(xùn)練和分類。試驗(yàn)所采用的數(shù)據(jù)集為UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中常用的4個(gè)多分類數(shù)據(jù)集：Iris，Grass，Wine，Vowel，這4個(gè)數(shù)據(jù)集的描述如表1所示，其中各個(gè)數(shù)據(jù)集的特征均經(jīng)歸一化處理為［-1，1］。

圖3　DAG-SVM多分類器示意圖

表1　所選數(shù)據(jù)集的基本描述

基于這4個(gè)數(shù)據(jù)集，本文從分類準(zhǔn)確率和訓(xùn)練所用時(shí)間兩個(gè)方面，對(duì)4種SVM多分類算法進(jìn)行比較。

采用十折交叉驗(yàn)證方法對(duì)數(shù)據(jù)集進(jìn)行訓(xùn)練和分類，具體步驟如下：①將數(shù)據(jù)集的樣本數(shù)據(jù)分為10組，其中9組用作訓(xùn)練樣本，剩下的1組作為測(cè)試樣本；②所有SVM分類器的核函數(shù)采用徑向基核函數(shù)，進(jìn)行二類別分類，因而兩個(gè)參數(shù)的值（C，γ）需要確定；③由于不同參數(shù)的設(shè)置會(huì)影響分類結(jié)果，本文采用Grid Search方法在C=［2-15，2-14，…，215］和γ=［2-15，2-14，…，215］尺度上進(jìn)行搜索，使最終所得參數(shù)在分類精度上達(dá)到最優(yōu)；④重復(fù)試驗(yàn)10次，使得10組中的每組數(shù)據(jù)均可作為一次測(cè)試樣本進(jìn)行分類，取10次試驗(yàn)的平均值作為分類精度和訓(xùn)練時(shí)間。表2和下頁(yè)表3分別為4種算法的分類精度和訓(xùn)練時(shí)間對(duì)比結(jié)果。

表2　4種多分類算法的分類精度對(duì)比（%）

表3　4種多分類算法的訓(xùn)練時(shí)間對(duì)比（second）

由表2，綜合分析4個(gè)數(shù)據(jù)集的分類精度，可以看到DAG-SVM算法的分類精度最高；由表3，可以看到DAG-SVM算法和1-v-1算法的訓(xùn)練時(shí)間最短。另外，由于DAG-SVM算法在對(duì)測(cè)試樣本進(jìn)行分類時(shí)，只需要經(jīng)過(guò)K-1個(gè)二類分類器的判斷，而1-v-1算法則需K（K-1）/2個(gè)分類器，因而DAG-SVM算法在決策速度上隨著類別的增加要高于1-v-1算法。因而選取DAG-SVM算法用于本文研究的軍事領(lǐng)域圖像中多目標(biāo)的識(shí)別，包括單兵、裝甲、直升機(jī)等。

3　測(cè)試結(jié)果及評(píng)價(jià)

通過(guò)對(duì)4種常用SVM多分類算法的對(duì)比，本文選擇DAG-SVM作為軍事圖像中三類目標(biāo)：?jiǎn)伪?、裝甲和直升機(jī)的分類。目前用于訓(xùn)練和測(cè)試的樣本數(shù)量各有300條，其中單兵、裝甲、直升機(jī)的樣本數(shù)各有100條，共有5個(gè)特征，在進(jìn)行訓(xùn)練和測(cè)試前，通過(guò)歸一化將特征值處理為［-1，1］。測(cè)試工作在一臺(tái)CPU為Intel（R）Core（TM）i7-3520M 2.9GHz，內(nèi)存4GB，Windows7操作系統(tǒng)的計(jì)算機(jī)上進(jìn)行，編程語(yǔ)言仍然使用Matlab R2012b。

針對(duì)3類目標(biāo)的分類，需要構(gòu)造如圖4的有向無(wú)環(huán)圖。

圖4　軍用三目標(biāo)分類構(gòu)造有向無(wú)環(huán)圖

由圖4可以看到，本文需要構(gòu)造3個(gè)SVM分類器，核函數(shù)仍采用徑向基核函數(shù)，利用樣本集中的300個(gè)訓(xùn)練樣本進(jìn)行訓(xùn)練，對(duì)參數(shù)值（C，γ）進(jìn)行求解；在參數(shù)求解過(guò)程中同樣使用Grid Search方法在C=［2-15，2-14，…，215］和γ=［2-15，2-14，…，215］尺度上進(jìn)行搜索，獲取分類精度最高的參數(shù)值。

訓(xùn)練完成之后，對(duì)樣本集的300個(gè)測(cè)試樣本進(jìn)行分類，本文對(duì)目標(biāo)的識(shí)別率和錯(cuò)誤率分別進(jìn)行統(tǒng)計(jì)，結(jié)果如表4。

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

由表4可以看出，DAG-SVM算法在軍事圖像中單兵、裝甲和直升機(jī)3種目標(biāo)的識(shí)別中取得了較好的效果。

4　結(jié)論

支持向量機(jī)（SVM）算法目前廣泛應(yīng)用于模式識(shí)別等領(lǐng)域，但是SVM僅在二類別分類問(wèn)題中具有優(yōu)異的性能，因而許多研究人員嘗試將SVM進(jìn)行推廣，使之可以解決現(xiàn)實(shí)中多分類問(wèn)題，本文對(duì)常用的基于SVM 4種多分類方法進(jìn)行了簡(jiǎn)要介紹，并使用Matlab進(jìn)行了訓(xùn)練與測(cè)試的仿真，根據(jù)仿真結(jié)果，最終選擇DAG-SVM算法用于軍事圖像中單兵、裝甲和直升機(jī)3種目標(biāo)的分類識(shí)別，并取得了較好的結(jié)果。

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

［2］孫剛.基于支持向量機(jī)的多分類方法研究［D］.大連：大連海事大學(xué)，2008.

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

［4］HSUCW，LINC J.A comparison ofmethods formulti-class support vectormachines［J］.IEEE Transactions on Neural Networks，2002，13（2）：415-425.

［5］PLATT J C，CRISTIANINI N，SHAWE T J.Large margin DAGs formulticlass classification［J］.Advance in Neural Information Processing Systems，2000，12（3）：547-553.

［6］WESTON J，WATKINS C.Modeling multi-class support vectormachines［R］.Technical Report CSD-TR-90-84，Department of Computer Science，University of London，1998：1-10.

M ultiTargetClassification and Recognition Based on Support Vector M achine

HOU Xiao-li1，WANG Jian-guo2，WANG Jia-li2
（1.Tayuan City Vocational Technology College，Tayiuan 030027，China；2.North Automatic Control Technology Institute，Taiyuan 030006，China）

Support Vector Machine（SVM），which was developed for binary classification initially，now is widely used in many research fields like pattern recognition.However，its application to multiclassification is inefficient.This paper did research on the extension algorithms of SVM from binary classification tomulti-classification，and found that Directed Acyclic Graph（DAG-SVM）is one of the most popularly used.Therefore，this paper focuses on its application ofmulti-classification in military area，and achieves recognition of many military objects，such as soldiers，armored cars，low altitude targets，and so on.

supportvectormachine，multi-classclassification，sensor technology

TM33

A

1002-0640（2016）09-0189-04

2015-07-05

2015-08-07

侯小麗（1980-），女，山西太原人，碩士。研究方向：軟件技術(shù)。