基于決策樹算法的遙感圖像分類研究與實現

摘要：針對傳統分類方法在處理空間特征分布極為復雜的數據時效果不佳的缺點，結合分層思想的樹分類技術，對廣泛用于數據挖掘模型中的CART決策樹算法進行改進，提出了一種基于人機交互的決策樹算法，將其應用到遙感圖像自動分類中，具有很好的彈性和魯棒性，且分類結構簡單明了，達到了更好的分類效果。以VC++ 6.0作為開發工具，定義了一種特殊的數據結構，實現了該分類系統。實踐表明，該系統具有很好的穩定性和交互性，實用性較強。

關鍵詞： 決策樹； 算法； 圖像分類； 遙感； VC++

中圖法分類號：TP391文獻標識碼：A

文章編號：1001－3695(2007)01－0207－03

在遙感技術的研究中，通過遙感圖像判讀識別各種目標是遙感技術發展的一個重要環節[1]，無論是專業信息獲取、動態變化預測，還是專題地圖制作和遙感數據庫的建立都離不開分類。早期的分類技術是目視解譯，其時效性、可重復性差，解譯結果也因人而異，很難進行比較和轉換。近年來隨著計算機技術的飛速發展，計算機識別自動分類已逐漸代替了早期的分類技術，成為遙感應用的一個重要組成部分，也是當前遙感發展的前沿[2]。

目前，遙感圖像自動分類主要利用統計模式方法[1]，可分為非監督和監督兩類。由于遙感圖像往往存在異物同譜和同物異譜的現象，用傳統的統計模式方法分類的效果不甚理想，因而人們不斷研究新的分類方法。例如模擬人腦思維方式提出的人工神經網絡分類[3]；針對地物特征和模糊性提出的模糊聚類分類[4]；模式識別與人工智能技術相結合的專家系統分類[1]；計算混合像元內各典型地物所占面積比例的混合像元分解法[5]；按照一定的知識規則，采用分層思想的樹分類[6]等技術。

雖然這些方法在一定程度上提高了分類精度，達到了更好的效果，但是它們仍是以遙感圖像的光譜特征為基礎的。在實踐中，由于各種因素的影響，如地面起伏對地物光譜反射強度的影響[7]；像素的分辨率低而造成的混類像素影響；分類中只考慮單個像素光譜特征而未考慮相鄰像素類屬的相關性及結構特征等因素，都會使常規的計算機分類效果不夠理想。因此需要采取一些輔助的處理措施[1]，如引入地面高程、坡度、坡向信息等，以設法改善分類效果。但目前的遙感圖像計算機自動分類技術均不能很好地引入這些輔助信息[1]。本文在采用分層思想的樹分類的基礎上，對廣泛用于數據挖掘模型中的決策樹算法進行改進，并以VC++ 6.0作為開發工具，將其應用到圖像自動分類中，能夠很好地解決這個難題，達到了更好的分類效果。

1決策樹算法的圖像分類研究及實現

1．1常用的決策樹算法簡介

決策樹[8，9]是一個類似流程圖的樹型結構，其中樹的每個內部節點代表對一個屬性的測試，其分支代表測試的每個結果，而樹的每個葉子節點代表一個類別，樹的最高層節點就是根節點，是整個決策樹的開始。其算法的早期版本可以追溯到20世紀60年代[10]。后來特別是最近幾年，它被廣泛應用到許多需要分類識別的領域，如科學實驗、醫療診斷、信貸審核、商業預測、案件偵破等。這類算法無須相關領域知識，且相對于基于模糊理論的分類方法，具有更高的分類準確率和更快的處理速度[11]。

在很多領域特別是數據挖掘中，決策樹是一種經常要用到的技術[12]，它可以用于分析數據，也可以用來作預測，常用的算法有ID3，CART，C4.5等。

（1）ID3算法是最有影響和最早的決策樹算法之一[10]，其建立在推理系統和概念學習系統的基礎上，但它是非遞增學習算法。每當一個或數個新例子進來，就必須重新執行一次該算法，把新來的例子和以前舊的全部例子集合變成決策樹，因此效率非常低。而且它是基于單變量的，難以表達復雜概念，抗噪性差。

（2）C4.5是ID3的改進版本[13]。它主要在以下幾個方面對ID3作了改進：缺省值的預測屬性仍可用，提出了修剪思想，可以進行規則推導。

