chapt6.org

决策树 decision tree

与SVM一样，Decision tree也是多功能学习算法，可以用于 分类 、 回归 、 多输出任务 。它能够拟合复杂数据集，是随机森林的组成部分。

决策树学习的目的是：产生一棵泛化能力强（即处理未见示例能力强）的决策树。 —— 周志华 《机器学习》

分类

sklearn实现示例：

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

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

tree_clf = DecisionTreeClassifier(max_depth=2, random_state=42) # 构建一个决策树
tree_clf.fit(X, y) # 训练一个决策树

export_graphviz( # 决策过程可视化，输出到dot文件
        tree_clf,
        out_file=image_path("iris_tree.dot"),
        feature_names=iris.feature_names[2:],
        class_names=iris.target_names,
        rounded=True,
        filled=True
    )

# 将dot文件用graphviz的dot倒序输出成png图片
dot -Tpng iris_tree.dot -o iris_tree.png

决策树优点：1. 需要的数据准备工作非常少，尤其不用特征缩放和集中，但要预处理缺失值。
          2. 它是白盒模型，不是黑盒模型（如神经网络）。

如何预测

决策树的预测过程直观地如上图所示，图中自上而下为根节点;没有子节点的称为叶节点， 储存了分类结果;有子节点的称为内部节点，储存了特征。这是个二叉树（CART算法导致）， 其他算法可以生成多叉树，但效率上讲，一般二叉树最高。

sample统计它应用的训练实例数量，gini衡量其不纯度（impurity）。gini不纯度的定义为：

G_i = 1 - ∑_i=1ⁿ p_i,k²

直观地讲，gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一样的概率。 因此，gini越小，D的纯度越高。 —— 周志华 《机器学习》P79

决策树也可以估算类别k的概率，方法如下：先跟随决策村找到该实例的叶节点，并将该节点 中类别k的实例占比，作为预测概率。

sklearn的预测实现如下：

>>> tree_clf.predict_proba([[5, 1.5], [6, 2.5]]) # 预测集合[[5, 1.5], [6, 2.5]]的类别概率
array([[0.        , 0.90740741, 0.09259259],
       [0.        , 0.02173913, 0.97826087]])
>>> tree_clf.predict([[5, 1.5]]) # 预测集合的类别
array([1])

注意：同一节点中的所有实例，它们的预测概率都是一样的。

如何训练

决策树的生成是一个递归过程。决策树学习的关键是如何选择最优级划分属性（特征）。一般而言， 我们希望随着划分过程地不断进行，决策树的分支节点所包含的样本尽可能属于同一类别， 即结点的纯度越来越高。

划分标准：

1. 信息增益（1986年Quinlan的ID3算法） 集合D的信息熵越小，则D的纯度越高。信息增益越大，用特征a划分后的信息熵越小， 纯度越高。信息增益定义为熵的减少量。
2. 信息增益率的启发式（1993年Quinlan的C4.5算法） 信息增益标准对可取值数目多的特征有偏好，而信息增益率标准对可取值数目少的特征有偏好。 信息率定义为：信息增益/属性a的固有值。
3. 基尼指数gini_index（1984年CART算法） gini_index(D,a) = ∑_v=1^V |D^v|/|D| gini(D^v) 并将划分后基尼指数最小的特征作为优先划分特征。 （此处还是多节点划分，不是二分？没有划分总阀值t_k ？） ——周志华《机器学习》P75

CART训练算法（分类与回归树）：

sklearn使用CART算法来训练决策树。想法非常简单：使用特征k和阀值t_k将训练集一分 为二，优化成本函数以寻找能产生最纯子集的划分方案(k, t_k)。一旦成功二分，它将使 用相同的逻辑继续二分。直到达到最大深度，或再也找不到能够提高纯度的二分，才会停止。

CART分类的成本函数：

J(k,t_k) = (m_left/m) * G_left + (m_right/m) * G_right

