用于SAR圖像海面溢油自動識別的Bagging-AdaBoost決策樹分類器系統(tǒng)

丁新濤， 曾 侃， 賀明霞

(中國海洋大學海洋遙感研究所，山東 青島 266003)

海上溢油是人類工業(yè)活動引發(fā)的嚴重海洋環(huán)境污染之一。上世紀90年代以來，國際上可用于海洋觀測的業(yè)務化衛(wèi)星大發(fā)展，為海上溢油事故監(jiān)測提供了無可比擬的新技術支持。其中，星載合成孔徑雷達(Synthetic Aperture Radar, SAR)具有高空間分辨率、全天時全天候工作等優(yōu)點，且對海面油膜的探測靈敏度高，被公認為監(jiān)測海面溢油的理想傳感器。

SAR對海面的成像機制基于雷達波與海面毛細波或短重力波的相互作用，其簡單模型是Bragg散射。海面油膜的存在，引起局部海表面張力的變大，導致海面粗糙度的變小，從而使Bragg后向散射系數(shù)變小。在SAR圖像上，海面油膜相對于周圍海面呈現(xiàn)為暗斑。但是，SAR圖像中的暗斑不僅是海面溢油，眾多大氣和海洋現(xiàn)象都可能導致SAR圖像中的暗斑，它們被稱為疑似溢油(look-alikes)。因此，利用星載SAR圖像監(jiān)測海面溢油的關鍵技術之一是海面溢油和疑似溢油的自動識別技術[1-3]。

目前,用于海面油膜識別的分類方法主要有四種，分別是概率統(tǒng)計模型[4-11]、神經(jīng)網(wǎng)絡[12-18]、決策樹[2,21-23]以及模糊邏輯[19-20,32]。這些方法的共同點是，通過各種方式試圖建立一個高檢測率的單分類器。實際上，獲得一個高檢測率及優(yōu)秀泛化性能和穩(wěn)定性能的強單分類器是相當困難的，因此，Schipire等于1990年代在計算機學習領域提出了將多個弱分類器組合為強分類器的算法[24]，其中包括Boosting算法及其改進型AdaBoost算法[25-26]和Bagging算法[30-31]。這些算法在計算機領域已成為分類器性能增強的通用方法。2006年，Geraldo L B Ramalho等在模式識別國際會議上首次以神經(jīng)網(wǎng)絡作為Boosting算法的內(nèi)核對SAR圖像進行海面溢油檢測[27]，結(jié)果顯示Boosting算法增強了神經(jīng)網(wǎng)絡的分類結(jié)果。2012年，Topouzelis等首次使用Bagging算法組合多個決策樹分類器對溢油和疑似溢油SAR圖像樣本進行分類，結(jié)果顯示Bagging算法增強了決策樹單分類器的識別性能[28]。

本研究針對1 448個Envisat/ASAR暗目標樣本，進一步驗證AdaBoost算法和Bagging算法對單分類器在SAR圖像海面溢油識別上的泛化性能和穩(wěn)定性能的增強效果，選擇決策樹(Decision Tree，DT)作為單分類器內(nèi)核。同時，在AdaBoost-DT分類器系統(tǒng)(DT-A)和Bagging-DT分類器系統(tǒng)(DT-B)的基礎上，本研究提出使用Bagging算法組合多個AdaBoost-DT分類器系統(tǒng)(DT-A)構(gòu)成Bagging-AdaBoost-決策樹分類器系統(tǒng)(DT-AB)，以期進一步增強自動識別分類器的檢測率、泛化性能和穩(wěn)定性能。

1 基本方法

1.1 決策樹算法

決策樹是一種樹形結(jié)構(gòu)的識別、分類算法。其基本思想是以不純度為度量指標，構(gòu)造一棵不純度下降最快的樹。不純度是指某樹節(jié)點上樣本多類別的程度。以i(N)表示節(jié)點N的“不純度”，當節(jié)點上的樣本屬于同一類時，i(N) =0；當節(jié)點上的樣本類別齊全且數(shù)量相當，則i(N)很大。

