机器学习丨决策树
决策树
分类树
如何选择每个结点划分的特征？
- 最大化纯度
什么时候停止划分？
结点只有一种类别
划分当前结点会导致树的深度超过最大限制
当划分带来的信息增益小于某个阈值
结点中的样本数小于某个阈值
纯度：用熵值来衡量
得到每个子结点的熵值后，根据每个结点的样本数对熵值进行加权平均。然后用原本结点的熵减去分裂后子结点熵的加权平均，得到分裂产生的信息增益：
- 所有样本一开始都放在根结点
- 计算按所有可能特征划分的信息增益，选择信息增益最大的特征
- 根据该特征将数据集划分为左右分支
- 使用以上划分方法对左右子树进行划分，直到满足停止条件
以上基于每个特征只有两个分类的情况。当特征有更多分类时，需要使用one-hot编码。
对于连续特征， 需要选取一个阈值将所有样本划分为两类。阈值的选取需要经过多次尝试，一种方法是将所有样本的特征值排序，然后依次选两两特征值的中点作为阈值，如果有10个样本则要进行9次尝试。然后从所有阈值产生的信息增益中选取最大的。
回归树
回归树用于预测一个连续的值。
回归树叶结点的值为落入该结点的所有样本的平均值。
划分效果使用每个结点内所有样本的方差的加权平均进行评估。
使用根节点的方差减去每个子结点方差的加权平均，得到信息增益。
树的集成
使用单个决策树可能对数据集中的微小变化高度敏感。
Bagging
可以采用有放回抽样的方法来构建多个训练集。例如原训练集有N个样本，则对训练集进行N次有放回抽样，得到一个新的训练集。使用这种方法可以得到多个不同的训练集，从而训练出多棵（经验值为64~128）决策树。最终模型结果可由这些树投票决定。
事实上，如果仅使用以上方法构建多棵决策树，构建出来的决策树可能不会有太大区别。
随机森林：当我们在选择特征划分一个结点时，假如一共有n个特征，那么我们可以从中随机选取k个（k<n，例如
Boosting
Bagging方法是并行地训练多棵决策树，而Boosting方法则是依次训练，并且每棵决策树会更多地关注在前面的决策树预测效果不好的样本，从而将多个较弱的模型组合成一个较强的模型。
当我们进行有放回抽样以构造一棵决策树时，我们可以以更高的概率抽取已经训练好的决策树预测效果不好的样本。
梯度提升树（GBDT）
- 用
代表时间t的模型， - 每个时间步使用
拟合 ，即将预测的残差作为标签 ，其中η为超参数。之所以不直接让η=1是为了避免过拟合
可以使用XGBoost等包。
决策树和神经网络
决策树通常适用于结构化数据（即表格数据），而像图像、视频、文本这样的非结构化数据不太适合使用决策树。
决策树模型的运行速度很快，并且小型决策树是可解释的（我们可以打印出决策树，观察每个结点来弄清楚这棵决策树是怎么做决策的）。
相比之下，神经网络适合几乎所有数据，并且适合用来做迁移学习，但是神经网络的运行速度比较慢。除此之外，我们可以使用梯度下降同时训练多个整合在一起的神经网络，而决策树一次只能训练一个。