陳麗萍　黃森旺

摘要：介紹了決策樹C4.5算法，并利用該算法實現(xiàn)了對遙感數(shù)據(jù)規(guī)則的挖掘，在此基礎(chǔ)上設計并實現(xiàn)了針對于C4.5規(guī)則的編輯器，通過該編輯器能夠?qū)崿F(xiàn)對規(guī)則的編輯與管理。規(guī)則編輯器的設計與實現(xiàn)，為在分類過程中人工的干預提供了可能。將人工干預與基于數(shù)學理論規(guī)則的自動提取相結(jié)合，尤其是在地形較復雜的地區(qū)，將有利于分類精度的提高。利用黃山市LandSat TM影像，進行了基于C4.5算法自動提取規(guī)則的遙感影像分類實驗。實驗結(jié)果表明，利用C4.5算法提取的分類規(guī)則準確率高，利用提取的分類規(guī)則進行的遙感影像分類效果較好。

關(guān)鍵詞：遙感； C4.5算法；規(guī)則；分類

中圖分類號：TP75文獻標志碼：A文章編號：1672-1098（2014）04-0046-05

遙感圖像包含了大量豐富的信息資源，它是探測地物目標最豐富、最直觀的信息載體[1-2]。隨著遙感技術(shù)的發(fā)展，遙感信息在國民經(jīng)濟及科學研究中的作用越來越受到各個行業(yè)的重視。而利用遙感圖像獲得遙感信息的一個重要的中間環(huán)節(jié)就是遙感圖像分類。遙感圖像分類是指按照一定的規(guī)則或算法，根據(jù)光譜亮度、空間結(jié)構(gòu)等特征將象元劃分為不同的類別[3]。遙感圖像分類是專題制圖的基礎(chǔ)也是遙感應用研究的基礎(chǔ)，在遙感影像的處理過程中處于重要的地位。它的精度直接影響到生產(chǎn)遙感影像各種產(chǎn)品的質(zhì)量。而在進行分類的過程中，遙感圖像處理的各個環(huán)節(jié)中，分類規(guī)則的建立至關(guān)重要。分類質(zhì)量好壞的關(guān)鍵在于是否有高質(zhì)量的分類規(guī)則。好的分類規(guī)則，能提高分類精度，反之建立的分類規(guī)則不合理，將會影響分類的精度[4-6]。

基于以上原因，本文主要是針對在分類過程中建立分類規(guī)則的方法進行研究。通過利用研究區(qū)影像提取的分類規(guī)則，對其進行分類，通過分類精度來對提取的分類規(guī)則的準確度進行評價。并設計出規(guī)則編輯器，通過該編輯器能夠?qū)崿F(xiàn)對規(guī)則的編輯，以達到人工干預的目的。將分析者的分類經(jīng)驗與基于規(guī)則的自動提取相結(jié)合，進而達到提高規(guī)則準確率，提高分類精度的目的。

1分類規(guī)則的提取方法

基于規(guī)則的遙感影像分類方法主要包括：訓練樣本的選擇、分類規(guī)則的建立、影像分類。其中最關(guān)鍵的是分類規(guī)則的提取。分類規(guī)則制定的準確程度嚴重影響到后續(xù)分類的精度。規(guī)則的定義是將知識用數(shù)學語言表達的過程，可以通過經(jīng)驗總結(jié)獲得，但這對分析者的分類經(jīng)驗及地學知識有較高的要求；也可以通過一定的算法獲取。通過算法提取的分類規(guī)則，具有一定的數(shù)學理論基礎(chǔ)，相較于經(jīng)驗獲取的規(guī)則，具有一定的嚴謹性。但是在地形較復雜的地區(qū)，如若將基于數(shù)學基礎(chǔ)自動建立的規(guī)則與人為經(jīng)驗相結(jié)合，制定的規(guī)則將更具有準確性。本文將基于決策樹C4.5算法開發(fā)規(guī)則編輯器，實現(xiàn)了規(guī)則提取過程中人工干預與自動提取的結(jié)合。

1.1C4.5算法

C4.5（classification 4.5）算法[7-16]是Quinlan在1993年提出的，它是模式識別中十分經(jīng)典的算法。它是在ID3算法的基礎(chǔ)上發(fā)展而來的。C4.5算法對ID3算法進行了改進，之后它成為了諸多算法的基礎(chǔ)。C4.5算法在單機應用中，不僅分類準確率高而且速度快。

在C4.5算法中，它的分裂指標采用的是信息增益率（information gain ratio）而非ID3算法中采用的信息增益。用信息增益率作為分裂指標，克服了用信息增益來選擇屬性時偏向選擇值多的屬性的不足。在ID3算法的基礎(chǔ)上，C4.5算法不僅增加了了對連續(xù)型屬性和屬性值空缺情況的處理，對樹剪枝也有了較成熟的方法。

