决策树 - 简书

基本流程

核心思想：通过构建一个树状模型来对新样本进行预测
主要结构：一棵决策树包含一个根节点、若干内部节点与叶结点。叶结点对应于决策结果，其他节点对应于一个测试属性。每个样本根据测试属性被划分到子节点中，根节点包含样本全集。

image-20200513074241388.png
CHAID

Chi-square automatic interaction detection (CHAID) is a decision tree technique, based on adjusted significance testing (Bonferroni testing). The technique was developed in South Africa and was published in 1980 by Gordon V. Kass, who had completed a PhD thesis on this topic. CHAID can be used for prediction (in a similar fashion to regression analysis, this version of CHAID being originally known as XAID) as well as classification, and for detection of interaction between variables. CHAID is based on a formal extension of the United States' AID (Automatic Interaction Detection) and THAID (THeta Automatic Interaction Detection) procedures of the 1960s and 1970s, which in turn were extensions of earlier research, including that performed in the UK in the 1950s.

CHAID（2*2）

		目标变量	Y
		Positive	Negtive
	Left	$n_{11}$	$n_{12}$	$n_{1.}$
X	Right	$n_{21}$	$n_{22}$	$n_{2.}$
		$n_{.1}$	$n_{.2}$	$n_{..}$

在垂直X的方向上寻找一个分界线使得Y在分割线左右的分布差异最大，等价于最大化 $\chi^2$ 统计量
$\chi^2 = \Sigma_{i=1}^2\Sigma_{j=1}^2\frac{(n_{ij}-e_{ij})^2}{e_{ij}} \\ e_{ij} = \frac{n_{i.}n_{.j}}{n_{..}}\\ \chi^2 = \frac{(n_{11}n_{22} - n_{12}n_{21})^2*n_{..}}{n_{.1}n_{.2}n_{1.}n_{2.}}$

image-20200513075716506.png

image-20200513075720926.png

决策树学习算法

image-20200513075900540.png
- 递归返回条件：
  1. 当前结点包含的样本全属于同一个类别，无法划分
  2. 当前属性集为空或所有样本在所有属性上取值相同，无法划分
    
    将当前结点标记为叶结点，并将其类别设定为大多数样本的类别，利用了当前样本的后验分布
  3. 当前结点包含的样本集合为空
    
    将当前结点标记为叶结点，并将其类别设定为父节点大多数样本的类别，利用了当前样本的先验分布

信息熵

假定当前样本集合 $D$ 中第 $k$ 类样本（分类变量）所占比例为 $p_k(k = 1,2,...,|y|)$ ，则其信息熵定义为
$Ent(D) = -\Sigma_{k=1}^{|y|}p_klog_2p_k$

假定离散属性 $a$ 有 $V$ 个可能的取值 $\{a^1, a^2,...,a^V\}$ ,使用 $a$ 来对样本集 $D$ 进行划分，会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性上取值为 $a_v$ 的样本，记为 $D_v$ 则可计算出 $D_v$ 的信息熵，再考虑不同分支结点包含的样本数的不同，给分支结点赋予权重 $\frac{|D_v|}{|D|}$ ,计算出如下的信息增益：
$Gain(D,a) = Ent(D) - \Sigma_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$
根据信息增益选择对应的属性 $a^*$ 作为分支属性
$a^* = \arg max_{a \in A}Gain(D,a)$
ID3（迭代二分器）决策树学习法以信息增益为准则选择划分属性

熵和Bit

一个等概率的二选一事件具有1Bit的不确定性,信息熵的单位是Bit
$H(P) = -\frac{1}{2}log_2(\frac{1}{2}) + -\frac{1}{2}log_2(\frac{1}{2}) =1$
- 离散型随机变量与连续型随机变量关于熵的定义
  1. 离散型随机变量 $X$ 只取有限个数值 $a_1,...,a_k$
    $H(x) = -E(logP(X = a_k)) = -\Sigma_{k=1}^KP(X = a_k)logP(X = a_k)$
  2. 连续随机向量有类似定义，更一般地，对于连续随机向量X，如果有联合密度分布，则
    $H(X) = -E(logP(x_1,...,x_n)) = -\int ...\int P(x_1,...,x_n)logP(x_1,...,x_n)dx_1...dx_n$
熵的性质

image-20200513232726681.png

