GBDT | davidlau's blog

GBDT（Gradient Boosting Descision Tree）, 梯度提升决策树, 又名 MART（Multiple Additive Regression Tree）, 是由多颗回归决策树组成的 Boosting 算法, 常用于 CTR 预估. 本文介绍了决策树、Boosting 决策树、Gradient Boosting 决策树的算法原理和实现.

熵

给定一个离散有限随机变量 $X$ 的分布为 $P(X = x_i)=p_i$ , $i=1,2,...,n$ , 那么 $X$ 的熵定义为

$H(X) = \sum_{i} - p_{i}\log p_{i}$

熵越大, 随机变量的不确定性越大, 从定义可以验证

$0 \le H(X) \le \log n$

条件熵

条件熵 $H(Y|X)$ 描述了在已知第二个随机变量 $X$ 的值的前提下, 随机变量 $Y$ 的信息熵

$\begin{aligned} H(Y|X) &=\sum_{x\in \mathcal X}p(x)H(Y|X=x) \\ &=-\sum_{x\in \mathcal X} p(x) \sum_{y\in\mathcal Y} p(y|x) \log p(y|x) \\ &=-\sum_{x\in\mathcal X,y\in\mathcal Y} p(x,y) \log \frac{p(x,y)}{p(x)} \end{aligned}$

当且仅当 $Y$ 的值完全由 $X$ 确定时, $H(Y|X)=0$ . 相反, 当且仅当 $Y$ 和 $X$ 为独立随机变量时, $H(Y|X)=H(Y)$ .

由数据估算 (如极大似然估计) 得到时, 称为经验条件熵.

条件熵的链式法则为

$H(Y|X) = H(X,Y) - H(X)$

条件熵的贝叶斯规则表述, 可由链式法则推导出

$H(Y|X) = H(X|Y) - H(X) + H(Y)$

联合熵

假设两个随机变数 X 和 Y 确定的组合系统的联合熵为 $H(X,Y)$ , 即我们需要 $H(X,Y)$ bit 的信息来描述它的确切状态

$H(X,Y) = \sum p(x,y)\log p(x,y)$

信息增益（相对熵）

信息增益表示得知特征 $A$ 的信息而使得数据集 $D$ 的类别信息不确定性减少的程度.

特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ , 定义为集合 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差, 即

$g(D, A)=H(D)-H(D|A)$

假设样本有 K 类, 记 $|C_k|$ 是属于类 $C_k$ 的样本个数；假设特征 $A$ 有 $n$ 个不同的值 $a_{1...n}$ , 把样本 $D$ 划分为 $n$ 个子集 $D_{1...n}$ , 记 $D_i$ 中属于类 $C_k$ 的样本集合是 $D_{ik}$ , 那么有

$\begin{aligned} H(D)&=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}\\ H(D|A)&=\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)\\ H(D_i)&=\sum_{k=1}^{k}\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|} \end{aligned}$

信息增益可以用于决策树的特征选取：对训练数据集 D, 计算每个特征的信息增益, 选择信息增益大的特征.

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向选择取值较多的特征问题。可以用信息增益比校正，定义：

特征 A 对训练数据集 D 信息增益比

$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|}$

n 是特征 A 对取值个数

KL 散度

即信息增益或相对熵，衡量一个分布 $p$ 对另一个分布 $q$ 的差异性

$D_{KL}(p||q) = \mathbb E_{p,q} [\log p(x) - \log q(x)]=\sum_i p(x_i) [\log p(x_i) - \log q(x_i)]$

若 $p=0,q\ne0$ ，有 $0 * log(0 / b) = 0$ ；若 $q=0,p\ne0$ 有 $D_{KL}=+\inf$

熵定义

$H(p) =\mathbb E_p[-\log p] = -\sum_i p(x_i) \log p(x_i)$

交叉熵

\begin{align} CE(p,q) &= \mathbb E_p [-\log q] \\ &= H(p)+D_{KL} (p||q) \\ &= -\sum_i p(x_i) \log q(x_i)\\ &= - [p \log q + (1-p) \log (1-q)] （二分类形式；p 样本标签分布；q 模型预估分布） \end{align}

