递归终止条件

决策树使用递归实现，而递归终止条件有以下三种：

当前结点所有样本属于同类，无需划分
当前属性集为空，无法划分，选取此节点中数量更多的标记作为类别标记
当前样本集为空，不能划分，依据父节点中数量更多的标记作为类别标记

名词概念

1.纯度：同类聚集程度高、不同类越分散，则纯度越高
2.信息熵：纯度的量化指标，来源于信息论
3.剪枝：防止决策树过拟合，减去部分划分属性。分为预剪枝和后剪枝

信息熵

信息熵计算公式：
$$ E n t ( D ) = - \sum _ { k = 1 } ^ { | y | } p _ { k } \log _ { 2 } p _ { k }$$
信息熵用于衡量信息的不确定性或信息的混乱程度，我们可以将其用于量化纯度
信息熵越大，数据分布越均匀、随机、杂乱无章，明显这不是我们想要的。我们想要的是相同类靠近，不同类远离的效果，即需要越小的信息熵

$p_k$表示选到k类别的概率，而 $-\log _ { 2 } p _ { k }$则表示信息量

1	我们可以理解对于某一事件，其发生的概率越小，那么其信息量越大；发生的概率越大，那么其信息量越小。所有对两者求期望即得到信息熵。

注意：此处计算公式里的Y的输出值种类，如二分类问题中Y=2

划分选择

决策树中最重要的部分，用于选择最佳划分属性

1.信息增益(Information Gain)

计算某属性的信息增益，用根节点的信息熵-属性各个属性值的信息熵的加权平均值
信息增益越大，意味着使用属性a进行划分获得的纯度提升越大
$$ Gain ( D , a ) = E n t ( D ) - \sum _ { v = 1 } ^ { V } \frac { | D ^ { v } | } { | D | } E n t ( D ^ { v } )$$

2.增益率(Gain Ratio)

由于信息增益对于取值数目较多的属性有所偏好，所以引进增益率进行选择最优划分属性，比如著名的C4.5决策树算法

当属性a的可能取值数目越多时(即V越大)，IV(a)越小，相应的增益率就越大

我们可以这样理解，IV(a)计算的其实就是信息熵，当属性值数目越多时，样本分类就越多且彼此之间就越分散越混乱，而我们希望分类效果越好，就需要减少属性值可能取值个数。

$$ Gain \space R a t i o ( D , a ) = \frac { G ain( D , a ) } { I V ( a ) }$$
$$ I V ( a ) = - \sum _ { v } ^ { V } \frac { | D ^ { v } | } { D } \log _ { 2 } \frac { | D ^ { v } | } { D }$$

思考🤔：

增益率可以减少信息增益对于属性值较多的属性有所偏好的问题，但是同样的，增益率对于属性值较少的属性有所偏好所以实际处理时，对于不同的属性的划分选择可以采取不同的方法，但是在同一层属性划分选择时只能使用同一种方法。

3.基尼指数(Gini Index)

含义：反映从数据集中随机抽取两个样本，其类别标记不一致的概率

用于CART决策树，既可以用于分类问题，也可以用于回归问题

基尼指数越小，则数据集纯度越高
$$ G i n i ( D ) = 1 - \sum _ { k = 1 } ^ { | y | } p _ { k } ^ { 2 }$$$$ G i n i \space I n d e x ( D , a ) = \sum _ { v = 1 } ^ { V } \frac { | D ^ { v } | } { | D | } G i n i ( D ^ { v } )$$