分类树方法范文
分类树方法范文（精选8篇）
分类树方法 第1篇
比较常用的多目标分类方法有快速分类算法、人工神经网络法[1]、支持向量机法[2]、贝叶斯分类算法[3]和决策树法[4]等。决策树是用于分类和预测的主要技术之一,它着眼从一组无次序无规则的实例中推测出以决策树表示的分类规则。构造决策树的目的是找出属性和类别之间的关系,用它来预测目标未来的类别。它不需要训练样本,只需要在每一次分类过程中识别一种属性[5],学习能力强,适合用于处理大规模的学习问题,是数据挖掘最常用的方法之一[6]。利用决策树方法从大量数据中提取潜藏在其中的有用信息和规则被广泛应用和研究。
本文利用决策树C4.5 经典算法、Bagging集成方法构建组合决策树,建立地面多运动目标的分区决策树分析模型,对地面目标进行分类和预测。并且根据国际空中机器人大赛(IARC)的比赛规则搭建仿真平台验证该分类方法的可靠性。
1相关概念及其算法
1.1 C4.5算法
决策树代表对象属性与对象值之间的一种映射关系,常用于构造分类模型。目前决策树算法中比较流行的算法有ID3、C4.5、CART和CHAID等[7]。决策树是数据挖掘的重要方法,基于信息熵的ID3算法是决策树技术的经典算法,信息增益越大的属性分裂的可能性越大[8]。但是它只能处理离散型的属性,而C4.5算法既能处理离散型属性,也能处理连续性属性[9]。
ID3 算法是一种基于信息熵的决策树分类算[6]。其核心在于构建策树的过程中,节点属性的选择标准为信息熵,即选用具有最大信息增益的属性。这种做法能够在通过每一个非叶节点时获得最多的有关数据的类别信息。构造决策树的方法是:计算出数据集中全部属性的信息增益,按照从大到小的顺序排序。按照信息增益排列的顺序将他们对应的属性作为决策树的节点。每一个节点属性都是最大增益的属性,通过决策树就可以对数据进行分类。文献[10]对ID3算法设计的相关理论知识进行了详细的定义。这里只给出信息熵、属性每个取值的信息增益加权平均值和属性的信息增益的计算公式。
1)信息熵。面对数据集M,其所属分类有X1,X2,X3…Xn,数据集M划分到各类中的概率分别为P1,P2,P3…Pn。确定数据集的分类需要的信息熵公式为:
2)假设将条件属性Xn的数据集T划分为T1,T2,T3…Tn,这时该数据集下分类所需的各子集的信息熵的加权平均值公式:
3)则该条件属性Xn对数据集M的信息增益公式:
Gain(X,M)= H(M)- H(X,T) C4.5 算法是ID3 算法的一种改进算法,用信息增益率来选择属性,在树建造过程中进行剪枝,既能处理离散型属性又能处理连续型属性,还能对缺省数据进行处理[9]。
信息增益率定义为:
Gain_ratio(X,M)= Gain(X,M)/Split_Info(X,M) 其中,Gain(X,M)与ID3中的信息增益相同,而分裂信息Split Info(X,M)代表了按照属性X分裂样本集M的广度和均匀性。其中:
确定分裂指标是生成决策树过程中的关键。C4.5 算法中分裂指标确定的基本思想是比较各训练样本数据中属性信息增益率的大小,取其中信息增益率最大的但又不低于所有属性平均值的属性作为树的一个分支节点。若存在连续的描述性属性,首先必须将该连续性属性分割为离散的区间集合,对其进行离散化处理。
1.2组合学习法
组合学习法将多个基分类器聚集在一起来构成组合分类器,用来提高分类准确率。理论研究和实验表明,样本数据集相同时,组合分类器的分类准确率和泛化能力往往高于单个分类器。根据分类器组合的形式,可分为四种[11]:第一种为串行方式,分类器组合方式为将一种分类器的输出作为另一种分类器的输入。第二种为并行方式,用一种算法将不同的分类器的输出结果进行整合,最后输出分类结果。这种方式第三种为嵌入方式,将一种分类器在分类过程中嵌入另一种分类器算法来提高分类精度,这种方法会显著提高原分类器的性能。第四种为混合方式,将上述3 中方式混合。为了算法上的快速性,本文采用并行的方式。
装袋(Bagging)是目前构建组合分类器使用最多的方法。Bagging对于有限样本组成的训练集S,通过Bootstrap过程生成测试样本Si,以Si为训练集分别构建分类器Ci,测试样本时分别用各基分类器对样本x进行预测,依据{C1,C2,C3...Cn}的综合投票结果,确定测试样本x的类别。由于放回抽样,每次抽样都是独立的,因此Bagging是一种并行训练的组合方法。
2基于Bagging的分区决策树组合分类器
论文[12]提出了一种动态分区方法。分区算法根据获得的环境信息,把复杂的不规则的不确定的区域分割成若干个子区,最终返回的数据是每个子区的序号、起点、终点和子区的个数。文中根据此算法对地面目标运动区域进行分区。
Bagging是集成学习实现的途径之一:基于样本采样策略。它利用组合学习法将多个基分类器集成到一个强分类器。由于Bagging采样使得各数据集相互独立,在此基础上形成多个保证基分类器的多样性,具备很强的泛化能力和稳定性。本文采用分区的思想分区构建组合决策树。用Bagging来构建训练子集,用C4.5算法构建基分类器,各基分类器间采用多数投票机制进行组合构建组合决策树。其模型如图1所示。
模型中H为原始数据集。H1、H2...Hn是将H分区处理后的子数据集,分别从子数据集H1、H2...Hn中进行有放回的随机抽取,利用决策树C4.5算法构建n组基分类器。各分类器之间相互独立,所以可以采用并行的思想进行训练。每个分类器都可以得到一个结果,n个分类器的结果构成了一个函数系列,将这个序列多数投票机制投票,得票数最高的类别为最终组合模型的分类结果。组合分类器的投票结果Dn由下式决定。
式中以两类分类为例,X和Y表示输出结果的类别号。由上式可知,判定X和Y投票总数大小,组合分类器将输出类别号较大的作为判定结果。当投票总数相等时会出现判定为平局(equ)的不良结果。为了避免这种情况的发生,常采用奇数个分类器进行组合。
3组合分类器在多目标分类中的应用
3.1信息提取与处理
本文的样本数据集从仿真平台中得到。根据国际空中机器人大赛(IARC)比赛规则并且基于VC++与Open GL搭建仿真平台,仿真平台中在多目标运动区域创建二维坐标系,将其划分为四个分区,如图2 与图3 所示。通过仿真平台可以实时保存地面多目标的信息,包括位置,速度大小,速度方向,目标所在的象限,目标到边界的时间,目标反向的时间,目标是否安全等等。同时还可以得到移动障碍物的位置、速度大小和方向以及空中机器人的位置、速度大小和方向。通过仿真平台得到大量地面运动目标的位姿信息,由于相同模型下,样本数量越多,预测的准确率越高[13],本文从每个分区分别保存10000 条数据作为原始数据集。然后利用粗糙集属性约简等方法[14,15]去掉不相关属性,并将连续性属性划分为0-2PI之间的区间值。
为了使用组合决策树来进行多目标分类和预测,本文对选取了对目标到达边界时间有影响的7 个属性:地面目标位置、地面目标速度大小、地面目标速度方向、地面目标反向时间、地面目标到达边界时间,空中机器人的位置、空中机器人的速度大小。将这7个属性作为分类属性,将目标是否安全价作为类属性。根据决策树C4.5 算法构建的决策树模型可以得到基分类器。本文参考了文献的实验结果:基分类器的个数越多,模型的准确率越高。在样本数量确定的情况下分别构建7 个基分类器。
3.2仿真实验
分别将得到的7个基分类器采用Bagging进行组合,并且采用多数投票机制对基分类器预测结果集成输出建立多目标分类模型。将得到的分类模型添加到全仿真平台进行验证,测试数据集直接由仿真平台产生。由于,仿真持续进行,所以产生的测试数据集将会非常大,保证了测试数据集过小对是实验结果的影响。仿真过程中,如果地面目标都是安全的,则由四旋翼控制距离右边界最近的地面运动目标。如果地面机器人有危险的,则判断哪一个最危险,此时由四旋翼控制最危险的机器人,直到它们解除危险。某一次的仿真过程如图4、图5、图6、图7、图8、图9所示。仿真图中,黄色代表空中机器人。
由图5、6、7、8、9 可知,在48s,、147s、337s、447s、569s内,能够该方法能够判断10 个地面目标是否安全,并且在全部安全的情况下空中机器人始终跟踪距离右边界最近的地面运动目标。T=569s时,地面目标全部运动到场外,且只有一个没有从指定边界出界。空中机器人始终能够根据地面目标的状态进行判断并且跟踪控制地面目标。
3.3 实验数据
分别利用传统的决策树C4.5 算法和基于分区决策树组合分类器算法进行2000 次仿真实验。当仿真时间到达600 秒或者10 个地面目标全部出界之后仿真实验终止,记录此时的用时和地面目标出界个数。传统的决策树C4.5 算法仿真的得到的部分实验结果如表1 所示。基于分区决策树组合分类器算法得到的部分实验结果如表2所示。
3.4实验结果分析
由表13和表14可以看出,采用传统决策树C4.5算法,空中机器人对地面目标的控制率最高为70%,平均值为63%左右。采用分区决策树组合分类器算法空中机器人对地面目标的控制率达到89%,部分实验中空中机器人都能在规定的时间以内将所有的地面目标从右边界赶出。实验结果表明,相对于传统决策树C4.5算法,分区决策树组合分类器算法能够对多目标快速分类,分类精度更高,提高了空中机器人对地面多运动目标的控制率。
4 结束语
使用C4.5 算法构建分区决策树不仅使用地面目标属性作为决策树节点,而且将空中机器人的位置和速度等属性作为决策树的节点,不仅将地面目标和空中机器人结合,而且提高了决策树的分类精度。构建的组合分类器具有很强的泛化能力,能够准确快速地实现地面运动目标的分类和预测。空中机器人在分类结果的基础上进行分析,能够快速跟踪并且控制地面运动目标。该方法避免了四旋翼在场地中盲目的飞行,缩短了搜索时间,提高了四旋翼的控制率。
摘要：针对地面有多个无规则运动的目标时,空中机器人很难判断跟踪哪一个的问题,提出一种基于分区决策树组合分类器的地面多目标分类方法。该方法对原始数据集分区处理,分别通过Bagging采样策略形成不同子数据集,利用C4.5经典算法构建基分类器,并用多数投票机制对基分类器预测结果集成输出,分区构建多目标分类模型。仿真表明相对于传统的C4.5算法,该方法能够快速实现地面多运动目标分类,提高空中机器人对地面运动目标的跟踪控制率。
“三分类三升级”典型培树工作方案 第2篇
“三分类三升级”典型培树工作方案
为充分发挥先进典型的示范带动作用，引导全镇广大基层党组织积极投入到创先争优活动中来，推动活动扎实深入开展，按照上级相关文件要求，经镇党委研究决定，制定本工作方案。
一、总体要求
按照“五好四强”标准要求，选树一批具有鲜明时代特征、广泛群众基础、强烈感召力的先进典型，使广大基层党组织学有榜样、做有标尺、干有方向，着力营造崇尚先进、积极向上、争创一流的工作氛围，提升全镇创先争优活动效果。
二、培树原则
（一）坚持近期与长期相结合。要树立近期目标和长期规划，培树的典型即要符合发展需要和时代特点，又要经受得住群众的检验和时间的考验，使其不但能发挥近期效果，又能发挥远期效应。
（二）坚持老典型与新典型相结合。即要注重挖掘受过上级表彰的一批老典型，又要注重培树当前农村党建和经济工作中涌现出的一批新典型，并将老典型、新典型融合培树，使新典型继承老传统，老典型体现新特点。
（三）坚持晋级、晋职推树相结合。要分级别、分层次、分专业学科打造和培树典型，对每个典型提出具体推进措施和时限。在规范发展的基础上要全力培树几名在全镇及到全县创先争优工作的影响力。
三、培树目标
（一）全镇培树典型要点基层党组织总数的20%以上，优秀党支部先进典型达到党员总数的10%以上。
（二）2011年7月前精心培植5个优秀基层党组织典型，在全镇宣传报道，提升典型的影响力。
（三）2011年12月前精心打造2个优秀基层党组织典型，向县级以上进行推树，进行重点宣传。
四、培树步骤
典型培树工作要抓好四个步骤，一是树立初步典型。经组织推荐、群众评议、上级审核，初步确定一批典型，采取先进典型述职、组织参观学习等形式，扩大典型影响力。二是搞好对标定位。所有基层党组织，对照本本单位的先进典型，对照工作标准，查找自身差距，明确努力方向，制定跟进、赶超的具体措施。三是实施晋档升级。对照创先争优标准，着眼全面提升，把典型进行逐级推树，使处于先进的当好标杆、中间状态的规范提高、相对后进的改变面貌。四是强化舆论宣传。要充分发挥信息、简报、广播、网络的作用，大力宣传优秀党支部典型，引导广大党支部以先进典型为榜样，努力在全镇形成学先进、比先进、争当先进的良好风气。
五、培树措施
（一）定量培树典型。根据典型培树的目标，合理划分典型培树比例和数量，按照比例要求及“五好”的创争标准，认真发现挖掘一批既体现优良传统，又能展示时代风彩的先进典型，做到及时发现、及级推荐。对发现的先进典型要深入走访，认真筛选，严格把关，真正把具有代表性、典型性和宣传价值的先进典型作为动态考察和精心
培植的对象，并将典型培树名单逐级上报。
（二）专人提炼典型。争创办公室人员为推树活动信息员，采取一对一的形式，对典型党支部进行跟踪培树，并将“一对一”名单层层上报，落实责任。信息员要重点做好先进典型事迹编写工作，要抓住先进典型的精神实质和闪光点，深入挖掘动人故事和感人细节，努力把先进人物写活，把先进事迹写实，把先进经验写透。要善于用鲜活具体的事实和真实客观的数据，以群众的视角和审美观点来表现典型，用平实的语言阐释深刻道理，用鲜活的事例揭示事物本质，使先进典型鲜活生动、真实丰满、可信可学，增强吸引力、感染力和影响力。
（三）定向突破典型。做好基层党组织表彰情况调查摸底工作，立册建档，把受到上级各种表彰的党支部做为推树初步典型的重要依据和考评条件，并根据实际情况确立推树重点。逐一拟定具体推树方案，实施定点定向推树突破。
（四）工程提升典型。实施建设“旗帜工程”，开展“树标杆、争一流、夺红旗”活动，做为培树典型的有力抓手，全力推进。要按要求和标准打造亮点工作，推进党建工作创新，在整体示范的基础上求工作创新，把党建示范点全部打造成创先争优工作典型。
（五）定期宣传典型。培育选树典型，其出发点和落脚点在于推广和应用。要在典型宣传推广上实现“由内而外、做大做强”，保持选树典型的生命力，增强典型辐射效果，突出典型示范性。一是实行专栏宣传。各级党组织要以信息简报、固定标语、宣传栏等形式强化活动宣传。二是实行媒体宣传。开辟专栏、专版、专题对先进事迹、典型做法、成功经验进行宣传报道。三是实行活动宣传。通过举办演讲
比赛、征文大赛、文艺演出、工作汇报会等活动，不断拓展典型宣传的途径和手段。要精心组织形式多样、内容丰富的“学典型、赶典型、超典型”主题实践活动，确保典型宣传形成规模、形成声势。
六、组织领导
（一）加强领导，落实责任。高度重视，精心组织、科学安排、周密部署培树宣传先进典型工作，制定实施方案，扎实工作举措，落实专人负责，明确工作责任。要立足长远，注重谋划，不断提高发现、培植、总结、宣传先进典型的能力。
（二）把握标准，注重成效。要牢牢把握“先进性、时代性、群众性、客观性”的标准要求，以科学严谨的态度，高度负责的精神深入一线，广泛听取广大群众意见，切实选好、选准典型，确保先进典型培树工作健康有序推进。
分类树方法 第3篇
关键词：决策树,光谱信息,空间纹理
引言
遥感信息的提取与分类是遥感影像分析与应用的重要内容。传统遥感图像分类方法有监督分类与非监督分类[2];近年较新的遥感图像分类比如人工神经网络分类法、模糊分类法[3]和专家系统分类法[4]等都是以遥感影像的光谱特征为基础的。但遥感影像本身存在“同谱异物, 同物异谱”的现象, 这些仅依赖于光谱特征的分类方法往往会导致遥感影像的错分或漏分, 从而降低遥感影像分类精度[5]。
决策树分类方法是一种基于空间数据挖掘来获得分类规则的方法, 数据挖掘 (Data mining, DM) 是从大量的、不完全的、模糊的、随机的数据中, 提取隐含其中的、人们不知道的、具有潜在利用价值的信息和知识的过程[6], 决策树分类方法能够有效地将遥感影像中的光谱信息和空间纹理信息结合, 并借助现有的土地、植被和水体等土地类型的分类知识对影像进行土地类型分类。本文尝试基于决策树分类方法之上, 结合光谱特征提取值和纹理信息特征提取值对Landsat5 TM影像进行分类, 并将分类结果与运用最大似然法的监督分类结果进行对比分析。
1 研究区概况与数据来源
尤溪县是福建省三明市下辖的一个县, 位于三明市东部, 北纬2 5°5 0′~2 6°2 6′, 东经117°48′~118°39′, 总面积3425.3平方千米, 属中亚热带季风性湿润气候。夏季暖热, 冬季温凉, 春夏多雨, 降水丰富。地处闽中、戴云山脉以北, 境内山岭耸峙, 丘陵起伏, 山峰林立, 盆地错综;中部河谷斜贯南北。全县区位优势明显, 资源丰富、交通便利。
本研究采用的数据有:福建省尤溪县梅仙镇2006年Landsat5 TM影像和ASTER影像、梅仙镇GPS野外实测样本点数据。
2 原理与方法
2.1 光谱信息特征提取
遥感图像中的光谱特征是反映地物本身物理属性的基本特征, 常用的光谱特征提取方法有代数运算法、导数法和变换法[1]。本文利用波段间的比值消除地形和光照等影响, 利用NDVI (归一化植被指数) 和NDWI (归一化水体指数) 分别对植被和水体进行特征提取。NDVI (归一化植被指数) 反映了植被光谱的典型特征, 部分消除大气程辐射和太阳-地物-卫星三者相对位置 (遥感几何) 的影响, 增强了对植被的响应能力, 具有简易操作的特点, 是目前应用最广的植被指数[7]。NDWI (归一化水体指数) 反映了水体光谱的典型特征。
2.2 纹理信息特征提取
由于研究区域山地居多, 地形崎岖, 目视解译工作难度大。同时, 分类结果因遥感图像本身的空间分辨率以及同物异谱和异物同谱现象的大量存在, 会有较多的错分、漏分情况出现, 也导致分类精度降低。为此, 许多专家学者进一步引入纹理特征, 以增强不同地物的可识别性。
纹理特征是一种不依赖于物体表面色调或亮度的、反映图像灰度的空间变化情况, 表现为平滑性、均一性、粗糙性和复杂程度[1]。纹理特征提取的主要方法是基于灰度共生矩阵的纹理特征提取方法, 利用的是纹理特征的局部随机性和整体统计规律性的特点。对于遥感图像来说对比度 (contrast) 、熵 (entropy) 、逆差矩 (homogeneity) 和相关性 (correlation) 等统计量效果最好[8]。本文以ENVI为平台, 先对试验区遥感影像进行主成分分析, 有效去除噪音和冗余, 取变换后的第一主成分分量;再根据灰度共生矩阵纹理提取方法对影像进行纹理分析, 得到对比度 (contrast) 、熵 (entropy) 、逆差矩 (homogeneity) 和相关性 (correlation) 纹理特征图像。
2.3 DEM
DEM即数字高程模型, 是一定范围内规则格网点的平面坐标 (x y) 及其高程 (z) 的数据集, 它主要是描述区域地貌形态的空间分布, 是通过等高线或相似立体模型进行数据采集 (包括采样和量测) , 然后进行数据内插而形成的, 是对地貌形态的虚拟表示, 可派生出等高线、坡度图等信息。由于试验区分布着大量低山丘陵, 林地与耕地较难区分, 林地主要分布在低山丘陵地区, 与耕地在高程上有明显差异, 所以尝试利用DEM将林地从植被中区分出来。
2.4 决策树分类
决策树分类法突破了以往分类树或分类规则的构建要利用分类者的生态学和遥感知识先验确定, 其结果往往与其经验和专业知识水平密切相关, 决策树分类过程中能够利用GIS数据库中的地学知识辅助分类[5], 将数据分割为特征更为均质的子集, 简化了计算过程, 提高了分类精度。本文采用的是二叉树结构, 二叉树除叶子节点之外, 每个节点都有两个分支。在分类过程中, 可以将复杂的问题转化成多级两类分类问题。在每个节点Ni处, 分类器都把样本集分为左和右两个子集, 每一部分可能依旧包含着多类别的样本, 需要把每一部分再划分成两个子集, 以此类推, 直到所分成的每一部分只包含同一个类别的样本, 或某一类样本占优势而不可再分为止[9]。
3 分类过程
3.1 最大似然法分类
本文采用监督分类中最常见的最大似然分类结果作为对照, 通过选择训练样区和定点考察, 进行监督分类, 分类结果见图1, 并进行分类后结果精度评价, 见表1。
3.2 基于决策树分类
根据梅仙镇的实际情况并结合实地采样结果, 土地类型划分为水体、林地、农田、建设用地和裸地及工矿用地五类。根据实地考察结果, 针对各土地类型选取相应的训练样区, 分别进行最大值、最小值、均值和方差统计, 在结合QUEST决策树算法的基础上, 集成影像光谱信息、空间纹理信息和DEM等数据于一体的多源数据确定决策树分类规则, 见图2。通过ENVI4.8软件平台运行决策树, 分类结果见图3, 分类后, 用精度验证训练样区进行精度评价, 见表2。
4 结果与分析
由于遥感影像的复杂性, 经常存在同物异谱和同谱异物的现象, 为了准确区分光谱特征相似的目标地物, 需结合影像的纹理信息以及其他有效辅助信息。基于光谱特征和纹理特征的决策树分类方法, 实现了对Landsat5 TM遥感影像的数据挖掘, 获取了更多分类参考信息, 分类精度达到了93.93%, 相比最大似然法, 精度提高了2.70%, 其中基于决策树的分类方法对于林地和建设用地分类的提升较为明显, 但是受同谱异物影响, 在研究裸地及其工矿用地时, 存在明显的缺陷, 分类精度低, 若能够结合更多的光谱信息和空间纹理信息等辅助数据, 并能够对结果进行分类后处理, 将进一步提高决策树分类的精度。
参考文献
[1]黄立贤, 沈志学.基于决策树的landsat多光谱影像分类方法.光电技术应用, 2011 (6) :49-51
[2]梅安新, 彭望, 秦其明, 等.遥感导论[M].北京:高等教育出版社, 2001
[3]王圆圆, 李京.遥感影像土地利用/覆盖分类方法研究综述[J].遥感信息, 2004 (01) :53-59
[4]肖鹏峰, 刘顺喜, 冯学智, 等.中分辨率遥感图像土地利用[J].国土资源遥感, 2004 (4) :41-45
[5]翁中银, 何政伟, 于欢.基于决策树分类的地表覆盖遥感信息提取2012 (4) :110-111
[6]史忠植.知识发现[M].北京:清华大学出版社, 2002:22-45
[7]沙晋明.遥感原理与应用.北京:科学出版社, 2012
[8]Benediktsson J A, Sveinsson J R, Kolbeinn Areas.Classi—fication and Feature Extraction of A, IRIS Data[J].IEEETransaction on Geoscience an d Remote Sensing, 1995, 33 (5) :1194-1205
分类树方法 第4篇
决策树分类作为一种基于空间数据挖掘和知识发现的监督分类方法, 能自动选取特征并融入影像以外的各种知识, 有效地将各种用于植被、水体和土地的分类知识以及空间纹理信息结合起来, 已经开始应用于各种遥感影像信息提取和土地利用、土地覆盖分类中[4,5]。尝试利用决策树分类法对Landsat TM影像进行分类, 并将分类结果与最大似然法和仅利用光谱特征的决策树分类结果进行对比分析。
1 原理与方法
多光谱图像特征在分类和信息提取过程中能起到至关重要的作用。文中在提取多光谱图像的光谱维特征和纹理特征的基础上, 采用决策树法进行遥感影像分类试验。
1.1 光谱维特征提取
遥感图像中的光谱特征是反映地物本身物理属性的基本特征, 常用的光谱特征提取方法有代数运算法、导数法和变换法。对于植被、水体和建筑特征提取, 利用波段间的比值消除地形和光照等影响, 真实地反映地物覆盖情况, 通过阈值分割可较精确地提取出地物信息, 常用的模型有归一化植被指数模型 (NDVI) 、归一化差异水体指数模型 (NDWI) 和归一化建筑指数 (NDBI) [6]
1.2 纹理信息特征提取
各种地物中, 水体和林草地能够利用光谱信息较好地与其他地物区分开, 而建筑物和未利用地的光谱值比较相似, 仅靠光谱特征很难将这些目标地物准确提取出来, 所以需要纹理特征参与分类。纹理特征是一种不依赖于物体表面色调或亮度的、反映图像灰度的空间变化情况, 表现为平滑性、均一性、粗糙性和复杂程度。纹理特征提取的主要方法是基于灰度共生矩阵的纹理特征提取方法, 利用的是纹理特征的局部随机性和整体统计规律性的特点。对于遥感图像来说对比度 (contrast) 、熵 (entropy) 、逆差矩 (homogeneity) 和相关性 (correlation) 等统计量效果最好[7]。
用于影像分类的纹理特征提取过程为先对试验区遥感影像进行主成分分析, 取变换后的第一主成分分量;再按照灰度共生矩阵纹理提取方法, 确定大小为33的窗口, 对变换后的影像进行纹理分析, 得到对比度、熵、逆差矩和相关性纹理特征图像.
1.3 决策树分类
决策树 (decision tree) 是通过对训练样本进行归纳学习, 生成决策树或决策规则, 然后使用决策树或决策规则对新数据进行分类的一种数学方法。决策树是一个树型结构, 它由一个根节点、内部节点及叶节点组成, 每一个节点有一个父节点和两个或者多个子节点, 节点间通过分支相连。决策树的每个内部节点对应一个非类别属性或属性的集合, 每条边对应该属性的每个可能值。决策树的叶结点对应一个类别属性值, 不同的叶结点可以对应相同的类别属性值[8,9]。
2 分类过程
采用的数据是Landsat-7多光谱影像, 影像覆盖区位于福建省厦门市, 影像的彩色合成图 (TM5、TM4、TM2) 如图1所示。针对地区的实际情况并结合地物的特点, 地物类型划分为水体、林草地、建筑用地和未利用土地四大类, 其光谱响应曲线如图2所示。根据各类地物光谱特征差异, 对每一种地物选取一定的样本, 测定各地类的光谱值, 进行最大值、最小值、均值和方差统计, 综合运用阈值法, 可将地物目标自动提取出来。对于光谱混淆的地物类型, 比如建筑用地和未利用地, 利用其纹理特征的差异, 采用纹理分析辅助识别方法, 可大大提高影像分类精度。
基于光谱图像的光谱维特征和纹理特征进行遥感影像分类试验, 分类流程如图3。
3 结果与分析
运用决策树分类得到分类结果如图4所示, 并利用最大似然法对影像分类作为对比, 结果如图5所示。
为了评价该分类方法的结果, 利用相同的训练样本和检验样本, 以及传统的有监督最大似然分类结果和决策树分类结果 (如图6所示) 进行比较, 建立混淆矩阵[10], 计算各类分类方法的总精度以及Kappa系数, 见表1。从评价的结果可以得出, 采用光谱特征与纹理特征结合的决策树分类法分类精度高于传统的最大似然法和决策树法。
4 结论
由于遥感影像的复杂性, 经常存在同物异谱和同谱异物的现象, 为了准确区分光谱特征相似的目标地物, 需结合影像的纹理信息以及其他有效辅助信息。基于光谱特征和纹理特征的决策树分类方法, 实现了Landsat-7遥感影像的地物分类, 分类精度达到了93.86%, 相比最大似然法和基于光谱特征的决策树法, 分类精度分别提高了7.086%和5.271%。研究若能够综合利用更多的图像信息和光谱信息, 在后续的子分类中加入其他分类方法, 将能进一步提高影像分类的精度。
摘要：构建了一种结合光谱特征和纹理特征的多光谱影像决策树分类方法。以Landsat-7影像作为试验数据, 通过分析Landsat-7影像的光谱特征值及NDVI、NDWI和NDBI特征值, 确定各类地物的综合阈值, 同时运用灰度共生矩阵对影像进行纹理信息提取, 得到对比度、熵、逆差矩和相关性等纹理特征图像。在此基础上, 运用决策树分类法对Landsat-7影像进行分类。结果表明, 结合光谱特征和纹理特征的决策树分类方法, 相比传统的最大似然法和决策树法, 具有更高的分类精度。
关键词：多光谱影像,决策树分类,纹理特征,光谱特征
参考文献
[1]赵英时.遥感应用分析原理与方法[M].北京:科学出版社, 2003.
[2]张良培, 张立福.高光谱遥感[M].武汉:武汉大学出版社, 2005.
[3]LI Shu, LIU Yong.Land use cover classification of re motely sensed imagery based on multi-features at the southeastern marginal area of the Tengle Desert[J].Re mote Sensing Technology and Application, 2006, 21 (2) :154-158.
[4]杨朝辉, 陈鹰, 邵永社, 等.基于多尺度空间的图像匹配算法[J].光电子·激光, 2009, 20 (6) :826-829.
[5]LIU Yong-hong, NIU Zheng, WANG Chang-yao.Re search and application of the decision tree classification using MODIS data[J].Journal of Remote Sensing, 2005, 9 (4) :405-412.
[6]杨国鹏, 余旭初, 刘伟, 等.面向高光谱遥感影像的分类方法研究[J].测绘通报, 2007 (10) :17-20.
[7]Benediktsson J A, Sveinsson J R, Kolbeinn Arnas.Classi-fication and Feature Extraction of AVIRIS Data〔J〕.IEEE Transaction on Geoscience and Remote Sensing, 1995, 33 (5) :1194-1205.
[8]李金莲, 刘晓玫, 李恒鹏.SPOT5影像纹理特征提取与土地利用信息识别方法[J].遥感学报, 2006, 10 (6) :926-931.
[9]Bor-Chen Kuo, David Landgrebe.Improved Statistics Estimation and Feature Extraction for Hyperspectral Da-ta Classification[P].Ph D Thesis and School of Electri-cal&Computer Engineering Technical Report TRECE01-6, December, 2001:88.
分类树方法 第5篇
随着现代软件产业的发展,软件规模不断扩大,其内部逻辑也变得更加复杂[1]。为了保证软件的质量,软件测试环节在软件生命周期中占据非常重要的地位,但仍然不可能彻底消灭软件中所有的逻辑缺陷。模糊测试通过向目标系统提供非预期的输入并异常监视结果发现软件漏洞,是安全检测和漏洞挖掘的有效方法,也是近年来信息安全领域的研究热点之一。网络协议模糊测试发现的漏洞通常具有非常高的危险程度,所以被认为是多数安全研究者最感兴趣的模糊测试类型[2]。在模糊测试的过程中,模糊测试数据生成和异常监视这两个关键环节需要研究者给予特别关注。本文对网络协议模糊测试用例生成方法[3]进行研究。
1 启发式网络协议模糊测试用例生成方法
1.1 网络协议分类树的构建过程
一棵网络协议分类树可以用五元组PT=(P,F,A,V,R)表示。其中根节点P代表测试目标网络协议;F代表目标网络协议的协议域,F={field}1,field2,field3,…,fieldn;A代表协议域互不相交的属性,
1.2 网络协议模糊测试数据生成过程
基于分类树的网络协议模糊测试数据生成过程可以概括为四个步骤:
(1)选定测试目标网络协议P,并根据其规范划分得到协议域集合F={field1,field2,field3,…,fieldn},该目标协议可以用n元序组<field1,field2,field3,…,fieldn>表示。
(2)针对步骤(1)中得到的每个协议域的属性进行分类,得到描述协议域fieldi的属性集合,其中每个属性attributeij分别在离散的属性值集合Vij中取值(1≤i≤n,1≤j≤mi)。
(3)对每个协议域fieldi不同属性的属性值进行相互组合,得到面向该协议域的测试数据集合
(4)依次从面向协议域fieldi的测试数据集合Si中取值,对描述目标协议的n元序组<field1,field2,field3,…,fieldn>进行展开,得到面向目标网络协议的测试用例。
1.3 启发算子在网络协议分类树中的引入
启发式网络协议模糊测试用例生成方法基于分类树的网络协议模糊测试数据生成过程中加入了启发算子的定义,利用启发算子演变得到启发式规则,用于指导每个协议域的测试数据生成过程[4]。
结合文中给出的基于分类树的网络协议模糊测试数据生成的具体过程,需要在步骤(2)中增加获取启发算子的操作,用于对协议域属性值集合Vij的精简。由于应用启发算子后并未对步骤(1)产生影响,而且该步骤的实现难度比较小,通常只需要对协议规范进行解读便可以获取用于描述目标协议的n元序组<field1,field2,field3,…,fieldn>。
启发算子(Heuristic Operator)的定义可以用映射关系fh:Vij→V*ij描述。启发算子的定义可以源于协议分类树中父节点与子节点之间的关系集合R,也可以源于对目标网络协议的协议规范分析,或者可以借助第三方工具进行提取[5]。
1.4 启发式网络协议模糊测试用例生成过程
启发式网络协议模糊测试用例生成过程需要利用启发算子h实现协议域属性值集合的精简,为了方便具体的实现过程,可以把启发算子写入相应的配置文件[6]。
在配置文件启发算子定义的基础上可以演变得到形如“if…,then…”的启发规则,用于剔除属性值集合Vij中的无效值,从而得到精简的属性值集合V*ij。
面向协议域fieldi的测试数据集合Si的生成过程可以视作协议域的属性值集合,进行笛卡尔乘积运算的过程,即
任取mi元序组<mutatedvalue1,mutatedvalue2,…,mutatedvaluem1>∈Si*,对n元序组<field1,field2,field3,…,fieldn>中的协议域fieldi进行替换,得到面向目标协议的一个测试用例,直至遍历完每个协议域的测试数据集合。至此,得到面向测试目标网络协议的测试用例的总数为
2 模糊测试用例生成方法的实现
2.1 验证平台网络协议模糊器的选取
根据各网络协议模糊器与验证平台选取标准的匹配结果可知,模糊器Peach和Sulley相对于SPIKE而言,更加符合本文对验证平台的选取标准。考虑到模糊器Peach相对于Sulley而言对测试执行前的准备工作要求更为简单,而其维护更新情况更加频繁,最终选取模糊器Peach作为启发式网络协议模糊测试用例生成方法的验证平台。
2.2 启发式网络协议模糊测试用例生成
2.2.1 目标协议与实施方案的选取
根据每个请求与之前的请求是否相关,可以把网络协议分为无状态协议(Stateless Protocol)和有状态协议(Stateful Protocol)[7]。无状态协议是指网络协议的相邻数据包之间没有上下文的关联性;有状态协议是指相邻的数据包之间具有上下文的关联性。
在实际运用中,有状态协议比无状态协议的应用更加普遍。本文选取有状态协议的典型代表FTP协议作为目标协议,对启发式模糊测试用例生成方法进行实例验证。FTP协议采用客户端/服务器的工作模式,在现实世界具有极为广泛的应用,选取FTP作为模糊测试目标协议不仅具有普遍的现实意义,同时还能与本文对启发式模糊测试用例生成方法的描述结合起来,避免出现针对相同步骤的多次重复分析[8]。
从客户端连接远程FTP服务程序的过程可以分为建立连接、传送数据、释放连接三个阶段,具体的通信过程可以描述为:
(1)首先建立TCP连接,客户端向FTP服务器发送USER命令表明身份;
(2)然后服务器要求客户端输入密码,客户端发送PASS命令将密码发送给服务器,服务器对客户端进行身份认证;
(3)身份认证通过后客户端可以传输其他FTP命令进行文件操作,需要结束此次连接时用QUIT命令退出。
FTP客户端与FTP服务器进行通信的过程中,首先生成一个TCP虚拟连接用于验证控制信息,然后再生成一个单独的TCP连接用于数据传输。具体如图1所示。
2.2.2 目标协议分类树的构建
FTP命令可以表示为三元序组<field1,field2,field3>,协议域集合FFTP={field1,field2,field3}。为了简化处理过程,本文不再针对FTP命令三个协议域的各自特点进行研究,在划分过程中做相同处理,得到内容和长度两个属性,即三个协议域field1,field2,field3均可以用二元组(内容,长度)进行描述。也就是说,attribute11=attri-bute21=attribute31=内容,attribute12=attribute22=attribute32=长度,那么不难得到三个协议域的属性集合A1=A2=A3={属性,长度}。
2.2.3 启发算子的抽取与启发规则的定义
文中选取FTP作为目标协议对启发式网络协议模糊测试用例生成方法进行验证,实现启发算子的提取和定义之前,需要首先对FTP协议传输过程中的数据单位信息有所了解[9]。在计算机网络中,对等层之间传递的数据单位称为协议数据单元(Protocol Data Unit,PDU),OSI七层参考模型中的各层协议数据单元具体如表1所示。
目标协议FTP属于OSI七层参考模型中的应用层协议,其协议数据单元是数据(Data),针对FTP协议的测试需要依托利用FTP协议进行通信的程序完成。本文借助IDA Pro工具实现针对测试目标程序的启发算子的提取。利用IDA Pro工具提取启发算子的具体操作步骤示意图如图2所示。
2.2.4 利用启发算子指导测试数据的生成
启发式网络协议模糊测试用例生成方法中,启发算子的引入是为了减小测试用例生成过程的搜索空间,实现网络协议模糊测试用例生成过程的优化[10]。启发算子配置文件constant List.conf和func List.conf与具体的启发规则之间的关系如图3所示。
在验证平台模糊器Peach完成对启发算子配置文件的处理之后,就可以开始利用具体的启发规则指导协议域测试数据的具体生成过程。启发式的协议域测试数据由格式化字符串、普通字符串、整型值、不同编码方式的字符串四个部分组成。
3 网络协议模糊测试用例生成方法的验证
3.1 模糊测试方案与环境要求
启发式网络协议模糊测试用例生成方法的实例验证过程在Windows操作系统环境下进行。利用模糊器Peach2.3.8源码在Windows平台下执行模糊测试所依赖的工具或者库,主要包括网络封包抓取工具Winpcap、调试工具Windbg、Python扩展等,要求在测试开始之前完成相应的安装准备工作。
测试实施方案示意图如图4所示。从图4中可知,模糊器Peach扮演客户端的角色对FTP服务端程序的安全性进行测试,而模糊器所集成的监控模块在测试过程中用于收集测试目标的行为并分析判断测试目标是否出现异常。
鉴于Open⁃FTPD1.2存在已知的安全漏洞,更适合作为模糊测试效果实例验证的测试目标程序。采用该FTP服务端程序作为测试目标程序,在模糊器Peach的平台上对启发式网络协议模糊测试用例生成方法的有效性进行验证。考虑到模糊测试的执行时间,实例验证过程只选择FTP命令中最常用的USER命令进行测试,以简化测试环节的处理。
利用模糊器Peach开始测试前,首先需要针对FTP服务端程序Open⁃FTPD定义相应的Pit文件openftp.xml,从而构造出完整的模糊器。Pit文件中Data Model元素用于对数据模型进行定义,包括数据结构和数据关系等,一个Pit文件中可以定义多个数据模型。
Pit文件中的Test元素用于定义测试配置信息,用于指定测试中所用的状态模型State Model,Publisher等信息。其中状态模型用于描述如何与目标程序进行通信,而Publisher用于定义模糊器Peach的I/O连接,构造网络协议数据流或者文件流等。
Pit文件中的Agent元素用于定义代理和监视器信息,指定模糊器Peach在测试执行过程中用于监视测试目标程序异常的调试器。每个Pit文件中可以定义多个Agent元素,每个Agent元素中可以定义多个Monitor。
3.2 实验验证与结果分析
3.2.1 模糊测试效率分析
利用模糊器Peach的语法命令“peach⁃cpeach_xml_file[run_name]”分别对应用启发式模糊测试用例生成方法前后所生成的测试用例数量进行计算。根据运行结果可知,改进前的测试用例为12 966个,而改进后的数量减少到2 532个,仅为原有测试用例总数的19.5%,证明启发式模糊测试用例生成方法有效地减少了用例生成的总数量。
模糊测试通过向目标程序注入大量的畸形数据试图发现测试目标中存在的漏洞,测试用例的数量直接关系到模糊测试的执行时间,亦即模糊测试的效率。根据实验结果可知,改进前的测试执行时间为10小时16分钟28秒,而改进后的执行时间降低到22分钟16秒,仅为改进前的测试执行时间的约3.6%,显著提升了模糊测试的效率。
3.2.2 发现漏洞能力分析
针对Open FTPD1.2执行模糊测试在应用启发式模糊测试用例生成方法前后,均捕获到的漏洞包括Tainted Da⁃ta Controls Branch Selection和Tainted Data Passed To Function两种类型,证明改进后的测试用例的有效性并没有因为总数量的减少而削弱。
在能够触发测试目标程序异常的模糊测试用例数量方面,应用启发式模糊测试用例生成方法前模糊器Peach触发Tainted Data Controls Branch Selection异常的用例数量为2个,触发Tainted Data Passed To Func⁃tion异常的用例数量为18个。
应用启发式模糊测试用例生成方法前模糊器Peach触发Tainted Data Controls Branch Selection异常的用例数量为12个,触发Tainted Data Passed To Function异常的用例数量为22个。
改进前触发测试目标程序异常的测试用例总数为20个,占测试用例总数量的比例为20 12 966≈0.15%;改进后触发测试目标程序异常的测试用例总数为34个,占测试用例总数量的比例为34 2 532≈1.34%,有效测试用例的比例约为改进前的9倍,证明了启发式模糊测试用例生成方法的有效性。
3.2.3 测试用例详细分析
针对应用启发式模糊测试用例生成方法前后的有效测试用例做详细比较,可以把改动前后有效测试用例的存在情况分为三种情况,具体如表2所示。
4 结论
本文在启发式搜索算法和分类树思想的基础上提出了启发式网络协议模糊测试用例生成方法,并对该方法的可行性和有效性进行了实例验证。文中对启发式网络协议模糊测试用例生成方法的研究仍然存在很多不足之处,目前尚未对OSI参考模型中其他层的网络协议进行具体实现与验证,需要在后续的研究过程中进行更加深入的探讨,在具体实现和实例验证的基础上总结提取启发式算子的常用方法。
参考文献
[1]李伟明,张爱芳,刘建财,等.网络协议的自动化模糊测试漏洞挖掘方法[J].计算机学报,2011,34(2):242-255.
[2]李卓君.一种新的协议安全漏洞检测方法[J].计算机安全,2012(7):79-82.
[3]张宝峰,张翀斌,许源.基于模糊测试的网络协议漏洞挖掘[J].清华大学学报(自然科学版),2009,49(z2):2113-2118.
[4]李玉,钱雪忠.启发式遗传算法求解两两组合测试用例集[J].计算机工程与设计,2011,32(5):1722-1724.
[5]潘晓英,陈皓.基于组织进化粒子群优化的测试用例自动生成[J].计算机应用研究,2012,29(6):2065-2067.
[6]田江,高炽扬,李亚伟.基于智能算法的测试数据自动生成模型研究[J].信息安全与技术,2010(11):27-29.
[7]崔应霞,李龙澍,姚晟.组合测试用例集的动态生成算法[J].电子科技大学学报,2011,40(7):612-619.
[8]黄玉涵,曾凡平,潘能刚,等.基于搜索算法的测试用例优化问题研究[J].小型微型计算机系统,2011,32(5):840-844.
[9]游亮,卢炎生.测试用例集启发式约简算法分析与评价[J].计算机科学,2011,38(12):147-150.
分类树方法 第6篇
关键词：懒惰式决策树,朴素贝叶斯,半懒惰式决策树算机
0引言
分类是数据挖掘和机器学习的一种非常重要的方法, 可以用来提取描述重要数据类的模型。分类是在已有数据集合的基础上学会一个分类函数或构造出一个分类模型 (即通常所说的分类器) 。该函数或模型能够给由属性集描述的未分类的实例指派最适合的类标签, 从而可以应用于数据分类和预测[1,2]。机器学习、数据挖掘、专家系统、统计学和神经生物学方面的研究者已经提出了许多的分类方法和技术, 例如, 懒惰式决策树、朴素贝叶斯方法[1,2]、贝叶斯网络[1,2]、双层贝叶斯[3]、决策树[4]、决策表[5]、K-最邻近以及支持向量机等等。众所周知, 没有一种分类方法在所有领域都是有效的。懒惰式决策树具有较高分类精确度[6], 决策树具有良好的可解释性[4], 从而使得这两种分类器模型逐渐成为机器学习和数据挖掘领域的研究热点。
本文仔细地分析了决策树和懒惰式决策树这两种分类模型的分类原则, 结合了这两者的长处, 从一种新的角度提出了一种新的分类模型Semi-LDtree。它生成的决策树的节点, 如普通决策树一样, 包含单变量分裂, 但是叶子节点相当于一个懒惰式决策树分类器。本文给出了Semi-LDtree分类模型的算法, 并实验比较了Semi-LDtree、weka包下的J48、懒惰式决策树和贝叶斯这四种分类器的分类精确度。
1决策树分类模型
分类方法中最为典型的是基于决策树的分类方法。它从训练集合中构造出决策树, 是一种有指导的学习方法。决策树的叶节点是类名, 中间节点是带有分支的属性, 该分支对应属性的某一可能值。最为典型的决策树学习系统是ID3, 它采用自顶向下分而治之的策略, 能保证构造出一棵简单的树。算法C4.5和C5.0都是ID3的扩展, 它们将分类领域从枚举型属性扩展到数值型属性[4]。
构建决策树最重要的是如何选择分裂属性。迄今为止已经提出了许多选择分裂属性的标准, 例如, 标准熵增益和增益比率, Gini索引, Kolmogorov-Smirnov度量, 基于Goodman-Kruskal关联索引等等。本文采用的是一种基于NBtree的思想[7]。对每一个候选属性划分当前节点的数据集合, 计算朴素贝叶斯分类器在分裂后的数据集合上的交叉验证精确度值的权重和。取精确度最大的属性作为最佳的分裂属性。
2懒惰式决策树与朴素贝叶斯的比较
朴素贝叶斯分类器是一种简单而有效的概率分类方法, 但是其“属性独立性假设”在现实世界中大多数数据集合上明显不成立, 从而使其分类性能受到限制;而懒惰式决策树分类器采用决策树思想和懒惰式分类思想, 从概念上为每一个待分类实例建立一棵“最优”的树, 不受属性独立性假设的约束, 在小一些的数据集合上, 其分类精确度十分高。大量实验表明:懒惰式决策树分类器在大多数数据集合上所得的分类精确度要比朴素贝叶斯分类器高, 但是朴素贝叶斯分类器在大多数据集合上的分类速度要比懒惰式决策树分类器快。
因此本文利用懒惰式决策树分类器代替仅仅预测一个简单类标签的普通决策树的叶子节点来建立半懒惰式决策树分类器:Semi-LDtree分类器。同时利用朴素贝叶斯分类器分类速度快的优点计算当前节点分裂后分类精确度的悲观估计, 来选择最佳的分裂属性。
3Semi-LDtree分类模型及算法
Semi-LDtree分类模型产生的分类器是一棵决策树, 它与普通决策树的不同之处在于它的叶子节点是一个懒惰式决策树。在训练阶段, 它利用训练实例集合递归迭代生成一棵决策树。当给定一个测试实例, 它从决策树根节点被分到一个叶节点时, 懒惰决策树开始学习, 学习完后给出了这个测试实例的类标签。
Semi-LDtree分类模型充分吸取了懒惰决策树在小的数据集合上分类精确度高这一优点, 同时保留了决策树良好的可解释性, 提高了分类速度和精确度。
本文提出的Semi-LDtree算法如下所示。这个算法类似于经典的C4.5算法, 采用的都是分而治之自顶向下迭代递归的策略。特别之处在于叶子节点是一个分类精确度高的懒惰决策树, 而不是仅仅预测一个简单类标的节点。
对于数值连续型属性的阈值的产生, 本文仍沿用J48提出的方法。首先将数据集合按照数值连续型属性排序选择多个分裂点。对每一个分裂点计算信息增益, 选择信息增益最大的分裂点作为阈值点[4]。
如何选择最佳的分裂属性, 本文采用的是对每一个候选属性划分当前节点的数据集合, 计算朴素贝叶斯分类器在分裂后的数据集合上的交叉验证精确度值的权重和, 记为AccW。取精确度最大的属性作为最佳的分裂属性[7]。
对于什么时候停止决策树的生长而生成相当于懒惰式决策树的叶子节点, 本文采用的是在当前节点上计算朴素贝叶斯分类器的交叉验证精确度 (记为Acc) , 当这个精确度大于给定的限制值, 或者这个精确度明显大于用属性分裂后的权重和精确度, 或者找不到最佳的分裂属性时, 停止决策树的生长, 否则继续在此节点上分裂。
Semi-LDtree算法:
输入:带有类标的训练数据集合;
输出:叶子节点是懒惰式决策树分类器的决策树。
1) 计算当前节点的Acc值;
2) 计算每个候选属性的AccW值, 选择一个AccW值最大的属性作为最佳的分裂属性;
3) 如果Acc值明显大于MAX (AccW) 值, 或者Acc值大于一个给定值, 或者当前节点的实例数目小于一个给定的值时, 生成叶子节点, 调用懒惰式决策树。否则按最佳属性分裂生成子节点。在每个子节点上递归建树。
4实验数据及实验结果分析
为了评估Semi-LDtree算法, 本文采用的实验数据集合都来自UCI的数据文件[8]。在所有的数据集合上评估分类器的性能所采用的方法都是十倍交叉验证的方法。在训练数据上建树的过程中本文删掉了那些类值缺省的训练实例。
实验的主要目的是对Semi-LDtree、J48、懒惰式决策树和贝叶斯分类器在每个数据集合上的分类精确度进行了比较。每个分类器的分类精确度是在测试集合上成功预测的实例占总实例的百分比, 采用的10重交叉验证估计分类器的精确度。每一个数据集合被分成十个没有交叉数据的子集, 所有子集的大小大致相同。分类器训练和测试共十次;每一次, 分类器使用去除一个子集的剩余数据作为训练集, 然后在被去除的子集上进行测试。把所有得到的精确度的平均值作为评估精确度, 即10重交叉验证精确度。在运行J48, lazytree和Naïve bayes三种分类器时候, 均采用的是默认的参数。实验结果如表1所示。
表1列出了Semi-LDtree, J48, lazytree和Naïve bayes这四种分类器在23个实验数据上分类精确度的对比。从实验结果可以看出, Semi-LDtree在大部分实验数据集上取得了最好的分类性能。在23个实验数据集合上, Semi-LDtree的平均分类精确度为82.5220;J48的平均分类精确度为81.5136;lazytree的平均分类精确度为81.4582;Naïve bayes的平均分类精确度为78.0976。对audio, lung-cancer, anneal, ttt数据集合, Semi-LDtree的分类精确度均比J48, lazytree和Naïve bayes分类器的精确度高。对audio, zoo, anneal, echocardiogram, weather, sonar, ttt数据集合上, Semi-LDtree的分类精确度均比J48高出许多。对于所有的数据集合, 因为Semi-LDtree分类器如果不构建决策树就相当于一个lazytree分类器, 所以它的分类精确度不会比lazytree分类器低。在audio, anneal, ttt, german, solarflare-m五个大数据集合上, Semi-LDtree体现了决策树的优势, 它的分类精确度比lazytree分类器的精确度高。
Semi-LDtree产生的决策树的节点数目明显少于J48产生的决策树的节点数目。例如, 对于数据集合anneal, J48生成了78个节点, 分类精确度为90.9800, 而Semi-LDtree只生成7个节点, 精确度却达到了92.5390;对于数据集合ttt, J48生成了142个节点, 分类精确度为85.0731, 而Semi-LDtree生成39个节点, 精确度却达到了92.5887。因此, 它比J48具有更好的可解释性。但是, Semi-LDtree的每个叶子节点的复杂度比J48要高。
在本文的实验中判断停止决策树生长的条件时, 精确度的界限值是0.95, 分裂前后精确度值的差本文采用-0.05, 叶子节点最少的实例数目是30。实际上, 这三个值的取值的变动均会引起Semi-LDtree分类器分类精确度的上下浮动。
5结论
懒惰式决策树分类模型从概念上为每一个测试实例建立一棵“最优”的决策树, 所以分类精确度高。但是, 在大的数据集合上, 它的分类速度慢、内存消耗大、易被噪声误导等缺点, 影响了它的分类性能。决策树分类模型, Semi-LDtree, 它生成的决策树的节点, 如普通决策树一样, 但是叶子节点相当于一个懒惰式决策树分类器。这种分类模型同时保留了普通决策树良好的可解释性和懒惰式决策树在小的数据集合上分类精确度高这两种优点。实验结果表明了它提高了分类速度和分类精确度, 在某些分类任务上它的分类性能经常性地胜过两者, 特别是在大的数据集合上。
在Semi-LDtree的实现中, 最佳分裂属性的选择标准是非常重要的。本文中采用的方法是比较每一个候选属性的交叉验证精确度值的大小来选择最佳的分类属性, 是否还有其它更好的分类标准, 是下一步研究的一个内容。另外, 在本文实验中判断停止决策树生长的条件时, 选用了三个参数。实际上, 对于不同的数据集合, 这三个值的取定也不同。是否有一个更好的判断停止决策树生长的标准, 这也是需要进一步研究的问题。
参考文献
[1]Han J, Kamber M.Data Mining Concepts and Techniques[M].San Francisco:Morgan Kaufmann Publishers, 2001:185-219.
[2]Mitchell TM.Machine Learning[M].McGraw Hill, 1997:112-140.
[3]石洪波, 王志海, 黄厚宽.一种限定性的双层贝叶斯分类模型[J].软件学报, 2004, 15 (2) :193-199.
[4]Simovici Dan A, Jaroszewicz Szymon.A Metric Approach to Building Decision Trees Based on Goodman-Kruskal Association Index[C].PA-KDD, 2004:181-190.
[5]Witten IH, Frank E.Data Mining:Practical Machine Learning Tools and Techniques with Java Implementations[M].Seattle:Morgan Kauf-mann, 2000.
[6]Friedman JH, Kohavi Ron, Yeogirl Yun.Lazy Decision Trees[C].AAAI-96, 1996:717-724.
[7]Kohavi R.Scaling up the accuracy of Na ve-Bayes classifiers:A deci-sion-tree Hybrid[C].In:Simoudis E, Han J, Fayyad UM, eds.Proc.of the2Int l Conf.on Knowledge Discovery and Data Mining.Menlo Park:AAAI Press, 1996:202-207.
基于决策树算法的客户分类模型研究 第7篇
数据挖掘的分类技术应用于研究CRM中客户分类方法的现象已经非常普遍, 特别是使用决策树算法来研究客户分类方法的比较多但是真正非常有效地解决客户分类问题的方法还没有实现。
1 客户分类过程的总体结构
CRM系统中的客户分类方法并不固定经过多年的CRM实践, 企业家及学者对客户分类的研究, 对客户进行分类管理的一般步骤做了如下总结:首先, 确定所有的客户群, 包括现有的和潜在的客户并搜集整理客户的相关信息;然后根据自身需求选择分类标准, 应用分类方法对所有客户进行分类;其次, 筛选出有发展潜力的客户, 分析客户特点并制定相应的CRM策略;最后, 监督管理CRM策略的实施。
研究了CRM中客户分类的总体过程, 按照数据挖掘中分类方法基本机理, 结合决策树
分类方法进行分类的一般过程, 决策树方法应用于CRM中客户分类管理的一般过程如下:首先产生对问题描述产生一般数据集进行训练, 然后在训练数据集上应用决策树分类算法产生分类规则, 最后应用分类规则进行分类。
2 一个改进的客户分类模型
分析CRM中客户分类的总体过程和决策树分类的总体过程, 结合决策树方法分类的过程中几个基本步骤, 给出一个基于决策树和匹配模型的客户分类模型。此模型在应用决策树方法分类之前, 进行有效的改进了的数据预处理生成训练数据集, 经过优化产生训练数据集然后结合分类算法应用于决策树分类模型;而从决策树提取规则之后, 经过评价规则的有效性, 生成决策规则矩阵应用于数理统计的匹配模型, 对现有的客户数据集进行分类。
2.1 数据预处理
基于线性代数理论和相关性分析的数据预处理方法, 在建立决策树之前先对客户数据进行预处理, 对数据集进行面向记录压缩[1]然后再采用相关分析方法, 取得分类的关键属性, 从而实现对数据集的面向属性压缩[1]。
2.1.1 面向记录压缩
为获得训练决策树的训练数据集, 我们将客户数据集m+x个客户的数据记录组成矩阵C, 矩阵C由向量组所构成, 分别代表客户记录中的一个元组。
由线性代数理论, 假设客户数据集A是一个m+x维的向量组, 是A中m个向量, 如果满足向量组线性无关且A中任意向量a都可以用向量组线性表示, 则称为向量组A的一个最大线性无关组[38]。向量组A的一个最大无关组的向量个数称为向量组A的秩。
所以只要从客户数据集A中取得m个记录组成向量组, 而且它是数据集A的最大线性无关组, 则客户数据集A中的任意一个记录a都可以由推出。
在客户数据集A中求出m+x个客户记录向量的秩, 设为R, 那么由线性代数的理论, 只要在R个记录中获得分类信息, 其它记录的分类就可以由这个R个记录的分类推出, 进而就可以对客户数据集进行分类预测。
这样只要抽取的R个客户记录满足客户数据集的最大无关组的定, 就可以这R个记录组成训练数据集, 以达到了减少客户分析的数量, 对训练数据集的获得的规模有一定的参考作用, 分类的效率也将提高。由抽取的R个记录产生的分类对剩余的记录分类是有效的。
2.1.2 面向属性压缩
设决定客户分类函数为Y, 有客户记录属性有m个。那么存在因变量Y和m个自变量构成的自变量集合, 为了研究因变量与自变量之间的统计关系, 观测n个样本点, 由此构成nm的观测矩阵。使用偏最小二乘法[2]在矩阵X中提取成分t1 (t1为的线性组合) , 要求t1能很好地代表X中的变异信息, 且与Y的相关度最大, 这样, t1尽可能好地综合了X的信息同时也对Y有最强的解释力, 在第一个成分t1被提取后, 实施X对t1的回归及Y对t1的回归, 如果回归方程已达到满意精度, 则计算可以终止;否则, 将利用X被t1解释后的剩余信息进行第二轮成分提取, 如此反复迭代, 直到能达到一个较满意的精度为止。若最终X共提取了k个成分t 1, , t k, 通过实施Y对t 1, , t k的回归, 然后表达成Y关于原变量的回归方程。
通过使用偏最小二乘法, 建立回归模型并在Matlab7.0中使用回归分析, 可以得到决定客户分类的K个关键属性组, 对于M个属性中的M-K个属性可以进行删除, 从而面向属性地对数据集进行简约, 结合决策树构建的方法, 可以有效地介绍决策树中的节点从而降低决策树构造的复杂度, 为构建决策树进行分类奠定了良好的基础。
2.2 应用分类匹配模型进行客户分类
由决策树生成的决策规则形成一个知识库, 将客户数据中的客户记录经过模式化成一定长的字符串, 即特征串, 然后将客户数据集中字符串与知识库中知识进行模型匹配。由于Forrest提出的r连续位的匹配规则[3]在应用与客户分类问题上是存在问题的, 所以匹配方式采用基于汉明距离的非线性匹配方式。
基于汉明距离的非线性匹配方式在进行模式匹配的问题上克服了这个问题, 它从整体上把握匹配原则, 在进行模式匹配的时候设定一定的阈值, 比如说对于r位连续的字符串其中r-1位匹配则已经满足阈值。
将决策树生成的分类规则模型化生成规则矩阵R, Ri表示任一行向量, rij表示客户分类决策因子。
根据入侵检测的基本原理, 将决策树生成的分类规则模式化为特征串作为匹配模型的初始知识库。客户决策因子匹配模型启动忠诚客户知识特征串与需评判的客户因子进行匹配, 采用基于汉明距离的入侵检测模型, 使用基于汉明距离的数理统计匹配算法。
结合基于汉明距离进行匹配选择的模型对客户数据集进行分类, 应用此分类匹配模型来进行数据分类的模型。
3 改进的客户分类模型的分析及结论
改进的客户分类模型通过分析应用决策树方法进行客户分类的一般过程, 从数据预处理和应用规则进行数据集分类的几个方面对客户分类方法进行了组合优化。在数据预处理阶段采用线性代数的相关理论对产生优化的数据集的方法进行了研究, 得出了一组优化数据集的方法;在应用规则对数据进行分类的阶段, 给出了一种应用基于入侵检测的匹配模型来进行数据分类的方法, 该方法具有自适应与智能性的特点。整个改进的客户分类模型从一定的程度上有效地简化了分类方法和提高的分类效率, 并且有一定的智能性。
摘要：分析了应用决策树算法对CRM系统中客户进行分类的一般过程, 对分类的过程中的几个方面进行了优化, 给出了一个改进了的基于决策树分类算法的客户分类模型。
关键词：客户分类,决策树,数据集,匹配
参考文献
[1]刘小虎, 李生.决策树的优化算法[J].软件学报, 1998, 9 (10) :797～800.
分类树方法 第8篇
关键词：分类,决策树,信息论,ID3
1 决策树的定义
在决策树方法中, 有两个基本的步骤:构建树和将树应用于数据库。大多数研究都集中在如何有效地构建树, 而应用过程是很简单的。
定义1给出了决策树分类方法的定义。
定义1给定一个数据库D={t1, ..., tn}, 其中ti= (ti1, ..., tih) , 数据库模式包含下列属性{A1, A2, ..., Ah}。同时给定类别集合C={C1, ..., Cm}。对于数据库D, 决策树 (或分类树) 是指具有下列性质的树:
每个内部结点都被标记一个属性Ai;
每条弧都被标记一个谓词, 这个谓词可应用于相应父结点的属性;
每个叶结点都被标记一个类Cj。
利用决策树求解分类问题包括两个步骤: (1) 决策树归纳利用训练数据集构建一棵决策树; (2) 对每个元素, 应用决策树确定元素的类别。
2 ID3算法的信息论基础
信息论是C.E.Shannon为解决信息传递 (通信) 过程问题建立的一系列理论。一个传递信息的体统是由发送端 (信源) 和接收端 (信宿) , 以及连接两者的通道 (信道) 组成。信息论把通信过程看作是在随机干扰的环境中传递信息的过程。在这个通信模型中, 信息源和干扰 (噪声) 都被理解为某种随机过程或随机序列。因此, 在进行实际的通信之前, 收信者不可能确切了解信源究竟会发出什么样的具体信息, 不可能判断信源会处于怎样的状态, 这种情形就称为信宿对于信源状态具有不确定性。由于这种不确定性存在于通信之前, 因而又叫做先验不确定性。
在进行了通信之后, 信宿收到了信源发来的信息, 这种先验不确定性才会被消除或者被减少。如果干扰很小, 不会对传递的信息产生任何可察觉的影响, 信源发出的信息能够被完全收到, 在这种情况下, 信宿的先验不确定性就会被完全消除。但是, 在一般情况下, 干扰总会对信源发出的信息造成某种破坏, 使信宿收到的信息不完全。因此, 先验不确定性不能全部被清除。即通信结束后, 信宿还仍然具有一定程度的不确定性。这就是后验不确定性。
显然, 后验不确定性总要小于先验不确定性, 不可能大于先验不确定性。如果后验不确定性的大小正好等于先验不确定性的大小, 这就表示信宿根本没有收到信息。如果后验不确定性的大小等于零, 这就表示信宿收到了全部信息。
可见, 信息是用来消除不确定的东西。信息量的到小, 由所消除的不确定性的大小来计量。
3 基于互信息的ID3算法
3.1 ID3算法的基本思想
在实体世界中, 每个实体用多个特征来描述。每个特征限制在一个离散集中取互斥的值。例如, 设实体是某天早晨的气候, 分类任务是得到关于气候的类型有如下特征和取值:
outlook={sunny, overcast, rain}
temperature={cool, mild, hot}
humidity={high, normal}
windy={true, false}
某天早晨的气候描述为:
outlook:overcast
temperature:cool
humidity:normal
windy:false
它属于哪类气候呢?要解决这个问题, 需要用某个原则来判定, 这个原则来自于大量的实际例子, 从例子中总结出原则, 有了原则就可以判定任何一天的天气属于哪类气候了。
每个实体在世界中属于不同的类别, 为简单起见, 假定仅两个类别, 跟别为P、N。在这两种类别的归纳任务中, P类和N类的实体分别称为概念的正例和反例。将一些已知的正例和反例放在一起便得到了训练集。
由ID3算法的出一棵正确分类训练集中每个实体的决策树, 如图2所示:
决策树叶子为类名, 即P或N。其他结点由实体的特征组成, 每个特征的不同取值对应一分枝。若要对一实体分类, 从树根开始进行测试, 按特征的取值分枝向下进入新结点, 对新结点进行测试, 过程一直进行到叶结点, 实体被判为属于该叶结点所标记的类别。现用图2判本节开始处的例子, 得该实体的类别为P类。ID3就是要训练构成像图2这样的决策树。
实际上, 能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策是树。
3.2 ID3算法描述
(1) 主算法
(1) 从训练集中随机选择一个既含正例又含反例的子集 (称为“窗口”) ; (2) 用建树算法对当前窗口形成一棵决策树; (3) 对训练集 (窗口除外) 中的例子用决策树进行类别判定, 找出错判的例子; (4) 若存在错判的例子, 把它们插入窗口, 转入b) , 否则结束。
主算法中每迭代循环一次, 生成的决策树将会不同。
(2) 建树算法
(1) 对当前例子集合, 计算各特征的互信息; (2) 选择互信息最大的特征Ak; (3) 把在Ak处取值相同的例子归于同一子集, Ak取几个值就得几个子集; (4) 对既含正例又含反例的子集, 递归调用建树算法; (5) 若子集仅含正例或反例, 对应分枝标上P或N, 返回调用处。
(3) 实例计算
对于气候分类问题进行具体计算, 有以下五步。
(1) 信息熵的计算
对9个正例和5个反例, 有:
(2) 条件熵计算
A=outlook, 取值v1=sunny, v2=overcast, v3=rain。
在A1处取值sunny的例子5个, 取值overcast的例子4个, 取值rain的例子5个, 故:
而取sunny的5个例子中2个正例, 3个反例, 取overcas的4个例子中4个均为正例, 取rain的例子5个, 其中正例为3个, 反例为2个, 故:
(3) 互信息计算
对A1=outlook处, 有
类似可得:
(4) 构建决策树的树根和分枝
ID3算法将选择互信息最大的特征outlook作为树根, 在14个例子中对outlook的3个取值进行分枝, 3个分枝对应3个子集, 分别是:
其中F2中的例子全属于P类, 因此对应分枝标记为P, 其余两个子集既含有正例又含有反例, 将递归调用建树算法。
(5) 递归建树
分别对F1和F2子集利用ID3算法, 在每个子集中对各个特征 (仍为四个特征) 求互信息。
F1中的outlook全取sunny值, 则H (U) =H (U│V) , 即I (U, V) =0, 在余下3个特征中求出humidity的互信息量最大, 以它为该分枝的根结点, 再向下分枝。humidity取high全为N类, 该分枝标记N;取值normal全为P类, 该分枝标记为P。
在中, 对四个特征求互信息, 得到windy特征互信息最大, 则以它为该分枝根结点, 再向下分枝。它取ture时全为N类, 该分枝标记N;取false时全为P类, 该分枝标记为P。
这样就得到图2所示的决策树。
3.4 对ID3算法的讨论
(1) 优点
ID3在选择重要特征时利用了互信息的概念, 算法的基础理论清晰, 得算法较简单, 是一个具有使用价值的示例学习算法。
(2) 缺点
互信息的计算具有依赖于特征取值的数目较多的特征, 这样不太合理。一种简单的办法是对特征进行分解, 如气候问题中的例子, 特征取值不一样, 可以把它们统统化为二值特征。如outlook取值sunny, overcast, rain, 可以分解为三个特征:outlook_sunny, outlook_overcast, outlook_rain。取值都为“是”或“否”, 对temperature也可做类似的工作。这样就不存在偏向问题了。
用互信息作为特征选择量存在一个假设, 即训练例子集中能够的正、反例的比例应与实际问题领域里正、反例比例相同。一般情况不能保证相同, 这样计算训练集的互信息就有偏差。
ID3在建树时, 每个结点仅含一个特征, 是一种单变元的是算法, 特征间的相关性强调不够。虽然它将多个特征用一棵树连在一起, 但联系还是松散的。
ID3对噪声较为敏感。关于什么是噪声, Quinlan的定义是训练例子中的错误就是噪声。
它包括两方面:一是特征值取错;二是类别给错。
当训练集增加时, ID3的决策树会随之变化。在建树过程中, 各特征的互信息会例子的增加而改变, 从而使决策树也变化。这对于渐进学习 (即训练例子不断增加) 是不方便的。
4 结束语
ID3由于其理论清晰, 方法简单, 学习能力较强, 适于处理大规模学习问题, 得到了广泛使用, 是数据挖掘和机器学习领域的一个极好范例, 也不失为一种知识获取的有用工具。但其也存在一些不足之处。
参考文献
[1]陈文伟, 黄金才.数据仓库与数据挖掘[M].北京:人民邮电出版社.
[2]IAN H.Witten Eibe Frank.数据挖掘——实用机器学习技术[M].北京:机械工业出版社, 2006.
[3]Jiawei Han Micheline Kamber.数据挖掘:概念与技术[M].北京:机械工业出版社, 2007.
[4]Margaret H.Dunbam.数据挖掘教程[M].北京:清华大学出版社, 2010.
[5]J.R.QUINLAN.Induction of Decision Trees.Machine Learning 1:81-106, 1986.
[6]TJEN SIEN LIM and WEI YIN LOH and YU SHAN SHIH.A Com-parison of prediction accuracy, complexity, and training time of thir-ty-three old and new classification algorithms[J].Machine Learn-ing, 40, 203-228, 2000.
分类树方法范文
声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
