决策树ID3算法详解

 

1决策树学习是以实例为基础的归纳学习。

决策树学习采用的是自顶向下的递归方法，决策树的每一层节点依照某一属性向下分子节点，待分类的实例在每一节点处与该节点相关的属性进行比较，根据不同的比较结果向响应的子节点扩展，这一过程在到达决策树的叶节点时结束，此时得到结论。

决策树学习最大的优点是它可以自学习。

2 决策树是描述分类的一种数据结构从上端的根节点开始，各种分类原则被引用进来，并以 这些分类原则见根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束。

3 构造一棵决策树要解决的4个问题；

 （1）收集待分类的数据，这些数据的所有属性应该是完全标注的。

（2）设计分类原则，即数据的哪些属性可以用来分类，以及如何将该属性量化。

（3）分类原则的选择，在众多的分类准则中，每一步选择哪一准则是最终的树更令人满意。

（4）设计分类停止条件。通用分类目标是整棵树的熵的总量最小。

4自信息量：设信源X发出a的概率p(a),在收到符号a之前，收信者对a的不确定性定义为a的自信息量I(a)=-logp(a)。

信息熵：自信息量只能反映符号的不确定性，而信息熵用来度量整个信源整体的不确定性，定义为：H(X)= 求和(p(ai) I(ai))

条件熵：设信源为X，收信者收到信息Y，用条件熵H(X|Y)来描述收信者收到Y后X的不确定性的估计。

平均互信息量：用平均互信息量来表示信息Y所能提供的关于X的信息量的大小。

互信息量I(X|Y)=H(X)-H(X|Y)    下边的ID3算法就是用到了每一个属性对分类的信息增益大小来决定属性所在的层次，信息增益越大，则越应该先作为分类依据。

5 ID3算法

 

下边的例子转自新浪博客，很详细，讲的不错。

 

还有一个老外的例子，也很不错，http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm。 

 

决策树是数据挖掘中应用较广的一种算法，下面我将用一个例子来对较早出现的ID3算法探索应用一下，从而复习下昨天所学的知识，由于是刚接触，理解有限，有一些问题还得高手们解答一下；

    世界杯期间我和同学一起去吃了几回大排档，对那种边凑热闹边看球的氛围感觉很不错，但虽然每个夏天我都会凑几回这种热闹，但肯定并不是所有人都喜欢凑这种热闹的，而应用决策树算法则能有效发现哪些人愿意去，哪些人偶尔会去，哪些人从不愿意去；

    变量如表1所示，自变量为年龄、职业、性别；因变量为结果（吃大排档的频率）。

                            表1   数据表

                    

年龄A	职业B	性别C	结果
20-30	学生	男	偶尔
30-40	工人	男	经常
40-50	教师	女	从不
20-30	工人	女	偶尔
60-70	教师	男	从不
40-50	工人	女	从不
30-40	教师	男	偶尔
20-30	学生	女	从不
20以下	学生	男	偶尔
20以下	工人	女	偶尔
20-30	工人	男	经常
20以下	学生	男	偶尔
20-30	教师	男	偶尔
60-70	教师	女	从不
30-40	工人	女	偶尔
60-70	工人	男	从不

计算过程：

1、首先计算结果选项出现的频率：

             表2   结果频率表

从不p1	经常p2	偶尔p3
0.375	0.125	0.5

2、计算因变量的期望信息：

E(结果)=-(p₁*log₂^(p1)+p₂*log₂^(p2)+p₃*log₂^(p3) )

       =-(0.375*log₂^(0.375)+0.125*log₂^(0.125)+0.5*log₂^(0.5) )

        =1.406

注：这里Pi对应上面的频率

3、计算自变量的期望信息(以年龄A为例)：

E(A)=∑count(Aj)/count(A)* (-(p_1j*log₂^(p1j)+p_2j*log₂^(p2j)+p_3j*log₂^(p3j) ))

3.1公式说明：

Count(Aj):年龄A第j个选项个数； j是下面表3五个选项任一

 

                       表3   年龄记录数量表

选项	20-30	20以下	30-40	40-50	60-70
数量	5	3	3	2	3

Count(A):年龄总记录数

 

p_1j =count(A_1j)/count(Aj) :年龄A第j个选项在结果中选择了“从不”的个数占年龄A第j个选项个数的比例；

p_2j =count(A_2j)/count(Aj) :年龄A第j个选项在结果中选择了“偶尔”的个数占年龄A第j个选项个数的比例；

p_3j =count(A_3j)/count(Aj) :年龄A第j个选项在结果中选择了“经常”的个数占年龄A第j个选项个数的比例；

 

