决策树算法及应用
决策树算法及应用
数
一 决策树算法简介
[1][6
]
[8]
决策树算法是一种归纳分类算法,它通过对训练集的学习,挖掘出有用的规则,用于对新集
进行预测.决策树算法可设计成具有良好可伸缩性的算法,能够很好地与超大型数据库结合,处
理相关的多种数据类型,并且,其运算结果容易被人理解,其分类模式容易转化成分类规则。因
此,在过去的几十年中,决策树算法在机器学习(machine learning)和数据挖掘( data mining)
领域一直受到广泛地重视.
决策树算法以树状结构表示数据分类的结果。树的非叶结点表示对数据属性(at tribute)
的测试.每个分枝代表一个测试输出,而每个叶结点代表一个分类。由根结点到各个叶结点的路
径描述可得到各种分类规则。目前有多种形式的决策树算法。其中最值得注意的是 CART 和 ID3/
C4. 5 。许多其它的算法都是由它们演变而来。下面介绍决策树算法 ID3 (Quinlan ,1979) 在
实际中的一例应用.
决策树算法 ID3 使用信息增益( Information Gain)作为选择属性对节点进行划分的指标。
信息增益表示系统由于分类获得的信息量,该量由系统熵的减少值定量描述。熵(Entropy) 是
一个反映信息量大小的概念。最终信息增益最高的划分将被作为分裂方案。
决策树和决策规则是实际应用中分类问题的数据挖掘方法。决策树表示法是应用最广泛的
逻辑方法,它通过一组输入-输出样本构建决策树的有指导的学习方法。
对于分类决策树来说,需要先对原始资料来进行分类训练,经由不断的属性分类后,得到
预期的分类结果.判定树归纳的基本算法是贪心算法,它采用自上而下、分而治之的递归方式来
构造一个决策树。ID3 算法是一种著名的判定树归纳算法,伪代码如下:
Function Generate_decision_tree(训练样本 samples,候选属性 attribute
list){
评论0
最新资源