交叉熵与 log-likelihood 关系

\prod_i(i 观察到的概率)^{i 出现的次数} = \prod_i q_i^{N_{p_i}}

$\frac{1}{N} \log \prod_i q_i^{N_{p_i}} = \sum_i p_i \log q_i = - H(p,q)$

x = [np.random.randint(1, 11) for i in range(10)]
px = x / np.sum(x) 
# [0.12903226 0.01612903 0.06451613 0.12903226 0.11290323 0.09677419 0.14516129 0.14516129 0.01612903 0.14516129] 
y = [np.random.randint(1, 11) for i in range(10)]
py = y / np.sum(y)
# [0.09090909 0.09090909 0.06060606 0.03030303 0.03030303 0.15151515 0.18181818 0.09090909 0.24242424 0.03030303]
KL = 0.0
for i in range(10):
    KL += px[i] * np.log(px[i] / py[i])
print("KL = ", KL)
# KL = 0.5323363925599

基尼指数

Gini coefficient, 分类问题中, 假设有 $K$ 个类, 样本属于第 $k$ 类的概率为 $p_k$ , 则概率分布的基尼指数定义为:

$Gini(p)=\sum_k p_k(1-p_k)=1 - \sum_k p^2_k$

对于二分类问题, 若样本点属于第 1 个类的概率是 p, 则概率分布的基尼指数为:

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

对于给定的样本集合D, 其基尼指数为:

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

这里, $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集, $k$ 是类的个数.

如果样本集合 $D$ 根据特征 $A$ 是否取到某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分, 则在特征 $A$ 的条件下, 集合 $D$ 的基尼指数定义为:

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

基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性, 基尼指数越大, 样本集合的不确定性也就越大, 这一点与熵相似.

决策树

求所有可能的决策树是 NP 完全问题, 常用启发式方法, 近似求解, 得到次优解, 常用学习算法: ID3 / C4.5 / CART

特征选择的准则, 用信息增益、信息增益比、损失函数来衡量: 如果用一个特征进行分类的结果与随机分类的结果没有很大差异, 则认为这个特征是没有分类能力的.

一般算法: 递归地选择最优特征, 并根据该特征对训练数据进行分割.

剪枝: 以避免过拟合, 考虑全局最优.

优点: wiki

易于理解和解释
只需很少的数据准备其他技术往往需要数据归一化
即可以处理数值型数据也可以处理类别型数据
强健控制. 对噪声处理有好的强健性
可以很好的处理大规模数据

ID3（Quinlan 86’ 分类 / 信息增益）

极大似然进行概率模型的选择, 每次根据最大 信息增益 来选择特征分割数据，切分后不再用同一特征做分割。

信息增益

$g(D,A)=H(D)-H(D|A)$

其中 H(D) 是数据集 D 的经验熵

$H(D)=-\sum_{k} \frac{|C_k|}{|D|} \log \frac{|C_k|}{|D|}$

其中 H(D|A) 是特征 A 对数据集 D 的经验条件熵

$H(D|A)=\sum_i \frac{|D_i|}{|D|}H(D_i)=\sum_i \frac{|D_i|}{|D|} \sum_k \frac{|D_ik|}{|D_i|} \log \frac{|D_ik|}{|D_i|}$

缺点：

不能处理连续特征值
信息增益优先选择值较多的 Feature

输入: 训练集 D, 特征集 A, 阈值 ε

输出: 决策树 T

若 $D$ 同属一类 $C_k$ , 则 $T$ 为单节点树, 将 $C_k$ 作为该节点的类标记, 返回 $T$
若 $A = \{\}$ , 则 $T$ 为单节点树, 将 $D$ 中实例数最大的类 $C_k$ 作为该节点的类标记, 返回 $T$
否则, 计算 $A$ 中特征对 $D$ 的信息增益, 选择信息增益最大的特征 $A_g$
如果 $A_g$ 的信息增益小于阈值 ε, 则置 $T$ 为单节点树, 将 $D$ 中实例数最大的类 $C_k$ 作为该节点的类标记, 返回 $T$
否则, 对 $A_g$ 的每一可能值 $a_i$ , 以 $A_g=a_i$ (选均值、随机值或者其他) 将 $D$ 分割为若干非空子集 $D_i$ , 将 $D_i$ 中实例最大的类作为标记, 构建子节点, 构成树 $T$ , 返回 $T$
对第 $i$ 个子节点, 以 $D_i$ 为训练集, $A-{A_g}$ 为特征集, 递归地调用步骤 1 至 5, 得到子树 $T_i$ , 返回 $T_i$

