基于決策樹的最佳通信漁船選擇方法

邵旻暉，張　琳，周　凡

(上海海事大學(xué)信息工程學(xué)院，上海 201306)

無線網(wǎng)絡(luò)技術(shù)的快速發(fā)展為海洋與漁業(yè)部門在海上通信提供了巨大的幫助。早在2004年，中國(guó)就建設(shè)了全國(guó)海洋漁業(yè)安全通信網(wǎng)，包括短波、超短波[1-2]、衛(wèi)星監(jiān)測(cè)[3-4]、公眾移動(dòng)通信等，并開始運(yùn)用信息化手段服務(wù)于漁業(yè)發(fā)展[5]。但是在距離海岸10～15 n mile及以外的地方，由于海上不確定的環(huán)境變化，無線網(wǎng)絡(luò)的信號(hào)強(qiáng)度會(huì)被削弱，漁船和岸上之間的信息交流會(huì)受到巨大影響[6]。因此，急需發(fā)展海洋漁業(yè)通信技術(shù)。徐碩等[1]提出了一套專用于漁船之間高可靠性遠(yuǎn)距離傳輸?shù)臄?shù)字通信網(wǎng)絡(luò)系統(tǒng)，形成一套漁船之間、漁船與岸臺(tái)之間的有效通信網(wǎng)絡(luò)。沈丹丹[2]提出了一種海上漁船超短波無線自組織網(wǎng)絡(luò)，用于彌補(bǔ)超短波不能遠(yuǎn)距離通信的缺陷，可更好地為海上通信服務(wù)。夏明華等[6]針對(duì)中國(guó)南海島礁眾多的地理特點(diǎn)，提出了一種新型海洋通信網(wǎng)絡(luò)架構(gòu)，通過固定的島礁或者海上浮臺(tái)、飛艇、無人船等中繼節(jié)點(diǎn)建立新的高速寬帶鏈路。Kolios等[7]基于現(xiàn)有船舶自動(dòng)識(shí)別系統(tǒng)(AIS)獲得船舶移動(dòng)數(shù)據(jù)，預(yù)測(cè)船—船相遇模型，構(gòu)建了從任意節(jié)點(diǎn)向目標(biāo)節(jié)點(diǎn)傳遞消息的最優(yōu)路徑，優(yōu)化信息傳輸性能。

相關(guān)研究表明，在漁船間構(gòu)建專用于漁船的無線通信網(wǎng)絡(luò)系統(tǒng)已成為可能[1-2]，而且，選擇一個(gè)海洋無線網(wǎng)絡(luò)中的最優(yōu)通信節(jié)點(diǎn)能保證艦船通信的高效性和可靠性[6-7]。針對(duì)漁船移動(dòng)和海上環(huán)境的特殊性，本研究提出了一種使用數(shù)據(jù)挖掘算法來選擇漁船無線通信網(wǎng)絡(luò)系統(tǒng)中最優(yōu)通信節(jié)點(diǎn)的方法。為了獲取漁船集群中的最優(yōu)通信節(jié)點(diǎn)，采用決策樹中的C4.5算法，通過分析漁船自身的信號(hào)強(qiáng)度和基于AIS數(shù)據(jù)[8-9]的環(huán)境參數(shù)(風(fēng)速、海面溫度和海面氣壓)，對(duì)漁船的無線通信狀態(tài)進(jìn)行分類。決策樹算法的分類結(jié)果將幫助尋找用來發(fā)送岸上信息的最佳船只，可以是附近具有良好信號(hào)強(qiáng)度并可建立連接的船只。因?yàn)闈O船所處的位置和環(huán)境條件的不同，海上漁船的通信狀態(tài)會(huì)不斷發(fā)生變化。為了向指定的船只發(fā)送信息，需要得知漁船的位置和狀態(tài)，這在一定程度上也有助于發(fā)現(xiàn)偏離漁場(chǎng)的船只。

1　決策樹與集成學(xué)習(xí)

1.1　決策樹C4.5算法

