二叉樹多分類SVM在目標分群中的應用

段同樂，張冬寧

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

?

二叉樹多分類SVM在目標分群中的應用

段同樂，張冬寧

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

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

關鍵詞目標分群；二叉樹；支持向量機；統(tǒng)計學習理論

0引言

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

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

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

1常用的SVM多類分類算法

1.1　SVM基本思想

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

圖1　SVM基本思想

目標分群問題在其特征空間中是線性不可分的，其最優(yōu)分類超平面的判別函數(shù)為：

1.2　核函數(shù)的選擇

核函數(shù)本質上是一種映射函數(shù)，能夠將低維空間的非線性問題映射到高維空間中，變成線性問題進行處理，而計算復雜度并沒有增加。常用的核函數(shù)有：

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

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

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

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

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

1.3　多分類SVM

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

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

1-v-r算法是對N類訓練樣本中的每一類和其余樣本構造一個二類分類器，共構造N個分類器。其優(yōu)點是算法簡單，容易實現(xiàn)，并且計算速度較快，缺點是由于每個二類分類器的正負樣本規(guī)模嚴重不對稱，容易產生無法分類的樣本或屬于多個類別的樣本。

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

2基于二叉樹多分類SVM的目標分群模型

2.1　二叉樹多分類SVM算法

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

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

2.2　目標分群模型

對于目標分群問題，用二叉樹多分類SVM算法進行求解的過程如下[10]：

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

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

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

④ 采用二叉樹多分類SVM算法將目標分群問題轉化為多個二分類問題。

算法分為訓練和分類2個階段，訓練階段的步驟如下：

步驟1:構造一個新的二叉樹節(jié)點；

步驟2:計算目標群數(shù)量N；

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

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

步驟5:對TargetSetA中的目標標記為正類，TargetSetB中的目標標記為負類，用此二類目標訓練一個二類SVM分類器；

步驟6：設定TargetSetA為葉子節(jié)點，其編號就為測試目標樣本進入該節(jié)點時的分類編號；

步驟7:對TargetSetB重復步驟l到步驟3，進行下一次判斷；

步驟8:對二類目標樣本中的一個類別標記為正類，另一個類別標記為負類，訓練一個二類SVM分類器；

步驟9:設定上述2類為葉子節(jié)點，其編號就為測試目標樣本進入該節(jié)點時的分類編號；

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

分類階段的算法如下：

步驟1:把測試目標數(shù)據(jù)輸入二叉樹結構的根節(jié)點；

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

步驟3:把測試目標數(shù)據(jù)輸入訓練好的二分類SVM分類器，如果SVM分類器輸出正值，則轉入步驟4，輸出負值則轉入步驟5；

步驟4:進入該節(jié)點的左孩子節(jié)點，并轉到步驟6；

步驟5:進入該節(jié)點的右孩子節(jié)點，并轉到步驟2；

步驟6:直接得出該葉節(jié)點類編號為輸入測試目標數(shù)據(jù)所屬的群。

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

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

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

圖3　仿真目標圖形顯示

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

圖4　群中心簡化圖形顯示

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

4結束語

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

參考文獻

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

[2]龍真真,張策,王維平.基于層次聚類態(tài)勢估計中的目標分群算法[J].彈箭與制導學報,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)計學習理論的本質[M].張學工，譯.北京:清華大學出版社,2000:85-125.

[5]張學工.關于統(tǒng)計學習理論與支持向量機[J].自動化學報,2000,26(1):32-42.

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

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

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

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

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

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

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

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

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

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

作者簡介

基金項目：國家部委基金資助項目。

收稿日期：2015-03-05

中圖分類號TP391.4

文獻標識碼A

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

doi:10.3969/j.issn.1003-3106.2015.06.24

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