邵旻暉，張　琳，周　凡

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

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

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

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

1.1　決策樹C4.5算法

決策樹是由內(nèi)部節(jié)點和葉節(jié)點構(gòu)成的類似于流程圖的樹結(jié)構(gòu)，內(nèi)部節(jié)點表示對屬性的測試，葉節(jié)點代表最終的分類結(jié)果，其目的主要是分類與決策[10]。決策樹分類算法的優(yōu)點是能高效地對海量數(shù)據(jù)集中的信息進(jìn)行分類，通過自身的學(xué)習(xí)獲取知識，并以決策樹的形式表示出來。以決策樹形式表示的知識不僅清晰直觀,而且具有很高的推理效率(決策樹推理就是對決策樹的遍歷)[10]。C4.5算法是數(shù)據(jù)挖掘中最常用、最經(jīng)典的分類算法[11]。C4.5算法是根據(jù)信息增益率(Information Gain Ratio)選擇測試屬性，是非常有效的監(jiān)督式學(xué)習(xí)模式，通過學(xué)習(xí)，最終找到一個從屬性值到類別的映射關(guān)系，并且這個映射能用于對新的類別未知的實體進(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算法采用的是隨機且有放回的從訓(xùn)練集中進(jìn)行子抽樣，組成所需要的子訓(xùn)練集，通過分類子訓(xùn)練集訓(xùn)練多個分類器,最后組合產(chǎn)生最終的預(yù)測結(jié)果。Boosting是一種框架算法，通過將多個弱學(xué)習(xí)器組合成一個強學(xué)習(xí)器，明顯地提高了分類器的精度[16]。該算法根據(jù)學(xué)習(xí)時間和使用弱分類器的數(shù)量，逐步改進(jìn)預(yù)測過程，通過有限次的迭代，這些弱學(xué)習(xí)器的加權(quán)集成便形成了最終的強學(xué)習(xí)器[16]。

2　最佳通信漁船選擇方法

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

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

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

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

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

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

表1　屬性列表

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

2.2　屬性選擇方法

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

2.3　使用C4.5算法分類

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

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

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

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

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

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

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

練過程對錯誤分類樣本加以重視，最終達(dá)到所要求的測試性能[21]。在Bagging算法中，每個訓(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)練各個子分類器，最終對所有的子分類器進(jìn)行組合[21]。這里將C4.5算法作為基本學(xué)習(xí)算法，得到多個弱學(xué)習(xí)器，分別使用Bagging算法和Boosting算法構(gòu)建強學(xué)習(xí)器。

3　結(jié)果與分析

3.1　結(jié)果

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

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

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

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

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

3.2　分類結(jié)果分析

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

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

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

3.3　分類性能分析

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

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

4　結(jié)論

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

□