師永征

摘要：針對地面有多個無規(guī)則運動的目標(biāo)時，空中機器人很難判斷跟蹤哪一個的問題，提出一種基于分區(qū)決策樹組合分類器的地面多目標(biāo)分類方法。該方法對原始數(shù)據(jù)集分區(qū)處理，分別通過Bagging采樣策略形成不同子數(shù)據(jù)集，利用C4.5經(jīng)典算法構(gòu)建基分類器，并用多數(shù)投票機制對基分類器預(yù)測結(jié)果集成輸出，分區(qū)構(gòu)建多目標(biāo)分類模型。仿真表明相對于傳統(tǒng)的C4.5算法，該方法能夠快速實現(xiàn)地面多運動目標(biāo)分類，提高空中機器人對地面運動目標(biāo)的跟蹤控制率。

關(guān)鍵詞：多目標(biāo)；分區(qū)決策樹； C4.5算法； Bagging；空中機器人；組合分類器

中圖分類號：TP391 文獻標(biāo)識碼：A 文章編號：1009-3044（2015）34-0014-04

Abstract： It is difficult for aerial robotics to decide following which one when there are multi-moving Targets . A multi-moving Targets classification method Based on Multi-classifiers of Sub-region Decision Tree was proposed in the paper. This paper divide the original dataset into several parts in which different datasets are formed by Bagging ，and then base-classifier is constructed based on C4.5 classic algorithm and Multi-Moving Targets classification model is built by majority vote.The final simulation results show that compared with traditional C4.5 classic algorithm this method can classify the multi-moving targets more quickly and improve the speed of the Tracking and controlling.

Key words： multi-targets； sub-region decision tree； C4.5 classic algorithm； bagging； aerial robotics； multi-classifiers

在空中機器人眾多應(yīng)用領(lǐng)域中，都會包含跟蹤地面運動目標(biāo)的任務(wù)。例如，在空間作戰(zhàn)時需要跟蹤打擊運動目標(biāo)、在海上進行人員搜救時，需要空中機器人對隨波漂流人員的識別以及跟蹤等。但是，當(dāng)有多個無規(guī)則運動的目標(biāo)時空中機器人很難判斷跟蹤控制哪一個。所以，亟需設(shè)計一種有效的多運動目標(biāo)分類方法解決這一問題。

比較常用的多目標(biāo)分類方法有快速分類算法、人工神經(jīng)網(wǎng)絡(luò)法[1]、支持向量機法[2]、貝葉斯分類算法[3]和決策樹法[4]等。決策樹是用于分類和預(yù)測的主要技術(shù)之一，它著眼從一組無次序無規(guī)則的實例中推測出以決策樹表示的分類規(guī)則。構(gòu)造決策樹的目的是找出屬性和類別之間的關(guān)系，用它來預(yù)測目標(biāo)未來的類別。它不需要訓(xùn)練樣本，只需要在每一次分類過程中識別一種屬性[5]，學(xué)習(xí)能力強，適合用于處理大規(guī)模的學(xué)習(xí)問題，是數(shù)據(jù)挖掘最常用的方法之一[6]。利用決策樹方法從大量數(shù)據(jù)中提取潛藏在其中的有用信息和規(guī)則被廣泛應(yīng)用和研究。

本文利用決策樹C4.5經(jīng)典算法、Bagging集成方法構(gòu)建組合決策樹，建立地面多運動目標(biāo)的分區(qū)決策樹分析模型，對地面目標(biāo)進行分類和預(yù)測。并且根據(jù)國際空中機器人大賽（IARC）的比賽規(guī)則搭建仿真平臺驗證該分類方法的可靠性。

1相關(guān)概念及其算法

1.1 C4.5算法

決策樹代表對象屬性與對象值之間的一種映射關(guān)系，常用于構(gòu)造分類模型。目前決策樹算法中比較流行的算法有ID3、C4.5、CART和CHAID等[7]。決策樹是數(shù)據(jù)挖掘的重要方法，基于信息熵的ID3算法是決策樹技術(shù)的經(jīng)典算法，信息增益越大的屬性分裂的可能性越大[8]。但是它只能處理離散型的屬性，而C4.5算法既能處理離散型屬性，也能處理連續(xù)性屬性[9]。

ID3算法是一種基于信息熵的決策樹分類算[6]。其核心在于構(gòu)建策樹的過程中，節(jié)點屬性的選擇標(biāo)準(zhǔn)為信息熵，即選用具有最大信息增益的屬性。這種做法能夠在通過每一個非葉節(jié)點時獲得最多的有關(guān)數(shù)據(jù)的類別信息。構(gòu)造決策樹的方法是：計算出數(shù)據(jù)集中全部屬性的信息增益，按照從大到小的順序排序。按照信息增益排列的順序?qū)⑺麄儗?yīng)的屬性作為決策樹的節(jié)點。每一個節(jié)點屬性都是最大增益的屬性，通過決策樹就可以對數(shù)據(jù)進行分類。文獻[10]對ID3算法設(shè)計的相關(guān)理論知識進行了詳細(xì)的定義。這里只給出信息熵、屬性每個取值的信息增益加權(quán)平均值和屬性的信息增益的計算公式。

