1.简介html
gbdt全称梯度降低树,在传统机器学习算法里面是对真实分布拟合的最好的几种算法之一,在前几年深度学习尚未大行其道以前,gbdt在各类竞赛是大放异彩。缘由大概有几个,一是效果确实挺不错。二是便可以用于分类也能够用于回归。三是能够筛选特征。这三点实在是太吸引人了,致使在面试的时候你们也很是喜欢问这个算法。 gbdt的面试考核点,大体有下面几个:面试
2. 正式介绍算法
首先gbdt 是经过采用加法模型(即基函数的线性组合),以及不断减少训练过程产生的残差来达到将数据分类或者回归的算法。app
咱们经过一张图片,图片来源来讲明gbdt的训练过程: 框架
图 1:GBDT 的训练过程机器学习
gbdt经过多轮迭代,每轮迭代产生一个弱分类器,每一个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求通常是足够简单,而且是低方差和高误差的。由于训练的过程是经过下降误差来不断提升最终分类器的精度,(此处是能够证实的)。函数
弱分类器通常会选择为CART TREE(也就是分类回归树)。因为上述高误差和简单的要求 每一个分类回归树的深度不会很深。最终的总分类器 是将每轮训练获得的弱分类器加权求和获得的(也就是加法模型)。学习
模型最终能够描述为:$$F_{m}(x) = \sum_{m=1}^{M}T\left ( x;\theta _m \right )$$spa
模型一共训练M轮,每轮产生一个弱分类器 $T\left ( x;\theta _m \right )$。弱分类器的损失函数$$\hat\theta_{m} = \mathop{\arg\min}_{\theta_{m}} \sum_{i=1}^{N}L\left ( y_{i},F_{m-1}(x_{i})+T(x_{i};\theta_{m} ) \right )$$3d
$F_{m-1}(x)$ 为当前的模型,gbdt 经过经验风险极小化来肯定下一个弱分类器的参数。具体到损失函数自己的选择也就是L的选择,有平方损失函数,0-1损失函数,对数损失函数等等。若是咱们选择平方损失函数,那么这个差值其实就是咱们日常所说的残差。
gbdt选择特征的细节实际上是想问你CART Tree生成的过程。这里有一个前提,gbdt的弱分类器默认选择的是CART TREE。其实也能够选择其余弱分类器的,选择的前提是低方差和高误差。框架服从boosting 框架便可。
下面咱们具体来讲CART TREE(是一种二叉树) 如何生成。CART TREE 生成的过程其实就是一个选择特征的过程。假设咱们目前总共有 M 个特征。第一步咱们须要从中选择出一个特征 j,作为二叉树的第一个节点。而后对特征 j 的值选择一个切分点 m. 一个 样本的特征j的值 若是小于m,则分为一类,若是大于m,则分为另一类。如此便构建了CART 树的一个节点。其余节点的生成过程和这个是同样的。如今的问题是在每轮迭代的时候,如何选择这个特征 j,以及如何选择特征 j 的切分点 m:
1 def findLossAndSplit(x,y): 2 # 咱们用 x 来表示训练数据 3 # 咱们用 y 来表示训练数据的label 4 # x[i]表示训练数据的第i个特征 5 # x_i 表示第i个训练样本 6 7 # minLoss 表示最小的损失 8 minLoss = Integet.max_value 9 # feature 表示是训练的数据第几纬度的特征 10 feature = 0 11 # split 表示切分点的个数 12 split = 0 13 14 # M 表示 样本x的特征个数 15 for j in range(0,M): 16 # 该维特征下,特征值的每一个切分点,这里具体的切分方式能够本身定义 17 for c in range(0,x[j]): 18 L = 0 19 # 第一类 20 R1 = {x|x[j] <= c} 21 # 第二类 22 R2 = {x|x[j] > c} 23 # 属于第一类样本的y值的平均值 24 y1 = ave{y|x 属于 R1} 25 # 属于第二类样本的y值的平均值 26 y2 = ave{y| x 属于 R2} 27 # 遍历全部的样本,找到 loss funtion 的值 28 for x_1 in all x 29 if x_1 属于 R1: 30 L += (y_1 - y1)^2 31 else: 32 L += (y_1 - y2)^2 33 if L < minLoss: 34 minLoss = L 35 feature = i 36 split = c 37 return minLoss,feature ,split
其实说gbdt 可以构建特征并不是很准确,gbdt 自己是不能产生特征的,可是咱们能够利用gbdt去产生特征的组合。在CTR预估中,工业界通常会采用逻辑回归去进行处理,在个人上一篇博文当中已经说过,逻辑回归自己是适合处理线性可分的数据,若是咱们想让逻辑回归处理非线性的数据,其中一种方式即是组合不一样特征,加强逻辑回归对非线性分布的拟合能力。
长久以来,咱们都是经过人工的先验知识或者实验来得到有效的组合特征,可是不少时候,使用人工经验知识来组合特征过于耗费人力,形成了机器学习当中一个很奇特的现象:有多少人工就有多少智能。关键是这样经过人工去组合特征并不必定可以提高模型的效果。因此咱们的从业者或者学界一直都有一个趋势即是经过算法自动,高效的寻找到有效的特征组合。Facebook 在2014年 发表的一篇论文即是这种尝试下的产物,利用gbdt去产生有效的特征组合,以便用于逻辑回归的训练,提高模型最终的效果。
图 2:用GBDT 构造特征
如图 2所示,咱们 使用 GBDT 生成了两棵树,两颗树一共有五个叶子节点。咱们将样本 X 输入到两颗树当中去,样本X 落在了第一棵树的第二个叶子节点,第二颗树的第一个叶子节点,因而咱们即可以依次构建一个五纬的特征向量,每个纬度表明了一个叶子节点,样本落在这个叶子节点上面的话那么值为1,没有落在该叶子节点的话,那么值为 0.
因而对于该样本,咱们能够获得一个向量[0,1,0,1,0] 做为该样本的组合特征,和原来的特征一块儿输入到逻辑回归当中进行训练。实验证实这样会获得比较显著的效果提高。
首先明确一点,gbdt 不管用于分类仍是回归一直都是使用的CART 回归树。不会由于咱们所选择的任务是分类任务就选用分类树,这里面的核心是由于gbdt 每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值 。这个要求每轮迭代的时候,弱分类器的输出的结果相减是有意义的。残差相减是有意义的。
若是选用的弱分类器是分类树,类别相减是没有意义的。上一轮输出的是样本 x 属于 A类,本一轮训练输出的是样本 x 属于 B类。 A 和 B 不少时候甚至都没有比较的意义,A 类- B类是没有意义的。
咱们具体到分类这个任务上面来,咱们假设样本 X 总共有 K类。来了一个样本 x,咱们须要使用gbdt来判断 x 属于样本的哪一类。
图三 gbdt 多分类算法流程
第一步 咱们在训练的时候,是针对样本 X 每一个可能的类都训练一个分类回归树。举例说明,目前样本有三类,也就是 K = 3。样本 x 属于 第二类。那么针对该样本 x 的分类结果,其实咱们能够用一个 三维向量 [0,1,0] 来表示。0表示样本不属于该类,1表示样本属于该类。因为样本已经属于第二类了,因此第二类对应的向量维度为1,其余位置为0。
针对样本有 三类的状况,咱们实质上是在每轮的训练的时候是同时训练三颗树。第一颗树针对样本x的第一类,输入为$(x,0)$。第二颗树输入针对 样本x 的第二类,输入为$(x,1)$。第三颗树针对样本x 的第三类,输入为$(x,0)$
在这里每颗树的训练过程其实就是就是咱们以前已经提到过的CATR TREE 的生成过程。在此处咱们参照以前的生成树的程序 便可以就解出三颗树,以及三颗树对x 类别的预测值$f_{1}(x),f_{2}(x),f_{3}(x)$。那么在此类训练中,咱们仿照多分类的逻辑回归 ,使用softmax 来产生几率,则属于类别 1 的几率$$p_{1}=exp(f_{1}{(x)})/\sum_{k= 1}^{3}exp(f_{k}{(x)})$$
而且咱们咱们能够针对类别1 求出 残差$y_{11}(x) = 0-p_{1}(x)$;类别2 求出残差$y_{22}(x)= 1-p_2(x)$;类别3 求出残差$y_{33}(x)= 0-p_{3}(x)$.
而后开始第二轮训练 针对第一类 输入为(x,$y_{11}(x)$), 针对第二类输入为(x,$y_{22}(x))$, 针对 第三类输入为 (x,$y_{33}(x)$).继续训练出三颗树。一直迭代M轮。每轮构建 3颗树。
因此当K =3。咱们其实应该有三个式子 $$F_{1M}{(x)}=\sum_{m=1}^{M}{\hat{C_{1m}}I(x\epsilon R_{1m})}$$ $$F_{2M}{(x)}=\sum_{m=1}^{M}{\hat{C_{2m}}I(x\epsilon R_{2m})}$$ $$F_{3M}{(x)}=\sum_{m=1}^{M}{\hat{C_{3m}}I(x\epsilon R_{3m})}$$
当训练完毕之后,新来一个样本 x1 ,咱们须要预测该样本的类别的时候,即可以有这三个式子产生三个值,$f_{1}(x),f_{2}(x),f_{3}(x)$。样本属于 某个类别c的几率为 $$p_{c}=exp(f_{c}{(x)})/\sum_{k= 1}^{3}exp(f_{k}{(x)})$$
上面的理论阐述可能仍旧过于难懂,咱们下面将拿Iris 数据集中的六个数据做为例子,来展现gbdt 多分类的过程。
样本编号 | 花萼长度(cm) | 花萼宽度(cm) | 花瓣长度(cm) | 花瓣宽度 | 花的种类 |
1 | 5.1 | 3.5 | 1.4 | 0.2 | 山鸢尾 |
2 | 4.9 | 3.0 | 1.4 | 0.2 | 山鸢尾 |
3 | 7.0 | 3.2 | 4.7 | 1.4 | 杂色鸢尾 |
4 | 6.4 | 3.2 | 4.5 | 1.5 | 杂色鸢尾 |
5 | 6.3 | 3.3 | 6.0 | 2.5 | 维吉尼亚鸢尾 |
6 | 5.8 | 2.7 | 5.1 | 1.9 | 维吉尼亚鸢尾 |
这是一个有6个样本的三分类问题。咱们须要根据这个花的花萼长度,花萼宽度,花瓣长度,花瓣宽度来判断这个花属于山鸢尾,杂色鸢尾,仍是维吉尼亚鸢尾。具体应用到gbdt多分类算法上面。咱们用一个三维向量来标志样本的label。[1,0,0] 表示样本属于山鸢尾,[0,1,0] 表示样本属于杂色鸢尾,[0,0,1] 表示属于维吉尼亚鸢尾。
gbdt 的多分类是针对每一个类都独立训练一个 CART Tree。因此这里,咱们将针对山鸢尾类别训练一个 CART Tree 1。杂色鸢尾训练一个 CART Tree 2 。维吉尼亚鸢尾训练一个CART Tree 3,这三个树相互独立。
咱们以样本 1 为例。针对 CART Tree1 的训练样本是$[5.1, 3.5 , 1.4, 0.2]$,label 是 1,最终输入到模型当中的为$[5.1, 3.5 , 1.4, 0.2, 1]$。针对 CART Tree2 的训练样本也是$[5.1, 3.5 , 1.4, 0.2]$,可是label 为 0,最终输入模型的为$[5.1, 3.5 , 1.4, 0.2, 0]$. 针对 CART Tree 3的训练样本也是$[5.1, 3.5 , 1.4, 0.2] $,label 也为0,最终输入模型当中的为$[5.1, 3.5 , 1.4, 0.2, 0]$.
下面咱们来看 CART Tree1 是如何生成的,其余树 CART Tree2 , CART Tree 3的生成方式是同样的。CART Tree的生成过程是从这四个特征中找一个特征作为CART Tree1 的节点。好比花萼长度作为节点。6个样本当中花萼长度 大于5.1 cm的就是 A类,小于等于 5.1 cm 的是B类。生成的过程其实很是简单,问题 1.是哪一个特征最合适? 2.是这个特征的什么特征值做为切分点? 即便咱们已经肯定了花萼长度作为节点。花萼长度自己也有不少值。在这里咱们的方式是遍历全部的可能性,找到一个最好的特征和它对应的最优特征值可让当前式子的值最小。
咱们以第一个特征的第一个特征值为例。R1 为全部样本中花萼长度小于 5.1 cm 的样本集合,R2 为全部样本当中花萼长度大于等于 5.1cm 的样本集合。因此 $R1 = \left \{ 2\right \}$,$R2 = \left \{ 1,3,4,5,6 \right \}$.
图 5 节点分裂示意图
y1 为 R1 全部样本的label 的均值 $1/1 = 1$。y2 为 R2 全部样本的label 的均值 $(1+0+0+0+0) /5 = 0.2$。
下面便开始针对全部的样本计算这个式子的值。样本1 属于 R2 计算的值为$( 1 - 0.2)^2$, 样本2 属于R1 计算的值为$( 1 -1 )^2$, 样本 3,4,5,6同理都是 属于 R2的 因此值是$(0-0.2)^2$. 把这六个值加起来,即是 山鸢尾类型在特征1 的第一个特征值的损失值。这里算出来(1-0.2)^2+ (1-1)^2 + (0-0.2)^2+(0-0.2)^2+(0-0.2)^2 +(0-0.2)^2= 0.84
接着咱们计算第一个特征的第二个特征值,计算方式同上,R1 为全部样本中 花萼长度小于 4.9 cm 的样本集合,R2 为全部样本当中 花萼长度大于等于 4.9 cm 的样本集合.因此 $R1 = \left \{ \right \}$,$R1 = \left \{ 1,2,3,4,5,6 \right \}$. y1 为 R1 全部样本的label 的均值 = 0。y2 为 R2 全部样本的label 的均值 $(1+1+0+0+0+0) /6 = 0.3333$。
图 6 第一个特征的第二个特侦值的节点分裂状况
咱们须要针对全部的样本,样本1 属于 R2, 计算的值为$( 1 - 0.333 )^2$, 样本2 属于R2 ,计算的值为$( 1 -0.333 )^2$, 样本 3,4,5,6同理都是 属于 R2的, 因此值是$(0-0.333)^2$. 把这六个值加起来山鸢尾类型在特征1 的第二个特征值的损失值。这里算出来 (1-0.333)^2+ (1-0.333)^2 + (0-0.333)^2+(0-0.333)^2+(0-0.333)^2 +(0-0.333)^2 = 2.244189. 这里的损失值大于 特征一的第一个特征值的损失值,因此咱们不取这个特征的特征值。
图 7 全部状况说明
这样咱们能够遍历全部特征的全部特征值,找到让这个式子最小的特征以及其对应的特征值,一共有24种状况,4个特征*每一个特征有6个特征值。在这里咱们算出来让这个式子最小的特征花萼长度,特征值为5.1 cm。这个时候损失函数最小为 0.8。
因而咱们的预测函数此时也能够获得: $$f(x) = \sum_{x\epsilon R_{1}} y_{1}*I(x\epsilon R_{1})+\sum_{x\epsilon R_{2}} y_{2}*I(x\epsilon R_{2})$$
此处 R1 = {2},R2 = {1,3,4,5,6},y1 = 1,y2 = 0.2。训练完之后的最终式子为 $$f_{1}(x) = \sum_{x\epsilon R_{1}} 1*I(x\epsilon R_{1})+\sum_{x\epsilon R_{2}} 0.2*I(x\epsilon R_{2})$$
借由这个式子,咱们获得对样本属于类别1 的预测值 $f_{1}(x) = 1 + 0.2 * 5 = 2$。同理咱们能够获得对样本属于类别2,3的预测值$f_{2}(x)$,$f_{3}(x)$.样本属于类别1的几率 即为 $$p_{1}=exp(f_{1}{(x)})/\sum_{k= 1}^{3}exp(f_{k}{(x)})$$
下面咱们用代码来实现整个找特征的过程,你们能够本身再对照代码看看。
1 # 定义训练数据 2 train_data = [[5.1,3.5,1.4,0.2],[4.9,3.0,1.4,0.2],[7.0,3.2,4.7,1.4],[6.4,3.2,4.5,1.5],[6.3,3.3,6.0,2.5],[5.8,2.7,5.1,1.9]] 3 4 # 定义label 5 label_data = [[1,0,0],[1,0,0],[0,1,0],[0,1,0],[0,0,1],[0,0,1]] 6 # index 表示的第几类 7 def findBestLossAndSplit(train_data,label_data,index): 8 sample_numbers = len(label_data) 9 feature_numbers = len(train_data[0]) 10 current_label = [] 11 12 # define the minLoss 13 minLoss = 10000000 14 15 # feature represents the dimensions of the feature 16 feature = 0 17 18 # split represents the detail split value 19 split = 0 20 21 # get current label 22 for label_index in range(0,len(label_data)): 23 current_label.append(label_data[label_index][index]) 24 25 # trans all features 26 for feature_index in range(0,feature_numbers): 27 ## current feature value 28 current_value = [] 29 30 for sample_index in range(0,sample_numbers): 31 current_value.append(train_data[sample_index][feature_index]) 32 L = 0 33 ## different split value 34 print current_value 35 for index in range(0,len(current_value)): 36 R1 = [] 37 R2 = [] 38 y1 = 0 39 y2 = 0 40 41 for index_1 in range(0,len(current_value)): 42 if current_value[index_1] < current_value[index]: 43 R1.append(index_1) 44 else: 45 R2.append(index_1) 46 47 ## calculate the samples for first class 48 sum_y = 0 49 for index_R1 in R1: 50 sum_y += current_label[index_R1] 51 if len(R1) != 0: 52 y1 = float(sum_y) / float(len(R1)) 53 else: 54 y1 = 0 55 56 ## calculate the samples for second class 57 sum_y = 0 58 for index_R2 in R2: 59 sum_y += current_label[index_R2] 60 if len(R2) != 0: 61 y2 = float(sum_y) / float(len(R2)) 62 else: 63 y2 = 0 64 65 ## trans all samples to find minium loss and best split 66 for index_2 in range(0,len(current_value)): 67 if index_2 in R1: 68 L += float((current_label[index_2]-y1))*float((current_label[index_2]-y1)) 69 else: 70 L += float((current_label[index_2]-y2))*float((current_label[index_2]-y2)) 71 72 if L < minLoss: 73 feature = feature_index 74 split = current_value[index] 75 minLoss = L 76 print "minLoss" 77 print minLoss 78 print "split" 79 print split 80 print "feature" 81 print feature 82 return minLoss,split,feature 83 84 findBestLossAndSplit(train_data,label_data,0)
目前,咱们总结了 gbdt 的算法的流程,gbdt如何选择特征,如何产生特征的组合,以及gbdt 如何用于分类,这个目前能够认为是gbdt 最常常问到的四个部分。至于剩余的问题,由于篇幅的问题,咱们准备再开一个篇幅来进行总结。