属性选择的统计度量
❖ 信息增益——Information gain (ID3/C4.5)
所有属性假设都是种类字段 经过修改之后可以适用于数值字段
❖ 基尼指数——Gini index (IBM IntelligentMiner)
能够适用于种类和数值字段
信息增益度度量(ID3/C4.5)
❖ 任意样本分类的期望信息：
gin(iT) 1
n
p2j
j1
❖ 如果集合T分成两部分 N1 and N2 。那么这个分割的
Gini就是 gisn p(T l) ii tN N 1gi(T n 1 ) iN N 2gi(T n 2 )i
❖ 提供最小Ginisplit 就被选择作为分割的标准(对于每个 属性都要遍历所有可以的分割方法).
编码所需二进位最少的树即为“最佳剪枝树”
❖ 期望错误率最小原则
思想：选择期望错误率最小的子树进行剪枝 对树中的内部节点计算其剪枝/不剪枝可能
出现的期望错误率，比较后加以取舍
Cost of Encoding Data Records
❖ 对n条记录进行分类编码的代价(2种方法)
lon g (k1)logn !
>40 medium no fair
>40 low
yes fair
>40 low
yes excellent
31…40 low
yes excellent
<=30 medium no fair
<=30 low
yes fair
>40 medium yes fair
<=30 medium yes excellent
age:
Similarly
age <=30
pi ni I(pi, ni) 2 3 0.971
Gai(inncom )e0.029 Gai(sntude)nt0.151
30…40 4 0 0
>40
3 2 0.971
Gai(cnred_irt atin)g0.048
Decision Tree (结果输出)
预备知识二(Pruning Tree)
❖ 目的：
消除决策树的过适应(OverFitting)问题 实质：消除训练集中的异常和噪声
❖ 两种方法：
先剪枝法(Public 算法) 后剪枝法(Sprint 算法)
两种剪枝标准
❖ 最小描述长度原则(MDL)
思想：最简单的解释最期望的 做法：对Decision-Tree 进行二进位编码，
age?
<=30 student?
o3v0e.r.c4a0st
yes
>40 credit rating?
no
yes
no
yes
excellent
fair
no
yes
基尼指数 Gini Index (IBM
IntelligentMiner)
❖ 集合T包含N个类别的记录，那么其Gini指标就是
pj 类别j出现的频率
(如, 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 } }
31…40 medium no excellent
31…40 high
yes fair
>40 medium no excellent
buys_computer no no yes yes yes no yes no yes yes yes yes yes no
使用信息增益进行属性选择
Class P: buys_computer = “yes”
概述(一)
❖ 传统挖掘方法的局限性
只重视从数据库中提取规则，忽视了库中数据的 变化
挖掘所用的数据来自稳定的环境，人为干预较少
概述(二)
❖ 捕捉新旧数据变化的目的：
挖掘出变化的趋势
❖例：啤酒——尿布
阻止/延缓不利变化的发生
❖例：金融危机——银行的信贷策略
❖ 差异挖掘算法的主要思想：
合理比较新/旧数据的挖掘结果，并清晰的描述其 变化部分
Class N: buys_computer = “no”
E(age) 5 I(2,3) 4 I(4,0)
14
14
5 I(3,2) 0.971 14
Hence
I(p, n) = I(9, 5) =0.940 G( a a ) g iI(p n e ,n ) E ( a)g
Compute the entropy for
❖A为属性，具有V个不同的取值 ❖信息增益：Gain(A)= I(s1,s2,……,sm) － E(A)
训练集(举例)
ID3算法
age income student credit_rating
<=30 high
no fair
<=30 high
no excellent
30…40 high
no fair
I(s1,s2,……,sm)=－∑Pi log2(pi) (i=1..m)
❖其中，数据集为S，m为S的分类数目， Pi
| Si
|
|S |
❖Ci为某分类标号，Pi为任意样本属于Ci的概率，
si为分类Ci上的样本数 由A划分为子集的熵：
❖E(A)= ∑(s1j+ ……+smj)/s * I(s1j+ ……+smj)
树的生成 ❖ 开始，数据都在根节点 ❖ 递可能是噪音或者异常的数据
❖ 决策树使用: 对未知数据进行分割
按照决策树上采用的分割属性逐层往下，直到一个叶子节点
决策树算法
❖ 基本算法（贪心算法）
自上而下分而治之的方法 开始时，所有的数据都在根节点 属性都是种类字段 (如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量
预备知识一(Building Tree)
❖ 基本思想： ❖ 用途：提取分类规则，进行分类预测
input
output 判定树分类算法
训练集
决策树
使用决策树进行分类
❖ 决策树
一个树性的结构 内部节点上选用一个属性进行分割 每个分叉都是分割的一个部分 叶子节点表示一个分布
❖ 决策树生成算法分成两个步骤