文档介绍：硕士学位论文

基于遗传算法的决策树优化算法研究
The Optimization Algorithm of Decision Trees Based on Genetic
Algorithm

作者姓名：张冬冬
学科、专业：计算数学
学号： 0211520
指导教师：李玉龙
完成日期： 2014-04

兰州交通大学
Lanzhou Jiaotong University
兰州交通大学硕士学位论文
摘要
随着网络技术和数据库管理系统的快速发展，不同领域的企业内部都积累了海量的
数据,这使得以往的数据分析工具和技术已经无法满足数据信息处理的需求，进而造成
数据资源的巨大浪费。于是如何寻找这些数据中所存在的巨大信息和知识，为企业所用，
成为人们关注的新视角。数据挖掘就是自动发现海量数据中隐含的、有潜在用途知识的
一种新技术。其中，分类和预测是一种重要的数据挖掘研究任务。
目前，决策树算法以其分类的准确率高、速度快、分类规则易于理解而作为数据挖
掘分类技术中最常用的方法，评价决策树性能好坏主要取决于决策树模型分类预测的准
确率和复杂度。作为经典的决策树分类算法，具有很好的分类精度（准确率），但
是由于其在树的构造过程中采用贪心算法，因此构造的决策树往往存在过度拟合，规模
过大等缺陷。而遗传算法是一种全局优化的智能搜索算法，具有潜在的并行性和可扩展
性，容易与其他算法相结合。因而，将遗传算法组合应用到决策树分类算法中，
通过两种不同的思路对决策树进行优化：
（1）通过深入分析决策树经典算法的基本原理，总结出该算法在平衡决策树
的分类精度和规模控制等方面的不足，从实用的角度提出了在构建决策树时应权衡好决
策树的分类精度和树的规模。针对遗传算法具有搜索全局最优的特点，第四章将遗传算
法直接用于决策树的优化，由于算法生成的决策树分类精度还是较高的，则先利
用算法生成初始的决策树种群，可以有效地避免遗传算法刚开始盲目的搜索，但
由于树的不易编码性，于是将初始种群中的决策树转换成相应的规则集，然后对规则集
进行编码，通过设定适当的适应度函数和遗传操作，从而得到优化后的决策树。
（2）在现实生活中，数据集中的属性对分类问题并不都是有效的，有些可能是不
相关、冗余的属性，因而在数据集进行分类之前，对属性集进行合理的约简具有很好的
研究价值。于是第五章提出利用遗传算法的全局寻优能力首先对数据的属性集进行约
简，借助粗糙集理论对适应度函数进行合理的构造，从而得到约简的分类属性组合，然
后对约简后的属性集再利用经典的分类算法构造相应的决策树，从而得到遗传属
性约简后相应的决策树。
最后，将以上两种优化方案分别通过天气样本数据集和经典的分类 UCI 数据集进行
测试，针对决策树分类的准确率、规则数目（叶子结点的个数）、分类属性的个数等方
面，通过和直接利用算法构造的决策树进行比较。实验结果表明，在一定的条件
下，遗传优化的决策树算法在不降低决策树分类精度的前提下，有效的减小了树的规模，
进而增加了分类规则的可读性。
- I -
基于遗传算法的决策树优化算法研究

关键词：数