C4.5（Quinlan 93‘ 分类 / 信息增益比）

改进 ID3

优点：

用 信息增益比 来选择特征，改善 信息增益 偏向选择值较多 Feature 的问题，对其进行校正、归一化。原因是 信息增益 定义 “已知特征 A 对数据集 D 类别不确定性减少对程度“，当 Feature 的值越多，数据集划分得越细，不确定性越小
不能处理特征值连续的问题
缺失值处理：众数、丢弃、按概率填补

缺点：

处理连续值需要扫描排序，性能下降

信息增益比

$g_R(D,A)= \frac{g(D,A)}{SplitInfo(D,A)}$

通过引入 Split Information 来惩罚值较多的 Feature：

$SplitInfo(D,A)= -\sum_i \frac{|D_i|}{|D|}\log \frac{|D_i|}{|D|}$

其中 $n$ 是特征 $A$ 取值的个数， $D_i$ 是根据特征 $A$ 的值将 $D$ 划分为 $n$ 个子集。

剪枝方法：极小化损失函数

一种简单的方法: 通过极小化 损失函数 来实现, 损失函数定义

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

其中 $T$ 任意子树, ${C(T)}$ 是对训练数据的预测误差（如基尼指数、平方误差）, $|T|$ 为子树的节点个数, $\alpha$ 为参数, 用于权衡训练数据的拟合程度和模型复杂度.

输入：由 CART 算法生成的决策树 $T_0$

输出：最优决策树 $T_\alpha$

设 $k=0,T=T_0,\alpha=+\inf$
自下而上地对内部节点 $t$ 的子树 $T_t$ , 计算训练集预测误差 $C(T_t)$ , 叶节点个数 $|T_t$ 以及

$\begin{aligned} g(t) &= \frac{C(t)-C(T_t)}{|T_t|-1} \\ \alpha &= min(\alpha, g(t)) \end{aligned}$

$g(t)$ 表示剪枝后整体损失函数减少的程度. 对 $g(t)=\alpha$ 即 $g(t)$ 最小的内部节点 $t$ 进行剪枝, 并对叶节点 $t$ 以多数表决发决定其类, 得到树 $T$
设 $k=k+1, \alpha_k=\alpha, T_k=T$
如果 $T_k$ 不是由根节点及两个叶节点构成的树, 则回到步骤 3; 否则令 $T_k=T_n$
采用交叉验证法在子树序列 $T_0,T_1,...,T_n$ 中选取最优子树 $T_\alpha$

CART（Breiman 84‘，分类 / 基尼指数，回归 / 平方误差）

分类与回归树, Breiman 1984 提出, 算法由特征选择、树的生成、剪枝组成, 分类、回归任务都可以用.

最小二乘法生成回归树

输入：训练集 $T=\{(x_1,y_1),...,(x_N,y_N)\}, x_i \in X, y_i \in Y$ , 其中 $Y$ 是连续变量

输出：回归树 $f(x)$

假设将输入空间划分成 $M$ 个单元 $R_1,...,R_M$ , 并且在每个单元 $R_m$ 上有固定输出值 $c_m$ , 于是回归树模型可表示为

$f(x)=\sum_{m=1}^{M} c_m I(x \subseteq R_m)$

当输入空间的划分确定时, 可用平方误差表示回归树的预测误差, 用平方误差最小的准则求借每个单元上的最优输出值

$\hat c_m = ave(y_i|x_i \subseteq R_m)$

如何对输入空间划分? 用启发式的方法, 选择第 j 个变量 $x^{(j)}$ 和它的取值 $s$ , 作为切分变量和切分点, 并定义两个区域

