决策树简介
决策树是一种有监督的机器学习算法，可以实现分类和回归任务，通常对数据有比较好的拟合效果。
决策树能够非常直观地提供分类规则，易于解释。
公众号后台回复“决策树”可获得本文全部代码和PDF版本，便于练习保存。
决策树训练和可视化
使用sklearn自带的iris数据集，训练一个决策树，并用graphviz将其可视化出来。代码如下面所示：
需要提前在电脑上安装Graphviz，安装完后需要配置环境变量，可能需要重启电脑才能生效。mac下可以直接使用brew安装：brew install graphviz 即可。windows下的安装过程和使用可以参考下面的连接。 https://www.cnblogs.com/shuodehaoa/p/8667045.html。还需要在Python环境中安装pydotplus和graphviz包。直接使用pip安装即可。
深入理解一下图中的决策树：
这棵树有两个非叶子节点(白色)，三个叶子节点(分别是棕色，绿色，蓝色)。非叶子节点上有分裂属性，叶子节点上有目标类别。
在进行决策时，从根节点出发，判断pletal length(花瓣长度)，如果小于等于2.45，则移动到左边棕色的叶子节点，叶子节点的类别就是最终决策的类别，即setosa；如果大于2.45，则移动到右边白色的非叶子节点上，该节点上有第二个分裂属性，petal width(花瓣宽度)，如果小于等于1.75，移动到绿色的叶子节点，类别是versicolor，如果大于1.75，移动到右边的蓝色节点，类别是virginical。
上面理解了分裂属性，class的含义。再来理解一下samples，value和gini三个值。samples指的是实例的数量。根节点上有150个实例，其中50个实例花瓣长度小于等于2.45，100个实例大于2.45。这100个实例中，又有54个花瓣宽度小于等于1.75，46个大于1.75。value值指的是该节点上每个类别的实例数量。例如绿色的叶节点上，一共有54个实例，其中49个是versicolor，5个是virginical。该节点的类别是按照大多数实例的类别确定的。gini指的是该节点上实例的不纯度。棕色的节点上，所有的实例都属于一个类别，对应的不纯度为0。gini的计算公式如下：
决策边界
另一种表示决策树分类的方法是画出决策边界，如下面代码所示。可以看出，随着树深度的不同，花瓣长度和宽度从不同的点分隔，把整个区域分成了不同部分，每一部分对应了一个叶子节点。例如最右下角的区域的花瓣长度大于4.95，宽度小于等于1.75，对应sample=46，gini=0.043的紫色叶子节点。
对于一个新的样本，决策树可以根据训练好的规则，给出它属于各个类别的概率，概率最大的类别为新样本的预测类别。假设有一个新样本的花瓣长度是5，宽度是1.5，对它预测的类别和概率为：Versicolor，0.9。
类别编号0，1，2对应的分别是iris.target_names中的样本类别。注意上图中右下角矩形区域任意点的估算概率都是相同的，例如花瓣长度为6，宽度为1.5时，结果是Versicolor的概率仍然是0.9(可以用代码验证)。
sklearn中决策树的训练和度量
sklearn中使用的是CART(Classification And Regression Tree)算法来训练决策树，它只能生成二叉树，非叶子节点只有两个子节点。训练过程是：对于单个特征和阈值将训练集分为两个子集，和要根据下面的分类成本函数，确定最小的gini不纯度
对第一步的子集，按照同样的方式继续分裂，直到达到最大深度或不纯度达到最低，就会停止分裂。CART算法是一种贪婪算法，贪婪算法会产生一个“不错”的解，但不一定是最优解。
通常决策树是大致平衡的。使用决策树进行预测，需要遍历大约O(log2(m))个节点，每个节点需要检查1个特征值，所以总体预测的复杂度也是O(log2(m))，与特征数量无关。即便是处理大型数据集，预测也很快。
对决策树进行训练时，对于每一个节点，都需要在所有样本上比较所有特征，训练的复杂度为O(n*mlog(m))对于小型训练集(几千个样本)，可以设置将数据预处理的参数(presort=True)提高训练速度，但对于较大的训练集而言，可能会减慢训练的速度。
决策树节点不纯度的测量，除了使用gini系数，还可以使用信息熵，将相应的超参数设置为criterion=entropy即可，默认为gini。信息熵的计算方式如下：
例如前文提到的绿色节点的熵值计算如下：
gini系数和熵大部分情况下产生的树很相似，但是gini系数计算更快一些，所以作为默认参数。二者不同点在于，gini系数倾向于从树枝中分裂出最常见的类别，信息熵则倾向于产生更平衡的树。
过拟合问题
决策树通常不会对训练数据作出假设(区别于线性模型会假设数据是线性的)，如果不加以限制，树的结构会跟随训练集变化，严密拟合，可能出过拟合。
为了避免过拟合，需要在训练过程中降低决策树的自由度。可以通过设定一些参数来实现。最典型的参数是是树的最大深度max_depth，减小树的深度能降低过拟合的风险。还有一些其他参数，可以限制决策树的形状：min_sample_split:分裂前节点必须有的最小样本数，min_sample_leaf:叶节点必须有的最小样本数量，min_weight_fraction_leaf:加权的叶节点最小样本数，max_leaf_nodes:最大叶节点数量，max_features:分裂每个节点评估的最大特征数量。增加min_*或者减小max_*都能够使模型正则化。
控制以上超参数是在训练模型时控制树的形状来减少过拟合。另外一种方式是事先不加约束地训练模型，之后再进行剪枝。需要判断剪掉某个节点能否够提升纯度。如果一个节点的子节点全部为叶子节点，则该节点可被认为不必要，除非它所表示的纯度提升有重要的统计意义。判定是否具有统计意义的方法可以做卡方测试，当p值高于阈值时，子节点可以被删除，直到所有不必要的节点被删除，剪枝结束。
下面的例子显示了通过控制参数减少过拟合的训练过程。通过min_sample_leaf=4，将左图的过拟合变为右图泛化效果更好的模型。
决策树回归
决策树可以用于执行回归任务，下面使用构造的随机数据训练一棵回归树，如图所示。与之前的分类树的差别在于，每个节点上不再是一个类别而是一个预测值。例如，如果对一个新的值x=0.6进行预测，按照该决策树的规则，从根节点开始，最终会到达白色节点，value=0.111。这个预测结果是与这个叶节点关联的110个实例的平均目标值。在这110个实例上，预测产生的均方误差mse=0.015。
下面的代码展示了，设置max_depth=2和等于3的可视化结果。
每个区域的预测值等于该区域内实例的目标平均值，算法分裂每个区域的方法，就是使最多的训练实例尽可能接近这个预测值。
做回归任务时，CART树的分裂方式从最小化不纯度变为最小化MSE，用公式表示为：
决策树在回归任务中也可能出现过拟合。下图左边是使用默认的决策树预测的结果，右边是设置了超参数min_samples_leaf=10之后的结果，可以看到效果确实好很多。
决策树的不稳定性
从前面的学习我们可以看到，决策树倾向于正交的决策边界，这一特点决定了它对训练集的旋转非常敏感。可以看下面的例子。
左图中的决策树可以很简单找到决策边界，右图中，数据集旋转了45度之后，决策边界就产生了一定的扭曲，虽然这个模型都看似完美拟合数据集，但很可能右边模型泛化能力不佳。解决这种问题的方法之一是使用PCA将数据定位在一个更好的方向上。
决策树对于数据集中的小变化非常敏感。如果我们从iris数据集中去掉花瓣最宽的Versicolor类的实例，训练得到的结果如下图，这与之前的结果完全不同。
随机森林通过对许多树的预测结果进行平均，可能有效改善决策树的不稳定性。
小结
本篇我们学习了决策树的相关知识。决策树可用于分类和回归问题，对于已知的数据能够有比较好的拟合效果，但容易发生过拟合，需要在模型中设置一些超参数来避免过拟合。决策树在分裂时通过信息熵或者gini值确定节点的重要性。可以将决策树分裂过程用图形表示出来，也可以将决策边界可视化呈现。决策树的决策边界通常垂直于坐标轴，因此对于数据旋转比较敏感，对于数据集中的小变化也比较敏感。决策树最大的特点是易于解释，同时它也是很多集成模型的基础，如随机森林。公众号后台回复“决策树”可获得本文全部代码和PDF版本，便于练习保存。
reference:
《机器学习实战：基于Scikit-Learn和Tensorflow》第六章