決策樹的構(gòu)造是通過對樣本集的學習，自頂向下建立決策規(guī)則(見圖1)。樹中每個節(jié)點代表某些樣本的集合，每個分叉路徑代表某一特征及其閾值對節(jié)點進行分裂生長。在每個非葉節(jié)點上，遍歷所有特征參數(shù)，找到能使此節(jié)點的不純度下降最大的特征參數(shù)及其閾值以進行分裂。以此類推，直到葉節(jié)點處不純度為0止，此時每個葉節(jié)點中的樣本都屬于同一類別。

圖1 決策樹示意圖Fig.1 The scheme of decision tree

常用的決策樹算法有ID3，ID4，C4.5，C5.0，CART等，本研究選擇opencv函數(shù)庫中的CART樹算法。CART樹的不純度指標為Gini(基尼)不純度：

(1)

其中：i,j為類的編號；P(ωj)是節(jié)點N處屬于ωj類的樣本數(shù)占總樣本數(shù)的頻度。

在決策樹構(gòu)造過程中，如果樹分支停止太晚，決策樹的泛化性能將較差，被稱為“過擬合”。相反，如果樹分支停止太早，將導致分類性能較差，被稱為“欠擬合”。為解決“過擬合”問題，有交叉驗證、不純度下降差門限、節(jié)點樣本數(shù)門限以及剪枝等方法可供選擇[22-23，31，66]。本研究同時使用opencv函數(shù)庫中提供的交叉驗證和剪枝方法。

1.2 AdaBoost算法

AdaBoost是Adaptive Boosting(自適應增強)算法的縮寫，它是一種分類器的自適應增強算法。AdaBoost算法的基礎是1990年Schapire構(gòu)造的Boosting算法[40]，經(jīng)Freund和Schapire對Boosting算法的改進[41-42]，解決了原Boosting算法中需要依靠弱學習器先驗知識的限制，最終形成了AdaBoost算法。AdaBoost算法的基本思想是：針對同一個訓練樣本集，并選定某單分類器，例如決策樹，通過調(diào)整樣本權重，訓練一系列不同的分類器，進而組合成一個分類器系統(tǒng)。調(diào)整樣本權重的規(guī)則是提高分類錯誤樣本的權重，降低分類正確樣本的權重。其目的是訓練下一個分類器時，更加關注上一個分類器錯分的樣本。如此迭代訓練，構(gòu)建一系列單分類器，直到足夠小的分類錯誤率為止。AdaBoost算法目前已成為一族算法，具有多個變種，其中包括Discrete AdaBoost、Real AdaBoost、Logit Boost、Gentle AdBoost等。本研究表明，Gentle AdBoost算法對SAR溢油檢測效果是較好的。本研究使用opencv函數(shù)庫提供的Gentle AdaBoost算法。

Gentle AdaBoost的具體步驟如下：

第一步：定義權重分布空間。

Dm=(ωm,1，ωm,2,ωm,3，……ωm,i……,ωm,N)。

(2)

其中：m為迭代輪數(shù)，即單分類器的個數(shù)；i為訓練樣本編號，i=1,2,…N; 為m輪迭代時第i個樣本的權重。

第二步：初始化權重空間。因為有N個訓練樣本，因此每個訓練樣本的初始權重為1/N。首先訓練第一個單分類器，即迭代輪數(shù)為1，因此權重分布空間為：

(3)

第三步：進行多次迭代，訓練系列單分類器。

(1)使用具有權重分布的訓練樣本集訓練出第m個單分類器Gm(x)的回歸函數(shù)fm(x)，其中fm(x)值域為[-1,1]，|fm(x)|反映了樣本被分為某類的置信度，其符號為分類器輸出的類別，即Gm(x)=sign(fm(x))。

(2)更新權重分布空間，從Dm更新至Dm+1：

ωm+1,i=ωm,iexp(-yifm(xi))。

(4)

其中：是第m個分類器對某樣本xi的回歸函數(shù)值。yi是xi樣本的真實值。此公式表明，對于分類錯誤的樣本，其權重被增加，且被錯分樣本的置信度越高其權重被增加越多。

規(guī)一化以使樣本總權重為1，即：

(5)

第四步：組合各單分類器，形成一個強分類器系統(tǒng)，其回歸函數(shù)由M個單分類器的回歸函數(shù)之和求得。

