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

决策树的生产，基本方法有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}$ 倍