C2：决 策树分类.ppt

文档介绍：2017/11/11
1
第2讲决策树分类
2017/11/11
2
数据实例
PlayTennis数据库片段:
2017/11/11
3
决策树实例
关于PlayTennis的决策树:
2017/11/11
4
决策树学习算法的代表
早在1986年的时候,Quinlan就提出了著名的ID3算法。(Published on MLJ)
用ID3算法长树的基本思想:
分类能力最好的属性被测试并创建树的根结点
测试属性每个可能的值产生一个分支
训练样本划分到适当的分支形成儿子结点
重复上面的过程,直到所有的结点都是叶子结点
两个问题:什么属性最好?什么结点才是叶子结点?
2017/11/11
5
信息增益(Information Gain)
属性A划分样本集S的信息增益Gain(S, A)为:
Gain(S, A)=E(S)–E(S, A)
其中,E(S)为划分样本集S为c个类的熵; E(S, A)为属性A划分样本集S导致的期望熵。
2017/11/11
6
熵(Entropy)
划分样本集S为c个类的熵E(S) 为:
其中,pi =ni /n,为S中的样本属于第i类Ci的概率,n为S中样本的个数。
2017/11/11
7
期望熵(Expected Entropy)
属性A划分样本集S导致的期望熵E(S, A)为:
其中,Values(A)为属性A取值的集合;Sv为S中A取值为v的样本子集,Sv={sSA(s)=v};E(Sv)为将Sv中的样本划分为c个类的信息熵。|Sv|/|S|为Sv和S中的样本个数之比。
2017/11/11
8
回味ID3算法
ID3算法每一步选择具有最大信息增益的属性作为测试属性来长树。直到最大的信息增益为也零为止。(两个问题的解决)
熵(Entropy)刻画了样本集的纯度,长树的过程是一个熵降低、信息增益、从混沌到有序的过程。(长树的物理意义)
2017/11/11
9
伪代码
算法 Decision_Tree(samples, attribute_list)
输入由离散值属性描述的训练样本集samples;候选属性集合atrribute_list。
输出一棵决策树。
方法
(1) 创建节点N;
(2) if samples 都在同一类C中 then
(3) 返回N作为叶节点,以类C标记;
(4) if attribute_list为空 then
2017/11/11
10
伪代码(续)
(5) 返回N作为叶节点,以samples中最普遍的类标记;//多数表决
(6) 选择attribute_list中具有最高信息增益的属性test_attribute;
(7) 以test_attribute标记节点N ;
(8) for each test_attribute的已知值v //划分samples
(9) 由节点N分出一个对应test_attribute=v的分支;
(10) 令Sv为samples中test_attribute=v的样本集合; //一个划分块
(11) if Sv为空 then
(12) 加上一个叶节点,以samples中最普遍的类标记;
(13) else 加入一个由Decision_Tree(Sv, attribute_list–test_attribute)返回的节点。