1 原文

2 GBDT+LR

2.1 背景

CTR预估，广告点击率（Click-Through Rate Prediction）是互联网计算广告中的关键环节，预估准确性直接影响公司广告收入。CTR预估中用的最多的模型是LR，LR是广义线性模型，与传统线性模型相比，LR使用了Logit变换将函数值映射到0~1区间 ，映射后的函数值就是CTR的预估值。

LR，逻辑回归模型，这种线性模型很容易并行化，处理上亿条训练样本不是问题，但线性模型学习能力有限，需要大量特征工程预先分析出有效的特征、特征组合，从而去间接增强LR 的非线性学习能力。LR模型中的特征组合很关键，但又无法直接通过特征笛卡尔积 解决，只能依靠人工经验，耗时耗力同时并不一定会带来效果提升。如何自动发现有效的特征、特征组合，弥补人工经验不足，缩短LR特征实验周期，是亟需解决的问题。

GBDT（Gradient Boost Decision Tree）是一种常用的非线性模型，它基于集成学习中的boosting思想，每次迭代都在减少残差的梯度方向新建立一颗决策树，迭代多少次就会生成多少颗决策树。GBDT的思想使其具有天然优势，可以发现多种有区分性的特征以及特征组合，决策树的路径可以直接作为LR输入特征使用，省去了人工寻找特征、特征组合的步骤。这种通过GBDT生成LR特征的方式（GBDT+LR），业界已有实践（Facebook，Kaggle-2014），且效果不错，是非常值得尝试的思路。

2.2 三个问题

1、为什么建树采用ensemble决策树？

一棵树的表达能力很弱，不足以表达多个有区分性的特征组合，多棵树的表达能力更强一些。GBDT每棵树都在学习前面棵树尚存的不足，迭代多少次就会生成多少颗树。按paper以及Kaggle竞赛中的GBDT+LR融合方式，多棵树正好满足LR每条训练样本可以通过GBDT映射成多个特征的需求。

2、为什么建树采用GBDT而非RF？

RF也是多棵树，但从效果上有实践证明不如GBDT。且GBDT前面的树，特征分裂主要体现对多数样本有区分度的特征；后面的树，主要体现的是经过前N颗树，残差仍然较大的少数样本。优先选用在整体上有区分度的特征，再选用针对少数样本有区分度的特征，思路更加合理，这应该也是用GBDT的原因。

3、如何使用GBDT 映射得到的特征？

通过GBDT生成的特征，可直接作为LR的特征使用，省去人工处理分析特征的环节，LR的输入特征完全依赖于通过GBDT得到的特征。此思路已尝试，通过实验发现GBDT+LR在曝光充分的广告上确实有效果，但整体效果需要权衡优化各类树的使用。同时，也可考虑将GBDT生成特征与LR原有特征结合起来使用，待尝试。

2.3 GBDT构建特征

原文这么说： In this paper we introduce a model which combines decision trees with logistic regression, outperforming either of these methods on its own by over 3%, an improvement with significant impact to the overall system performance.
在预测Facebook广告点击中，使用一种将决策树与逻辑回归结合在一起的模型，其优于其他方法，超过3％。

用已有特征训练GBDT模型，然后利用GBDT模型学习到的树来构造新特征，最后把这些新特征加入原有特征一起训练模型。构造的新特征向量是取值0/1的，向量的每个元素对应于GBDT模型中树的叶子结点。当一个样本点通过某棵树最终落在这棵树的一个叶子结点上，那么在新特征向量中这个叶子结点对应的元素值为1，而这棵树的其他叶子结点对应的元素值为0。新特征向量的长度等于GBDT模型里所有树包含的叶子结点数之和。

上图有两棵树，左树有三个叶子节点，右树有两个叶子节点，最终的特征即为五维的向量。对于输入x，假设他落在左树第一个节点，编码[1,0,0]，落在右树第二个节点则编码[0,1]，所以整体的编码为[1,0,0,0,1]，这类编码作为特征，输入到线性分类模型（LR or FM）中进行分类。

2.4 GBDT与LR融合

在CTR预估中，如何利用AD ID是一个问题。直接将AD ID作为特征建树不可行，而onehot编码过于稀疏，为每个AD ID建GBDT树，相当于发掘出区分每个广告的特征。而对于曝光不充分的样本即长尾部分，无法单独建树。

综合方案为：使用GBDT对非ID和ID分别建一类树。

非ID类树：不以细粒度的ID建树，此类树作为base，即这些ID一起构建GBDT。即便曝光少的广告、广告主，仍可以通过此类树得到有区分性的特征、特征组合。

ID类树：以细粒度 的ID建一类树（每个ID构建GBDT），用于发现曝光充分的ID对应有区分性的特征、特征组合。

