基于決策樹學習的航運企業(yè)優(yōu)勢航次知識發(fā)現(xiàn)

夏明星， 胡正華， 張 濤 （南京航空航天大學，江蘇 南京 210016）

0 引 言

航運企業(yè)在承接航運任務時面臨的首要問題是什么樣類型的航運任務盈利的可能性大，或者說容易盈利。航運企業(yè)自身狀況的不同，導致了航運企業(yè)對航運任務的運營控制能力不同。不同的航運企業(yè)擅長組織管理航運任務類型不同。有的企業(yè)可能只擅長控制比較短途的航運任務，而對于有的航運企業(yè)來說，可能更容易從長途的航運業(yè)務中獲取利潤。對于每個航運企業(yè)來說，弄清楚自己的優(yōu)勢所在，避開自己的弱勢來承接航運任務，是非常重要的。

1 航次任務特征屬性

在基于決策樹的航次優(yōu)勢知識發(fā)現(xiàn)中，條件屬性是指航次任務特征屬性。航次任務特征屬性是指那些可以用于區(qū)分每個航次任務類型的航次屬性，是優(yōu)勢航次知識的挖掘對象。航次任務的類型主要由船舶的類型、貨物、航線的遠近這3個方面決定。

船舶的類型主要是指船舶的噸位與結構。以船舶的噸位分類為：①1～3.9萬噸便型船：船舶吃水一般控制在9～10米之間；②4～5.9萬噸大靈便型船：這種船舶吃水一般在11米左右；③6～7.9萬噸巴拿馬型船：船型主要受到巴拿馬運河的限制；④8～19萬噸好望角型船：經(jīng)過好望角連接大西洋和太平洋的典型船型；⑤20萬噸以上的超大型貨船。船舶的結構決定了船舶能夠裝載的貨物類型，在航次任務特征中，船舶裝載貨物的類型與貨物類型這一屬性等同，將在貨物類型中考慮。

貨物主要指在航次任務中運載的貨物的類型與貨物的比數(shù)。根據(jù)貨物的形態(tài)和包裝，航海界將海上運輸貨物類型劃分為：液體貨、干散貨、件雜貨3大類。3大類貨物是這樣劃分的：①液體貨物：石油、成品油、液化燃氣、液態(tài)化學品、其它液體貨物。②干散貨：各種初級產(chǎn)品、原材料。通常根據(jù)運輸批量的大小，干散貨又分為大宗散貨和小宗批量散貨兩類，大宗散貨主要有：煤炭、金屬礦石、糧食等；小宗批量散貨包括：鋼鐵、木材、化肥、水泥等。③件雜貨：這些貨物一般以 “件”“箱” “捆”等形式托運，包括包裝貨物、裸裝貨物和成組化貨物。貨物的批數(shù)指的是同時裝載貨物的批數(shù)。在運輸過程中，航次任務可以是從同一地點或不同地點裝載兩種或兩種以上的貨物。

航線按航線的遠近被分為以下幾類：①遠洋航線，指航程距離較遠，船舶航行跨越大洋的運輸航線。②近洋航線，指本國各港口至鄰近國家港口間的海上運輸航線的統(tǒng)稱。③沿海航線，指本國沿海各港之間的海上運輸航線。

由上分析，航次特征屬性主要有船舶噸位、貨物種類、貨物批數(shù)、航線遠近組成，它們的屬性值即為各自的分類。決策屬性是指航次案例的盈利情況，分為虧損與盈利。

表1總結了在構建決策樹是需要條件屬性與決策屬性及其值域。

2 基于CLS算法的航次優(yōu)勢決策樹學習

CLS（Concept Learning System）學習算法是1966年由Hunt等人提出的，CLS算法的主要思想是從一個空的決策樹出發(fā)，通過添加新的判定結點來改善原來的決策樹，直至該決策樹能夠正確地將訓練實例分類為止，決策樹的構造過程也是假設特化的過程[1]。本文以CLS學習算法為基礎，設計了從航次任務特征數(shù)據(jù)表中進行學習，獲取航次盈利優(yōu)勢知識的算法。其具體步驟如下： （1）從航次案例庫中選取航次任務特征數(shù)據(jù)，構建航次任務特征數(shù)據(jù)表。 （2）確定航次任務特征數(shù)據(jù)表中的條件屬性集A和決策屬性集D。 （3）航次任務特征數(shù)據(jù)表轉換，將條件屬性集和決策屬性集的值V離化，生成新的航次任務特征數(shù)據(jù)表，按此開始訓練。 （4）令航次優(yōu)勢決策樹T的初始狀態(tài)只含有一個樹根（X,Q），其中X是全體航次特征訓練實例的集合，Q是全體決策屬性的集合。 （5）若T的所有中結點（X',D'）都有如下狀態(tài)：或者第一個分量X'中的訓練實例都屬于同一類，即其決策屬性相同，或者第二個分量D'為空，則停止執(zhí)行學習算法，學習的結果為航次優(yōu)勢決策樹。 （6）否則，選取一個不具備有步驟 （5）所述狀態(tài)的葉結點（X',D'）。 （7）對于D'，按照一定的規(guī)則選取測試屬性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類的訓練實例個數(shù)是Ci，X中總的訓練實例個數(shù)為，若記一個實例屬性第i類的概率為P（ Ci），則：

此時決策樹對劃分C的不確定程度為：H（ X,C）=-ΣP（ Ci）log2P（ Ci）

在無混淆的情況下可將H（ X,C ）簡記為H（X ）。

決策樹學習過程就是使得決策樹對劃分的不確定程度逐漸減少的過程。若選擇測試屬性a進行測試，在得知a＝aj的情況下屬于第i類的實例個數(shù)為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，它們擁有的實例個數(shù)分別為n1+n2+…+nk=n，其中n為訓練實例的總數(shù)。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 實 證

從航次實例數(shù)據(jù)中選取與航次特征相關的數(shù)據(jù)，并按分類轉化為可供挖掘的形勢，如表2所示。

根據(jù)上述方法獲得優(yōu)勢航次知識決策樹 （如圖1）所示。

表2 航次任務特征數(shù)據(jù)

圖1

[1] 史忠植.知識發(fā)現(xiàn)[M].北京：清華大學出版社，2002.

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