（计算机应用技术专业论文）基于程序演化的决策树算法优化研究.pdf

摘要 程序演化是根据某些法贝从一个程序生成另一个新的程序，这两个程序在 语义上是等价的，通过对源程序进行一系列保证正确性的演化，进行算法和数据 结构的求精，最终将源程序演化成一个等价的、高效的程序文本。 本文在决策树的优化问题中，引入程序演化的思想，演化得到了具有更高效 率的决策树。围绕该问题展开了以下工作： ( 1 ) 用h o m 伽o r p h i s m s 递归结构描述l d 3 算法。为演化出新的高效程序 奠定基础。 ( 2 ) 在对程序的规范化描述进行认真分析的基础上，找到影响程序运行效 率的主要因素，运用t u p l i n g 策略定义新的数据结构。 ( 3 ) 基于新的数据结构，对标准l d 3 算法和基于样本分布元组的决策树算 法进行演化，运用节点提升算法，最终演化得到新的基于样本分布树的决策树构 造算法，该算法构造决策树只需要扫描一次数据集合。 ( 4 ) 对本文演化所得的新决策树算法的时间有效性进行分析，并用h a s k e l l 函数式语言编程实现相关算法，对算法的正确性和有效性进行验证。 应用程序演化方法进行决策树算法的优化，为决策树算法优化的研究提供了 新的思路，同时研究成果将进一步验证程序演化方法的有效性。 关键词：程序演化；函数式语言；数据挖掘；决策树 p m 孕锄t r 锄曝f o 姗a t i 伽i sam e t h o db yw h i c hap r o 伊锄i st r a n s f e 仃e di n t o 卸o t h e r 伽ea c c o r d i n gt ot h ec c n a i nm l e s t h cs y n t 觚o ft h et r 矩s f e 玎c dp r o 铲a mi s e q u a v o i e n tt ot h eo r i g i m lp m 伊a m t h ea 1 9 0 r i t h m s 柚dd a t as t m c t u f c s 觚es i m p l i f i e d t l l | o u 曲t h eu s eo f 仃a n s f o m a t i o ns c h e m ew h i c hc a l lg i l a 砌t e et h ec c i l r a c y f i n a l l y l h es 0 u r c ep r o 伊锄i sd e r i v a t e di n t oap m c c d u 他嘶e n t c de f f i c i 曲tv e 墙i 伽 ho r d c rt 0o b t a i l lam o r ce f f j c i e n td e c i s i o n 仃t 圮，i nt h ef i e l do fo p t i m i z a t i 彻o f d e c i s i o nt r e e ，t l l em a i nh d d yo ft h ew i ! i t i n gu s e dt h cp r o 掣锄t m n 蚰咖a t i o nm e t h o dt o o p 血n i z et h ea l g o r i t h m ： ( 1 ) s t a n e db yd i s c f i b i n gas i m p l e 锄dc o 眦d ( b u tp r o b a b l yi 鹏f f i c i c n dp r 0 粤锄 u s i l l gh o m o m o 叩h i s m sf c c u r s i o ns t n l c t u r c ( 2 ) b 髂e d 锄t h e 觚a l y s i so ft h ep r o 掣a m 柚dc h s ep r 叩c rm e t h o d st o 仃a n s f 咖“i l i t om o r ee 1 五c i e n te q u i v a l c n t s a p p l yt l l p l i n gt c c h n i q u ci nd a t as 协l c t u r c d e f i n i t i o n 0 b t a i n i l l gt h en e we f f i d e n tp m 掣吼，w en e e ds 啪t h ed a t as e to n l y 衄e t i m ( 3 ) n u g hs 姗m a r i z i n gt h ej o ba b 0 v e ，w ed r a wac o n c l u s i o nt 0c o l l e c tt h c m e l h o d sb yw h i c hm e 咖p l c xp r o 铲锄c o u l db ew e nt r 柚s f o 姗c d 皿ef i d di l lo p t i m i 盈t i o no ft h ed e d s i o nt r c ei si n t c r s e t e d b yt h es d e n t i s t sa t h 咖e 柚da b r o a da ut h et j m e s c h o l a r s 蜥n gu pa1 0 to fi d e at oi m p m v et h ee 笳c j e n c y i na c c o r d a n w i t ht l l ee x c e s s i v em a l c h i n g 锄ds c a l eo fd e c i s i 彻t f t h r o u g ht h e e f f o n s ，t l l e yo b t a i n e dal a f g en u m b c fo fa c h i e v e m e n t s 1 【e yw d s ：芦o 黟砌t r a 璐f o m a t i o n ；f i l n c i o n a ll a n g i l a g e ；d a t am i n i n 苗曲c i s i o n 虹e e 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：习移唪 日期：知呻年孕月叼日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密因。 ( 请在以上相应方框内打“”) 日期：槲年牛月二7 日 日期：阳夕年弘月讶日 峰反 梆限 名 名 签 登 者 耀 作 刷 1 1 引言 第一章绪论 随着信息时代海量数据的出现，如何有效利用海量的原始数据分析 现状和预测未来，已经成为人类面临的一大挑战。由此，数据挖掘技术应运 而生并得到迅猛发展。数据挖掘是一种新型的数据分析技术，被广泛应用 于银行金融、保险、政府、教育、运输等企事业单位及国防科研上。数 据挖掘应用的普遍性及带来的巨大经济和社会效益，吸引了许多专家和 研究机构从事该领域的研究。 数据挖掘( d a t am i n i n g ) 又称数据库中的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，k d d ) ，是指从大型数据库或数据仓库中提取隐含 的、未知的、非平凡的极有潜在应用价值的知识或模式。它是数据库研 究中的一个很有应用价值的新领域，融合了数据库、人工智能、机器学 习、统计学等多个领域的理论和技术。数据挖掘从大量的数据中发现的 模式按其作用可分为两类：一类称为描述型模式，它是对数据中存在的 规律做出描述。如泛化模式、聚类模式、关联模式及时间序列模式。另 一类是预测型模式，它依据从己有数据获得的知识对未知数据的某些性 质进行预测。包括分类模式和回归模式。 其中，数据分类是数据挖掘中一个重要的内容。分类存在很多方法， 其中决策树分类以其易于提取显式规则、计算量相对较小、可以显示重 要的决策属性和较高的分类准确率等优点而得到广泛的应用【1 2 l 。 用于挖掘分类模式的方法有很多，如决策树方法，贝叶斯网络，遗 传算法，基于关联的分类方法，粗糙集，k 最临近方法等等。其中决策 树方法以其易被人理解、需要信息较少、效率及准确率较高等优点占据 着重要地位。决策树方法自产生至今，先后涌现出多种算法，包括i d 3 、 c 4 5 、c a r t 、s u q 、s p r i n t 、p u b l l c 等。它们的共同特点是对训练 样本集进行挖掘后都会生成一棵形如二叉树或多叉树的决策树。树的叶 子节点代表某一类别，非叶节点，包括根节点及内节点代表某个一般属 性( 非类别属性) 的一个测试，测试的一个结果形成非叶子节点的一个分 枝。从根节点到叶子节点的一条路径形成一条分类规则。一棵决策树能 够很方便的转化为若干条分类规则。人们可以依据分类规则直观地对未 知类别的样本进行预测【3 1 。 随着决策树在数据挖掘中的普遍使用，如何提高决策树的执行效率 就成了普遍关注的问题。 1 2 研究背景及国内外研究动态 1 2 1 数据挖掘技术 从数据库中发现知识( k d d ) 一词首次出现在1 9 8 9 年举行的第十 一届国际联合人工智能学术会议上。到目前为止，由美国人工智能协会 主办的k d d 国际研讨会已经召开了8 次，规模由原来的专题讨论会发 展到国际学术大会，研究重点也逐渐从发现方法转向系统应用，注重多 种发现策略和技术的集成，以及多种学科之间的相互渗透。1 9 9 9 年，亚 太地区在北京召开的第三届p a k d d 会议收到1 5 8 篇论文，空前热烈。 i e e e 的k n o w l e d g e a n d d a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并行计算、计算机网络和信息工程等其他领域的国际学会、 学刊也把数据挖掘和知识发现列为专题和专刊讨论，甚至到了脍炙人口 的程度。 数据挖掘技术在实际生活中有着重要的实用价值，被广泛应用于银 行金融、保险、政府、教育、运输等企事业单位及国防科研上。数据挖 掘应用的普遍性及带来的巨大经济和社会效益，吸引了许多专家和研究 机构从事该领域的研究。目前，数据挖掘技术正处在发展当中。数据挖 掘涉及到数理统计、模糊理论、神经网络和人工智能等多种技术，技术 含量比较高，实现难度较大。此外，数据挖掘技术还会同可视化技术、 地理信息系统、统计分析系统相结合，丰富了数据挖掘技术及工具的功 能与性能。 图卜1 数据挖掘的形成 数据挖掘研究主要基于三大技术支柱，包括数据库、人工智能和数 理统计。图1 1 简要描述了数据挖掘技术的形成过程：数据库理论的发 2 展促成了数据仓库的形成，人工智能的发展促进了机器学习的进步，同 时这些技术与传统的数理统计理论的结合，最终促成了数据挖掘的产生。 数据挖掘方法有多种，其中比较典型的有分类分析、聚类分析、关 联分析、序列模式分析、可视化、偏差分析、粗糙集和模糊集理论等。 与数据挖掘所采用的方法相对应，数据挖掘能发现的知识可分以下几类： 1 、广义型知识( g e n e r a l i z a t i o n ) ，指类别特征的概括性描述知识，根 据数据的微观特性发现其表征的、较高层次概念上的、宏观的知识，是 对数据的概括、精炼和抽象，通常用来反映同类事物的共同性质； 2 、特征型知识，反映同类事物的共同性质的知识； 3 、差异型知识，反映不同事物之间属性差别的知识； 。 4 、关联型知识，反映事物之间依赖或关联的知识，如果多项不同 属性间存在关联，那么其中一项的属性值即可依据其他属性值预测； 5 、预测型知识，根据时间序列型数据，根据历史的和当前的数据 推测未来数据，也可以认为是以时间为关键属性的关联知识； 6 、偏差型知识，是对差异和极端特例的描述，揭示事物偏离常规 的异常现象。如标准类外的特例、数据聚类外的离群值等。 以上这些知识都可以随着概念树的提升在不同的概念层次上被发 现，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要，。 例如，从一家超市的数据仓库中，可以发现的一条典型关联规则可能是 “买面包和黄油的顾客十有八九也买牛奶”，也可能是”买食品的顾客几 乎都用信用卡”，这种规则对于商家开发和实施客户化的销售计划和策略 是非常有用的。 1 2 2 数据分类 数据分类( c l a s s i f i c a t i o n ) 是数据挖掘中一个重要的内容。分类 ( c 1 a s s i f i c a t i o n ) 模型的主要功能是根据商业数据的属性将数据分派到不 同的组中。在实际应用过程中，分类模型可以分析分组中数据的各种属 性，并找出数据的属性模型，确定哪些数据模型属于哪些组。这样就可 以利用该模型来分析已有数据，并预测新数据将属于哪一个组。分类模 型应用的实例很多，例如，可以将银行网点分为好、一般和较差3 种类 型，并以此分析这3 种类型银行网点的各种属性，特别是位置、盈利情 况等属性，找出决定它们分类的关键属性及相互问关系，此后就可以根 据这些关键属性对每一个预期的银行网点进行分析，以便决定预期银行 网点属于哪一种类型。 数据分类作为数据挖掘的一个重要内容，在统计学，机器学习、神 经网络和专家系统中得到了较早的研究i4 1 ，但只是近些年来，人们才将 3 它与数据库技术结合起来解决实际问题。数据分类实际上就是从数据库 对象中发现共性，并将数据对象分成不同几类的一个过程，分为两步： 第一步，建立一个模型，描述预定的数据类集或概念集。通过分析由属 性描述的数据库元组来构造模型。输入数据，即为建立模型而被分析的 数据元组形成训练集( t f a i n i n gs e t ) ，是由一条条的数据库记录( r e c o f d ) 组成的。每一条记录包含若干条属性( a t t r i b u t e ) ，组成一个特征向量。训 练集的每条记录还有一个特定的类标签( c l a s sl a b e l ) 与之对应。该类标 签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可 为样本向量：( v l ，v 2 ，v 。：c ) 在这里v 1 表示字段值，c 表示类别。这一 步的目标是对训练数据进行分析，使用数据的某些特征属性，给出每个 类的准确描述。第二步，使用建好的模型进行分类。首先评估模型，预 测准确率，如果认为模型的准确率可以接受，就可以用它对类标号未知 的数据元组或对象进行分类l5 l 。 分类和预测的效果可以根据以下标准进行比较和评估： 1 预测准确度，预测准确度是使用最多的一种比较尺度，特别是对 于预测型分类任务，目前公认的方法是1 0 折分层交叉验证法。 2 计算复杂度，计算复杂度依赖于具体的实现细节和硬件环境，在 数据挖掘中，由于操作对象是海量的数据库，因此空间和时间的复杂度 闯题将是非常重要的一个环节。 3 模型描述的简洁度，对于描述型的分类任务，模型描述越简洁越 受欢迎；例如，采用规则表示的分类器构造法就更有用，而神经网络方 法产生的结果就难以理解。 4 强壮性，这涉及给定噪声数据或具有空缺值的数据，模型正确预 测的能力。 5 可伸缩性，这涉及当给定大量数据时，算法有效构造模型的能力。 一个算法是可伸缩的，如果给定内存和磁盘空间等可利用的系统资源， 其运行时间应当随数据库大小线性增加。分类的典型应用：信用卡系统 中的信用分级、市场调查、疗效诊断、寻找店址等等。 1 2 3 决策树分类算法 分类存在很多方法，其中决策树归纳以其易于提取显式规则、计算量 相对较小、可以显示重要的决策属性和较高的分类准确率等优点而得到 广泛的应用。据统计，目前决策树算法是应用最广泛的数据挖掘算法之一， 利用率高达1 9 。应用领域已由医疗到博弈论和商务等领域，是一些商业 规则归纳系统的基础【6 】。 4 决策树算法自2 0 世纪6 0 年代以来，在分类、预测、规则提取等领 域有着广泛应用。特别是在q u i n l a n 于1 9 8 6 年提出l d 3 算法以后，在机 器学习、知识发现领域得到了进一步应用及巨大的发展。在分类问题上， 流行的技术是贝叶斯分类、神经网络、遗传算法和决策树等。基于决策 树的分类模型以其特有的优点广为采用。首先，决策树方法结构简单， 生成便于人们理解的规则；其次，决策树模型效率高，对训练集数据量 较大的情况较为适合；再者，决策树算法的计算量相对来说不是很大； 然后，决策树方法通常不需要受训数据外的知识，擅长处理非数值型数 据。最后，决策树方法具有较高的分类精确度。它是指在数据库的各个 对象中找出共同特性，并按照分类模型把它们进行分类。“训练集”作为 分类器中的输入，它的每一个元组的属性和数据库的元组的属性相同， 并且每个元组都有一个类标志。分类的目标是通过分析训练集中的数据， 对类进行准确的描述或者为类建立模型，然后用它对数据库中的其它数 据分类或者上升为分类规则【7 8 1 。图1 2 简单描述了决策树的生成过程。 图卜2 决策树的生成过程 由于这些优点，决策树算法在数据挖掘、统计分析、机器学习、神 经网络、专家系统等领域中得到了广泛的应用，常用的是l d 3 决策树归 纳算法【9 ，1 0 ，1 1 】。 对决策树算法的优化问题，一直是一个倍受关注的领域。寻找新的 构造决策树和简化决策树的方法一直是决策树技术研究的一个热点。由 于数据库中有些属性的描述语言不当、噪音数据的存在以及构建的决策 树中存在着结构完全相同的重复子树等原因，导致决策树过大，使得用 户难以理解。因此，必须寻找一些技术对决策树进行优化，在不影响分 类正确率或有更好的分类正确率的前提下，使优化后的决策树有尽可能 小的规模( 叶子节点数少) ，并能推导出尽可能短的分类规则。目前用于 优化决策树的方法主要有修改测试属性空间、修改测试属性选择、对实 例的数据限制和采用其他数据结构方法等【1 2 1 3 ，14 1 。 当今，国内外不少研究人员致力于对决策树的优化工作，研究人员 5 针对决策树容易过度拟合、规模过大、产生的规则过长等缺点提出了不 少优化方法；在实现决策树算法并行性【1 5 ，1 6 ，1 7 】和实现高效增量型挖掘算 法【1 8 ，1 9 ，2 0 j 方面也取得了比较好的效果。 1 2 4 程序演化 1 9 8 7 年，r b i r d 首先提出了程序演化的概念1 2 ，随后r b i r d ， e m e i j e r ，f o k k i n g a 等人将范畴理论( c a t e g o r yt h e o r y ) 引入程序演化中 【2 2 ，2 3 1 ，从程序代数的角度建立了程序演化的理论基础，完善了 b i r d m e e f t e n s 形式体系( b i r d m e e n e n sf o f m a l i s m ) ，并将这一方法应用 于程序优化中。 为了正确清晰地进行复杂程序的设计，在模块化程序设计中，程序 p r o g 被定义为若干个模块( 在函数式程序中表现为递归函数) r i 的组合， 每个r i 的功能简单明了，程序表示为： p r o g = r 1o or n 这种组合方式使得程序设计能够更清晰地描述程序。然而，这样的 程序设计方法可能由于下列的原因造成程序运行效率的下降： 在两个模块( 递归函数) 之间可能产生不必要的中间数据结构。多 个模块( 递归函数) 为了保证结构的清晰，常常不必要地对同一数据进 行多次重复的处理。因此，应用程序演化方法进行程序优化要解决的问 题就是：如何建立一套描述机制简洁严格地描述程序，这样的描述应该 具有良好的数学性质，并便于其后的演化操作；如何用合理的策略去消 除造成程序运行效率下降的因素。 为解决这些问题，许多学者做了大量的工作。文献【2 4 】对在演化过程 中用融合规则消除冗余的中间结果。用元组处理规则消除重复的数据处 理、通过累积规则增加额外的结果以提高效率等方法进行了归纳，wn c h i n 等人探讨了应用融合和元组处理规则进行模块化程序优化设计的 方法【2 5 1 ，p e t t o r o s s i 提出演化的组合策略( c o m p o s i t i o ns t r a t e g y ) 和基于 l a m b d a 抽象的泛化策略( g e n e r a l i z a t i o ns t r a t e g y ) 【26 1 ，a p a r d o 及m a u r o j a s k l i o f f 分别讨论了类属积累( g e n e r i c a c c u m u l a t i o n s ) 规则，提出通过 积累进行程序推导的若干代数法则【2 7 1 。a p a r d o 在他的博士论文中对演 化方法在递归程序优化中的应用进行了深入的讨论。j a n i sv o i g t l a n d e f 提 出了消除冗余中间结果的新策略【2 引。z h e n j i a n gh u 等人应用演化方法得 出了一种高效的频繁项集的挖掘算法【2 射。 6 1 3 论文的主要工作 鉴于决策树算法在数据挖掘中的重要作用，这种分类算法有着十分 广泛的应用领域和客观的应用前景。程序演化虽然已经建立了其理论框 架，并取得了一些实践成果，但该方法的完善仍需要更多的程序开发的 实践应用加以推动。 应用程序演化方法探讨决策树算法的优化，为决策树算法优化的研 究提供了新的思路，同时研究成果将进一步验证程序演化方法的有效性。 本文的主要工作是把程序演化的思想引入决策树的优化问题中： ( 1 ) 用h o m o m o r p h i s m s 递归结构描述i d 3 算法。为演化出新的高 效程序奠定基础。 ( 2 ) 在对程序的规范化描述进行认真分析的基础上，研究选择合 理的演化规则和演化策略。 ( 3 ) 运用t u p l i n g 策略定义一种新的数据结构( 样本分布元组) ， 基于这种数据结构分别对样本分布判别算法和样本划分函数进行演化和 推导，得到了一个基于样本分布元组的决策树构造函数，该函数构造决 策树的每一层仅需要扫描一次数据集合，从而提高了程序执行的效率； 在此基础上，又定义了一种新的数据结构( 样本分布树) ，基于这种数据 结构对样本划分函数进行演化，运用接点提升算法，最终演化得到新的 样本分布树的构造算法，该算法构造决策树只需要扫描一次数据集合。 ( 4 ) 对本文演化所得的新决策树算法的时间有效性进行分析，并 用h a s k e l l 函数式语言编程实现相关算法，对算法的正确性和有效性进 行验证 1 4 论文的结构 本文分析了使用函数式语言描述的决策树算法，使用程序演化策略 减少数据扫描次数，以达到提高程序运行的效率的目的。 全文内容结构如下： 第一章简述了决策树分类算法和程序演化的背景及研究现状，最 后说明了本文的研究重点，简要给出了文章的组织结构。 第二章介绍了程序演化及类h a s k e l l 语言的一般概念，阐述了类 h a s k e l l 的基本语法和递归函数的一般结构：h o m o m o r p h i s m s 。 第三章阐述了l d 3 决策树算法，定义了数据结构，并使用类h a s k e l l 7 语言描述了l d 3 决策树算法。 第四章阐述了程序演化常见的演化策略，运用t u p i i n g 策略对决策 树算法进行演化：基于样本分布元组的决策树构造函数演化和基于样本 分布树的决策树构造函数演化。 第五章全文的总结，对新算法的主要性能进行简要的阐述和说明， 分析了实验结果，并对下一步的工作进行了展望和探讨。 8 第二章程序演化及类h a s k ei l 描述语言 程序演化为程序优化、并行程序的设计与实现提供了理论基础和技 术手段。用类h a s k e l l 描述语言规范化的描述问题是程序演化工作的第 一步，由于该语言有严格的代数性质，有利于下一步的衍生推理。 2 1程序演化 所谓程序演化( 又称程序变换) ，是根据某些法则从一个程序生成 另一个新的程序，这两个程序在语义上是等价的，通过一系列保证正确 性的源程序的演化，进行算法和数据结构的求精，最终将源程序演化成 一个面向过程的、高效的程序文本。程序演化思想的出现，使得程序优 化工作耳目一新，可有效的提高程序执行的效率。 由于计算机应用领域的不断扩展，用于解决相关问题的计算机程序 变得愈来愈庞大和复杂。如何设计高效的程序一直是软件理论研究的重 要课题。程序变换( p r o 盯a mt r a n s f o 加a t i o n ) 为程序优化、并行程序设 计与实现提供理论框架和技术手段。应用程序演化进行程序优化，其过 程可分为程序的描述和程序的改进两个阶段。首先从问题的形式规定出 发，采用函数式语言规范化描述一个面向问题的、易于理解的正确程序， 暂不考虑效率；其后通过一系列保证语义等价的演化步骤，进行算法和 数据结构的求精，最终衍生出一个高效程序。 用p i ( i - 0 ，1 ，n ) 表示程序。如果程序p i 与p i 具有相同的语义，称 p i 与p j 语义等价，记为s e m ( p i ) = s e m ( p j ) ，对于每个程序p i ，给定函数c 用于描述程序p i 运行的代价( 时间复杂性或空间复杂性) ，则程序变换 过程如图2 1 所示。通过p o p l 一一p n 的变换序列，得到p n ，其中 s e m ( p 1 ) = s e m ( p 2 ) = = s e m ( p n ) ，且有c ( p 。) 1 时) 。 不仅可以对整数进行递归运算，对列表也可以进行递归运算。针对 列表设计递归算法时，通常把空列表“【】”当作基本情况( 递归终止条 件) ，而把非空列表当作递归情况。 可以将计算列表长度分成两种情况：空列表和非空列表。空列表的 长度等于0 ，而非空列表的长度等于摘掉列表的第一个元素之后剩下的 部分的长度加1 。定义计算列表长度的函数如下： m l l c n g t h 【】= o m y l e n g t h ( x ：x s ) = 1 + m y l e n g t hx s 同样地，f i l t e r 函数的基本情况是空列表，递归情况是非空列表。 m y f i l t e rp 【】= 【】 m y f i l t e rp ( x ：x s ) = i fpx t h e nx ：m y f i l t e rpx s e l s em y f i l t e rpx s 当传递给m yf i l t e r 一个空列表时，只是地返回一个空列表。当传递 给m vf i l t e r 一个非空列表时( 用x ：x s 表示) ，们需要判断x 是不是应该 被过滤掉，这个判断用px 来完成，在f i l t e r 的原型中，p 是一个返回b o o l 型的函数。如果px 返回t u r c ，那么就说明x 需要保留，这时把x 加入 返回的列表的前面，然后递归地处理剩下的部分。如果px 返回f a l s e ， 说明x 需要剔除，这时只处理剩下的部分。 同样地，m a p 和f o l d l f o l d r 这些函数都可以类似实现。 2 3h o m o m o r p h i s m s 结构 为了使程序演化的操作合法化并且简单化，在命令式语言的结构化 程序设计方法中，命令g o t o 是禁止使用的，以有助于实现对条件和l o o p 循环等流结构的控制。象函数式程序这样的高水平算法程序，递归定义 为规范程序提供了强大的控制机制。如下对列表的变量定义： f ( a ：x ) = fx f ( gx ) f ( fx ) 在函数的右侧通常没有具体的递归形式；它这可以以任何方式表 示，f 的递归定义可以以任何形式出现在任何位置。从某种角度讲，这 很类似与命令式语言的g o t o 的任意使用，使得递归定义难以控制。相反， 这种演化方法在函数右侧使用合适的递归方法产生了一种比较好的演化 形式。h o m o m o r p h i s m s 就是一种最重要最普遍的演化方式【3 饥。 h o m o m o f p h i s m s 是操控象列表和树这样的代数数据结构的函数。它 们演化来自具有集中结构的代数数据。列表的数据结构是【a 】。从代数 的角度而言，这种结构可以等价地表示成由三部分组成的结构模式： ( 【a 】，【】，( ：) ) 。其中： 【o 】表示整个列表的元素都是a 类型； 【】和( ：) 是用予建立列表的数据结构。 h o m o m o r p h i s mh o m i 是一种重要的递归形式，( r ，e ，o ) 这种列表递归函数 的基本形式定义如下： h o m l 口= e h o m l ( a ：x ) = a o h o m l ( x ) 实际上，h o m l 是一个重复使用的标记，它用“e ”取代每一个出现 的“【】”，用“o ”取代了列表中出现的每一个“：”。由于这中列表 h o m o m o r p h i s m 可以被“e ”和“毋”唯一确定，就使用如下方式描述列 表： h o m l = ( 【e ，o 】) l 假如有关联操作。和 ，二进制操作e ，以及一个同构g ，这时如 果满足下面式子 纠c - c e 口 ? 啪) c - 重c $ 掣( c o g ) 1 7 这里，g 满足 g 弘l i 鼍4 g t 一g z 秘g # 则称h 是一个h _ h o m o m o r p h i s m 对于一个h h 同构，则程序可以按下面方式分解： h z c ；o ( 归教传磅) b 而 也就是说，对于一个h h 同构，它能够切分为o 和。教两个并行 架构，这些并行架构能够在逻辑上并行的时间里线性顺序的执行。 例如：s u m = ( 【0 ，+ 】) 等价于： s u m 【】= o s u m ( a ：x ) = a + s u m ( x ) 即求和的递归函数s u m ，在没有任何输入的情况下，返回0 ；如果 输入是一个数字序列，那么就用第一个数字加上递归的使用s u m 得到的 数值。 2 4 小结 本章分析和评述了程序演化的基本思想、研究现状及意义。阐述了 类h a s k e l l 这种函数式语言的产生，发展及基本特点，概述了这种函数 式语言的基本语法，本章最后还介绍了程序演化中常用的h o m o m o r p h i s m 结构。 1 8 第三章i d 3 决策树算法的规范描述 在i d 3 算法中，决策树是以自顶向下递归地各个击破方式构建的。 首先判断样本是否属于同一类，如果不属于同一类就计算属性的信息增 益，再找出具有最大信息增益的属性作为选择属性，利用这个选择属性 划分数据集合。本章用h o m o m o r p h i s m 结构递归地描述标准i d 3 决策树 算法，这是整个程序演化工作的第一步，是进行下一步衍生推理的开始， 为演化出新的高效程序奠定了基础。 3 1i d 3 决策树算法 决策树是对数据进行分类，并以此达到预测的目的。该决策树算法 先根据训练集数据形成决策树，如果该树不能对所有对象给出正确的分 类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正 确的决策集。决策树代表着决策集的树形结构。决策树由决策结点、分 支和叶子组成。决策树中最上面的结点为根结点，每个分支是一个新的 决策结点，或者是树的叶子。每个决策结点代表一个问题或决策，通常 对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。 沿决策树从上到下遍历的过程中，在每个结点都会遇到一个测试，对每 个结点上问题的不同的测试输出导致不同的分支，最后会到达一个叶子 结点，这个过程就是利用决策树进行分类的过程，利用若干个变量来判 断所属的类别【3 8 】。 常用的是i d 3 决策树归纳算法，基本策略如下1 3 8 j ； 树以代表训练样本的单个节点开始； 如果样本都在同一个类，则该节点称为树叶，并用该类标记； 否则，算法使用称为信息增益的基于熵的度量作为启发信息，选 择能够较好的将样本分类的属性。该属性称为该节点的“测试”或“判 定”属性； 对测试属性的每个已知的值，创建一个分支，并据此划分样本； 算法使用同样的过程，递归地形成每个划分上的样本判定树。一 旦一个属性出现在一个节点上，就不必考虑该节点的任何后代； 1 9 递归划分步骤仅当下列条件之一时停止： 给定节点的所有样本都属于同一类。 没有剩余属性可以用来进一步划分样本。在此情况下使用多数表 决。 分支测试属性没有样本，在这种情况下使用多数表决创建一个树叶 i d 3 的一个优点，是它的建树时间和任务的困难程度呈线性关系，计算量 以、。 i d 3 算法是由q u i n l a n 首先提出的。该算法是以信息论为基础，以 信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类【3 9 1 。 i d 3 算法，在树的每个节点上使用信息增益度量选择测试属性。这 种度量称做属性选择度量或者分裂的优良性度量。选择具有最高信息增 益的属性作为当前节点的测试属性【4 0 1 。 ，设s 是s 个数据样本的集合。假设类标号属性具有m 个不同值，定 义m 个不同类，s i 是类c i ( i = 1 ，2 ，m ) 中的样本数。则对一个给定的样 本分类所需的期望信息由下式给出： 地 ，小一私l o g z n ( s = s ，+ s 2 + + s m ) 其中p i 是任意样本属于类c i 的概率，并用s i s 估计；由于信息以二 进制编码，所以对数函数以2 为底。 设属性a 有v 个不同的值 a 1 ，a 2 ，a v ) 。可以用属性a 将s 划分为 v 个子集 s 1 ，s 2 ，s v ；其中，s i 包含s 中这样一些样本，它们在a 上具有值a j 。如果a 选作测试属性，则这些子集对应于由包含集合s 的 节点生长出来的分枝。设8 i j 是s ；中类c i 的样本数。根据由a 划分成子 集的期望信息由下式给出： 删一塞鱼专皇 ) 项鱼二二兰立充当第j 个子集的权，并且等于子集中的样本数除以s s 中的样本总数。对于给定子集s j ， ，0 1 ，) 一一p f1 0 9 2p f 两 其中，p i j 是s j 中样本属于类c i 的概率。 在a 上分枝将获得的编码信息是 g 口加) 一，o 。，5 2 ，j 。) 一e ) 换言之，g a i n ( a ) 是由于知道属性a 的值而导致的熵的压缩。算法 计算每个属性的信息增益。具有最高信息增益的属性选做给定集合s 的 测试属性。创建一个节点，并以该属性标记，对属性的每个值创建分枝， 并据此划分样本。 给定a l l e l e c t r o n i c s 顾客数据库训练数据集如表3 1 ：类标号属性 b u y s - c o m p u t e r 有两个不同值( 即 y e s ，n o ) ) ，因此有两个不同的类( m = 2 ) 。 设类c l 对应与y e s ，而c 2 对应于n o 。类c 1 有9 个样本，类c 2 有5 个样 本。为了计算每个属性的信息增益，首先计算对给定样本所需的期望信 息：i ( s l ，s 2 ) = i ( 9 ，5 ) = 0 9 4 0 下一步，计算每个属性的熵。从属性a g c 开始，观察每个样本值的 y e s 和n o 分布。 对于a g e = “ 4 0 ”： s 1 3 = 3s 2 3 = 2 i ( s 1 3 ，s 2 3 ) = o 9 7 1 如果样本按a g e 划分，对一个给定的样本分类所需的期望信息为： 气d气 e ( 4 舻) 5 云7 0 1 l ，) + 云7 0 t ：，3 z ) + 云7 0 1 ，5 ) - o 2 4 6 表3 1a l l e l e c t r o n i c s 顾客数据库训练数据集 r i d a g e l n c 0 m es t u d e n t c r c d i t c l a s s ：b u y s c o m p “t e 1 4 0l o w y e s f a i r y e s 6 4 0l o w y c s e x c e l l e n tn o 7 3 1 4 01 0 w y c s e x c e l l e n t y e s 8 4 0m e d i u m y e s f a i r y e s 1 l= 3 0m e d i u m y e s e x c e l l e n t y c s 1 23 1 4 0m e d i u mn o e x c e l l e n t y e s 1 3 3 1 一4 0h i g h y e s f a i r y e s 1 4 4 0m e d i u mn 0e x c e l l e n tn o 这种划分的信息增益就是 白洲4 ) 一j ，5 ：) 一( d ) 一o 2 4 6 类似地，可以计算出g a i n ( i n c o m e ) = o 0 2 9 ，g a i n ( s t u d e n t ) = 0 1 5 1 和 g a i n ( c r e d i t ) = 0 0 4 8 。由于a g e 在属性中具有最高信息增益，它被选做测试 属性。创建一个节点，用a g e 标记，并对每个属性值引出一个分枝。 3 2 数据结构描述 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实 际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程。而数据挖掘的主要目标是学会一个分类函数或 分类模型把数据库中的数据项映射到给定类别中的某一个。最为典型的 分类方法是基于决策树的分类方法。它是从实例集中构造决策树，是一 种有指导的学习方法。典型的决策树学习系统是l d 3 ，它采用自顶向下 不回溯策略，能保证找到一个简单的树1 4 1 1 。 在i d 3 算法中，决策树是以自顶向下递归的各个击破方式构建的。 开始时所有的训练样本都在根节点，递归划分步骤仅当下列条件之一时 停止： 给定节点的所有样本都属于同一类。 没有剩余属性用来进一步划分样本。在次情况下，使用多数表决。 这涉及将给定的节点转换成树，并用s a m p l e s 中的多数所在的类标记它。 换一种方式，可以存放节点样本的类分布。 针对i d 3 算法，应用程序演化思想最终会得到一个新的快速的等价 算法。本文的任务就是用函数式语言规范的描述一个简明的，但暂时不 考虑效率的规范算法。该算法只考虑正确性，但不考虑程序的效率。这 是程序演化有效进行的保障。 程序演化受到了相当大的关注。早期工作主要集中在命令式的语言 领域，例如d i j k s t r a 的命令向导语言。而当今，非常流行的已经是函数 式语言了，相比命令式语言，函数式语言有一下优点【4 2 l ： 函数式语言比较抽象，能够更加简练的描述问题，产生更加简短 易懂的程序； 函数式语言使用了代数法则，像数学一样，能够被构建，操作和 推理； 函数式语言经常即用来表示清晰的规范说明，又用来表达它有效 的处理方式，使得衍生可以用一种独特的形式进行：相反，命令式语言 的衍生常依赖一个本质上的演算，以获得详细的说明和程序的特性； 通过使用程序演化的方法，由一个函数式的规范i d 3 算法，应用演 化策略衍生出一个高效的等价的算法。这个过程的基础是建立在合理的 数据结构的基础上的，因此定义新的数据结构是整个程序演化的前提。 经过对i d 3 算法的反复研究，分析得出样本的属性名( a t t r i n a m ) 、 属性值( a t t r i v a l ) 以及类值( c l a s s v a l ) 是整个算法中十分重要的参数。多次 实验以后，定义了一种数据结构( 【( a t t r i n a m ，a t t f i v a l ) 】，c l a s s v a l ) ，用这三 个参数来描述样本；使用类分布( c l s d i s ) 和样本分布( s a m p l e d i s ) 来描述数 据集合。 首先，使用一个记录列表【s a m p l e l 来表示训练数据集合，使用二元组 ( 【( a t l r i n a m ，a t t r i v a l ) 】，c l a s s v i l ) 表示样本： ( 1 ) d a t a s c t = f s a m p l e 】 2 ) s a m p l e = ( 【( a t t “n a m ，a t t r i v a l )