XGBoost 实现网络入侵数据的检测

XGBoost 原理及公式推导

                          *单位:东北大学*   *作者:王文举*
1. xgboost描述

      xgboost算法将各种弱评估器结合,是一种可扩展性提升树算法,弱评估器一般为CART树。
      CART 树是基于类别的条件概率分布模型,其模型结构为二叉树。CART既可以用于分类也能用于回归,对于CART回归树来说,其预测结果为叶结点上所有样本的均值。对CART分类树来说,可以采用投票的方法确定类别标签。
      xgboost算法是在梯度提升树(GBDT)的基础上改进而来。相同点都是采用前向分布加法模型,多个弱评估器加权累加,使目标预测值逐渐逼近真值,两者都是参数估计形式来表示模型。
不同点主要为:
(1)GBDT优化过程,采用损失函数的一阶导数信息,而XGBoost是对损失函数泰勒级数展开,利用二阶导。
(2)XGBoost在损失函数中引入正则化,限制叶节点数以及每个节点上的预测得分。
(3)XGBoost支持多线程,在划分节点是时,每个特征并行计算,提高运算迅速。同时,也引入随机森林列采样思想,节点划分时,只考虑部分属性。
(4)GBDT中预测值是由所有弱分类器上的预测结果的加权求和,其中每个样本上的预测结果就是样本所在的叶子节点的均值。而XGBT中的预测值是所有弱分类器上的叶子权重直接求和得到,也称为预测得分。
XGBoost的目标函数为:
L(ϕ)=i=1nl(y^i,yi)+Ω(fk) L(\phi)=\sum_{i = 1}^nl( \hat y_{i},y_{i} )+\Omega(f_k) L(ϕ)=i=1∑n​l(y^​i​,yi​)+Ω(fk​)Ω(fk)=γT+12λw2\Omega(f_k) = \gamma T+\frac{1}{2}\lambda||w||^2 Ω(fk​)=γT+21​λ∣∣w∣∣2 函数 lll是损失函数,l(y^i,yi)l(\hat y_i,y_i)l(y^​i​,yi​) 可以用来计算预测值 y^i\hat y_iy^​i​和真实值 yi\ y_i yi​差别程度。函数 Ω 为正则项,可以用来减少模型的复杂度,防止过拟合的发生。Ω(fk)\Omega(f_k)Ω(fk​)中包含两项,γT\gamma TγT与λw2\lambda||w||^2λ∣∣w∣∣2。其中 T 为树模型中叶节点的数量,这部分提供了对叶节点数目的控制。λw2\lambda||w||^2λ∣∣w∣∣2表示正则项,ω 为叶节点的权重,这部分控制了叶节点的权重,保证了不会因为过大的权重而导致过拟合现象的产生。当正则项被置为 0 时,XGBoost 目标函数就退化为提升树的目标函数。
      右侧第一项l(y^iyi)l(\hat y_i-y_i)l(y^​i​−yi​)是衡量我们的偏差,模型越不准确,第一项就会越大。第二项Ω(fk)\Omega(f_k)Ω(fk​)是衡量我们的方差,模型越复杂,模型的学习就会越具体,方差就会越大。所以其实在求解方差与偏差的平衡点,以求模型的泛化误差最小。
      由于模型通过叠加的方式来训练,在迭代的每一步过程中都添加一个基分类器ftf_tft​。则第t轮模型的预测结果为:
y^t(xi)=y^t1+ft(xi)\hat y^t (x_{i})=\hat y^{t -1}+f_t(x_{i})y^​t(xi​)=y^​t−1+ft​(xi​)      则目标损失函数改写为:
Obj(t)=i=1nl(yi,y^t1+ft(xi))+Ω(ft)+constantObj^{(t)}=\sum_{i = 1}^nl(y_{i},\hat y^{t-1}+f_{t}(x_{i}))+\Omega(f_t)+constantObj(t)=i=1∑n​l(yi​,y^​t−1+ft​(xi​))+Ω(ft​)+constant

2.损失函数求解

根据泰勒级数展开公式
f(x+Δx)f(x)+f(x)Δx+12f(x)Δx2 f(x+\Delta x)\simeq f(x)+f^{'}(x)\Delta x+\frac{1}{2}f^{''}(x)\Delta x^2f(x+Δx)≃f(x)+f′(x)Δx+21​f′′(x)Δx2将Δx\Delta xΔx替换为ft(xi)f_{t}(x_{i})ft​(xi​),则目标函数可以写成为
Obj(t)i=1n[l(yi,y^t1)+gift(xi)+12hift2(xi)]Obj^{(t)}\simeq \sum_{i = 1}^n[l(y_{i},\hat y^{t-1})+g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}{f_{t}}^{2}(x_{i})]Obj(t)≃i=1∑n​[l(yi​,y^​t−1)+gi​ft​(xi​)+21​hi​ft​2(xi​)] +Ω(ft)+constant+\Omega(f_t)+constant+Ω(ft​)+constant 上式定义: gi=ϑy^t1l(yi,y^t1)g_{i} =\vartheta_{\hat y^{t-1}} l(y_{i},\hat y^{t-1})gi​=ϑy^​t−1​l(yi​,y^​t−1) hi=ϑy^t12l(yi,y^t1)h_{i} ={\vartheta}^{2}_{\hat y^{t-1}} l(y_{i},\hat y^{t-1})hi​=ϑy^​t−12​l(yi​,y^​t−1)

