机器学习之GBDT

机器学习之GBDT

gbdt全称梯度下降树，在传统机器学习算法里面是对真实分布拟合的最好的几种算法之一，在前几年深度学习还没有大行其道之前，gbdt在各种竞赛是大放异彩。原因大概有几个，一是效果确实挺不错。二是即可以用于分类也可以用于回归。三是可以筛选特征。这三点实在是太吸引人了，导致在面试的时候大家也非常喜欢问这个算法。

GBDT如何训练

首先gbdt 是通过采用加法模型（即基函数的线性组合），以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。

                         GBDT的训练过程

 gbdt通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求一般是足够简单，并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度。

弱分类器一般会选择分类回归树,由于上述高偏差和简单的要求 每个分类回归树的深度不会很深。最终的总分类器是将每轮训练得到的弱分类器加权求和得到的（也就是加法模型）。

gbdt 通过经验风险极小化来确定下一个弱分类器的参数。具体到损失函数本身的选择也就是L的选择，有平方损失函数，0-1损失函数，对数损失函数等等。如果我们选择平方损失函数，那么这个差值其实就是我们平常所说的残差.

但是其实我们真正关注的，1.是希望损失函数能够不断的减小，2.是希望损失函数能够尽可能快的减小。

所以如何尽可能快的减小呢？

让损失函数沿着梯度方向的下降。这个就是gbdt 的 gb的核心了。 利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值去拟合一个回归树。gbdt 每轮迭代的时候，都去拟合损失函数在当前模型下的负梯度。这样每轮训练的时候都能够让损失函数尽可能快的减小，尽快的收敛达到局部最优解或者全局最优解。

GBDT如何选择特征？

   gbdt选择特征的细节其实是想问你CART Tree生成的过程。这里有一个前提，gbdt的弱分类器默认选择的是CART TREE。其实也可以选择其他弱分类器的，选择的前提是低方差和高偏差。框架服从boosting 框架即可。

    下面我们具体来说CART TREE(是一种二叉树) 如何生成。CART TREE 生成的过程其实就是一个选择特征的过程。假设我们目前总共有 M 个特征。第一步我们需要从中选择出一个特征 j，做为二叉树的第一个节点。然后对特征 j 的值选择一个切分点 m. 一个 样本的特征j的值 如果小于m，则分为一类，如果大于m,则分为另外一类。如此便构建了CART 树的一个节点。其他节点的生成过程和这个是一样的。现在的问题是在每轮迭代的时候，如何选择这个特征 j,以及如何选择特征 j 的切分点 m:

原始的gbdt的做法非常的暴力，首先遍历每个特征，然后对每个特征遍历它所有可能的切分点，找到最优特征 m 的最优切分点 j。

如何衡量我们找到的特征 m和切分点 j 是最优的呢？ 我们用定义一个函数 FindLossAndSplit 来展示一下求解过程。

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

在这里，我们先遍历训练样本的所有的特征，对于特征 j，我们遍历特征 j 所有特征值的切分点 c。就可以找到最小的特征 j 以及切分点c。