段同樂，張冬寧

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

?

二叉樹多分類SVM在目標(biāo)分群中的應(yīng)用

段同樂，張冬寧

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

摘要為了解決目標(biāo)分群?jiǎn)栴}，在研究目標(biāo)關(guān)鍵屬性的基礎(chǔ)上，提出一種基于二叉樹多分類支持向量機(jī)(SVM)的目標(biāo)分群方法。介紹了基于統(tǒng)計(jì)學(xué)習(xí)理論的支持向量機(jī)方法的基本原理和算法本身的理論優(yōu)勢(shì)，由于支持向量機(jī)的本質(zhì)是解決二分類問題的，因此如何建立支持多分類的支持向量機(jī)是研究的關(guān)鍵。采用基于二叉樹的多分類支持向量機(jī)算法，建立了解決目標(biāo)分群?jiǎn)栴}的算法模型，將分類器分布在各個(gè)節(jié)點(diǎn)上，從而構(gòu)成了多分類的支持向量機(jī)。將算法進(jìn)行軟件實(shí)現(xiàn)，并利用模擬數(shù)據(jù)對(duì)支持向量機(jī)進(jìn)行了訓(xùn)練，調(diào)整支持向量機(jī)參數(shù)，得到了較好的分群結(jié)果，證明了該方法的有效性。

關(guān)鍵詞目標(biāo)分群；二叉樹；支持向量機(jī)；統(tǒng)計(jì)學(xué)習(xí)理論

0引言

目標(biāo)分群是二級(jí)數(shù)據(jù)融合的關(guān)鍵步驟。在綜合考慮目標(biāo)位置、屬性和運(yùn)動(dòng)狀態(tài)等信息的基礎(chǔ)上，將類型相近、運(yùn)動(dòng)狀態(tài)相近、執(zhí)行相同任務(wù)或具有相同威脅的目標(biāo)進(jìn)行合并，簡(jiǎn)化對(duì)象域情況，給指揮員提供簡(jiǎn)單明了的視圖[1]。

分群的基本思想是對(duì)可用數(shù)據(jù)進(jìn)行分組,目前已經(jīng)有很多目標(biāo)分群方法研究[2]，如層次聚類、K均值動(dòng)態(tài)聚類和神經(jīng)網(wǎng)絡(luò)等，這些方法共同的理論基礎(chǔ)之一是統(tǒng)計(jì)學(xué)。傳統(tǒng)統(tǒng)計(jì)學(xué)研究的是樣本數(shù)目趨于無窮大時(shí)的漸進(jìn)理論，但在實(shí)際問題中，數(shù)據(jù)樣本往往是有限的。統(tǒng)計(jì)學(xué)習(xí)理論(Statistical Learning Theory，SLT)是一種專門研究小樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論[3,4]。

SVM是一種基于統(tǒng)計(jì)學(xué)習(xí)理論的機(jī)器學(xué)習(xí)方法[4]，由于其建立在結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則上，從而使得SVM分類器具有較好的推廣能力[5]。但SVM本質(zhì)上是一種二分類方法，而目標(biāo)分群?jiǎn)栴}是一個(gè)多分類問題，將二類分類拓展到多類分類是目前SVM研究的熱點(diǎn)問題[6]。本文提出基于二叉樹多分類的支持向量機(jī)方法，將目標(biāo)的屬性空間定義為分類樣本的特征空間，建立目標(biāo)分群的分類模型，通過樣本目標(biāo)的學(xué)習(xí)訓(xùn)練，調(diào)整模型參數(shù)，得到了較為理想的分群結(jié)果。

1常用的SVM多類分類算法

1.1　SVM基本思想

