决策树算法及应用拓展教材

n n
Public(S)算法(证明二)



题设：子树N有S个分裂点(Split),K个类 S+1个叶子节点 至多有S+1个主要类 至少有K-S-1个少数类 取Ci为某少数类,C(Sj)为编码叶子节点j上记录的代价 n ij n ij ( Sj ) n ij * E ( Sj ) n ij * * log C n ij n ij


两种剪枝标准

最小描述长度原则(MDL)

思想：最简单的解释最期望的 做法：对Decision-Tree 进行二进位编码， 编码所需二进位最少的树即为“最佳剪枝 树” 思想：选择期望错误率最小的子树进行剪 枝 对树中的内部节点计算其剪枝/不剪枝可能

期望错误率最小原则


Cost of Encoding Data Records
引入Public算法


一般做法：先建树，后剪枝 Public算法：建树的同时进行剪枝

思想：在一定量(用户定义参数)的节点分 裂后/周期性的进行部分树的剪枝 存在的问题：可能高估(Over-Estimate)被 剪节点的值 改进：采纳低估(Under-Estimate)节点代价 的策略
具体思路

I(s1,s2,……,sm)=－∑Pi log2(pi) (i=1..m) | Si |

其中，数据集为S，m为S的分类数目， Pi
|S |
Ci为某分类标号，Pi为任意样本属于Ci的概率， si为分类Ci上的样本数

由A划分为子集的熵： E(A)= ∑(s1j+ ……+smj)/s * I(s1j+ ……+smj)
决策树算法及应用拓展

内容简介：

概述 预备知识
决策树生成(Building Decision Tree) 决策树剪枝(Pruning Decision Tree)


捕捉变化数据的挖掘方法 小结
概述(一)

传统挖掘方法的局限性

只重视从数据库中提取规则，忽视了库中 数据的变化 挖掘所用的数据来自稳定的环境，人为干 预较少
Cost of Encoding Tree


编码树结构本身的代价 编码每个分裂节点的代价
确定分类属性的代价 确定分类属性值的代价 v log( 2 2 ) & log( v 1 ) 其中，v是该节点上不同属性值的个数


编码每个树叶上的记录分类的代价
剪枝算法


设N为欲计算其最小代价的节点 两种情形：

集合T包含N个类别的记录，那么其Gini指标就是 pj 类别j出现的频率 如果集合T分成两部分 N1 and N2 。那么这个分割的 Gini就是 N N 1 2
n gini ( T) 1 p2 j j 1

( T ) gini ( ) gini ( ) gini T T 1 2 split N N

N是叶结点——C(S)+1 ——Cost1 N是内部节点，有两个子节点N1、N2
已剪去N1、N2，N成为叶子节点 ——Cost1 计算N节点及其子树的代价，使用递归过程 Csplit(N)+1+minCost1+minCost2 ——Cost2 比较Cost1和Cost2，选取代价较小者作为返回 值
概述(二)

捕捉新旧数据变化的目的：

挖掘出变化的趋势

例：啤酒——尿布 例：金融危机——银行的信贷策略
阻止/延缓不利变化的发生


差异挖掘算法的主要思想：

合理比较新/旧数据的挖掘结果，并清晰的 描述其变化部分
预备知识一(Building Tree)


基本思想： 用途：提取分类规则，进行分类预测

计算最小子树代价的伪代码
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
Gain ( age ) I ( p , n ) E ( ag )
Compute the entropy for Similarly age: Gain ( income )0 .029 age pi ni I(pi, ni) Gain (student )0 .151 <=30 2 3 0.971 30…40 4 0 0 Gain (credit _rating )0 .048
input
训练集
判定树分类算法
output
决策树
使用决策树进行分类

决策树


一个树性的结构 内部节点上选用一个属性进行分割 每个分叉都是分割的一个部分 叶子节点表示一个分布
树的生成 开始，数据都在根节点 递归的进行数据分片 树的修剪 去掉一些可能是噪音或者异常的数据 按照决策树上采用的分割属性逐层往下，直到一个叶子节点
两个子节点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)+and N2 return minCostN
一个节点上的数据都是属于同一个类别 没有属性可以再用于对数据进行分割

停止分割的条件

