文档介绍：决策树生成
基本思想:
用途:提取分类规则,进行分类预测
判定树分类算法
output
训练集
决策树
input
决策树示意图
使用决策树进行分类
决策树
一个树性的结构
内部节点上选用一个属性进行分割
每个分叉都是分割的一个部分
叶子节点表示一个分布
决策树生成算法分成两个步骤
树的生成
开始,数据都在根节点
递归的进行数据分片
树的修剪
去掉一些可能是噪音或者异常的数据
决策树使用: 对未知数据进行分割
按照决策树上采用的分割属性逐层往下,直到叶子节点
决策树算法
基本算法(贪心算法)
自上而下分而治之的方法
开始时,所有的数据都在根节点
属性都是种类字段(如果是连续的,将其离散化)
所有记录用所选属性递归的进行分割
属性的选择是基于一个启发式规则或者一个统计的度量(如, 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(s1,s2,……,sm)=-∑Pi log2(pi) (i=1..m)
其中,数据集为S,m为S的分类数目, Pi
Ci为某分类标号,Pi为任意样本属于Ci的概率, si为分类Ci上的样本数
由A划分为子集的熵:
E(A)= ∑(s1j+ ……+smj)/s * I(s1j+ ……+smj)
A为属性,具有V个不同的取值
信息增益:Gain(A)= I(s1,s2,……,sm) - E(A)
训练集(举例)
ID3算法