学位论文 > 优秀研究生学位论文题录展示

基于程序演化的决策树算法优化研究

作　者: 杨峰
导　师: 陈曦
学　校: 长沙理工大学
专　业: 计算机应用技术
关键词: 程序演化函数式语言数据挖掘决策树
分类号: TP301.6
类　型: 硕士论文
年　份: 2007年
下　载: 134次
引　用: 0次
阅　读: 论文下载

内容摘要

程序演化是根据某些法则从一个程序生成另一个新的程序,这两个程序在语义上是等价的,通过一系列保证正确性的对源程序的演化,进行算法和数据结构的求精,最终将源程序演化成一个面向过程的、高效的程序文本。程序演化思想的出现,使得程序优化工作耳目一新,可有效的提高程序执行的效率。对决策树算法的优化问题,一直是一个倍受关注的领域。当今,国内外不少研究人员致力于对决策树的优化工作,针对决策树容易过度拟合、规模过大、产生的规则过长等缺点,研究人员提出了不少优化方法,并取得了比较好的效果。本文在总结已有成果的基础上,在决策树的优化问题中,引入程序演化的思想,以期得到具有更高效率的决策树。围绕该问题展开以下工作:(1)用Homomorphisms递归结构描述ID3算法。为演化出新的高效程序奠定基础。(2)在对程序的规范化描述进行认真分析的基础上,研究选择合理的演化规则和演化策略。(3)运用tupling策略定义新的数据结构,基于这种数据结构进行演化,运用接点提升算法,最终演化得到新的决策树构造算法,该算法构造决策树只需要扫描一次数据集合。(4)对本文演化所得的新决策树算法的时间有效性进行分析,并用Haskell函数式语言编程实现相关算法,对算法的正确性和有效性进行验证。

全文目录

摘要  5-6
Abstract  6-9
第一章绪论  9-17
  1.1 引言  9-10
  1.2 研究背景及国内外研究动态  10-15
    1.2.1 数据挖掘技术  10-11
    1.2.2 数据分类  11-12
    1.2.3 决策树分类算法  12-14
    1.2.4 程序演化  14-15
  1.3 论文的主要工作  15
  1.4 论文的结构  15-17
第二章程序演化及类 Haskell 描述语言  17-27
  2.1 程序演化  17-18
  2.2 类Haskell描述语言  18-25
    2.2.1 Haskell语言简介  18-20
    2.2.2 基本语法  20-25
  2.3 Homomorphisms结构  25-26
  2.4 小结  26-27
第三章 ID3 决策树算法的规范描述  27-38
  3.1 ID3决策树算法  27-30
  3.2 数据结构描述  30-32
  3.3 ID3算法的Homomorphisms描述  32-37
    3.3.1 决策树构造函数的描述  32-33
    3.3.2 样本分类判别函数的描述  33
    3.3.3 最大信息增益值属性选择函数描述  33-35
    3.3.4 数据集划分函数的描述  35-37
  3.4 小结  37-38
第四章新的高效决策树算法的演化  38-60
  4.1 程序演化策略  38-39
    4.1.1 Fusion演化策略  38
    4.1.2 Tupling演化策略  38-39
  4.2 基于样本分布元组的决策树构造函数演化  39-44
    4.2.1 样本分类判别函数的演化  40-41
    4.2.2 样本划分函数的推导  41-43
    4.2.3 新的基于样本分布元组的决策树构造函数  43-44
  4.3 基于样本分布树的决策树构造函数演化  44-55
    4.3.1 样本分布树的构造及描述  44-45
    4.3.2 样本划分函数的演化  45-47
    4.3.3 分布节点提升函数的构造  47-51
    4.3.4 基于样本分布树的决策树函数  51-55
  4.4 试验及分析  55-59
    4.4.1 新算法的正确性分析  55-56
    4.4.2 试验数据及描述  56-58
    4.4.3 试验结果及分析  58-59
  4.5 小结  59-60
第五章总结与展望  60-63
  5.1 总结  60
  5.2 展望  60-63
    5.2.1连续属性值的高效决策树研究  60-61
    5.2.2并行决策树算法研究  61
    5.2.3基于决策树的增量挖掘算法研究  61-63
参考文献  63-67
致谢  67-68
附录 A（攻读学位期间发表论文目录）  68

基于程序演化的决策树算法优化研究

内容摘要

全文目录

相似论文