1） 用信息增益率來選擇屬性。生成決策樹過程中的關(guān)鍵是確定分裂指標。C4.5算法中分裂指標確定的基本思想是比較各訓練樣本數(shù)據(jù)中屬性信息增益率的大小，取其中信息增益率最大的但又不低于所有屬性平均值的屬性作為的一個分支節(jié)點，然后再將每一個可能的取值作為這個節(jié)點的一個分支，遞歸地形成決策樹。

在C4.5算法中作為屬性分裂指標的信息增益率定義為

GainRatio（S，A）=Gain（S，A）SplitInformation（S，A）

式中：Gain（S，A）與ID3算法中的信息增益相同，而分裂信息SplitInformation（S，A）代表了按照屬性A分裂樣本集S的廣度和均勻性。

SplitInformation（S，A）=-∑ci=1|Si||S|log2|Si||S|

式中：S1到Sc是c個不同值的屬性A分割S而形成的c個樣本子集。

2） 可以處理連續(xù)數(shù)值型屬性。若存在連續(xù)的描述性屬性，首先必須將該連續(xù)性屬性分割為離散的區(qū)間集合，對其進行離散化處理。

C4.5既可以處理離散型屬性，也可以處理連續(xù)性屬性。在選擇某節(jié)點上的分枝屬性時，對于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個數(shù)進行計算；對于某個連續(xù)性屬性Ac，假設在某個結(jié)點上的數(shù)據(jù)集的樣本數(shù)量為total，C4.5將作以下處理：

a） 將該結(jié)點上的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體數(shù)值，由小到大進行排序，得到屬性值的取值序列{A1c，A2c，……Atotal}。

b） 在取值序列中生成total-1個分割點。第i（0

c） 從total-1個分割點中選擇最佳分割點。對于每一個分割點劃分數(shù)據(jù)集的方式，C4.5計算它的信息增益比，并且從中選擇信息增益比最大的分割點來劃分數(shù)據(jù)集。

3） 采用了一種后剪枝方法。為了避免樹的高度無節(jié)制的增長，避免過度擬合數(shù)據(jù)，C4.5采用了一種后剪枝方法。該方法使用訓練樣本集本身來估計剪枝前后的誤差，從而決定是否真正剪枝。方法中使用的公式如下

pr[f-qq（1-q）/N>Z]=C（3）

其中：N是實例的數(shù)量； f=E/N為觀察到的誤差率（其中E為N個實例中分類錯誤的個數(shù)）；q為真實的誤差率；c為置信度；z為對應于置信度c的標準差，其值可根據(jù)c的設定值通過查正態(tài)分布表得到。

通過該公式即可計算出真實誤差率q的一個置信度上限，用此上限為該節(jié)點誤差率e做一個悲觀的估計

e=f+z22N+ZfN-f2N+z24N21+z2N（4）

通過判斷剪枝前后e的大小，從而決定是否需要剪枝。

4） 對于缺失值的處理。在某些情況下，樣本中可供使用的數(shù)據(jù)可能缺少某些屬性的值。處理缺少屬性值的一種策略是賦給它結(jié)點n所對應的訓練實例中該屬性的最常見值；另外一種更復雜的策略是為A的每個可能值賦予一個概率，通過它分配到某個類別的概率值來進行類別的分配。例如，實例S，給定一個布爾屬性A，如果結(jié)點n包含6個已知A=1和4個A=0的實例，那么A（x）=1的概率是0.6，而A（x）=0的概率是0.4。于是，實例S的60%被分配到A=1的分支，40%被分配到另一個分支。這些片斷樣例的目的是計算信息增益，另外，如果有第二個缺少值的屬性必須被測試，這些樣例可以在后繼的樹分支中被進一步細分。C4.5就是使用這種方法處理缺少的屬性值。

1.2規(guī)則編輯器的設計與實現(xiàn)

在基于規(guī)則的遙感影像分類方法中，對規(guī)則的組織與管理十分重要。本文依據(jù)決策樹C4.5算法，以VS2008和C#為開發(fā)環(huán)境，設計并實現(xiàn)規(guī)則管理系統(tǒng)，規(guī)則編輯器中的規(guī)則是以樹結(jié)構(gòu)的形式來表示的，在分類規(guī)則建立的過程中，為人工干預提供了方式和途徑。

1） 系統(tǒng)設計。規(guī)則管理系統(tǒng)主要包括對規(guī)則的一些常規(guī)管理操作（打開、新建、撤銷、重做、保存）和對規(guī)則的編輯操作（添加分支節(jié)點、添加葉子節(jié)點、對分支進行編輯）兩大部分。