3.2公式分析

    在决策树中自变量是否显著影响因变量的判定标准由自变量选项的不同能否导致因变量结果的不同决定，举例来说如果老年人都从不去大排档，中年人都经常去，而少年都偶尔去，那么年龄因素肯定是决定是否吃大排档的主要因素；

    按照假设，即不同年龄段会对结果产生确定的影响，以表3年龄在20以下的3个人为例，假设他们都在结果中选择了“偶尔”选项，此时:

p_2j =count(A_2j)/count(Aj)=1，

p_1j =count(A_1j)/count(Aj)=0、

p_3j =count(A_3j)/count(Aj)=0；

 (p_1j*log₂^(p1j)+p_2j*log₂^(p2j)+p_3j*log₂^(p3j) )→0；

    具体说来:

LIM_(p2j→1) p_2j*log₂^(p2j) →LIM_(p2j→1) 1*0→0

LIM_(p1j→0) p_1j*log₂^(p1j) →LIM_(p1j→0) log₂^(p1j) /(1/ p_1j) →LIM_(p1j→0) p_1j* log₂^(e) →0

LIM_(p3j→0) p_1j*log₂^(p3j) →LIM_(p3j→0) log₂^(p3j) /(1/ p_3j) →LIM_(p3j→0) p_3j* log₂^(e) →0

(p_1j*log₂^(p1j)+p_2j*log₂^(p2j)+p_3j*log₂^(p3j) )→0+0+0=0

    可见，如果每个年龄段都对结果有确定影响，那么各年龄段的不加权的期望信息(p_1j*log₂^(p1j)+p_2j*log₂^(p2j)+p_3j*log₂^(p3j) )就很小，从而E(A)就很小甚至趋近0了；

4、自变量的期望信息计算

4.1、E（A）计算

    从表4看，有两个年龄段对结果产生了不同影响，计算如下：

E(30-40)= count(Aj)/count(A)* (-(p_1j*log₂^(p1j)+p_2j*log₂^(p2j)+p_3j*log₂^(p3j) ))

       =3/16*(-(2/3* log₂^(2/3) +1/3*log₂^(1/3) ))

       =0.172

E(20-30)= count(Aj)/count(A)* (-(p_1j*log₂^(p1j)+p_2j*log₂^(p2j)+p_3j*log₂^(p3j) ))

       =5/16*(-(1/5* log₂^(1/5)+3/5* log₂^(3/5) +1/5*log₂^(1/5) ))

       =0.428

    最终算得：

E(A)= E(30-40)+ E(20-30)=0.172+0.428=0.6

  

                        表4    年龄信息表

年龄A	结果
60-70	从不
60-70	从不
60-70	从不
40-50	从不
40-50	从不
30-40	经常
30-40	偶尔
30-40	偶尔
20以下	偶尔
20以下	偶尔
20以下	偶尔
20-30	偶尔
20-30	偶尔
20-30	从不
20-30	经常
20-30	偶尔

5、信息增益的计算

年龄变量的信息增益计算为：

Gain(A)=E(结果)-E(A)= 1.406-0.6=0.806

同理可以计算Gain(B)、Gain(C)；

注：信息增益大说明较好的降低了划分前的无序程度，因此决策树的第一次划分就看哪个变量的信息增益大就按哪个划分；

6、划分过程

如果是像上例那样变量选项比较少的决策树来讲，假设年龄变量的信息增益最大，那么第一部划分就是：

40-70岁      从不去光顾

20岁以下     偶尔

20-30岁      数据再按照职业和性别计算信息增益找出规则

30-40岁      数据再按照职业和性别计算信息增益找出规则

实际划分是按分割阈值的标准：
A、数值型变量——对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。
B、分类型变量——列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。
注两个问题：根节点一定要产生两个子集吗，要是产生三个子集、四个子集呢，产生多少子集有什么标准呢？我猜测是不是多个子集之间的结果两两差异显著就可以继续进行拆分，如果新的子集不能和原来任一子集的结果都有显著差异就停止划分呢？如何构建这个阈值的统计量呢？

7、划分停止的标准

    满足以下一个即停止生长。
（1） 节点达到完全纯性；
（2） 数树的深度达到用户指定的深度；
（3） 节点中样本的个数少于用户指定的个数；
（4） 异质性指标下降的最大幅度小于用户指定的幅度。

剪枝：完整的决策树对训练样本特征的描述可能“过于精确”（受噪声数据的影响），缺少了一般代表性而无法较好的用对新数据做分类预测，出现 ”过度拟合“。
——移去对树的精度影响不大的划分。使用 成本复杂度方法，即同时度量错分风险和树的复杂程度，使二者越小越好。
剪枝方式：
A、 预修剪（prepruning）：停止生长策略
B、后修剪（postpruning）：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。