支持向量機(jī)是Vapnik等根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論提出的一種新的機(jī)器學(xué)習(xí)方法，其最大特點(diǎn)是根據(jù)Vapnik的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，盡量提高學(xué)習(xí)的泛化能力，即由有限的訓(xùn)練集樣本得到的小誤差仍能夠保證對(duì)獨(dú)立的測(cè)試集小的誤差。另外由于支持向量機(jī)算法是一個(gè)凸優(yōu)化問題，因此局部最優(yōu)解一定是全局最優(yōu)解，可防止過學(xué)習(xí)，這些特點(diǎn)是其他學(xué)習(xí)算法，如神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法所不及的。對(duì)于分類問題，支持向量機(jī)可簡(jiǎn)述為：在線性可分的情況下，有很多線性分類器可以把2類樣本分隔開，但是只有一個(gè)分類器能夠使2類樣本的分類間隔最大，這個(gè)線性分類器就是最優(yōu)分類超平面，與其它分類器相比，具有更好的泛化性。對(duì)于非線性情況，首先，將輸入空間中的樣本通過某種非線性函數(shù)關(guān)系映射到高維特征空間中，使2類樣本在此特征空間中線性可分；然后，在此特征空間中構(gòu)造一個(gè)最優(yōu)分類超平面。把2類樣本沒有錯(cuò)誤地分開就是保證經(jīng)驗(yàn)風(fēng)險(xiǎn)最小(為0)，使分類間隔的距離最大就保證置信范圍最小，從而使真實(shí)風(fēng)險(xiǎn)最小，如圖 1所示。

圖1　SVM基本思想

目標(biāo)分群?jiǎn)栴}在其特征空間中是線性不可分的，其最優(yōu)分類超平面的判別函數(shù)為：

1.2　核函數(shù)的選擇

核函數(shù)本質(zhì)上是一種映射函數(shù)，能夠?qū)⒌途S空間的非線性問題映射到高維空間中，變成線性問題進(jìn)行處理，而計(jì)算復(fù)雜度并沒有增加。常用的核函數(shù)有：

線性核函數(shù)(Linear function)

多項(xiàng)式核函數(shù)(Polynomial function)

徑向基核函數(shù)(Radial function，RBF)

Sigmoid核函數(shù)(Sigmoid function)

核函數(shù)的選擇實(shí)際上是選擇一組具有幾個(gè)參數(shù)的核，比如徑向基核函數(shù)中參數(shù)γ需要確定。并且，核函數(shù)的選擇必須適用于具體的樣本數(shù)據(jù)。當(dāng)缺乏可靠的條件時(shí)，在應(yīng)用中通過使用驗(yàn)證集或者交叉驗(yàn)證的方式來確定這些參數(shù)。

1.3　多分類SVM

將二分類SVM拓展到多分類SVM，本質(zhì)就是將一個(gè)多分類SVM按照一定的方法分解成多個(gè)二分類SVM，通過求解多個(gè)二分類SVM，達(dá)到求解多分類SVM的目的。常用的多分類SVM方法有1-v-1算法[7]、1-v-r算法[7]和有向無環(huán)圖算法[8]等。

1-v-1算法是對(duì)N類訓(xùn)練樣本中的任意2類構(gòu)造一個(gè)二類分類器，共構(gòu)造N(N-1)/2個(gè)分類器。其優(yōu)點(diǎn)是每個(gè)判別函數(shù)的支持向量數(shù)少，缺點(diǎn)是需要進(jìn)行大量的二次規(guī)劃計(jì)算，并且由于每次參與訓(xùn)練的樣本只有2類，容易造成錯(cuò)誤分類。

1-v-r算法是對(duì)N類訓(xùn)練樣本中的每一類和其余樣本構(gòu)造一個(gè)二類分類器，共構(gòu)造N個(gè)分類器。其優(yōu)點(diǎn)是算法簡(jiǎn)單，容易實(shí)現(xiàn)，并且計(jì)算速度較快，缺點(diǎn)是由于每個(gè)二類分類器的正負(fù)樣本規(guī)模嚴(yán)重不對(duì)稱，容易產(chǎn)生無法分類的樣本或?qū)儆诙鄠€(gè)類別的樣本。

有向無環(huán)圖算法構(gòu)造二類分類器的方法和1-v-1算法一樣，共構(gòu)造N(N-1)/2個(gè)分類器，由于利用了圖論中的有向無環(huán)圖的思想，將測(cè)試樣本輸入根節(jié)點(diǎn)，每次判別排除最不可能的一個(gè)類別，經(jīng)過N-1次后剩下的類別即為該樣本所屬的類別。其優(yōu)點(diǎn)是速度優(yōu)于1-v-1算法，缺點(diǎn)是沒有考慮分類錯(cuò)誤傳遞對(duì)后續(xù)分類產(chǎn)生的影響。