1）信息熵。面對數(shù)據(jù)集M，其所屬分類有X1，X2，X3…Xn，數(shù)據(jù)集M劃分到各類中的概率分別為P1，P2，P3…Pn。確定數(shù)據(jù)集的分類需要的信息熵公式為：

2）[H（M）=H（P1，P2，...Pn）=-i=1nPilog2（Pi）]假設(shè)將條件屬性Xn的數(shù)據(jù)集T劃分為T1，T2，T3…Tn，這時該數(shù)據(jù)集下分類所需的各子集的信息熵的加權(quán)平均值公式：

[H（X，M）=i=1nH（Mi）TiT]3）則該條件屬性Xn對數(shù)據(jù)集M的信息增益公式：

[Gain（X，M）=H（M）-H（X，T）]C4.5算法是ID3算法的一種改進算法，用信息增益率來選擇屬性，在樹建造過程中進行剪枝，既能處理離散型屬性又能處理連續(xù)型屬性，還能對缺省數(shù)據(jù)進行處理[9]。

信息增益率定義為：

[Gain_ratio（X，M）=Gain（X，M）/Split_Info（X，M）]其中，Gain（X，M）與ID3中的信息增益相同，而分裂信息SplitInfo（X，M）代表了按照屬性X分裂樣本集M的廣度和均勻性。其中：

[Split_Info（X，M）=-i=1n（（TiT）×log2（TiT））] 確定分裂指標(biāo)是生成決策樹過程中的關(guān)鍵。C4.5算法中分裂指標(biāo)確定的基本思想是比較各訓(xùn)練樣本數(shù)據(jù)中屬性信息增益率的大小，取其中信息增益率最大的但又不低于所有屬性平均值的屬性作為樹的一個分支節(jié)點。若存在連續(xù)的描述性屬性，首先必須將該連續(xù)性屬性分割為離散的區(qū)間集合，對其進行離散化處理。

1.2組合學(xué)習(xí)法

組合學(xué)習(xí)法將多個基分類器聚集在一起來構(gòu)成組合分類器，用來提高分類準(zhǔn)確率。理論研究和實驗表明，樣本數(shù)據(jù)集相同時，組合分類器的分類準(zhǔn)確率和泛化能力往往高于單個分類器。根據(jù)分類器組合的形式，可分為四種[11]：第一種為串行方式，分類器組合方式為將一種分類器的輸出作為另一種分類器的輸入。第二種為并行方式，用一種算法將不同的分類器的輸出結(jié)果進行整合，最后輸出分類結(jié)果。這種方式第三種為嵌入方式，將一種分類器在分類過程中嵌入另一種分類器算法來提高分類精度，這種方法會顯著提高原分類器的性能。第四種為混合方式，將上述3中方式混合。為了算法上的快速性，本文采用并行的方式。

裝袋（Bagging）是目前構(gòu)建組合分類器使用最多的方法。Bagging對于有限樣本組成的訓(xùn)練集S，通過Bootstrap過程生成測試樣本Si，以Si為訓(xùn)練集分別構(gòu)建分類器Ci，測試樣本時分別用各基分類器對樣本x進行預(yù)測，依據(jù){C1，C2，C3...Cn}的綜合投票結(jié)果，確定測試樣本x的類別。由于放回抽樣，每次抽樣都是獨立的，因此Bagging是一種并行訓(xùn)練的組合方法。

2基于Bagging的分區(qū)決策樹組合分類器

論文[12]提出了一種動態(tài)分區(qū)方法。分區(qū)算法根據(jù)獲得的環(huán)境信息，把復(fù)雜的不規(guī)則的不確定的區(qū)域分割成若干個子區(qū)，最終返回的數(shù)據(jù)是每個子區(qū)的序號、起點、終點和子區(qū)的個數(shù)。文中根據(jù)此算法對地面目標(biāo)運動區(qū)域進行分區(qū)。

Bagging是集成學(xué)習(xí)實現(xiàn)的途徑之一：基于樣本采樣策略。它利用組合學(xué)習(xí)法將多個基分類器集成到一個強分類器。由于Bagging采樣使得各數(shù)據(jù)集相互獨立，在此基礎(chǔ)上形成多個保證基分類器的多樣性，具備很強的泛化能力和穩(wěn)定性。本文采用分區(qū)的思想分區(qū)構(gòu)建組合決策樹。用Bagging來構(gòu)建訓(xùn)練子集，用C4.5算法構(gòu)建基分類器，各基分類器間采用多數(shù)投票機制進行組合構(gòu)建組合決策樹。其模型如圖1所示。