$\begin{aligned} R_1(j,s)=\{x|x^{(j)} \leq s\}\\ R_2(j,s)=\{x|x^{(j)} \gt s\} \end{aligned}$

然后寻找最优切分变量 $j$ 和最优切分点 $s$ , 即求解

$\min_{j,s} \bigg[\min_{c_1} \sum_{x_i\in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i\in R_2(j,s)} (y_i-c_2)^2\bigg]$

对固定输入变量 $j$ 可以找到最优切分点 $s$

$\begin{aligned} \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)) \end{aligned}$

遍历所有输入变量,找到最优的切分变量 $j$ , 构成一个对 $(j,s)$ , 将输入空间划分为两个区域

接着,对每个区域重复上述划分过程, 直到满足停止条件, 得到输入空间的划分空间 $R_1,R_2,...,R_M$ , 和一颗回归树

$f(x)=\sum_{m-1}^M \hat c_m I(x\in R_m)$

Regression Descision Tree

最小二乘回归树生成算法

输入：训练数据集 $D$

输出：回归树

算法：在训练集所在的输入空间中, 递归地将每个区域划分为两个子区域并决定每个子区域上的输出值, 构建二叉决策树：

(1) 选择最优切分变量 j 与切分点 s, 求解

$\min_{j,s} \bigg[\min_{c_1} \sum_{x_i \in R_1 (j, s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2) ^2 \bigg]$

遍历特征 j, 对固定的切分变量 j 扫描切分点, 选择使上式达到最小值的对 $(j, s)$

(2) 用选定的对 $(j, s)$ 划分区域并决定响应的输出值：

$\begin{aligned} 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_m (j,s)} y_i, x\in R_m, m=1,2\\ \end{aligned}$

(3) 继续对两个子区域调用步骤 (1) (2) , 直值满足停止条件（最大深度、样本数量不足无法细分）

(4) 将输入空间划分为 $M$ 个区域 $R_1,R_2,...,R_M$ , 生成决策树：

$T(x;\Theta_m)=\sum_{m=1}^{M} \hat c_m I(x \in R_m)$

Boosting Regression Decision Tree

迭代地使用多棵回归决策树, 每一颗树的学习目标, 是最小化上一棵树的残差

残差=真实值-预测值

这是一种加法模型, 模型预测值等于所有子树输出值的累加

$f_M(x)=\sum_{m=1}^M T(x;\Theta_m)$

其中 $T$ 表示决策树, $\Theta_m$ 表示决策树的参数, $M$ 树的个数.

用前向分布算法训练决策树：

(1) 令 $f_0(x)=0$

(2) $m=1,2,...,M$ 时,

$f_m(x)=f_{m-1}(x)+T(x;\Theta_m)$

其中 $f_{m-1}$ 是当前树, 通过最小化损失函数, 确定下一棵树的参数

$\hat \Theta_m=\arg \min \sum_{i=1}^{N} L(y_i, f_{m-1} + T(x_i;\Theta_m))$

GBDT (MART)

Boosting Tree 用加法模型和前向分步算法实现学习的优化过程. 当损失函数是平方损失和指数损失时, 每一步优化很简单；对一般损失函数而言, 如 absolute loss 和 Huber-M loss [4], 有时并不容易

针对这个问题, Freidman [3] 提出了梯度提升 Gradient Boost 算法, 利用最速下降法的近似方法, 其关键是将提升树算法中的残差，替换为值损失函数的 负梯度 （有别于 Boosting 方法的残差），为了可以扩展到更复杂的损失函数中（MSE 损失函数的负梯度与残差形式相同）

$-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)}$

简单而言，训练

初始回归拟合值为当前样本平均值 f0
进行多轮迭代 m=1，2，3…：
1. 计算当前残差 rm=y-fm
2. 用回归数拟合当前残差（最小化当前残差的平方值）
3. fm = fm-1 + 当前回归数残差
最后的分类器即为当前fm的拟合

输入: 训练集 $T=\{x_1,y_1,...,(x_n,y_n)\}, x_i \in X \subseteq \mathbb{R}^n, y_i \in Y \subseteq \mathbb{R}$ ;损失函数 $L(y, f(x))$

输出: 回归树 $\hat f(x)$