決策樹是由內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)構(gòu)成的類似于流程圖的樹結(jié)構(gòu)，內(nèi)部節(jié)點(diǎn)表示對(duì)屬性的測(cè)試，葉節(jié)點(diǎn)代表最終的分類結(jié)果，其目的主要是分類與決策[10]。決策樹分類算法的優(yōu)點(diǎn)是能高效地對(duì)海量數(shù)據(jù)集中的信息進(jìn)行分類，通過自身的學(xué)習(xí)獲取知識(shí)，并以決策樹的形式表示出來。以決策樹形式表示的知識(shí)不僅清晰直觀,而且具有很高的推理效率(決策樹推理就是對(duì)決策樹的遍歷)[10]。C4.5算法是數(shù)據(jù)挖掘中最常用、最經(jīng)典的分類算法[11]。C4.5算法是根據(jù)信息增益率(Information Gain Ratio)選擇測(cè)試屬性，是非常有效的監(jiān)督式學(xué)習(xí)模式，通過學(xué)習(xí)，最終找到一個(gè)從屬性值到類別的映射關(guān)系，并且這個(gè)映射能用于對(duì)新的類別未知的實(shí)體進(jìn)行分類[12]。

1.2　集成學(xué)習(xí)算法

在數(shù)據(jù)挖掘中，單一的分類算法往往存在缺陷，比如C4.5算法受到數(shù)據(jù)集合中的奇異數(shù)據(jù)影響較大[13]。因此，研究者提出集成學(xué)習(xí)的概念，其中應(yīng)用最廣泛的集成學(xué)習(xí)算法是Bagging算法[14]和Boosting算法[15]。Bagging算法采用的是隨機(jī)且有放回的從訓(xùn)練集中進(jìn)行子抽樣，組成所需要的子訓(xùn)練集，通過分類子訓(xùn)練集訓(xùn)練多個(gè)分類器,最后組合產(chǎn)生最終的預(yù)測(cè)結(jié)果。Boosting是一種框架算法，通過將多個(gè)弱學(xué)習(xí)器組合成一個(gè)強(qiáng)學(xué)習(xí)器，明顯地提高了分類器的精度[16]。該算法根據(jù)學(xué)習(xí)時(shí)間和使用弱分類器的數(shù)量，逐步改進(jìn)預(yù)測(cè)過程，通過有限次的迭代，這些弱學(xué)習(xí)器的加權(quán)集成便形成了最終的強(qiáng)學(xué)習(xí)器[16]。

2　最佳通信漁船選擇方法

研究目標(biāo)是在海洋無線通信環(huán)境下，通過考慮漁船各自的信號(hào)強(qiáng)度和環(huán)境條件，用決策樹集成算法對(duì)漁船的數(shù)據(jù)集進(jìn)行分類，決策樹的分類結(jié)果將幫助尋找具有良好通信條件的船只節(jié)點(diǎn)。這有助于使無線數(shù)據(jù)在無線網(wǎng)絡(luò)覆蓋區(qū)域下的所有節(jié)點(diǎn)上進(jìn)行交換，實(shí)現(xiàn)岸邊和海上漁船的連續(xù)實(shí)時(shí)通信。

系統(tǒng)工作流程如下：1)基于無線通信數(shù)據(jù)，分析漁船的海上位置；2)將C4.5決策樹分類算法應(yīng)用于訓(xùn)練集，以識(shí)別通信的可能性；3)應(yīng)用集成學(xué)習(xí)算法(Bagging、Boosting)，以提高決策樹的精度；4)根據(jù)決策樹的分類結(jié)果尋找最適合通信的漁船；5)建立岸邊與最佳通信漁船的連接，若漁船在出海作業(yè)期間發(fā)生任何情況，及時(shí)通過最佳通信漁船向相應(yīng)的船只傳送信息。系統(tǒng)架構(gòu)如圖1所示。

圖1　系統(tǒng)架構(gòu)

