决策树的简要理论及其部分python实现

Posted on 2019-03-01 | Comments:

前言

决策树是机器学习中非常重要的一类监督学习方法。它可以对数据进行分类和回归学习。我们来看一下一个简单的决策树模型，如下图所示。

注意：本文 python 实现都是基于标签值位于样本的最后一列进行计算。

在进行垃圾邮件分类的时候，首先从根节点开始判断，如果发送的邮件域名为:myEmployer.com，那么将其分类为”无聊时需要阅读的邮件”，否则进一步判断是否为包含单词”曲棍”的邮件，如果是则被列入”需要及时处理的朋友邮件”，否则被归入”无需阅读的垃圾邮件”。总之，像这样一步步缩小判断范围，至到找到目标分类的过程就是决策树不断作出决策的机制。

决策树的构造

决策树的优缺点

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过拟合的问题。
适用数据类型：数值型(回归分析)和标称型(分类任务)

决策树的一般流程

收集数据: 可以使用任何方法;
准备数据: 树的构造算法只适用于标称型数据，因此数值型的数据需要离散化；
分析数据：可以使用任何方法，构造树完成之后，需要检查决策树是符合预期；
训练算法：构造树的数据结构；
测试算法：使用经验树计算错误率；
使用算法：使用决策树可以更好地理解数据的内在含义。

熵的概念及其公式

熵，也称信息熵，它是度量样本集合纯度的一种指标。也就说，样本集合中越不纯，那么表示信息越杂乱无序(如集合中类别越多,表示这个集合信息越杂乱)，则其含有的信息量就越大。而比较官方的定义是，熵是对不确定性的度量，即越不确定,信息量越大。
在衡量样本集合的熵时，单个类别的信息量我们可以定义为

$h\left( x_{i}\right) =-\log_{2} p\left( x_{i}\right)$

其中p(x)是类别占比(该类别的数目占总类别数目的概率)
而熵是信息(或单个类别所含信息)的期望值,因此最终(香农)熵的公式为:

$H=-\sum ^{N}_{i=1}P\left( x_{i}\right) \log_{2} P\left( x_{i}\right)$

计算给定数据的香农熵

其实就是把每个类别在样本集合中的占比计算出来,即p(xi),再利用上述公式计算即可。

划分数据集

决策的时候其实也是划分数据集的过程，你需要一个依据来将数据集划分开，一步一步地缩小可选的范围。所以我们此时需要一个依据，也就是能让我们作出最好决策的一个依据。然后根据这个依据将数据集划分开。
在决策树算法中，常用的依据主要有三种算法：ID3、C4.5和CART。

基于信息增益(ID3)

信息增益主要是利用集合的香农熵来计算的。信息增益衡量的是集合划分前的香农熵与划分后各子集香农熵的期望之差。
简单决策树
我们以上图为例。假设样本集合为 D，年龄为每个样本具备的其中一个特征，记作 a，它共有三个属性值(青年、中年、老年)，设 v 为属性值的个数,D^v 为属性值为v的样本集合(被划分为青年的人数)。记 Ent(D) 表示样本集合 D 对应的熵,那么信息增益的计算公式为:

$Gain\left( D,a\right) =Ent\left( D\right) -\sum ^{3}_{v=1}\dfrac {\left| D^{v}\right| }{\left| D\right| }Ent\left( D^{v}\right)$

我们用 Gain(D,a) 表示样本集合 D 依据属性 a 进行划分时的信息增益。那么，在实际中，属性 a 可以有多个，即划分方式有多种，但是我们只取信息增益最大的那个划分方式来划分数据集。

基于信息增益率(C4.5)

信息增益率为信息增益的改进版本。由于信息增益对可取值数目较多的属性有所偏好，为减少这种偏好所带来的不利影响，信息增益率应运而生。增益率定义为:

$IV\left( a\right) =-\sum ^{V}_{v=1}\dfrac {\left| D^{v}\right| }{\left| D\right| }\log _{2}\dfrac {\left| D^{v}\right| }{\left| D\right| }$ $Gain\_ ratio\left( D,a\right) =\dfrac {Gain\left( D,a\right) }{IV\left( a\right) }$

这其实比之前的版本多除了一个分母，IV(a)其实表示就是属性 a 的各个属性值对应的香农熵总和。

需要注意的是，增益率对可取值数目较少的属性也有所偏好，所以 C4.5 算法并不是取增益率最大的那个最为最佳划分方式，而是先从候选属性中找出信息增益高于平均水平的属性(ID3 算法)，再从中计算出信息增益率最高的那个属性。

基于基尼指数(CART)

在前面介绍的 ID3 和 C4.5 算法其实都是采用熵模型进行计算，并且涉及到大量的对数运算。计算相对复杂。
那么，基尼指数呢。它可以也用来衡量数据集的纯度，但是它与前面二者相反，基尼指数越小，数据集的纯度反而是越高的。对于数据集 D 的纯度可用基尼值来衡量(在分类问题中，假设有 k 个类别，第 k 个类别的占比为pk):

$Gini\left( D\right) =\sum ^{K}_{k=1}p_{k}\left( 1-p_{k}\right) \\ =1-\sum ^{K}_{k=1}P^{2}_{k}$

对于属性a，我们给出它的基尼系数定义为:

$Gini\_ index\left( D,a\right)=\sum ^{V}_{v=1}\dfrac {\left| D^{v}\right| }{\left| D\right| }Gini\left( D\right)$

最后我们选择基尼指数最小的属性作为最优划分属性。特别注意的是，利用基尼指数来划分数据集只会对数据集二分，不多分。怎样理解?，对于多分类问题，可以利用整体思想，把数据集分成两大类，常见的有一对多，多对多,即一边是正例，一边是反例，因此使用基尼指数进行最优属性划分后得到的树是一颗优雅的二叉树。

基于ID3的python代码实现

根据指定特征的属性值返回数据集的子集

注意 extend 与 append 的用法区别,前者为抽取元素加入列表，后者可能会将整个列表作为元素加入列表中。

选择最好的数据集划分

其实大致步骤可以概括为：  
1. 遍历每个属性；  
2. 得到每个属性的属性值集合，并遍历；  
3. 对每个属性值进行划分，计算各个子集的信息熵期望；  
4. 计算信息增益；  
5. 比较不同属性划分下的信息增益，取最大的信息增益对应的特征索引返回。

创建决策树

根据标签列表”投票”选出最多标签的

主要使用字典记录类别的个数，然后再按递减排序即可。

决策树具体算法

使用决策树分类

[1] <<剑指offer2>>