文档介绍：决策树算法及应用拓展
内容简介：
概述
预备知识
决策树生成(Building Decision Tree)
决策树剪剪枝(Pruning Decision Tree)
捕捉变化化数据的挖掘方法
小结
概述(一)
传统挖掘方法的局限性
只重视从数据库中提取规则，忽视了库中
数据的变化化
挖掘所用的数据来自稳定的环境，人为干
预较少
概述(二)
捕捉新旧数据变化化的目的：
挖掘出变化化的趋势势
例：啤酒——尿布
阻止/延缓不利变化化的发生
例：金融危机——银行的信贷策略
差异挖掘算法的主要思想：
合理比较新/旧数据的挖掘结果，并清晰的
描述其变化化部分
预备知识一(Building Tree)
基本思想：
用途：提取分类规则，进行分类预测
input output
判定树分类算法
训练集决策树
使用决策树进行分类
决策树
一个树性的结构
内部节点上选用一个属性进行分割割
每个分叉都是分割割的一个部分
叶子节点表示一个分布
决策树生成算法分成两个步骤
树的生成
开始，数据都在根节点
递归的进行数据分片
树的修剪剪
去掉一些可能是噪音或者异常的数据
决策树使用: 对未知数据进行分割割
按照决策树上采用的分割割属性逐层往下，直到到一个叶子节点
决策树算法
基本算法（贪心算法）
自上而下分而治之的方法
开始时，所有的数据都在根节点
属性都是种类字段 (如果是连续的，将其离散化化)
所有记录用所选属性递归的进行分割割
属性的选择是基于一个启启发式规则或者一个统计的度量
(如, information gain )
停止分割割的条件
一个节点上的数据都是属于同一个类别
没有属性可以再用于对数据进行分割割
伪代码(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/)
所有属性假设都是种类字段
经过修改之后可以适用于数值字段
基尼指数—— Gini index (IBM IntelligentMiner)
能够适用于种类和和数值字段
信息增益度度量(ID3 /)
任意样本分类的期望信息：
I(s 1,s 2,……,sm)= －∑Pi log 2(p i) (i=1..m) | Si |
其中，数据集为S，m为S的分类数目， Pi≈
| S |
Ci 为某分类标号，Pi为任意样本属于Ci 的概
率， si为分类Ci 上的样本数
由A划分为子集的熵：
E(A)= ∑(s1j + ……+smj )/ s * I( s1j + ……+smj )
A为属性，具有V个不同的取值
信息增益：Gain(A)= I(s1,s2,……,sm) － E(A)
训练集(举例)
age income student credit_rating buys_computer
ID3 算法 <=30 high no fair