《统计学习方法》读书笔记5:决策树

  1. 决策树像是if-then的规则集合。
  2. 决策树很可能发生过拟合现象,这时需要自下而上的剪枝。决策树的生成只考虑局部最优,而剪枝考虑全局最优。
  3. 特征选择时需要选取具有分类能力的特征,如果利用一个特征进行分类与随机分类的结果没有区别,则称这个特征没有分类能力。通常特征选择的标准是信息增益或信息增益比。
  4. 信息增益
    1. 熵(entropy)表示的是一个随机变量不确定的程度。设$X$是一个取有限值的离散随机变量,它的熵定义为
      $$ H(X)=-\sum_{i=1}^Np_i \log p_i $$
      如果与 $X$ 取值无关,只与其分布有关,还可以记作 $H(p)$。对数以2为底时,熵的单位为比特(bit);以 $e$ 为底时,单位为奈特(nat)。
    2. 条件熵 $H(Y|X)$ 表示已知 $X$ 的条件下,随机变量 $Y$ 的不确定程度
      $$
      H(Y|X)=\sum_{i=1}^Np_iH(Y|X=x_i)
      $$
    3. 信息增益:指给定特征 $A$ 的情况下,训练数据集 $D$ 的不确定性的减少量
      $$
      g(D, A) = H(D) - H(D|A)
      $$
      在信息论中称为互信息。$H(D)$ 是由训练集的经验概率得到的,所以称为经验熵
    4. 在实际选取过程中,根据信息增益大小选择特征
    5. 为了解决偏向于选择取值较多的特征的问题,可以用信息增益比:
      $$
      g_R(D,A) = \frac{g(D,A)}{H_A(D)}
      $$
      其中,$ H_A(D) = -\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|} $
  5. 决策树的生成
    1. ID3算法:每次挑选信息增益最大的特征分裂数据集,直到信息增益小于某一阈值。
    2. C4.5算法:改进了ID3算法,使用信息增益比
  6. 决策树的剪枝
    1. 决策树的剪枝通过极小化决策树的损失函数完成。
    2. 决策树的损失函数定义为
      $$
      C_\alpha(T)=\sum_{i=1}^{|T|}N_tH_t(T)+\alpha|T|
      $$
      其中,经验熵为
      $$
      H_t(T)=-\sum_k\frac{H_{tk}}{N_t}\log\frac{N_{tk}}{N_t}
      $$
      通常,记
      $$
      C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log\frac{N_{tk}}{N_t}
      $$
      这时有
      $$
      C_\alpha(T)=C(T)+\alpha|T|
      $$
    3. 设一组节点回缩到其父节点之前与之后的整体树分别为$T_B$与$T_A$,其对应的损失函数分别为$C_\alpha(T_B)$与$C_\alpha(T_A)$,如果
      $$
      C_\alpha(T_A)\leq C_\alpha(T_B)
      $$
      则进行剪枝,即将父节点变为新的叶节点。重复这一过程,直至不能进行为止。
  7. CART算法
    1. CART(classification and regression tree)
    2. 回归树:X和Y分别为输入变量与输出变量,且Y为连续变量
    3. 分类树
      1. 基尼系数
      2. 根据基尼系数生成回归树

标签: none

添加新评论