论文导读：随着数据挖掘技术的逐步成熟，其算法的深入研究已成为当前该领域的焦点，决策树方法作为数据挖掘领域重要算法之一，在分类规则中突现了它的优势。决策树方法是从机器学习中引出的，它根据给定的训练样本数据集来构建分类模型，以树的形式来表达模型。建立决策树的经典算法是ID3算法，它可以被描述成一个递归的过程：首先，选择训练样本的一个属性作为节点，对该属性的每种可能的取值创建一个分枝，并据此训练样本划分为几个子集。
关键词：决策树，训练样本，ID3算法
随着数据挖掘技术的逐步成熟，其算法的深入研究已成为当前该领域的焦点，决策树方法作为数据挖掘领域重要算法之一，在分类规则中突现了它的优势。
1. 决策树方法概述
决策树方法是从机器学习中引出的，它根据给定的训练样本数据集来构建分类模型，以树的形式来表达模型。决策树的算法通常分为两个阶段：决策树的构建和决策树的修剪。模型建成后，对于树中每一类别的描述，形成分类规则。论文格式。
1.1决策树的表示形式
一般来说，决策树是一个类似于流程图的树结构，其中每个节点表示在一个属性上的测试，每个分枝代表一个测试输出，每个树叶节点代表类或类分布。决策树的最顶层节点是根节点。更明确地说，决策树通过根节点到叶节点的顺序对实例进行分类，其中每个节点代表一个属性，每个分枝代表它所连接的上节点在其属性上的可能取值。举例来说，一个实例的分类是从树的根节点开始，测试该节点所代表的属性，然后沿属性取值的某个分枝向下移动，不断重复这个过程，直至到达叶节点，即得到该实例所属的类。
1.2决策树的核心问题
建立决策树的目标是通过训练样本建立目标类变量关于各输入变量的分类预测模型，全面实现输入变量和目标变量在不同取值下的数据分组，进而用于新数据对象的分类和预测。当利用所建决策树对象进行分析时，决策树能够依据该数据输入变量的取值，推断成相应目标变量的分类或取值。
目前，从事机器学习的专家学者们仍在潜心研究这些算法的改进或寻找更有效的新算法。归纳起来，决策树算法主要围绕两个核心问题展开：第一，决策树的建立问题，即如何更快、更有效地利用样本数据建立决策树以及建立的决策树能容易地被现实世界所理解；第二，决策树的剪枝问题，即利用训练数据或检验数据对已建立的决策树进行优化处理，使最终的决策树大小适中。
1.3决策树方法的适用范围
决策树方法并不适用于现实世界中的所有问题，它需要满足下列条件时才能产生较优的结果。
首先，实例要用“属性-值”的形式描述。具体讲，实例是由一系列固定的属性（如：性别）和值（如：男）构成：属性的可能取值范围比较小（如：男、女）时，决策树的效果最好。
其次，目标类变量的可能取值是离散的。论文格式。决策树算法要求每个实例属于某个类，最简单的情况是只存在两个可能的目标类取值，当然也可以扩充到两个以上的可能取值。
最后，训练样本可以有错误。即决策树算法应是健壮的，不仅训练样本的目标类可以有错误，而且属性值也可以有错误。训练样本数据的某个属性可以包含缺失值。
2.建立决策树的基本算法
建立决策树的经典算法是ID3算法，它可以被描述成一个递归的过程：首先，选择训练样本的一个属性作为节点，对该属性的每种可能的取值创建一个分枝，并据此训练样本划分为几个子集。然后，对每个分枝采取相同的方法，训练样本是其父节点划分的若干子集中的对应于该分枝取值的那个样本子集。
当以下情况出现时停止该节点分枝的分裂，并使其成为叶节点：（1）该节点的所有训练样本属于同一分类；（2）每一剩余属性可以用来进一步划分样本；（3）该分枝没有样本。
此时，一棵完整的决策树便形成了。
该算法的核心是确定分枝准则，即如何从众多的属性变量中选择一个最佳的分裂属性。通常，在树的每个节点上使用信息增益度量选择属性，选择具有最高增益的属性作为当前节点的测试属性，该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性。这种理论方法使得对每一个对象分类所需的期望测试数目达到最小，并确保找到一棵简单的树。
3.决策树实际应用中的改进
前面所描述的算法是在数据十分理想的情况下进行的,而现实中的数据在多数情况下不能满足算法所要求的条件,这样就不能直接应用建立决策树的算法。因此,决策树算法在实际应用之前应在以下几个方面进行改进。
（1）连续型属性的处理
在实际应用中,除了离散型属性之外,还存在大量的连续型属性，而决策树算法处理的属性要求是离散型的,这就要求算法的扩展使之能够处理连续型属性。
对于连续型属性取值为相对集中的整数时,可以采取以下方法:首先,将连续型数据按照升序排列(重复的值被合并到一起)；其次,因为最大值不能作为分裂点,所以用基本算法计算其他每个属性值的信息增益,选择值最大的作为分裂点。由于给定的参照值相同,所以只需计算信息熵,选择熵值最小的即可；最后,将其属性值进行二分，一般情况下用中值作为分裂位置。对于连续型属性的取值为比较分散的实数时,可以采取划分区间的方法,将其映射为整数。
对离散型属性的分裂用到了该属性提供的所有信息,而对于连续型属性来说,后续的分裂还可以产生新的信息。从根节点到叶节点的一条路径上,一个离散型属性只能被分裂一次,而连续型属性可以进行多次分裂,从而产生一个杂乱且不易理解的树。因为对于某个连续型属性的分裂不是集中而是沿着这条路径分散进行的。一种替代的做法是对连续型属性进行多分枝的分裂,以便产生更易于理解的树,却难以实现。
（2）缺失值情况的处理
在建立决策树时,训练样本中缺失值的情况会经常出现。一种处理方法是将缺失值看作属性的一种可能的取值。如果在某种程度上该属性的缺失值情况很明显的话,这种处理方法很恰当;如果缺失值情况不明显的话,则需要更为复杂的解决方法。另一种缺失值处理方法是将缺失值的实例常常能够提供很多的信息。如果缺失值的属性根本没在决策中发挥作用,那么这些实例和其他没有缺失值的实例没有什么区别。
在将已有的决策树应用到一个属性有缺失值的测试实例时,首先看是否有缺失值的分枝,如果有的化,沿该分枝进行下去;如果没有的话,则需要将实例按照语义拆分。这可以通过加入权值来实现,即沿着每个分枝下去的部分要与该分枝训练实例的数量成正比，最终，被测试的每个部分都会到达一个叶节点，通过权值将它们再合并成一个最终的结果。
（3）决策树的剪枝
决策树的剪枝问题是决策树技术中的一个重要的部分。因为初始建立的决策树并不是一棵分析新数据对象的最佳决策树。这主要由于在建立决策树的过程中，每个分枝处理的训练样本数据随着层数的增加而迅速减少，其体现的数据特征也就更加具体，一般性更差，甚至可能出现一些荒谬的结论。解决这种问题的主要方法是对决策树进行必要的剪枝。
（4）从树中推导规则
决策树的规则是以IF-THEN形式表示的。产生规则的方法是：首先为每个叶节点产生一个规则，然后把从该叶节点路径上的所有条件合并，这样就产生了一条规则。其中，每个“属性-值”形成规则的IF部分的合取项，叶节点包含类预测，形成规则THEN部分。论文格式。规则的先后顺序并不影响其执行结果。
总之，决策树算法在分类规则中，通过训练样本数据集即可构建分类模型，但这并不适用于现实生活中的任何数据，所以，在不满足其条件时，应尽可能的创造条件，使其算法能够准确、快速的实施，使决策树方法能更好的为数据挖掘领域服务。
参考文献：
[1] 黎敏.数据挖掘算法研究与应用:[学位论文].大连:大连理工大学2005.
[2] 唐华松,姚耀文.数据挖掘中决策树算法的探讨.计算机应用研究,2008(8)
[3] 韩慧等.数据挖掘中决策树算法的最新进展.计算机应用研究,2008,12
|