2） 系統(tǒng)模塊介紹。規(guī)則編輯器系統(tǒng)界面如圖1所示。通過該系統(tǒng)，可以實現(xiàn)對規(guī)則的各種操作與管理?？梢灾匦陆⑴c制定新的規(guī)則集，也可以對規(guī)則集進行修改。利用此編輯器可以對利用C4.5算法提取的規(guī)則進行人工干預，以求得到最優(yōu)的分類質(zhì)量。

3） 系統(tǒng)功能介紹。①常規(guī)編輯管理，主要包括對規(guī)則集的一些最基本的操作，包括新建、打開、撤銷、重做、刪除、保存等操作。通過這些操作，可以實現(xiàn)對規(guī)則的管理；②規(guī)則編輯功能，主要包括添加分支節(jié)點、添加葉子節(jié)點、編輯等操作。通過這幾個功能可實現(xiàn)對規(guī)則的修改等操作，進而實現(xiàn)人工干預。規(guī)則編輯功能界面如圖2所示。

圖1規(guī)則管理系統(tǒng)界面圖2規(guī)則編輯操作界面

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

為了驗證C4.5算法提取的規(guī)則的準確度，本文利用其對遙感影像提取的規(guī)則進行了分類實驗。采用黃山市LandSat TM影像作為數(shù)據(jù)源，影像獲取日期為2009年11月4日，該影像共7個波段（B1、B2、B3、B4、B5、B6、B7），其中B6波段空間分辨率為120 m，其余波段空間分辨率為30 m。并對影像進行了幾何校正，誤差在一個像元以內(nèi)。然后利用感興趣區(qū)域?qū)τ跋襁M行裁剪，獲得試驗區(qū)影像，圖4（左）為試驗區(qū)第4、3、2波段的RGB彩色合成影像。

圖3分類規(guī)則

3實驗結(jié)果與分析

3.1訓練樣本的選擇

C4.5算法對訓練樣本的質(zhì)量要求很高，只有應用高質(zhì)量的訓練樣本進行訓練才能得出可信度很高的分類規(guī)則。本試驗是在ENVI中調(diào)入試驗區(qū)LandSat TM影像（見圖4（左）），同時參考研究區(qū)的SPOT影像，人機交互的選擇訓練樣本。對于截取的試驗區(qū)按照森林（Class 1），裸地（Class2），水體（Class 3），其它水面（Class 4），其它用地（Class 5）劃分為5個地物類別，共選取813個訓練樣本。

3.2規(guī)則的提取

在利用C4.5算法對遙感影像進行歸納學習之前，首先要確定學習的測試變量和目標變量。用試驗區(qū)TM影像的7個波段的灰度值（B1、B2、B3、B4、B5、B6、B7）為測試變量，森林、裸地、水體、其它水面和其它用地為目標變量。

首先將選擇的訓練樣本文件轉(zhuǎn)換為ASCII格式， 再利用excel處理ASCII數(shù)據(jù)文件， 使之滿足C4.5歸納學習所要求的數(shù)據(jù)結(jié)構(gòu)格式。利用C4.5算法自動建立決策樹必須建立兩個后綴分別為data和names的文件， 這兩個文件必須同名， 且必須保存在同一個文件夾中。 其中data文件是訓練區(qū)樣本點的條件屬性及所屬類別構(gòu)成的數(shù)據(jù)文件， 而names文件主要是對屬性的名稱和類型的定義。 本文在基于C4.5算法對試驗區(qū)遙感影像進行知識挖掘后， 挖掘出的本試驗區(qū)所有規(guī)則如圖3所示。 將C4.5提取的規(guī)則應用到分類模型中， 實現(xiàn)對研究區(qū)TM影像的分類，其分類結(jié)果如圖4（右）所示。

圖4待分類圖像（左）及分類結(jié)果圖（右）3.3分類精度評價

為了更好地分析基于C4.5算法提取的分類規(guī)則的準確度，本文對分類結(jié)果進行了精度評價精度。本文采用的是基于混淆矩陣的方法[17]對遙感影像進行分類結(jié)果的評價，精度評價結(jié)果如表1所示。其中檢驗數(shù)據(jù)是綜合參考同一地區(qū)高分辨率遙感影像與目視解譯相結(jié)合，隨機選取的檢測樣本。

