Python机器学习决策树算法

1、什么是决策树？

决策树（decision tree）也叫做判定树，类似于流程图的结构，每个内部的结点表示在一个属性上的测试，每个分支代表一个属性的输出，每个树叶结点代表类或类分布。书的顶层是树根结点。看下面的这个决策树图。

?

上面的这颗决策树模型是上一篇文章中的小明是否享受运动的例子构建起来的决策树模型，从根节点开始看，是有9天play和5天dont’play然后向下分，看三种天气情况向下走，然后又分别根据判定条件，最终走到树叶，确定出是不是享受运动，可以看出，最终分的叶子节点都是play或者don’play,不会出现两种情况共存。

忽然想到了数据结构老师--李老师讲到的一个决策树例子，决策时好比去饭店点菜，点什么样的菜，点的菜要清淡的还是咸的，加辣还是不加辣，最后确定出这一道菜。

从上面的介绍也可以看得出，决策树适合判定一个事物属于哪一类，所以它是机器学习中分类方法中的一个重要算法。

2、信息熵的概念

熵（entropy）是1948年，香农提出的。它代表一条信息不确定性大小，信息熵越大不确定性就越大。一条信息的信息量大小和它的不确定性有直接的关系，要搞清楚一件非常非常不确定的事情，或者是我们一无所知的事情，需要了解大量信息==>信息量的度量就等于不确定性的多少。我们使用比特（bit）来衡量信息的多少。计算公式如下：

?

2、决策树归纳算法（ID3）

我们怎么来构造这么一个决策树呢，关键的问题在于谁是树根和谁是树枝，也就是说，我们要找到作为根和树枝的属性。

ID3算法就可以来帮助我们计算选择出属性判断结点。下面看计算公式和例子

信息获取量(Information Gain)：Gain(A) = Info(D) - Infor_A(D)，最终的Gain（A）代表着通过A来作为结点分类的时候获取的信息量的多少。Info（D）代表只按照结果来分的信息熵，Infor_A(D)代表根绝某一属性来分的信息熵。看下面的例子。

?

在最后一列，也就是label列中，有9个yes和5个no，所以：

?

下面如果我们根据年龄来分，假设我们计算youth，共有5个，其中对用的yes有2个no有三个，所以：

?

最终得到的age信息熵为：

?

用同样的方式我们可以计算出其他几个属性的信息熵：

Gain(income) = 0.029

Gain(student) = 0.151

Gain(credit_rating)=0.048

通过上面可以看出，最大的信息熵就是age的，也就是说最不缺的的就是age，所以我们就把它作为根结点。第一次构造出来的树如下：

?

然后我们进行重复，以上算法，确定出剩下的树枝，最终形成一个完整的决策树。

具体的算法实现我也没有仔细看，就不写了。感兴趣的同学可以去网上看一下，不止一种实现算法。

3、决策树的优缺点

优点：直观、便于理解、小规模数据有效。

缺点：处理连续性变量不好、类别较多的时候错误增加的比较快、可规模性一般。