决策树学习和实现

记得是大二时候的一个课程设计了,到现在都忘了,特温故一下.

1.什么是决策树

  • 决策树(decision tree)是一个树结构(可以是二叉树或非二叉树)。其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。
  • 决策树算法是从数据的属性(或者特征)出发,以属性作为基础,划分不同的类.

无耻的引用一个来自developerworks的图和说明

上图是一棵结构简单的决策树,用于预测贷款用户是否具有偿还贷款的能力。贷款用户主要具备三个属性:是否拥有房产,是否结婚,平均月收入。每一个内部节点都表示一个属性条件判断,叶子节点表示贷款用户是否具有偿还能力。例如:用户甲没有房产,没有结婚,月收入 5K。通过决策树的根节点判断,用户甲符合右边分支 (拥有房产为“否”);再判断是否结婚,用户甲符合左边分支 (是否结婚为否);然后判断月收入是否大于 4k,用户甲符合左边分支 (月收入大于 4K),该用户落在“可以偿还”的叶子节点上。所以预测用户甲具备偿还贷款能力。

决策树的判定过程就相当于从树中根结点到某一个叶子结点的遍历,每一步如何遍历是由数据各个特征的具体特征属性决定.
其实决策树可以看做if-then的集合..

实现决策树的算法有很多种,如ID3C4.5CART等算法.比较基础的是ID3算法,所以这里介绍的也是该算法.

2.ID3算法介绍

ID3算法是以信息熵和信息增益作为衡量标准的分类算法。

选取使得信息增益最大的特征进行分裂!也就是作为非叶节点.

  • 信息熵是代表随机变量的复杂度(不确定度)
  • 条件熵代表在某一个条件下,随机变量的复杂度(不确定度)

    这两个概念都可以深度展开,这里就不再赘述,可以参看
    通俗理解信息熵
    通俗理解条件熵
    而信息增益恰好是:

  • 信息熵-条件熵。

    我们看如下定义:

  • 当前样本集合 D 中第 k 类样本所占的比例为 pk ,则 D 的信息熵定义为

    $$Ent(D)=-\sum_{k=1}^{|y|}p_k*\log_{2}{p_k}$$

  • 离散属性a有V个可能的取值${a1,a2,…av}$;样本集合中,属性a上取值为av的样本集合,记为Dv.

  • 用属性a对样本集D尽行划分所获得的信息增益

    $$Gain(D,a) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)$$

3.任务

以下是当时的例子,要求根据这个表格构建决策树,并实现分类.

Day Outlook Temperature Humidity Wind PlayTennis
1 sunny hot high weak No
2 sunny hot high strong No
3 overcast hot high weak Yes
4 rainy mild high weak Yes
5 rainy cool normal weak Yes
6 rainy cool normal strong No
7 overcast cool normal strong Yes
8 sunny mild high weak No
9 sunny cool normal weak Yes
10 rainy mild normal weak Yes
11 sunny mild normal strong Yes
12 overcast mild high strong Yes
13 overcast hot normal weak Yes
14 rainy mild high strong No

说明: 最后一列 PlayTennis为类别,就是最终想看到的结果,是否要去打网球.前面的除了Day(一般不看这个..)都是属性,可以作为非叶节点.

1.从根节点开始, 最后的类别只有YesNo两个类别,所以$p_k$的取值也就只有1和2.

规定,$p_1$为正例(Yes),$p_2$为反例(No),则:
$$p_1 = \frac{9}{14}$$,$$p_2 = \frac{5}{14}$$
根节点的信息熵为
$$Ent(D)=-\sum_{k=1}^{2}p_k\log{2}p_k = -(\frac{9}{14}\log{2}\frac{5}{14}+\frac{5}{14}\log{2}\frac{5}{14})=0.9402859586706309$$

  1. 计算当前属性集合{Outlook,Temperature,Humidity,Wind}中每个属性的信息增益
    Outlook中有{sunny,rainy,overcast}三个可能的取值
    D1(Outlook=sunny)={1,2,8,9,11} ,$p_1=\frac{2}{5}$,$p_2=\frac{3}{5}$
    D1(Outlook=rainy)={4,5,6,10,14} ,$p_1=\frac{3}{5}$,$p_2=\frac{2}{5}$
    D1(Outlook=overcast)={3,7,12,13} ,$p_1=\frac{5}{5}$,$p_2=\frac{0}{5}$
    三个分支的信息熵
    $$Ent(D^1)=-(\frac{2}{5}\log{2}\frac{2}{5}+\frac{3}{5}\log{2}\frac{3}{5})=0.9709505944546686$$
    $$Ent(D^2)=-(\frac{3}{5}\log{2}\frac{3}{5}+\frac{2}{5}\log{2}\frac{2}{5})=0.9709505944546686$$
    $$Ent(D^3)=-(\frac{4}{4}\log{2}\frac{4}{4}+\frac{0}{4}\log{2}\frac{0}{4})=0.0$$
    从而可以知道属性Outlook的信息增益是:
    $$Gain(D,Outlook) = Ent(D) - \sum_{v=1}^{3}\frac{|D^v|}{|D|}Ent(D^v) =0.9402859586706309 -( \frac{5}{14}0.9709505944546686+\frac{5}{14}0.9709505944546686+\frac{4}{14}*0.0)=0.06300830809030594$$

同理,我们可以求出其他属性的信息增益,分别如下
…待更