伪代码(Building Tree)
Procedure BuildTree(S) 用数据集S初始化根节点R 用根结点R初始化队列Q While Q is not Empty do { 取出队列Q中的第一个节点N if N 不纯 (Pure) { for 每一个属性 A 估计该节点在A上的信息增益 选出最佳的属性，将N分裂为N1、N2 } }
属性选择的统计度量

信息增益——Information gain (ID3/C4.5)

所有属性假设都是种类字段 经过修改之后可以适用于数值字段 能够适用于种类和数值字段

基尼指数——Gini index (IBM IntelligentMiner)

信息增益度度量(ID3/C4.5)

任意样本分类的期望信息：

相关概念
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
Public(S)算法(证明一)

提供最小Ginisplit 就被选择作为分割的标准(对于每个 属性都要遍历所有可以的分割方法).
预备知识二(Pruning Tree)

目的：

消除决策树的过适应(OverFitting)问题 实质：消除训练集中的异常和噪声 先剪枝法(Public 算法) 后剪枝法(Sprint 算法)

两种方法：

对n条记录进行分类编码的代价(2种方法)
n k 1 n ! log( ) log k 1 n 1 ! nk !

ni k 1 n π C ( S ) ni * log log log n 2 2 Γ ( k / 2 ) i
n ——记录数，k ——类数目，ni——属于 类i的记录数 k / 2

决策树生成算法分成两个步骤



决策树使用: 对未知数据进行分割

决策树算法

基本算法（贪心算法）




自上而下分而治之的方法 开始时，所有的数据都在根节点 属性都是种类字段 (如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量 (如, information gain)
A为属性，具有V个不同的取值 信息增益：Gain(A)= I(s1,s2,……,sm) － E(A)

训练集(举例)
ID3算法
age <=30 <=30 30…40 >40 >40 >40 31…40 <=30 <=30 >40 <=30 31…40 31…40 >40 income student credit_rating high no fair high no excellent high no fair medium no fair low yes fair low yes excellent low yes excellent medium no fair low yes fair medium yes fair medium yes excellent medium no excellent high yes fair medium no excellent buys_computer no no yes yes yes no yes no yes yes yes yes yes no
i=s+2..k
While s+1<k and ns+2>2+log a do{ tmpCost=tmpCost+2+log a-ns+2
S++}
Return min{C(S)+1,tmpCost} }
Public(S)示例
age 16 Car type truck label high
1 N 1
编码具有类 i 且位于叶子节点 j 的记录的代价是nij 所有少数类的代价 Cost= ∑ni i∈少数类
又有
n
ni j
ij
2
C(S)> ∑nij
计算minCost_S的代码
Procedure computeMinCostS(Node N)
If k=1 return (C(S)+1) S=1 tmpCost=2*S+1+S*log a +∑i ni
>40 3 2 0.971
Decision Tree (结果输出)
age? <=30 overcast 30..40 yes yes yes >40
student?
no no
credit rating?
excellent no fair yes
基尼指数 Gini Index (IBM
IntelligentMiner)
计算子树代价下界


Public(1)

假设节点N的代价至少是1 计算以N为根且包含S个分裂点的子树代价 的下界(包括确定分裂节点属性的代价)
Public(S) S —— split


Public(V)

V ——split value
同上，还包括确定分裂节点值的代价
Public(S)算法(一)

证明：编码S+1个叶子节点的代价至少 为 ∑ ni i=s+2..k
相关概念：
1.主要类(Majority Class):if Ci , Ck C 有 ij kj ，则Ci为主要类 2.少数类(Minority Class): if Cj then C majority Cj为少数类

三种叶节点：

有待扩展：需计算子树代价下界 不能扩展(纯节点) C(S)+1 剪枝后的结点
改进算法的伪代码
Procedure ComputCoste&Prune(Node N)
If N是仍待扩展的结点，return N节点的代价下界 If N是纯节点或不可扩展的叶节点， return (C(S)+1)
N
1+log2 1+log2 1+log2 1+1
24
32 34
sports
sports truck
high
Medi low
[16,truck,high]
[16,truck,high] [65,family,low] [24,sports,high] [24,sports,high][34,truck,low] 1 1 [32,sports,medi] [32,sports,medi] [65,family,low]
使用信息增益进行属性选择


Class P: buys_computer = “yes”
Class N: buys_computer Hence = “no” I(p, n) = I(9, 5) =0.940
5 4 E (age ) I(2 ,3 ) I(4 ,0 ) 14 14 5 I(3 ,2 ) 0 .971 14