基于分区决策树组合分类器的多目标分类方法

师永征

摘要：针对地面有多个无规则运动的目标时，空中机器人很难判断跟踪哪一个的问题，提出一种基于分区决策树组合分类器的地面多目标分类方法。该方法对原始数据集分区处理，分别通过Bagging采样策略形成不同子数据集，利用C4.5经典算法构建基分类器，并用多数投票机制对基分类器预测结果集成输出，分区构建多目标分类模型。仿真表明相对于传统的C4.5算法，该方法能够快速实现地面多运动目标分类，提高空中机器人对地面运动目标的跟踪控制率。

关键词：多目标；分区决策树； C4.5算法； Bagging；空中机器人；组合分类器

中图分类号：TP391 文献标识码：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

在空中机器人众多应用领域中，都会包含跟踪地面运动目标的任务。例如，在空间作战时需要跟踪打击运动目标、在海上进行人员搜救时，需要空中机器人对随波漂流人员的识别以及跟踪等。但是，当有多个无规则运动的目标时空中机器人很难判断跟踪控制哪一个。所以，亟需设计一种有效的多运动目标分类方法解决这一问题。

比较常用的多目标分类方法有快速分类算法、人工神经网络法[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，...Pn）=-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，C3...Cn}的综合投票结果，确定测试样本x的类别。由于放回抽样，每次抽样都是独立的，因此Bagging是一种并行训练的组合方法。

2基于Bagging的分区决策树组合分类器

论文[12]提出了一种动态分区方法。分区算法根据获得的环境信息，把复杂的不规则的不确定的区域分割成若干个子区，最终返回的数据是每个子区的序号、起点、终点和子区的个数。文中根据此算法对地面目标运动区域进行分区。

Bagging是集成学习实现的途径之一：基于样本采样策略。它利用组合学习法将多个基分类器集成到一个强分类器。由于Bagging采样使得各数据集相互独立，在此基础上形成多个保证基分类器的多样性，具备很强的泛化能力和稳定性。本文采用分区的思想分区构建组合决策树。用Bagging来构建训练子集，用C4.5算法构建基分类器，各基分类器间采用多数投票机制进行组合构建组合决策树。其模型如图1所示。

模型中H为原始数据集。H1、H2...Hn是将H分区处理后的子数据集，分别从子数据集H1、H2...Hn中进行有放回的随机抽取，利用决策树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.

[9] 姚亚夫，邢留涛.决策树C4.5连续属性分割阈值算法改进及其应用[J].中南大学学报：自然科学版，2011，42（12）：3772-3776.

[10] 王国勋. 基于多目标决策的数据挖掘模型选择研究[D].电子科技大学，2013.

[11] 李畅，刘鹏程. 多特征和多分类器组合的湿地遥感影像分类[J]. 计算机工程与应用，2012，48（33）：9-13.

[12] 张洪峰，王硕，谭民，等. 基于动态分区方法的多机器人协作地图构建[J].机器人，2003，25（02）：156-162.

[13] 李俊磊，滕少华，张巍. 基于决策树组合分类器的气温预测[J]. 广东工业大学学报，2014，31（04）：54-59.

[14] 王平. 基于粗糙集属性约简的分类算法研究与应用[D].大连理工大学，2013.

[15] 江峰，王莎莎，杜军威，等. 基于近似决策熵的属性约简[J].控制与决策，2015，30（1）：65-70.