简述决策树的原理
决策树的实质就是一系列的if-else，根据决策条件，从根节点走到叶子节点。对于分类问题，根据叶子结点的标签进行投票决定；对于回归问题是根据叶子节点的均值作为预测值信息量
- 发生概率越低的事件信息量越大
- 信息量必须大于0
- 信息量的累加性
基于上述三个特性，一个事件的信息量公式定义为h(x)= -log p(x)
-
信息熵
信息熵是度量信息“纯度”的指标。信息熵越大，越不纯。例如一张二维表，学号字段相比性别字段，信息熵要大得多
信息熵.png -
决策树结点划分
-
ID3
ID3是基于信息增益作为节点划分的标准，选择信息增益最大进行划分。
image.png -
C4.5
由于ID3只考虑了信息增益，没有考虑分裂字段本身的“信息熵”。假如有一个字段“学号”，每个学号对应唯一的label，那么根据信息增益公式，这个字段的信息增益一定是最大的，但是这个字段真的适合分裂吗？肯定不是的。C4.5相比ID3，优化了分裂倾向选择类别多的字段，选择信息增益率最大进行划分
image.png -
CART
cart是基于基尼系数进行划分，分别计算各字段的基尼系数，选择最小的字段进行分裂，公式如下
image.png
-
-
ID3，C4.5，CART对比
image.png 树的剪枝
通过剪枝可以防止树节点过拟合，提高模型的泛化能力。剪枝方式分两种，预剪枝和后剪枝。根据周志华老师在西瓜书中的剪枝内容，思想是类似于XGBoost中的early stopping，如果在验证集效果不再提升，那么就不再进行分裂
- 预剪枝
在节点进行分裂时，计算验证集分裂前后精度是否降低。如果提高，继续分裂；否则停止分裂 -
后剪枝
先构建完整的决策树，自下向上进行查找，如果合并叶子节点后的精度相比合并前有提升，那么进行剪枝，将叶子节点的样本进行合并，并删除叶子节点
image.png
连续值处理
对于连续型特征，假设有n个样本的特征x取值为{x1,x2,...xn}，那么将x1,x2,...xn从小到大排序，取两两值的中点作为分割点，依次遍历每个分割点并计算信息增益(率)或基尼系数，选择对应的分割点作为最终的分割条件
注：对于连续型特征，特征选择后是可以继续作为后续的节点的分裂条件-
缺失值处理
根据是否缺失给样本赋予不同的权重，无缺失是1，缺失是0。当计算信息增益时，只考虑非缺失的样本，将最终结果乘以(1-缺失率)作为修正后的增益率
image.png
