xgboost是boosting算法的一种，其主要思想就是基于弱分类器集成在一起形成强分类器。训练时从一棵树开始直到k棵树，而最终预测的结果是：
$$\widehat{y_i}=\text{Ø}(x_i)=\sum _{k=1}^K{f}_k(x_i),f_k\in ϝ$$
其中 ϝ={f(x)=wq(x)}(q:Rm→T,w∈RT)\digamma=\{ f(x)=w_{q(x)}\}(q:\R^m\to T,w \in \R^T)ϝ={f(x)=wq(x)​}(q:Rm→T,w∈RT) 是CART。如下图训练两棵树老人和小孩的预测结果计算。

CART假设决策树是一棵二叉树，内部节点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。CART算法分两步：
1、决策树生成：递归地构建二叉决策树的过程，对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树；
回归树生成：假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练集D={(x1,y1),(x2,y2),...,(xN,yN)}D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}D={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，将输入空间（特征空间）划分为M个单元$R_1,R_2,...,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$，于是回归树模型可表示为：$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$当输入空间的划分确定时，可以用平方误差${\sum }_{x_i\in R_m}(y_i-f(x_i){)}^2$来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。而单元$R_m$上的$c_m$的最优值${\hat{c}}_m$是$R_m$上的所有输入实例$x_i$对应的输出$y_i$的均值，${\hat{c}}_m=\frac{1}{N}{\sum }_{x_i\in R_m}{y}_i,x\in R_m,m=1,2,...$。这里划分输入空间（特征空间）采用的启发式方法，选择第$j$个变量$x^{(j)}$和它的取值$s$，作为切分变量和切分点，并定义两个区域：R1(j,s)={x∣xj≤s}和R2(j,s)={x∣xj>s}R_1(j,s)=\{x|x^{j}\le s\} 和 R_2(j,s)=\{x|x^{j}> s\}R1​(j,s)={x∣xj≤s}和R2​(j,s)={x∣xj>s}然后寻找最优切分变量j和最优切分点s，具体地，求解$$\underset{j,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2]$$对固定输入变量$j$可以找到最优切分点$s$。遍历所有的输入变量，找到最优的切分变量$j$，构成一个$(j,s)$对。

算法描述：
输入：训练数据集D；
输出：回归树f(x)
在训练集所在的输入空间中，递归地将每个区域划分为两个子区域并决定子区域上的输出值，构建二叉决策树：
(1). 选择最优切分变量j与切分点s，求解：$$\underset{j,s}{\min }[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}(y_i-c_1{)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}(y_i-c_2{)}^2]$$遍历遍历$j$，对固定的切分变量$j$扫描切分点$s$，选择使上式达到最小值的$(j,s)$对。
(2). 用选定的$(j,s)$对划分区域并决定相应的输出值：R1(j,s)={x∣xj≤s}和R2(j,s)={x∣xj>s}R_1(j,s)=\{x|x^{j}\le s\} 和 R_2(j,s)=\{x|x^{j}> s\}R1​(j,s)={x∣xj≤s}和R2​(j,s)={x∣xj>s}$${\hat{c}}_m=\frac{1}{N}\sum _{x_i\in R_m}{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{c}_{m}I(x\in R_m)$$

分类树生成：使用基尼指数选择最优特征，同时决定该特征的最优二值切分点。分类问题中，假设有K个类，样本点属于第k类的概率为，则概率分布的基尼指数定义为：$$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$对于二分类问题，若样本点属于第1个类的概率是$p$，则概率分布的基尼指数为$Gini(p)=p(1-p)$。对于给定的样本集合$D$，其基尼指数为$Gini(D)=1-{\sum }_{k=1}^K(\frac{|C_k|}{|D|}{)}^2$，其中$C_k$是$D$中属于第$k$类的样本子集，$K$是类的个数。如果样本集合$D$根据特征$A$是否取某一可能值$a$被分割成和两部分，即：D1={(x,y)∈D∣A(x)=a},D2=D−D1D_1=\{(x,y) \in D|A(x)=a\},D_2=D-D_1D1​={(x,y)∈D∣A(x)=a},D2​=D−D1​则特征$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$的不确定性。基尼指数值越大，样本集合的不确定性越大。

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

2、决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
CART剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小（模型变简单），从而能够对未知数据有更准确的预测。CART剪枝算法有两步组成：1）从生成算法产生的决策树底端开始不断剪枝，直到的根节点，形成一个子树序列{T0,T1,...,Tn}\{T_0,T_1,...,T_n\}{T0​,T1​,...,Tn​}；2）通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。

CART剪枝算法描述：
输入：CART算法生成的决策树$T_0$
输出：最优决策树$T_a$
(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$为根节点的子树，$C(T_t)$是对训练数据的预测误差，$|T_t|$是$T_t$的叶结点个数
(4). 自上而下地访问内部节点$t$，如果有$g(t)=a$，进行剪枝，并对叶结点$t$以多数表决法决定其类，得到树$T$
(5). 设$k=k+1,a_k=a,T_k=T$
(6). 如果T不是由根节点单独构成树，则回到步骤（4）
(7). 采用交叉验证法在子树序列$T_0,T_1,...,T_n$中选取最优子树$T_a$。

XGBoost目标函数由预测值与真实值的误差和正则化项组成：$$L(\varphi )=\sum _{i=1}^n\ell (y_i,{\hat{y}}_i)+\sum _{k=1}^K\Omega (f_k)$$其中正则化项表达式为$\Omega (f)=\gamma T+\frac{1}{2}\lambda ||\omega |{|}^2$。$T$表示叶子节点的个数，$\omega$表示叶子节点的分数。$\gamma$可以控制叶子节点的个数，$\lambda$可以制叶子节点的分数不会过大，防止过拟合。

如一开始所说，每新训练一棵树都要拟合上次预测的残差，即当生成$t$棵树后，预测分数可以表示为：${\hat{y}}_i^{(t)}={\hat{y}}_i^{(t-1)}+f_t(x_i)$，此表达式是xgboost的训练梯度提升树的解决方案。则目标函数可以表示为$L(\varphi {)}^{(t)}={\sum }_{i=1}^n\ell (y_i,{\hat{y}}_i^{(t-1)}+f_t(x_i))+{\sum }_{k=1}^K\Omega (f_k)$，此时需要找到一个$f_t$能够最小化目标函数。这里XGBoost利用$f_t=0$处的泰勒二阶展开的方法求解目标函数。如下图是梯度提升树的训练过程。每增加一棵树都比上一次更加准确。因为每训练一棵树都会对数据集中预测不准确的样本进行权重标记，增加下一轮训练采样的几率（shrinkage subsampling）。

在决策树生成时xgboost在CART算法基础上做了一些改进，就是在寻找最优特征划分点时使用目标函数作为评价函数。在特征划分之前进行预排序，Weighted Quantile Sketch算法处理带权样本数据，Sparsity-aware Split Finding处理稀疏数据。
xgboost在系统设计时支持并行处理（Column Block for Parallel Learning
），在特征预排序时将数据加入内存单元；缓存的设置。