从熵概念到决策树算法

顶级程序员

发布于 2018-07-23 11:30:54

6260

发布于 2018-07-23 11:30:54

文章被收录于专栏：顶级程序员顶级程序员

源 / 顶级程序员文 / 数据挖掘机

一、熵

熵可以认为是对无序的一种度量，熵越大越无序，熵越小越有序。

信息熵是将熵的理论应用于信息混乱度的描述，在随机变量中可以描述随机变量不确定性的程度，在机器学习的样本集合中，可以用于描述样本集合的纯度。

假定样本集合D中第k类样本所包含的样本数所占总样本数的比例为则D的信息熵可以定义为：

此文，可以以一个实际例子来做说明，该样本集合较简单，样本如下：

从上述样本集合中可以看出，该样本共有四个属性，分别为outlook、temperature、humidity、windy，最终分类结果只有两个，yes和no，即建模的目的就是根据天气情况来判断当前是否适合出去运动。那么，根据前面介绍的方法，就可以利用熵这个指标来描述一下当前样本集合D的混乱程度，本文的计算将全部使用python语言来描述：

所以，训练集合D在未进行分类的情况下，其样本集合的熵为0.94。

二、决策树算法

了解了熵的概念以后，就可以引出今天我们主要的话题，决策树算法了，决策树算法是机器学习算法中较常用的一种算法，该算法最常用于分类问题，比如根据西瓜的根蒂、纹理来判断该瓜是熟瓜还是不熟瓜等，决策树算法较为简单、易于理解，并且其结果最终又可以总结成规则，是一种应用十分广泛的算法。

首先，先介绍一下决策树算法，然后再展开具体讲每个细节，决策树算法最终生成的结果是一颗树，其中节点是属性，节点间的分支是该属性对应的值，从根到叶子结点就是一个判断的流程。

决策树学习的基本算法如下：

输入：训练集D={(x1,y1),(x2,y2),(x3,y3),…,(xm,ym)}

属性集A={a1,a2,a3,…,ad}

过程：函数TreeGenerate(D,A)

1、生成节点node

2、如果D中样本全部属于同一个类别C then将node标记为C类叶节点并返回

3、如果A=或者D中样本在A上的取值均相同，则将node标记为叶节点，其类别标记为D中样本最多的类

4、如果上面两个条件不存在，在需要根据属性来划分，从A中选择最优划分属性（如何找到最优划分属性后面讲解），对于中的每一个属性里面的值都可以将样本集合D生成一个分支，且可以用来表示在上取值为的样本子集

5、如果为空，则将该分支节点标记为叶节点，其类别标记为D中样本最多的类（因为为空，没有类别，用父类别）

6、如果不为空，则继续递归执行TreeGenerate(,A\{})

根据上面的步骤就可以构造出一颗决策树，不过，里面有一点也是非常重要的一点就是如何去不断找到最优属性，也就是此时需要有一个衡量标准，能够根据这个标准来衡量那个属性可以作为最优属性，此时就引入了信息增益的概念：

上面的公式就是决策树算法的信息增益。

其中D表示样本集D，假定属性a有v个可能的取值（离散或连续）{a1,a2,a3,a4,…,aV}，在选择最优划分属性的时候，比如先找到了a属性，然后接着需要计算下并比较下a属性是否是最优划分属性，也就是需要给属性a一个打分，属性a判断完成后，接着再判断下一个属性，给每个属性都一个打分，然后选择得分最高的那个作为最优划分属性，于是，当拿到属性a的时候，根据a的不同取值（1到v）就可以把样本集D划分成v个样本子集，然后每个值对应的样本子集又有一个或者多个类别，就可以计算出这个值的样本子集所对应的熵，将所有值对应的样本子集的熵相加就变成了这个属性a的熵，即，又因为不同的取值所分成的样本集合数量不同，越多的，说明此种情况更容易出现，所以可以给每个值对应的熵加上一个所占比例的权重，用来表示，则属性a划分数据集D的熵就是，此时a的熵越小，说明划分能力越强，然后此时可以用一个减少量去衡量，即使用上面公式来衡量，因为对于数据集D而言，Ent(D)是固定的，所以减去的数值越小就越大，即减少量就越大，即就可以用于衡量该属性划分能力的强弱，且该值越大，划分能力越强，于是通过该值可以对所有属性进行选择了，不过这只是ID3算法的标准，本文将以最简单的ID3为例子讲解。

好了，到这里决策树基本算法的东西就讲完了，这样看来决策树算法还是很简单易懂的，不过后面还有剪枝和调参数的很多东西，此时，可以先根据上面的理论得到前面天气数据集的最优划分属性：

从上面的计算结果可以看出，四个属性分别计算了其信息增益后，outlook的值最大，可以作为最优划分属性，于是就是该决策树的根节点root。

接着，再根据上面的算法来找到不同分支的子节点：

此时，用属性outlook划分样本后，三个属性值把样本集合D分成了三部分，分别为D-sunny，D-overcast、D-rainy，

其中，D-sunny为：

此时，再用另外三个属性划分这个小样本集D-sunny

计算各自信息增益：

所以，该数据集再进行划分的时候，选择的最优属性为humidity，

使得humidity=sunny时，数据集变成如下，此时可以看到最终分类结果均为同一种类别，无需划分，此时humidity=normal时为叶子结点

同样的，humidity=high时：

该节点同样属于同一类别，无需划分，即humidity完成了D-sunny的划分，生成了如下分支：

outlook = sunny
|   humidity = high: no (3.0)
|   humidity = normal: yes (2.0)

然后，D-overcast数据集就变成了：

此时，满足上面所讲算法的步骤2，此时D-overcast属于同一类别，将该节点标志为叶子节点，并且类别为样本最多的类别，即yes：

outlook = overcast: yes (4.0)

然后，D-rainy为：

好了，从这里可以看出，使用outlook进行划分的时候，前两个值，sunny和overcast已经都形成了最终分支，此时只需对这个数据集划分完成，一颗决策树就形成了，所以，依旧按照前面的方法求信息增益：

所以，此时最优划分属性变成了windy，上面属性集又可以根据windy的不同取值变成两个子集：

从上面可以看出，windy=False和windy=True的时候，这两个子集都把原来的集合划分成了两个同一类别，即满足了算法中2的步骤，即生成了如下分支：

outlook = rainy
|   windy = TRUE: no (2.0)
|   windy = FALSE: yes (3.0)

Bingo！到此为止，所有分支都按照算法的步骤生成完成，最终的分类树如下：

outlook = sunny
|   humidity = high: no (3.0)
|   humidity = normal: yes (2.0)
outlook = overcast: yes (4.0)
outlook = rainy
|   windy = TRUE: no (2.0)
|   windy = FALSE: yes (3.0)
Number of Leaves  : 5
Size of the tree : 8

即最终决策树为：