决策树

由结点和有向边组成
- 结点有两种类型：
  - 内部结点（表示一个特征或属性）
  - 和叶结点（表示一个类）
决策树可视作是一个if-then规则的集合
- 路径上内部结点特征对应规则的条件
- 叶结点对应规则的结论
- 决策树路径互斥且完备
决策树的一条路径对应特征空间划分的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成
决策树学习本质上是从训练数据集中归纳出一组分类规则
步骤：特征选择——决策树的生成——决策树的修剪
- 决策树的生成对应于模型的局部选择，只考虑局部最优
- 决策树的剪枝对应于模型的全局选择，考虑全局最优
特征选择
1. 信息熵
  - 有限值离散随机变量X的熵定义为：
    - $H(X) = -\sum\limits^n_{i=1}p_i\log p_i$
    - $\log$通常以e或2为底
    - 也可记为$H(p)$
2. 条件熵
  - $H(Y | X)$ : 已知随机变量X的条件下，随机变量Y的不确定性
  - $H(Y|X)=\sum\limits^n_{i=1}p_iH(Y | X = x_i),\quad p_i = P(X=x_i),\text{ }i=1,2,…,n$
3. 信息增益
  - 表示得知特征X的信息而使得类Y的信息不确定性减少的程度
  - $g(D, A) = H(D) - H(D | A)$，D是训练数据集，A是特征
  - 计算：
    - 数据：
      - 训练数据集$D$的样本个数为$|D|$；
      - 属于类$C_k$的样本个数为$|C_k|$；
      - 根据特征$A$划分的样本集合$D_1,…,D_n$的样本个数$|D_1|,…,|D_n|$
      - 子集$|D_i|$中属于类$C_k$的样本集合$D_{ik}$的样本个数$|D_{ik}|$
    - $H(D) = -\sum\limits^K_{k=1}\cfrac{|C_k|}{|D|}\log_2\cfrac{|C_k|}{|D|}$
    - $H(D | A) = \sum\limits^n_{i=1}\cfrac{|D_i|}{|D|}\log_2H(D_i)=-\sum\limits^n_{i=1}\cfrac{|D_i|}{|D|}\sum\limits^K_{k=1}\cfrac{|D_{ik}|}{|D_i|}\log_2\cfrac{|D_{ik}|}{|D_i|}$
    - $g(D, A) = H(D) - H(D | A)$
4. 信息增益比
  - 信息增益值的大小是相对于训练数据集而言的，没有绝对意义
  - 训练数据集经验熵偏大时，信息增益值也偏大，反之偏小
  - 使用信息增益比对其进行矫正：
    - $g_R(D, A) = \cfrac{g(D,A)}{H(D)}$
决策树生成
1. ID3算法
  - 若D中所有实例属于同一类，则为单结点树
  - 若特征为 $\empty$ ，则为单结点数
  - 否则，计算各特征对D的信息增益，选择信息增益最大的特征$A_g$
    - 若$A_g < \epsilon$（阈值），则为单结点树
    - 否则，依据$A_g$的特征划分D，构建子结点
      - 对各子结点以$A-{A_g}$为特征集继续操作
2. C4.5算法
  - 与ID3类似，采用的比较方式是信息增益比
决策树剪枝
- 从已生成的树上裁掉一些子树或叶结点，简化分类树模型
- 算法：
  - 数据：
    - 树T的叶结点数为|T|
    - 叶结点t有$N_t$个样本点，其中k类样本点有$N_{tk}$个
  - 叶结点的经验熵为：
    - $H_t(T)=-\sum\limits_{k}\cfrac{N_{tk}}{N_t}\log_2\cfrac{N_{tk}}{N_t}$
  - 决策树学习的损失函数为：
    - $\begin{aligned}C_\alpha(T) = & \sum\limits_{t=1} ^{|T|}N_tH_t(T)+\alpha|T| \\ = & -\sum\limits_{t=1}^{|T|}\sum\limits_{k}N_{tk}\log_2\cfrac{N_{tk}}{N_t}+\alpha|T| \\ = & C(T)+\alpha|T| \end{aligned}$
  - 依据损失函数，从树$T_B$的叶结点回缩为树$T_A$
  - 如果$C_\alpha(T_A) \le C_\alpha(T_B)$，则进行剪枝（保留为$T_A$）
  - 直到得到损失函数最小的树为止

CART（分类与回归树）算法

是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法；
假设决策树是二叉树——左“是”右“否”。

回归树生成（最小二乘回归树生成算法）
- 假设已将输入空间划分为M个单元$R_1, R_2, …, R_M$，且每个单元$R_m$有一个固定的输出值$c_m$
- 回归树模型可表示为： $f(x) = \sum\limits_{m=1}^Mc_mI(x \in R_m)$
- 用平方误差表示回归树对训练数据的预测误差：$\sum\limits_{x_i \in R}(y_i - f(x_i))^2$
- $c_m$的最优值$\hat{c_m}$是单元$R_m$上所有输入实例$x_i$对应的输出$y_i$的均值
  - $\hat{c_m} = ave(y_i | x_i \in R_m)$
- 划分方法：
  - 选择第j个变量$x^{(j)}$和其取值s，定义两个区域
    - $R_1(j, s) = {x | x^{(j)} \le s}$
    - $R_2(j, s) = {x | x^{(j)} > s}$
  - 寻找最优切分变量j和最优切分点s：
    - $\min\limits_{j,s}\left[ \min\limits_{c_1} \sum\limits_{x_i \in R_1(j, s)}(y_i - c_1)^2 + \min\limits_{c_2} \sum\limits_{x_i \in R_2(j, s)}(y_i - c_2)^2 \right]$
      - 固定j，得到当前最优s:
        
        $\hat{c_1} = ave(y_i | x_i \in R_1(j, s))$
        
        $\hat{c_2} = ave(y_i | x_i \in R_2(j, s))$
      - 遍历所有变量，计算损失函数，得到最优切分变量j
  - 得到后对划分的两个子区域继续重复上述过程，直到满足停止条件为止
分类树生成
- K个类，概率为$p_K$，概率分布的基尼指数：
  - $Gini(p)=\sum\limits^K_{k=1}p_k(1-p_k)=1-\sum\limits^K_{k=1}p_k^2$
  - $Gini(p)=1-\sum\limits^K_{k=1}\left(\cfrac{|C_k|}{|D|}\right)^2$
- 如果D根据A 是否取某一值a被分割成D1和D2两部分，则：
  - $Gini(D, A)=\cfrac{|D_1|}{|D|}Gini(D_1) + \cfrac{|D_2|}{|D|}Gini(D_2)$
  - Gini指数表示集合D经A分类后的不确定性，数值越大说明越不确定
- 划分方法：
  - 用每个特征A的每个可能取值对 D 分类成两部分，衡量Gini(D, A)
  - 选择Gini指数最小时对应的A的取值即为切分点a
  - 重复上述过程，直到满足停止条件
CART剪枝
- 进行决策树剪枝，从原树$T_0$不断剪枝得到子树序列${T_0, T_1, …, T_n}$
  - 得到序列的方法：
    - 将$C(T)+\alpha|T|$的$\alpha$从小增大:$0 = \alpha_0 < \alpha_1, < \cdots < \alpha_n < + \infty$
    - 得到一系列区间$a = [\alpha_i, \alpha_{i+1})$
    - 进而得到子树序列
- 交叉验证法对子树序列进行测试，选择最优子树