决策树基本要点及方法对比

作者: 有机会一起种地OT | 来源:发表于2020-04-20 16:38 被阅读0次

决策树基本要点及方法对比
第一章：决策树：从原理到算法实现
机器学习算法——决策树1（基础）
决策树与随机森林
机器学习实战教程（二）：决策树基础篇
决策树
分类方法二之决策树
决策树学习
产品经理数据分析
数据分析中常用分析思路对比分析解析（一）

决策树的生产，基本方法有ID3、C4.5、CART。基于基础决策树学习器，可进一步构建提升树。

ID3

ID3算法的核心在于在决策树各个结点上应用信息增益进行特征选择。从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的分裂特征，由该特征的不同取值分割成子结点。并不断递归地在各结点上进行，直到所有特征的信息增益均小于给定阈值，或没有特征可用为止。
ID3相当于用极大似然法进行概率模型的选择。

训练集 $D$ （存在 $K$ 类），特征集 $A$ （非空），阈值 $e$

从根结点开始，计算所有特征 $A_i\in A$ 对D的信息增益 $g(D,A)=H(D)-H(D|A)$ ，其中
$D$ 的经验熵 $H(D)=-\sum_{k=1}^K\frac{|D_k|}{|D|}\log_2\frac{|D_k|}{|D|}$
经验条件熵 $H(D|A_i)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)$
选择信息增益最大的特征 $A_g$
如果 $A_g$ 的信息增益小于阈值 $e$ ，那么不进行结点分割。取结点数据中实例最多的类为结点类标记。
否则，对 $A_g$ 的每个取值，将 $D$ 分割为若干个结点 $D_i$ ，将 $D_i$ 中实例最多的类作为子结点的类标记。
对第 $i$ 个子结点，以 $D_i$ 为训练集， $A-{A_g}$ 为特征集，递归地执行上述操作。

C4.5

对于C4.5算法，其使用信息增益比 $g_r(D,A)=\frac{g(D,A)}{H_A(D)}$ 来选择特征。其中 $H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2 \frac{|D_i|}{|D|}$ 为数据集 $D$ 关于特征 $A$ 的值的熵。

CART

CART算法既可以用于分类也可以用于回归。其假设决策树是二叉树，并递归地二分每个特征。每次遍历所有特征以及特征上的值，选择最小化目标准则的特征 $A_i$ 与分割点 $a$ 。
$\min_{A_i,a}[L(y,x|_{x\in(x^{(A_i)}\leq a)})+L(y,x|_{x\in(x^{(A_i)}>a)})]$
对于回归树用最小化平方误差的准则，对于分类树则采取最小化基尼系数的准则。

提升树

提升树则是以分类树和回归树为基本学习器的提升方法。最基本的提升树模型可以表示为决策树的加法模型。
$f_M(x)=\sum_{m=1}^M T_m(x)$
其中 $T_m(x|\Theta_m)$ 表示各个决策树。这里用 $\Theta_m$ 表示第 $m$ 棵树 $f_m(x)$ 的权重。对于分类和回归问题，不同之处在于经验误差函数 $L$ （平方误差、指数损失函数等）。
其基本步骤为：

构建初始树 $f_0(x)=0$ 。
增加第 $m$ 棵树 $T_m(x|\Theta_m)$ ，最小化经验风险 $L$
$\hat{\Theta}_m=\arg \min_{\Theta_m}\sum_{i-1}^N L(y_i,f_{m-1}+T_m(x_i|\Theta_m))$
新的提升树 $f_m=f_{m-1}+T_m(x_i|\hat{\Theta}_m)$ 。

这里因为训练集等权重，故各树也是等权重。一般的AdaBoost算法还要考虑样本数据的权重，计算各子学习器的权重。

例如，对于采用平方误差的回归提升树，最小化经验风险
$L(y,f_{m-1}+T_m(x|\Theta_m))=[y-f_{m-1}(x)-T_m(x|\Theta_m)]^2$

令 $r$ 表示之前的数与目标输出之间的残差 $r=y-f_{m-1}(x)$ 。这意味着新树 $T_m(x)$ 用来拟合残差。

对于无法直接求解来最小化经验误差的复杂误差函数，可采用梯度提升进行优化。残差用一阶导数来反映
$r_i=-\left\{ \frac{\partial{L(y_i,f_{m-1}(x_i))}}{\partial{f_{m-1}(x_i)}} \right\}$
这种计算方式就是GBDT算法。

XGBoost

