基于决策树学习的航运企业优势航次知识发现

夏明星， 胡正华， 张 涛 （南京航空航天大学，江苏 南京 210016）

0 引 言

航运企业在承接航运任务时面临的首要问题是什么样类型的航运任务盈利的可能性大，或者说容易盈利。航运企业自身状况的不同，导致了航运企业对航运任务的运营控制能力不同。不同的航运企业擅长组织管理航运任务类型不同。有的企业可能只擅长控制比较短途的航运任务，而对于有的航运企业来说，可能更容易从长途的航运业务中获取利润。对于每个航运企业来说，弄清楚自己的优势所在，避开自己的弱势来承接航运任务，是非常重要的。

1 航次任务特征属性

在基于决策树的航次优势知识发现中，条件属性是指航次任务特征属性。航次任务特征属性是指那些可以用于区分每个航次任务类型的航次属性，是优势航次知识的挖掘对象。航次任务的类型主要由船舶的类型、货物、航线的远近这3个方面决定。

船舶的类型主要是指船舶的吨位与结构。以船舶的吨位分类为：①1～3.9万吨便型船：船舶吃水一般控制在9～10米之间；②4～5.9万吨大灵便型船：这种船舶吃水一般在11米左右；③6～7.9万吨巴拿马型船：船型主要受到巴拿马运河的限制；④8～19万吨好望角型船：经过好望角连接大西洋和太平洋的典型船型；⑤20万吨以上的超大型货船。船舶的结构决定了船舶能够装载的货物类型，在航次任务特征中，船舶装载货物的类型与货物类型这一属性等同，将在货物类型中考虑。

货物主要指在航次任务中运载的货物的类型与货物的比数。根据货物的形态和包装，航海界将海上运输货物类型划分为：液体货、干散货、件杂货3大类。3大类货物是这样划分的：①液体货物：石油、成品油、液化燃气、液态化学品、其它液体货物。②干散货：各种初级产品、原材料。通常根据运输批量的大小，干散货又分为大宗散货和小宗批量散货两类，大宗散货主要有：煤炭、金属矿石、粮食等；小宗批量散货包括：钢铁、木材、化肥、水泥等。③件杂货：这些货物一般以 “件”“箱” “捆”等形式托运，包括包装货物、裸装货物和成组化货物。货物的批数指的是同时装载货物的批数。在运输过程中，航次任务可以是从同一地点或不同地点装载两种或两种以上的货物。

航线按航线的远近被分为以下几类：①远洋航线，指航程距离较远，船舶航行跨越大洋的运输航线。②近洋航线，指本国各港口至邻近国家港口间的海上运输航线的统称。③沿海航线，指本国沿海各港之间的海上运输航线。

由上分析，航次特征属性主要有船舶吨位、货物种类、货物批数、航线远近组成，它们的属性值即为各自的分类。决策属性是指航次案例的盈利情况，分为亏损与盈利。

表1总结了在构建决策树是需要条件属性与决策属性及其值域。

2 基于CLS算法的航次优势决策树学习

CLS（Concept Learning System）学习算法是1966年由Hunt等人提出的，CLS算法的主要思想是从一个空的决策树出发，通过添加新的判定结点来改善原来的决策树，直至该决策树能够正确地将训练实例分类为止，决策树的构造过程也是假设特化的过程[1]。本文以CLS学习算法为基础，设计了从航次任务特征数据表中进行学习，获取航次盈利优势知识的算法。其具体步骤如下： （1）从航次案例库中选取航次任务特征数据，构建航次任务特征数据表。 （2）确定航次任务特征数据表中的条件属性集A和决策属性集D。 （3）航次任务特征数据表转换，将条件属性集和决策属性集的值V离化，生成新的航次任务特征数据表，按此开始训练。 （4）令航次优势决策树T的初始状态只含有一个树根（X,Q），其中X是全体航次特征训练实例的集合，Q是全体决策属性的集合。 （5）若T的所有中结点（X',D'）都有如下状态：或者第一个分量X'中的训练实例都属于同一类，即其决策属性相同，或者第二个分量D'为空，则停止执行学习算法，学习的结果为航次优势决策树。 （6）否则，选取一个不具备有步骤 （5）所述状态的叶结点（X',D'）。 （7）对于D'，按照一定的规则选取测试属性b，设X'被b的不同取值分为m个不相交的子集Xi'，1≤i≤m，从（X',D'）伸出m个分支，每个分支代表b的一个不同取值，从而形成m个新的中结点（Xi',D'-｛b｝）， 1≤i≤m。 （8） 转步骤 （5）。

表1 决策树条件属性与决策属性

3 基于C4.5算法的条件属性重要判断方法

在步骤 （7）中，测试属性b的选取至关重要，当前最有影响的是Quinlan于1979年提出的以信息熵的下降速度作为选取测试属性的标准ID3算法[2]。

设训练实例集为X，目的是将训练实例分为n类。设属于第i类的训练实例个数是Ci，X中总的训练实例个数为，若记一个实例属性第i类的概率为P（ Ci），则：

此时决策树对划分C的不确定程度为：H（ X,C）=-ΣP（ Ci）log2P（ Ci）

在无混淆的情况下可将H（ X,C ）简记为H（X ）。

决策树学习过程就是使得决策树对划分的不确定程度逐渐减少的过程。若选择测试属性a进行测试，在得知a＝aj的情况下属于第i类的实例个数为Cij个。即p（ C ; a=a）为在测试属性a的取值为a时它属于第i类的概率。此时ijj决策树对分类的不确定程度就是训练实例集对属性X的条件熵。

又因为在选择测试属性a后申出的每个a＝aj叶结点Xj对于分类信息的信息熵为：

属性a对于分类提供的信息量I X;（）a 为：

式 （1）的值越小则式 （2）的值越大，说明选择测试属性a对于分类提供的信息越来越大，选择a之后对于分类的不确定程度越小。Quinlan的ID3算法就是选择使得I（ X;a ）最大的属性作为测试属性，即选择使得式 （1）最小。

在ID3算法当中，只考虑了实类分类过程当中的变化，但是有时为了知道一个实例关于属性a的取值，需要做试验、计算等，这是需要付出一定代价的。设属性a取值a1,a2,…,ak，它们拥有的实例个数分别为n1+n2+…+nk=n，其中n为训练实例的总数。Quinlan利用属性a的熵值V（ X,a）来定义为了获取实例关于属性a的取值所需付出的代价：

在属性a提供相同的信息量I（ X,a）的同时，V（ X,a ）的取值越小越好，其值越小说明为了获取关于属性a的取值所需付出的代价也就越小。Quinlan定义了另外一种测试属性选取标准：E（ X,a）=I（ X,a）/V（ X,a）

即选取使得E（ X,a ）最大的属性a作为测试属性。C4.5算法就是基于这种度量方法的。

4 实 证

从航次实例数据中选取与航次特征相关的数据，并按分类转化为可供挖掘的形势，如表2所示。

根据上述方法获得优势航次知识决策树 （如图1）所示。

表2 航次任务特征数据

图1

[1] 史忠植.知识发现[M].北京：清华大学出版社，2002.

[2] J.Ross Quinlan.C4.5:Programs for Machine Learning[M].Morgan Kaufmann Publishers Inc.San Francisco,CA,USA,1993.