文档介绍：决策树算法及应用拓展
第1页，此课件共41页哦
概述(一)
传统挖掘方法的局限性
只重视从数据库中提取规则，忽视了库中数据的变化
挖掘所用的数据来自稳定的环境，人为干预较少
第2页，此课件共41页哦
概述(二)
捕捉想：最简单的解释最期望的
做法：对Decision-Tree 进行二进位编码，编码所需二进位最少的树即为“最佳剪枝树”
期望错误率最小原则
思想：选择期望错误率最小的子树进行剪枝
对树中的内部节点计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍
第15页，此课件共41页哦
Cost of Encoding Data Records
对n条记录进行分类编码的代价(2种方法)
n ——记录数，k ——类数目，ni——属于类i的记录数
第16页，此课件共41页哦
Cost of Encoding Tree
编码树结构本身的代价
编码每个分裂节点的代价
确定分类属性的代价
确定分类属性值的代价
&
其中，v是该节点上不同属性值的个数
编码每个树叶上的记录分类的代价
第17页，此课件共41页哦
剪枝算法
设N为欲计算其最小代价的节点
两种情形：
N是叶结点——C(S)+1 ——Cost1
N是内部节点，有两个子节点N1、N2
已剪去N1、N2，N成为叶子节点 ——Cost1
计算N节点及其子树的代价，使用递归过程
Csplit(N)+1+minCost1+minCost2 ——Cost2
比较Cost1和Cost2，选取代价较小者作为返回值
第18页，此课件共41页哦
计算最小子树代价的伪代码
Procedure ComputeCost&Prune(Node N)
if N 是叶子节点，return (C(S)+1)
minCost1= Compute&Prune(Node N1)
minCost2= Compute&Prune(Node N2)
minCostN=min{C(S)+1,Csplit(N)+1+minCost1
+minCost2}
if minCostN=C(S)+1 Prune child nodes N1 and N2
return minCostN
第19页，此课件共41页哦
引入Public算法
一般做法：先建树，后剪枝
Public算法：建树的同时进行剪枝
思想：在一定量(用户定义参数)的节点分裂后/周期性的进行部分树的剪枝
存在的问题：可能高估(Over-Estimate)被剪节点的值
改进：采纳低估(Under-Estimate)节点代价的策略
第20页，此课件共41页哦
具体思路
三种叶节点：
有待扩展：需计算子树代价下界
不能扩展(纯节点)
剪枝后的结点
C(S)+1
第21页，此课件共41页哦
改进算法的伪代码
Procedure ComputCoste&Prune(Node N)
If N是仍待扩展的结点，return N节点的代价下界
If N是纯节点或不可扩展的叶节点， return (C(S)+1)
两个子节点N1、N2
minCost1= Compute&Prune(Node N1)
minCost2= Compute&Prune(Node N2)
minCostN=min{C(S)+1,Csplit(N)+1+minCost1
+minCost2}
if minCostN=C(S)+1 Prune child nodes N1 and N2
return minCostN
第22页，此课件共41页哦
计算子树代价下界
Public(1)
假设节点N的代价至少是1
Public(S) S —— split
计算以N为根且包含S个分裂点的子树代价的下界(包括确定分裂节点属性的代价)
Public(V) V ——split value
同上，还包括确定分裂节点值的代价
第23页，此课件共41页哦
Public(S)算法(一)
相关概念
第24页，此课件共41页哦
Public(S)算法(二)
定理：
任何以N为根结点且有S个分裂点的子树的代价至少是2*S+1+S*log a+∑ ni i=s+2..k
证明：
编码树结构代价 2*S+1
确定节点分裂属性的代价 S*log a
编码S+1个叶子结点的代价 ∑ ni i=s+2..k
第25页，此课件共41页哦
Public(S)算法(证明