XGBoost所使用的基础学习器是CART模型。相比GBDT只是用一阶导数，XGBoost对损失函数的改写增加了二阶泰勒展开。
残差就变为
$r_i=-\left\{ \frac{\partial{L(y_i,f_{m-1}(x_i))}}{\partial{f_{m-1}(x_i)}}+\frac{\partial^2{L(y_i,f_{m-1}(x_i))}}{\partial{f_{m-1}(x_i)}} \right\}$

此外完整的XGBoost方法还在损失函数中直接集成了正则项。（实际上上述所有方法都可以在损失函数后加入表示树结构复杂度的正则项，用于剪枝）

其定义的正则化项为
$\Omega(f)=\gamma |T|+\frac12 \lambda \|\omega\|^2$
其中 $|T|$ 表示树 $T$ 叶子结点个数， $\omega$ 表示叶子结点的输出值向量， $\gamma$ 和 $\lambda$ 是相应的超参数。

LightGBM

XGBoost基于CART模型，计算过程中会遍历特征及特征值，这需要对特征值进行预排序。逐个数据样本来计算划分收益，这样的算法能够精确的找到最佳划分值，但是代价比较大同时也没有较好的推广性。

而LightGBM在基础学习器的构建上，是基于直方图的决策树算法。其将这些特征上精确的连续值划分到一系列离散的桶中，简化了数据表示，特减少了内存的使用。同时直方图也带来了一定的正则化效果，提高了可推广性。

基于直方图，LightBGM在构建树的过程上采用按叶生长 leaf-wise 的方法，每次选择能最大化分裂增益的叶子结点，将其分裂为两个叶子结点。这不同于上述算法的按层生长 level-wise 方法。

LightBGM采用GOSS（Gradient-based One-Side Sampling 单边梯度采样）方法对数据采样，排除大部分小梯度的样本，尽量用梯度大的实例。具体到算法上：

指定大梯度数据采样率 $\alpha$ ，小梯度数据采样率 $\beta$
对当前模型下的数据梯度进行排序，排序后的数据集记为 $I$
采样全部 $\alpha|I|$ 个大梯度数据 $topSet = I[1:\alpha|I|]$
抽取 $\beta |I|$ 个其余小梯度数据 $randSet = randomPick(I[\alpha|I|:|I|],\beta |I|)$
$topSet$ 和 $randSet$ 共同构成下一棵树的训练集
$randSet$ 中数据的权重放大 $\frac{1-\alpha}{\beta}$ 倍

这样做主要还是为了提升学习速度，用小部分小梯度数据参与计算，来代替原本所有的小梯度数据（权重放大 $\frac{1-\alpha}{\beta}$ ）。

LightBGM还采取EFB（Exclusive Feature Bundling 独立特征绑定）的方法来降低维度。将相互独立的特征合并为一个，减少了特征维度的同时又不丢失信息。对于不完全互斥的特征，采用冲突比率的指标衡量这种不互斥程度，当这个值较小时，也可以将对应的特征绑定在一起。

LightGBM是结合使用GOSS和EFB的GBDT算法。

决策树基本要点及方法对比
决策树的生产，基本方法有ID3、C4.5、CART。基于基础决策树学习器，可进一步构建提升树。 ID3 ID3算法...
第一章：决策树：从原理到算法实现
前言：决策树（Decision Tree）是一种基本的分类与回归方法，本文主要讨论分类决策树。决策树模型呈树形结构...
机器学习算法——决策树1（基础）
决策树导读决策树Decision Tree是一种基本的分类和回归方法。决策树模型呈现树形结构，在分类问题上，主...
决策树与随机森林
决策树（decision tree）是一种基本的分类与回归方法，本文主要讨论用于分类的决策树。决策树模型呈树形结构...
机器学习实战教程（二）：决策树基础篇
一、决策树决策树是什么？决策树(decision tree)是一种基本的分类与回归方法。举个通俗易懂的例子，如下...
决策树
1.基本概念 1.决策树是一种基本的分类与回归方法。这里主要讨论决策树用于分类。 2.决策树模型是描述对样本进行分...
分类方法二之决策树
决策树决策树是什么？决策树(decision tree)是一种基本的分类与回归方法。举个通俗易懂的例子，如下图所...
决策树学习
下文介绍学习决策树的过程，我们通过例子来更好地理解决策树。决策树是什么，是一种基本的分类与回归的方法。分类决策树...
产品经理数据分析
基本分析方法对比横向对比纵向对比漏斗分析
数据分析中常用分析思路对比分析解析（一）
对比是识别事物的基本方法对比——横向、纵向及多维度对比比值比率背后的逻辑指标的逻辑与管理指标对标的层次和维度标杆管...