决策树

1. 基本流程

  • 学习目的:为了产生一颗泛化能力强的决策树
  • 基本流程:分而治之,不断选择最优划分属性
  • 决策树生成是一个递归的过程,递归返回的三种情况:
    • 节点包含样本是同一类别
    • 属性集为空or样本所有属性取值相同
    • 样本集为空

2. 划分选择

  • 划原则:树的分支节点所包含的样本尽可能的属于同一类别,即节点的“纯度”越来越高

2.1 信息增益(ID3)

  • “信息熵”是度量样本集合纯度常用的一种指标
    • 设样本集合D中第k类样本所占的比例为p_k(k=1,2,......,y),则D的信息熵定义为:
      Ent(D) = -\sum_{k=1}^yp_klog_2p_k

    Ent(D) 的值越小,D的纯度越高

  • 用属性a对样本集D进行划分所获得的“信息增益”(information gain)为:

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

  • 一般的,信息增益越大,意味着使用属性a来进行划分所获得的“纯度提升”越大,再以信息增益为准则来划分属性

2.2 增益率(C4.5)

  • 信息增益准则对可选取数目较多的属性有所偏好,为了减少这种偏好可能带来的不利影响,著名的C4.5决策树算法不直接使用信息增益,而是使用“增益率”来选择最优划分属性。
  • 增益率定义为:
    Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}

    IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}

  • 增益率称为属性a的“固有值”,属性a的可能取值数目越多(V越多),则IV(a)的值通常会越大

  • 增益率准则对可选取数目较少的属性有所偏好,因此C4.5算法并不是直接选择增益率最大的候选划分属性,而是先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的

2.3 基尼系数(CART)

  • 基尼系数反映了从数据集D中随机抽走两个样本,其类别不一致的概率,因此其基尼系数越小,数据集D的纯度越高
  • 数据集D的计算:
    Gini(D) = -\sum_{k=1}^{|y|}\sum_{k^,!=k}^{|y|}p_kp_k,=1-\sum_{k=1}^{|y|}p_k^2

  • 属性a的基尼系数为:
    Gini_index(D,a) = -\sum_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)

    计算得到每个属性的基尼系数后,在候选属性集合A中,选择使划分后基尼指数最小的属性作为最优划分属性。

3. 剪枝处理

  • 目的:降低过拟合风险

3.1 预剪枝

  • 在决策树生成过程中,对每个节点在划分前先进行估计,若当前划分不能带来决策树泛化能力的提升,则停止划分并把当前节点标记为叶子节点
  • 判断泛化能力的方法:将数据集切为训练集和验证机,不断计算验证集精度,来确定剪枝与否
  • 优点:降低过拟合风险,同时显著减少了决策树的训练时间开销和测试时间开销
  • 缺点:预剪枝基于“贪心”本质禁止这些分支展开,可能带来欠拟合的风险

3.2 后剪枝

  • 先从训练集生成一颗完整的决策树,然后自底向上对非叶子节点进行考察,若将该节点替换成叶节点能带来决策树泛化能力的提升,则将该子树替换为叶节点。
  • 判断泛化能力的方法同预剪枝
  • 优点:后剪枝通常比预剪枝保留了更多的分支,欠拟合风险较小,泛化性能往往优于预剪枝
  • 缺点:训练时间开销大

4. 连续与缺失值

4.1 连续值处理

  • 最简单的策略是采用二分法对连续属性处理(C4.5决策树算法采用的),对于属性a的n个可取值,划分为n-1个元素候选划分集合,然后像离散属性值一样来考察这些分类点,选取最佳分类点来进行样本集合的划分
  • 与离散型不同,连续属性还可以作为节点的后代节点的划分标准

4.2 缺失值处理

5. 多变量决策树

  • 目的:在属性坐标空间中,决策树的边界都是与轴平行的,面对一些复杂问题时,“多变量决策树”可以实现“斜划分”甚至更复杂的划分
  • 多变量决策树的学习过程中,不是为每个非叶子节点寻找一个最优划分属性,而是试图建立一个合适的线性分类器(有点像感知机和神经网络的区别)

参考文献

  • 周志华《西瓜书》
  • 李航《统计学习方法》

我的心不为谁而停留,但心总要为谁而跳动~