基于序貫決策融合的變化檢測方法研究

李 雪，舒 寧，劉小利

(1.中國地震局地震研究所 地震大地測量重點實驗室，武漢 430071;2.武漢大學(xué)遙感信息工程學(xué)院，武漢 430079)

序貫分析(Sequential Analysis)是數(shù)理統(tǒng)計學(xué)的一個分支，由著名統(tǒng)計學(xué)家A WALD于1947年提出。序貫分析的研究對象就是所謂“序貫抽樣方案”，即如何用這種抽樣方案得到的樣本去作統(tǒng)計推斷。序貫抽樣方案是指在抽樣時，不事先規(guī)定總的抽樣個數(shù)(觀測或?qū)嶒灤螖?shù))，而是先抽少量樣本，根據(jù)其結(jié)果，再決定停止抽樣或繼續(xù)抽樣、抽多少，這樣下去，直至決定停止抽樣為止。序貫分析方法的提出是數(shù)理統(tǒng)計學(xué)中的一大成就，該方法在眾多領(lǐng)域得到了廣泛的應(yīng)用［1－3］。

本文在基于決策樹分類的面向?qū)ο笞兓瘷z測方法中引入了序貫分析概念，提出一種基于序貫決策融合的變化檢測方法，為提高遙感影像變化檢測結(jié)果的準(zhǔn)確性提供了一條技術(shù)途徑。

1 決策樹變化檢測

1.1 決策樹分類器

決策樹(Decision Tree)是一種機器學(xué)習(xí)方法，通過對訓(xùn)練樣本進(jìn)行歸納學(xué)習(xí)獲得一組分類規(guī)則。決策樹一般是由根節(jié)點、中間節(jié)點和葉節(jié)點組成的一幅有向無環(huán)圖。與基于向量間距離度量的模式識別方法不同，決策樹是一種非度量模式識別方法。由于只對屬性d元組(d為有限元)的取值狀況進(jìn)行統(tǒng)計分析，不計算屬性向量的距離或相似性，因此決策樹可以用于處理任何離散數(shù)據(jù)，甚至非數(shù)字類數(shù)據(jù)(例如語義數(shù)據(jù)等)［4］。

決策樹分類的基本算法主要包括以下5個步驟。

(1)生成訓(xùn)練樣本數(shù)據(jù)集:所有的訓(xùn)練樣本例子滿足形式(X，L)={x1，x2，…，xn，li}，其中X代表參與分類的n維特征屬性向量，L={l1，l2，…，lK}代表K個樣本類別，li表示K個類別中的第i種類別。

(2)分支:在節(jié)點t，對單一問題(屬性)進(jìn)行“是”、“否”劃分，生成 tY，tN2個子節(jié)點。設(shè) I(t)，I(tY)，I(tN)分別表示節(jié)點t與tY，tN的不純度，則劃分準(zhǔn)則為使分支后不純度減小量ΔI(t)最大，計算公式如式為

式中:Nt表示節(jié)點t處待分樣本數(shù)量;NtY和NtN分別表示在節(jié)點t處被劃分為“是”和“否”的樣本數(shù)量;不純度函數(shù)I(t)常用信息熵表示，即

式中:Pt(li)表示節(jié)點t處類別為li的樣本數(shù)量占節(jié)點t處所有樣本數(shù)量的比例，節(jié)點t處樣本類別越一致則I(t)越小。

(3)停止分支:對節(jié)點停止分支并將其表明為“樹葉”。停止分支的準(zhǔn)則一般有2種:一是采用閾值法，如果ΔI(t)小于閾值T則停止分支;二是節(jié)點處的樣本數(shù)量足夠小或樣本類別足夠純凈(屬于同一類)則停止分支。

