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

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

0 引 言

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

1 航次任務(wù)特征屬性

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

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

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

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

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

表1總結(jié)了在構(gòu)建決策樹(shù)是需要條件屬性與決策屬性及其值域。

2 基于CLS算法的航次優(yōu)勢(shì)決策樹(shù)學(xué)習(xí)

CLS（Concept Learning System）學(xué)習(xí)算法是1966年由Hunt等人提出的，CLS算法的主要思想是從一個(gè)空的決策樹(shù)出發(fā)，通過(guò)添加新的判定結(jié)點(diǎn)來(lái)改善原來(lái)的決策樹(shù)，直至該決策樹(shù)能夠正確地將訓(xùn)練實(shí)例分類為止，決策樹(shù)的構(gòu)造過(guò)程也是假設(shè)特化的過(guò)程[1]。本文以CLS學(xué)習(xí)算法為基礎(chǔ)，設(shè)計(jì)了從航次任務(wù)特征數(shù)據(jù)表中進(jìn)行學(xué)習(xí)，獲取航次盈利優(yōu)勢(shì)知識(shí)的算法。其具體步驟如下： （1）從航次案例庫(kù)中選取航次任務(wù)特征數(shù)據(jù)，構(gòu)建航次任務(wù)特征數(shù)據(jù)表。 （2）確定航次任務(wù)特征數(shù)據(jù)表中的條件屬性集A和決策屬性集D。 （3）航次任務(wù)特征數(shù)據(jù)表轉(zhuǎn)換，將條件屬性集和決策屬性集的值V離化，生成新的航次任務(wù)特征數(shù)據(jù)表，按此開(kāi)始訓(xùn)練。 （4）令航次優(yōu)勢(shì)決策樹(shù)T的初始狀態(tài)只含有一個(gè)樹(shù)根（X,Q），其中X是全體航次特征訓(xùn)練實(shí)例的集合，Q是全體決策屬性的集合。 （5）若T的所有中結(jié)點(diǎn)（X',D'）都有如下?tīng)顟B(tài)：或者第一個(gè)分量X'中的訓(xùn)練實(shí)例都屬于同一類，即其決策屬性相同，或者第二個(gè)分量D'為空，則停止執(zhí)行學(xué)習(xí)算法，學(xué)習(xí)的結(jié)果為航次優(yōu)勢(shì)決策樹(shù)。 （6）否則，選取一個(gè)不具備有步驟 （5）所述狀態(tài)的葉結(jié)點(diǎn)（X',D'）。 （7）對(duì)于D'，按照一定的規(guī)則選取測(cè)試屬性b，設(shè)X'被b的不同取值分為m個(gè)不相交的子集Xi'，1≤i≤m，從（X',D'）伸出m個(gè)分支，每個(gè)分支代表b的一個(gè)不同取值，從而形成m個(gè)新的中結(jié)點(diǎn)（Xi',D'-｛b｝）， 1≤i≤m。 （8） 轉(zhuǎn)步驟 （5）。

表1 決策樹(shù)條件屬性與決策屬性

3 基于C4.5算法的條件屬性重要判斷方法

在步驟 （7）中，測(cè)試屬性b的選取至關(guān)重要，當(dāng)前最有影響的是Quinlan于1979年提出的以信息熵的下降速度作為選取測(cè)試屬性的標(biāo)準(zhǔn)ID3算法[2]。

設(shè)訓(xùn)練實(shí)例集為X，目的是將訓(xùn)練實(shí)例分為n類。設(shè)屬于第i類的訓(xùn)練實(shí)例個(gè)數(shù)是Ci，X中總的訓(xùn)練實(shí)例個(gè)數(shù)為，若記一個(gè)實(shí)例屬性第i類的概率為P（ Ci），則：

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

在無(wú)混淆的情況下可將H（ X,C ）簡(jiǎn)記為H（X ）。

決策樹(shù)學(xué)習(xí)過(guò)程就是使得決策樹(shù)對(duì)劃分的不確定程度逐漸減少的過(guò)程。若選擇測(cè)試屬性a進(jìn)行測(cè)試，在得知a＝aj的情況下屬于第i類的實(shí)例個(gè)數(shù)為Cij個(gè)。即p（ C ; a=a）為在測(cè)試屬性a的取值為a時(shí)它屬于第i類的概率。此時(shí)ijj決策樹(shù)對(duì)分類的不確定程度就是訓(xùn)練實(shí)例集對(duì)屬性X的條件熵。

又因?yàn)樵谶x擇測(cè)試屬性a后申出的每個(gè)a＝aj葉結(jié)點(diǎn)Xj對(duì)于分類信息的信息熵為：

屬性a對(duì)于分類提供的信息量I X;（）a 為：

式 （1）的值越小則式 （2）的值越大，說(shuō)明選擇測(cè)試屬性a對(duì)于分類提供的信息越來(lái)越大，選擇a之后對(duì)于分類的不確定程度越小。Quinlan的ID3算法就是選擇使得I（ X;a ）最大的屬性作為測(cè)試屬性，即選擇使得式 （1）最小。

在ID3算法當(dāng)中，只考慮了實(shí)類分類過(guò)程當(dāng)中的變化，但是有時(shí)為了知道一個(gè)實(shí)例關(guān)于屬性a的取值，需要做試驗(yàn)、計(jì)算等，這是需要付出一定代價(jià)的。設(shè)屬性a取值a1,a2,…,ak，它們擁有的實(shí)例個(gè)數(shù)分別為n1+n2+…+nk=n，其中n為訓(xùn)練實(shí)例的總數(shù)。Quinlan利用屬性a的熵值V（ X,a）來(lái)定義為了獲取實(shí)例關(guān)于屬性a的取值所需付出的代價(jià)：

在屬性a提供相同的信息量I（ X,a）的同時(shí)，V（ X,a ）的取值越小越好，其值越小說(shuō)明為了獲取關(guān)于屬性a的取值所需付出的代價(jià)也就越小。Quinlan定義了另外一種測(cè)試屬性選取標(biāo)準(zhǔn)：E（ X,a）=I（ X,a）/V（ X,a）

即選取使得E（ X,a ）最大的屬性a作為測(cè)試屬性。C4.5算法就是基于這種度量方法的。

4 實(shí) 證

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

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

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

圖1

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

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