决策树

一 简述

决策树的训练通常由三部分组成:特征选择树的生成剪枝

  • 分类树
    • ID3 决策树信息增益(选择信息增益最大的特征)
      • I(D,A) = H(D) – H(D|A) 样本为D,特征为A,H(D) 为熵, H(D|A) 为条件熵
      • 不能处理连续特征
      • 信息增益作为标准容易偏向于取值较多的特征
      • 无法处理缺失值
      • 存在过拟合问题
    • C4.5 决策树信息增益比(选择信息增益比最大的特征)
      • , ,特征熵𝐻𝐴(𝐷)
      • 连续特征离散化:
      • 多叉树运算效率比二叉树低
      • C4.5只能用于分类
      • C4.5由于使用了熵模型,里面有大量的耗时的对数运算
    • CART决策树基尼系数(选择基尼系数最小的特征)
      • , K个类别,第k个类别的概率为𝑝𝑘
      • , 给定的样本D,假设有K个类别, 第k个类别的数量为𝐶𝑘
      • , 样本D,如果根据特征A的某个值a,把D分成D1和D2两部分,则在特征A的条件下D的基尼系数
  • 回归树:

二 比较

三.缺失值处理(C4.5, CART较复杂, ID3不支持)

  • 样本某些特征缺失的情况下选择划分的属性
    • 对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分,对每个样本设置一个权重(初始可以都为1),然后划分数据,一部分是有特征值A的数据D1,另一部分是没有特征A的数据D2. 然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比,最后乘上一个系数,这个系数是无特征A缺失的样本加权后所占加权总样本的比例。
  • 选定了划分属性,对于在该属性上缺失特征的样本的处理
    • 可以将缺失特征的样本同时划分入所有的子节点,不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1,特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1,A2,A3。对应权重调节为2/9,3/9, 4/9。

四.连续特征和离散特征处理

  • 连续特征(离散化)
    • ID3:不支持
    • C4.5或者CART分类树:m个样本的连续特征A有m个,从小到大排列为𝑎1,𝑎2,...,𝑎𝑚,则C4.5取相邻两样本值的平均数,一共取得m-1个划分点,其中第i个划分点𝑇𝑖为:𝑇𝑖=(𝑎𝑖+𝑎_𝑖+1)/2。对于这m-1个点,分别计算以该点作为二元分类点时的信息增益比(或基尼系数)。选择信息增益比最大(或基尼系数最小)的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为𝑎𝑡,则小于𝑎𝑡的值为类别1,大于𝑎𝑡的值为类别2,这样我们就做到了连续特征的离散化
  • 离散特征:
    • ID3或者C4.5:如果某个特征A被选取建立决策树节点,如果它有A1,A2,A3三种类别,我们会在决策树上一下建立一个三叉的节点,这样导致决策树是多叉树
    • CART分类树:采用的是不停的二分,CART分类树会考虑把A分成{𝐴1}{𝐴2,𝐴3}{𝐴2}{𝐴1,𝐴3}{𝐴3}{𝐴1,𝐴2}三种情况,找到基尼系数最小的组合,比如{𝐴2}{𝐴1,𝐴3},然后建立二叉树节点,一个节点是A2对应的样本,另一个节点是{A1,A3}对应的节点。同时,由于这次没有把特征A的取值完全分开,后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这样导致决策树是二叉树

五.优缺点

  • 决策树算法的优点:
    • 1)简单直观,生成的决策树很直观。
    • 2)基本不需要预处理,不需要提前归一化,处理缺失值。
    • 3)使用决策树预测的代价是𝑂(𝑙𝑜𝑔2𝑚)。 m为样本数。
    • 4)既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
    • 5)可以处理多维度输出的分类问题。
    • 6)相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以得到很好的解释
    • 7)可以交叉验证的剪枝来选择模型,从而提高泛化能力。
    • 8) 对于异常点的容错能力好,健壮性高。
  • 决策树算法的缺点:
    • 1)决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
    • 2)决策树会因为样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
    • 3)寻找最优的决策树是一个NP难的问题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习之类的方法来改善。
    • 4)有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决。
    • 5)如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

六.参考

0