决策树

决策树是最符合人类思考模式，最容易被理解和解释的模型之一，所以在一些需要可解释性的场景下经常使用，其训练过程相比其他机器学习算法也更加通俗易懂

训练过程

1. 初始情况下生成一个根节点，所有的数据都在这一个节点之内。
2. 寻找一个最能区分开不同类样本的最优划分属性，按照样本在该属性上取值的不同，分配到不同的下一级的子节点上。
3. 如果某个节点上没有了样本或者可用来划分的属性或者样本都属于同一个类，则停止生成下一级节点，否则继续2中步骤生成更深的决策树。
4. 每个叶节点被标记为该节点样本最多的那个类别，预测新样本时，从根节点开始判断新样本的各个属性值，最后落到的叶节点的类别就是预测得出的新样本类别

最优划分属性

最优划分属性存在一个发展历史，也是一些经典决策树算法的提出历史。

如最开始的ID3决策树，利用划分前后的信息增益作为标准选择最优划分属性。

其中Ent为信息熵，Gain即为原节点不划分时的信息熵减去减去划分后节点带上样本个数权重的信息熵之和。

但是上述方法存在天生偏好，如果某个属性取值本来就很多，那么生成很多节点，节点的纯度就会比较高就特别容易被选取为划分属性。
所以之后又提出了C4.5决策树，利用信息增益率作为划分属性。

相当于给信息增益除了一个该属性的一个固有值（取决于属性取值个数）来平衡这种影响。
当时上式又矫正过枉了，对于取值少的属性有偏好，虽然实际实现时采用一种启发式思想，先找出增益大于平均水平的，再在里面找增益率高，但总归不是那么美好，于是就有人提出了CART树，使用基尼指数作为评价指标。
一个数据集的纯度用基尼指数衡量的话，最直观的解释就是任选两个样本，它们属于不同类别的概率。
那么一个属性划分的好坏就可以看划分总结点的基尼指数带权中之和了，选择最小的当作划分属性。

连续和缺失值

连续值会根据样本出现的值情况计算出候选划分点进行划分。
出现缺失值的话，可以不考虑出现缺失的样本先进行计算划分属性的数值，再乘上这个属性的缺失比作为最终比较的数值。

剪枝操作

预剪枝

预剪枝很好理解，就是在决策树生成时候提前终止一些节点继续向下分裂，可能因为该次分裂对结果没有提升或者精度更低，这样使得决策树更加简单，泛化性能更好，时间开销小，但是因为有些分支没有展开，可能陷入局部最优解，带来欠拟合风险。

后剪枝

后剪枝即是在决策树生成之后，对一些分支进行修剪完成简化，把一些节点换成叶节点，阻断这条分支路径。该方法基于极小化决策树的损失函数。

注意虽然出现了经验熵，但是第一项可以展开写成

可以看到里面一层和LR推导损失的形式几乎一致，所以决策树的损失函数应该为极大似然损失，先最大化每个节点的极大似然，再到整棵树的极大似然。

多变量决策树

决策树选择单一属性作为划分标准时，对样本的划分边界会是和坐标轴平行的。

但是如果每个节点是一个线性分类器，参考多个变量的话模型就会更加简化。

CART树

CART树是一种可以用于分类和回归问题的决策树，虽然回归的效果一般不咋滴哈哈。
需要注意的CART假设是个二叉树，节点分支只有‘是’和‘否’两种选择。

决策树回归过程

用于回归任务的话，预测值是一个连续变量，上述的寻找最优划分属性的方法就要更改为

寻找某个属性的某个取值多为切分点，目的是让左右子树中样本和切分点的平方误差最小，叶节点中样本标签的平均值当作这个叶节点标记。

CART剪枝

回忆决策树的损失函数

对T中每一个内部节点t计算

即是寻找让整棵树T和把内节点t分支剪掉的树损失函数相等的a阈值，剪掉a最小的树后便得到了一个a对应的最优子树。重复剪枝过程，在得到的从完整决策树到一个决策树桩的一系列树中进行交叉验证取结果最好的决策树作为结果返回。

相关面试题

1.决策树将特征的尺度变化有什么影响?
没有任何影响，因为决策树是将样本划分之后计算类别概率，特征尺度放缩不影响用取值划分样本集。
2.决策树的损失函数是什么？
上文提过了，虽然长得就像经验熵，但是整理之后是极大似然损失。