CatBoost：专治类别型特征的Boosting算法

在建模过程中，我们常常会遇到一类比较“棘手”的特征——类别型特征。例如在针对客户的价值或行为进行预测时，经常需要将诸如性别、城市、学历、婚姻状况等信息纳入考量。在对这些信息进行建模时，往往需要进行大量的前期工作。

本文要介绍一种专门针对类别型变量的算法——CatBoost，让我们不再需要手动处理类别型变量。

• 一、CatBoost 算法简介

• 二、目标变量统计

• 三、预测偏移

• 四、树模型的建立

• 五、Python实践案例

• 六、总结

一、CatBoost 算法简介

CatBoost^[1]，来源于“Category”和“Boosting”，属于 Boosting 算法的一种，由俄罗斯最大的搜索引擎 Yandex 于 2017 年开发，与 XGBoost^[2]、LightBGM^[3] 一样，都是对 GBDT 算法的改进。相较于其他 Boosting 算法，CatBoost 的优势在于能够高效处理类别型变量、能够有效防止过拟合且模型训练精度高。

CatBoost 的主要特点

自动处理类别型特征: 在使用 CatBoost 建模时，不需要对类别型特征进行任何预处理。CatBoost 使用内置的算法，实现了在建模的过程中直接将类别型特征转化为数值型特征。

特征组合: CatBoost 在建模中还会根据特征的内在联系将原有类别型特征进行组合，丰富了特征维度，提升了预测结果的精确性。

排序的思想: CatBoost 在处理类别型变量和进行树模型构建时，都是基于样本的某个随机排序，对样本进行加工和计算，以获取目标变量统计值和模型梯度值的无偏估计，有效避免了预测偏移(Prediction Shift)。

二、目标变量统计

2.1 类别型变量数值转换

类别型特征是在金融数据分析中常见的一类特征。所谓类别型特征，即这类特征不是连续的数值，而是一些用以区分类别的值的集合。这些特征值不能直接应用于建模，需要先向数值型特征进行转换，将这些特征加工成目标变量统计值 (Target Statistics)，再进行建模工作。

在一般算法中，TS 的计算往往是采用特征值为某一类别的所有样本对应的目标变量的期望  。假设总样本量为  ，对于第  个样本  的第  个特征  ，假设该特征类别为  ，则对于所有第  个特征取值为  的样本  都有：

其中  为样本  的目标变量值， 为示性函数，即  时函数取值为 1 ，否则函数取值为0 。

然而，这种方法的主要缺陷在于类别型特征中低频次特征带来的噪声。为了解决这一问题，Catboost 算法采用了 Greedy TS，即在公式中添加了先验分布项：

其中  是添加的先验项， 是大于 0 的权重系数。针对类别数较少的特征，添加先验项可以减少噪音。对于回归问题，先验项可取数据集目标变量的均值；对于二分类问题，先验项是正例的先验概率。

Greedy TS 依旧存在一定缺陷，因为其使用了  对  进行估计，导致  有偏。

通过抽取不包含  的部分样本  对  进行估计可以解决  有偏的问题：

抽取部分样本  的方法有很多，比如 Holdout TS，Leave-one-out TS 以及 Ordered TS 。Catboost算法采用的是效率更高的Ordered TS：  ，即取在某一给定的样本排序  中排在样本  前的样本  的集合。

我们可以看到，这里第  项的表达为  ，其含义为在某一样本排序  中的第  项。通过构造样本的排序， 的估计值  等于：前  个样本中所有第  个特征类别为 c 的样本对应的目标变量的平均值  。这一算法有效克服了  有偏引起的过拟合问题。

2.2 特征组合

CatBoost 的另一个重要细节就是将所有类别型特征进行组合，并将存在较高内在联系的组合特征作为新的的特征参与建模。例如在进行销售预测时，可以将用户号 (user_id) 与用户喜欢的商品名称或类别进行组合。

组合数量随类别型特征数量的增加呈指数型增长，类别型特征较多的情况下很难将所有类别型特征都进行组合。CatBoost采用了一种贪婪策略：在每次进行树模型新的分割结点选择时，将当前树所有分割点已使用的类别型特征（组合）与数据集中所有类别型特征进行组合，并计算其 TS 作为新的特征值参与树模型构建。

三、预测偏移

3.1 梯度提升算法的基本概念

首先来说说梯度提升 (gradient boosting) 的整体迭代过程：

梯度提升算法通过对一组弱分类器  串行迭代，最终得到一个强学习器  ，以此来提高分类器的拟合精度。

假设前一轮迭代得到的强学习器是  , 损失函数是  ，则本轮迭代的目的是从一组函数  中找到能使本轮迭代的损失函数  取到最小的  ，其中  ， 为步长或学习率 (learning rate)。式 (5) 为本轮迭代的目标函数:

