博客

数据分析之决策树ID3算法

什么是分类算法？

分类算法跟之前的聚类都是让不同对象个体划分到不同的组中的。但是分类不同之处在于类别在运算之前就已经是确定的。

分类是根据训练数据集合，结合某种分类算法，比如这篇讲的ID3算法来生成最终的分类规则，这样当提供一个对象的时候我们可以根据它们的特征将其划分到某个分组中。

决策树ID3算法是分类中的经典算法，决策树的每一层节点依照某一确定程度比较高的属性向下分子节点，每个子节点在根据其他确定程度相对较高的属性进行划分，直到 生成一个能完美分类训练样例的决策树或者满足某个分类终止条件为止。

术语定义：

自信息量：设信源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算法就是用到了每一个属性对分类的信息增益大小来决定属性所在的层次，信息增益越大，则越应该先作为分类依据。

ID3算法步骤

a.对当前例子集合，计算属性的信息增益；

b.选择信息增益最大的属性Ai(关于信息增益后面会有详细叙述)

c.把在Ai处取值相同的例子归于同于子集，Ai取几个值就得几个子集

d.对依次对每种取值情况下的子集,递归调用建树算法，即返回a，

e.若子集只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处，或者树达到规定的深度，或者子集所有元素都属于一个分类都结束。

举例分析

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

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

计算过程：

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

表2 结果频率表

从不p1 经常p2 偶尔p3

0.375 0.125 0.5

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

E(结果)=-(p1*log2(p1)+p2*log2(p2)+p3*log2(p3) )

=-(0.375*log2(0.375)+0.125*log2(0.125)+0.5*log2(0.5) )

=1.406

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

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

E(A)=∑count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) ))

3.1公式说明：

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

表3 年龄记录数量表

Count(A):年龄总记录数

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

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

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

3.2公式分析

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

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

p2j =count(A2j)/count(Aj)=1，

p1j =count(A1j)/count(Aj)=0、

p3j =count(A3j)/count(Aj)=0；

(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )→0；

具体说来:

LIM(p2j→1) p2j*log2(p2j) →LIM(p2j→1) 1*0→0

LIM(p1j→0) p1j*log2(p1j) →LIM(p1j→0) log2(p1j) /(1/ p1j) →LIM(p1j→0) p1j* log2(e) →0

LIM(p3j→0) p1j*log2(p3j) →LIM(p3j→0) log2(p3j) /(1/ p3j) →LIM(p3j→0) p3j* log2(e) →0

(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )→0+0+0=0

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

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

4.1、E（A）计算

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

E(30-40)= count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) ))

=3/16*(-(2/3* log2(2/3) +1/3*log2(1/3) ))

=0.172

E(20-30)= count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) ))

=5/16*(-(1/5* log2(1/5)+3/5* log2(3/5) +1/5*log2(1/5) ))

=0.428

最终算得：

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

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）：在允许决策树得到最充分生长的基础上，再根据一定的规则，自下而上逐层进行剪枝。