2基于二叉樹多分類SVM的目標(biāo)分群模型

2.1　二叉樹多分類SVM算法

鑒于1-v-1算法、1-v-r算法和有向無環(huán)圖算法的缺陷，本文采用二叉樹多分類SVM算法來解決目標(biāo)分群?jiǎn)栴}。二叉樹多分類SVM算法有2種[9]。一種是在把N類中最相近的N-1類看作一類，余下的一類看作一類，構(gòu)建一個(gè)二類分類器，進(jìn)行分類。然后在N-1類中，取出最相近的(N-1)-1類看作一類，把N-1類中余下的一類看作另一類，構(gòu)建第二個(gè)二類分類器。以此類推，直到最后兩類，如圖 2所示。對(duì)于N類問題，一共需要構(gòu)建N-1個(gè)二類分類器。其優(yōu)點(diǎn)是：① 構(gòu)建的二類分類器較少；② 不會(huì)產(chǎn)生無法分類的樣本或?qū)儆诙鄠€(gè)類別的樣本；③ 重復(fù)訓(xùn)練的樣本量少，訓(xùn)練和分類的速度較快。另一種是在每次分割成2個(gè)子類時(shí)，每個(gè)子類中可以包含多個(gè)類。本文采用第1種算法，即每次只分出一類。

圖2　二叉樹多分類SVM分類過程

2.2　目標(biāo)分群模型

對(duì)于目標(biāo)分群?jiǎn)栴}，用二叉樹多分類SVM算法進(jìn)行求解的過程如下[10]：

① 將目標(biāo)分群?jiǎn)栴}數(shù)據(jù)化。目標(biāo)分群?jiǎn)栴}中，樣本數(shù)據(jù)的特征包括：在某一時(shí)刻目標(biāo)所處位置的經(jīng)度、緯度、高度、航向、航速、目標(biāo)的敵我屬性、型號(hào)、類型和作戰(zhàn)任務(wù)[11]，共9維。由于SVM本質(zhì)上是基于距離進(jìn)行分類的算法，因此需要將特征的表示方式轉(zhuǎn)換為可距離化的數(shù)據(jù)。其中，經(jīng)度、緯度、高度、航向及航速本身已數(shù)值化，但需要統(tǒng)一量綱；敵我屬性、型號(hào)、類型和作戰(zhàn)任務(wù)則需要數(shù)值化，即用數(shù)值表示語義。

② 對(duì)特征數(shù)據(jù)歸一化。每個(gè)特征的取值范圍有很大差異，為了避免大數(shù)值范圍的特征主宰小數(shù)值范圍的特征，需要對(duì)特征數(shù)據(jù)進(jìn)行歸一化，以降低支持向量對(duì)某些特征的過度依賴。歸一化通常是將每個(gè)特征縮放到[-1，+1]或者[0，1]這個(gè)范圍。

③ 選擇核函數(shù)。本文采用RBF核函數(shù)。

④ 采用二叉樹多分類SVM算法將目標(biāo)分群?jiǎn)栴}轉(zhuǎn)化為多個(gè)二分類問題。

算法分為訓(xùn)練和分類2個(gè)階段，訓(xùn)練階段的步驟如下：

步驟1:構(gòu)造一個(gè)新的二叉樹節(jié)點(diǎn)；

步驟2:計(jì)算目標(biāo)群數(shù)量N；

步驟3:如果N>2則執(zhí)行步驟4；如果N=2則轉(zhuǎn)到步驟8；

步驟4:把目標(biāo)集合分為兩個(gè)子集TargetSetA和TargetSetB，TargetSetB為距離最相近的N-1個(gè)群中的目標(biāo)集合，TargetSetA為余下的一個(gè)群中的目標(biāo)集合；

步驟5:對(duì)TargetSetA中的目標(biāo)標(biāo)記為正類，TargetSetB中的目標(biāo)標(biāo)記為負(fù)類，用此二類目標(biāo)訓(xùn)練一個(gè)二類SVM分類器；

步驟6：設(shè)定TargetSetA為葉子節(jié)點(diǎn)，其編號(hào)就為測(cè)試目標(biāo)樣本進(jìn)入該節(jié)點(diǎn)時(shí)的分類編號(hào)；

