基于决策树的最佳通信渔船选择方法

邵旻晖，张　琳，周　凡

(上海海事大学信息工程学院，上海 201306)

无线网络技术的快速发展为海洋与渔业部门在海上通信提供了巨大的帮助。早在2004年，中国就建设了全国海洋渔业安全通信网，包括短波、超短波[1-2]、卫星监测[3-4]、公众移动通信等，并开始运用信息化手段服务于渔业发展[5]。但是在距离海岸10～15 n mile及以外的地方，由于海上不确定的环境变化，无线网络的信号强度会被削弱，渔船和岸上之间的信息交流会受到巨大影响[6]。因此，急需发展海洋渔业通信技术。徐硕等[1]提出了一套专用于渔船之间高可靠性远距离传输的数字通信网络系统，形成一套渔船之间、渔船与岸台之间的有效通信网络。沈丹丹[2]提出了一种海上渔船超短波无线自组织网络，用于弥补超短波不能远距离通信的缺陷，可更好地为海上通信服务。夏明华等[6]针对中国南海岛礁众多的地理特点，提出了一种新型海洋通信网络架构，通过固定的岛礁或者海上浮台、飞艇、无人船等中继节点建立新的高速宽带链路。Kolios等[7]基于现有船舶自动识别系统(AIS)获得船舶移动数据，预测船—船相遇模型，构建了从任意节点向目标节点传递消息的最优路径，优化信息传输性能。

相关研究表明，在渔船间构建专用于渔船的无线通信网络系统已成为可能[1-2]，而且，选择一个海洋无线网络中的最优通信节点能保证舰船通信的高效性和可靠性[6-7]。针对渔船移动和海上环境的特殊性，本研究提出了一种使用数据挖掘算法来选择渔船无线通信网络系统中最优通信节点的方法。为了获取渔船集群中的最优通信节点，采用决策树中的C4.5算法，通过分析渔船自身的信号强度和基于AIS数据[8-9]的环境参数(风速、海面温度和海面气压)，对渔船的无线通信状态进行分类。决策树算法的分类结果将帮助寻找用来发送岸上信息的最佳船只，可以是附近具有良好信号强度并可建立连接的船只。因为渔船所处的位置和环境条件的不同，海上渔船的通信状态会不断发生变化。为了向指定的船只发送信息，需要得知渔船的位置和状态，这在一定程度上也有助于发现偏离渔场的船只。

1　决策树与集成学习

1.1　决策树C4.5算法

决策树是由内部节点和叶节点构成的类似于流程图的树结构，内部节点表示对属性的测试，叶节点代表最终的分类结果，其目的主要是分类与决策[10]。决策树分类算法的优点是能高效地对海量数据集中的信息进行分类，通过自身的学习获取知识，并以决策树的形式表示出来。以决策树形式表示的知识不仅清晰直观,而且具有很高的推理效率(决策树推理就是对决策树的遍历)[10]。C4.5算法是数据挖掘中最常用、最经典的分类算法[11]。C4.5算法是根据信息增益率(Information Gain Ratio)选择测试属性，是非常有效的监督式学习模式，通过学习，最终找到一个从属性值到类别的映射关系，并且这个映射能用于对新的类别未知的实体进行分类[12]。

1.2　集成学习算法

在数据挖掘中，单一的分类算法往往存在缺陷，比如C4.5算法受到数据集合中的奇异数据影响较大[13]。因此，研究者提出集成学习的概念，其中应用最广泛的集成学习算法是Bagging算法[14]和Boosting算法[15]。Bagging算法采用的是随机且有放回的从训练集中进行子抽样，组成所需要的子训练集，通过分类子训练集训练多个分类器,最后组合产生最终的预测结果。Boosting是一种框架算法，通过将多个弱学习器组合成一个强学习器，明显地提高了分类器的精度[16]。该算法根据学习时间和使用弱分类器的数量，逐步改进预测过程，通过有限次的迭代，这些弱学习器的加权集成便形成了最终的强学习器[16]。

2　最佳通信渔船选择方法

研究目标是在海洋无线通信环境下，通过考虑渔船各自的信号强度和环境条件，用决策树集成算法对渔船的数据集进行分类，决策树的分类结果将帮助寻找具有良好通信条件的船只节点。这有助于使无线数据在无线网络覆盖区域下的所有节点上进行交换，实现岸边和海上渔船的连续实时通信。