初始化

$f_0(x)=\arg \min_c \sum_{i=1}^{N}L(y_i,c)$

对 $m=1,2,..,M$

a. 对 $i=1,2,...,N$ 计算

$\gamma_{mi}=-\bigg[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\bigg]_{f(x)=f_{m-1}(x)}$

b. 对 $\gamma_{mi}$ 拟合一个回归树, 得到第 $m$ 棵树的叶节点区域 $R_{mj}$ , $j=1,2,...,J$

c. 对 $j=1,2,...,J$ 计算

$c_{mj}=\arg \min_c \sum{x_i \in \mathbb{R}_{mj}} L(y_i,f_{m-1}(x_i)+c)$

d. 更新

$f_m(x)=f_{m-1}(x)+\sum{j=1}^{J}c_{mj}I(x\in \mathbb{R}_{mj})$

得到回归树

$\hat f(x)=f_M(x)=\sum_{m=1}^{M}\sum_{j=1}^{J} c_{mj}I(x\in \mathbb{R}_{mj})$

其中, 当损失函数是 MSE 时, 损失函数与负梯度恰好相同, 此时 GBDT 与 Boosting Descision Tree 的形式相同.

(XG)Boosted Trees

Boosted Trees 模型定义：

$\hat y_i = \sum_{k=1}^K f_k(x_i), f_k \in \mathcal F$

其中 K 是树的个数, $f$ 是属于函数空间 $\mathcal F$ 的树, $\mathcal F$ 是所有可能的树集合.

目标函数定义：

$obj(\theta)=\sum_i^n l(y_i, \hat y_i) + \sum_{k=1}^K \Omega(f_k)$

Boosted Trees 定义和 RF 一样, 区别是树的训练的方法：增量训练和并行训练.

增量训练过程：

$\begin{aligned} \hat y^{(0)} &= 0 \\ \hat y_i^{(1)} &= f_1(x_i) = \hat y_i^{(0)} + f_1(x_i)\\ &...\\ \hat y_i^{(t)} &= \sum_{k=1}^t f_k (x_i) = \hat y_i^{(t-1)} + f_t(x_i) \end{aligned}$

在训练的每一步 t, 最优化目标：

$\begin{aligned} obj^{(t)} &= \sum_{i=1}^n l(y_i, \hat y_i^{(t)}) + \sum_{i=1}^t \Omega(f_i)\\ &= \sum_{i=1}^n l(y_i, \hat y_i^{(t-1)} + f_t(x_i)) + \sum_{i=1}^t \Omega(f_i) \end{aligned}$

如果 $l$ 是 MSE, 对目标函数 $obj^{(t)}$ 用二阶泰勒展开, 移除常数项得到：

$obj^{(t)} = \sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)$

其中：

$\begin{aligned} g_i = \partial_{\hat y_i^{(t-1)}} l (y_i, \hat y_i ^{(t-1)}) \\ h_i = \partial^2_{\hat y_i^{(t-1)}} l (y_i, \hat y_i ^{(t-1)}) \end{aligned}$

树函数定义：

$f_t(x)=w_{q(x)}, w \in R^T, q:R^d \to {1, 2, ..., T}.$

其中 $w$ 是叶子分数向量 , $q$ 是把数据映射到叶子的函数, $T$ 是树叶个数.

复杂度定义可以是：

$\Omega(f) = \gamma T + \frac{1}{2} \sum_{j=1}^T w_j^2$

结合 $f$ 和 $\Omega$ 的定义, 更新目标函数：

$\begin{aligned} obj^{(t)} &= \sum_{i=1}^n[g_i w_{q(x_i)} + \frac{1}{2}h_i w^2_{q(x_i)}] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^T w_j^2 \\ &= \sum_{j=1}^T [(\sum_{j \in I_j} g_i) w_j +\frac{1}{2} (\sum_{i \in I_j} h_i + \lambda) w_j^2] + \gamma T \end{aligned}$

其中 $I_j= \{i | q(x_i)=j\}$ 是所有归于 j 叶子的 i 的集合.

代入 $G_j=\sum_{i\in I_j} g_i$ 和 $H_j=\sum_{i\in I_j} h_i$ 得到：