(4)剪枝:有時，分支會因算法缺少足夠的前瞻性而過早停止，這稱為“視界局限效應(yīng)”。在剪枝過程中，對充分生長的樹比較其所有相鄰的成對葉節(jié)點。如果消去它們能引起令人滿意(很小的)的不純度增長，則消去葉節(jié)點，并令它們的父節(jié)點成為新的葉節(jié)點［5］。

(5)類別分配:采用多數(shù)規(guī)則，將葉子t標(biāo)記為Xt中占多數(shù)的類別ωj。

決策樹在數(shù)據(jù)挖掘、機器學(xué)習(xí)等領(lǐng)域具有廣泛的應(yīng)用。經(jīng)典的決策樹分類算法有ID3和C4.5/C5.0。ID3算法最早由Quinlan提出，稱為交互式二分法程序第3版(Interactive Dichotomizer－3)，其設(shè)計意圖只是針對語義數(shù)據(jù)進(jìn)行處理［6］。C4.5/C5.0算法是ID3算法的改進(jìn)版，也是目前最流行的分類樹方法。C4.5/C5.0算法不僅增加了剪枝算法而且還加強了對連續(xù)屬性的處理能力，通過對連續(xù)數(shù)據(jù)的離散化處理，實現(xiàn)了對連續(xù)屬性的決策樹分類［7］。

1.2 決策樹變化檢測

基于決策樹分類器的變化檢測屬于分類后變化檢測方法，本文以像斑作為影像處理的基本單元，通過遙感影像與矢量輔助數(shù)據(jù)進(jìn)行數(shù)據(jù)套合提取地物像斑。矢量輔助數(shù)據(jù)可以是基準(zhǔn)期的土地利用數(shù)據(jù)或其他專題類數(shù)據(jù)。將矢量輔助數(shù)據(jù)分別與基準(zhǔn)期和檢測期的遙感影像套合，獲取的地物像斑具有相同的空間屬性(位置相同、形狀相同)和不同的影像特征屬性(光譜特征不同、紋理特征不同)。通過特征提取，提取不同時相遙感影像像斑的光譜特征(不同波段像斑的均值和方差)和紋理特征(不同波段像斑灰度共生矩陣的二階矩、慣性矩和熵)，建立像斑特征數(shù)據(jù)庫。由于矢量輔助數(shù)據(jù)帶有基準(zhǔn)期像斑的類別信息，通過逐類人工選擇的方式可以獲取少量檢測期類別未發(fā)生變化地物像斑作為樣本像斑。將樣本像斑的特征數(shù)據(jù)帶入決策樹算法進(jìn)行訓(xùn)練，再利用訓(xùn)練后的決策樹分類器對非樣本像斑特征進(jìn)行分類判別，即可獲得檢測期像斑的地物類別。最后，將像斑的基準(zhǔn)期類別和檢測期類別進(jìn)行對比，即可找出發(fā)生變化的像斑對象。

本文基于決策樹算法的變化檢測流程如圖1。

2 序貫決策融合變化檢測

決策樹分類器由于具備非度量模式識別的特性，適合對非數(shù)值型離散數(shù)據(jù)進(jìn)行處理。由于決策樹C5.0算法加強了對連續(xù)型數(shù)據(jù)的處理能力，使其可同時處理具有連續(xù)和離散2種屬性的數(shù)據(jù)。然而基于決策樹分類的變化檢測方法采用的是一次性分類原則，這種方法容易受到初始樣本和分類誤差的影響。因此本文提出一種序貫決策融合方法對決策樹變化檢測方法進(jìn)行了改進(jìn)。

圖1 決策樹變化檢測流程Fig.1 Change detection process by decision tree

2.1 序貫決策融合

本文根據(jù)序貫分析的思想提出一種序貫決策融合方法(Sequential Decision Fusion)。該方法是一種針對單分類器的決策融合方法，其核心思想是對同一樣本反復(fù)進(jìn)行分類判別，每次判別時都將前一次分類結(jié)果作為下一次的輸入變量與原特征向量一起組成新的特征向量輸入分類器［8－9］。