一般处理最优化问题常见的做法是采用牛顿法 (Newton's Method^[4])，即使用损失函数的负梯度  来拟合每一轮的损失的近似值。求解梯度公式如式 (6) :

使用最小二乘法拟合的损失函数如下:

最终得到本轮的强学习器  :  。

CatBoost 使用二叉树 (Binary Decision Tree) 作为基分类器，在 CatBoost 中的分类器  可写作：

其中  是第  个叶子结点包含的样本集合， 是这些样本集的个数，属于叶子结点  的所有样本  的目标变量  的取值都为  。

3.2 预测偏移的形成

所有经典的梯度提升算法都存在由有偏的点态梯度估计引起的过拟合问题。在使用训练集  训练模型时，公式 (7) 的实际形式如下：

由于上一轮在获得强分类器  时，已经使用了当前样本点  进行建模，导致使用式 (6) 拟合本轮梯度的条件分布  有偏于测试集的真实分布  ，进而影响了本轮强分类器的  的预测效果，形成预测偏移 (Prediction Shift)。

想要获得所有样本点  ,...,  在  轮循环中梯度  的无偏估计，理论上在训练模型  时就不能使用其中的任何一个，这样一来看似就没有可以用来进行建模的样本了。为了解决这一问题，CatBoost 提出了一种叫做 Ordered Boosting 的集成算法。

3.3 Ordered Boosting

为了获得每一个样本点上梯度值的无偏估计，Ordered Boosting 依旧利用了排序的核心思想。首先初始化模型  ,...,  。给定某一排序  ，在第  轮建模中：

1. 使用排在  之前的所有样本  ,...,  建模得到的模型  对  的目标值进行估计，并计算出残差 (residual) ；

2. 用  来构建模型  ;

3. 最后用  来修正第   轮得到的  ，以降低下一轮预测的残差;

这一做法避免了使用当前样本导致的误差偏移 (residual shift) ，有效的避免了过拟合问题。

使用 Ordered Boosting 思想建树的伪代码如图1：

图1 Ordered Boosting伪代码

从代码中可以看出，该方法在每轮循环中，针对每一个  都要训练并优化一个模型  ，一共需要训练  个不同的模型，大大增加了算法的时间复杂度和占用的内存空间。同时，选定的样本排序不同对于模型的预测结果也存在一定影响，提高了算法的不稳定性。CatBoost 在 Order Boosting 的基础上，结合 GBDT 的基本概念对算法进行了优化。

四、树模型的建立

CatBoost算法的核心环节在于树结构  的建立：  。

4.1 建立新树的基本思想

CatBoost 建模过程与其他 GBDT 算法一样分为两个阶段：选择树结构  和在树结构固定后计算叶子节点的值  。每一轮循环的输出结果都是一个树结构  和更新后的模型  。

在 CatBoost 构建树的过程中，模型  用于计算叶子结点上目标变量的值。 是基于样本排序  中前  个样本计算出的样本  的当前目标变量的估计值  。在每轮迭代中，从  个不同的样本排序  中抽取一组排序  ，并基于这个排序建立一个新的树结构  ，再依据  更新所有模型  ,...,  。在这里，  代表对于所有样本随机生成的  种不同顺序的序列。

4.2 两个核心公式

• ：计算每个样本点  基于树  和排序  所属的叶子结点（不同的排序会导致算出不同的 TS，进而影响每个样本点所属的叶子结点）。

• ：基于损失函数  和当前的模型  以及目标变量  计算模型  在样本点  上的梯度，如式 (6)，  相当于其中的  。

4.3 建立新树  步骤

1. 随机抽取一种样本排序  ;

2. 基于样本排序以及模型 ，估计每一个样本点  的梯度值 ;

3. 对每一种可能的分割方案  ，建立树结构  ，计算所有样本基于  和排序  所属的叶子结点，并计算每个叶子结点的所有样本梯度的均值作为该叶子结点样本的梯度的估计值 ;

4. 构造梯度值损失函数，选取使损失函数取最小值的树结构作为本轮的树模型  ;

5. 基于树  ，计算每一种排序  ,...,  情况下属于同一叶子结点的样本  的负梯度均值，作为样本基于树  在该排序下的目标值  ;

6. 更新每种排序策略  对应的  ： = ，其中  。输出  ， ;

建立树结构的伪代码如图2：

图2 CatBoost树模型伪代码

4.4 CatBoost完整建模过程

CatBoosts 输入：

• ：训练集；
• ：循环数；
• ：步长；
• ：损失函数；
• ：排序的个数；
• Mode ：模式
• 其中真实排序个数为  个，  ,...,  用于计算 Oredered TS，这些 TS 进一步用于分割结点的选择，从而固定树模型的结构。  用于计算叶子结点的值 （详见公式 (8)）。

CatBoosts 建模步骤：

1. 设置  个不同的样本排序方式，  ,...,  ；
2. 初始化用于计算叶子结点取值的模型  ,...,  ；
3. 在第  次循环中，使用  建立树结构  ，并更新  ，  ；
4. 使用排序  计算 Ordered TS，并基于树  确定每个样本所属的叶子结点；
5. 基于样本排序  以及模型  ，估计每一个样本点的梯度值；
6. 对于  上每一个叶子结点，计算叶子结点的值  ，即所有属于该叶子点的样本的负梯度均值；
7. 更新  ， = ，其中  ；

CatBoost建模的伪代码如图3：

图3 CatBoost伪代码

为了便于理解，其中的  可换成 。使用  的目的是提升模型预测速度（详见4.6）。

4.5 对Oredered Boosting的改进

如上述伪代码中所示，CatBoost 算法有两种模式 (Mode) ， Plain 和 Ordered 。 Plain 与标准 GBDT 算法相似，只是在计算过程中使用内置的 Oredered TS 方法对类别型特征进行转化，而不需要人为对类别型特征进行加工。Ordered 模式则是对 Ordered Boosting 的改进，即在计算梯度值时，使用了 Ordered Boosting 中对梯度进行无偏估计的方法。

算法中，  ,...,  的计算方法是相同的，区别在于基于的样本排序  不同。 CatBoost 在每次迭代都随机抽取一个排序进行树的建立，并对所有  同步更新，降低了 Ordered Boosting 中不同排序对于模型预测结果的影响，增强了模型的泛化能力。

4.6 快速预测

在树的结构上， CatBoost 采用对称树（Oblivious Decision Tree），即在树的同一层的节点上都采用相同的分割标准。这种对称树能够有效避免过拟合，同时能够显著提升测试效率。

同时，在实际运算中（如图3），为了降低运算复杂度， CatBoost 使用的是前  个样本建立的模型  进行估计，而非之前伪代码中的  个。这部分伪代码详见论文 (CatBoost: unbiased boosting with categorical features) 的附件 B。

五、Python实践案例

CatBoost 库^[5] 既可以解决分类问题 (CatBoostClassifier) ，也可以解决回归问题 (CatBoostRegressor) 。本文将以分类问题为例，数据采用UCI 数据库中的 Adult 数据集^[6]。

该数据集抽取自 1994 年人口普查数据，包含 14 个特征变量和 1 个目标变量，目标是预测样本的年收入是否大于 5 万美金。数据集中已提供训练集 (adult.data) 和测试集 (adult.test) 。

首先，导入 Catboost 库、CatBoostClassifier 分类器，并读取数据:

import numpy as np
import pandas as pd
from catboost import CatBoostClassifier
## 读取数据
train_set = pd.read_csv('adult_data.csv',na_values='?',encoding = 'gbk')
test_set = pd.read_csv('adult_test.csv',na_values='?',encoding = 'gbk')


查看数据train_set.shape，test_set.shape可以得知测试集包含32561个样本，测试集包含16281条样本 (图4)：

图4 train_set

其中education-num使用数字编码代替了对应的学历，与education是一一对应的，本文在建模时就将此列删掉了。

#将目标变量转化为数值型
train_set['salary'] = train_set['salary'].astype('category').cat.codes
test_set['salary'] = test_set['salary'].astype('category').cat.codes
#将数据集分为特征变量和目标变量
train_labels = train_set['salary']
train_data = train_set.drop(['salary','education-num'],axis = 1)
test_labels = test_set['salary']
test_data = test_set.drop(['salary','education-num'],axis = 1)

看一下各变量的数据类型train_data.dtypes，（如图 5）可以看出特征变量既有数值型，也有类别型:

图5 特征的数据类型

可以看出，我们没有手动处理任何类别型特征。CatBoost 可以直接处理缺失的特征以及类别型特征，我们只需告知分类器哪些维度是类别维度。

##提取类别型特征的index
categorical_features= np.where(train_data.dtypes != np.int64)[0]
##使用训练集对模型进行拟合
model = CatBoostClassifier(loss_function='Logloss')
model.fit(train_data, np.ravel(train_labels), cat_features)


将模型应用于测试集，检验模型预测效果：

result = model.predict(test_data)
print('error:',1-np.mean(result==np.ravel(test_labels)))

在没有进行调参的情况下，CatBoost 分类的错误率为12%（在训练集上的预测错误率为11%）。

六、总结

CatBoost 能够直接处理类别型特征，同时提升了预测精度，具有较强的泛化性及较低的时间复杂度，还能兼顾分类问题与回归问题，是一种非常强大的算法。

对 Boosting 算法感兴趣的读者可以自己尝试用 CatBoost 解决回归问题，在本专题后续的文章中还会与大家分享 CatBoost 算法的调优以及 CatBoost 与其它 GBDT 算法的效果对比。

参考资料

[1]

CatBoost: unbiased boosting with categorical features: https:///abs/1706.09516v2

[2]

XGBoost: https://xgboost./en/latest/

[3]

LightBGM: https://www.microsoft.com/en-us/research/project/lightgbm/

[4]

百度百科-牛顿迭代法: https://baike.baidu.com/item/%E7%89%9B%E9%A1%BF%E8%BF%AD%E4%BB%A3%E6%B3%95/10887580?fr=aladdin

[5]

CatBoost: https:///project/catboost

[6]

Adult: https://archive.ics./ml/datasets/Adult

我们是光大科技公司的追光实验室团队，将不定期推出数据挖掘和算法相关的数据科学原创文章。团队定位打造基于知识驱动的机器学习实验室，由实践经验丰富的数据分析挖掘工程师和专注算法的数据科学家精心准备相关作品，志在分享结合实际业务的理论应用和算法创新，以及其中的心得体会。