如何根据GBDT建的两类树，对原始特征进行映射？以如下图为例，当一条样本x进来之后，遍历两类树到叶子节点，得到的特征作为LR的输入。当AD曝光不充分不足以训练树时，其它树恰好作为补充。

3 python实现

3.1 生成数据

from sklearn import datasets

X, Y = datasets.make_classification(n_samples = 2000, n_features = 7, n_informative = 2, n_redundant = 2, n_repeated = 0, n_classes = 2)

X[0:2, :]

array([[ 0.55617676,  1.15518068,  1.14471709,  1.60238303, -0.83274605,
         0.9809634 , -1.06788763],
       [-0.3802745 , -1.16172054,  0.97471291,  0.37325733,  0.62175847,
        -1.04289459, -0.35255169]])

Y[0:2]

array([0, 1])

3.2 数据集划分

from sklearn.cross_validation import train_test_split

X_train, X_test, y_train, y_test = train_test_split(X, Y, test_size = 0.2, random_state = 33)

print(X_train.shape)
print(y_train.shape)
print(X_test.shape)
print(y_test.shape)

(1600, 7)
(1600,)
(400, 7)
(400,)

3.3 为GBDT生成数据集

import lightgbm as lgb

lgb_train = lgb.Dataset(X_train, y_train)
lgb_eval = lgb.Dataset(X_test, y_test, reference=lgb_train)

lgb_train.data[0:5, :]

array([[-1.78901975e+00, -2.13672953e+00, -3.55867954e-01,
         7.07590363e-01,  2.45621113e+00, -1.57509749e+00,
         1.33151080e-01],
       [-1.12873443e+00, -1.76466074e+00,  4.45921841e-02,
         8.93417107e-01,  1.60835722e+00, -1.41064052e+00,
         6.34965515e-01],
       [-9.30466511e-01,  8.84486094e-01, -8.23090631e-04,
        -1.50658131e+00,  9.96338385e-01,  1.17815479e+00,
         3.52329692e-01],
       [ 4.94948092e-01,  3.74651957e-01,  4.06111794e-01,
        -1.09187592e+00, -6.49036651e-01,  2.19101769e-01,
        -6.27506001e-01],
       [ 6.37746226e-01,  8.40892512e-01,  2.12280392e-02,
         3.26615088e-01, -8.86740977e-01,  6.40745122e-01,
        -2.80656519e-01]])

lgb_train.label[0:5]

array([1, 1, 1, 0, 0])

3.4 设置参数

# 各个参数含义可以查看官方文档：http://lightgbm.apachecn.org

params = {
            'task' : 'train',
            'boosting_type' : 'gbdt',
            'objective' : 'binary',
            'metric' : {'binary_logloss'},
            'num_leaves' : 64,
            'num_trees' : 100,
            'learning_rate' : 0.01,
            'feature_fraction' : 0.9,
            'bagging_fraction' : 0.8,
            'bagging_freq' : 5,
            'verbose' : 0
}

num_leaf = 64

3.5 训练GBDT

gbm = lgb.train(params, lgb_train, num_boost_round=100, valid_sets=lgb_eval)

D:\anaconda\envs\tensorflow\lib\site-packages\lightgbm\engine.py:118: UserWarning: Found `num_trees` in params. Will use it instead of argument
  warnings.warn("Found `{}` in params. Will use it instead of argument".format(alias))


[1]	valid_0's binary_logloss: 0.685329
[2]	valid_0's binary_logloss: 0.677346
[3]	valid_0's binary_logloss: 0.669733
[4]	valid_0's binary_logloss: 0.662271
[5]	valid_0's binary_logloss: 0.654957
[6]	valid_0's binary_logloss: 0.647804
......
[98]	valid_0's binary_logloss: 0.303422
[99]	valid_0's binary_logloss: 0.301712
[100]	valid_0's binary_logloss: 0.300002

3.6 保存模型

gbm.save_model('model.txt')

<lightgbm.basic.Booster at 0x1ad54f2ef28>

3.7 预测

# 训练得到100棵树之后，我们需要得到的不是GBDT的预测结果，而是每一条训练数据落在了每棵树的哪个叶子结点上
y_pred = gbm.predict(X_train, pred_leaf=True)

import numpy as np

print(np.array(y_pred).shape)
print(y_pred[0])

(1600, 100)
[15 16 30 30 30 40 17 38 17 17 25 26 26 26 38 45 44 40 41 42 39 40 48 40
 47 47 49 48 49 49 47 47 47 47 47 49 44 47 46 49 50 50 46 50 14 45 48 49
 48 50 43 47 46 46 46 44 41 46 41 37 47 53 46 46 48 48 48 38 38 51 49 50
 43 49 43 47 42 42 47 41 42 46 50 46 48 48 44 47 46 46 49 47 49 48 48 49
 49 26 52 35]

