大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

最近重点学习了gbdt算法，看了较多的博客文章，整理了一下这些比较有用的内容，包括算法理论、算法分析、代码剖析、注意事项等各个方面。

转载来源：

http://www.cnblogs.com/rocketfan/p/4324605.html

http://www.cnblogs.com/rocketfan/p/4365950.html

http://www.cnblogs.com/rocketfan/p/4366501.html

http://blog.163.com/zhoulili1987619@126/blog/static/3530820120159852041442/

http://blog.csdn.net/w28971023/article/details/43704775

http://www.cnblogs.com/leftnoteasy/archive/2011/03/07/random-forest-and-gbdt.html

GBDT的基本原理

这里以二元分类为例子，给出最基本原理的解释

   

GBDT 是多棵树的输出预测值的累加

GBDT的树都是 回归树 而不是分类树

   

1. 分类树

   

分裂的时候选取使得误差下降最多的分裂

计算的技巧

最终分裂收益按照下面的方式计算，注意圆圈内的部分是固定值

1. GBDT 二分类

GBDT在实现中可以完全复用上面的计算方法框架，只是我们的优化的目标函数不同。

这里使用的是 指数误差函数，不管是预测正确还是错误 误差值都存在，但是正确的预测 会使得误差值小于错误的预测 参考

AdaBoost and the Super Bowl of Classifiers

A Tutorial Introduction to Adaptive Boosting

关于常用误差函数 参考 http://www.cnblogs.com/rocketfan/p/4083821.html

   

参考 Greedy Functon Approximation:A Gradient Boosting Machine

4.4节关于二分类情况误差函数的设计

这里其实和上面给出的一样，只是增加了 log(1 +, 另外多了一个2,2yF), 参考前面的LossFunction http://www.cnblogs.com/rocketfan/p/4083821.html

的推导，其实这个应该算作LogLoss或者说是logistic regression, cross entropy error,也就是从probablity出发的logloss推导到output F(x)的表示就是上面的

式子，而它看上去刚好就是一个指数误差函数。

严格意义上说是LogLoss不是指数误差 不过LogLoss和指数误差看上去比较相似。

   

这个F值其实就是逻辑回归的思路，类似 语音语言处理一书27页解释，线性加权的值（output)用来预测 p(true)和p(false)的比例的log值（回归值是实数范围取值不适合预测0-1，做了一个转换)，越是接近true，那么F(x)越接近+无穷(对应最大可能性判断true)， p(false)越大 那么越接近-无穷(对应最大可能性判断false)

   

F(X) 对应 feature X 当前的回归预测值也就是多棵树经过决策到达叶子节点的输出值output(x)的累加值。N个样本则F(x)N个维度，当开始没有分裂的时候所有样本在一个节点则所有F(x)对应一个相同的值，分裂一次后两个叶子节点则F(X)对应可能到不同的叶子节点从而可能有两个不同的值。

对误差函数计算关于F的梯度，误差函数是

变量是F(x)

   

考虑learning_rate之后是 （@TODO)

F(X) 对应 叶子节点中一个样本对应它的feature X 当前的预测值

参考 机器学习概率角度 一书的16章

   

   

我们的分裂目标从上面回归树基本算法中的希望逼近y 变成了 逼近梯度值 r_im，

也就是说当前树是预测负梯度值的。

F_m(x) = F_m-1(x) + learning_rate*(当前树的预测值(也就是预测负梯度..)) //@TODO check

   

再对比下ng课件最简单的梯度下降 针对regression的例子

   

我们采用的每颗树更新策略是针对F(x)的，而F(x)沿着梯度的方向的累加，目标是使得我们的

误差函数达到最小。

GBDT原理实例演示 1

考虑一个简单的例子来演示GBDT算法原理

下面是一个二分类问题，1表示可以考虑的相亲对象，0表示不考虑的相亲对象

特征维度有3个维度，分别对象 身高，金钱，颜值

   

cat dating.txt

#id,label,hight,money,face

_0,1,20,80,100

_1,1,60,90,25

_2,1,3,95,95

_3,1,66,95,60

_4,0,30,95,25

_5,0,20,12,55

_6,0,15,14,99

_7,0,10,99,2

   

这个例子仅仅为了试验，数据量很小没有更多统计意义。

   

0,1,2,3对应可以考虑的相亲对象

4,5,6,7 对应不考虑的相亲对象

   

先看一下gbdt训练的结果

mlt dating.txt -cl gbdt -ntree 2 -nl 3 -lr 0.1 -mil 1 -c train -vl 1 -mjson=1

设置2棵树，叶子节点最多3个 也就是最多2次分裂，learning rate设置为0.1， 叶子节点中的最少样本数设置为1（仅供试验，一般不会设置为1，避免过拟合)

