《统计学习方法》极简笔记P5：决策树公式推导

2019-08-19 本文已影响0人统计学家

决策树学习

通过训练数据集 $T=\{(x_1,y_1),(x_2,y_2),(x_N,y_N)...,(x_1,y_1)\}$
$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T$ 为输入实例
$y_i\in\{1,2,...,K\}$ 为类标记
学习目标：对实例进行正确分类

特征选择

熵
$H(X)=-\sum_{i=1}^{n}p_ilogp_i$
条件熵
$H(Y|X)=-\sum_{i=1}^{n}p_iH(Y|X=x_i)$
信息增益的算法
输入：特征A，训练集D
输出：特征A对训练集D的信息增益 $g(D,A)$
(1)计算训练集D的经验熵
$H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$
(2)计算特征A对训练集D的经验条件熵
$H(D,A)=\sum_{k=1}^{K}\frac{|D_i|}{|D|}H(D_i)=-\sum_{k=1}^{K}\frac{|D_i|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}$
(3)计算信息增益
$g(D,A)=H(D)-H(D|A)$
信息增益比的算法
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$
其中 $H(D)=-\sum_{k=1}^{n}\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$

决策树剪枝

树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有 $N_t$ 个样本点，其中k类的样本点有 $N_{tk}$ 个， $H_t(T)$ 为叶结点t上的经验熵，则决策树学习的损失函数
$C_a(T)=\sum_{t=1}^{|T|}N_tH_t(T)+a|T|$
其中 $H_t(T)=-\sum_{k}\frac{|N_{tk}|}{|N_t|}log\frac{|N_{tk}|}{|N_t|}$
则 $C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}$
则 $C_a=C(T)+a|T|$
树的剪枝算法
输入：生成的决策树T，参数α
输出：修剪后的子树 $T_\alpha$
(1)计算每个结点经验熵
(2)递归地从树的叶结点向上回溯，若：
$C_\alpha(T_A)\leq{C_\alpha}(T_B )$ 则剪枝，其中 $T_A$ 为剪枝后, $T_B$ 为剪枝前
(3)返回(2)，直至得到损失函数最小的子树 $T_\alpha$

CART算法--回归树

对输入空间划分为M个单元 $R_1,R_2,...,R_M$ ,每个划分上有固定输出 $C_m$ ,则回归树模型表示为
$f(x)=\sum_{m=1}^{M}c_m{I}(x\in{R_m})$
预测误差： $\sum_{x\in{R_m}}(y_i-f(x_i))^2$
划分单元 $R_m$ 上的 $c_m$ 最优值 $\hat{c}_m=avg(y_i|x_i\in{R_m})$
输入空间的划分采用启发式方法
选择第j个变量 $x^{(j)}$ 和它的取值s作为切分变量和切分点，定义两个区域：
$R_1(j,s)=\{x|x^{(j)}\leq{s}\}$ , $R_2(j,s)=\{x|x^{(j)}>{s}\}$
然后寻找最优切分变量j和最优切分点s，求解：
$\mathop{min}\limits_{j,s}[\mathop{min}\limits_{c_1}\sum_{x_i\in{R_1(j,s)}}(y_i-c_1)^2+\mathop{min}\limits_{c_2}\sum_{x_i\in{R_2(j,s)}}(y_i-c_2)^2]$
对固定输入变量j，找到最优切分点s
$\hat{c}_1=avg(y_i|x_i\in{R_1(j,s)})$
$\hat{c}_2=avg(y_i|x_i\in{R_2(j,s)})$
最小二乘回归树生成算法
输入：训练集D
输出：回归树f(x)
(1)选择最优切分变量j和切分点s，求解
$\mathop{min}\limits_{j,s}[\mathop{min}\limits_{c_1}\sum_{x_i\in{R_1(j,s)}}(y_i-c_1)^2+\mathop{min}\limits_{c_2}\sum_{x_i\in{R_2(j,s)}}(y_i-c_2)^2]$
遍历j，对固定j扫描切分点s，找出使上式达到最小的(j,s)组合
(2)选择(j,s)划分区域并决定相应输出值：
$R_1(j,s)=\{x|x^{(j)}\leq{s}\}$ , $R_2(j,s)=\{x|x^{(j)}>{s}\}$

$\hat{c_m}=\frac{1}{N_m}\sum_{x_i\in{R_1(j,s)}}y_i,x\in{R_m},m=1,2$
(3)对两个子区域循环(1),(2),直至满足停止条件
(4)将输入空间划分为M个单元 $R_1,R_2,...,R_M$ ,生成决策树：
$f(x)=\sum_{m=1}^{M}\hat{c}_m{I}(x\in{R_m})$

CART算法--分类树

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点
基尼指数
K个类，属于第k类的概率 $p_k$ ,则
$Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2$
样本集D的基尼指数
$Gini(D)=1-\sum_{k=1}^{K}({\frac{|C_k|}{|D|})}^2$
样本D根据特征A是否取值a被划分为 $D_1$ , $D_2$
$D_1=\{(x,y)\in{D}|A(x)=a\},D_2=1-D_1$

$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$
CART生产算法
输入:训练数据集D，停止计算的条件;
输出:CART决策树.
(1)训练数据集D，计算现有特征对该数据集的基尼指数.此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割成D1和D2两部分，根据 $Gini(D,A)$ 计算A=a时的基尼指数;
(2)在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点.依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去；
(3)对两个子结点递归地调用(1)(2)，直至满足停止条件.
(4)生成CART决策树.

CART剪枝算法

输入:CART算法生成的决策树 $T_0$ ;
输出:最优决策树 $T_\alpha$ .
(1)设 $k=0,T=T_0$ .
(2)设 $a=+\infty$
(3)自下而上地对各内部结点t计算 $C(T_t) ,|T_t|$ 以及
$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$ , $a=min(a,g(t))$
这里 $T_t$ 表示以t为根结点的子树., $C(T_t)$ 是对训练数据的预测误差， $|T_t|$ 引是 $T_t$ 的叶结点个数；
(4)对 $g(t)=a$ 的内部结点t进行剪枝，并对叶结点t以多数表决法决定其类，得到树T；
(5)设 $k=k+1,a_k=a,T_k=T$ ；
(6)如果T不是由根结点单独构成的树。则回到步骤(4)；
(7)采用交叉验证法在子树序列 $T_0,T_1,...,T_n$ 中选取最优子树 $T_a$