漁船的數(shù)據(jù)來自船訊網(wǎng)(http://www.shipxy.com/)，選澤屬于舟山市普陀區(qū)在舟山漁場(chǎng)作業(yè)的漁船(圖2)。點(diǎn)擊某只漁船可以查看漁船的位置信息和其所在海域的氣象信息。向哲等[17]提出了一種利用海量的AIS歷史數(shù)據(jù)、插值算法和網(wǎng)格化技術(shù)的GridCount算法[17]。漁船自身的信號(hào)強(qiáng)度可以按照文獻(xiàn)[17]的方法計(jì)算。最終選取了200艘漁船的數(shù)據(jù)集進(jìn)行評(píng)估。

2.1　數(shù)據(jù)集預(yù)處理

從數(shù)據(jù)庫(kù)中隨機(jī)選擇一組數(shù)據(jù)集，記為訓(xùn)練集A。訓(xùn)練集A中的屬性(表1)包括了漁船的位置(經(jīng)度和緯度)、風(fēng)速、海面溫度、海面氣壓和信號(hào)強(qiáng)度。使用訓(xùn)練數(shù)據(jù)來預(yù)測(cè)岸邊和海上漁船的通信狀態(tài)。通信狀態(tài)分為三類:好、一般、差。

表1　屬性列表

圖2　在舟山漁場(chǎng)作業(yè)的漁船

2.2　屬性選擇方法

屬性選擇的原則是選擇能夠最佳分離給定訓(xùn)練集A到單個(gè)類別的屬性。如果分裂屬性能盡可能地把訓(xùn)練集A分裂成更小的分區(qū)，那么這個(gè)分區(qū)所代表的結(jié)果就越簡(jiǎn)單，這個(gè)分裂屬性就被選擇為給定訓(xùn)練元組的分裂屬性。如果被選中的分裂屬性是連續(xù)值，那么分裂節(jié)點(diǎn)就被確定；如果分裂屬性是離散值且要求生成二叉決策樹，那么分裂子集也必須與分裂規(guī)則一起決定。分裂節(jié)點(diǎn)將被分裂規(guī)則標(biāo)記，分裂規(guī)則的每個(gè)結(jié)果會(huì)生成分支，并相應(yīng)地對(duì)訓(xùn)練集A進(jìn)行劃分。這里采用的屬性選擇方法是信息增益和信息增益率。

2.3　使用C4.5算法分類

在尋找最佳通信漁船的方法下，最終分類結(jié)果是“好”、“一般”和“差”的通信狀態(tài)，而分類屬性列表由經(jīng)度、緯度、風(fēng)速、海面溫度、海面氣壓和信號(hào)強(qiáng)度組成，其中經(jīng)度和緯度被用來計(jì)算漁船的信號(hào)強(qiáng)度。在決策樹中，迭代地選擇信息增益最高的屬性作為決策樹節(jié)點(diǎn)的分裂屬性。

最終分類結(jié)果是通信狀態(tài)，具有3個(gè)不同的類。設(shè)C1類對(duì)應(yīng)于0(即通信好)，C2類對(duì)應(yīng)于1(即通信一般)，C3類對(duì)應(yīng)于2(即通信差)，輸入的訓(xùn)練集都被分成這3類。為了獲得這些訓(xùn)練元組的分裂規(guī)則，分別按照訓(xùn)練集的各個(gè)屬性對(duì)數(shù)據(jù)進(jìn)行分類，對(duì)每個(gè)分類結(jié)果，計(jì)算相應(yīng)的信息增益率[18]。

對(duì)訓(xùn)練集A，設(shè)Fi(i=1,2,3,…,n)為分類標(biāo)記屬性有n個(gè)不同的值，屬性X有m個(gè)不同的取值x={x1,x2,…,xm}，可以用屬性X將訓(xùn)練集A離散地劃分為m個(gè)子集{A1,A2,…,Am}，其中子集Aj包含了訓(xùn)練集A中的元組，在屬性X上的值為xj，主要計(jì)算[18-19]：

計(jì)算訓(xùn)練集A中元組的信息熵E(A):

(1)

計(jì)算使用屬性對(duì)訓(xùn)練集A進(jìn)行分類的信息熵E(XA):

(2)

計(jì)算屬性X的信息增益G(X)：

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

(3)

計(jì)算屬性X的分裂信息S(XA)：

(4)

計(jì)算屬性X的信息增益率R(X)：

(5)

最后，按照與最大信息增益率對(duì)應(yīng)的屬性，將當(dāng)前訓(xùn)練集劃分為不同的子集，建立相應(yīng)的決策樹分支，形成新的子節(jié)點(diǎn)[20]。由于篇幅有限，此處未給出具體的計(jì)算過程。在大多數(shù)情況下，選擇信號(hào)強(qiáng)度作為分裂屬性。

2.4　集成學(xué)習(xí)

集成學(xué)習(xí)(Ensemble learning)是使用一系列個(gè)體學(xué)習(xí)器進(jìn)行學(xué)習(xí)，并使用某種結(jié)合策略把多個(gè)學(xué)習(xí)器進(jìn)行集成從而獲得比使用單一學(xué)習(xí)器更強(qiáng)泛化能力的一種機(jī)器學(xué)習(xí)方法。在Boosting算法(以Adaboost為例)中，首先初始化訓(xùn)練集A上樣本的權(quán)值并賦予相同的權(quán)值為1/n，然后進(jìn)行T輪迭代訓(xùn)練。在每輪訓(xùn)練結(jié)束后，降低正確分類的樣本權(quán)重，增加錯(cuò)誤分類的樣本權(quán)重，使下次訓(xùn)

練過程對(duì)錯(cuò)誤分類樣本加以重視，最終達(dá)到所要求的測(cè)試性能[21]。在Bagging算法中，每個(gè)訓(xùn)練集都是通過原始訓(xùn)練集的bootstrap復(fù)制而構(gòu)造的。也就是說，Bagging算法通過bootstrap方法在訓(xùn)練集A上進(jìn)行有放回的抽取樣本來構(gòu)成訓(xùn)練數(shù)據(jù)的子集，然后通過訓(xùn)練數(shù)據(jù)的子集來訓(xùn)練各個(gè)子分類器，最終對(duì)所有的子分類器進(jìn)行組合[21]。這里將C4.5算法作為基本學(xué)習(xí)算法，得到多個(gè)弱學(xué)習(xí)器，分別使用Bagging算法和Boosting算法構(gòu)建強(qiáng)學(xué)習(xí)器。

3　結(jié)果與分析

3.1　結(jié)果

在這種用于選擇海上最佳通信漁船的方法中，對(duì)舟山漁場(chǎng)的200個(gè)漁船實(shí)例進(jìn)行試驗(yàn)，考慮了4個(gè)屬性：信號(hào)強(qiáng)度、風(fēng)速、海面溫度和海面氣壓。使用C4.5分類算法實(shí)現(xiàn)了對(duì)訓(xùn)練集中各個(gè)屬性的合理分類。圖3顯示了使用C4.5算法生成的決策樹。

圖3　C4.5算法生成的決策樹

采用10折交叉驗(yàn)證來測(cè)試分類器的性能，將數(shù)據(jù)集平均劃分為10份，其中9份用來訓(xùn)練，1份用來測(cè)試[22]。通過分析測(cè)試集上的算法泛化精度、正確分類實(shí)例的百分比、均方根誤差和Kappa數(shù)據(jù)，對(duì)集成學(xué)習(xí)和決策樹本身的精度進(jìn)行性能比較。表2給出了性能比較結(jié)果，表3給出了精度、均方根誤差和Kappa系數(shù)的比較結(jié)果。

表2　決策樹與集成學(xué)習(xí)方法的性能比較

表3　　　　決策樹與集成學(xué)習(xí)方法在精度、均方根誤差

3.2　分類結(jié)果分析

從決策樹的最終分類結(jié)果中發(fā)現(xiàn)，在大多數(shù)情況下，漁船自身的信號(hào)強(qiáng)度是影響漁船之間通信的最重要的屬性。當(dāng)漁船的信號(hào)強(qiáng)度>-50 dBm時(shí)(即信號(hào)強(qiáng)度較好)，海面的環(huán)境因素對(duì)漁船的通信狀態(tài)基本沒有影響，通常都是好的，適合被選擇成為最佳通信漁船。

但是，風(fēng)速、海面氣壓、海面溫度等海上環(huán)境因素會(huì)對(duì)海上無線通信產(chǎn)生不利影響。當(dāng)漁船自身的信號(hào)強(qiáng)度<-75 dBm時(shí)(即信號(hào)強(qiáng)度較差)，海面氣壓會(huì)干擾漁船的通信狀態(tài)，通信狀態(tài)最多達(dá)到一般。當(dāng)漁船的信號(hào)強(qiáng)度位于-75～-50 dBm時(shí)(即信號(hào)強(qiáng)度一般)，風(fēng)速和海面溫度會(huì)對(duì)漁船通信狀態(tài)產(chǎn)生影響，具體表現(xiàn)為：當(dāng)溫度≤20 ℃時(shí)(即較適宜)，若風(fēng)速≤30 km/h，漁船的通信狀態(tài)好，否則是一般。當(dāng)溫度>20 ℃時(shí)，若風(fēng)速≤30 km/h，漁船的通信狀態(tài)也是一般；若風(fēng)速>30 km/h且<35 km/h，漁船的通信狀態(tài)是一般；若風(fēng)速>35 km/h且自身的通信強(qiáng)度介于-75～-65 dBm之間，漁船的通信狀態(tài)是差的。

根據(jù)分類結(jié)果，可以從結(jié)果為“好”的那一類中的漁船中選取一艘或多艘作為最佳通信漁船，而當(dāng)被選中的漁船因?yàn)槲恢靡苿?dòng)或天氣變化而不再具備良好通信條件時(shí)，決策樹又會(huì)自動(dòng)選擇新的最佳通信船只。