为了打印二叉树设置输出json格式的模型

   

Per feature gain:

0:face 1

1:hight 0.730992

2:money 0.706716

Sigmoid/PlattCalibrator calibrating [ 8 ] (0.00011 s)100% |******************************************|

I0324 16:57:53.240083 17630 time_util.h:113] Train! finished using: [1.486 ms] (0.001486 s)

I0324 16:57:53.240094 17630 time_util.h:102] Test itself! started

   

TEST POSITIVE RATIO:        0.5000 (4/(4+4))

   

Confusion table:

||===============================||

|| PREDICTED ||

TRUTH || positive | negative || RECALL

||===============================||

positive|| 4 | 0 || 1.0000 (4/4)

negative|| 0 | 4 || 1.0000 (4/4)

||===============================||

PRECISION 1.0000 (4/4) 1.0000(4/4)

LOG LOSS/instance:                0.2981

TEST-SET ENTROPY (prior LL/in):        1.0000

LOG-LOSS REDUCTION (RIG):        70.1854%

   

OVERALL 0/1 ACCURACY:        1.0000 (8/8)

POS.PRECISION:                1.0000

PPOS.RECALL:                1.0000

NEG.PRECISION:                1.0000

NEG.RECALL:                1.0000

F1.SCORE:                 1.0000

AUC: [1.0000]

   

对应这个例子，训练结果是perfect的，全部正确， 特征权重可以看出，对应这个例子训练结果颜值的重要度最大，看一下训练得到的树。

print-gbdt-tree.py –tree -1

Tree 0:

Tree 1:

GBDT原理实例演示 2

一开始我们设定F(x)也就是每个样本的预测值是0(也可以做一定的随机化)

Scores = { 0， 0， 0， 0， 0， 0， 0， 0}

   

那么我们先计算当前情况下的梯度值

   

GetGradientInOneQuery = [this](int query, const Fvec& scores)

{

//和实际代码稍有出入 简化版本

_gradient[query] = ((2.0 * label) * sigmoidParam) / (1.0 + std::exp(((2.0 * label) * sigmoidParam) * scores[query]));

};

   

考虑 0号样本 label是1 , learningRate也就是sigmoidParam设置为0.1, scores[query] = 0 当前Scores全是0

2 * 1 * 0.1 / (1 + exp(2 * 1 * 0.1 * 0)) = 0.1

考虑 7号样本 label是-1

