catboost

CatBoost = Category + Boosting 
2017年7月21日，俄罗斯Yandex开源CatBoost，亮点是在模型中可直接使用Categorical特征并减少了tuning的参数。

建树的过程：

1.初步计算splits 
对每个数值特征二值化，选择可能的分桶方式，结果用于选择树结构。binarization method (feature_border_type) 和number of buckets (border_count) 参数设置在初始参数中。
2.将categorical特征转化为numerical特征 
(也可以使用one-hot编码) 
有以下三步： 
(1). 随机重排输入对象； 
(2). 将target从浮点数转换为整数 (Regression/ Classification/ Multiclassification不同)； 
(3). 将categorical特征转化为numerical特征 (与初始参数有关)： 

3.选择树结构 
        贪婪算法，找出所有可能分割方式，计算每种方式的惩罚函数，选择最小的，将结果分配个叶节点。后续叶节点重复此过程。在构建新树前进行随机重排，按梯度下降方向构建新树。

过拟合检测

1.IncToDec 
在建每棵树之前，在测试集上检测损失的变化，如果CurrentPValue大于初始参数Thresold则认为过拟合。计算CurrentPValue的方法如下： 

2.Iter 
在建每棵树之前，检查最小损失时的迭代次数，大于设置的参数值则认为过拟合。

参考资料

http://learningsys.org/nips17/assets/papers/paper_11.pdf