Page 285 - 《软件学报》2021年第10期

周杰英 等:融合随机森林和梯度提升树的入侵检测研究 3257

2 梯度提升决策树算法原理

2.1 梯度提升决策树模型
梯度提升决策树模型 [19] 是一种加法模型:
()  
Fx T  h ()x (1)
t 1 tt
其中,x 为输入样本,h t (x)为分类回归树(classification and regression trees,简称 CART),T 是梯度提升决策树中需
要构建的树的数量, t 是第 t 棵树的权重.
梯度提升决策树算法采用前向分布算法,首先确定 F 0 (x)为模型初始值,通常为常数,第 m 步的模型是
F m (x)=F m1 (x)+ m h m (x) (2)
其中,F m1 (x)为当前模型.
新添加的分类回归树 h m (x)通过最小化损失函数求得:
h  m argmin  N L ( ,y F m 1 ()x  i h ())x i (3)
i
h i 1
其中,N 是样本个数.梯度提升决策树采用梯度下降法来求解最优模型,将损失函数在当前模型 F m1 (x)的负梯度
值作为梯度下降的方向:
() 
Fx F   m N  L ( ,y F ( ))x (4)
m m 1 i 1 F m 1 i
其中, m 通过线性搜索(line search)求得:
i
 m argmin  N i 1 Ly i m 1 ( ))x i     L (,yF m 1 ( ))x i (5)
( ,F
  F m 1 ()x i
梯度提升决策树的正则化,可以通过设置学习率(learning rate)来控制:
F m (x)=F m1 (x)+v m h m (x) (6)
其中,v 表示学习率.学习率越小,则需要更多的 CART,最终误差会更小,但也会增加训练的时间.所以,需要同时
控制学习率和 CART 的个数以确定一个速度快且精度高的模型.
2.2 特征重要性评估

梯度提升决策树模型可以基于特征重要性评估来进行特征选择,以此选择与目标变量更加相关的特征进
行训练.它不仅能缩短计算的时间、加快训练的速度,还可以提高模型预测的精度.一个特征在所有决策树中被
选择用来划分数据的次数越多,则该特征对于预测结果起的作用越大.
假设有 C 个特征 X 1 ,X 2 ,X 3 ,…,X C ,使用基尼指数来评估特征的重要性.在第 i 棵树中,节点 m 的基尼指数是
2
GI m ()p  K k  1 p mk (1 p  mk ) 1  k  K p mk (7)
其中,K 表示有 K 个类别,p mk 表示节点 m 中类别 k 所占的比例.
节点 m 分枝前后的基尼指数变化量为
G=GI m GI l GI r (8)
其中,GI l 表示分枝后左节点的基尼指数,GI r 表示分枝后右节点的基尼指数.
特征 X j 在节点 m 的重要性为
Gn
VIM ( ii )  w  G (9)
m j m
n
其中, w  表示节点 m 的样本量 n 占总样本量 N 的比例.
m N
如果特征 X j 在第 i 棵树中出现的节点在集合 M 中,那么特征 X j 在第 i 棵树的重要性为
Gn
G
VIM ( ii )   VIM ( i i n ) (10)
ij mM jm

假设梯度提升树一共有 n 棵,那么特征 X j 的特征重要性为
n
G
Gn
VIM ( ii )   i 1 VIM ij ( ii n ) (11)
j