南山小马

南山小马

0%

决策树笔记

发表于 更新于 分类于 Disqus：

特征选择

准则

信息增益 或 信息增益比

信息增益：
表示得知特征X的信息而使得类Y的信息不确定性减少的程度。 特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差。

$$g(D,A) = H(D) - H(D|A)$$

信息增益比：
以信息增益作为划分训练集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。

$${g_R}(D,A) = \frac{{g(D,A)}}{{{H_A}(D)}}$$

决策树的生成

ID3算法

应用信息增益准则选择特征，递归地构建决策树。

C4.5算法

用信息增益比来选择特征。

决策树的剪枝

防止过拟合
极小化决策树的整体损失函数(loss function)或代价函数(cost funciton)

$${C_\alpha }(T) = \sum\limits_{t = 1}^{|T|} {{N_t}{H_t}(T) + \alpha |T|}$$

其中${H_t}(T)$为叶节点$t$上的经验熵：

$${H_t}(T) = - \sum\limits_k {\frac{{{N_{tk}}}}{{{N_t}}}\log \frac{{{N_{tk}}}}{{{N_t}}}}$$

CART算法

分类与回归树(classification and regression tree, CART)，既可以分类也可以回归。
CART算法由以下两步组成：

  1. 决策树生成；
  2. 决策树剪枝。

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。

决策树生成

回归树

《统计学习》 P69
最小二乘回归树生成算法：
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：

  1. 选择最优切变量j与切分点s，（可以用平方误差来表示回归树对于训练数据的预测误差）
$$\mathop {\min }\limits_{j,s} [\mathop {\min }\limits_{{c_1}} \sum\limits_{{x_i} \in {R_1}(j,s)} {{{({y_i} - {c_1})}^2}} + \mathop {\min }\limits_{{c_2}} \sum\limits_{{x_i} \in {R_2}(j,s)} {{{({y_i} - {c_2})}^2}} ]$$

遍历遍历j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对(j,s)

  1. 用选定的对(j,s)划分区域并决定相对应的输出值： $${R_1}(j,s) = \{ x|{x^{(j)}} \leqslant s\} ,{\text{ }}{R_2}(j,s) = \{ x|{x^{(j)}} > s\}$$ $${\hat c_m} = \frac{1}{{{N_m}}}\sum\limits_{{x_i} \in {R_m}(j,s)} {{y_i}} ,{\text{ }}x \in {R_m},{\text{ }}m = 1,2$$
  2. 继续对连个子区域调用步骤1,2，直至满足停止条件；
  3. 将输入空间划分为M个区域R1, R2, …, RM，生成决策树。 $$f(x) = \sum\limits_{m = 1}^M {{{\hat c}_m}I(x \in {R_m})} $$

分类树生成

基尼指数
分类问题中，假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为：

$$Gini(p) = \sum\limits_{k = 1}^K {{p_k}(1 - {p_{\text{k}}}) = 1 - } \sum\limits_{k = 1}^K {p_k^2}$$

如果样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，即

$${D_1} = \{ (x,y) \in D|A(x) = a\} ,{D_2} = D - {D_1}$$

特征在A的条件下，集合D的基尼指数定义为

$$Gini(D,A) = \frac{{|{D_1}|}}{{|D|}}Gini({D_1}) + \frac{{|{D_2}|}}{{|D|}}Gini({D_2})$$

基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。

CART生成算法(p 70)：

  1. 计算现有特征对训练数据集的基尼指数。 此时，对每一个特征A，对其可能取的每个值a，根据样本点A=a的测试为“是”或“否”将D分为D1和D2两部分，利用Gini(D,A)计算A=a时的基尼系数；
  2. 在所有可能的特征以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点；依最优特征与最优切分点，从现节点生成两个子节点，将训练数据集依特征分配到两个子节点中去；
  3. 对两个子节点递归地调用（1），（2），直至满足停止条件。

算法停止计算的条件是节点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。

总结

  1. 决策树学习算法包括3部分：特征选择、树的生成、树的剪枝。
  2. 决策树的生成：通常使用信息增益最大、信息增益比最大或基尼指数最小作为特征选择的准则。
  3. 决策树的剪枝：往往从已生成的树上减掉一些叶节点或叶节点以上的子树，并将其父节点或根节点作为新的叶节点，从而简化生成的决策树。