系统工作流程如下：1)基于无线通信数据，分析渔船的海上位置；2)将C4.5决策树分类算法应用于训练集，以识别通信的可能性；3)应用集成学习算法(Bagging、Boosting)，以提高决策树的精度；4)根据决策树的分类结果寻找最适合通信的渔船；5)建立岸边与最佳通信渔船的连接，若渔船在出海作业期间发生任何情况，及时通过最佳通信渔船向相应的船只传送信息。系统架构如图1所示。

图1　系统架构

渔船的数据来自船讯网(http://www.shipxy.com/)，选泽属于舟山市普陀区在舟山渔场作业的渔船(图2)。点击某只渔船可以查看渔船的位置信息和其所在海域的气象信息。向哲等[17]提出了一种利用海量的AIS历史数据、插值算法和网格化技术的GridCount算法[17]。渔船自身的信号强度可以按照文献[17]的方法计算。最终选取了200艘渔船的数据集进行评估。

2.1　数据集预处理

从数据库中随机选择一组数据集，记为训练集A。训练集A中的属性(表1)包括了渔船的位置(经度和纬度)、风速、海面温度、海面气压和信号强度。使用训练数据来预测岸边和海上渔船的通信状态。通信状态分为三类:好、一般、差。

表1　属性列表

图2　在舟山渔场作业的渔船

2.2　属性选择方法

属性选择的原则是选择能够最佳分离给定训练集A到单个类别的属性。如果分裂属性能尽可能地把训练集A分裂成更小的分区，那么这个分区所代表的结果就越简单，这个分裂属性就被选择为给定训练元组的分裂属性。如果被选中的分裂属性是连续值，那么分裂节点就被确定；如果分裂属性是离散值且要求生成二叉决策树，那么分裂子集也必须与分裂规则一起决定。分裂节点将被分裂规则标记，分裂规则的每个结果会生成分支，并相应地对训练集A进行划分。这里采用的属性选择方法是信息增益和信息增益率。

2.3　使用C4.5算法分类

在寻找最佳通信渔船的方法下，最终分类结果是“好”、“一般”和“差”的通信状态，而分类属性列表由经度、纬度、风速、海面温度、海面气压和信号强度组成，其中经度和纬度被用来计算渔船的信号强度。在决策树中，迭代地选择信息增益最高的属性作为决策树节点的分裂属性。

最终分类结果是通信状态，具有3个不同的类。设C1类对应于0(即通信好)，C2类对应于1(即通信一般)，C3类对应于2(即通信差)，输入的训练集都被分成这3类。为了获得这些训练元组的分裂规则，分别按照训练集的各个属性对数据进行分类，对每个分类结果，计算相应的信息增益率[18]。

对训练集A，设Fi(i=1,2,3,…,n)为分类标记属性有n个不同的值，属性X有m个不同的取值x={x1,x2,…,xm}，可以用属性X将训练集A离散地划分为m个子集{A1,A2,…,Am}，其中子集Aj包含了训练集A中的元组，在属性X上的值为xj，主要计算[18-19]：

计算训练集A中元组的信息熵E(A):

(1)

计算使用属性对训练集A进行分类的信息熵E(XA):

(2)

计算属性X的信息增益G(X)：

G(X)=E(A)-E(XA)

(3)

计算属性X的分裂信息S(XA)：

(4)

计算属性X的信息增益率R(X)：

(5)

最后，按照与最大信息增益率对应的属性，将当前训练集划分为不同的子集，建立相应的决策树分支，形成新的子节点[20]。由于篇幅有限，此处未给出具体的计算过程。在大多数情况下，选择信号强度作为分裂属性。

2.4　集成学习

集成学习(Ensemble learning)是使用一系列个体学习器进行学习，并使用某种结合策略把多个学习器进行集成从而获得比使用单一学习器更强泛化能力的一种机器学习方法。在Boosting算法(以Adaboost为例)中，首先初始化训练集A上样本的权值并赋予相同的权值为1/n，然后进行T轮迭代训练。在每轮训练结束后，降低正确分类的样本权重，增加错误分类的样本权重，使下次训

练过程对错误分类样本加以重视，最终达到所要求的测试性能[21]。在Bagging算法中，每个训练集都是通过原始训练集的bootstrap复制而构造的。也就是说，Bagging算法通过bootstrap方法在训练集A上进行有放回的抽取样本来构成训练数据的子集，然后通过训练数据的子集来训练各个子分类器，最终对所有的子分类器进行组合[21]。这里将C4.5算法作为基本学习算法，得到多个弱学习器，分别使用Bagging算法和Boosting算法构建强学习器。

3　结果与分析

3.1　结果

在这种用于选择海上最佳通信渔船的方法中，对舟山渔场的200个渔船实例进行试验，考虑了4个属性：信号强度、风速、海面温度和海面气压。使用C4.5分类算法实现了对训练集中各个属性的合理分类。图3显示了使用C4.5算法生成的决策树。

图3　C4.5算法生成的决策树

采用10折交叉验证来测试分类器的性能，将数据集平均划分为10份，其中9份用来训练，1份用来测试[22]。通过分析测试集上的算法泛化精度、正确分类实例的百分比、均方根误差和Kappa数据，对集成学习和决策树本身的精度进行性能比较。表2给出了性能比较结果，表3给出了精度、均方根误差和Kappa系数的比较结果。

表2　决策树与集成学习方法的性能比较

表3　　　　决策树与集成学习方法在精度、均方根误差

3.2　分类结果分析

从决策树的最终分类结果中发现，在大多数情况下，渔船自身的信号强度是影响渔船之间通信的最重要的属性。当渔船的信号强度>-50 dBm时(即信号强度较好)，海面的环境因素对渔船的通信状态基本没有影响，通常都是好的，适合被选择成为最佳通信渔船。

但是，风速、海面气压、海面温度等海上环境因素会对海上无线通信产生不利影响。当渔船自身的信号强度<-75 dBm时(即信号强度较差)，海面气压会干扰渔船的通信状态，通信状态最多达到一般。当渔船的信号强度位于-75～-50 dBm时(即信号强度一般)，风速和海面温度会对渔船通信状态产生影响，具体表现为：当温度≤20 ℃时(即较适宜)，若风速≤30 km/h，渔船的通信状态好，否则是一般。当温度>20 ℃时，若风速≤30 km/h，渔船的通信状态也是一般；若风速>30 km/h且<35 km/h，渔船的通信状态是一般；若风速>35 km/h且自身的通信强度介于-75～-65 dBm之间，渔船的通信状态是差的。

根据分类结果，可以从结果为“好”的那一类中的渔船中选取一艘或多艘作为最佳通信渔船，而当被选中的渔船因为位置移动或天气变化而不再具备良好通信条件时，决策树又会自动选择新的最佳通信船只。

3.3　分类性能分析

通过表2可以发现，与集成学习结合的决策树算法的综合精度都超过了95%，单一的决策树算法的综合精度也有94%，这意味着三种数据挖掘算法对训练集的预测效果均很好。此外，两种与集成学习结合的决策树算法虽然都比单一的决策树算法在复杂程度和耗时上更高，但两种决策树集成算法的综合精度都有了明显的提高，分别使C4.5算法的正确分类率提升了1.55和1.22个百分点。

表3中的均方根误差是观测值与真值偏差的平方与观测次数n比值的平方根，Kappa系数用于一致性检验也可以用于衡量分类精度，通常追求低均方根误差和高Kappa系数，因为这代表着更高的总体分类精度。通过表3可以发现，两种与集成学习结合的决策树算法都比单一的决策树算法具有更低的均方根系数和更高的Kappa系数。这些都说明了集成学习通过提高系统泛化能力确实能够提高整体精度。而Boosting算法和Bagging算法孰优孰劣通常与采用的数据集特性有关，在文中的渔船数据集上，Boosting算法比Bagging算法有更好的表现。

4　结论

面对海洋环境复杂多变、通信环境恶劣的挑战，提出一种基于决策树的最佳通信渔船选择方法，寻找一个渔船集群中具有良好信号强度的最佳节点作为通信节点。同时在决策树C4.5算法中应用集成学习算法(Bagging和Boosting)来提高算法分类的性能，性能分析结果表明，与Boosting算法结合的C4.5算法分类精度最高，可以达到95.76%。在现实环境中，决策树能在相对短的时间内对数据集做出可行且效果良好的分类，只需要一次构建并可反复使用。本研究将有助于保障岸边和渔船的通信效率并及时向离岸较远的目标渔船发送信息。

□