-
简述决策树的原理
决策树的实质就是一系列的if-else,根据决策条件,从根节点走到叶子节点。对于分类问题,根据叶子结点的标签进行投票决定;对于回归问题是根据叶子节点的均值作为预测值 -
信息量
- 发生概率越低的事件信息量越大
- 信息量必须大于0
- 信息量的累加性
基于上述三个特性,一个事件的信息量公式定义为h(x)= -log p(x)
-
信息熵
信息熵是度量信息“纯度”的指标。信息熵越大,越不纯。例如一张二维表,学号字段相比性别字段,信息熵要大得多
信息熵.png -
决策树结点划分
-
ID3
image.png
ID3是基于信息增益作为节点划分的标准,选择信息增益最大进行划分。
-
C4.5
image.png
由于ID3只考虑了信息增益,没有考虑分裂字段本身的“信息熵”。假如有一个字段“学号”,每个学号对应唯一的label,那么根据信息增益公式,这个字段的信息增益一定是最大的,但是这个字段真的适合分裂吗?肯定不是的。C4.5相比ID3,优化了分裂倾向选择类别多的字段,选择信息增益率最大进行划分
-
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
网友评论