第四章 决策树

策略：分而治之；

决策树的生成是一个递归过程，有三种情况下会返回：（1）当前结点属于同一类别，无需划分（2）当前的属性集为空，无法划分（3）当前结点包含的样本集合为空，不能划分；

如何选择最优划分属性

（1）信息熵越小，样本的纯度越高；$|\mathcal{Y}|$表示类别数目；

$$\mathrm{Ent}(D)=-\sum_{i=1}^{|\mathcal{Y}|}p_k\log p_k$$

（2）信息增益：所有在$a$属性上取值为$a^v$的样本，记为$D^v$; 而信息增益表示特征$a$对样本纯度的提升程度；

$$\mathrm{Gain}(D,a) = \mathrm{Ent}(D)-\sum_{v=1}^{|\mathcal{V}|}\frac{|D^v|}{|D|}\mathrm{Ent}(D^v)$$

ID3算法选择信息增益最大的属性为划分属性

（3）增益率：信息增益准则对于可取值数目较多的属性有偏好，为减少不离影响，故引入增益率来选择划分属性;

$$\mathrm{Gain\_ratio}(D,a)=\frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)}\\ 属性a的固有值：\mathrm{IV}(a)=-\sum_{v=1}^{|\mathcal{V}|}\frac{|D^v|}{|D|}\log\frac{|D^v|}{|D|}$$

增益率准则对取值较少的属性有偏好，

C4.5算法不直接采用信息增益，而采用一种启发式想法：从候选属性中找出信息增益高于平均水平的，再选择增益率高的；

（4）基尼指数

$$\mathrm{Gini}(D)=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2\\ \mathrm{Gini\_index}(D,a)=\sum_{v=1}^{|\mathcal{V}|}\frac{|D^v|}{|D|}\mathrm{Gini}(D^v)$$

CART决策树中选择划分后基尼指数最小的属性作为最优划分属性

决策树的剪枝处理

剪枝：处理过拟合的重要手段；

（1）预剪枝：基于贪心的本质）

对划分前后的泛化性能进行估计，若划分后精度更高，则选择划分；否则该结点不深入划分；

优点：可以节省计算开销；缺点：具有欠拟合的风险

（2）后剪枝

生成一个完整的决策树后，考察叶结点的父结点，若剪枝后精度提高则剪枝，否则保留该结点；

优点：欠拟合风险小，泛化性能更好；缺点：时间开销较大；

连续值的处理

---

• ← Previous Post
• Next Post →