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

邵旻暉，張　琳，周　凡

(上海海事大學信息工程學院，上海 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%。在現實環境中，決策樹能在相對短的時間內對數據集做出可行且效果良好的分類，只需要一次構建并可反復使用。本研究將有助于保障岸邊和漁船的通信效率并及時向離岸較遠的目標漁船發送信息。

□