圖2 分類序列Fig.2 Classification sequence

設(shè)x代表樣本特征向量，f(x)代表分類器，y為樣本所屬的類別，則對樣本x多次分類判別后產(chǎn)生的類別序列如圖2所示。

圖2中:yi表示第i次分類判別時獲得的類別;xi表示第i次分類判別時的輸入變量對x多次分類得到的類別序列，類別序列的計算可以由后驗概率表示，即

序貫決策融合的具體算法如下。

(1)分類器融合訓(xùn)練:

①設(shè)訓(xùn)練樣本集為S={(xi，yi)}，則對于訓(xùn)練樣本的預(yù)測集合可以表示為

式中:f(·)表示一種分類器算法;^yi表示樣本xi的預(yù)測類別。

③返回函數(shù)f=f(S)，f'=f(S')。

(2)分類器決策分類:

①對于待分類數(shù)據(jù)x，求其預(yù)測值^y=f(x)。

②生成擴(kuò)展數(shù)據(jù)x'。

③返回決策融合類別y=f'(x')。

函數(shù)f'為對函數(shù)f的輸入變量維度進(jìn)行擴(kuò)展后的分類函數(shù)。序貫決策融合算法中的參數(shù)W決定了參與決策融合的歷史決策層數(shù)，當(dāng)W取值為1時的序貫決策融合又可被視為一馬爾科夫過程，其算法結(jié)構(gòu)如圖3所示。由于序貫決策融合是將分類器預(yù)測類別作為新的特征輸入的迭代算法，因此所選擇的分類器必須能處理輸入的數(shù)值變量(特征向量)和符號變量(類別符號)。由于決策樹C5.0算法在原有善于處理離散數(shù)據(jù)這一特性的基礎(chǔ)上，增強了對連續(xù)型數(shù)據(jù)的處理能力，因此本文采用決策樹分類器作為序貫決策融合的基本分類算法。

圖3 序貫決策融合分類算法結(jié)構(gòu)(W=1)Fig.3 The structure of classification algorithm by sequential decision fusion(W=1)

2.2 序貫決策融合變化檢測

采用序貫決策融合算法代替1.2節(jié)決策樹變化檢測方法中的決策樹訓(xùn)練，即可獲得本文的序貫決策融合變化檢測方法。序貫決策融合訓(xùn)練流程如圖4所示。首先，將訓(xùn)練樣本(特征向量形式為{影像特征，樣本類別}，其中影像特征包括像斑的光譜特征和紋理特征)帶入決策樹進(jìn)行初始訓(xùn)練，獲得樣本的預(yù)測類別，再對原輸入特征數(shù)據(jù)集進(jìn)行擴(kuò)展，獲得形如{影像特征，預(yù)測類別，樣本類別}的擴(kuò)展訓(xùn)練樣本特征向量。然后，將擴(kuò)展訓(xùn)練樣本帶入決策樹訓(xùn)練，生成擴(kuò)展決策樹，并獲得樣本的預(yù)測類別。將樣本新的預(yù)測類別與原預(yù)測類別進(jìn)行對比，如完全一致，則表示決策樹訓(xùn)練輸出穩(wěn)定，算法終止;如不一致，則將新的預(yù)測結(jié)果帶回對上一次輸入特征擴(kuò)展步驟，生成新的擴(kuò)展訓(xùn)練樣本，其特征向量形式為{影像特征，原預(yù)測類別，新預(yù)測類別，樣本類別}并再次對決策樹進(jìn)行訓(xùn)練。經(jīng)過反復(fù)迭代訓(xùn)練，直至決策樹輸出穩(wěn)定則訓(xùn)練終止。

由于本文序貫決策融合算法中的序貫歷史參數(shù)W取值為1，因此，對決策樹訓(xùn)練的輸入特征數(shù)據(jù)集只擴(kuò)展至“原預(yù)測類別”，每次迭代訓(xùn)練中產(chǎn)生的新的樣本類別預(yù)測結(jié)果將取代上一次輸入特征向量中的“原預(yù)測類別”，生成新的特征向量并參與擴(kuò)展決策樹的訓(xùn)練。

