决策树算法简介

树模型是机器学习中非常常用的一种算法，既可以处理分类问题，也可以处理回归问题，更多的时候是用来处理分类问题的。
我们用下图做一个示例，小明家有五口人，爷爷、奶奶、妈妈、妹妹和自己，我们现在要判断谁喜欢打游戏。这里我们选了两个特征年龄和性别，先用年龄进行分类，年龄大于15岁的一组，年龄小于15岁的一组，再使用性别特征对小于15岁的这组进行分类，男生一类，女生一类，最终就分出了男生喜欢打游戏。
这个过程跟我们高中数学学过的流程图是一样的。在计算机语言中，我们将这样的模型称为树模型，一组数据经过不同的特征进行多次分支，最后形成一棵枝繁叶茂的树。这些特征我们称之为节点，第一个特征我们称之为根节点，最后无法再分的节点我们称之为叶子结点（最终决策结果）。

树的组成
从图中可以看出，树模型是由根结点，叶子结点和非叶子节点构成的。

决策树示例.png
决策树的构造与训练
训练阶段：从给定的数据集训练出一棵树（从根节点开始选择特征，如何进行特征切分），这是决策树的难点。像上图中例子，无论选择年龄还是性别，对于整个决策树的构造，基本没有什么影响。但是对于特征多的数据来说，我们在选择切分特征时是有一定的先后顺序的，前后不可颠倒。
测试阶段：根据构造出来的树模型从上到下走一遍就好了。

分类节点的选择标准 -- 熵
熵，看到这个词，我第一个想到的是高中化学中关于“熵”的定义。熵是衡量系统混乱程度的量，任何化学反应系统都是朝着熵增加的方向进行。但在分类任务中，我们希望能够将系统中不同种类的事物清清楚楚的划分开，是朝着熵减的方向进行。
H(x) = -∑pi * log(pi), i=1,2,3,4.......
举个例子：
A集合[1,1,1,1,1,1,1,2,2]
B集合[1,2,3,4,5,6,7,8,9]
显然A集合的熵值要低的多，因为A集合中只有两类值，相对稳定一些，而B集合中的类别非常多，熵值就会大很多。在分类任务中，我们希望通过节点分支，系统的熵值能大幅度的减小。

信息增益
数据通过节点分支后，系统熵值的减小幅度。假设分类前系统的熵值H(x) = 0.96，分类后H(x) = 0.64，信息增益则为0.32。我们通过信息增益的大小来选择节点，信息增益值最大的作为根节点，其次选出第二节点，第三节点等等。

分类节点的选择标准 -- GiNi系数
Gini(p) = ∑p(1-p) = 1-∑p^2
基尼系数与熵类似，只是计算方式不同，当系统数据越纯时，p趋近于1，gini系数趋近于0。

决策树的剪枝策略
理论上，通过树模型，我们可以将任何数据区分开，只要我们无限去分类。但是这样会存在一个问题，我们构造出来的决策树枝繁叶茂（如图），这样对于训练集数据的分类效果非常好，但是在测试集上的表现就比较差，这就导致了我们机器学习中经常出现的过拟合问题。

Decision tree.jpg

所以我们就需要对决策树进行修剪，就像园丁一样，对花园定期修剪。决策树的剪枝策略有两种，预剪枝和后剪枝。
预剪枝：在构造决策树的过程中，提前添加限制条件，如：限制深度，比如只能分叉3次；叶子结点个数；叶子结点样本数，信息增益量等。这也是我们常用的方法。
后剪枝：当建立完决策树后来进行剪枝。