2 * -1 * 0.1 / (1 + exp(2 * -1 * 0.1 * 0）) = –0.1

   

因此当前计算的梯度值是

Gradient = { 0.1， 0.1， 0.1， 0.1， –0.1， –0.1， –0.1， –0.1}

   

于是我们要当前树的输出F(x)拟合的targets就是这个Grandient

Targets = { 0.1， 0.1， 0.1， 0.1， –0.1， –0.1， –0.1， –0.1}

RegressionTree tree = TreeLearner->FitTargets(activeFeatures, AdjustTargetsAndSetWeights());

   

virtual RegressionTree FitTargets(BitArray& activeFeatures, Fvec& targets) override

   

现在我们考虑拟合这个梯度

gdb ./test_fastrank_train

(gdb) r -in dating.txt -cl gbdt -ntree 2 -nl 3 -lr 0.1 -mil 1 -c train -vl 1 -mjson=1

p Partitioning

$3 = {_documents = std::vector of length 8, capacity 8 = {0, 1, 2, 3, 4, 5, 6, 7}, _initialDocuments = std::vector of length 0, capacity 0, _leafBegin = std::vector of length 3, capacity 3 = {0, 0,

0}, _leafCount = std::vector of length 3, capacity 3 = {8, 0, 0}, _tempDocuments = std::vector of length 0, capacity 0}

   

gbdt对应每个特征要做离散化分桶处理，比如分255个桶，这里样本数据比较少，对应height特征，

20, 60, 3, 66, 30, 20, 15, 10

分桶也就是变成

BinMedians = std::vector of length 7, capacity 7 = {3, 10, 15, 20, 30, 60, 66}

p *Feature

$11 = {_vptr.Feature = 0xce8650 <vtable for gezi::Feature+16>, Name = “hight”,

BinUpperBounds = std::vector of length 7, capacity 7 = {
6.5, 12.5, 17.5, 25, 45, 63, 1.7976931348623157e+308},

BinMedians = std::vector of length 7, capacity 7 = {
3, 10, 15, 20, 30, 60, 66},

Bins = {_vptr.TVector = 0xce8670 <vtable for gezi::TVector<int>+16>, indices = std::vector of length 0, capacity 0,

values = std::vector of length 8, capacity 8 = {
3, 5, 0, 6, 4, 3, 2, 1}, sparsityRatio = 0.29999999999999999, keepDense = false, keepSparse = false, normalized = false, numNonZeros = 7,

length = 8, _zeroValue = 0}, Trust = 1}

 

Bins对应分桶的结果，比如_0样本hight 20，那么分桶结果是编号3的桶(0开始index)

   

考虑Root节点的分裂，分裂前考虑是8个样本在一个节点，我们选取一个最佳的特征，以及对应该特征最佳的分裂点

考虑hight特征，我们要扫描所有可能的分裂点 这里也就是说 考虑6个不同的分裂点

for (int t = 0; t < (histogram.NumFeatureValues – 1); t += 1)

   

比如6.5这个分裂点

那么

就是左子树 1个(_2样本)， 右子树7个，考虑下面公式 收益是 0.1^2/1 + (-0.1)^2/7 – CONSTANT = 0.01142857142857143 – CONSTANT

   

类似的考虑分裂点12.5,17.5……….. 选取一个最佳分裂点

   

然后同样的考虑 money, face 特征 选取最优(特征，分裂点）组合，

这里最优组合是(hight, 45)

   

左侧得到

   

_0,_2,_4,_5,_6, _7 -> 0.1 + 0.1 – 0.1 – 0.1 – 0.1 -0.1

   

右侧得到

_1,_3 -> 0.1 + 0.1

收益是

(-0.2)^2 /6 + (0.2)^2 / 2 – CONSTANT = 0.026666666666666665 – CONSTANT

(gdb) p bestShiftedGain

$22 = 0.026666666666666675

   

对应>的子树输出应该是 0.2 / 2 = 0.1 下图对应展示output是1，因为后续还有AdjustOutput，因为至少需要 F_m(x) = F_m-1(x) + learning_rate*(当前树的预测值(也就是预测负梯度..)) 黄色部分是最终该棵树的输出值

   

   

之后再选取两个分裂后的组 选一个最佳(特征，分裂)组合 -> (face, 57.5)

   

(gdb) p tree

$26 = {<gezi::OnlineRegressionTree> = {NumLeaves = 3, _gainPValue = std::vector of length 2, capacity 2 = {0.15304198078836101, 0.27523360741160119},

_lteChild = std::vector of length 2, capacity 2 = {1, -1}, _gtChild = std::vector of length 2, capacity 2 = {-2, -3}, _leafValue = std::vector of length 3, capacity 3 = {-0.10000000000000002,

0.10000000000000002, 0.033333333333333347}, _threshold = std::vector of length 2, capacity 2 = {4, 2}, _splitFeature = std::vector of length 2, capacity 2 = {0, 2},

_splitGain = std::vector of length 2, capacity 2 = {0.026666666666666675, 0.026666666666666679}, _maxOutput = 0.10000000000000002, _previousLeafValue = std::vector of length 2, capacity 2 = {0,

-0.033333333333333333}, _weight = 1, _featureNames = 0x6e6a5a <gezi::FastRank::GetActiveFeatures(std::vector<bool, std::allocator<bool> >&)+34>},

_parent = std::vector of length 3, capacity 3 = {1, -1, -2}}

   

调整一下Output

//GradientDecent.h

virtual RegressionTree& TrainingIteration(BitArray& activeFeatures) override

{

RegressionTree tree = TreeLearner->FitTargets(activeFeatures, AdjustTargetsAndSetWeights());

if (AdjustTreeOutputsOverride == nullptr)

{ //如果父类ObjectiveFunction里面没有虚函数 不能使用dynamic_pointer_cast… @TODO

(dynamic_pointer_cast<IStepSearch>(ObjectiveFunction))->AdjustTreeOutputs(tree, TreeLearner->Partitioning, *TrainingScores);

}

{

UpdateAllScores(tree);

}

Ensemble.AddTree(tree);

return Ensemble.Tree();

}

   

virtual void AdjustTreeOutputs(RegressionTree& tree, DocumentPartitioning& partitioning, ScoreTracker& trainingScores) override

{

//AutoTimer timer(“dynamic_pointer_cast<IStepSearch>(ObjectiveFunction))->AdjustTreeOutputs”);

for (int l = 0; l < tree.NumLeaves; l++)

{

Float output = 0.0;

if (_bestStepRankingRegressionTrees)

{

 * tree.GetOutput(l);

}

else

{
 //现在走这里

 * (tree.GetOutput(l) + 1.4E-45)) / (partitioning.Mean(_weights, Dataset.SampleWeights, l, false) + 1.4E-45);

}

if (output > _maxTreeOutput)

{

output = _maxTreeOutput;

}

else if (output < -_maxTreeOutput)

{

output = -_maxTreeOutput;

}

tree.SetOutput(l, output);

}

}

   

(gdb) p _weights

$33 = std::vector of length 8, capacity 8 = {0.010000000000000002, 0.010000000000000002, 0.010000000000000002, 0.010000000000000002, 0.010000000000000002, 0.010000000000000002,

0.010000000000000002, 0.010000000000000002}

   

_learningRate * tree.Getoutput(1) / partioning.Mean(_weights..) = 0.1 * 0.1 / 0.01 = 1

   

(gdb) p tree

$35 = (gezi::RegressionTree &) @0x7fffffffd480: {<gezi::OnlineRegressionTree> = {

NumLeaves = 3, _gainPValue = std::vector of length 2, capacity 2 = {0.15304198078836101, 0.27523360741160119},

_lteChild = std::vector of length 2, capacity 2 = {1, -1}, _gtChild = std::vector of length 2, capacity 2 = {-2, -3}, _leafValue = std::vector of length 3, capacity 3 = {-1, 1,

0.33333333333333343}, _threshold = std::vector of length 2, capacity 2 = {4, 2}, _splitFeature = std::vector of length 2, capacity 2 = {0, 2},

_splitGain = std::vector of length 2, capacity 2 = {0.026666666666666675, 0.026666666666666679}, _maxOutput = 0.10000000000000002, _previousLeafValue = std::vector of length 2, capacity 2 = {0, -0.033333333333333333}, _weight = 1, _featureNames = 0x6e6a5a <gezi::FastRank::GetActiveFeatures(std::vector<bool, std::allocator<bool> >&)+34>}, _parent = std::vector of length 3, capacity 3 = {1, -1, -2}}

   

之后UpdateAllScores(tree); 是用来更新scores的值，这里就是8个样本对应的scores值，也就是计算F(x)，注意多棵树则是对应记录多棵树的输出的值累加。

virtual void AddScores(RegressionTree& tree, DocumentPartitioning& partitioning, Float multiplier = 1)

{

for (int l = 0; l < tree.NumLeaves; l++)

{

int begin;

int count;

ivec& documents = partitioning.ReferenceLeafDocuments(l, begin, count);

Float output = tree.LeafValue(l) * multiplier;

int end = begin + count;

#pragma omp parallel for

for (int i = begin; i < end; i++)

{

Scores[documents[i]] += output;

}

SendScoresUpdatedMessage();

}

   

对应第一个棵树生成结束后

   

(gdb) p Scores

$7 = std::vector of length 8, capacity 8 = {
0.33333333333333343, 1, 0.33333333333333343, 1, -1, -1, 0.33333333333333343, -1}

   

这个时候再对应计算梯度：

for (int query = 0; query < Dataset.NumDocs; query++)

{

GetGradientInOneQuery(query, scores);

}

   

_gradient[0] =

2 * 1 * 0.1 / (1 + exp(2 * 1 * 0.1 * 0.33333333333333343))

: 0.2/(1.0 + math.exp(2*0.1/3))

Out[2]: 0.09666790068611772

   

这时候 我们需要拟合的梯度变为

(gdb) p _gradient

$9 = std::vector of length 8, capacity 8 = {0.096667900686117719, 0.090033200537504438,

0.096667900686117719, 0.090033200537504438, -0.090033200537504438, -0.090033200537504438,

-0.10333209931388229, -0.090033200537504438}

   

   

第二棵树

p tree

$10 = {<gezi::OnlineRegressionTree> = {NumLeaves = 3,

_gainPValue = std::vector of length 2, capacity 2 = {0.13944890100441296,

0.02357537149418417}, _lteChild = std::vector of length 2, capacity 2 = {-1, -2},

_gtChild = std::vector of length 2, capacity 2 = {1, -3},

_leafValue = std::vector of length 3, capacity 3 = {-0.9721949587186075,

-0.30312179217966367, 0.94840573799486361},

_threshold = std::vector of length 2, capacity 2 = {1, 1},

_splitFeature = std::vector of length 2, capacity 2 = {1, 2},

_splitGain = std::vector of length 2, capacity 2 = {0.024924858166579064,

0.023238200798742146}, _maxOutput = 0.094456333969913306,

_previousLeafValue = std::vector of length 2, capacity 2 = {0, 0.032222633562039242},

_weight = 1,

_featureNames = 0x6e6a5a <gezi::FastRank::GetActiveFeatures(std::vector<bool, std::allocator<bool> >&)+34>}, _parent = std::vector of length 3, capacity 3 = {0, 1, -2}}

   

累加第二棵树后的Scores，如果有第三棵树，那么在这个Scores的基础上再计算梯度值

(gdb) p Scores

$11 = std::vector of length 8, capacity 8 = {1.2817390713281971, 0.69687820782033638,

1.2817390713281971, 1.9484057379948636, -1.3031217921796636, -1.9721949587186076,

-0.63886162538527413, -1.3031217921796636}

GBDT（MART） 迭代决策树入门及源码解析