数据挖掘算法分析与实践C4.5决策树算法(2)

菜单

2.1决策树算法 5

2.2 ID3算法 6

2.2.1 ID3算法的优点 6

2.2.2 ID3算法的不足 6

2.3 C4.5算法 7

3、算法分析 7

3.1 C4.5算法基本介绍 7

3.2 C4.5算法流程 8

3.3 C4.5算法举例 10

3.3.1数据预处理 11

3.3.2决策树生成 13

3.4研究意义 15

4、总结与发展 16

参考文献 17

致谢 17

1、引言

在流失客户分析、企业投资风险分析、设备建造寿命预测等众多管理问题中，数据挖掘分类方法被普遍的使用。我们现在所处的环境中处处都存在着数据，处处都可以利用对数据的分析分类来寻求解决方案。对于数据的分析已经成为我们提高工作效率、降低投资风险必不可少的需求。然而，在这些问题中，由于数据收集的存在问题，不同类别的样本可能在某些属性具有相似的数据，这将导致对数据的分类效果不佳 ^([1])。

分类是一种分析数据的重要形式，它是刻画数据的重要模型。这种分类方式被称为分类器，可以预测离散、无序数据和其他类型数据。例如，可以建立一个分类模型，把银行贷款风险分成安全或危险等不同情况，这种分析方法可以帮助我们全面地理解数据。现在有许多种分类和预测方法已经被机器学习、模式识别和统计学方面的研究人员提出 ^([2])。

决策树是一种预测模型算法，它将大量数据进行有目的分类，从中找到最有用的信息为决策者提供判断的标准，是最常使用的一种分类方法。所以，研究决策树生成的算法就十分的重要。而且在钻研算法的过程中，会存在着大量复杂和不确定的影响因素，很难用精确建模的方法建立适用于数据分析过程中的数学模型，但是数据挖掘与人工智能理论的发展使得人们可以利用各类影响数据建立模型，从而将数据进行分类，做出较为正确的决策，减少决策的风险性。

2、算法介绍

2.1决策树算法

决策树以流程图的形式展示，最终构造出树形结构，内部的每一个节点表示一个属性值，即影响计算结果的各个因素中选择出来的，每一个节点就代表了一种分类情况，也就是每个分支就是每个元组的测试结果，树的最上方的节点是根节点，也是决策树的开始点，同时也是对决策结果影响最大的属性值。

决策树生成有两个阶段：构造决策树和决策树剪枝。决策树的生成采用自顶向下的递归方式：按照给定的计算方式计算出每个影响因素的测试属性，从而确定树中的每个节点，也就是构成树的各个节点的确定，然后再计算出其他选择属性集的所有可能值，来确定下一节点，直到所有的样本都可以在某一个叶节点被划分到一个类别中。在这一阶段的关键的操作是在选择树的节点时需要选择计算结果最高的测试属性值，该属性可以将训练样本进行最高划分的结果。测试属性的选择标准可以根据信息增益、基尼指数以及基于距离的划分等数据来决定。

2.2 ID3算法

ID3 算法是 1986 年由罗斯昆（J. Ross Quinlan）提出的一种基于信息熵作为标准的决策树算法。它是在60和70年代的推理体系和概念学习系统的坚实基础上建立的。罗斯昆把香农的信息论引入到了决策树算法的计算中，在选择影响决策树结果的各级节点时，ID3 算法运用信息熵理论，采用当前样本中拥有最大信息增益值的属性作为测试属性，即该测试属性为决策树的根节点，再计算其他属性的信息增益的值来建立树的分支，对各分支的子集进行递归调不断地建立决策树叶节点，直到所有的子集都只被划分到同一类的数据为止。最终就会得到一棵决策树，可以将所有的样本数据进行分类 ^([3])。