image-20200513233405545.png
条件熵
$H(X|Y= y) = -\int p(x|y)\log p(x|y)dx \\ H(X|Y) = -E_{y}\int p(x|y)\log p(x|y)dx = -\int \int p(x,y)\log p(x|y)dxdy$
条件熵的交换性质
$H(X) = -\int P(x)\log P(x)dx = -\int \int P(x,y) \log P(x)dxdy \\ H(X|Y) = -\int \int p(x,y)\log p(x|y)dxdy \\ I(X,Y) = -\int \int p(x,y)\log \frac{p(x,y)}{p(x)p(y)}dxdy \\ H(X) - H(X|Y) = H(Y) - H(Y|X) = I(X,Y)$
联合熵
对于一对随机变量(X,Y),具有联合分布P(x,y)可以定义联合熵
$H(X,Y) = \Sigma_x\Sigma_yP(x,y)[-\log P(x,y)]\\$
对于两个以上的变量 $X_1,...,X_n$ ，该式有一般形式
$H(X_1,...,X_n) = -\Sigma_{x_1}...\Sigma_{x_n}P(X_1,...,X_n)\log_2[P(X_1,...,X_n)]$
存在不等式
$\max [H(X),H(Y)] \leq H(X,Y) \leq H(X)+H(Y)$
决策树划分依据
1. 信息增益（ID3决策树）[最大]
  $Ent(D) = -\Sigma_{k=1}^{|y|}p_klog_2p_k \\ Gain(D,a) = Ent(D) - \Sigma_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$
2. 增益率（C4.5决策树）[最大]
  $Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}\\ IV(a) = -\Sigma_{v = 1}^V\frac{|D^v|}{|D|}\log_2 \frac{|D^v|}{|D|}$
3. 基尼指数（CART决策树）[最小]
  $Gini(D) = \Sigma_{k=1}^{|y|}\Sigma_{k' \not =k}p_{k}p_{k'} = 1 - \Sigma_{k=1}^{|y|}p_{k}^2 \\ Gini\_index(D,a) = \Sigma_{v=1}^{V}\frac{|D^v|}{|D|}Gini(D^v)$
剪枝
- 预剪枝：
  
  对每个结点在划分前先进行估计,若该结点的划分不能带来决策树泛化性能提升,则停止划分.
  
  预剪枝基于"贪心"本质,所以有欠拟合的风险.
- 后剪枝
  
  先生成一棵完整的决策树,然后自底向上对非叶结点考察,若该结点替换为叶结点能带来决策树泛化性能提升,则将子树替换为叶结点.
  
  缺点是时间开销大.
  
  若后剪枝过程中减去一个结点和保留结点对泛化性能无影响，仍应该减去（奥卡姆剃刀原则）

连续值处理

选择依据
$T_a = \{ \frac{a^i + a^{i+1}}{2}|1 \leq i \leq n-1 \}\\ Gain(D,a) = \max_{t \in T_a} [Ent(D) - \Sigma_{\lambda \in \{-,+\}}\frac{|D_{t}^{\lambda}|}{|D|}Ent(D_{t}^{\lambda})]$
- 不同临界值的同名连续值变量可在决策树的一个分支上多次出现（对比类别变量）
缺失值处理
- 划分属性选择
  
  给定训练集 $D$ 和属性 $a$ ，令 $\tilde D$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集。
  
  假定属性 $a$ 有 $V$ 个可取值 $\{a^1,a^2,...,a^V\}$ ，令 $\tilde D^v$ 表示 $\tilde D$ 中在属性 $a$ 上取值为 $a^v$ 的样本子集， $\tilde D_k$ 表示 $\tilde D$ 中属于第 $k$ 类 $(k = 1,2,...,|y|)$ 的样本子集
  
  假定为每个样本 $x$ 赋予一个权重 $w_x$ ,并定义
$\rho = \frac{\Sigma_{x \in \tilde D} w_x}{\Sigma_{x \in D}w_x} \\ \tilde p_k = \frac{\Sigma_{x \in \tilde D_k} w_x}{\Sigma_{x \in \tilde D}w_x} \\ \tilde r_v = \frac{\Sigma_{x \in \tilde D^v} w_x}{\Sigma_{x \in \tilde D}w_x}$

基于此，我们将信息增益的计算式推广为
$\begin{array}{ll} { Gain(D,a)\\ = \rho * Gain(\tilde D,a) \\ = \rho * (Ent(\tilde D) - \Sigma_{v=1}^V\tilde r_vEnt(\tilde D^v)) \\ } \end{array}$
- 样本划分
  1. 若样本在划分属性上取值已知，则将样本划入与其取值对应的子结点，且样本权值在子结点中保持不变
  2. 若样本在划分属性上取值未知，则将样本同时划入所有子结点，且样本权值在与属性值对应的子结点中调整为 $\tilde r_v * w_x$

多变量决策树

单变量决策树生产的分类边界平行于坐标轴，但存在不足：生成决策树的深度较大，这意味着更多次的循环与递归，计算开销过大