3.3　分類性能分析

通過表2可以發(fā)現(xiàn)，與集成學(xué)習(xí)結(jié)合的決策樹算法的綜合精度都超過了95%，單一的決策樹算法的綜合精度也有94%，這意味著三種數(shù)據(jù)挖掘算法對(duì)訓(xùn)練集的預(yù)測(cè)效果均很好。此外，兩種與集成學(xué)習(xí)結(jié)合的決策樹算法雖然都比單一的決策樹算法在復(fù)雜程度和耗時(shí)上更高，但兩種決策樹集成算法的綜合精度都有了明顯的提高，分別使C4.5算法的正確分類率提升了1.55和1.22個(gè)百分點(diǎn)。

表3中的均方根誤差是觀測(cè)值與真值偏差的平方與觀測(cè)次數(shù)n比值的平方根，Kappa系數(shù)用于一致性檢驗(yàn)也可以用于衡量分類精度，通常追求低均方根誤差和高Kappa系數(shù)，因?yàn)檫@代表著更高的總體分類精度。通過表3可以發(fā)現(xiàn)，兩種與集成學(xué)習(xí)結(jié)合的決策樹算法都比單一的決策樹算法具有更低的均方根系數(shù)和更高的Kappa系數(shù)。這些都說明了集成學(xué)習(xí)通過提高系統(tǒng)泛化能力確實(shí)能夠提高整體精度。而Boosting算法和Bagging算法孰優(yōu)孰劣通常與采用的數(shù)據(jù)集特性有關(guān)，在文中的漁船數(shù)據(jù)集上，Boosting算法比Bagging算法有更好的表現(xiàn)。

4　結(jié)論

面對(duì)海洋環(huán)境復(fù)雜多變、通信環(huán)境惡劣的挑戰(zhàn)，提出一種基于決策樹的最佳通信漁船選擇方法，尋找一個(gè)漁船集群中具有良好信號(hào)強(qiáng)度的最佳節(jié)點(diǎn)作為通信節(jié)點(diǎn)。同時(shí)在決策樹C4.5算法中應(yīng)用集成學(xué)習(xí)算法(Bagging和Boosting)來提高算法分類的性能，性能分析結(jié)果表明，與Boosting算法結(jié)合的C4.5算法分類精度最高，可以達(dá)到95.76%。在現(xiàn)實(shí)環(huán)境中，決策樹能在相對(duì)短的時(shí)間內(nèi)對(duì)數(shù)據(jù)集做出可行且效果良好的分類，只需要一次構(gòu)建并可反復(fù)使用。本研究將有助于保障岸邊和漁船的通信效率并及時(shí)向離岸較遠(yuǎn)的目標(biāo)漁船發(fā)送信息。

□