啼鸟还知如许恨

料不啼清泪长啼血

概述

决策树也是一种多功能的机器学习算法，它可以实现分类和回归任务，甚至是多输出任务。它们功能强大、能够拟合复杂数据集。

决策树训练和可视化

在鸢尾花上训练一个决策树分类器

 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)

输出一个图形定义文件

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

使用graphviz包中的dot命令行将其转换为图片
```
 dot -Tpng iris_tree.dot -o iris_tree.png
```

做出预测

决策树的特质之一是需要的数据准备工作非常少，完全不需要进行特征放缩

节点的samples属性统计它应用的训练实例数量；values属性说明该节点上每个类别的训练实例数量:如右下节点应用在0个Setosa、1个Versicolor和45个Virginica实例上；最后gini属性衡量其 不纯度。如果应用的所有实例都属于同一类别，那么节点就是纯的（gini=1），绿色节点基尼系数计算：\(1 - (0/54)^2 - (49/54)^2 - (5/54)^2 \approx 0.168\)

基尼不纯度计算公式：

决策边界：

估算类别概率

决策树同样可以估算某个实例属于特定类别k的概率，即返回叶节点中改节点类别k的训练实例占比。

tree_clf.predict_proba([[5, 1.5]])
tree_clf.predict([[5, 1.5]])

可知此时最大可能是第一类，即Versicolor

CART训练算法

Scikit-Learn使用分类与回归树（CART）算法来训练决策树。首先，使用单个特征k和阈值\(t_k\)将训练集分为两个子集。k和\(t_k\)经算法搜索确定的产生最纯子集的值，算法的成本函数是：

一旦将训练集成功一分为二，它将使用相同的逻辑，继续分裂子集，直到到达最大深度或者再也不能降低不纯度。

计算复杂度

决策时需要从根到叶遍历决策树，因此大约要经历\(O(log_2(m))\)个节点，每个节点只要检查1个特征，因此总体预测复杂度也是\(O(log_2(m))\)，与特征数量无关，预测很快。
但是训练时，每个节点都需要在所有样本上比较所有特征，导致训练复杂度是\(O(n \times mlog(m))\)，对于小型数据集（几千个实例以内）可以通过预处理（presort=True）来加快训练；对于大型数据集，就很慢了。

信息熵

默认使用基尼不纯度作为不纯度的测量方式，也可以将超参数criterion设置为entropy来选择信息熵作为不纯度的测量方式。熵是一种分子混乱程度的度量：如果分子保持静止和良序，则熵接近0。后来根据香农的信息理论，如果所有信息相同，则熵为0。在这里，如果数据集中只包含一个类别的实例，则熵为0。绿色节点熵值为：\(-49/54log(49/54) - 5/54log(5/54)) \approx 0.31\)

信息熵：

正则化超参数

决策树很少对训练数据进行假设（线性模型明显假设训练数据是线性的），如果不加限制，很有可能过拟合，这种模型叫做 非参数模型。为避免过拟合，需要对决策树加以限制，降低决策树自由度，即正则化。
限制参数：

max_depth 决策树最大深度
min_samples_split 分裂前节点必须有的最小样本数
min_samples_leaf 叶节点必须有的最小样本数
min_weight_fraction_leaf 叶节点必须的加权实例总数占比
max_leaf_nodes 最大叶节点数量
max_fretures 分裂每个节点评估的最大特征数量

可以先不加限制地训练模型，然后对不必要的节点进行剪枝。

约束前后对比如上，右边模型泛化更好。

回归

决策树也可以进行回归任务

X = np.random.randint(0,1000,100).reshape(-1,1)
y = X * X + 1
tree_reg = DecisionTreeRegressor(max_depth=2)
tree_reg.fit(X, y)
export_graphviz(
	tree_reg,
	out_file='tree_reg.dot',
	rounded=True,
	filled=True
	)

由于只是测试，每个节点的mse都很糟糕。其与分类树的差别在于，每个节点不再是预测一个类别，而是预测一个值，算法分裂每个区域的方法，就是使更多的实例接近这个预测值。
CART算法工作原理与之前基本相同，只是分裂训练集的方式不再是最小话不纯度，而是最小化MSE。成本函数如下：

回归决策树也需要约束

如图所示，约束之后的模型更合理。

不稳定性

决策树很容易理解和解释，但有一些限制，比如对数据旋转很敏感。

如图，旋转后的数据应用决策树时，决策边界产生了不必要的卷曲，因此可以使用PCA，让训练数据定位在一个合适的方向上。

总结

子节点的基尼不纯度通常是低于其父节点的
决策树过拟合时，可以尝试减少max_depth
决策树欠拟合时，缩放输入特征并无影响

机器学习（六）

决策树

概述