當(dāng)訓(xùn)練終止后，由初始訓(xùn)練獲得的決策樹和其后歷次迭代訓(xùn)練獲得的擴(kuò)展決策樹構(gòu)成的決策樹序列稱為序貫決策樹。將非樣本像斑的檢測期特征代入序貫決策樹，依序列進(jìn)行序貫決策分類，獲得的最終類別為經(jīng)過序貫決策融合的像斑類別。將像斑的檢測期類別與基準(zhǔn)期類別進(jìn)行對比即可找出發(fā)生變化的像斑對象。

圖4 序貫決策融合訓(xùn)練流程Fig.4 Training process of sequential decision fusion

3 實驗與結(jié)果

3.1 實驗數(shù)據(jù)

本文實驗采用的遙感影像數(shù)據(jù)為武漢市某區(qū)域2002年和2005年獲取的Quickbird多光譜影像，包含藍(lán)、綠、紅和近紅外4個波段，分辨率為2.4m(圖5(a)為2002年遙感影像，圖5(b)為2005年遙感影像)。矢量輔助數(shù)據(jù)為同一區(qū)域的土地利用矢量數(shù)據(jù)(如圖5(c)所示)，成圖時間為2002年，圖中包含22種基本土地利用類型，共計572個矢量對象。

3.2 實驗結(jié)果

圖5 實驗數(shù)據(jù)Fig.5 Experimental data

經(jīng)過數(shù)據(jù)套合、特征提取、樣本選擇后，獲得84個樣本像斑和488個待檢測像斑，根據(jù)樣本對檢測期像斑類別進(jìn)行判別。序貫決策融合初始時，先將84個樣本像斑的特征輸入決策樹分類器進(jìn)行訓(xùn)練，獲得初始判別決策樹，再經(jīng)過反復(fù)擴(kuò)展、迭代訓(xùn)練獲得序貫決策樹。將488個待檢測像斑特征代入序貫決策樹進(jìn)行類別判別，找出變化像斑。圖6所示為變化檢測結(jié)果，其中:圖6(a)為標(biāo)準(zhǔn)變化結(jié)果，該結(jié)果為人工解譯判斷的變化地物像斑的結(jié)果;圖6(b)為采用決策樹判別(C5.0算法)的變化檢測結(jié)果;圖6(c)為采用序貫決策融合的變化檢測結(jié)果(其中W=1)。

圖6 變化檢測結(jié)果Fig.6 Results of change detection

分別將決策樹變化檢測和序貫決策融合變化檢測結(jié)果與標(biāo)準(zhǔn)變化結(jié)果進(jìn)行對比，2種方法的漏檢率、誤檢率、總體精度和kappa系數(shù)(一種計算分類精度的方法)如表1所示。由于序貫融合方法是利用過去的預(yù)判值對分類結(jié)果進(jìn)行修正，因此與未經(jīng)迭代的原分類器算法獲得的變化檢測結(jié)果相比，各項精度都有所提高。序貫融合的迭代一般都會快速收斂，圖7給出了迭代次數(shù)與發(fā)生變化的像斑數(shù)量之間的關(guān)系。由圖7可知，本文序貫決策融合在第4次迭代時，變化像斑數(shù)量已經(jīng)穩(wěn)定。影響收斂迭代次數(shù)的主要因素為參與訓(xùn)練的樣本數(shù)量及樣本特征的數(shù)量。

圖7 序貫決策融合迭代統(tǒng)計Fig.7 Statistics of iterative process by sequential decision fusion

表1 變化檢測結(jié)果精度評定Table 1 Accuracy assessment for change detection results

4 結(jié)論

