决策树Decision Tree

本文的内容参考了机器学习实战：基于Scikit-Learn和Tensorflow一书。

决策树可以实现分类和回归任务，甚至是多输出任务。能够拟合复杂的数据集。

决策树训练和可视化

在鸢尾花数据集上训练一个DecisionTreeClassifier：

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

iris = load_iris()
X = iris.data[:, 2:]  # petal length and width
y = iris.target

tree_clf = DecisionTreeClassifier(max_depth=2)
tree_clf.fit(X, y)

# 可视化

from sklearn.tree import export_graphviz

export_graphviz(
    tree_clf,
    out_file='iris_tree.dot',
    feature_names=iris.feature_names[2:],
    rounded=True,
    filled=True
)

import graphviz

with open('iris_tree.dot') as f:
    dot_graph = f.read()
dot = graphviz.Source(dot_graph)
dot.view()     # 以pdf形式查看

决策树的特质之一是需要做的数据准备工作非常少。完全不需要进行缩放或集中。
节点的gini属性衡量其不纯度（impurity）：如果应用的所有训练实例都属于同一个类别，那么节点就是“纯”的（gini=0）。
深度2左侧节点，基尼系数等于1–（0/54）^2^–（49/54）^2^–（5/54）^2^≈0.168

基尼不纯度：
$G_{i} = 1 - <munderover> \sum k = 1 n </munderover> {p_{i, k}}^{2}$
pi，k是第i个节点上，类别为k的训练实例占比。
信息熵
将超参数 criterion设置为"entropy"来选择信息熵作为不纯度的测量方式。
$H_{i} = - <munderover> \sum k = 1, p_{i, k} \neq 0 n </munderover> p_{i, k} \log (p_{i, k})$
基尼不纯度的计算速度略微快一些，基尼不纯度倾向于从树枝中分裂出最常见的类别，而信息熵则倾向于生产更平衡的树。
CART算法：Classification And Regression Tree
算法描述：其中T代表当前样本集，当前候选属性集T_attributelist表示。（1）创建根节点N （2）为N分配类别（3）if T都属于同一类别or T中只剩下一个样本则返回N为叶节点，否则为其分配属性（4）for each T_attributelist中属性执行该属性上的一个划分，计算此划分的GINI系数（5）N的测试属性test_attribute=T_attributelist中最小GINI系数的属性（6）划分T得到T1 T2子集（7）对于T1重复（1）-（6）（8）对于T2重复（1）-（6）
CART分类成本函数：
$J (k, t_{k}) = \frac{m_{l e f t}}{m} G_{l e f t} + \frac{m_{r i g h t}}{m} G_{r i g h t}$
G_left/right衡量左右子集的不纯度，m_left/right是左右子集的实例数量。
CART算法考虑到每个节点都有成为叶子节点的可能，对每个节点都分配类别。分配类别的方法可以用当前节点中出现最多的类别，也可以参考当前节点的分类错误或者其他更复杂的方法。CART算法仍然使用后剪枝。在树的生成过程中，多展开一层就会有多一些的信息被发现，CART算法运行到不能再长出分支为止，从而得到一棵最大的决策树。然后对这棵大树进行剪枝。
Scikit-Learn使用的是CART算法，该算法仅生成二叉树：非叶节点永远只有两个子节点（即问题答案仅有是或否）。但是，其他算法，比如ID3生成的决策树，其节点可以拥有两个以上的子节点。
CART是一种贪婪算法：从顶层开始搜索最优分裂，然后每层重复这个过程。几层分裂之后，它并不会检视这个分裂的不纯度是否为可能的最低值。贪婪算法通常会产生一个相当不错的解，但是不能保证是最优解。
决策边界
决策树是非常直观的，它们的决策也很容易解释，这类模型通常被称为白盒模型。与之相反的，随机森林或是神经网络被认为是一种黑盒模型。

估算类别概率

max_depth=2时，

print(tree_clf.predict_proba([[5,1.5]]))
print(tree_clf.predict([[5,1.5]]))
#[[0. 0.90740741 0.09259259]]
#[1]

计算复杂度

预测时，遍历决策树需要经历大约O(log₂(m))个节点，每个节点需要检测一个特征值。总体预测复杂度为：O(log₂(m))。
训练时，算法需要在所有样本上比较所有特征，复杂度为O(n×mlog₂(m))。对于小型训练集（几千个实例以内），ScikitLearn可以通过对数据预处理（设置presort=True）来加快训练，但是对于较大训练集而言，可能会减慢训练的速度。

正则化超参数

为避免过度拟合，需要在训练过程中降低决策树的自由度。正则化超参数的选择取决于你所使用的模型，但是通常来说，至少可以限制决策树的最大深度。
DecisionTreeClassifier类还有一些其他的参数，同样可以限制决策树的形状：min_samples_split（分裂前节点必须有的最小样本数），min_samples_leaf（叶节点必须有的最小样本数量）， min_weight_fraction_leaf（跟min_samples_leaf一样，但表现为加权实例总数的占比），max_leaf_nodes（最大叶节点数量），以及 max_features（分裂每个节点评估的最大特征数量）。增大超参数 min_*或是减小max_*将使模型正则化。
还可以先不加约束地训练模型，然后再对不必要的节点进行剪枝（删除）。如果一个节点的子节点全部为叶节点，则该节点可被认为不必要，除非它所表示的纯度提升有重要的统计意义。标准统计测试，比如χ2测试，是用来估算“提升纯粹是出于偶然”（被称为虚假设）的概率。如果这个概率（称之为p值）高于一个给定阈值（通常是5%，由超参数控制），那么这个节点可被认为不必要，其子节点可被删除。直到所有不必要的节点都被删除，剪枝过程结束。
如以下对卫星数据集的决策树，左图模型过拟合，右图泛化效果更好。
###回归

from sklearn.tree import DecisionTreeClassifier,DecisionTreeRegressor
tree_reg=DecisionTreeRegressor(max_depth=2)
tree_reg.fit(X,y)

与分类相比，每个节点上不再是预测一个类别而是预测一个值。每个区域的预测值永远等于该区域内实例的目标平均值（标签值平均）。
CART回归成本函数：
$J (k, t_{k}) = \frac{m_{l e f t}}{m} M S E_{l e f t} + \frac{m_{r i g h t}}{m} M S E_{r i g h t}$
其中
$M S E_{n o d e} = <munder> \sum i \in n o d e </munder> ({<mover>}_{y Λ </mover> n o d e} - y^{(i)})^{2}, <mover> y Λ </mover> = \frac{1}{m_{n o d e}} <munder> \sum i \in n o d e </munder> y^{(i)}$
在处理回归任务时也需要考虑正则化的问题：
### 不稳定性
决策树正交的决策边界（所有的分裂都与轴线垂直），这导致它们对训练集的旋转非常敏感。
决策树的主要问题是它们对训练数据中的小变化非常敏感。如果你从鸢尾花数据集中移除花瓣最宽的Versicolor 鸢尾花（花瓣长4.8厘米，宽1.8厘米），然后重新训练一个决策树，可能会得到下图所示结果。