其中m_left/right为左右子集的实例数量;G_left/right为左右子集的不纯度。

训练的总体复杂度为 O(n*mlog(m)),预测的总体复杂度为 O(log₂(m))。对于几千的小训练 集，可以用presort=True加快训练。

gini vs 香农熵？

设置超参criterion=”entropy”来使用信息熵（香农熵）作用不纯度的测量方式。它们几乎没有 区别，gini计算速度略快，所以作为默认选择。区别在于：gini倾向于从树中分裂中常见类别， 而信息熵则趋于产生更平衡的树。

如何正则？

决策树极少对训练数据作出假设（比如线性模型就相反，它假设数据是线性的），如不加限制，树结构将 跟随训练集变化，严密拟合，很有可能过拟合。

这种模型称为 非参数模型 ，在训练前没有确定参数的数量，导致模型结构自由而紧密地贴近数据。 相应地， 参数模型 预先设定好了一部分参数，自由度受限，降低了过拟合风险，也可能拟合不足。

可以在训练时加入正则化来降低决策树的自由度，比如在sklearn的实现中可以增大超参min_*或减 小max_*使模型正则化。

剪枝 :

剪枝是对付过拟合的主要手段。在决策学习中，有时会产生过多分支，学习地太好，以致于把训练集 自身的一些特点当作所有数据都具有的一般性质而导致过拟合。可主动去掉一些分支来降低过拟合。

剪枝的基本策略有 预剪枝 和 后剪枝 。预剪枝在决策树生成过程中，对每个节点划分前进行 估计， 节点的划分能否提升决策树的泛化性能？ ，不能则停止划分，并将当前节点标记为叶节点。 后剪枝则先从训练集产生一棵完整的决策树，然后 自下而上 对非叶节点进行考察， 如果将此节点 对应的子树替换为叶节点能提升决策树的泛化性能, 则替换。

可以用交叉验证来判断是否提升了泛化能力。 ——周志华《机器学习》P79

回归

决策树也可以用于回归任务，sklearn的示例代码如下：

from sklearn.tree import DecisionTreeRegressor

tree_reg = DecisionTreeRegressor(max_depth=2) # 构建一个回归决策树
tree_reg.fit(X, y) # 训练一个回归决策树

如何预测

与分类相同，从根节点遍历，最后到达叶节点，并将此叶节点所有实例的目标平均值作为预测结果。 同样地，同一节点的预测值相同！

如何训练

训练算法依然是CART，唯一不同在于，它二分训练集的方式不是最小化不纯度，而是最小化MSE。 决策树回归的成本函数如下：

J(k,t_k) = (m_left/m) * MSE{left} + (m_right/m) * MSE{right}

其中，MSE_node = ∑_{i in node} (y_node - y⁽ⁱ⁾)², y_node = ∑_{i in node} y⁽ⁱ⁾/m_node

如何正则

与分类相同（如设置min_samples_leaf=10）

决策树的优缺点

优点：

• 容易理解和解释
• 使用简单，功能全面且强大

缺点：

对训练集的小变化十分敏感。比如，决策树更青睐正交的决策边界，导致对训练集旋转十分敏感， 解决方法之一是PCA（让数据写位在一个更好的方向上）。随机森林对许多树的预测进行平均， 可以限制这种不稳定性。

练习

Github上本书词条里有许多绘图函数值得学习，甚至可以复用。最好过一遍手！

• 在不加限制时，决策树学习得到的模型基本是平衡的，即每个叶节点只有一个实例。

那么对于m个实例的训练集，树的深度为 log₂^m（二叉树）。

• 训练的复杂度为n*m*log(m)，用于估算时间等占用资源。
• 子节点的gini不纯度不一定比父节点小，只要子节点的加权和比父节点小即可。
• 改变数组的维度：

>>> import numpy as np
>>> print(y_pred_split.shape, y_pred_split.ravel())
(1, 2500) (2500, )

• chapt6_exercise.ipynb