3.8 onehot处理

print(np.array(y_pred[0]))
print(np.arange(len(y_pred[0])))
print(np.arange(len(y_pred[0])) * num_leaf)
print(np.arange(len(y_pred[0])) * num_leaf + np.array(y_pred[0]))

[15 16 30 30 30 40 17 38 17 17 25 26 26 26 38 45 44 40 41 42 39 40 48 40
 47 47 49 48 49 49 47 47 47 47 47 49 44 47 46 49 50 50 46 50 14 45 48 49
 48 50 43 47 46 46 46 44 41 46 41 37 47 53 46 46 48 48 48 38 38 51 49 50
 43 49 43 47 42 42 47 41 42 46 50 46 48 48 44 47 46 46 49 47 49 48 48 49
 49 26 52 35]
[ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
 96 97 98 99]
[   0   64  128  192  256  320  384  448  512  576  640  704  768  832
  896  960 1024 1088 1152 1216 1280 1344 1408 1472 1536 1600 1664 1728
 1792 1856 1920 1984 2048 2112 2176 2240 2304 2368 2432 2496 2560 2624
 2688 2752 2816 2880 2944 3008 3072 3136 3200 3264 3328 3392 3456 3520
 3584 3648 3712 3776 3840 3904 3968 4032 4096 4160 4224 4288 4352 4416
 4480 4544 4608 4672 4736 4800 4864 4928 4992 5056 5120 5184 5248 5312
 5376 5440 5504 5568 5632 5696 5760 5824 5888 5952 6016 6080 6144 6208
 6272 6336]
[  15   80  158  222  286  360  401  486  529  593  665  730  794  858
  934 1005 1068 1128 1193 1258 1319 1384 1456 1512 1583 1647 1713 1776
 1841 1905 1967 2031 2095 2159 2223 2289 2348 2415 2478 2545 2610 2674
 2734 2802 2830 2925 2992 3057 3120 3186 3243 3311 3374 3438 3502 3564
 3625 3694 3753 3813 3887 3957 4014 4078 4144 4208 4272 4326 4390 4467
 4529 4594 4651 4721 4779 4847 4906 4970 5039 5097 5162 5230 5298 5358
 5424 5488 5548 5615 5678 5742 5809 5871 5937 6000 6064 6129 6193 6234
 6324 6371]

# 将每棵树的特征进行one-hot处理，第一棵树落在15号叶子结点上，那我们需要建立一个64维的向量，除15维之外全部都是0。

# 转换训练集
transformed_training_matrix = np.zeros([len(y_pred), len(y_pred[0]) * num_leaf], dtype=np.int64)
for i in range(len(y_pred)):
    temp = np.arange(len(y_pred[0])) * num_leaf + np.array(y_pred[i])
    transformed_training_matrix[i][temp] += 1

# 转换测试集
y_pred2 = gbm.predict(X_test, pred_leaf=True)
transformed_testing_matrix = np.zeros([len(y_pred2), len(y_pred2[0]) * num_leaf], dtype=np.int64)
for i in range(len(y_pred2)):
    temp = np.arange(len(y_pred2[0])) * num_leaf + np.array(y_pred2[i])
    transformed_testing_matrix[i][temp] += 1

3.9 逻辑回归

from sklearn.linear_model import LogisticRegression

lm = LogisticRegression(penalty = 'l2', C = 0.05)
lm.fit(transformed_training_matrix, y_train)
y_pred_test = lm.predict_proba(transformed_testing_matrix)

# print(y_pred_test)

NE = (-1) / len(y_pred_test) * sum(((1+y_test)/2 * np.log(y_pred_test[:,1]) +  (1-y_test)/2 * np.log(1 - y_pred_test[:,1])))
print("Normalized Cross Entropy " + str(NE))

Normalized Cross Entropy 0.9422853076579945

参考

1、原文：http://quinonero.net/Publications/predicting-clicks-facebook.pdf
2、代码：https://github.com/princewen/tensorflow_practice/blob/master/recommendation/GBDT%2BLR-Demo/GBDT_LR.py
3、随机森林、GBDT、XGBOOST区别：https://blog.csdn.net/yingfengfeixiang/article/details/80210145
4、腾讯大数据：http://www.cbdio.com/BigData/2015-08/27/content_3750170.htm
5、GBDT与LR：https://blog.csdn.net/shine19930820/article/details/71713680
6、刘建平博客—GBDT原理：https://www.cnblogs.com/pinard/p/6140514.html
7、代码2：https://github.com/guestwalk/kaggle-2014-criteo