$obj^{(t)} = \sum_{j=1}^T [G_j w_j + \frac{1}{2}(H_j + \lambda) w_j^2] + \gamma T$

对于 $w_j$ , 最优的值取在 $G_j w_j + \frac{1}{2} (H_j + \lambda) w_j^2$ 导数零点：

$\begin{aligned} w_j^* &= - \frac{G_j}{H_j + \lambda} \\ obj^* &= - \frac{1}{2} \sum_{j=1}^T \frac{G^2_j}{H_j + \gamma} + \gamma T \end{aligned}$

最后一个等式可以衡量树结构函数 $q(x)$ 的优劣. 在分裂节点的时候, 可以用 Gain 来衡量分裂节点的好坏：

$Gain = \frac{1}{2}[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L + G_R)^2 }{H_L+H_R+\lambda}] - \gamma$

其中每项含义：1) 新的左叶子分数 2) 新的右叶子分数 3) 原来叶子的分数 4) 新叶子的惩罚项

XGBoost 是基于上述监督规则和正则项（取代 CART 剪枝）的 Boosted Tree 库, 特性有：

支持分类和回归问题
shrinkage （衰减因子 $\eta$ ）：事实上这是一种正则化（regularization）方法，为了进一步过拟合，在每次对残差估计进行迭代时，不直接加上当前步所拟合的残差，而是乘以一个系数
行采样（Bagging）：每次迭代单步的树时，随机选一些样本的残差做拟合，而不是把所有样本的残差做拟合
列采样
Split Finding 算法优化：sklearn的gbdt是贪心算法穷举所有 split 较为耗时, xgboost 通过近似方法加速, 通过 weighted quantile sketch 算法划分特征区间, 使得搜索空间变小、计算结果 g h 可复用、可并行化；Sparsity-ware split finding, 缺失值走节点的默认方向（默认方向学习得到）, 提速50x；
系统设计优化：特征粒度并行支持, data 预排序以 column block 形式存储；Cache-aware access；可并行的近似直方图算法, 用于高效地生成候选的分割点.

决策树

包括 ID3 C4.5 CART 和剪枝技巧

优点：

可解释性好，容易理解，可视化
用于二、多分类和回归
处理数值型、连续型特征

缺点：

容易过拟合，一般通过限制高度、剪枝缓解
学习决策树被认为是 NP 难问题，启发式的贪心算法训练，不能保证全局最优解。可以通过 RF 的 bagging 方法引入随机性缓解。

随机森林

是决策树的组合, 适用于分类和回归. 较决策树, 它更容易避免过拟合, 不需要对参数进行正则化预处理, 冗余、相关的参数不会影响结果, 输入特征可以是离散和连续的.

在训练过程中引入随机性, 如特征的随机选择、训练集的随机抽样, 并行训练多颗树. 多个预测的结合, 有助于降低预测在某棵树上的相关性, 增加在测试集上的性能.

优点:

对于很多数据集表现良好, 精确度比较高
不容易过拟合
可以得到变量的重要性排序
既能处理离散型数据, 也能处理连续型数据
不需要进行归一化处理
能够很好的处理缺失数据
容易并行化等等

RF vs GBDT

GBDT 迭代地训练一组决策树, 每棵树的训练残差结果, 作为下一个带训练的树的输入标签.

RF 并行训练多个树, 每个树训练时用随机的样本、特征, 最后投票得到预测结果。

二者的区别有:

GBDT 每次训练一颗树, 而 RF 是并行训练多棵树, 前者时间较长
增加 GBDT 的 numTrees, 会增加过拟合的可能;增加 RF 的 numTree, 会减少过拟合的可能性
RF 较容易调参, 因为 numTree 增加会使性能单调提高, 而 GBDT 的 numTree 增加有可能会使性能降低
RF 是通过减少模型的方差来提高性能, 而 GBDT 是减少模型的偏差来提高性能
组成 RF 可是分类树也可以是回归树, 而 GBDT 只由回归树组成
RF 树的权值相等, GBDT 权值不等
GBT 是回归树而不是分类树, RF 可以是分类树或回归树
RF 使用的是随机样本、特征构建子树, GBT 使用所有样本、特征构建子树
RF 适合决策边界是矩形的, 不适合对角线型的
RF 一般较 GBDT 精度低，泛化性好
RF 自带 OOB 作为验证集合, 在生成过程中可以对误差进行无偏估计, 如果样本数量太小容易过拟合
RF 关注降低方差，适合高噪声数据集；GBDT 关注降低偏差，适合低噪声数据集

