1、决策树

1.1、决策树的概念

    决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。[来自百度百科的解释]
    决策树顾名思义，是通过树结构来对数据集构成的假设空间进行划分，直到将各个样本数据划分到同一类别中或遍历完特征值。

1.1 应用场景

    可以用以解决二分类和多类别分类的分类的问题以及回归的问题。

2、预备知识：信息熵

    前面概念介绍时已经提到了决策树主要是通过遍历各个特征属性及特征值，并对假设空间进行划分，从而实现将各个类别的数据独立划分出来，即对应树结构中的子节点。
    看到这里的同学肯定会有个疑问了，怎么划分？这么多个特征属性，划分时如何选择？每个特征属性又有那么多取值甚至连续的，划分的阈值又该如何确定呢？那么接下来我们引入信息熵的概念：
熵：用于表示体系混乱程度的度量。【这个概念相信大家都很熟悉了】
信息熵：描述信源的不确定度，用于解决对信息的量化度量问题。公式为：

信息熵公式.gif
二元的信息熵函数图像.png

    从函数图像可以看到当 P1 取值为 0.5 时，因为是二元分类，则另外一个概率（P2）为 1-0.5 = 0.5 时，信息熵函数取最大值，则说明当信源不确定性越大时，其信息熵越大。
    接下来引入另外一个概念：信息增益（information gain）：可以用于表示为划分前的信息熵值减去划分后的信息熵值。则可以得出如果信息增益越大，则代表划分后不确定性越小，则叶子节点的类别越肯定。

3、算法介绍

3.1、ID3 算法

算法步骤【以特征值为离散的情况举例】：
1、从整个数据集中遍历 n 个特征值，依据各个特征属性的不同取值划分数据集，并计算每个特征值划分前后所对应的信息增益，选择信息增益最大所对应特征属性进行划分数据集；
2、遍历所划分各个子节点，重复步骤1，直到节点中所有类别一致或没有可以接着划分的特征属性，并将该节点设为叶子节点，将多数的类别作为该节点的类别。

3.2、c4.5 算法

如下公式为分裂信息值，用来衡量属性分裂数据的广度和均匀：

切分后的信息熵.gif

如下为信息增益比的公式，其中 Gain（A）就是信息增益，即划分前后的信息增益：

信息增益比.gif
    其中 C4.5 算法由 ID3 算法优化而来，就是将衡量划分特征属性的算法由信息增益更改为由信息增益比来判断。此处不再赘述。

3.3、CART 算法

    CART全称为 classification and Regression Tree，即说明这个算法可以用于解决分类问题和回归拟合问题。其中需要说明的一点是CART树假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间及特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
算法步骤如下：
1、设节点的训练数据集为：D，计算现有特征对该数据集的信息熵。并对每一个特征，对其可能取的每个值，根据样本点对的测试为“是”或“否”将分割成两部分，以及计算所对应的信息熵；
2、在所有可能的特征以及它们所有可能的且分店中，选择信息增益最大的特征及其对应的切分点。依据最优特征与最优切分点，从现节点生成连个子节点，将训练数据集D依特征分配到两个子节点中去。
3、对两个子节点递归地调用步骤1~2，直至满足停止条件。
4、生成 CART 决策树。
备注：算法停止计算的条件是节点中的样本个数小于预定阈值，或样本集的信息增益小于预定阈值（样本基本属于同一类），或者没有更多特征。

4、信息熵的替换算法

    前面三种算法均采用了信息熵来作为数据集划分的依据，但我们也可以采用 Gini index 和 misclassification ERROR来替换信息熵，下面分别介绍一下两个函数：

4.1、基尼指数

Gini index 函数公式如下：

Gini index 函数公式.gif

其可以用于CART、SLIQ和SPRINT。
    当一个节点 p 被切分成 K 个分支时，衡量切分的好坏的公式如下：

衡量切分后的 Gini index 公式.png
其中：

• ni = 子节点 i 的样本数量
• n = 节点 P 的样本数量
  备注：其中切分后的 Gini Index 函数值越小，其切分效果越好。

4.2、misclassification ERROR

其公式如下：

misclassification ERROR.png

举例如下：其中将一个节点 P 划分为两个节点 C1 和 C2 ，且两个节点对应的样本数及各自对应的计算过程如下：

示例截图.png

从例子可以看出来，其函数值越小，其划分效果越好。

4.3 综合分析信息熵、Gini Index 和 misclassification ERROR 三种方式的优劣：

三个函数在二元分类的函数图像.png
结论：
1、三个函数的趋势是一样的，都在0和1两点取最小值，在0.5处取得最大值。
2、三个函数的易算程度排列如下：misclassification error > Gini Index > Entropy
3、三个函数并不存在谁一定比谁合适，要是具体的数据集和计算环境而定。当然，大多数情况下，这三种方式都可以适用且互相替换适用都可以。
备注
1、文章材料参考秦曾昌老师机器学习课程的课件
2、本人知识有限，刚刚入门，顺手做个笔记，如有错误，还请帮忙指正，谢谢！