机器学习算法系列

1. 机器学习 之线性回归
2. 机器学习 之逻辑回归及python实现
3. 机器学习项目实战 交易数据异常检测
4. 机器学习之 决策树(Decision Tree)
5. 机器学习之 决策树(Decision Tree)python实现
6. 机器学习之 PCA(主成分分析)
7. 机器学习之 特征工程

这次，我们来看下决策树算法

决策树（Decision Tree）

决策树是一种常见的机器学习方法，它是从根节点开始，一步一步决策，直到走到叶子节点。
最终，所有的样本数据都会落到叶子节点，显然，决策过程的最终结论对应了我们所希望的判定结果 。
它即可以做分类问题，也可以做回归问题。

决策树组成

一般，一棵决策树包含一个根节点，若干个内部节点（非叶子节点）和若干个叶子节点。

1. 根节点：第一个选择点
2. 内部节点（非叶子节点）：中间决策过程
3. 叶子节点：最终的决策结果

决策树的训练流程

如何从给点定的训练集中去构造一棵决策树呢？ 其实，决策树的构建就是一个递归过程，从根节点开始，根据选择的特征，将原始数据集切分为几个分支，然后依次遍历每个分支，在剩下的特征集中继续选择一个特征，进行对应划分，就是这个流程，一直递归下去，直到不可再分。
那么，什么情况下会不可再分呢？有三种情况：

1. 当前节点包含的样本全属于同一类别，不需要再划分
2. 当前属性集已为空，或者 当前节点中的所有样本在当前所剩属性集中取值相同，无法再分
3. 当前节点包含的样本集为空，无法划分

具体的算法流程，这块贴下周志华大佬的《机器学习》中的一个图，大家可以看下

我们可以发现，上述算法中，最重要的一点，就是在每个节点上，选择最优的划分特征，也就说，每次在节点处划分时，我们都需要考虑，选择剩余特征集中的哪个属性进行划分，可以更好的划分数据呢？这个，也就是决策树算法的核心

决策树划分选择

通过上述，我们直到，决策树算法的核心是，如何选择最优的划分特征，我们希望随着划分的进行，我们经过每次划分后的分支节点所包含的样本尽可能的属于同一类别，也就是节点中所包含的样本纯度越来越高。从而，我们引入信息熵这个衡量标准

信息熵

信息熵表示的是随机变量不确定性的度量，熵越大，不确定性越强，也就是说纯度越低；
熵越小，不确定性越弱，纯度越高

设置样本集合D中总共有类样本，其中第类样本所占的比例为,则的信息熵定义为：

对于一个二分类问题，我们可以画出信息熵的图像看看