文档介绍：第卷第期赤峰学院学报科学教育版..
年月& .
决策树算法及其改进算法研究
常州信息职业技术学院,江苏常州
摘要:本文主要研究决策树算法及其改进算法,阐述了算法的基本思想及存在的不足,并由此引出根据
算法中的信息增益计算原理的特点,利用凸函数的性质简化信息增益的计算,提高了算法中信息增益的计算效率。
关键词:算法;改进;成绩
中图分类号: 文献标识码: 文章编号:———
算法基本思想算法的优缺点
算法是由提出的一种归纳学****算法,它可算法通过不断的循环处理,直到找到一棵完全正确
以从一个训练例子集合中归纳出知识,抽取出的知识以决的决策树,并从顶向下归纳形成了一组类似的规
策树的形式表示。该算法的核心用信息的增益率作为选择则。
属性的标准,并且是在决策书树上的哥哥结点上进行测验, . 优势:
能获得最大的信息类别。期望该非叶结点到达各后代叶结.. 容易生成一组类似的规则,虽然看起来复
点的平均路径最短,使生成的决策树平均深度较小,提高分杂,但是很容易理解路径含义。
类速度和准确率。.. 不是逐个考虑数据,有效降低噪音。
信息增益是基于信息论中嫡的概念。熵是对事件对应.. 没有无解风险,所有目标函数都在搜索空间。
的在信息论中,熵表示的是不确定性的量度。由信息论的创. 劣处:
始人在著作《通信的数学理论》中提出、建立在概.. 对噪声比较的敏感。
率统计模型上的信息度量。他把信息定义为“用来消除不确.. 由于很多时候取值较多的属性往往不是最核心的属
定性的东西”。性,而算法却选择取值较多的属性;例如:在进行某单
设是个数据样本的集合,假定类标号属性具有位系统客户分析中,名字属性取值最多,但是却从中得不到
个不同值,定义个不同类一,。设是类中的任何信息。
样本数。相关定义如下: .. 当训练集增加时,决策树也随之变化,决策树对
对一个给定的样本分类所需的期望信息由下式给定: 训练集变化的敏感性引起了决策树算法的不稳定的问题。
这种不稳定的现象也使分类中知识发现的过程更加复杂。
,⋯,’。
: 总的来说,算法理论清晰,方法简单,学****能力较
。的概率,一般可用/来估强,适于处理大规模的学****问题。
计。算法改进
设属性具有个不同值。可用属性将划分为. 函数的凹凸性
个子集,⋯;其中包含中这样一些样本,它们在定理设在,】上连续,在内具有一阶和二
上具有值。如果选择作为测试属性,则这些子集就是从阶导数,那么
代表样本集的节点生长出来的新的叶子节点。设是子若在内,,则在,上的图形是凹的;
集中类别为的样本数,则根据划分样本的信息熵由若在内,.。,则在上的图形是凸的。
下式给出: 性质若在区间上是凸函数,∈,∈
,,则有:
∑【’⋯,
; 一≤【一
性质若是区间上的凸函数,则,:,⋯,∈,
其中,⋯,一;音是中类为的
’。,,⋯,,:⋯。,贝有’
样本的概率。最后用属性划分样本集后所得的信息增⋯≤‘一。.【
益值由下式给出: . 改进算法的基本思想
⋯, 信息量计算公式中所用的函数中,代表某一类
一一
记录数占记录数的百分比,定义域为,】,并且当,】上任信息量改变后引起信息熵计算公式修改