模型中H為原始數(shù)據(jù)集。H1、H2...Hn是將H分區(qū)處理后的子數(shù)據(jù)集，分別從子數(shù)據(jù)集H1、H2...Hn中進行有放回的隨機抽取，利用決策樹C4.5算法構(gòu)建n組基分類器。各分類器之間相互獨立，所以可以采用并行的思想進行訓(xùn)練。每個分類器都可以得到一個結(jié)果，n個分類器的結(jié)果構(gòu)成了一個函數(shù)系列，將這個序列多數(shù)投票機制投票，得票數(shù)最高的類別為最終組合模型的分類結(jié)果。組合分類器的投票結(jié)果Dn由下式?jīng)Q定。

式中以兩類分類為例，X和Y表示輸出結(jié)果的類別號。由上式可知，判定X和Y投票總數(shù)大小，組合分類器將輸出類別號較大的作為判定結(jié)果。當(dāng)投票總數(shù)相等時會出現(xiàn)判定為平局（equ）的不良結(jié)果。為了避免這種情況的發(fā)生，常采用奇數(shù)個分類器進行組合。

3組合分類器在多目標(biāo)分類中的應(yīng)用

3.1信息提取與處理

本文的樣本數(shù)據(jù)集從仿真平臺中得到。根據(jù)國際空中機器人大賽（IARC）比賽規(guī)則并且基于VC++與OpenGL搭建仿真平臺，仿真平臺中在多目標(biāo)運動區(qū)域創(chuàng)建二維坐標(biāo)系，將其劃分為四個分區(qū)，如圖2與圖3所示。通過仿真平臺可以實時保存地面多目標(biāo)的信息，包括位置，速度大小，速度方向，目標(biāo)所在的象限，目標(biāo)到邊界的時間，目標(biāo)反向的時間，目標(biāo)是否安全等等。同時還可以得到移動障礙物的位置、速度大小和方向以及空中機器人的位置、速度大小和方向。通過仿真平臺得到大量地面運動目標(biāo)的位姿信息，由于相同模型下，樣本數(shù)量越多，預(yù)測的準(zhǔn)確率越高[13]，本文從每個分區(qū)分別保存10000條數(shù)據(jù)作為原始數(shù)據(jù)集。然后利用粗糙集屬性約簡等方法[14][15]去掉不相關(guān)屬性，并將連續(xù)性屬性劃分為0-2PI之間的區(qū)間值。

為了使用組合決策樹來進行多目標(biāo)分類和預(yù)測，本文對選取了對目標(biāo)到達(dá)邊界時間有影響的7個屬性：地面目標(biāo)位置、地面目標(biāo)速度大小、地面目標(biāo)速度方向、地面目標(biāo)反向時間、地面目標(biāo)到達(dá)邊界時間，空中機器人的位置、空中機器人的速度大小。將這7個屬性作為分類屬性，將目標(biāo)是否安全價作為類屬性。根據(jù)決策樹C4.5算法構(gòu)建的決策樹模型可以得到基分類器。本文參考了文獻的實驗結(jié)果：基分類器的個數(shù)越多，模型的準(zhǔn)確率越高。在樣本數(shù)量確定的情況下分別構(gòu)建7個基分類器。

3.2仿真實驗

分別將得到的7個基分類器采用Bagging進行組合，并且采用多數(shù)投票機制對基分類器預(yù)測結(jié)果集成輸出建立多目標(biāo)分類模型。將得到的分類模型添加到全仿真平臺進行驗證，測試數(shù)據(jù)集直接由仿真平臺產(chǎn)生。由于，仿真持續(xù)進行，所以產(chǎn)生的測試數(shù)據(jù)集將會非常大，保證了測試數(shù)據(jù)集過小對是實驗結(jié)果的影響。仿真過程中，如果地面目標(biāo)都是安全的，則由四旋翼控制距離右邊界最近的地面運動目標(biāo)。如果地面機器人有危險的，則判斷哪一個最危險，此時由四旋翼控制最危險的機器人，直到它們解除危險。某一次的仿真過程如圖4、圖5、圖6、圖7、圖8、圖9所示。仿真圖中，黃色代表空中機器人。

由圖5、6、7、8、9可知，在48s，、147s、337s、447s、569s內(nèi)，能夠該方法能夠判斷10個地面目標(biāo)是否安全，并且在全部安全的情況下空中機器人始終跟蹤距離右邊界最近的地面運動目標(biāo)。T=569s時，地面目標(biāo)全部運動到場外，且只有一個沒有從指定邊界出界?？罩袡C器人始終能夠根據(jù)地面目標(biāo)的狀態(tài)進行判斷并且跟蹤控制地面目標(biāo)。

3.3 實驗數(shù)據(jù)

