五种决策树算法的比较研究

论文摘要

决策树分类算法是数据挖掘领域中最为广泛研究和应用的一个课题,其优点是计算量小、速度快、分类准确率高、分类规则容易理解。目前经典的决策树算法有ID3、CART、C4.5、SLIQ等。为了解决连续属性以及数据中存在的不确定性等问题,模糊决策树应运而生。不同算法产生的决策树,在测试数据上的准确率、树的繁简程度等方面都有所不同。本文针对五种决策树算法,从分类的准确率、树的复杂程度（即生成树的叶子节点个数）、模糊决策树对连续属性的模糊化方法、分裂属性的选择方法以及决策树对样本空间划分的相似程度五个方面,在十七个UCI数据集上进行了详细的实验比较。对分类准确率的比较,我们应用了统计比较方法——Friedman测试方法。在对决策树的评价中,分类规则集的稳定性往往被忽略,即在多次实验中,我们得到的分类规则集对样本空间的划分是否相似及其相似程度如何,这样的问题往往不被重视。因此,本文提出了一种衡量决策树对样本空间划分的相似程度的评价方法,其主要目的是衡量某种决策树自身分类能力的稳定性和不同决策树分类能力的相似性。通过新视角去观测不同方法的异同,为我们“相信”分类结果、评价分类结果的稳定性以及解决不同问题选择不同算法提供了一个有意义的探索。本文将C4.5、CART、Fuzzy ID3、FS-DT和Yuan’s FDT五种决策树算法应用于UCI数据库的十七组数据集。实验结果表明,在统计意义下Fuzzy ID3的分类结果好于FS-DT,而CART的分类规则是最少的。在几组稳定性实验中,本文所定义的相似性概念给出了准确、合理的相似性值。通过比较发现,分类器的相似性往往依赖于分类器本身的特性及其所应用的数据集,分布混乱的数据更容易导致较低的相似性,这种规律在多个分类器上都有体现。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 本文研究内容
• 1.4 本文组织结构
• 2 决策树算法介绍及其评价标准
• 2.1 决策树算法介绍
• 2.1.1 决策树的定义
• 2.1.2 决策树算法描述
• 2.1.3 决策树算法的优缺点
• 2.1.4 模糊决策树算法描述
• 2.2 常见决策树算法简介
• 2.2.1 C4.5算法
• 2.2.2 CART算法
• 2.2.3 Fuzzy ID3算法
• 2.2.4 FS-DT算法
• 2.2.5 Yuan's FDT算法
• 2.2.6 SPRINT算法
• 2.2.7 PUBLIC算法
• 2.2.8 CHAID算法
• 2.3 不同决策树算法优劣的评价标准
• 3 五种决策树算法的对比研究
• 3.1 分裂属性选择方法
• 3.1.1 C4.5分裂属性选择方法
• 3.1.2 CART分裂属性选择方法
• 3.1.3 Fuzzy ID3分裂属性选择方法
• 3.1.4 FS-DT分裂属性选择方法
• 3.1.5 Yuan's FDT分裂属性选择方法
• 3.1.6 五种决策树算法分裂属性的对比研究
• 3.2 三种模糊决策树连续属性的模糊化方法
• 3.2.1 Fuzzy ID3对连续属性的模糊化方法
• 3.2.2 FS-DT对连续属性的模糊化方法
• 3.2.3 Yuan's FDT对连续属性的模糊化方法
• 3.2.4 三种模糊决策树模糊化方法的对比研究
• 3.3 分类准确率
• 3.4 叶子节点的多少
• 3.5 样本空间划分的相似程度
• 3.5.1 相似性的重要性
• 3.5.2 相似性的定义
• 3.5.3 与其它一致性评价方法的对比
• 4 决策树算法在不同数据集上的实验比较
• 4.1 数据集介绍
• 4.2 实验建立
• 4.3 比较结果分析
• 4.3.1 准确率比较
• 4.3.2 叶子节点比较
• 4.3.3 相似性比较
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