分类树 vs 回归树

分类树使用信息增益或者增益比率来划分节点, 每个节点样本的类别投票决定测试样本的类别
回归树使用最小化均方差划分节点, 每个节点样本的均值作为测试样本的回归预测值

GBDT vs XGBoost

GBDT 优化用到一阶梯度信息（损失函数函数负梯度）, XGB 优化用二阶梯度信息（损失函数泰勒二阶展开的负梯度）
GBDT 以 CART 回归树作为基分类器, XGB 还支持线性分类器
GBDT 通过剪枝做正则, XGB 通过在损失函数加入了正则项达到剪枝目的, 综合考虑叶节点个数、叶子结点输出的分数，还可以自定义正则项（要求二阶可导）
XGB 支持特征粒度的并行计算优化, 通过索引算法减少特征选择的时间
XGB 支持列抽样，借鉴 RF，降低计算量，减少过拟合
XGB 支持缺省值

一个特征的 Gini feature importance, 指 Gini 指数下降程度之和。

GBDT Encoder

一种有监督的特征选择方法，在 encode 过程中做了：特征离散化、特征组合、特征选择。

可以使用 leaf 信息 / branch 信息，作为 LR / FM 的输入。

LR / FM 能更好的刻画长尾信息；GBDT 更好刻画头部样本，同时自动做特征工程，二者结合效果更好。

XGBoost 不足

基于预排序（pre-sorted）方法的决策树算法：首先，对所有特征都按照特征的数值进行预排序。其次，在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点。最后，在找到一个特征的最好分割点后，将数据分裂成左右子节点。

优点：精确地找到分割点。

缺点：

空间消耗大：这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如，为了后续快速的计算分割点，保存了排序后的索引），这就需要消耗训练数据两倍的内存。
时间开销大：在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
对cache优化不友好：在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。

LightGBM

优化思路：

单个机器在不牺牲速度的情况下，尽可能多地用上更多的数据
多机并行时通信的代价尽可能地低，并且在计算上可以做到线性加速。

优化技巧：

基于直方图（histogram）的决策树算法。
GOSS，Gradient-based One-Side Sampling 单边梯度采样，在保留大梯度样本的同时，随机地保留一些小梯度样本，同时放大了小梯度样本带来的信息增益（首先把样本按照梯度排序，选出梯度最大的a%个样本，然后在剩下小梯度数据中随机选取b%个样本，在计算信息增益的时候，将选出来b%个小梯度样本的信息增益扩大 1 - a / b 倍。这样就会避免对于数据分布的改变）
EFB，Exclusive Feature Bundling 互斥特征的特征捆绑，将许多互斥的特征绑定为一个特征，这样达到了降维的目的。
leaf-wise 的叶子生长策略（带深度限制的）：LightGBM使用了带有深度限制的按叶子生长 (leaf-wise) 算法，选择具有最大误差的树叶进行生长。
直方图做差加速
直接支持 categorical 特征
并行优化，利用多核
Cache命中率优化
调参技巧：

Speed	better accuracy	over-fitting
将 max_bin 设置小一些	用较大的 max_bin	max_bin 小一些
用 feature_fraction 来做 sub-sampling		用 feature_fraction
用 bagging_fraction 和 bagging_freq		设定 bagging_fraction 和bagging_freq
	training data 多一些	training data 多一些
用 save_binary 来加速数据加载	直接用 categorical feature	用 gmin_data_in_leaf 和min_sum_hessian_in_leaf
用 parallel learning	用 dart	用 lambda_l1, lambda_l2 ，min_gain_to_split 做正则化
	num_iterations 大一些，learning_rate 小一些	用 max_depth 控制树的深度
	num_leaves 大一些	num_leaves 小一些