（3）CART（Classification and Regression Tree，分類回歸樹）[14]是一種數據勘測和預測算法。它用一種非常簡單的方法來選擇問題，即將每個問題均試一次，然后挑出最好的一個，用它把數據分成更有序的兩個分割，再對新的分割分別提出所有可能的問題。因此該算法得到的決策樹每個節點有兩個分支，即二叉樹。

1．2改進決策樹生成算法

為了更好地將決策樹算法應用于遙感圖像分類中，本文在CART算法的基礎上作了以下改進：

（1）常用的決策樹算法均由用戶提供訓練樣本集，計算機執行算法生成決策樹，整個過程由計算機自動完成，不需要任何人工干預。由于遙感圖像訓練集的屬性取值太多，而有些取值是用不到的，需要把這些用不到的取值過濾掉，否則會影響整顆樹的質量。因此本文在決策樹的生成過程中引入人機交互技術，將用戶的先驗知識用于決策樹的生成過程中，使得生成的決策樹更加合理可信。基于人機交互的決策樹方法由用戶與計算機相互交互，共同完成，故要求計算機提供可視化環境和工具（圖1），友好的界面方便用戶輸入先驗知識。

（2）建立一棵樹首先需要選擇一個屬性作為根節點，然后將該屬性的每一個可能值作為一個分支；再在每個分支所剩余的屬性中找出一個屬性作為該分支的下一個節點，如此循環到所有屬性均被選用為止。常用的決策樹算法均采用信息熵作為選擇標準。由于遙感圖像中的噪音比較多，而基于信息熵屬性選擇標準往往抗干擾能力不強且以對數計算為累加計算的計算量較大，故本文采用了一種新型的屬性選擇標準——屬性重要性[15]來提高屬性選擇的效率。該方法是用訓練值的變化而引起輸出變化的累加值作為衡量屬性重要性的標準，即對于某個屬性，如果訓練值的變化而引起的輸出變化越大，說明該屬性就越重要。可用式（1）表示為

1．3一種自定義的數據結構

數據結構的設計在程序設計中很關鍵，一個好的數據結構可以讓算法更加精練，大大提高開發效率。本文采用的算法是在CART算法的基礎上改進過來的，因此生成的也是一棵二叉樹。但由于在生成算法中要頻繁地查找和調整決策樹（添加或者刪除子樹），傳統的二叉樹結構在速度上不能滿足算法的需求，故筆者在設計系統時創新了一種類二叉樹的結構（圖2）。在樹的每一層都設置了一個頭節點，且樹的每個節點只有指向父節點和左右兄弟節點的指針。

class TreeNode//樹節點的結構

{

public:

TreeNodeInfo m_NodeInfo;//這個節點的數據區

TreeNode* m_ParentNode;//父節點指針 

TreeNode* m_LBrotherNode;//左兄弟節點指針

TreeNode* m_RBrotherNode;//右兄弟節點指針

TreeNode(position newpos， CString newQorA， CString newExpression);

TreeNode();

virtual ~TreeNode();

};

struct level_node//每一層的頭節點結構

{

TreeNode *level_treenode;//指向這一層的第一個樹節點

level_node *next_level;//指向下一層的頭節點

};

1．4系統實現

圖3為系統架構圖。其中D是訓練集合， A為分類屬性集合。另有測試數據集合T用來評估生成決策樹的誤差ε。整個過程分為兩個部分進行：①決策樹構造，也稱學習過程，主要工作是輸入訓練集，采用改進的決策樹生成算法生成決策樹，并作好分類前的預備工作，即提取分類規則；②決策樹預測，也稱分類過程，主要工作是應用分類規則進行分類，并根據測試集，計算出分類誤差，誤差較大的對決策樹作裁剪算法。

圖3系統架構圖

誤差較小的就輸出其分類結果，分類結果有兩種：

（1）將分類結果寫入新的遙感圖像文件（如IMG文件）中；

（2）可視化的樹結構，在樹的葉子節點保存著每一類的屬性。

該系統以VC++6.0為開發工具，采用面向對象的思想設計與開發。

2應用實例

本文以某農村TM17波段（圖4）作為數據源，利用本系統進行決策樹分類。圖5為分類后的圖像，圖6為分類后決策樹分類結果圖。為了對分類精度進行評價，本文將原始圖像與分類后的圖像進行對比，選取了大量的樣本數據，建立了該分類方法的混淆矩陣，并計算出總體分類精度為86.9%，Kappa系數可達0.85。通過混淆矩陣發現，除了建筑用地外，對于其他地物可以達到90.3%以上的分類精度。經檢驗發現，其誤判像元主要是位于耕地中。這主要是因為建筑用地與耕地形狀都非常相似，且緊密分布在一起，從而在分類中被誤判。

