论文决策树算法综述是关于本文可作为相关专业决策树论文写作研究的大学硕士与本科毕业论文决策树例题经典案例280论文开题报告范文和职称论文参考文献资料。
摘 要：数据挖掘中一项重要的方法是数据的分类,而决策树是分类算法中一个主要的算法分支,决策树算法是我们在数据挖掘中常常会用到的一种方法.本文重点介绍构造决策树过程中应用最广泛的ID3算法、C4.5算法和GART算法.
关键词：数据挖掘；分类算法；决策树；ID3、C4.5、GART算法
1.引言
随着计算机技术的不断进步,现在已经是互联网时代,互联网时代背景下是海量的数据,在大数据背景下,我们需要对数据进行更高层次的分析,发现数据之前存在的一切潜在的联系及规则.而数据挖掘技术便是将这些看似毫无规则,毫无联系的数据进行预测分析,提取其中有用的信息的过程.
数据挖掘技术中常用的一种分类方法便是决策树.决策树是一个树结构,其每个非叶节点表示一个特征属性上的测试,每個分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别.运用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果.决策树的应用十分广泛,目前决策树成功运用于医学,制造产业、天文学、分支生物学以及商业等诸多领域.
2.决策树的基本思想
首先,树以代表训练样本的单个结点开始,选择最具有分类能力的属性作为决策树的当前结点.其次根据当前决策结点属性取值的不用,将训练样本数据集分为若干子集,每个取值形成一个分枝.针对上一步得到的一个子集,重复进行先前步骤,形成每个划分样本上的决策树,一旦一个属性出现在一个结点上,就不必在该结点的任何后代考虑它.
3.决策树的构造
决策树的构造主要有两个步骤：分裂属性的选择和树剪枝.
3.1分裂属性的选择
分裂属性的选择就是选择哪个自变量作为树杈,即在n个自变量中,优先选择哪个自变量进行分叉,而采用何种计算方式选择树杈决定了决策树算法的类型,典型的分裂属性的选择的方法有ID3算法、C4.5算法、CART算法三种,三种决策树算法选择树杈的方式是不一样的.
3.1.1 ID3算法
ID3算法是目前决策树算法中较有影响力的算法,它是1986年由Quinlan 提出的,该算法只是一个启发式算法.ID3算法的核心是判断测试哪个属性为最佳的分类属性.ID3算法选择分裂后信息增益最大的属性进行分裂,以信息增益度量属性选择.ID3算法中常用到的两个概念是熵和信息增益.
熵,是刻画任意样本例集的纯度,如果目标属性具有m个不同的值,那么D相对于m这个状态的分类的熵定义为：
[info（D）等于-i等于1mpilog2（Pi）]
其中Pi表示Pi是m类别的比例.
一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低,更精确来讲,一个属性A相对样本例集合S的信息增益Gain（S,A）被定义为：
gain（A）等于info（D）-infoA（D）
A对D划分的期望信息为；
[infoA（D）等于j等于1vDjDinfo（Dj）]
ID3算法不足之处是只能处理离散型数据,信息增益的选择分裂属性的方式会偏向选择具有大量值得属性.
3.1.2 C4.5算法
ID3算法在实际应用中存在一些问题,于是Quilan在保留ID3算法优点基础上提出了C4.5算法,C4.5算法只是ID3算法的改进算法.C4.5算法采用最大信息增益率的属性被选为分裂属性.C4.5算法中用到了“分裂信息”这一概念,该概念可以表示为：
[split_infoA（D）等于-j等于1vDjDlog2DjD]
信息增益率的定义是：
[gain_ratio（A）等于gainAsplit_info（A）]
C4.5算法是对ID3算法的一种改进,改进后可以计算连续型属性的值.对于连续型属性的值,只需将连续型变量由小到大递增排序,取相邻连个值的中点作为分裂点,然后按照离散型变量计算信息增益的方法计算信息增益,取其中最大的信息增益作为最终的分裂点.
C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进：用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足；在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整的数据进行处理.
3.1.3 GART算法
GART算法选择分裂属性的方式首先要计算不纯度,然后利用不纯度计算Gini指标,然后计算有效子集的不纯度和Gini指标,选择最小的Gini指标作为分裂属性.
不纯度的计算方式为：
[Gimi（D）等于1-i等于1MP2i]
Pi表示按某个变量划分中,目标变量不同类别的概率.某个自变量的Gini指标的计算方式如下：
[Gini（D）等于1-i等于1MP2i]
D1和D2分别为按变量的子集所划分出的两个不同元组.
3.2树的剪枝
即在构建树杈时,由于数据中的噪声和离群点,许多分支反映的是训练数据中的异常,而树剪枝则是处理这种过分拟合的数据问题,常用的剪枝方法为先剪枝和后剪枝.
3.2.1先剪枝
通过提前停止树的构造,如通过决定在给定的节点不再分裂或划分训练元组的子集,而对树剪枝,一旦停止,该结点即为树叶.
3.2.2后剪枝
它由完全生长的树剪去子树,通过删除节点的分支,并用树叶替换它而剪掉给定节点的子树,树叶用被替换的子树种最频繁的类标记.
其中C4.5使用悲观剪枝方法,CART采用后剪枝.
总结
数据挖掘中比较热门的就是分类算法的研究,而决策树算法是分类算法中最重要的,在我们的生活中也有着广泛的应用,本文介绍了从最基本的决策树的含义开始定义,到决策树的基本思想,最后介绍了决策树中经典的ID3算法、C4.5算法和CART算法.
参考文献：
[1]韩家炜.数据挖掘：概念与技术第二版[M].北京：机械工业出版社,2001.
[2]王艳兵,赵锐,姚青.基于可变精度的 ID3 改进算法[J].计算机工程与设计,2006,27（14）：2683-2685.
[3]韩松来,张辉,周华平.基于关联度函数的决策树分类算法[J],计算机应用,2005,25（11）：2655-2657.
[4]Quinlan J R. Introduction of Decision Tree[J].Machine Learning, 1986.
[5]谢金梅,王艳妮.决策树算法综述[J].软件导报,2008,7（11）： 83-85.
作者简介：
田欣（1992.02- ）,女,汉族,河北石家庄人,硕士研究生在读,现就读于河北大学管理学院,管理科学与工程专业.
总结:本文关于决策树论文范文,可以做为相关论文参考文献,与写作提纲思路参考。
参考文献：
1、 探究决策树法在工程项目中应用 摘 要：现代科学技术的迅猛发展和人文观念的逐步完善，都影响着人们对目标的选择和规划。在现代工程项目中招投标已经在全国全面的推行，并且以完善的制度。
2、 基于支持向量机和决策树CART的个人信用评估 摘要：为了更好地控制借款人的信用风险，利用支持向量机对个人信用进行预测与分析，在支持向量机对个人信用评估产生缺陷的基础上提出基于代价敏感学的CA。
3、 修改雅可比改进算法综述 摘 要：本文主要叙述改进潮流算法程序设计的主要步骤：主要叙述雅可比矩阵以及修改雅可比矩阵改进算法的形成过程和步骤，在进行第一次迭代计算的时候，使。
4、 基于决策树分类济宁市土壤有机碳遥感反演 摘要：本研究利用Landsat 8遥感影像数据以及土壤有机碳实测数据，以研究区表层0～20 cm土壤的有机碳含量为研究对象，通过SPSS的多元线。
5、 基于决策树验证的属性约简方法 摘要：属性约简能够有效地减少冗余，同时，通过约简去除对预测结果贡献极小的属性能够有效地提高分类精度。提出了一种属性约简方法，该方法在分类前对现有。
6、 基于决策树的学生成绩对毕业影响分析 摘要：高校生源质量的下降使得学生顺利毕业问题成为关注的焦点，该文以温州商学院会计学专业学生的毕业情况为例，运用决策树分类技术对学生的成绩进行综合。