本文根據(jù)序貫分析方法提出了一種序貫決策融合的變化檢測方法。該方法利用決策樹算法可同時處理連續(xù)型和離散型數(shù)據(jù)的特點，通過將前一次決策樹判決結(jié)果與原輸入數(shù)據(jù)組合成新的輸入特征向量并代入決策樹重新訓(xùn)練，進(jìn)行反復(fù)迭代，直至算法獲得穩(wěn)定的輸出。經(jīng)過實驗對比，發(fā)現(xiàn)采用序貫決策融合的變化檢測結(jié)果各項精度評定指標(biāo)均好于決策樹判別的變化檢測結(jié)果。

實驗結(jié)果證明了本文方法的有效性，為提高遙感影像變化檢測結(jié)果的準(zhǔn)確性提供了一條新的技術(shù)途徑。

［1］崔 穎，郭 偉，王 蕾，等.序貫分析方法在不同分析方法一致性檢驗中的應(yīng)用［J］.吉林大學(xué)學(xué)報(醫(yī)學(xué)版)，2007，33(1):173－175.(CUI Ying，GUO Wei，WANGLei，etal.Application of Sequential Analysis Methods in Consistency Test［J］.Journal of Jilin University(Medicine Edition)，2007，33(1):173－175.(in Chinese))

［2］李 騫，馮金富，彭志專，等.基于IEK-PF的多傳感器序貫融合跟蹤［J］.系統(tǒng)仿真學(xué)報，2009，21(9):2531－2534.(LI Qian，F(xiàn)ENG Jin-fu，PENG Zhi-zhuan，etal.Multi-sensors Sequential Fusion Tracking Based on Iterated Extend Kalman Particle Filter［J］.Journal of System Simulation，2009，21(9):2531－2534.(in Chinese))

［3］李 軍，李敏勇，常玉國.基于模式識別和序貫分析的綜合態(tài)勢感知模型研究［J］.艦船電子工程，2010，30(1):60－62.(LI Jun，LI Min-yong，CHANG Yuguo.Research on Situation Awareness Model Based on Pattern Recognition and Sequential Recognition［J］.Ship Electronic Engineering，2010，30(1):60－62.(in Chinese))

［4］THEODORIDISS，KOUTROUMBASK.模式識別［M］.李晶皎，朱志良，王愛俠，等譯.北京:電子工業(yè)出版社，2004.(THEODORIDIS S，KOUTROUMBAS K.Pattern Recognition［M］.Translated by LI Jing-jiao，ZHU Zhi-liang，WANG Ai-xia，etal.Beijing:Publishing House of Electronics Industry，2004.(in Chinese))

［5］DUDA R O，HART P E，STORK D G.模式分類［M］.李宏東，姚天翔，譯.北京:機械工業(yè)出版社，2004.(DUDA R O，HARTPE，STORK D G.Pattern Classification［M］.Translated by LI Hong-dong，YAO Tianxiang.Beijing:China Machinery Press，2004.(in Chinese))

［6］MITCHELL T M，Machine Learning［M］.New York:McGraw-Hill，1997.

［7］QUINLAN J R.C4.5:Programs for Machine Learning［M］.San Francisco:Morgan Kaufmann，1993.

［8］COHEN W W，ROCHA de CARVALHO V.Stacked Se-quential Learning［C］∥University of Aberdeen，Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence(IJCAI)，Edinburgh，Scotland，UK，30 July-5 August，2005，Denver:Professional Book Center，2005:671－676.

［9］宋曉寧，吳小俊.基于決策樹的模糊序貫最小優(yōu)化分類器的人臉識別［J］.江蘇科技大學(xué)學(xué)報(自然科學(xué)版)，2006，20(3):41－44.(SONG Xiao-ning，WU Xiao-jun.Face Recognition Based on Fuzzy Sequential Minimal Optimization and Decision Tree［J］.Journal of Jiangsu University of Science and Technology(Natural Science Edition)，2006，20(3):41－44.(in Chinese))