决策树

分类 回归 有监督学习

---

主要思想

决策树（Decision tree）由一个决策图和可能的结果（包括资源成本和风险）组成， 用来创建到达目标的规划。决策树建立并用来辅助决策，是一种特殊的树结构。决策树是一个利用像树一样的图形或决策模型的决策支持工具，包括随机事件结果，资源代价和实用性

产生背景

ID3 1986年提出
C4.5 1993年提出
CART 1984年提出

应用场景

• 常见分类问题/回归问题
• 特征选择

核心理解

决策树表示给定特征条件下类的条件概率分布。

主要推导

ID3

信息熵

$$H(D) = - \sum\limits_{k = 1}^K {{p_k}\log _2^{{p_k}}}$$

$${p_k} = {{\sum\limits_{j = 1}^N {I({y_j}{\rm{ = }}{{\rm{c}}_k})} } \over N}$$

条件熵
使用特征${X^i}$对数据集进行分类，假定特征${X^i}$有${S_i}$维

$$H(D|{X^i}) = \sum\limits_{j = 1}^{{S_i}} {{{|{D_j}|} \over N}H({D_j})}$$

信息增益

$$g(D,{X^i}) = H(D) - H(D|{X^i})$$

C4.5

信息增益会偏袒取值较多的特征

可以使用增益率解决这一问题

$${g_R}(D,{X^i}) = {{g(D,{X^i})} \over {{H_{{X^i}}}(D)}}$$

$${H_{{X^i}}}(D) = \sum\limits_{j = 1}^{{S_i}} {{{|{D_j}|} \over N}\log _2^{{{|{D_j}|} \over N}}}$$

CART

CART可以用来分类，也可以用来做回归。

此种决策树每次都进行二分。

1. 回归

最小化平方误差。

选择第j个变量和他的取值s作为划分，c代表类中实例输出结果均值。

$$\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}} ]$$

2. 分类

基尼指数定义:

$$Gini(D) = 1 - \sum\limits_{k = 1}^K {{{({{|{D_k}|} \over N})}^2}}$$

通过判断特征${X^i}$是否取某一特定值把数据集分为两类${D_1}$和${D_2}$:

$$Gini(D,{X^i}) = {{|{D_1}|} \over N}Gini({D_1}) + {{|{D_2}|} \over N}Gini({D_2})$$

在所有可能的特征${X^i}$和划分中选择基尼指数最小的做划分。

求解算法

与推导过程类似，使用贪心的策略迭代求解。

伪代码

输入:数据集D(N个样本),特征集合X
过程:
genarateTree(D,Xi)
    生成节点node
    if D中所有样本属于同一类别
        将node标记为此类别/回归为均值 return
    end if
    if X为空集或者D中样本在X上取值相同
        将node标记为D中较多的样本的类/回归为均值 return
    end if
    选择最优划分Xi
    for Xi = 所有的可能取值
        在X中去掉Xi这一维，命名为X’
        D’为Xi取当前值的样本子集
        genarateTree(D’,X’)
    end for
输出:完整的决策树

复杂度分析

to be done

大数据下改进

评价

• 优点

  • 计算量简单，可解释性强
  • 比较适合处理有缺失属性值的样本
  • 能够处理不相关（没用的）的特征
  • 是一个白盒模型，给定一个模型，很好推出逻辑表达式

• 缺点

  • 单颗决策树分类能力弱
  • 容易过拟合（剪枝，随机森林减小了过拟合）

算法改进

• 随机森林
• GBDT

参考资料

1. wiki

2. 机器学习常见算法个人总结