李 雪,舒 宁,刘小利
(1.中国地震局地震研究所 地震大地测量重点实验室,武汉 430071;2.武汉大学遥感信息工程学院,武汉 430079)
序贯分析(Sequential Analysis)是数理统计学的一个分支,由著名统计学家A WALD于1947年提出。序贯分析的研究对象就是所谓“序贯抽样方案”,即如何用这种抽样方案得到的样本去作统计推断。序贯抽样方案是指在抽样时,不事先规定总的抽样个数(观测或实验次数),而是先抽少量样本,根据其结果,再决定停止抽样或继续抽样、抽多少,这样下去,直至决定停止抽样为止。序贯分析方法的提出是数理统计学中的一大成就,该方法在众多领域得到了广泛的应用[1-3]。
本文在基于决策树分类的面向对象变化检测方法中引入了序贯分析概念,提出一种基于序贯决策融合的变化检测方法,为提高遥感影像变化检测结果的准确性提供了一条技术途径。
决策树(Decision Tree)是一种机器学习方法,通过对训练样本进行归纳学习获得一组分类规则。决策树一般是由根节点、中间节点和叶节点组成的一幅有向无环图。与基于向量间距离度量的模式识别方法不同,决策树是一种非度量模式识别方法。由于只对属性d元组(d为有限元)的取值状况进行统计分析,不计算属性向量的距离或相似性,因此决策树可以用于处理任何离散数据,甚至非数字类数据(例如语义数据等)[4]。
决策树分类的基本算法主要包括以下5个步骤。
(1)生成训练样本数据集:所有的训练样本例子满足形式(X,L)={x1,x2,…,xn,li},其中X代表参与分类的n维特征属性向量,L={l1,l2,…,lK}代表K个样本类别,li表示K个类别中的第i种类别。
(2)分支:在节点t,对单一问题(属性)进行“是”、“否”划分,生成 tY,tN2个子节点。设 I(t),I(tY),I(tN)分别表示节点t与tY,tN的不纯度,则划分准则为使分支后不纯度减小量ΔI(t)最大,计算公式如式为
式中:Nt表示节点t处待分样本数量;NtY和NtN分别表示在节点t处被划分为“是”和“否”的样本数量;不纯度函数I(t)常用信息熵表示,即
式中:Pt(li)表示节点t处类别为li的样本数量占节点t处所有样本数量的比例,节点t处样本类别越一致则I(t)越小。
(3)停止分支:对节点停止分支并将其表明为“树叶”。停止分支的准则一般有2种:一是采用阈值法,如果ΔI(t)小于阈值T则停止分支;二是节点处的样本数量足够小或样本类别足够纯净(属于同一类)则停止分支。
(4)剪枝:有时,分支会因算法缺少足够的前瞻性而过早停止,这称为“视界局限效应”。在剪枝过程中,对充分生长的树比较其所有相邻的成对叶节点。如果消去它们能引起令人满意(很小的)的不纯度增长,则消去叶节点,并令它们的父节点成为新的叶节点[5]。
(5)类别分配:采用多数规则,将叶子t标记为Xt中占多数的类别ωj。
决策树在数据挖掘、机器学习等领域具有广泛的应用。经典的决策树分类算法有ID3和C4.5/C5.0。ID3算法最早由Quinlan提出,称为交互式二分法程序第3版(Interactive Dichotomizer-3),其设计意图只是针对语义数据进行处理[6]。C4.5/C5.0算法是ID3算法的改进版,也是目前最流行的分类树方法。C4.5/C5.0算法不仅增加了剪枝算法而且还加强了对连续属性的处理能力,通过对连续数据的离散化处理,实现了对连续属性的决策树分类[7]。
基于决策树分类器的变化检测属于分类后变化检测方法,本文以像斑作为影像处理的基本单元,通过遥感影像与矢量辅助数据进行数据套合提取地物像斑。矢量辅助数据可以是基准期的土地利用数据或其他专题类数据。将矢量辅助数据分别与基准期和检测期的遥感影像套合,获取的地物像斑具有相同的空间属性(位置相同、形状相同)和不同的影像特征属性(光谱特征不同、纹理特征不同)。通过特征提取,提取不同时相遥感影像像斑的光谱特征(不同波段像斑的均值和方差)和纹理特征(不同波段像斑灰度共生矩阵的二阶矩、惯性矩和熵),建立像斑特征数据库。由于矢量辅助数据带有基准期像斑的类别信息,通过逐类人工选择的方式可以获取少量检测期类别未发生变化地物像斑作为样本像斑。将样本像斑的特征数据带入决策树算法进行训练,再利用训练后的决策树分类器对非样本像斑特征进行分类判别,即可获得检测期像斑的地物类别。最后,将像斑的基准期类别和检测期类别进行对比,即可找出发生变化的像斑对象。
本文基于决策树算法的变化检测流程如图1。
决策树分类器由于具备非度量模式识别的特性,适合对非数值型离散数据进行处理。由于决策树C5.0算法加强了对连续型数据的处理能力,使其可同时处理具有连续和离散2种属性的数据。然而基于决策树分类的变化检测方法采用的是一次性分类原则,这种方法容易受到初始样本和分类误差的影响。因此本文提出一种序贯决策融合方法对决策树变化检测方法进行了改进。
图1 决策树变化检测流程Fig.1 Change detection process by decision tree
本文根据序贯分析的思想提出一种序贯决策融合方法(Sequential Decision Fusion)。该方法是一种针对单分类器的决策融合方法,其核心思想是对同一样本反复进行分类判别,每次判别时都将前一次分类结果作为下一次的输入变量与原特征向量一起组成新的特征向量输入分类器[8-9]。
图2 分类序列Fig.2 Classification sequence
设x代表样本特征向量,f(x)代表分类器,y为样本所属的类别,则对样本x多次分类判别后产生的类别序列如图2所示。
图2中:yi表示第i次分类判别时获得的类别;xi表示第i次分类判别时的输入变量对x多次分类得到的类别序列,类别序列的计算可以由后验概率表示,即
序贯决策融合的具体算法如下。
(1)分类器融合训练:
①设训练样本集为S={(xi,yi)},则对于训练样本的预测集合可以表示为
式中:f(·)表示一种分类器算法;^yi表示样本xi的预测类别。
③返回函数f=f(S),f'=f(S')。
(2)分类器决策分类:
①对于待分类数据x,求其预测值^y=f(x)。
②生成扩展数据x'。
③返回决策融合类别y=f'(x')。
函数f'为对函数f的输入变量维度进行扩展后的分类函数。序贯决策融合算法中的参数W决定了参与决策融合的历史决策层数,当W取值为1时的序贯决策融合又可被视为一马尔科夫过程,其算法结构如图3所示。由于序贯决策融合是将分类器预测类别作为新的特征输入的迭代算法,因此所选择的分类器必须能处理输入的数值变量(特征向量)和符号变量(类别符号)。由于决策树C5.0算法在原有善于处理离散数据这一特性的基础上,增强了对连续型数据的处理能力,因此本文采用决策树分类器作为序贯决策融合的基本分类算法。
图3 序贯决策融合分类算法结构(W=1)Fig.3 The structure of classification algorithm by sequential decision fusion(W=1)
采用序贯决策融合算法代替1.2节决策树变化检测方法中的决策树训练,即可获得本文的序贯决策融合变化检测方法。序贯决策融合训练流程如图4所示。首先,将训练样本(特征向量形式为{影像特征,样本类别},其中影像特征包括像斑的光谱特征和纹理特征)带入决策树进行初始训练,获得样本的预测类别,再对原输入特征数据集进行扩展,获得形如{影像特征,预测类别,样本类别}的扩展训练样本特征向量。然后,将扩展训练样本带入决策树训练,生成扩展决策树,并获得样本的预测类别。将样本新的预测类别与原预测类别进行对比,如完全一致,则表示决策树训练输出稳定,算法终止;如不一致,则将新的预测结果带回对上一次输入特征扩展步骤,生成新的扩展训练样本,其特征向量形式为{影像特征,原预测类别,新预测类别,样本类别}并再次对决策树进行训练。经过反复迭代训练,直至决策树输出稳定则训练终止。
由于本文序贯决策融合算法中的序贯历史参数W取值为1,因此,对决策树训练的输入特征数据集只扩展至“原预测类别”,每次迭代训练中产生的新的样本类别预测结果将取代上一次输入特征向量中的“原预测类别”,生成新的特征向量并参与扩展决策树的训练。
当训练终止后,由初始训练获得的决策树和其后历次迭代训练获得的扩展决策树构成的决策树序列称为序贯决策树。将非样本像斑的检测期特征代入序贯决策树,依序列进行序贯决策分类,获得的最终类别为经过序贯决策融合的像斑类别。将像斑的检测期类别与基准期类别进行对比即可找出发生变化的像斑对象。
图4 序贯决策融合训练流程Fig.4 Training process of sequential decision fusion
本文实验采用的遥感影像数据为武汉市某区域2002年和2005年获取的Quickbird多光谱影像,包含蓝、绿、红和近红外4个波段,分辨率为2.4m(图5(a)为2002年遥感影像,图5(b)为2005年遥感影像)。矢量辅助数据为同一区域的土地利用矢量数据(如图5(c)所示),成图时间为2002年,图中包含22种基本土地利用类型,共计572个矢量对象。
图5 实验数据Fig.5 Experimental data
经过数据套合、特征提取、样本选择后,获得84个样本像斑和488个待检测像斑,根据样本对检测期像斑类别进行判别。序贯决策融合初始时,先将84个样本像斑的特征输入决策树分类器进行训练,获得初始判别决策树,再经过反复扩展、迭代训练获得序贯决策树。将488个待检测像斑特征代入序贯决策树进行类别判别,找出变化像斑。图6所示为变化检测结果,其中:图6(a)为标准变化结果,该结果为人工解译判断的变化地物像斑的结果;图6(b)为采用决策树判别(C5.0算法)的变化检测结果;图6(c)为采用序贯决策融合的变化检测结果(其中W=1)。
图6 变化检测结果Fig.6 Results of change detection
分别将决策树变化检测和序贯决策融合变化检测结果与标准变化结果进行对比,2种方法的漏检率、误检率、总体精度和kappa系数(一种计算分类精度的方法)如表1所示。由于序贯融合方法是利用过去的预判值对分类结果进行修正,因此与未经迭代的原分类器算法获得的变化检测结果相比,各项精度都有所提高。序贯融合的迭代一般都会快速收敛,图7给出了迭代次数与发生变化的像斑数量之间的关系。由图7可知,本文序贯决策融合在第4次迭代时,变化像斑数量已经稳定。影响收敛迭代次数的主要因素为参与训练的样本数量及样本特征的数量。
图7 序贯决策融合迭代统计Fig.7 Statistics of iterative process by sequential decision fusion
表1 变化检测结果精度评定Table 1 Accuracy assessment for change detection results
本文根据序贯分析方法提出了一种序贯决策融合的变化检测方法。该方法利用决策树算法可同时处理连续型和离散型数据的特点,通过将前一次决策树判决结果与原输入数据组合成新的输入特征向量并代入决策树重新训练,进行反复迭代,直至算法获得稳定的输出。经过实验对比,发现采用序贯决策融合的变化检测结果各项精度评定指标均好于决策树判别的变化检测结果。
实验结果证明了本文方法的有效性,为提高遥感影像变化检测结果的准确性提供了一条新的技术途径。
[1]崔 颖,郭 伟,王 蕾,等.序贯分析方法在不同分析方法一致性检验中的应用[J].吉林大学学报(医学版),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].系统仿真学报,2009,21(9):2531-2534.(LI Qian,FENG 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]李 军,李敏勇,常玉国.基于模式识别和序贯分析的综合态势感知模型研究[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].李晶皎,朱志良,王爱侠,等译.北京:电子工业出版社,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].李宏东,姚天翔,译.北京:机械工业出版社,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]宋晓宁,吴小俊.基于决策树的模糊序贯最小优化分类器的人脸识别[J].江苏科技大学学报(自然科学版),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))