分类与决策树[1]
信息熵 （ Entropy）
Pj 是数据集合中类别j的相对比例. entropy =
什么情况下，熵最小？ 什么情况下，熵最大？
entropy = - 1 log21 - 0 log20 = 0
目标变量为二元变量： entropy = -0.5 log20.5 – 0.5 log20.5 =1
No
Yes
13 Old
Yes
No
14 Old
Yes
No
15 Old
No
No
Fair
No
Good
No
Good
Yes
Fair
Yes
Fair
No
Fair
No
Good
No
Good
Yes
Excellent Yes
Excellent Yes
Excellent Yes
Good
Yes
Good
Yes
Excellent Yes
Age
Young
Middle
Old
Yes:2 No:3
Yes：3 No:2
Yes:4 No:1
裂分后数据集的熵EntropyAge(T)= 5/15* Entropy(T1)+ 5/15* Entropy(T2)+ 5/15* Entropy(T3) = 5/15*(− 3/5*log2(3/5) − 2/5*log2(2/5) )+
1 Young No
No
2 Young No
No
3 Young Yes
No
4 Young Yes
Yes
5 Young No
No
6 Middle No
No
7 Middle No
No
8 Middle Yes
Yes
9 Middle No
Yes
10 Middle No
Yes
11 Old
No
Yes
12 Old
分类与决策树[1]
信息增益
Information Gain = 裂分前数据集的熵 – 裂分后各子数据集的熵
加权和 其中：权重为每个子集中的观测数在裂分前总
观测数中所占的比例
分类与决策树[1]
案例数据集基于own_home属性划分
ID Age
Has_job Own_home Credit
Class
Yes
No
Yes
Excellent
Yes
No
Yes
Good
Yes
Yes
No
Good
Yes
Yes
No
Excellent
Yes
No
No
Fair
No
分类与决策树[1]
分类与预测
• 分类：
– 目标变量为非数值型
• 预测：
– 目标变量为数值型
• 根据历史数据集（已知目标变 量），构建模型描述目标变量 与输入变量之间的关系，并依 据模型来分类或预测新数据（ 目标变量值未知)。 分类模型也称为分类器。
建模
模型评估
规则1：If refund=no and
marst=married then cheat=no
……
模 型
应
用
分类与决策树[1]
分类的过程
•数据集分区
– 训练集：建立模型 – 验证集：调整和选择模型 – 测试集：评估模型的预测能力
•建立模型 •评估并选择模型 •运用模型
新数据（打分集）
思考：分类模型在什么情况下不适合用于新数据？
银行贷款申请 Has_job
Own_home
Credit
Class
No
No
Fair
No
No
No
Good
No
Yes
No
Good
Yes
Yes
Yes
Fair
Yes
No
No
Fair
No
No
No
Fair
No
No
No
Good
No
Yes
Yes
Good
Yes
No
Yes
Excellent
Yes
No
Yes
Excellent
Class
No No Yes Yes No No No Yes Yes Yes Yes Yes Yes Yes No
银行贷款案例数据集的熵：
Entropy(T)=−6/15*log2(6/15) − 9/15*log2分(9类/与1决5策)=树0[1.]971
Gini 指数
Pj 是数据集合中类别j的相对比例.
分类与决策树[1]
分类方法
•决策树方法 •贝叶斯分类法 •LOGISTIC回归 •神经网络方法 •K近邻分类法 •SVM分类法 ……….
分类与决策树[1]
决策树(decision tree)
Root
Node
Leaf
规则1：If refund=no and (marst=single or marst=divorced) and taxincome>80k
Own_home
No No No Yes No No No Yes Yes Yes Yes Yes No No No
Credit
Fair Good Good Fair Fair Fair Good Good Excellent Excellent Excellent Good Good Excellent Fair
GINI最大=？1-1/2 （目标变量为二元变量） GINI最小=？0
分类与决策树[1]
银 ID
行1
贷2
款 数
3
据4
集5
6
7
8
9
10
11
12
13
14
15
Age
Young Young Young Young Young Middle Middle Middle Middle Middle Old Old Old Old Old
分类与决策树[1]
银 ID
行1
贷2
款 数
3
据4
集5
6
7
8
9
10
11
12
13
14
15
Age
Young Young Young Young Young Middle Middle Middle Middle Middle Old Old Old Old Old
Has_job
No No Yes Yes No No No Yes No No No No Yes Yes No
Class
No No Yes Yes No No No Yes Yes Yes Yes Yes Yes Yes No
银行贷款案例数据集的基尼指数： gini=1-(6/15)2-(9/15)2=0.48
分类与决策树[1]
分类误差（classification error) CE最大=？1-1/2 （目标变量为二元变量） CE最小=？0
分类与决策树[1]
一、决策树思想
•将数据集根据某种测试条件分为2个或多个 子集，使分裂后的子集在目标变量上具有更 纯的分类
纯度与混杂度
分类与决策树[1]
混杂度的常用测度指标
• 信息熵 （ Entropy） • 基尼指数（ Gini Index） • 分类误差（classification error)
Own_home
No No No Yes No No No Yes Yes Yes Yes Yes No No No
Credit
Fair Good Good Fair Fair Fair Good Good Excellent Excellent Excellent Good Good Excellent Fair
9/15*(− 3/9*log2(3/9) − 6/9*log2(6/9) =0.551
信息增益Gain(ownhome)=0.971-0.551=0.42
分类与决策树[1]
案例数据集基于age属性划分
ID Age
Has_job Own_home Credit
Class
1 Young No
No
2 Young No
分类与决策树[1]
12
银 ID
行1
贷2
款 数
Байду номын сангаас
3
据4
集5
6
7
8
9
10
11
12
13
14
15
Age
Young Young Young Young Young Middle Middle Middle Middle Middle Old Old Old Old Old
Has_job
No No Yes Yes No No No Yes No No No No Yes Yes No
Class
No No Yes Yes No No No Yes Yes Yes Yes Yes Yes Yes No
银行贷款案例数据集的分类误差： CE=1- 9/15=6/15=0.4
分类与决策树[1]
二、建立决策树
常用算法
•ID3-ID5,C4,C4.5,C5.0
二叉或多叉 信息熵
•CART（Classification and Regression Trees分 类与回归树) （C&RT） •CHAID(chi-squared automati二c i叉nteracGtIiNoIn指数 detection，卡方自动交互检测)