论文部分内容阅读
摘要 介绍了决策树的理论和算法，研究了决策树算法在数据挖掘中的应用实例，实验结果表明决策树是一种很有效的数据挖掘技术。
关键词 数据挖掘；决策树
Abstract The theory and algorithm of decision tree are introduced in the paper. The decision tree algorithm’s application case in data mining is researched. The experimental results indicate the decision tree is an effective data mining technique.
Key words Data mining； Decision tree
一、引言
数据挖掘是近年来计算机科学中的热点领域。决策树[1，2]是一种应用广泛的算法，在数据挖掘中占有重要的地位。本文介绍了决策树的理论和算法，研究了决策树算法在数据挖掘中的应用实例，实验结果表明决策树是一种很有效的数据挖掘技术。
二、决策树的理论和算法
决策树是一种逼近离散函数值的方法，是用于分类和预测的主要数据挖掘方法之一。作为以实例为基础的归纳学习算法，决策树能够对一组无次序、无规则的实例进行学习，从而推理出决策树表现形式的分类规则。
决策树是一种典型的分类方法，是研究如何利用树把一个复杂的多类分类问题转化为若干个简单的分类问题，从而较容易的表示和解决问题。决策树首先对数据进行处理，利用归纳算法生成可读的规则和决策树，通过利用树来转换问题，决策树算法可以很容易地得到if-then形式的分类规则，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
建立决策树的过程可以分为两个阶段。其中，第一阶段为建树，即通过使用训练数据集进行学习，从而导出决策树。决策树归纳的基本算法是贪心算法，它采用的是自项向下递归的各个击破方式来构建判定树。建立决策树的第二个阶段为剪枝。通过使用测试数据集对决策树进行验证。当建立的决策树无法正确分类时，就需要对决策树进行剪枝以便解决过度拟合训练集合的问题。剪枝阶段降低了由于训练集的噪声而产生的影响，从而建立一棵正确的决策树。在众多的决策树算法中，ID3和C4.5是最早研究的决策树算法。
具体的ID3算法如下：
用训练集R创建节点N；
If A为空
返回N为叶节点，标记为R中多数样本对应的类；
If N为属于同一个类
返回N为叶节点，标记为所有样本对应的类；
Else{
For每一个属性
估计选择a作节点的信息增益；
选出信息增益最大的属性a*作为当前节点；
根据a*的取值将R分裂为{Ri），并对决策树分叉；
For 每一个Ri
If Ri为空则返回叶结点；Else 执行ID3（Ri）；}
针对ID3算法不能直接处理连续型属性的不足， C4.5决策树算法进行了改进]，从而能够处理属性值空缺和连续型属性等应用。
作为数据挖掘领域中的经典算法，决策树算法与其它数据挖掘方法相比具有如下的显著优点：
（1）易于理解：决策树能够生成简单和易于理解的规则，能够清晰的显示哪些字段比较关键和重要，因此用户不需要了解很多决策树的背景知识。
（2）执行效率高：由于决策树计算量相对较小，而且容易转化成分类规则，只需要从树根向下一直到达叶子节点，沿途的分裂条件就能唯一确定一条分类的规则，因此较容易计算，执行速度快，分类效率非常高。
（3）准确性高：跟其它分类方法相比，决策树算法通常可以得到很好的分类准确性，因此利用决策树得到的分类规则能够较准确地对样本进行分类，可以较好的满足用户的的应用需要。
（4）具有很好的可伸缩性：决策树算法具有很好的可伸缩性，决策树算法不但可以应用到对小数据集进行数据挖掘，而且可对海量数据集进行数据挖掘。
三、应用实例
本文将决策树算法应用到sonar数据集上进行应用实例研究。sonar数据集是UCI数据库[3]中的一个数据集，它包括了61个属性，208个样本，2个类别。本文采用精度来衡量分类算法的性能。本文采用精度来衡量分类算法的性能。分类器对样本的分类结果有4种情况。
TP：被正确地分类为属于此类别的样本数量。
TN：被正确地分类为不属于此类别的样本数量。
FP：被错误地分类为属于此类别的样本数量。
FN：被错误地分类为不属于此类别的样本数量。
根据以上4种情况，分类性能可以按照精度来评价，精度的定义如下：
实验中也利用na?ve bayes算法对到sonar数据集进行了分类，并将其结果作为比较的基准。
四、结论
决策树算法是数据挖掘中的重要方法。本文介绍了决策树的理论和算法，研究了决策树算法在的一个数据挖掘应用实例，实验结果说明决策树算法是一种非常有效的算法。
参考文献：
[1] QUINLAN J. C4.5：Programs for Machine Learning[M].San Matteo，CA：Morgan Kaufm- ann Publishers，1993.
[2] 董跃华，刘力.基于相关系数的决策树优化算法.计算机工程与科学， 2015， 37（9）：1783-1793.
关键词 数据挖掘；决策树
Abstract The theory and algorithm of decision tree are introduced in the paper. The decision tree algorithm’s application case in data mining is researched. The experimental results indicate the decision tree is an effective data mining technique.
Key words Data mining； Decision tree
一、引言
数据挖掘是近年来计算机科学中的热点领域。决策树[1，2]是一种应用广泛的算法，在数据挖掘中占有重要的地位。本文介绍了决策树的理论和算法，研究了决策树算法在数据挖掘中的应用实例，实验结果表明决策树是一种很有效的数据挖掘技术。
二、决策树的理论和算法
决策树是一种逼近离散函数值的方法，是用于分类和预测的主要数据挖掘方法之一。作为以实例为基础的归纳学习算法，决策树能够对一组无次序、无规则的实例进行学习，从而推理出决策树表现形式的分类规则。
决策树是一种典型的分类方法，是研究如何利用树把一个复杂的多类分类问题转化为若干个简单的分类问题，从而较容易的表示和解决问题。决策树首先对数据进行处理，利用归纳算法生成可读的规则和决策树，通过利用树来转换问题，决策树算法可以很容易地得到if-then形式的分类规则，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。
建立决策树的过程可以分为两个阶段。其中，第一阶段为建树，即通过使用训练数据集进行学习，从而导出决策树。决策树归纳的基本算法是贪心算法，它采用的是自项向下递归的各个击破方式来构建判定树。建立决策树的第二个阶段为剪枝。通过使用测试数据集对决策树进行验证。当建立的决策树无法正确分类时，就需要对决策树进行剪枝以便解决过度拟合训练集合的问题。剪枝阶段降低了由于训练集的噪声而产生的影响，从而建立一棵正确的决策树。在众多的决策树算法中，ID3和C4.5是最早研究的决策树算法。
具体的ID3算法如下：
用训练集R创建节点N；
If A为空
返回N为叶节点，标记为R中多数样本对应的类；
If N为属于同一个类
返回N为叶节点，标记为所有样本对应的类；
Else{
For每一个属性
估计选择a作节点的信息增益；
选出信息增益最大的属性a*作为当前节点；
根据a*的取值将R分裂为{Ri），并对决策树分叉；
For 每一个Ri
If Ri为空则返回叶结点；Else 执行ID3（Ri）；}
针对ID3算法不能直接处理连续型属性的不足， C4.5决策树算法进行了改进]，从而能够处理属性值空缺和连续型属性等应用。
作为数据挖掘领域中的经典算法，决策树算法与其它数据挖掘方法相比具有如下的显著优点：
（1）易于理解：决策树能够生成简单和易于理解的规则，能够清晰的显示哪些字段比较关键和重要，因此用户不需要了解很多决策树的背景知识。
（2）执行效率高：由于决策树计算量相对较小，而且容易转化成分类规则，只需要从树根向下一直到达叶子节点，沿途的分裂条件就能唯一确定一条分类的规则，因此较容易计算，执行速度快，分类效率非常高。
（3）准确性高：跟其它分类方法相比，决策树算法通常可以得到很好的分类准确性，因此利用决策树得到的分类规则能够较准确地对样本进行分类，可以较好的满足用户的的应用需要。
（4）具有很好的可伸缩性：决策树算法具有很好的可伸缩性，决策树算法不但可以应用到对小数据集进行数据挖掘，而且可对海量数据集进行数据挖掘。
三、应用实例
本文将决策树算法应用到sonar数据集上进行应用实例研究。sonar数据集是UCI数据库[3]中的一个数据集，它包括了61个属性，208个样本，2个类别。本文采用精度来衡量分类算法的性能。本文采用精度来衡量分类算法的性能。分类器对样本的分类结果有4种情况。
TP：被正确地分类为属于此类别的样本数量。
TN：被正确地分类为不属于此类别的样本数量。
FP：被错误地分类为属于此类别的样本数量。
FN：被错误地分类为不属于此类别的样本数量。
根据以上4种情况，分类性能可以按照精度来评价，精度的定义如下：
实验中也利用na?ve bayes算法对到sonar数据集进行了分类，并将其结果作为比较的基准。
四、结论
决策树算法是数据挖掘中的重要方法。本文介绍了决策树的理论和算法，研究了决策树算法在的一个数据挖掘应用实例，实验结果说明决策树算法是一种非常有效的算法。
参考文献：
[1] QUINLAN J. C4.5：Programs for Machine Learning[M].San Matteo，CA：Morgan Kaufm- ann Publishers，1993.
[2] 董跃华，刘力.基于相关系数的决策树优化算法.计算机工程与科学， 2015， 37（9）：1783-1793.