步驟7:對(duì)TargetSetB重復(fù)步驟l到步驟3，進(jìn)行下一次判斷；

步驟8:對(duì)二類目標(biāo)樣本中的一個(gè)類別標(biāo)記為正類，另一個(gè)類別標(biāo)記為負(fù)類，訓(xùn)練一個(gè)二類SVM分類器；

步驟9:設(shè)定上述2類為葉子節(jié)點(diǎn)，其編號(hào)就為測(cè)試目標(biāo)樣本進(jìn)入該節(jié)點(diǎn)時(shí)的分類編號(hào)；

步驟10:以訓(xùn)練好的二類SVM分類器作為二叉樹中間節(jié)點(diǎn)，加上步驟6和步驟9中的葉子節(jié)點(diǎn)，構(gòu)成二叉樹。

分類階段的算法如下：

步驟1:把測(cè)試目標(biāo)數(shù)據(jù)輸入二叉樹結(jié)構(gòu)的根節(jié)點(diǎn)；

步驟2:如果該節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則轉(zhuǎn)入步驟3，如果是葉子節(jié)點(diǎn)則轉(zhuǎn)入步驟6；

步驟3:把測(cè)試目標(biāo)數(shù)據(jù)輸入訓(xùn)練好的二分類SVM分類器，如果SVM分類器輸出正值，則轉(zhuǎn)入步驟4，輸出負(fù)值則轉(zhuǎn)入步驟5；

步驟4:進(jìn)入該節(jié)點(diǎn)的左孩子節(jié)點(diǎn)，并轉(zhuǎn)到步驟6；

步驟5:進(jìn)入該節(jié)點(diǎn)的右孩子節(jié)點(diǎn)，并轉(zhuǎn)到步驟2；

步驟6:直接得出該葉節(jié)點(diǎn)類編號(hào)為輸入測(cè)試目標(biāo)數(shù)據(jù)所屬的群。

⑤ 用交叉驗(yàn)證的方法，確定RBF核中參數(shù)γ和懲罰因子C，從而得到最高的預(yù)測(cè)精度。

3軟件實(shí)現(xiàn)效果

針對(duì)上述目標(biāo)分群算法進(jìn)行了軟件實(shí)現(xiàn)。使用二維仿真數(shù)據(jù)來模擬紅、藍(lán)軍空中目標(biāo)的偵察巡邏場(chǎng)景。當(dāng)所關(guān)注的區(qū)域里出現(xiàn)較多目標(biāo)時(shí)，用戶難以確定要關(guān)注的目標(biāo)，在顯示時(shí)也顯得比較復(fù)雜凌亂，如圖 3所示。圖3中，以圓形符號(hào)表示紅軍，以三角符號(hào)表示藍(lán)軍。

圖3　仿真目標(biāo)圖形顯示

經(jīng)過對(duì)目標(biāo)進(jìn)行分群處理后，出現(xiàn)了3個(gè)紅軍目標(biāo)群和2個(gè)藍(lán)軍目標(biāo)群，對(duì)象環(huán)境中的重要情況可以由目標(biāo)群的運(yùn)動(dòng)情況來判斷得出。目標(biāo)群的圖形顯示方式有2種：一種為在群中心上顯示一個(gè)帶方向的群符號(hào)，并用數(shù)字顯示架次數(shù)，這種方式更利于簡(jiǎn)化整體態(tài)勢(shì)展現(xiàn)，如圖 4所示；另一種為顯示群的外接多邊形，這種方式有利于展現(xiàn)目標(biāo)隊(duì)形，如圖 5所示。

圖4　群中心簡(jiǎn)化圖形顯示

圖5　群外接多邊形圖形顯示

4結(jié)束語

