CatBoost：比XGBoost更优秀的GBDT算法

互联网的算法有很多应用场景，包括推荐系统、计算广告和金融反欺诈等。许多互联网的机器学习和数据挖掘问题都可以转化为分类问题。在处理这一类分类问题的时候，最常用的方法包括逻辑回归、GBDT和深度学习等。其中逻辑回归因为算法效率高，能有效处理大规模的数据，在深度学习还没有流行之前就被广泛的应用于大型的互联网公司。

深度学习是自 2012 年由百度首先成立深度学习实验室之后在国内掀起的人工智能大潮。然而由于深度学习目前还处于蓬勃发展的阶段，并且处理大规模数据时对于机器的经费的要求都比较高，因此在很多应用场景下大家选择的并不是机器学习。GBDT 自问世以来便在诸多机器学习问题上取得了良好的效果，不仅在工业界，而且在 Kaggle 比赛上取得了非常优秀的成绩。

针对 GBDT 算法，在学术界和工业界有许多开源的算法包。著名的包括 University of Washington 的陈天奇开发的 XGBoost ，微软的 LightGBM ，还有 Yandex 公司开发的 CatBoost 。XGBoost 被广泛的应用于工业界，LightGBM 有效的提升了 GBDT的计算效率， 而 Yandex 的 CatBoost 号称是比 XGBoost 和 LightGBM 在算法准确率等方面表现更为优秀的算法。本文主要通过介绍 Yandex 2017 年发表的一篇题为 CatBoost: Unbiased Boosting with Categorical Features 的论文给大家介绍 CatBoost 算法。

CatBoost 算法的设计初衷是为了更好的处理 GBDT 特征中的 categorical features 。在处理 GBDT 特征中的 categorical features 的时候，最简单的方法是用 categorical feature 对应的标签的平均值来替换。在决策树中，标签平均值将作为节点分裂的标准。这种方法被称为 Greedy Target-based Statistics , 简称 Greedy TBS，用公式来表达就是：

这种方法有一个显而易见的缺陷，就是通常特征比标签包含更多的信息，如果强行用标签的平均值来表示特征的话，当训练数据集和测试数据集数据结构和分布不一样的时候会出问题（条件偏移问题）。

一个标准的改进 Greedy TBS的方式是添加先验分布项，这样可以减少噪声和低频率数据对于数据分布的影响：

其中 P 是添加的先验项，a 通常是大于 0 的权重系数。

为了解决条件迁移问题，常用的方法例如可以将数据集合分为两部分，在第一个部分上对数据的特征进行类似 Greedy TBS 的处理，而在第二个数据集合上进行训练。CatBoost 参考了在线学习的方法，首先对训练书进行了随机的重排列，然后选择 作为训练样本，而整个的数据集合做为测试样本。

类似的，在GBDT的模型训练阶段，同样会因为训练数据与测试数据分布不同的问题产生预测偏移（Prediction Shift）和残差偏移（Residual Shift）的问题。为了解决相应的问题，CatBoost 作者采用了排序提升（Ordered Boosting）的方式，首先对所有的数据进行随机排列，然后在计算第 i 步残差时候的模型只利用了随机排列中前 i-1 个样本。

CatBoost 针对于原始 GBDT 的各种偏移问题进行改进之后的算法伪代码如下：

CatBoost 和 XGBoost 以及 LightGBM 在一些知名的数据集合上的测试效果如下表所示，评测指标为 Logloss 和 Zero-one Loss 。

CatBoost 的基本原理是解决原始 GBDT 中的各种数据偏移问题。在一些开源的机器学习和数据挖掘的算法包里有现成的模块可以调用。CatBoost 自从 2017 年被 Yandex 首次提出以来得到了广泛的关注。希望本文的介绍能给大家带来帮助。