1、互性,实用性较强。关键词:决策树;算法;图像分类;遥感;VC +中图法分类号:TP391文献标识码:A 文章编号:100123695（20070120207203Research and I m p lementati on of Classificati onin Remote Sensing I m age Based on Decisi on Tree A lgorith mLUO Lai 2p ing 1,G ONG Hui 2li 2,L I U Xian 2lin（1.A rtificial Intelligence Institute,B eijing C ity U niver
2、sity,B eijing 100083,China;2.Key L aboratory of R esource Environm ent &GI S,Collegeof Resource Environm ent &Touris m ,Capital N or m al U niversity,B eijing 100037,China Abstract:I n allusi on t o the traditi onal classificati on s shortcom ing of l ow effect when dealing with re mote sensing data
3、 thathas comp lex s patial 2character distributing,combining with tree 2classificati on technol ogy which using dela m inating method,Classificati on and Regressi on Tree （CART algorith m is i m p r oved,which is used largely in data m ining .And an algorith m based on hu man 2computer interacti on
4、is put f or ward,which is app lied t o re mote sensing i m age classificati on with better flexi 2bility and r obust,als o with si m p le and clear class structure,having achieved better classified effect .And a s pecial data struc 2ture is designed t o realize this classifying syste m in VC +.Pract
5、ice show that this system has good stability,alternateness and str ong p racticability .Key words:Decisi on Tree;A lgorith m;I m age Classificati on;Re mote Sensing;在遥感技术的研究中,通过遥感图像判读识别各种目标是遥感技术发展的一个重要环节1,无论是专业信息获取、动态变化预测,还是专题地图制作和遥感数据库的建立都离不开分类。早期的分类技术是目视解译,其时效性、可重复性差,解译结果也因人而异,很难进行比较和转换。近年来随着计算机技术
6、的飞速发展,计算机识别自动分类已逐渐代替了早期的分类技术,成为遥感应用的一个重要组成部分,也是当前遥感发展的前沿2。目前,遥感图像自动分类主要利用统计模式方法1,可分为非监督和监督两类。由于遥感图像往往存在异物同谱和同物异谱的现象,用传统的统计模式方法分类的效果不甚理想,因而人们不断研究新的分类方法。例如模拟人脑思维方式提出的人工神经网络分类3;针对地物特征和模糊性提出的模糊聚类分类4模式识别与人工智能技术相结合的专家系统分类计算混合像元内各典型地物所占面积比例的混合像元分解法5;按照一定的知识规则,采用分层思想的树分类6等技术。虽然这些方法在一定程度上提高了分类精度,达到了更好的效果,但是它
7、们仍是以遥感图像的光谱特征为基础的。在实践中,由于各种因素的影响,如地面起伏对地物光谱反射强度的影响7;像素的分辨率低而造成的混类像素影响;分类中只考虑单个像素光谱特征而未考虑相邻像素类属的相关性及结构特征等因素,都会使常规的计算机分类效果不够理想。因此需要采取一些辅助的处理措施1,如引入地面高程、坡度、坡向信息等,以设法改善分类效果。但目前的遥感图像计算机自动分类技术均不能很好地引入这些辅助信息1。本文在采用分层思想的树分类的基础上,对广泛用于数据挖掘模型中的决策树算法进行改进,并以VC +6.0作为开发工具,将其应用到图像自动分类中,能够很好地解决这个难题,达到了更好的分类效果。1决策树算
8、法的图像分类研究及实现111常用的决策树算法简介决策树8,9是一个类似流程图的树型结构,其中树的每个内部节点代表对一个属性的测试,其分支代表测试的每个结702第1期罗来平等:基于决策树算法的遥感图像分类研究与实现果,而树的每个叶子节点代表一个类别,树的最高层节点就是根节点,是整个决策树的开始。其算法的早期版本可以追溯到20世纪60年代10。后来特别是最近几年,它被广泛应用到许多需要分类识别的领域,如科学实验、医疗诊断、信贷审核、商业预测、案件侦破等。这类算法无须相关领域知识,且相对于基于模糊理论的分类方法,具有更高的分类准确率和更快的处理速度11。在很多领域特别是数据挖掘中,决策树是一种经常要
9、用到的技术12,它可以用于分析数据,也可以用来作预测,常用的算法有I D3,CART,C4.5等。（1I D3算法是最有影响和最早的决策树算法之一10,其建立在推理系统和概念学习系统的基础上,但它是非递增学习算法。每当一个或数个新例子进来,就必须重新执行一次该算法,把新来的例子和以前旧的全部例子集合变成决策树,因此效率非常低。而且它是基于单变量的,难以表达复杂概念,抗噪性差。（2C4.5是I D3的改进版本13。它主要在以下几个方面对I D3作了改进:缺省值的预测属性仍可用,提出了修剪思想,可以进行规则推导。（3C ART（on and Regressi on Tree,分类回归树14是一种数
10、据勘测和预测算法。它用一种非常简单的方法来选择问题,即将每个问题均试一次,然后挑出最好的一个,用它把数据分成更有序的两个分割,再对新的分割分别提出所有可能的问题。因此该算法得到的决策树每个节点有两个分支,即二叉树。112改进决策树生成算法为了更好地将决策树算法应用于遥感图像分类中,本文在CART算法的基础上作了以下改进:（1常用的决策树算法均由用户提供训练样本集,计算机执行算法生成决策树,整个过程由计算机自动完成,不需要任何人工干预。由于遥感图像训练集的属性取值太多,而有些取值是用不到的,需要把这些用不到的取值过滤掉,否则会影响整颗树的质量。因此本文在决策树的生成过程中引入人机交互技术,将用户
11、的先验知识用于决策树的生成过程中,使得生成的决策树更加合理可信。基于人机交互的决策树方法由用户与计算机相互交互,共同完成,故要求计算机提供可视化环境和工具（图1,友好的界面方便用户输入先验知识。（2建立一棵树首先需要选择一个属性作为根节点,然后将该属性的每一个可能值作为一个分支;再在每个分支所剩余的属性中找出一个属性作为该分支的下一个节点,如此循环到所有属性均被选用为止。常用的决策树算法均采用信息熵作为选择标准。由于遥感图像中的噪音比较多,而基于信息熵属性选择标准往往抗干扰能力不强且以对数计算为累加计算的计算量较大,故本文采用了一种新型的属性选择标准属性重要性15来提高属性选择的效率。该方法是
12、用训练值的变化而引起输出变化的累加值作为衡量属性重要性的标准,即对于某个属性,如果训练值的变化而引起的输出变化越大,说明该属性就越重要。可用式（1表示为C（K=|x（i,k-x（j,k|sign|y（i-y（j|（ij（1式中:C（K表示第k个属性的输入/输出关联值;x（i,k,x（j, k表示第i,j个样本的第k个条件属性值;y（i,y（j表示第i, j个样本的决策属性值;sign（x表示符号函数。113一种自定义的数据结构数据结构的设计在程序设计中很关键,一个好的数据结构可以让算法更加精练,大大提高开发效率。本文采用的算法是在C ART算法的基础上改进过来的,因此生成的也是一棵二叉树。但由
13、于在生成算法中要频繁地查找和调整决策树（添加或者删除子树,传统的二叉树结构在速度上不能满足算法的需求,故笔者在设计系统时创新了一种类二叉树的结构（图2。在树的每一层都设置了一个头节点,且树的每个节点只 有指向父节点和左右兄弟节点的指针。class Tree Node/树节点的结构public:Tree Node I nfo m_Node I nf o;/这个节点的数据区Tree Node3m_Parent N ode;/父节点指针Tree Node3m_LB r other Node;/左兄弟节点指针Tree Node3m_RB r other Node;/右兄弟节点指针Tree Node（p
14、ositi on ne wpos,CString ne wQor A,CString ne wEx2 p ressi on;Tree Node（;virtualTree Node（;struct level_node/每一层的头节点结构Tree Node3level_treenode;/指向这一层的第一个树节点level_node3next_level;/指向下一层的头节点114系统实现图3为系统架构图。其中D是训练集合,A为分类属性集合。另有测试数据集合T用来评估生成决策树的误差。整个过程分为两个部分进行:决策树构造,也称学习过程,主要工作是输入训练集,采用改进的决策树生成算法生成决策树,并
15、作好分类前的预备工作,即提取分类规则;决策树预测,也称分类过程,主要工作是应用分类规则进行分类,并根据测试集,计算出分类误差,误差较大的对决策树作裁剪算法。8计算机应用研究2007年误差较小的就输出其分类结果,分类结果有两种:（1将分类结果写入新的遥感图像文件（如I M G 文件中;（2可视化的树结构,在树的叶子节点保存着每一类的属性。该系统以VC +6.0为开发工具,采用面向对象的思想设计与开发。2应用实例本文以某农村T M127波段（图4作为数据源,利用本系统进行决策树分类。图5为分类后的图像,图6为分类后决策树分类结果图。为了对分类精度进行评价,本文将原始图像与分类后的图像进行对比,选取
16、了大量的样本数据,建立了该分类方法的混淆矩阵,并计算出总体分类精度为86.9%,Kappa 系数可达0.85。通过混淆矩阵发现,除了建筑用地外,对于其他地物可以达到90.3%以上的分类精度。经检验发现,其误判像元主要是位于耕地中。这主要是因为建筑用地与耕地形状都非常相似,且紧密分布在一起,从而在分类中被误判。3总结与展望在遥感技术飞速发展的今天,人们更多地应用多源遥感数据、多波段图像数据、高光谱数据,如何充分利用这些数据,又不至于使计算速度降低,传统分类方法就显得力不从心了,尤其是面对空间特征分布极为复杂的数据时,更显示出它们的不足。通过本文研究发现:决策树算法对于输入数据的空间特征和分类标志
17、具有更好的弹性和鲁棒性,它用于遥感数据分类的优势主要在于对数字图像数据特征空间的分割上,其分类结构简单明了,尤其是二叉树结构的单一决策树结构十分容易解释。因此,当遥感图像数据特征的空间分布很复杂,或者源数据各维具有不同的统计分布和尺度时,基于决策树算法的分类方法能够获得较为理想的分类结果。然而,决策树算法应用于遥感图像分类尚处于探索阶段,大部分都是理论上针对某一具体应用的探讨,目前研究成果比较少16,还没有较为通用的软件诞生。本文则在探索理论的基础上对开发该分类系统作出了尝试,并且该分类系统已投入遥感应用行业中,实践发现该系统交互性和稳定性很好,能适应一般的需求。进一步的工作就是将决策树算法与
18、其他技术,如神经网络相结合应用到该系统中,以期获取更高的分类精度和更好的分类效率。参考文献:1汤国安,等.遥感数字图像处理M .北京:科学出版社,2004.2张仁华.实验遥感模型及地面基础M .北京:科学出版社,1996.3It o Y,Omatu S .Extended LVQ Neural Net w ork App r oach t o Land Cover Mapp ing J .I EEE Transacti ons on Geoscience and Remote Sensing,1999,37（1:3132316.4Paola J D ,Schowengerdt R A.A De
19、tailed Comparis on of Back 2p r opa 2gati on Neural Net w ork and Maxi m um 2likelihood Classifiers for U rban Land U se Classificati on J .I EEE Transacti ons on Geosciences Re 2mote Sensing,1995,33（4:9812996.5FridelM A,B r odley C E,Strahler A H.Maxi m izing Land Cover Clas 2sificati on Accuracies
20、 Pr oduced by Decisi on Trees at Continental t o Gl obal Scales J .I EEE Transacti ons on Geosciences and Remote Sensing,1999,37（2:9692979.6FriedlM A,B r odeley C E .Decisi on Tree Classificati on of Land Coverfr om Re motely Sensing Data J .Re mote Sensing of Envir onment,1997,（61:3992409.7李彤,等.采用决
21、策树分类技术对北京市土地覆盖现状进行研究J .遥感技术与应用,2004,19（6:4852487.8J ia wei Han,M icheline Kamber .Data M ining:Concep ts and Tech 2niquesM .北京:高等教育出版社,2002.9A lex Bers on,Stephen S m ith,Kurt Thearling .Building Data M ining App licati on for CR M M .北京:人民邮电出版社,2001.10戴南.基于决策树的分类方法研究D .南京师范大学硕士学位论文,2003.11李宁,等.决策树算
22、法及其常见问题的解决J .计算机与数字工程,2005,33（3:60264.12孙雪莲.数据挖掘中分类算法研究D .吉林大学硕士学位论文,2002.13曹叶虹.结合粗糙集理论的决策树技术的研究D .华南理工大学硕士学位论文,2002.14秦欢,等.基于决策树CART 的中文文语转换系统语音合成单元的预选J .微型电脑应用,2004,20（5:526.15倪春鹏,等.一种新型决策树属性选择标准J .武汉科技大学学报（自然科学版,2004,27（4:4372439.16刘小平,等.像元信息分解和决策树相结合的图像分类方法J .地理与地理信息科学,2004,20（6:35.作者简介:罗来平（19822,男,江西人,助教,工学硕士,主要研究方向为遥感与三维地理信息系统;宫辉力（19562,男,长春人,教授,博导,博士,主要研究方向为地理信息系统和遥感技术应用;刘先林（19392,男,广西人,院士,博导,主要研究方向为三维获取与应用。902第1期罗来平等:
