（计算机应用技术专业论文）基于优化决策树的短期电力负荷预测研究.pdf

华北电力大学硕士学位论文摘要 摘要 短期负荷预测是一项重要和具有挑战性的工作。从寻求准确预测电力系统负荷 的目的出发，提出了基于优化决策树的短期负荷预测新方法，有效地考虑了非负荷 因素对短期负荷预测的影响。利用负荷的纵向相似性和横向相似性对负荷坏数据进 行辨识和修正，采用粗糙集理论对决策树的测试属性约简进行一次优化，约简负荷 相关影响因素。针对决策树i d 3 算法的缺陷，对测试属性选择方法进行改进，提出 了优化算法m b s i d 3 ，并对决策树剪枝以降低复杂度，通过三次优化建立的决策树 短期负荷预测模型在有更好的分类准确率的前提下具有较小的规模。良好的实例分 析效果说明，该方法可提高短期负荷预测的精度，具有实用性和优越性。 关键词：短期负荷预测，决策树，粗糙集，i d 3 算法 a bs t r a c t s h o r t t e m1 0 a df b r e c a s t i n gi sa ni m p o r t a n ta n dc h a h e n g e a b l ew o r k i no r d e rt o a c c u r a t e l yf o r e c a s tt h el o a d so fp o w e rs y s t e m ，t h i sa r t i c l ep r e s e n t san c w s h o r t t e r mi o a d f o r c c a s t i n gm e t h o db 弱e d0 n0 p t i m i z e dd e c i s i o nt r e e ，w h i c hc f n c i e n t l yt a k e st h e n o n - 1 0 a df a c t o r s i n f l u e n c e si n t 0a c c o u n t p 0 r 仃a i ta n dt r a n s v e r s e c o m p a r a b i l i t ya r e e m p l o y e dt 0d i s t i n g u i s ha n dc o r r e c tb a d1 0 a dd a t a r 0 u g hs e ti su s e dt oo p t i m i z et h e t e s t i n ga t t r i b u t e s0 fd e c i s i o nt r e eb yr e d u c i n gt h en o n - 1 0 a df a c t o r s t h e nt 0 e i i m i n a t e l i m i t a t i o no ft h el d 3a l g o r i t h m ，a no p t i m i z e da l g o r i t h mm b s i d 3i sp r e s e n t e dt os e l e c t t h et e s t i n ga t t r i b u t e s a n dt h ep m n i n gm e t h o di su s e dt 0r e d u c et h ec o n l p l e x i t y a f t e r t h r e eo p t i m i z a t i o n ，t h ee s t a b l i s h e ds h o r t t e 彻l o a df b r e c a s t i n gm o d e lc a nc a t e g o r i z e m u c hb e t t e ra n dh a sl e s s e rs c a l e g o o dt e s tr e s u l t su s i n ga c t u a ld a t ad e m o n s t r a t et h a t t h i sm e t h o dc o u l di m p r o v et h ea c c u r a c y0 fs h o r t t e 珊1 0 a df b r e c a s t i n ge f f e c t i v e l y ，a n di t h a sp r a c t i c a b i l i t ya n ds u p e r i o r i t y o uf a n g f a n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f w a n gc u i r u k e yw o r d s ：s h o r t - t e r ml o a df o r e c a s t i n g ，d e c i s i o nt r e e ，r o u g hs e t ，i d 3a l g o r i t h m 华北电力大学硕士学位论文摘要 摘要 短期负荷预测是一项重要和具有挑战性的工作。从寻求准确预测电力系统负荷 的目的出发，提出了基于优化决策树的短期负荷预测新方法，有效地考虑了非负荷 因素对短期负荷预测的影响。利用负荷的纵向相似性和横向相似性对负荷坏数据进 行辨识和修正，采用粗糙集理论对决策树的测试属性约简进行一次优化，约简负荷 相关影响因素。针对决策树i d 3 算法的缺陷，对测试属性选择方法进行改进，提出 了优化算法m b s i d 3 ，并对决策树剪枝以降低复杂度，通过三次优化建立的决策树 短期负荷预测模型在有更好的分类准确率的前提下具有较小的规模。良好的实例分 析效果说明，该方法可提高短期负荷预测的精度，具有实用性和优越性。 关键词：短期负荷预测，决策树，粗糙集，i d 3 算法 a bs t r a c t s h o r t t e 珊1 0 a df b f e c a s t i n gi sa ni m p o r t a ma n dc h a l l e n g e a b l ew o r k i no f d e rt o a c c u r a t e l yf o r e c a s tt h el o a d so fp o w e rs y s t e m ，t h i sa r t i c l ep r e s e n t san c ws h o r t t e r mi o a d f o r c c a s t i n gm e t h o db 筋e d 0 n0 p t i m i z e dd e c i s i o nt r e e ，w h i c hc f n c i e n t l yt a k e st h e n o n - 1 0 a df a c t o r s i n f l u e n c e si n t 0a c c o u n t p 0 r 仃a i ta n dt r a n s v e r s ec o m p a r a b i l i t ya r e e m p l o y e dt 0d i s t i n g u i s ha n dc o r r e c tb a d1 0 a dd a t a r 0 u g hs e ti su s e dt 0o p t i m i z et h e t e s t i n ga t t r i b u t e so fd e c i s i o nt r e eb yr e d u c i n gt h en o n - l o a df a c t o r s t h e nt oe i i m i n a t e l i m i t a t i o no ft h el d 3a l g o r i t h m ，a no p t i m i z e da 1 9 0 r i t h mm b s i d 3i sp r e s e n t e dt 0s e l e c t t h et e s t i n ga t t r i b u t e s a n dt h ep m n i n gm e t h o di su s e dt 0r e d u c et h ec o n l p l e x i t y a f t e r t h r e eo p t i m i z a t i o n ，t h ee s t a b l i s h e ds h o r t t e 彻l o a df b r e c a s t i n gm o d e lc a nc a t e g o r i z e m u c hb e t t e ra n dh a sl e s s e rs c a l e g o o dt e s tr e s u l t su s i n ga c t u a ld a t ad e m o n s t r a t et h a t t h i sm e t h o dc o u l di m p r o v et h ea c c u r a c y0 fs h o r t t e 珊l o a df b r e c a s t i n ge f f b c t i v e l y ，a n di t h a sp r a c t i c a b i l i t ya n ds u p e r i o r i t y o uf a n g f a n g ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f w a n gc u i r u k e yw o r d s ：s h o r t - t e r ml o a df o r e c a s t i n g ，d e c i s i o nt r e e ，r o u g hs e t ，i d 3a l g o r i t h m 声明尸明 本人郑重声明：此处所提交的硕士学位论文基于优化决策树的短期电力负荷预测 研究，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取 得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 、 学位论文作者签名：丝型墨日期：罂堕丛 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文：学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播 学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：攻甓菪 日期：2 0 。z 孑 新虢逝 日期：垒! 望皇：! 华北电力人学硕士学位论文 1 1 课题研究的内容及意义 第一章引言 电力系统的作用是对电力系统的各类用户尽可能经济的提供可靠而合乎标准 要求的电能，以随时满足各类用户的负荷要求。但是由于电能不能大量储存，要求 系统发电应随时和系统负荷的变化保持动态平衡。而系统未来负荷变化的获取是通 过负荷预测来实现的，这样电力系统负荷预测就因此发展起来了，成为工程科学中 重要的研究领域，是电力系统自动化中的一项重要内容。 电力系统负荷预测乜1 是根据电力负荷、经济、社会、气象等的历史数据，探索 电力负荷历史数据变化规律对未来负荷的影响，寻求电力负荷与各种相关因素之间 的内在联系，从而对未来的电力负荷进行科学的预测。 电力系统负荷预测从时间方面来说，可以分为长期、中期、短期与超短期口1 。长 期负荷预测是年度预测，一般指5 年以上的预测，其目的是合理安排电网、电源的 建设，提供宏观决策依据。中期负荷预测是月度预测，指提前几周到几个月甚至几 年的预测。主要用于电量估计，指导发电企业制定燃料供应计划，电力市场条件下 期货合同的制定，合理安排机组检修计划等。短期负荷预测是同度预测，一般是指 提前几小时到一周的负荷预测，是电力系统发电计划的重要组成部分，对于调度安 排开停机计划、机组最优组合、经济调度、最优潮流、电力市场交易有着重要的意 义。超短期负荷预测是时分预测，指提前一小时、半小时甚至十分钟对负荷进行预 测，主要用来对电网进行在线控制，对发电厂进行合理调度，从而提高电网的经济 性和安全性。本文中，研究对象为短期负荷预测。 短期负荷预测是负荷预测的重要组成部分，其应用范围最广，在现代电力系统 的安全和经济运行中起着重要的作用。短期负荷预测精度的好坏直接关系到产业部 门的经济利益。负荷预测精度越高，越有利于提高发电设备的利用率和经济调度的 有效性。在电力系统发展规划阶段，如果负荷预测结果偏低，将会导致系统的规划 装机容量、输电规划等不足，无法满足社会的用电需求，甚至还可能缺电；而如果 负荷预测结果偏高，则会导致一些发电、输电设备投入系统后的运行效率不高，增 加运行费用，从而引起投资的浪费。总之，短期负荷预测工作的准确性对电力系统 的经济效益有着重要的影响，是电力系统最基础性的工作之一。建立良好的预测模 型，减小负荷预测误差，提高预测精度，是电力系统运行经济性和安全性的有利保 证。短期负荷预测的重要意义可以归纳为如下几点： ( 1 ) 短期负荷预测是电力系统发电计划的重要组成部分，是合理安排电网运 华北电力人学硕十学1 1 ：) ：论文 行方式、机组启停计划、交换功率计划等的基础。准确的短期电力负荷预测，能 对运行中的发电厂的出力要求提出预告，使得事先可以估计出发电机组出力变化的 情况。对于装机容量不大的孤立电网，短期负荷预测是十分必要的。 ( 2 ) 对于一个容量较大的电网，为了经济合理的安排本网内各发电机组的启 动与停机，以使系统在要求的安全范围内为保持必要的旋转储备容量的耗费为最 小，短期负荷预测也是必须的拍，。 ( 3 ) 当电网进行计算机在线控制时，应当用短期负荷预测的信息来实现发电 容量的合理调度，满足给定的运行要求，同时使发电成本为最小。 ( 4 ) 电价是电力市场的杠杆和核心内容，体现了电力市场的竞争性和开放性， 而电价的制定是在未来给定电价计算期的负荷预测的基础上完成的。因此，发电企 业要保证其电价的竞争能力并且盈利，就必须获得精确的短期负荷预测值，才能定 出既有竞争力又保证盈利的电价1 。 ( 5 ) 在电力系统中，随着电力体制改革的深化和电力市场的建立和发展，经 济性成为电网运行的重要指标 1 ，也对短期负荷预测提出了更高的要求，短期负荷 预测是指导电力市场交易计划的重要依据。电力市场条件下的短期负荷预测不仅是 一个技术问题而且还是一个经济性问题，因此电力市场的发展更加需要准确的短期 负荷预测。 1 2 短期负荷预测的国内外研究现状及发展趋势 短期负荷预测的研究已有很长历史，国内外的许多专家、学者在预测理论和方 法方面作了大量的研究工作，取得了很多卓有成效的进展。由于负荷的随机因素太 多，非线性极强，而有些传统方法理论依据尚存在局限性等问题，因此，新理论和 新技术的发展一直推动着短期负荷预测的不断发展，新的预测方法层出不穷。 短期负荷预测技术的发展是从过分依赖于调度员的运行经验到自动化、智能化 逐步转变的过程，大体上经历了三个阶段。 最早的电力负荷预测工作完全依赖于预测人员以往的运行经验完成，由于缺乏 科学的理论做指导，不同的预测人员的预测结果往往差别很大，并且预测人员的运 行经验是经过生产实践逐步积累起来的，所以没有经验的新的调度员一般无法胜任 这项工作，总之，早期的短期负荷预测主要依赖预测人员的实际经验，预测误差往 往较大。 自八十年代中期以来，国内外学者开展了大量以各种电力负荷预测模型和方法 为主体的电力负荷预测理论研究，提出了许多有效的电力负荷预测模型和方法，这 一阶段所提出的符种预测方法，总体而言，可以归结为数学模型法和非数学模型法 华北电力人学硕士学位论文 两类。 数学模型法是这一阶段早期电力负荷预测研究的主要方向，使短期负荷预测摆 脱了完全依赖调度员经验的历史，将短期负荷预测技术提高到一个新的水平。典型 的数学模型法有回归分析法( 线性回归分析法、非线性回归分析法、多变量回归分 析法) 阳3 、确定性时间序列分析法( 时间序列平滑法、时间序列分解法) 、随机时间 序列分析法一b o x - j e n k i n s 法、状态空间法。但由于电力负荷变化的非线性、时变性 和不确定性的等特点，很难建立一个合适的数学模型来清晰地表达负荷和影响负荷 的变量之间的关系。这一问题随着电力系统的日趋复杂化越发突出。 九十年代以来，基于人工智能、模糊集等理论的非数学模型电力负荷预测方法 研究成为该领域的研究热点与重点。它们为解决数学模型法的不足提供了新的思 路。非数学模型主要用来解决非线性问题和不确定性问题，和数学模型法相比，非 数学模型预测方法在预测过程中考虑了各种不确定因素( 如温度因素、天气因素、 季节因素、人工经验等) ，在实际的负荷预测过程中确实能提高预测精度。典型的 非数学模型法主要有人工神经网络呻，1 训、专家系统法3 、模糊推理n 副、灰色预测法 【1 3 】盘蕾 守。 以上所述的方法都是单一的预测方法，这些方法虽然在电力系统短期负荷预测 中得到了应用，但是各有其局限性。如人工神经网络本身存在不能直接处理模糊化 信息的缺点，使得天气、特殊事件和专家经验无法应用，由于训练样本中隐含的信 息太多，可能导致训练不好，收敛速度慢，容易收敛到局部最小点，在网络结构和 连接权值的确定上缺乏有效的全局寻优手段n4 1 。再如专家系统法中专家知识存在着 主观性、不确定性，不完全性，往往造成知识冗余、蕴涵、矛盾、遗漏；计算机程 序不一定能够准确、完全地表达专家的知识等等。如何实现预测知识的自动获取是 专家系统方法进一步发展的关键所在。所以随着对负荷预测的深入研究和广泛应 用，单一的预测方法的应用越来越难以适应发展，现在人们正在探索和研究多种智 能方法综合的预测模型。 优选组合预测有两种概念：一种是指将几种预测方法所得的预测结果，选取适 当的权重进行加权平均的预测方法；另一种是指在几种预测方法中进行比较，选择 拟合优度最佳或标准离差最小的预测模型作为最优模型进行预测。组合预测集合多 种单一模型所包含的信息进行最优组合，提高负荷预测的精度，从而达到改善预测 结果的目的。如文献【1 5 】构建了一种新型的短期负荷预测模型，首先采用多层前馈 神经网络，以与预报点负荷相关性最大的几种因素作为输入因子，以改进b p 算法 作为预测算法，来获得预报同相似同负荷曲线；然后引入自适应模糊神经网络，用 于预测预报同的最大、最小负荷；针对模糊神经元的权值更新问题，采用一种新的 权值更新算法一一步搜索寻优法，在获得预报同相似同各点负荷和最大、最小负荷 3 华北电力大学硕士学位论文 的基础上，通过纵向变换，对预报r 的负荷修正，进一步减小预测误差，从而提高 了电力系统短期负荷预测的准确度。在文献【1 6 】中，以软计算方法中的神经网络和 模糊系统为实现工具，将数据挖掘中的分类和聚类思想应用于负荷预测问题的研究 中，根据数据挖掘理论中的分类和聚类思想，构建k o h o n e n 网和b p 网的组合模型 进行坏数据辨识和调整。采用c a r t 算法完成模糊推理系统的结构辨识任务，构造 相应的a n f i s 网络进行参数辨识。文献f 1 7 】作者列举出粗糙集和神经网络相结合的 短期负荷预测模型，采用粗糙集理论对各种影响负荷预测的因素变量进行识别，以 此确定预测模型的输入变量；在此基础上通过属性约简和属性值约简获得推理规则 集，再以这些推理规则构筑神经网络预测模型，并采用附加动量项的b p 学习算法 对网络进行优化。 尽管短期负荷预测技术在算法理论研究上取得了很大的成就，但是在实际应用 中由于种种原因短期负荷预测技术还存在很多问题，短期负荷预测理论和实践有待 进一步发展。 1 3 决策树技术应用于短期负荷预测的研究现状 决策树起源于人工智能，是数据挖掘模型中最广泛采用的模型之一，决策树技 术是数据挖掘中的一个重要分支，决策树和决策规则是解决实际应用中分类问题的 数据挖掘方法。决策树也用于监督式的数据挖掘上，尤其是数据分类，可以解决高 维数据的分类问题，将训练模块的记录分为独立的子群，而其中的子群都有自己的 规律。决策树技术具有分类速度快，精度高，生成的模式简单等优点。随着数据挖 掘技术的兴起和数据挖掘技术在商业智能等方面的应用，决策树技术越来越发挥出 强大的作用。 决策树是一种较为通用并深入研究的分类函数逼近方法，是一种有指导的学习 方法，它着眼于从一组无秩序、无规则的事例中推理出决策树表示形式的分类规则。 它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同的 属性值判断从该节点向下的分支，在决策树的叶节点得到结论。其中每个内部节点 代表对某个属性的一次测试，一条边代表一个测试结果，叶子代表某个类或类的分 布。目前已产生多种决策树算法，如i d 3 算法n 引、c 4 5 算法n 引、c a l 玎算法心州等。 决策树分类与其他类分类算法如统计方法、神经网络等比较起来有如下优点：( a ) 产 生的分类规则易于理解。决策树的每个分枝都对应一个分类规则，因此决策树分类 算法最终可以输出一个容易理解的规则集；( b ) 速度相对较快：( c ) 准确率相对较 高。 决策树方法是分类方法中被广泛使用的一类方法，已经在信誉证实、市场调查、 疗效诊断、性能预测等领域得到了很好的应用。另外，近年来决策树研究的内容多 4 华北电力人学硕十学位论文 种多样，决策树技术和神经网络技术相结合，决策树与模糊集合原理相结合，决 策树技术与进化算法相结合等。目前已有多种文献采用数据挖掘中的决策树分类算 法或者采用决策树算法与其他技术相结合的方法来完成负荷的预测。 文献f 2 2 】提出了一种基于决策树技术的短期负荷预测算法，利用决策树对影响 负荷变化的因素进行了筛选；并在此基础上按照负荷分别进行处理，得到平稳的负 荷序列；然后应用时间序列技术进行预测。文献【2 3 】针对决策树i d 3 算法的缺陷， 提出了属性值对的两次信息增益优化算法，该算法克服了i d 3 算法在选取属性进 行扩展时易偏向属性值多的属性及i d 3 算法属性间相关性考虑较少的缺点，通过对 熵阈值的设定和预剪枝技术，部分克服了i d 3 算法对噪声敏感的不足，结合预测日 气象、星期等信息，建立日特征负荷决策树模型进行同特征负荷的预测。文献【2 4 1 提出决策树与专家系统相结合的负荷预测系统。利用决策树建立预测模型，对待测 日负荷进行初步预测，再结合专家系统中的修正模型对初步结果进行修正，得到最 终预测结果。文献【2 5 】提出了利用决策树方法将电力系统大量历史负荷数据按照相 应影响因素进行分类，采用c 4 5 算法建立负荷预测的决策树模型，完整阐述了基 于决策树技术的负荷预测技术，包括样本数据的预处理、数据离散化和决策树的生 成和剪枝。文献【2 6 】提出了一种用神经网络筛选出对数据分类最有效的若干条件属 性直接生成最小决策树的负荷预测方法。根据属性的重要性利用神经网络来选择对 分类效果最佳的条件属性，利用决策树模型进行样本的训练和分类预测。此方法结 合了神经网络和决策树的优势，大大改善了传统决策树的效能，在快速生成决策树 的同时提高了决策树的分类精度。 1 4 本论文的主要工作 电力系统短期负荷预测的研究具有重要的意义，为了提高短期负荷预测的精 度，必须认真研究分析各种信息( 负荷历史资料及相关影响因素等) ，研究新的理 论和方法，进一步提高预测精度。本文的研究对象是基于优化决策树的短期电力负 荷预测，试图从历史负荷数据预处理到短期负荷预测建模过程建立一个完整的预测 体系。本文的工作主要集中在如下几个方面： ( 1 ) 决策树基本概念及优化技术的研究与总结。决策树是数据挖掘中的一种 分类方法，主要用于分类和预测。决策树的复杂程度和分类精度是需要考虑的两个 最重要的因素，故本文介绍了决策树的量化评价标准。基于决策树的分类算法自提 出至今，种类不下几十种。各种算法在执行速度、可扩展性、输出结果的可理解性、 分类预测的准确性等方面各有千秋。本文主要介绍了c l s 算法、i d 3 算法和c 4 5 算法。洪家荣、p e i k it u 等人证明求解最优决策树是n p 难题。因此，必须寻找一 些技术对决策树进行优化，使构造的决策树尽可能接近最优决策树，即在不影响分 华北电力火学硕十学位论文 类正确率或有更好的分类正确率的自仃提下，使优化后的决策树有尽可能小的规模， 并能推导出尽可能短的分类规则。本文研究了对决策树进行优化的几种技术：修改 测试属性空间、修改测试属性选择、对实例的数据限制、控制树的大小和采用其他 数据结构方法等。 ( 2 ) 由于电力系统负荷是一个随机非平稳的过程，其负荷数据的观测值受到 各种人为或设备等随机因素的影响，因而得到的历史数据中常常包含有“异点数 据 ，即坏数据或不良数据。本文通过对电力负荷的特点进行分析，利用负荷曲线 的横向相似性和纵向相似性对历史负荷数据进行垂直和水平预处理，对其中的不良 数据进行辨识和修正。 ( 3 ) 电力负荷的变化受到很多不确定因素的影响，确定哪些是关键因素以及 选择哪些因素作为负荷预测模型的输入变量是负荷预测建模首先要解决的问题。目 前这部分工作仍主要由预测人员凭经验确定，缺乏有效、科学的知识支持手段。本 文针对这一问题展开讨论，提出基于条件熵和属性频度的属性约简算法，寻求负荷 预测最佳属性集。 ( 4 ) i d 3 算法是决策树构造算法中的一种经典核心算法。l d 3 算法具有理论清 晰，描述简单，学习能力较强，分类速度快等优点。但它也存在依赖于取值数目较 多的属性、学习简单逻辑表达式能力差等缺点。本文提出一种改进l d 3 算法，详细 介绍了改进算法的原理及理论依据，改进算法不仅能减小决策树计算复杂度，减少 决策树的生成时间，还能克服i d 3 算法易偏向于选择取值较多的属性的缺点，又能 很好的解决i d 3 学习简单的逻辑表达式能力差的缺点，同时对属性间的相关性进行 了一定的考虑。 ( 5 ) 为了进一步降低构造的决策树的复杂度，本文采用了r e p 后剪枝技术对 决策树进行优化，从而在保证j 下确率的前提下尽量构造简单的决策树，使决策树尽 可能的接近最优树。 ( 6 ) 采用优化决策树方法对非负荷影响因素和相应负荷分量之| 日j 的关系进行 挖掘，找出非负荷因素和待预测负荷之l 日j 的决策树形式知识表达，即建立基于优化 决策树的短期负荷预测模型，并采用北京地区和邯郸地区的历史负荷、气象数据研究 了本文算法的合理性和有效性。 6 华北电力大学硕七学位论文 2 1 决策树简介 第二章决策树算法概述 分类的目的是分析输入的数据，通过把握在训练集中的数据表现出来的特性， 为每一个类找到一种准确的描述或模型。分类问题一般分为两步：创建分类模型和 使用模型预测。创建分类模型是一个机器学习过程，通过某种分类算法对训练集进 行训练，得到分类模型；使用分类模型前先用测试集评估分类模型的准确率，满足 一定精度的分类模型可以用来对类别未知的数据集进行预测瞳 。 2 1 1 决策树描述 决策树( d e c i s i o nt r e e ) 又称判定树，是数据挖掘中的一种分类方法乜8 1 ，主要 用于分类和预测。可以用于分类规则挖掘的方法很多，除了决策树方法外，还有贝 叶斯网络、神经网络、概念格和粗糙集合等乜玑圳。其中基于决策树分类的理论研究 和应用研究是最重要的领域之一。与其它分类模型相比，在构造决策树的过程中， 不需要除训练数据集之外的任何额外信息，训练速度比较快，生成的决策树的分类 精度比较高，而且容易被人理解，因此决策树在实际中得到了广泛的应用1 。 决策树是一个可以自动对数据进行分类的倒立的树型结构，是树型结构的知识 表示，可以从一组无次序、无规则的事例中推理出树状形式表示的分类规则。它采 用自顶向下的递归方式构造，根据一定标准选取属性作为决策树的内部节点，并根 据该属性的不同取值构造不同的分支，在树的叶节点得到结论。其中每个内部节点 表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或 类分布，树的最顶层节点是根节点，从根节点到叶子节点的每条路径就代表一条判 定规则。 如图2 1 是一棵典型的决策树，该图根据历史数据，对“星期六的天气是否适 合打高尔夫球”进行归纳学习建立了一棵决策树。其中椭圆代表非叶节点，方块代 表叶子节点，从树中不难看出判定规则。 7 华北电力火学硕士学位论文 图2 1 “星期六的天气是否适合打高尔夫球”分类决策树 建立一棵决策树的算法如下： 输入：训练样本集s ，属性集a ； 输出：一棵决策树t ； b u i l d t r e e ( s ) b e g i n 用样本集s 创建节点n ； i fa 为空t h e n 返回n 为叶节点； i fn 为纯t h e n 返回n 为叶节点 e l s e f o r 每一个属性a 根据某一评价标准选取属性彳作为当前节点； 根据彳的取值将s 分裂为 s ) ，并对决策树分叉； 对每一个s i f 墨为空，则返回叶节点 e l s eb u i l d t r e e ( s ) ) 在实际应用中，数据中不可避免的会存在噪声和异常，决策树在建模的过程中 华北电力人学硕士学位论文 将既对正确数据建模，同时也对这些噪声和异常数据建模，为消除噪声和异常数据 对决策树的影响，需要对生成的决策树进行剪枝。剪枝按照实施时间的不同分为先 剪枝和后剪枝。先剪枝在决策树的构建过程中对每一个节点进行判断，如果符合某 种预剪枝的标准，就停止树的构造，生成叶节点。后剪枝则是待决策树完全生成后， 运用特定的剪枝算法对整棵决策树进行修剪口2 1 。 2 1 2 决策树的评价指标 在决策树学习算法当中，决策树的复杂程度和分类精度是需要考虑的两个最重 要的因素。下面给出决策树的量化的评价标准3 川。 ( 1 ) 过学习 在由决策树学习的过程中，必须从一组假设中选择一个使得它与训练实例集相 匹配，如果预先知道所要学习的函数属于整个假设空间中一个很小的子集，那么即 使在训练实例不完整的情况下，也有可能从训练实例集当中学习有用的假设，来使 其能够对未知实例进行正确分类。即使如此还是希望能有一个大的训练实例集，因 为训练集越大，则关于分类的信息越多，此时随机地从与训练集相一致的假设集中 选一个就能对未知实例的分类进行预测。相反，如果训练实例集与整个假设空间相 比已经非常小，但仍有过多的与训练实例相一致的假设供我们选择，此时做出假设 泛化的能力将很差，这时就会出现过学习，即当有过多的假设与训练实例集相一致 的时候称为过学习。c o h e n 和j e n s e n 副提出当一个算法过高估计增加树的复杂性对 于分类的正确性的贡献时，就会出现过学习现象。 ( 2 ) 决策树的有效性 利用一棵决策树来估计它在测试实例集合进行分类的性能称为决策树的有效 性。将决策树在测试实例集合上进行实际测试，然后从中选择在测试实例集上表现 最好的一棵决策树，这种方法等价于在测试集中训练决策树，很多情况下不现实。 因此，往往利用训练集本身来估计训练算法的有效性。即用2 3 训练集对决策树进 行训练，1 3 训练集来检测其有效性，但这样会增大过学习的可能性。 ( 3 ) 交叉有效性( c r o s s i n gv a l i d a t i o n ) 将训练实例集t 分为互不相交且大小相等的k 个子集，对于任意子集z ，用丁一z 训练决策树，之后z 用对生成的决策树进行测试，得到错误率q ，再求其平均值即 为整个算法的错误率。 ( 4 ) 余一有效性 这种有效性度量，类似于交叉有效性，不同之处在于将每个z 的大小定为1 ， 增大了算法的复杂程度，但相应地其准确程度也是最高的。 q 华北电力人学硕十学位论文 ( 5 ) 决策树的复杂程度 决策树的复杂程度是度量一个决策树算法学习效果的一个重要指标。对于给定 的描述语言，单变量( u n i v a r i a t e ) 决策树的复杂程度主要由树的节点个数决定；多 变量( m u i t i v a r i a t e ) 决策树则主要由节点中属性的总个数决定。 2 2 决策树生成算法 基于决策树的分类算法自提出至今，种类不下几十种。各种算法在执行速度、 可扩展性、输出结果的可理解性、分类预测的准确性等方面各有千秋。下面主要介 绍一下c l s 算法、i d 3 算法和c 4 5 算法。 2 2 1c l s ( 概念学习系统) 学习算法 c l s ( c o n c e p tl e a r n i n gs y s t e m ) 学习算法是h u n t 等人在1 9 6 6 年提出的，是归 纳学习中最早的分治算法。目前最有名的q u i n l a n 的i d 系列算法和c 4 5 算法的核 心仍然是c l s ，由于属性的选择不同，使得分类的效率和质量大大提高。 c l s 以一棵空决策树开始，并通过增加节点逐步求精，直到产生一棵能正确分 类训练例子的决策树。下面给出c l s 算法的描述。 已知全体训练实例集s 和全体测试属性集a t ： 1 ) 如果s 中所有的训练实例都属于同一个类，则产生一个该类的叶子节点， 并终止。 2 ) 如果a t 非空，根据某种启发式策略选择一个属性a ，设a 的取值为u ， ， ， ，并生成新节点。 3 ) 将s 中的实例根据其属性a 的取值加以划分，生成r 个子集，记为s ，s ， s ，和可供测试的属性集a t = a t a 。 4 ) 对于每个子集s ；和a t 递归调用c l s 算法。 从c l s 算法的描述可以看出，决策树的构造过程也就是假设特化的过程，所以 c l s 算法可以看作是只带一个操作符的学习算法，此操作符可以表示为：通过添加 一个新的判定条件( 新的判定节点) ，特化当前假设。c l s 算法递归调用这个操作 符，作用在每个叶节点，来构造决策树。 在算法的2 ) 中，如果训练实例集没有矛盾，即没有所有属性的取值相同的两 个实例属于不同的类，如果a t 为空，则s j 中的所有训练实例都属于同一个类，即 算法的终止条件只需要用“a t 为空”和“s i 中的所有训练实例都属于同一个类”二 者中的任何一个即可。但是对于可能存在的有矛盾的训练实例集，上述说法就未必 1 0 华北电力大学硕七学位论文 成立了。 在c l s 算法的步骤3 ) 中，应满足r 1 ，否则继续分类则没有意义，但是若训 练实例集中存在矛盾，则难以保证r 1 。 在c l s 算法的步骤2 ) 中，并没有给出测试属性的选取标准，因而为算法的改 进提供了很大的空间。 2 2 2i d 3 算法 l d 3 ( i n t e r a c t i v ed i c h o t o m e t e r3 ) 算法是1 9 7 9 年由q u i n l a n 提出的_ 种基于信 息熵的决策树学习算法，他把s h a n n o n 的信息论引入到了决策树算法中，把信息熵 作为选择测试属性的标准，对训练实例集进行分类，并构造决策树来预测如何由测 试属性对整个实例空间进行划分。 与c l s 算法相比，i d 3 算法主要做了两方面的修改，即增加了窗口技术和提出 了以信息熵的下降速度作为选取测试属性的标准。 在c l s 算法中，每次运行算法事先都要知道所有的训练实例，即在算法运行前， 将训练实例全部装入内存，而当训练实例非常大时，则不可能将实例集一次性装入 内存中。为了解决这个问题，q u i n l a n 在i d 3 算法中引入了窗口技术( w i n d o w s ) 。 信息熵是数据集中的不确定性、突发性或随机性程度的度量。信息熵的下降速 度是i d 3 中关键的选取测试属性的标准。信息熵的下降也就是信息不确定性的下降。 决策树学习过程就是使得决策树对划分的不确定程度逐渐减小的过程。i d 3 算法选 择当前样本集中具有最大信息增益值的属性作为测试属性。i d 3 算法的基本原理描 述如下。 定义2 1 ：设训练实例集为t ，若根据类别属性被划分为k 类，记为 c = c l ，c ：，g ) ，那么识别t 中训练实例的类属所需要的信息是蜘仃) ；，( p ) ，其中 p 是划分 c 。，c 2 ，c ) 的概率分布 p = ( ic il l 丁i ，ic ：i i 丁i ，igl lri ) ( 2 1 ) 蜘( 驴童科飞科一砉p ( c f 川烈c f ) ( 2 2 ) 其中，ic fi 是第f 类训练实例的个数，i 丁i 为t 中总的训练实例个数，记一个实例 属于第f 类概率为p ( c f 岍咖斜。 华北电力大学硕士学位论文 定义2 2 ：若选择非分类属性即测试属性a 进行测试，设属性a 具有y 个不同的属 性值并将t 划分为y 个不相交子集i ，- = l 2 ，v ，在彳。口，情况下属于第f 类的实例 个数为f ，弓2 尚为测试属性a 的取值为口j 时，它属于第f 类的概率。此时实例子集 t 对分类不确定性程度为： j 咖( 乃) 一一z 弓木i g 弓 ( 2 3 ) 那么识别t 中实例的类属所需要的信息就是识别瓦中实例的类属所需要的信息的 权平均，也就是蜘仃，) 的权平均 蜘似刃一耋谢宰蜘( 乙) - 一套薹斜 弓g 弓 c 2 4 ) 定义2 3 ：识别t 中实例的类属所需要的信息与获取属性a 值后识别t 中实例 的类属所需要的信息之差，称为属性a 的信息增益g 口加似，r ) ，可以将其看作是按照 属性a 的取值划分所获得的收益 g 口跏( 么，r ) t ，l 厂d ( 丁) 一办和( 彳，丁) ( 2 - 5 ) 属性a 对分类提供的信息，即属性a 的信息增益( i n f o r m a t i o ng a i n ) g 口咖研，r ) 的值越大，说明选择属性a 对于分类提供的信息越大，选择a 后对分类的不确定程度越 小。 给定测试属性x 。，x 2 t ，类别属性c 及训练集s ，构造决策树的i d 3 算法形 式化描述如图2 2 所示。 华北电力大学硕士学位论文 f u n c t i o nl d 3 ( r ：测试属性集合，c ：类别属性，s ：训练集) b e g i n i fs 为空t h e n f e t u m 值为失败的单个节点； i fs 所含记录类别属性值均相同t h e n r e t u m 值为该分类属性值的单个节点； i f r 为空i h e n r e t u m 单个节点，值为s 中各记录分类属性取值频度最高的值： l e td 是属性集r 中具有最大的g a i n ( d ，s ) 的属性： l e tp ，l - = l2 ，历 是属性d 的各种可能的取值； k t s ，i _ ；1 ，2 ，朋 是属性d 分别取不同值的子集； 返回一棵树，根节点标记为属性d ，由它生出的各个弧分别标记为d ， d 2 ，d 。，分别指向各个子树d 3 ( r - d ) ，c ，s ) ，i d 3 ( r d ) ，c ， s 2 ) ，l d 3 ( r d ，c ，毛) ； e n dl d 3 图2 - 2 构造决策树的i d 3 算法 i d 3 算法具有理论清晰，描述简单，学习能力较强，分类速度快等优点，适合 于处理大规模的学习问题，是数据挖掘和机器学习领域中的一个极好范例。但是l d 3 算法也存在着一些缺点。 1 ) 信息增益的计算依赖于属性取值数目较多的特征，而属性值较多的属性却 不总是最优的属性。 2 ) i d 3 学习简单逻辑表达式的能力较差。 3 ) i d 3 算法在建树时，每个节点只含有一个变量，属性之间的相关性强调的不 足，虽然多个属性通过一棵决策树联系起来，但是联系还是松散的。同时由于它是 单变量的算法，表达复杂概念也非常困难，所以有学者提出建立多变量决策树的方 法。 4 ) l d 3 算法对噪声较为敏感，其中噪声包括属性耿值错误，以及所给类别错误 触 奇。 5 ) 在数据挖掘中，由于某种操作对象很多是巨型数据集的数据库，故计算复 杂的问题将是非常重要的一个环节，将直接影响生成与使用模型的计算成本，数据 集越大，算法的计算量增加的越快。 1 3 华北电力大学硕士学位论文 6 ) 当训练集增加时，i d 3 算法的决策树也会随之变换，各属性的信息增益也会 随着实例的增加而改变，从而导致决策树也发生改变，因而不利于增量式学习。 2 2 3c 4 5 学习算法 c 4 5 算法是i d 3 算法的改进，i d 3 算法只能处理属性值为离散值的属性，通常 是二值属性，同时i d 3 算法没有考虑属性值缺损的情况。c 4 5 算法可以处理连续值 属性，属性值缺损，以及决策树剪枝，规则生成等问题。在应用于单机的决策树算 法中，c 4 5 算法不仅分类准确率高而且是速度最快的。 在i d 3 算法中使用了信息增益g a i n ( x ，t ) ，由信息增益的定义可知，当一个属 性可能的取值越多时，信息增益就越大，例如，当一个属性x ，每个记录在其上的 取值均不相同，那么它的i n f o ( x ，t ) 就为0 ，由此g a i n ( x ，t ) 即为最大值。为了弥补 这一点，q u i n l a n 提出了用增益率来替换增益。c 4 5 采用基于信息增益率( 1 n f o r m a t i o n g a i nr a t i o ) 的方法选择测试属性。信息增益率等于分割信息量( s p l i ti n f o r m a t i o n ) 的比值。 定义2 4 ：属性a 对训练样本集t 的信息增益率定义为： g 口胁尺口f 国( 么，丁) = g 口觑( 彳，丁) 印“f ，l 厂d ( 4 ，r ) ( 2 6 ) 其中，s p l i t i n f 0 ( x