隨着現在電子科技的發展，我國的科學家也發明了很多工具方便人們的工作和生活，空中機器人也是近年來的一種高科技產品，本文就針對基於分區決策樹組合分類器的多目標分類方法進行了一些論述的論文範文，供大家閱讀借鑑。
摘要：針對地面有多個無規則運動的目標時，空中機器人很難判斷跟蹤哪一個的問題，提出一種基於分區決策樹組合分類器的地面多目標分類方法。該方法對原始數據集分區處理，分別通過Bagging採樣策略形成不同子數據集，利用C4.5經典算法構建基分類器，並用多數投票機制對基分類器預測結果集成輸出，分區構建多目標分類模型。仿真表明相對於傳統的C4.5算法，該方法能夠快速實現地面多運動目標分類，提高空中機器人對地面運動目標的跟蹤控制率。
關鍵詞：多目標,分區決策樹,C4.5算法,Bagging,空中機器人,組合分類器
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 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
在空中機器人衆多應用領域中，都會包含跟蹤地面運動目標的任務。例如，在空間作戰時需要跟蹤打擊運動目標、在海上進行人員搜救時，需要空中機器人對隨波漂流人員的識別以及跟蹤等。但是，當有多個無規則運動的目標時空中機器人很難判斷跟蹤控制哪一個。所以，亟需設計一種有效的多運動目標分類方法解決這一問題。
比較常用的多目標分類方法有快速分類算法、人工神經網絡法[1]、支持向量機法[2]、貝葉斯分類算法[3]和決策樹法[4]等。決策樹是用於分類和預測的主要技術之一，它着眼從一組無次序無規則的實例中推測出以決策樹表示的分類規則。構造決策樹的目的是找出屬性和類別之間的關係，用它來預測目標未來的類別。它不需要訓練樣本，只需要在每一次分類過程中識別一種屬性[5]，學習能力強，適合用於處理大規模的學習問題，是數據挖掘最常用的方法之一[6]。利用決策樹方法從大量數據中提取潛藏在其中的有用信息和規則被廣泛應用和研究。
本文利用決策樹C4.5經典算法、Bagging集成方法構建組合決策樹，建立地面多運動目標的分區決策樹分析模型，對地面目標進行分類和預測。並且根據國際空中機器人大賽(IARC)的比賽規則搭建仿真平臺驗證該分類方法的可靠性。
1相關概念及其算法
1.1 C4.5算法
決策樹代表對象屬性與對象值之間的一種映射關係，常用於構造分類模型。目前決策樹算法中比較流行的算法有ID3、C4.5、CART和CHAID等[7]。決策樹是數據挖掘的重要方法，基於信息熵的ID3算法是決策樹技術的經典算法，信息增益越大的屬性分裂的可能性越大[8]。但是它只能處理離散型的屬性，而C4.5算法既能處理離散型屬性，也能處理連續性屬性[9]。
ID3算法是一種基於信息熵的決策樹分類算[6]。其核心在於構建策樹的過程中，節點屬性的選擇標準爲信息熵，即選用具有最大信息增益的屬性。這種做法能夠在通過每一個非葉節點時獲得最多的有關數據的類別信息。構造決策樹的方法是：計算出數據集中全部屬性的信息增益，按照從大到小的順序排序。按照信息增益排列的順序將他們對應的屬性作爲決策樹的節點。每一個節點屬性都是最大增益的屬性，通過決策樹就可以對數據進行分類。文獻[10]對ID3算法設計的相關理論知識進行了詳細的定義。這裏只給出信息熵、屬性每個取值的信息增益加權平均值和屬性的信息增益的計算公式。
1)信息熵。面對數據集M，其所屬分類有X1，X2，X3…Xn，數據集M劃分到各類中的概率分別爲P1，P2，P3…Pn。確定數據集的分類需要的信息熵公式爲：
2)[H(M)=H(P1，P2，)=-i=1nPilog2(Pi)]假設將條件屬性Xn的數據集T劃分爲T1，T2，T3…Tn，這時該數據集下分類所需的.各子集的信息熵的加權平均值公式：
[H(X，M)=i=1nH(Mi)TiT]3)則該條件屬性Xn對數據集M的信息增益公式：
[Gain(X，M)=H(M)-H(X，T)]C4.5算法是ID3算法的一種改進算法，用信息增益率來選擇屬性，在樹建造過程中進行剪枝，既能處理離散型屬性又能處理連續型屬性，還能對缺省數據進行處理[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))] 確定分裂指標是生成決策樹過程中的關鍵。C4.5算法中分裂指標確定的基本思想是比較各訓練樣本數據中屬性信息增益率的大小，取其中信息增益率最大的但又不低於所有屬性平均值的屬性作爲樹的一個分支節點。若存在連續的描述性屬性，首先必須將該連續性屬性分割爲離散的區間集合，對其進行離散化處理。
1.2組合學習法
組合學習法將多個基分類器聚集在一起來構成組合分類器，用來提高分類準確率。理論研究和實驗表明，樣本數據集相同時，組合分類器的分類準確率和泛化能力往往高於單個分類器。根據分類器組合的形式，可分爲四種[11]：第一種爲串行方式，分類器組合方式爲將一種分類器的輸出作爲另一種分類器的輸入。第二種爲並行方式，用一種算法將不同的分類器的輸出結果進行整合，最後輸出分類結果。這種方式第三種爲嵌入方式，將一種分類器在分類過程中嵌入另一種分類器算法來提高分類精度，這種方法會顯著提高原分類器的性能。第四種爲混合方式，將上述3中方式混合。爲了算法上的快速性，本文采用並行的方式。
裝袋(Bagging)是目前構建組合分類器使用最多的方法。Bagging對於有限樣本組成的訓練集S，通過Bootstrap過程生成測試樣本Si，以Si爲訓練集分別構建分類器Ci，測試樣本時分別用各基分類器對樣本x進行預測，依據{C1，C2，}的綜合投票結果，確定測試樣本x的類別。由於放回抽樣，每次抽樣都是獨立的，因此Bagging是一種並行訓練的組合方法。
2基於Bagging的分區決策樹組合分類器
論文[12]提出了一種動態分區方法。分區算法根據獲得的環境信息，把複雜的不規則的不確定的區域分割成若干個子區，最終返回的數據是每個子區的序號、起點、終點和子區的個數。文中根據此算法對地面目標運動區域進行分區。
Bagging是集成學習實現的途徑之一：基於樣本採樣策略。它利用組合學習法將多個基分類器集成到一個強分類器。由於Bagging採樣使得各數據集相互獨立，在此基礎上形成多個保證基分類器的多樣性，具備很強的泛化能力和穩定性。本文采用分區的思想分區構建組合決策樹。用Bagging來構建訓練子集，用C4.5算法構建基分類器，各基分類器間採用多數投票機制進行組合構建組合決策樹。其模型如圖1所示。
模型中H爲原始數據集。H1、是將H分區處理後的子數據集，分別從子數據集H1、中進行有放回的隨機抽取，利用決策樹C4.5算法構建n組基分類器。各分類器之間相互獨立，所以可以採用並行的思想進行訓練。每個分類器都可以得到一個結果，n個分類器的結果構成了一個函數系列，將這個序列多數投票機制投票，得票數最高的類別爲最終組合模型的分類結果。組合分類器的投票結果Dn由下式決定。
式中以兩類分類爲例，X和Y表示輸出結果的類別號。由上式可知，判定X和Y投票總數大小，組合分類器將輸出類別號較大的作爲判定結果。當投票總數相等時會出現判定爲平局(equ)的不良結果。爲了避免這種情況的發生，常採用奇數個分類器進行組合。
3組合分類器在多目標分類中的應用
3.1信息提取與處理
本文的樣本數據集從仿真平臺中得到。根據國際空中機器人大賽(IARC)比賽規則並且基於VC++與OpenGL搭建仿真平臺，仿真平臺中在多目標運動區域創建二維座標系，將其劃分爲四個分區，如圖2與圖3所示。通過仿真平臺可以實時保存地面多目標的信息，包括位置，速度大小，速度方向，目標所在的象限，目標到邊界的時間，目標反向的時間，目標是否安全等等。同時還可以得到移動障礙物的位置、速度大小和方向以及空中機器人的位置、速度大小和方向。通過仿真平臺得到大量地面運動目標的位姿信息，由於相同模型下，樣本數量越多，預測的準確率越高[13]，本文從每個分區分別保存10000條數據作爲原始數據集。然後利用粗糙集屬性約簡等方法[14][15]去掉不相關屬性，並將連續性屬性劃分爲0-2PI之間的區間值。
爲了使用組合決策樹來進行多目標分類和預測，本文對選取了對目標到達邊界時間有影響的7個屬性：地面目標位置、地面目標速度大小、地面目標速度方向、地面目標反向時間、地面目標到達邊界時間，空中機器人的位置、空中機器人的速度大小。將這7個屬性作爲分類屬性，將目標是否安全價作爲類屬性。根據決策樹C4.5算法構建的決策樹模型可以得到基分類器。本文參考了文獻的實驗結果：基分類器的個數越多，模型的準確率越高。在樣本數量確定的情況下分別構建7個基分類器。
3.2仿真實驗
分別將得到的7個基分類器採用Bagging進行組合，並且採用多數投票機制對基分類器預測結果集成輸出建立多目標分類模型。將得到的分類模型添加到全仿真平臺進行驗證，測試數據集直接由仿真平臺產生。由於，仿真持續進行，所以產生的測試數據集將會非常大，保證了測試數據集過小對是實驗結果的影響。仿真過程中，如果地面目標都是安全的，則由四旋翼控制距離右邊界最近的地面運動目標。如果地面機器人有危險的，則判斷哪一個最危險，此時由四旋翼控制最危險的機器人，直到它們解除危險。某一次的仿真過程如圖4、圖5、圖6、圖7、圖8、圖9所示。仿真圖中，黃色代表空中機器人。
由圖5、6、7、8、9可知，在48s，、147s、337s、447s、569s內，能夠該方法能夠判斷10個地面目標是否安全，並且在全部安全的情況下空中機器人始終跟蹤距離右邊界最近的地面運動目標。T=569s時，地面目標全部運動到場外，且只有一個沒有從指定邊界出界。空中機器人始終能夠根據地面目標的狀態進行判斷並且跟蹤控制地面目標。 3.3 實驗數據
分別利用傳統的決策樹C4.5算法和基於分區決策樹組合分類器算法進行2000次仿真實驗。當仿真時間到達600秒或者10個地面目標全部出界之後仿真實驗終止，記錄此時的用時和地面目標出界個數。傳統的決策樹C4.5算法仿真的得到的部分實驗結果如表1所示。基於分區決策樹組合分類器算法得到的部分實驗結果如表2所示。
3.4實驗結果分析
由表13和表14可以看出，採用傳統決策樹C4.5算法，空中機器人對地面目標的控制率最高爲70%，平均值爲63%左右。採用分區決策樹組合分類器算法空中機器人對地面目標的控制率達到89%，部分實驗中空中機器人都能在規定的時間以內將所有的地面目標從右邊界趕出。實驗結果表明，相對於傳統決策樹C4.5算法，分區決策樹組合分類器算法能夠對多目標快速分類，分類精度更高，提高了空中機器人對地面多運動目標的控制率。
4 結束語
使用C4.5算法構建分區決策樹不僅使用地面目標屬性作爲決策樹節點，而且將空中機器人的位置和速度等屬性作爲決策樹的節點，不僅將地面目標和空中機器人結合，而且提高了決策樹的分類精度。構建的組合分類器具有很強的泛化能力，能夠準確快速地實現地面運動目標的分類和預測。空中機器人在分類結果的基礎上進行分析，能夠快速跟蹤並且控制地面運動目標。該方法避免了四旋翼在場地中盲目的飛行，縮短了搜索時間，提高了四旋翼的控制率。
參考文獻：
[1] 常凱. 基於神經網絡的數據挖掘分類算法比較和分析研究[D].安徽大學，2014.
[2] 夏琴曄，楊宜民. 基於biSCAN和SVM的機器人目標識別新算法研究[J].廣東工業大學學報，2013，30(4)：65-69.
[3] 胡銀娥.基於粗糙集的樸素貝葉斯分類算法研究[D].長沙理工大學，2012.
[4] 蒲元芳，張巍，滕少華，等. 基於決策樹的協同網絡入侵檢測[J].江西師範大學學報：自然科學版，2010，34(3)：302-307.
[5] 劉文龍，李峯，米曉楠，等. 基於分區決策樹的烏達煤田土地覆被分類研究[J].煤炭工程，2014，46(9)：120-122.
[6] 王小巍，蔣玉明. 決策樹ID3算法的分析與改進[J]. 計算機工程與設計，2011，32(9)：3069-3072+3076.
[7] John Durkin，蔡競峯，蔡自興. 決策樹技術及其當前研究方向[J]. 控制工程，2005，12(1)：15-18+21.
[8] 喻金平，黃細妹，李康順. 基於一種新的屬性選擇標準的ID3改進算法[J].計算機應用研究，2012，29(8)：2895-2898+2908.