對(duì)多目標(biāo)對(duì)象進(jìn)行分群處理，可以更加準(zhǔn)確地掌握整體態(tài)勢(shì)。以分群處理后的目標(biāo)群顯示對(duì)象環(huán)境信息，更加清晰，并且突出重點(diǎn)，使指揮員能夠迅速掌握整體態(tài)勢(shì)的發(fā)展?fàn)顩r。本文提出了一種適合目標(biāo)分群?jiǎn)栴}的二叉樹多分類的支持向量機(jī)方法，將統(tǒng)計(jì)學(xué)習(xí)的理論引入到數(shù)據(jù)融合中。由于目標(biāo)分群的樣本數(shù)據(jù)并不是海量的，因此建立在小樣本機(jī)器學(xué)習(xí)基礎(chǔ)上的統(tǒng)計(jì)學(xué)習(xí)理論是適用于目標(biāo)分群?jiǎn)栴}的。經(jīng)過軟件實(shí)現(xiàn)顯示，該方法能夠有效地對(duì)多目標(biāo)對(duì)象進(jìn)行分群，值得進(jìn)一步深入研究。

參考文獻(xiàn)

[1]張芬,賈則,生佳根,等.態(tài)勢(shì)估計(jì)中目標(biāo)分群方法的研究[J].電光與控制,2008,15(4):21-23.

[2]龍真真,張策,王維平.基于層次聚類態(tài)勢(shì)估計(jì)中的目標(biāo)分群算法[J].彈箭與制導(dǎo)學(xué)報(bào),2009,29(3):209-211.

[3]VAPNIK V N.The Nature of Statistical Learning Theory[M].New York:Springer-Verlag,1995:59-64.

[4]VAPNIK V N.統(tǒng)計(jì)學(xué)習(xí)理論的本質(zhì)[M].張學(xué)工，譯.北京:清華大學(xué)出版社,2000:85-125.

[5]張學(xué)工.關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論與支持向量機(jī)[J].自動(dòng)化學(xué)報(bào),2000,26(1):32-42.

[6]袁勝發(fā),褚福磊.SVM多類分類算法及其在故障診斷中的應(yīng)用[J].振動(dòng)工程學(xué)報(bào),2004,17(5):419-421.

[7]呂曉麗,李雷,曹未豐.基于二叉樹的SVM多類分類算法[J].信息技術(shù),2008(4):1-3.

[8]李昆侖,黃厚寬,田盛豐.一種基于有向無環(huán)圖的多類SVM分類器[J].模式識(shí)別與人工智能,2003,16(2):164-168.

[9]唐發(fā)明,王仲東,陳綿云.支持向量機(jī)多類分類算法研究[J].控制與決策,2005,20(7):746-749.

[10]馬笑瀟,黃席樾,柴毅.基于SVM的二叉樹多類分類算法及其在故障診斷中的應(yīng)用[J].控制與決策,2003,18 (3):272 -276.

[11]盧文清,何加銘,曾興斌,等.基于多特征提取和粒子群算法的圖像分類[J].無線電通信技術(shù),2014,40(2):90-93.

[12]韓順杰,趙丁選.基于SVM的二叉樹多類分類算法在工程車輛檔位決策中的應(yīng)用[J].中國公路學(xué)報(bào),2007,20(5):122-126.

段同樂男，(1975—)，高級(jí)工程師。主要研究方向：智能信息處理。

張冬寧女，(1981—)，高級(jí)工程師。主要研究方向：智能信息處理、軟件產(chǎn)品線。

Application of Multiclass SVM Based on

Binary Tree in Target Grouping

DUAN Tong-le,ZHANG Dong-ning

(The54thResearchInstituteofCECT,ShijiazhuangHebei050081,China)

AbstractSupport Vector Machines (SVMs) is originally designed for linear binary pattern recognition.Many multiclass SVMs are introduced briefly in the paper.Then the method of multiclass SVM based on binary tree is designed after analyzing the key issues of target grouping.The model of the multiclass SVM algorithm is designed.And the algorithm is realized by coding.The algorithm parameters and weighting factors are adjusted by simulation experiment.The result of simulation validates the feasibility and correctness of the grouping algorithm.

Key wordstarget grouping;binary tree;SVM;SLT

作者簡(jiǎn)介

基金項(xiàng)目：國家部委基金資助項(xiàng)目。

收稿日期：2015-03-05

中圖分類號(hào)TP391.4

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1003-3106(2015)06-0088-04

doi:10.3969/j.issn.1003-3106.2015.06.24

引用格式：段同樂，張冬寧.二叉樹多分類SVM在目標(biāo)分群中的應(yīng)用[J].無線電工程，2015，45(6)：88-91.