决策树——算法

ID3-信息增益
C4.5-信息增益比
CART：基尼指数

1. 决策树的剪枝

决策树是递归产生，单纯追求正确分类，会产生过拟合的现象，解决方法是：剪枝；
剪枝：在决策树学习中将已生成的树进行简化的过程：裁剪部分叶子节点，或子树，将其根节点或说父节点作为新的叶节点

* 决策树的评价（cart树）

剪枝通过极小化决策树整体的损失函数或者代价函数来实现；
设：树T的叶节点个数是|T|,t是树T的叶节点，该叶节点有 $N_t$ 个样本点，其中k类样本点有 $N_{tk}$ 个， $k=1,2,...,k$ ； $H_t(T)$ 为叶节点t上的经验熵， $\alpha\geq 0$ 是参数，则决策树的损失函数是： $C_{\alpha}(T)=\sum\limits_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$

其中经验熵：

$H_t(T)=-\sum\limits_{k}\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$

令右端第1项：

$C(T)=\sum\limits_{t=1}^{|T|}N_tH_t(T)$

$C(T)$ 是评价函数：对叶节点的熵的加和

$C_{\alpha}(T)=C(T)+\alpha|T|$

* 解释

C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度
|T|表示复杂度
$\alpha$ 是控制两者的参数： $\alpha$ 较大，选择较简单的模型；较小选择复杂的模型；等于0，表示不考虑模型的复杂度，只考虑拟合程度

* 意义

决策树剪枝，通过优化损失函数，还考虑了减少模型的复杂度；
决策树的生成是局部学习模型，而决策树减枝学习是整体的模型
$C_{\alpha}(T)=C(T)+\alpha|T|$ 定义的损失函数的极小化等价于正则化的极大似然估计
利用损失函数最小化原则进行剪枝就是利用正则化极大似然函数选择模型

* 碎碎念

C4.5:后剪枝算法，使用悲观剪枝
CART：后剪枝算法，使用最小成本复杂度剪枝

* 剪枝：预剪枝和后剪枝

前剪枝：在决策树生成过程中
后剪枝：首先生成树，然后剪枝

2. 决策树剪枝的算法

总体思路：对于完全树 $T_0$ ,减去部分节点得到 $T_1$ ,再次减去部分节点得到 $T_2$ ...,直到仅剩余根的树 $T_k$
1.0 输入：生成算法产生的整个树： $T$ , 参数 $\alpha$
2.0 输出：修建后的子树： $T_{\alpha}$
(1) 计算每个节点的经验熵
(2) 递归的从树的叶节点向上回缩
(3) 设一组叶节点回缩到其父节点之前与之后的整体树分别是 $T_B$ 和 $T_A$ ,对应的损失函数是： $C_{\alpha}(T_B) 和 C_{\alpha}(T_A)$ :

如果： $C_{\alpha}(T_A)\leq C_{\alpha}(T_B)$

则：进行剪枝，即父节点变为新的叶节点

（4）返回(2)，只到不能继续为止，得到损失函数最小的子树 $T_{\alpha}$

上述算法，可以使用动态规划

* 损失函数的解释

比较：

$C_{\alpha}(T)=\sum\limits_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$

$L(w,d)=\frac{1}{N}\sum\limits_{i=1}^N(y_i-f(x_i))^2+r(d)$

决策树损失函数的衡量标准是确定性，确定性越强，说明拟合越，损失就会越小
$N_t$ 是节点的样本个数，可以看为权重
$H_t(T)$ 是熵
表示叶子节点的加权和

3. CART树

特征选择
树的生成
剪枝

* CART基础

二叉树
训练数据集生成决策树，生成的决策树尽量的大
决策树剪枝：用验证数据集对已经生成的树剪枝，并选择最优树

3.1 CART的生成

递归的构建二叉树的决策过程
回归树用平方误差最小化准则，选择特征，生成决策树
分类树用基尼指数最小化准则，选择特征，生成决策树

3.1.1 CART回归树

回归树：对应输入空间（特征空间）的一个划分以及在划分的单元上的输出值。假设已经将输入空间划分为M个单元 $R_1,...,R_M$ ，且在每个单元 $R_M$ 上有一个固定输出值 $c_m$ ，于是回归树：

$f(x)=\sum\limits_{m=1}^Mc_mI(x\in R_m)$