3.参数估计

      XGBoost所用的弱评估器为CART树,即每个样本数据最终会落入CART决策树的叶结点上,故每次迭代产生的弱评估器ftf_{t}ft​可以用参数形式表示。
     在依次迭代中,假设样本xix_{i}xi​落入第jjj个叶结点中,写为j=q(xi)j =q(x_{i})j=q(xi​)。则样本在jjj叶节点上预测分数(又称叶子权重)可以写成wq(xi)w_{q(x_{i})}wq(xi​)​,q(xi)q(x_{i})q(xi​)表示落在哪个叶节点上。以参数估计方式,可知wq(xi)=ft(xi)w_{q(x_{i})} =f_{t}(x_{i})wq(xi​)​=ft​(xi​) 。此外,还需要做一步转化,原目标在样本数据上遍历,可以转化为在叶子节点上遍历。
Obj(t)i=1n[gift(xi)+12hift2(xi)]+Ω(ft)Obj^{(t)}\simeq \sum_{i = 1}^n[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}{f_{t}}^{2}(x_{i})]+\Omega(f_t)Obj(t)≃i=1∑n​[gi​ft​(xi​)+21​hi​ft​2(xi​)]+Ω(ft​) =i=1n[giwq(xi))+12hiwq(xi)2]+γT+12λj=1Twj2= \sum_{i = 1}^n[g_{i}w_{q(x_{i})})+\frac{1}{2}h_{i}{w_{q(x_{i})}^{2}}]+ \gamma T+\frac{1}{2}\lambda\sum_{j = 1}^T{w_j^{2}}=i=1∑n​[gi​wq(xi​)​)+21​hi​wq(xi​)2​]+γT+21​λj=1∑T​wj2​=j=1T[(iIjgi)wj+12(iIjhi+λ)wj2]+γT= \sum_{j = 1}^T[(\sum_{i\subset I_{j}} g_{i})w_{j}+\frac{1}{2}(\sum_{i\subset I_{j}} h_{i}+\lambda){w_j^{2}}]+ \gamma T=j=1∑T​[(i⊂Ij​∑​gi​)wj​+21​(i⊂Ij​∑​hi​+λ)wj2​]+γT令Gj=iIjgiG_j=\sum_{i\subset I_{j}} g_{i}Gj​=∑i⊂Ij​​gi​,Hj=iIjhiH_j =\sum_{i\subset I_{j}} h_{i}Hj​=∑i⊂Ij​​hi​,替换后,对损失函数求倒数,求解新的评估器wj{w^*_j}wj∗​,并将其带入损失函数
即:Obj=γT12j=1TGj2Hj+γObj = \gamma T-\frac{1}{2}\sum_{j= 1}^T\frac{G^2_j}{H_j +\gamma}Obj=γT−21​j=1∑T​Hj​+γGj2​​这里,Gj,HjG_j,H_jGj​,Hj​是由gj,hjg_j,h_jgj​,hj​有关,而gj,hjg_j,h_jgj​,hj​又是通过损失函数lll对前一棵树求导而来。所以当lll确定后,文中二分类采用binary:logistic,Gj,HjG_j,H_jGj​,Hj​就固定。所以,整个损失函数只和树的结构T有关。
     上述目标函数是基于每个叶子节点,也就是树的结构来计算。所以,我们的目标函数又叫做“结构分数”,分数越低,树整体的结构越好。如此,就建立了树的结构(叶子)和模型效果的直接联系。

4.树的结构分裂

     由于决策树的建模属于 NP 问题,因此 XG-Boost 采用贪心思想来建模。假设 ILI_LIL​和IRI_RIR​是数据集经过某个节点判断之后分裂的两个集合,I=ILIRI = I_L∪ I_RI=IL​∪IR​,计算
XGBoost 实现网络入侵数据的检测     根据LsplitL_{split}Lsplit​最大,选取最佳的树结构,在这种树结构下,计算Gj,HjG_j,H_jGj​,Hj​。就可以求解每棵树叶子的权重wj{w^*_j}wj∗​。

     以上为整个XGBoost基本理论与原理,对比分析XGBoost与决策树的区别:
使用指标:决策树采用信息熵或者基尼指数,XGBoost采用目标函数Obj。在选取特征上,决策树采用信息增益最大,而XGBoost采用LsplitL_{split}Lsplit​最大进行特征分裂。决策树中当信息增益小于给定阈值ϵ\epsilonϵ时停止分裂,而XGBoost中LsplitL_{split}Lsplit​小于γ\gammaγ时停止分裂。

上一篇:《深入理解XGBoost》


下一篇:面试记录--阿里云交叉面