分別利用傳統(tǒng)的決策樹C4.5算法和基于分區(qū)決策樹組合分類器算法進行2000次仿真實驗。當(dāng)仿真時間到達(dá)600秒或者10個地面目標(biāo)全部出界之后仿真實驗終止，記錄此時的用時和地面目標(biāo)出界個數(shù)。傳統(tǒng)的決策樹C4.5算法仿真的得到的部分實驗結(jié)果如表1所示。基于分區(qū)決策樹組合分類器算法得到的部分實驗結(jié)果如表2所示。

3.4實驗結(jié)果分析

由表13和表14可以看出，采用傳統(tǒng)決策樹C4.5算法，空中機器人對地面目標(biāo)的控制率最高為70%，平均值為63%左右。采用分區(qū)決策樹組合分類器算法空中機器人對地面目標(biāo)的控制率達(dá)到89%，部分實驗中空中機器人都能在規(guī)定的時間以內(nèi)將所有的地面目標(biāo)從右邊界趕出。實驗結(jié)果表明，相對于傳統(tǒng)決策樹C4.5算法，分區(qū)決策樹組合分類器算法能夠?qū)Χ嗄繕?biāo)快速分類，分類精度更高，提高了空中機器人對地面多運動目標(biāo)的控制率。

4 結(jié)束語

使用C4.5算法構(gòu)建分區(qū)決策樹不僅使用地面目標(biāo)屬性作為決策樹節(jié)點，而且將空中機器人的位置和速度等屬性作為決策樹的節(jié)點，不僅將地面目標(biāo)和空中機器人結(jié)合，而且提高了決策樹的分類精度。構(gòu)建的組合分類器具有很強的泛化能力，能夠準(zhǔn)確快速地實現(xiàn)地面運動目標(biāo)的分類和預(yù)測?？罩袡C器人在分類結(jié)果的基礎(chǔ)上進行分析，能夠快速跟蹤并且控制地面運動目標(biāo)。該方法避免了四旋翼在場地中盲目的飛行，縮短了搜索時間，提高了四旋翼的控制率。

參考文獻：

[1] 常凱. 基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)挖掘分類算法比較和分析研究[D].安徽大學(xué)，2014.

[2] 夏琴曄，楊宜民. 基于biSCAN和SVM的機器人目標(biāo)識別新算法研究[J].廣東工業(yè)大學(xué)學(xué)報，2013，30（4）：65-69.

[3] 胡銀娥.基于粗糙集的樸素貝葉斯分類算法研究[D].長沙理工大學(xué)，2012.

[4] 蒲元芳，張巍，滕少華，等. 基于決策樹的協(xié)同網(wǎng)絡(luò)入侵檢測[J].江西師范大學(xué)學(xué)報：自然科學(xué)版，2010，34（3）：302-307.

[5] 劉文龍，李峰，米曉楠，等. 基于分區(qū)決策樹的烏達(dá)煤田土地覆被分類研究[J].煤炭工程，2014，46（9）：120-122.

[6] 王小巍，蔣玉明. 決策樹ID3算法的分析與改進[J]. 計算機工程與設(shè)計，2011，32（9）：3069-3072+3076.

[7] John Durkin，蔡競峰，蔡自興. 決策樹技術(shù)及其當(dāng)前研究方向[J]. 控制工程，2005，12（1）：15-18+21.

[8] 喻金平，黃細(xì)妹，李康順. 基于一種新的屬性選擇標(biāo)準(zhǔn)的ID3改進算法[J].計算機應(yīng)用研究，2012，29（8）：2895-2898+2908.

[9] 姚亞夫，邢留濤.決策樹C4.5連續(xù)屬性分割閾值算法改進及其應(yīng)用[J].中南大學(xué)學(xué)報：自然科學(xué)版，2011，42（12）：3772-3776.

[10] 王國勛. 基于多目標(biāo)決策的數(shù)據(jù)挖掘模型選擇研究[D].電子科技大學(xué)，2013.

[11] 李暢，劉鵬程. 多特征和多分類器組合的濕地遙感影像分類[J]. 計算機工程與應(yīng)用，2012，48（33）：9-13.

[12] 張洪峰，王碩，譚民，等. 基于動態(tài)分區(qū)方法的多機器人協(xié)作地圖構(gòu)建[J].機器人，2003，25（02）：156-162.

[13] 李俊磊，滕少華，張巍. 基于決策樹組合分類器的氣溫預(yù)測[J]. 廣東工業(yè)大學(xué)學(xué)報，2014，31（04）：54-59.

[14] 王平. 基于粗糙集屬性約簡的分類算法研究與應(yīng)用[D].大連理工大學(xué)，2013.

[15] 江峰，王莎莎，杜軍威，等. 基于近似決策熵的屬性約簡[J].控制與決策，2015，30（1）：65-70.