决策树算法及其应用(ppt 41页)

决策树算法及其应用目录：
1、概述
2、预备知识
3、捕捉变化数据的挖掘方法
4、小结

 

决策树算法及其应用内容提要：
决策树算法：
基本算法（贪心算法）
自上而下分而治之的方法
开始时，所有的数据都在根节点
属性都是种类字段 (如果是连续的，将其离散化)
所有记录用所选属性递归的进行分割
属性的选择是基于一个启发式规则或者一个统计的度量 (如, information gain)
停止分割的条件
一个节点上的数据都是属于同一个类别
没有属性可以再用于对数据进行分割
……

两种剪枝标准：
最小描述长度原则(MDL)
思想：最简单的解释最期望的
做法：对Decision-Tree 进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”
期望错误率最小原则
思想：选择期望错误率最小的子树进行剪枝
对树中的内部节点计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍
……

算法比较：
Sprint: 传统的二阶段“构造－剪枝”算法
Public(1):用保守的估计值1取代欲扩展节点的代价下界
Public(S):考虑具有分裂点的子树，同时计算为确定分裂节点及其属性的代价下界
Public(V):比前者准确，需计算确定结点上属性值的代价下界

 

..............................