image-20200516113301301.png

多变量决策树使用倾斜的划分边界，在该类决策树中，非叶结点是一个形如 $\Sigma_{i=1}^dw_ia_i = t$ 的线性分类器，其中 $w_i$ 是属性 $a_i$ 的权重， $w_i$ 和 $t$ 可以在该结点所含的样本集和属性集上学得

image-20200516113835228.png

image-20200516113909362.png

CART回归树

image-20200516122203403.png

回归模型

数据由 $p$ 个输入值和一个返回值组成，即对于 $N$ 个观测值： $(x_i,y_i)$ 其中 $i = 1,2,...,N$ ， $x_i = (x_{i1},x_{i2},...,x_{ip})$

训练算法将决定在选择哪些分量作为划分变量以及其划分位置

假设我们最初有一个划分能将特征空间划分为 $M$ 个区域 $R_1,R_2,...,R_M$ ,根据每个区域内样例的返回值 $c_m$ 作为常量，得到如下回归模型：
$f(x) = \Sigma_{m=1}^Mc_mI(x\in R_m)$
如果将 $\Sigma(y_i - f(x_i))^2$ 作为确定 $c_m$ 得到标准，则：
$\hat c_m = ave(y_i|x_i \in R_m)$
之后采用贪婪算法，按照如下规则找到划分变量 $j$ 与划分位置 $s$
$min_{j,s}[min_{c_1}\Sigma_{x_i \in R_1(j,s)}(y_i - c_1)^2 + min_{c_2}\Sigma_{x_i \in R_2(j,s)}(y_i - c_2)^2] \\ R_1(j,s) = {X|X_j \leq s} \\ R_2(j,s) = {X|X_j \geq s} \\ \hat c_1 = ave(y_i|x_i \in R_1)\\ \hat c_2 = ave(y_i|x_i \in R_2)$
得到特征空间的一个划分
- 如何确定树的深度？（浅会导致欠拟合，深会导致过拟合）
  1. 树的大小是一个需要基于数据集特征进行调节训练得到的参数
  2. 仅仅根据结点数据的误差平方和是否超过某一阈值来进行判断是目光短浅的做法，因为下一层的结点可能会有更小的误差平方和
  因此采用先生成完整树再进行剪枝的方式找到最优树
  - cost-complexity pruning
    
    定义子树 $T \in T_0$
    
    给树的每一个结点编号，第 $m$ 个结点代表区域 $R_m$
    
    用 $|T|$ 表示树中的终端结点
    $N_m =|\{x_i \in R_m \}| \\ \hat c_m = \frac{1}{N_m}\Sigma_{x_i \in R_m}y_i \\ Q_m(T) = \frac{1}{N_m}\Sigma_{x_i \in R_m}(y_i - \hat c_m)^2$
    由此定义cost complexity criterion
    $C_{\alpha}(T) = \Sigma_{m=1}^{|T|}N_m Q_m(T) + \alpha|T|$
    对于给定的 $\alpha$ 找到使得 $C_{\alpha}(T)$ 最小的子树 $T_{\alpha}$
    
    weakest link pruning:
    
    连续地压缩这样的内部结点，有最小的 $\Sigma_m N_m Q_m(T)$ 直到产生单节点（根）树
    
    这会产生一个子树序列，一定包含使得 $C_{\alpha}(T)$ 最小的子树 $T_{\alpha}$

小结

树的主要问题是较高的方差，通常数据的一个微小变化将导致一系列不同的分裂，使得解释具有不稳定性

造成这种不稳定的主要原因是过程的分层本质：顶层分裂中的错误影响将被传播到下层的所有分裂
通过尝试使用较稳定的分裂准则，可以在某种程度上缓解这种影响，但无法消除这种固有的不稳定性
决策树只适用于预测变量无关的情形，缺乏光滑性
在各个阶段可以考虑对每个结点进行多路分裂来分成多个组，而不是把每个结点都分裂成两组。但多路分类会导致子树过快到达叶结点，降低树的深度。（多路分类可以由一系列的二叉分裂实现，所以在树的算法里都使用二叉分裂[类似对连续属性的处理]）

决策树的量化评估标准

预测的准确性：停止准则
模型的稳健性：剪枝
描述的精炼性：
- 选择拆分变量
- 拆分变量的次序
计算的复杂性：
- 拆分的数量
- 树的结构
处理的规模性：训练数据的大小

参考资料

机器学习周志华

信息论（3）——联合熵，条件熵，熵的性质 https://zhuanlan.zhihu.com/p/36385989

The Elements of Statistic Learning