首先论文
Greedy Function Approximation: A Gradient Boosting Machine.
一些相关的开源实现
先贴几套开源实现代码的地址,这里主要研究的2,3，其中2是c++版的残差版本,3中的MART也是残差版本实现，最近在做ReRank相关的事情刚好要用到LambdaMART
- XgboostXgboost源码-github Xgboost文档
- C++版 gbdt源码下载地址-CSDN 10积分 github修改版地址
- Ranklibsourceforge地址
- simple-gbdtgoogle code地址 依赖tbb库github 某同学fork版本
- elf项目sourceforge地址
- Spark中的GradientBoostedTreesgithub地址
暂且简单描述下
- 1中Xgboost支持力度很大，支持python,R，Java.etc 甚至spark
- 2中所指gbdt网上有几篇分析的文章都是用的这个版本，这个版本训练是没啥问题，不过predict的时候不友好，感觉简化了。修改了下
- 3中Ranklib支持的算法也很多，基本可以开包即用了.
- 4中simple-gbdt，依赖tbb库.
- Spark中的实现
讲到GBDT的时候首先应该指出是残差版本还是Gradient版本，因为在原理，求解，实现上存在一些差异（这个差异在理解上可能会导致犯迷糊,反正自己绕不少弯路）,这里主要讨论残差版本。xgboost目前也在使用，还没深入研究，这里主要研究2和3中的版本。2，3也有讲解源代码的文章了。Ranklib的实现比较好理解。
Future选取问题
可以随机选择rand_fea_num个特征进行分裂，确定最优的分裂特性 2中C++代码实现
1
2
3
4
for (int i = 0; i < gbdt_inf.rand_fea_num; ++i)
{
int select = rand() % (last+1);//随机选择一个特征
}
分裂问题，
分裂：分裂后的均方误差最小
Best split标准计算依据
计算公式：
2中C++代码实现
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
for (int j=ninf.index_b; j< ninf.index_e; j++)
{
// d = y_result_score[data_set->order_i[j]];
d = data_set->y_list[data_set->order_i[j]];
left_sum += d;
right_sum -= d;
left_num++;
right_num--;
if (data_set->fv[j] < data_set->fv[j+1])
{/** 均方误差Mean Squared Error, MSE）最小? */
crit = (left_sum * left_sum / left_num) + (right_sum * right_sum / right_num) - ninf.critparent;
if (crit > critvar)
{
tmpsplit = (data_set->fv[j] + data_set->fv[j+1]) / 2.0; // 实际分割用的feature value
critvar = crit;
}
}
}
if (critvar > critmax) // 如果这个feature最终的critvar > cirtmax, 保存信息
{
spinf->bestsplit = tmpsplit; // split feature vale
spinf->bestid = fid; // split feature id
critmax = critvar; // split crit vaule
}
节点的输出值
节点的输出值为该节点上所有sample的label的均值 Ranklib中MART的实现,在GBDT中pseudoResponses就是残差，也就是label
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
protected void updateTreeOutput(RegressionTree rt)
{
List<Split> leaves = rt.leaves();
for(int i=0;i<leaves.size();i++)
{
float s1 = 0.0F;
Split s = leaves.get(i);
int[] idx = s.getSamples();
System.out.println("leaves(i)" + i +" idx.length: "+idx.length);
for(int j=0;j<idx.length;j++)
{
int k = idx[j];
s1 += pseudoResponses[k];
}
s.setOutput(s1/idx.length);
}
}
2中的代码gbdt_test.cpp 中跑test的时候尽然是一行输入一行输出？ 修改了几行代码
1
2
3
char* test_file_name = argv[2];
std::ifstream fin(test_file_name,std::ios::in)
while(getline(fin,line))
进入gbdt的目录
1
2
3
4
5
cd lib_gbdt
make all
cd output/test
./gbdt-train -r 0.8 -t 100 -s 0.03 -n 30 -d 5 -m test.model -f ../../train
./gbdt-test ./test.model ../../train
GDB调试代码
1
gdb ./gbdt-train
可以设置参数,断点，执行
1
2
(gdb) set args -r 0.8 -t 100 -s 0.03 -n 30 -d 5 -m test.model -f ../../train
(gdb) show args
参考链接