决策树

算法过程

1. 特征选择
2. 生成决策树
3. 决策树兼职

特征选择

选择下面 2 指标作为特征选择的依据

1. 信息增益：使用熵和条件熵来计算
2. 信息增益比：使用信息增益和特征的熵来计算

生成决策树

1. ID3算法：使用信息增益作为特征选择指标
2. C4.5算法：使用信息增益比作为特征选择指标
   选定特征之后要再选择一个阈值作为切分点

决策树剪枝

计算剪枝前后的整体树的损失函数值来决定是否需要剪枝
损失函数需要计算所有叶子节点的经验熵

CART树

CART树是二叉树，只有 是 和 否 两种切分特征

回归树

回归树使用平方误差最小作为切分准则
我们先选择输入样本 x 并且从它的取值内确定一个切分值s，然后计算由这个切分值导致的损失函数。然后不断的遍历取值 s，也就是针对 s 的取值不断的进行计算。得到不同 s 下的损失函数值。选择输入样本中损失函数 s 值最小的x作为切分变量和切分值。然后将样本集切分开。
接着，继续对切分开的 2 个区域继续进行同样的计算，继续分别找出各自的 s 值进行切分。直到满足条件
参考附录《Regression Tree 回归树》

分类树

分类树使用基尼指数最小化作为切分准则
可以通过计算，找出样本集D中的特征A在值为a时，基尼指数最小。使用该特征和特征值作为且分点，然后继续对切分后的 2 个区域继续找下一个特征

CART剪枝

剪枝分 2 个部分

1. 生成子树序列
2. 交叉验证取出最优子树

生成子树序列

1. 对CART树的每一个内部节点t，计算g(t)。
2. 将 g(t) 最小的子树剪掉(即以 t 为根节点的子树，将这一整棵子树剪掉)
3. 将这个最小的g(t) 设为 an，此时的CART树是[an,an+1)区间的最优子树Tn
4. 在对剪完枝的CART树上继续对每一个内部节点计算g(t)，重复上面的操作，直到根节点。

完成之后就可以得到我们的CART树序列T1，T2，T3，...，Tn

在这个过程中，an+1 > an

需要注意的是，在计算g(t)的过程中，C(Tt)是指训练数据的误差，即子树Tt的训练误差，可以通过计算这棵子树所有子节点的基尼系数总和来表示。

CART树的每个节点是一个特征，并不是一层是一个特征。
比如样本集被切分之后分为A和B，取其中一个样本集A再去计算基尼指数最小的特征和切分值未必和样本集B中的基尼指数最小的特征和切分值是一样的

验证CART树序列

使用交叉验证法，参考附录链接《cart决策树剪枝的个人理解》

思维导图

image.png

附录

Regression Tree 回归树：https://blog.csdn.net/weixin_40604987/article/details/79296427
cart决策树剪枝的个人理解：https://blog.csdn.net/wqtltm/article/details/82597334