使用平方最小准则来求解每个单元上的最优输出值，
单元 $R_m$ 上的 $c_m$ 的最优值 $\hat{c}_m$ 是 $R_m$ 上的所有输入实例 $x_i$ 对应输出 $y_i$ 的均值

$\hat{c}_m=ave(y_i|x_i\in R_m)$

输入空间的划分：
1. 选择第j个变量 $x^{(j)}$ 和它的取值s，作为切分变量和切分点：并定义两个区域：

$R_1(j,s)=\{x|x^{(j)}\leq s\}$

$R_2(j,s)=\{x|x^{(j)}> s\}$

然后寻找最优切分变量j和切分点s

$\min\limits_{j,s}[\min\limits_{c_1}\sum\limits_{x_1\in R_1(j,s)}(y_1-c_1)+\min\limits_{c_2}\sum\limits_{x_2\in R_2(j,s)}(y_i-c_2)^2]$

其中：

$\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,s),将空间划分为两个区域，接着对于区域重复上述的划分，只到满足停止条件，生成回归树；

* 算法

3.2 cart分类树

分类树使用基尼指数选择最优特征，同时决定该特征的最优二值切点

* 算法符号

概率分布的基尼指数：设有K个类，样本点属于第K类的概率为 $p_k$ :

$Gini(p)=\sum\limits_{k=1}^Kp_k(1-p_k)=1-\sum\limits_{k=1}^Kp_k^2$

二分类，若样本点属于第1个的概率是p，则概率分布的基尼指数：

$Gini(p)=2p(1-p)$

给定样本集D，则基尼指数：

$Gini(D)=1-\sum\limits_{k=1}^K\displaystyle{(\frac{|C_k|}{|D|})^2}$

$C_k$ 是D属于第k个样本子集，K是类的个数

若样本D根据特征A是否取某一个值a，被分割成 $D_1和D_2$ :

$D_1=\{(x,y)\in D|A(x)=a\}$

$D_2=D-D_1$

在特征A下的，集合D的基尼指数：

$Gini(D,A)=\frac{|D_1|}{D}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

$Gini(D)$ :表示集合D的不确定性
$Gini(D,A)$ : 表示A=a的分割后集合D的不确定性
基尼指数大，不确定性大

* Cart分类树算法

3.3 剪枝

首先从生成算法产生的决策树 $T_0$ 底端开始不断的剪枝，只到 $T_0$ 的根节点，形成子树 $\{T_0,...,T_n\}$
交叉验证法在独立的验证数据集对子树序列测试，选择最优子树

* 算法解释

设损失函数 $C_{\alpha}=C(T)+\alpha|T|$
1. T是任意子树，
2. C(T)为对训练数据的预测误差（例如基尼指数）
3. |T|为子树的叶节点个数
4. $\alpha \geq 0$ 是参数：衡量数据的拟合程度和模型的复杂度； $\alpha = 0$ : 整体树最优； $\alpha \rightarrow \infty$ :根节点组成的单节点最优
5. $C_{\alpha}(T)$ 是参数为 $\alpha$ 时的子树T的整体损失
设 $T_0$ 的任意内部节点t，以t为单结点的树的损失函数：

$C_{\alpha}(t)=C(t)+\alpha$

以t为跟结点的子树 $T_t$ 的损失函数：

$C_{\alpha}(T_t)=C(T_t)+\alpha|T_t|$

$\alpha=0$ ，及 $\alpha$ 较小时：

$C_{\alpha}(T_t) < C_{\alpha}(t)$

当 $\alpha$ 增大，在某 $\alpha$ 处

$C_{\alpha}(T_t) = C_{\alpha}(t)$

令 $\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$ : $T_t$ 和t有相同的损失函数值，而t的节点少，因此t比 $T_t$ 更可取，对 $T_t$ 剪枝
对 $T_0$ 中每一个内部结点t,计算：

$t=\frac{C(t)-C(T_t)}{|T_t|-1}$

表示：剪枝后整体损失函数减少的程度；在 $T_0$ 中减去g(t)最小的树 $T_t$ ,得到的子树是 $T_1$ ,同时g(t)设为 $\alpha_1$ ； $T_1$ 是区间 $[\alpha_1,\alpha_2)$ 的最优树

重复，到根节点，在过程中不断增加 $\alpha$ 的值，产生新的区间

决策树-算法