侯小麗，王建國，王佳麗

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

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

侯小麗1，王建國2，王佳麗2

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

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

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

0　引言

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

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

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

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

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

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

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

圖1　SVM擴展為多分類算法

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

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

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

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

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

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

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

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

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

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

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

1.3BT-SVM（Binary Tree SVM）算法

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

圖2　二叉樹分類原理

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

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

1.4DAG-SVM（Directed Acyclic Graph SVM）

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

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

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

2　4種多分類算法比較

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

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

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

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

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

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

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

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

3　測試結(jié)果及評價

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

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

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

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

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

表4　試驗結(jié)果

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

4　結(jié)論

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

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

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

［3］連可，黃建國，王厚軍，等.一種基于遺傳算法的SVM決策樹多分類策略研究［J］.電子學(xué)報，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ù)。