(6)

其中，M是單分類器的系列總數(shù)。Gentle AdaBoost分類器系統(tǒng)的分類結(jié)果由下式描述：

(7)

1.3 Bagging算法

Bagging 算法的名稱源自bootstrap aggregation(自助聚集)，是一種組合系列同類型分類器構(gòu)成一個強分類器系統(tǒng)的自助聚集算法。其基本思想是從個數(shù)為N的訓練樣本集中隨機且有放回的抽取個數(shù)為n(n(N)的訓練樣本以形成一系列獨立的自助數(shù)據(jù)集[30]。每個獨立自助數(shù)據(jù)集訓練一個選定類型的的分類器，例如決策樹。這一系列獨立決策樹分類器的分類結(jié)果的平均值被取為Bagging決策樹分類器系統(tǒng)的最終分類結(jié)果。選定的分類器被稱為Bagging分類器系統(tǒng)中的分量分類器。

研究表明[44，50-51，54-58]，當自助數(shù)據(jù)集的樣本數(shù)n與訓練樣本集的樣本數(shù)N相等時，由于其隨機且有放回的樣本抽取方式，某些樣本可能被多次抽取，某些樣本可能從不被抽取，而每個自助數(shù)據(jù)集中無重復的有效樣本的概率為訓練樣本集總數(shù)N的63.2%，許多研究均采用這種抽取方式。另一些研究者使用了不同的抽取方式，包括按比例抽樣[59]、無放回抽樣[60-62，65]、交叉驗證抽樣[61-62]、先驗概率抽樣[63]、EBBag抽樣[64-65]、under-sampling和over-sampling抽樣[64]等。對于SAR圖像海面溢油自動識別系統(tǒng)，SAR觀測到的海面油膜和疑似油膜的樣本數(shù)是不平衡的，即油膜樣本往往遠少于疑似油膜樣本。我們希望保持各自助數(shù)據(jù)集中兩種樣本數(shù)比例為訓練樣本集中的原比例，因此本研究使用按比例，無放回抽樣。

Bagging算法的關鍵問題是訓練多少個分量分類器是最佳的。許多研究表明[48，50-53]，并非分量分類器越多，Bagging系統(tǒng)的性能越好。許多研究者通過測試實驗來確定Bagging系統(tǒng)中分量分類器的個數(shù)[29，44-49]。本研究表明，分量分類器過少， Bagging分類器系統(tǒng)的性能欠佳；分量分類器過多，會導致計算量過大而Bagging分類器系統(tǒng)的性能并無提高。

Bagging算法不僅是一個強分類器系統(tǒng)，同時亦是一個穩(wěn)定性系統(tǒng)[30]。這是因為Bagging分類器系統(tǒng)中的每個分量分類器都是使用不同的獨立自助數(shù)據(jù)集訓練而得，因而組合的Bagging分類器系統(tǒng)得以適應各種樣本特征空間分布情況,并對不連續(xù)處作了平均化處理[30-31]。

2 數(shù)據(jù)與特征參數(shù)

本文使用的1 448個SAR圖像海面暗目標樣本集源自65幅Envisat/ASAR精處理和寬刈幅圖像，其中包括10幅2011中國渤海蓬萊19-3油田溢油事故期間的數(shù)據(jù)。暗目標樣本由Zeng[33]等研發(fā)的自適應閾值分割算法和軟件提供。經(jīng)人工經(jīng)驗判讀，其中溢油樣本564個，疑似溢油樣本884個。

對每個暗目標樣本提取68個特征，其中包括14個幾何特征、15個灰度特征、39個紋理特征(包括24個灰度共生矩陣特征和15個灰度梯度共生矩陣特征)。表1給出68個特征名稱、分類和特征計算公式的參考文獻[34-39，43]。

3 實驗與結(jié)果

本研究建立了四個分類器和分類器系統(tǒng)，分別是決策樹(DT)、AdaBoost-決策樹(DT-A)、Bagging-決策樹(DT-B)和Bagging-AdaBoost-決策樹(DT-AB)，并通過實驗測試它們的檢測率、泛化性能和穩(wěn)定性能，以驗證DT-A、DT-B分類器系統(tǒng)對于DT單分類器在海面溢油自動識別上的增強效果，并證明本文提出的DT-AB分類器系統(tǒng)的優(yōu)良性能和應用前景。

下面，首先介紹檢測率、錯檢率和識別率的基本概念；其次通過測試實驗確定DT-B和DT-AB分類器系統(tǒng)中分量分類器的個數(shù)。最后分別測試DT，DT-A，DT-B和DT-AB的性能并作比較分析。

3.1 檢測率、錯檢率和識別率

檢測率，錯檢率和識別率是模式識別的3個重要指標。識別率是描述整個樣本集內(nèi)所有類別樣本正確分類的比值，檢測率是描述特定樣本正確分類的比值，而錯檢率是描述特定樣本被錯誤分類的比值。在本研究中，關心的是海面溢油樣本的正確識別以及海面疑似溢油的誤判，并不關心海面疑似溢油的正確識別。因此，高檢測率和低錯檢率是SAR海面溢油自動識別業(yè)務化系統(tǒng)所追求的。

表1 特征參數(shù)列表Table 1 Features list

檢測率、錯檢率和識別率的計算公式及相關符號說明為下：

人工判定類別溢油(Y=Yy+Yn)疑似溢油(N=Ny+Nn)分類器判定類別溢油(y=Yy+Ny)YyNy疑似溢油(n=Yn+Nn)YnNn

檢測率=Yy/(Yy+Yn);

錯檢率=Ny/(Yy+Ny);

識別率=(Yy+Nn)/(Yy+Ny+Yn+Nn);

其中，檢測率是分類器正確判別的溢油樣本數(shù)(Yy)與人工判別的溢油樣本數(shù)(Y)的比值；錯檢率是分類器將人工判別為疑似溢油樣本誤判為溢油樣本數(shù)(Ny)與分類器判別的溢油樣本數(shù)(y)的比值；識別率是分類器正確判別的樣本數(shù)(Yy+Nn)與測試樣本集總數(shù)的比值。

3.2 Bagging分類器系統(tǒng)中分量分類器個數(shù)的選擇

如前所述，在測試兩個Bagging分類器系統(tǒng)(DT-B和DT-AB)的檢測率、泛化性能和穩(wěn)定性能之前，需要通過測試實驗來確定分量分類器的個數(shù)。

測試實驗流程如圖2所示：

圖2 Bagging系統(tǒng)中分量分類器個數(shù)選擇實驗流程圖Fig.2 The flow chart of the experiment that was used to test how many numbers component classifiers should be select

首先在1 448個SAR海面暗目標樣本集中按溢油/疑似溢油樣本比例隨機抽取70%的樣本作為訓練樣本集，剩余樣本作為測試樣本集。然后從訓練樣本集中按同樣比例隨機抽取70%的樣本作為獨立的自助數(shù)據(jù)集，并訓練出一個決策樹(DT)分類器和以決策樹為內(nèi)核的AdaBoost(DT-A)分類器系統(tǒng)。這個過程循環(huán)1 000次，即用1 000個獨立的自助數(shù)據(jù)集分別訓練出1 000個DT和DT-AB。

從訓練好的1 000個分類器中隨機抽取M(M=1～300)個分類器組成Bagging系統(tǒng)，并對測試樣本集進行測試，得到相應的檢測率、錯檢率、識別率。將這個過程循環(huán)100次，得到 100個分量分類器為M的Bagging系統(tǒng)，同樣對測試樣本集進行測試，得到100個相應的檢測率，錯檢率，識別率。這100個獨立分類器系統(tǒng)相應的檢測率、錯檢率和識別率的均值和標準差即為分量分類器為M的Bagging分類器系統(tǒng)(DT-B、DT-AB)的分類結(jié)果。

圖3為DT-B在不同個數(shù)分量分類器下的檢測率及標準差。可以看出，當分量分類器個數(shù)M達到10時，分類器系統(tǒng)的檢測率均值達到最大。隨著M的增加，檢測率均值呈降低趨勢，標準差呈變小趨勢。當M=130時，標準差趨于穩(wěn)定，因此選擇DT-B分類器系統(tǒng)的分量分類器個數(shù)M=130。

圖4為DT-AB在不同個數(shù)分量分類器下的檢測率及標準差?？梢钥闯?，當分量分類器個數(shù)M到10時，分類器系統(tǒng)的檢測率均值達到最大。隨著M的增加，檢測率均值呈降低趨勢，當M=50時，DT-AB檢測率均值趨于穩(wěn)定，標準差均值仍呈變小趨勢。綜合考慮分類性能和計算效率兩方面，選擇DT-AB分類器系統(tǒng)的分量分類器個數(shù)M=150。

對比圖3和4，可以看到，DT-AB分類器系統(tǒng)在檢測率和標準差兩方面均優(yōu)于DT-B分類器系統(tǒng)。

圖3 DT-B在不同個數(shù)分量分類器下的檢測率及標準差(檢測率的標準差表示為豎線線段)Fig.3 The mean value and standard deviation of DT-B’s detection rate with different numbers of component classifiers(The standard deviations of detection rate are expressed as vertical bar lines)

圖4 DT-AB在不同個數(shù)分量分類器下的檢測率及標準差(檢測率的標準差表示為豎線線段)Fig.4 The mean value and standard deviation of DT-AB’s detection rate with different numbers of component classifiers(The standard deviations of detection rate are expressed as vertical bar lines)

3.3 泛化性能

泛化性能是描述分類器或分類器系統(tǒng)的普適性指標。常用的泛化性能測試方法有交叉驗證法和自抽樣法。本研究選擇自抽樣法(Booststrapping)對四種分類器或分類器系統(tǒng)(DT、DT-A、DT-B以及DT-AB)的泛化性能進行測試。自抽樣法每次從樣本集中抽取一部分樣本訓練分類器，而后對剩余樣本進行測試。這樣做N次，最后獲取檢測率、錯檢率和識別率的均值，作為泛化性能的衡量標準。

設計的實驗流程如圖5所示。

圖5 泛化能力測試實驗流程圖

首先從樣本集中按溢油/疑似溢油樣本比例隨機抽取70%的樣本作為訓練樣本集，剩余30%樣本作為測試樣本集。用訓練樣本集訓練出DT、DT-A、DT-B、DT-AB四種分類器或分類器系統(tǒng)。然后分別使用四種分類器或分類器系統(tǒng)對相應的測試集進行測試，得到各自的檢測率、錯檢率、識別率。重復以上步驟100次，得到四種分類器或分類器系統(tǒng)各100個檢測率、錯檢率、識別率，其中每次從樣本集中隨機抽取70%的樣本作為訓練樣本集的過程即為自抽樣法(Booststrapping)的概念。各100個檢測率、錯檢率、識別率的均值和標準差即為評價DT、DT-A、DT-B和DT-AB泛化性能的指標。

實驗結(jié)果如表2所示?？梢钥闯?，DT-A和DT-B的檢測率、錯檢率和識別率均優(yōu)于DT，這說明AdaBoost算法(DT-A)與Bagging算法(DT-B)確實提高了決策樹單分類器的檢測率和泛化性能，DT-A略優(yōu)于DT-B。尤其，以DT-A分類器系統(tǒng)為分量分類器的Bagging系統(tǒng)DT-AB的檢測率和識別率最高而錯檢率最低，說明其泛化性能最佳。

3.4 穩(wěn)定性能

Breiman提出[30]，如果一個分類器因訓練集樣本的較小改變而導致分類器性能的顯著改變，則這種分類器被認為是“不穩(wěn)定”(Unstable)的。

Bagging算法對分類器穩(wěn)定性能的提高需通過實驗進行測試。測試過程需滿足訓練集樣本的較小改變這一條件。需要獲得一系列由略有差別的訓練集訓練出的某種分類器或分類器系統(tǒng)，進而得到它們對相同測試集的檢測率、錯檢率和識別率的均值、標準差。以標準差作為穩(wěn)定性的評價指標，標準差越小，表明穩(wěn)定性能越好。

表2 泛化能力測試實驗結(jié)果Table 2 The test result of generalization performance

Note：①Detection rate；②False discovery rate；③Recognition rate；④Average；⑤Standard deviation

設計的實驗流程如圖6所示。

首先從訓練樣本集中按溢油/疑似溢油樣本比例隨機抽取80%的樣本組成微調(diào)訓練集，并訓練出DT、DT-A、DT-B(130個分量分類器)和DT-AB(150個分量分類器)四種分類器或分類器系統(tǒng)。然后分別使用DT、DT-A、DT-B和DT-AB對測試樣本集進行測試，得到各自的檢測率、錯檢率、識別率。重復以上步驟100次，得到四種分類器各100個檢測率、錯檢率、識別率。最后，計算各100個檢測率、錯檢率、識別率的均值和標準差，以標準差作為分類器穩(wěn)定性能的指標。

實驗結(jié)果如表3所示?？梢钥闯?，DT-A和DT-B的檢測率、錯檢率和識別率的標準差均低于DT，這說明Bagging算法和AdaBoost算法不僅提高了決策樹單分類器的檢測率和泛化性能，同時提高了穩(wěn)定性能，DT-B的標準差略低于DT-A的標準差。尤其，DT-AB分類器系統(tǒng)的標準差最小，說明DT-AB分類器系統(tǒng)不僅泛化性能最佳，其穩(wěn)定性能亦最佳。

圖6 穩(wěn)定性能測試實驗流程圖Fig.6 The flow chart of the experiment that was used to test stability performance

DTDT-A檢測率①錯檢率②識別率③檢測率①錯檢率②識別率③均值④0.728 0.269 0.789 0.820 0.168 0.865 標準差⑤0.039 0.030 0.020 0.016 0.015 0.009 DT-B(130)DT-AB(150) 檢測率①錯檢率②識別率③檢測率①錯檢率②識別率③均值④0.810 0.184 0.855 0.826 0.161 0.870 標準差⑤0.014 0.014 0.008 0.011 0.011 0.007

Note：①Detection rate；②False discovery rate；③Recognition rate；④Average；⑤Standard deviation

4 結(jié)論與討論

近年一些重大的海上溢油事故引起廣泛重視，從而利用衛(wèi)星SAR圖像自動監(jiān)測海面溢油成為SAR數(shù)據(jù)海洋應用的熱點之一。

目前應用于SAR海面溢油檢測的分類器大多為單分類器，其檢測率往往難以達到要求。本研究引入AdaBoost算法和Bagging算法，采用決策樹(DT)單分類器為其內(nèi)核，形成兩種分類器系統(tǒng)DT-A和DT-B。進而提出以DT-A為內(nèi)核的Bagging分類器系統(tǒng)DT-AB。對1 448個Envisat/ASAR(C-Band)海面溢油和疑似溢油樣本集進行分類實驗。結(jié)果表明：(1)AdaBoost算法和Bagging算法可以明顯增強單分類器的分類性能、泛化性能和穩(wěn)定性能。(2)本研究首次提出的DT-AB分類器系統(tǒng)的分類性能、泛化性能和穩(wěn)定性能優(yōu)于DT-A和DT-B。因此，DT-AB分類器系統(tǒng)用于衛(wèi)星SAR海面溢油自動識別業(yè)務化應用方面具有前景。

本研究對不同時空覆蓋的Envisat/ASAR(C-Band)樣本集以及不同衛(wèi)星不同波段的COSMO-SkyMed SAR(X-Band)樣本集進行了同樣的實驗，結(jié)果與上述一致。

需要說明的是，上述用于實驗的樣本集中，海面溢油樣本數(shù)與疑似溢油樣本數(shù)的比例在1∶5左右。而實際應用中，一幅SAR圖像中的海面溢油樣本數(shù)與疑似溢油樣本數(shù)的比例往往達到1∶100甚至更大。這種樣本不平衡問題是模式識別中的難點之一。在項目研究方案中采用一個新的自適應閾值分割算法先行解決嚴重的不平衡問題。

今后，將針對樣本集深入研究海面溢油和疑似溢油的特征參數(shù)。

致謝：感謝中海油項目“海上溢油衛(wèi)星自動識別和預警業(yè)務化系統(tǒng)研發(fā)”對本研究的資助以及項目課題組師生對本研究的有益討論和幫助。感謝ESA-MOST Dargon3 ID10580 Project提供Envisat/ASAR衛(wèi)星圖像。