從分類結(jié)果以及精度評價表可以看出，利用C4.5算法提取的規(guī)則進行的分類，其結(jié)果是令人滿意的。其中對水體和其它水面的分類精度最高，達到了100%。對其它用地的分類精度最低，只有70.19%，分析原因可能是因為地形因素的影響。如若在這些地形較復雜的區(qū)域，對分類規(guī)則加入集合了人為分類經(jīng)驗的人工干預，在此基礎(chǔ)上可能會使分類精度得到提高。表1試驗區(qū)基于C4.5算法分類精度評價結(jié)果

類型森林裸地其它水面水體其它用地總和森林1288001137裸地91130041163其它水面5016006171水體0001490149其它用地101500113138總和152136160149161758生產(chǎn)者精度/%84.2183.08 100.00 100.00 70.19 用戶精度/%87.0279.60 95.81100.00 89.68總精度：87.496 0%kappa系數(shù)：0.862 3注：表中“森林、裸地、其它水面、水體、其它用地、總和”表示象元的個數(shù)

4結(jié)論

本文在研究C4.5算法的基礎(chǔ)上，利用其對遙感數(shù)據(jù)進行了規(guī)則挖掘，并根據(jù)其生成的規(guī)則形式，設計與實驗了規(guī)則編輯器，為人工干預與理論規(guī)則的結(jié)合提供了方式和途徑。在利用C4.5算法自動提取規(guī)則的分類實驗中，實驗結(jié)果驗證了利用該算法挖掘出的規(guī)則正確率高而且運行速度快，利用提取的規(guī)則進行的遙感影像分類結(jié)果令人滿意。雖然基于C4.5算法提取的規(guī)則在遙感影像分類中顯示出了巨大的潛力，但以下問題需要進一步研究：（1）當某一類別產(chǎn)生多條規(guī)則時，如何判別出最優(yōu)規(guī)則。（2）在地形較復雜的地區(qū)，如若將C4.5算法自動提取的規(guī)則與人工干預相結(jié)合，能否得到較高、較理想的分類精度。這些都將是后續(xù)所要進行實驗研究的內(nèi)容。

參考文獻：

[1]楊桄，劉湘南，張柏，等. 基于多特征空間的遙感信息自動提取方法[J]. 吉林大學學報：地球科學版， 2005，35 （2） ： 257-260.

[2]潘琛，杜培軍，羅艷，等.一種基于植被指數(shù)的遙感影像決策樹分類方法[J].計算機應用，2009，29（3）：777-798.

[3]趙英時.遙感應用分析原理與方法[M].北京：科學出版社，2003：10-200.

[4]術(shù)洪磊，毛贊猷.GIS 輔助下的基于知識的遙感影像分類方法研究—以土地覆蓋/土地利用類型為例[J].測繪學報，1997，26（4） ：328-332.

[5]張健康，程彥培，張發(fā)旺，等.基于多時相遙感影像的作物種植信息提取[J].農(nóng)業(yè)工程學報，2012，28（2）：134-141.

[6]吳健生，潘況一，彭建，等.基于QUEST決策樹的遙感影像土地利用分類-以云南省麗江市為例[J].地理研究，2012，31（11）：1 973-1 980.

[7]QUINLAN J R.C4.5：Programs for Machine Learning[M].San Mateo， CA： Morgan Kaufmann，1993：1-25.

[8]張桂杰.數(shù)據(jù)挖掘決策樹分類算法的研究與應用[D].長春理工大學碩士論文，2005.

[9]HAN JIAWEI，KAMBER M. Data mining： Concepts and Techniques[M]. Beijing：Beijing Higher Education Press， 2001：285-358.

[10]劉鶯迎.決策樹分類算法的分析和比較[J].科技情報開發(fā)與經(jīng)濟，2008（2）：65-67.

[11]吉根林.決策樹分類技術(shù)研究[J].計算機工程，2004，9（30）：94-98.

[12]唐華松，姚耀文.數(shù)據(jù)挖掘中決策樹算法的探討[J].計算機應用研究，2001（8）：18-22.

[13]姜麗華，楊曉蓉.基于決策樹分類技術(shù)的遙感影像分類方法研究[J].農(nóng)業(yè)網(wǎng)絡信息，2009（10）：34-42.

[14]劉勇洪，牛錚，王長耀.基于MODIS數(shù)據(jù)的決策樹分類方法研究與應用[J].遙感學報，2005，9（4）：405-412.

[15]吳寒.基于粗糙集的決策樹算法研究與改進[D].哈爾濱工程大學碩士論文，2008.

[16]夏琰.數(shù)據(jù)挖掘決策樹分類算法的研究與應用[D].吉林大學碩士論文，2008.

[17]CONGALTON R G.A review of assessing the accuracy of classifications of remotely sensed data[J].Remote Sensing of Enviroment，1991，37（1）：35-46.

（責任編輯：李麗，范君）