圖4原始圖像灰度圖

圖5決策樹分類后的圖像

圖6決策樹分類結果圖——二叉樹

3總結與展望

在遙感技術飛速發展的今天，人們更多地應用多源遙感數據、多波段圖像數據、高光譜數據，如何充分利用這些數據，又不至于使計算速度降低，傳統分類方法就顯得力不從心了，尤其是面對空間特征分布極為復雜的數據時，更顯示出它們的不足。通過本文研究發現：決策樹算法對于輸入數據的空間特征和分類標志具有更好的彈性和魯棒性， 它用于遙感數據分類的優勢主要在于對數字圖像數據特征空間的分割上，其分類結構簡單明了，尤其是二叉樹結構的單一決策樹結構十分容易解釋。因此，當遙感圖像數據特征的空間分布很復雜，或者源數據各維具有不同的統計分布和尺度時，基于決策樹算法的分類方法能夠獲得較為理想的分類結果。

然而，決策樹算法應用于遙感圖像分類尚處于探索階段，大部分都是理論上針對某一具體應用的探討，目前研究成果比較少[16]，還沒有較為通用的軟件誕生。本文則在探索理論的基礎上對開發該分類系統作出了嘗試，并且該分類系統已投入遙感應用行業中，實踐發現該系統交互性和穩定性很好，能適應一般的需求。進一步的工作就是將決策樹算法與其他技術，如神經網絡相結合應用到該系統中，以期獲取更高的分類精度和更好的分類效率。

參考文獻：

［1］湯國安，等.遙感數字圖像處理[M].北京:科學出版社，20-04.

［2］張仁華.實驗遙感模型及地面基礎[M].北京:科學出版社，1996.

［3］Ito Y，Omatu S.Extended LVQ Neural Network Approach to Land CoverMapping[J].IEEE Transactions on Geoscience and Remote Sensing，1999，37(1):313316.

［4］Paola J D，Schowengerdt R A.A Detailed Comparison of Backpropagation Neural Network and Maximumlikelihood Classifiers for Urban Land Use Classification[J].IEEE Transactions on Geosciences Remote Sensing，1995，33(4):981996.

［5］Fridel M A，Brodley C E，Strahler A H.Maximizing Land Cover Classification Accuracies Produced by Decision Trees at Continental to Global Scales[J].IEEE Transactions on Geosciences and Remote Sensing，1999，37(2):969979.

［6］Friedl M A，Brodeley C E.Decision Tree Classification of Land Cover from Remotely Sensing Data[J].Remote Sensing of Environment，1997，(61):399409.

［7］李彤，等. 采用決策樹分類技術對北京市土地覆蓋現狀進行研究[J].遙感技術與應用，20-04，19(6):485487.

［8］Jiawei Han，Micheline Kamber.Data Mining:Concepts and Techniques[M].北京:高等教育出版社，2002.

［9］Alex Berson，Stephen Smith，Kurt Thearling.Building Data Mining Application for CRM[M].北京:人民郵電出版社，2001.

［10］戴南.基于決策樹的分類方法研究[D].南京師范大學碩士學位論文，2003.

［11］李寧，等.決策樹算法及其常見問題的解決[J].計算機與數字工程，2005，33(3):6064.

［12］孫雪蓮.數據挖掘中分類算法研究[D].吉林大學碩士學位論文，2002.

［13］曹葉虹.結合粗糙集理論的決策樹技術的研究[D].華南理工大學碩士學位論文，2002.

［14］秦歡，等.基于決策樹CART的中文文語轉換系統語音合成單元的預選[J].微型電腦應用，20-04，20(5):56.

［15］倪春鵬，等.一種新型決策樹屬性選擇標準[J]. 武漢科技大學學報(自然科學版)，20-04，27(4):437439.

［16］劉小平，等.像元信息分解和決策樹相結合的圖像分類方法[J].地理與地理信息科學，20-04，20(6):35.

作者簡介：

羅來平（1982），男，江西人，助教，工學碩士，主要研究方向為遙感與三維地理信息系統；

宮輝力（1956），男，長春人，教授，博導，博士，主要研究方向為地理信息系統和遙感技術應用；

劉先林（1939）， 男，廣西人，院士， 博導，主要研究方向為三維獲取與應用。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文