CatBoost: unbiased boosting with categorical features.

paper：CatBoost: unbiased boosting with categorical features

CatBoost (Categorical Boosting)是一种把对称决策树 (oblivious tree)作为基学习器的梯度提升决策树GBDT方法，通过顺序生成基学习器构造强学习器。CatBoost能够有效地处理类别型特征，并解决了梯度偏差 (Gradient Bias)导致的预测偏移 (Prediction shift)的问题，减少过拟合的发生。CatBoost的主要优点是：

自动将类别型特征处理为数值型特征；
能够组合类别型特征，丰富了特征维度；
采用排序提升方法避免梯度估计的偏差，解决预测偏移问题。

CatBoost的主要缺点是对于类别型特征的处理需要大量的内存和时间。

XGBoost, LightGBM和CatBoost对类别特征的接受程度对比如下：

XGBoost：无法处理类别型特征，数据预处理时必须把类别型特征转换为序号编码、独热编码或二进制编码。
LightGBM：可以处理类别型特征，但需要将类别型特征变量转化为整型变量，不允许传递字符串数据。
CatBoost：能够自动将类别型特征处理为数值型特征，也可以通过传入类别型特征的列标识来使用One-hot编码。

1. 类别型特征 Categorical features

类别型特征是指特征的取值是离散的集合，比如省份名（山东、山西、河北等），城市名（北京、上海、深圳等）。在梯度提升算法中，通常把这些类别型特征转为数值型来处理。

对于特征基数比较低 (low-cardinality)的类别特征，即该特征的所有取值去重后构成的集合元素个数比较少，一般利用One-hot编码方法将特征转为数值型。One-hot编码可以在数据预处理时完成，也可以在模型训练时完成；从训练时间的角度，后一种方法的实现更为高效，CatBoost对于基数较低的类别型特征采用后一种实现。

对于高基数(high-cardinality)类别型特征，比如用户ID，One-hot编码方式会产生大量新的特征，造成维度灾难。CatBoost把这种类别特征转换成目标变量统计量(Target Statistics)，目标变量统计量用于估算每个类别的目标变量的期望值，并作为一个新的数值型变量来代替原来的类别型变量。

最简单的目标变量统计量的形式是对应标签的平均值：

\[\hat{x}_k^i = \frac{\sum_{j=1}^N[x_{j,k} = x_{i,k}] \cdot Y_i}{\sum_{j=1}^N[x_{j,k} = x_{i,k}]}\]

把标签平均值将作为节点分裂标准的方法被称为Greedy Target-based Statistics。这种方法的缺陷是，由于通常特征比标签包含更多的信息，如果强行用标签的平均值来表示特征的话，当训练数据集和测试数据集数据结构和分布不一样的时候会出条件偏移问题。

对标签平均值添加先验分布项，可以减少噪声和低频率类别型数据对于数据分布的影响：

\[\hat{x}_k^i = \frac{\sum_{j=1}^N[x_{j,k} = x_{i,k}] \cdot Y_i + a \cdot p}{\sum_{j=1}^N[x_{j,k} = x_{i,k}]+a}\]

其中$p$是添加的先验项。对于回归问题，先验项可取数据集标签的均值；对于二分类问题，先验项可取正样本的先验概率。

CatBoost每次随机选取一部分数据计算统计量，这一策略要求同一标签数据不能排列在一起（即先全是$0$之后全是$1$这种方式），训练之前需要打乱数据集。CatBoost构造数据集的$4$个不同排列，在每一轮建立树时随机选择一种排列计算目标变量统计量。

多个类别型特征的任意组合都可视为新的特征，并且可以得到一个新的强大的特征。然而组合的数量会随着数据集中类别型特征的数量成指数增长，因此不能在算法中考虑所有组合。为当前树构造新的分割点时，CatBoost采用贪婪的策略考虑组合：在选择第一个节点时，只考虑选择一个特征，例如A；在生成第二个节点时，考虑A和其余任意一个类别特征的组合，并选择其中最好的。CatBoost还可以生成数值型特征和类别型特征的组合：把树中选定的所有分割点视为具有两个值的类别型特征，并像类别型特征一样进行组合。

CatBoost处理类别型特征的总结：

通过添加先验分布项的目标变量统计量把类别型特征转换为数值型特征；
采用贪婪的策略考虑类别特征的组合。

2. 排序提升 Ordered boosting

CatBoost通过构建新的树来拟合当前模型损失函数的负梯度，这是一种有偏的点态梯度估计，容易引起过拟合问题。这是因为在每轮迭代中使用的梯度都是通过固定的训练数据集来估计的，这导致估计的梯度分布与数据域中梯度的真实分布相比具有梯度偏差(Gradient Bias)，并导致预测偏移(Prediction shift)，即当测试集的数据分布发生偏移时，预测结果也不可靠。

为了克服预测偏移问题，CatBoost提出了一种排序提升(Ordered boosting)算法，即在选择最佳的树结构时采用梯度步长的无偏估计。为了计算无偏估计，对每个样本$(X_i,Y_i)$训练一个单独的树模型$M_i$，模型$M_i$由使用不包含样本$(X_i,Y_i)$的训练集训练得到。然后使用模型$M_i$来得到样本$(X_i,Y_i)$的梯度估计，并使用该梯度来训练基学习器并得到最终的模型。

排序提升算法在大部分实际任务中都不具备使用价值，因为需要训练$N$个不同的模型，大大增加了内存消耗和时间复杂度。构建一棵树分为两个阶段：选择树结构和在树结构固定后计算叶结点的值。CatBoost主要在第一阶段进行优化。

3. 快速训练

对称树 (oblivious tree)：CatBoost使用对称树作为基学习器。在对称树中，相同的分割准则可以同时在树的某一层上使用。具体地，每个叶结点的索引可以被编码为长度等于树深度的二进制向量，然后将所有特征进行二值化，来计算模型预测值。
密集的数值特征：对于密集的数值特征数据集，CatBoost将特征离散化到固定数量的箱子中以减少内存使用，并利用了一种不依赖于原子操作的直方图计算方法。
类别型特征：CatBoost使用完美哈希来存储类别型特征的值，以减少内存使用。由于GPU内存的限制，在CPU RAM中存储按位压缩的完美哈希，以及要求的数据流、重叠计算和内存等操作。通过哈希来观察分组，在每个组中需要计算一些统计量的前缀和，该统计量的计算使用分段扫描GPU图元实现。
多GPU支持：CatBoost可支持多个GPU，分布式树学习可以通过数据或特征进行并行化。

4. CatBoost的代码实现

pip install catboost

catboost库中定义的CatBoost模型的主要参数可以查阅catboost文档。

本节以kaggle竞赛中的2015年航班延误数据集为例，介绍使用CatBoost进行回归的方法。

该数据集一共有约$500$万条记录，此处使用了$1\%$的数据：$5$万行记录，其中同时包含类别型变量和数值变量。以下是建模使用的特征：

月、日、星期：整型数据
航线或航班号：整型数据
出发、到达机场：数值数据
出发时间：浮点数据
距离和飞行时间：浮点数据
到达延误情况：这个特征作为预测目标，并通过航班是否延误超过$10$分钟转为二值变量

数据集的预处理过程为：

import pandas as pd, numpy as np
from sklearn.model_selection import train_test_split

# 一共有约500万条记录，从中随机抽取1%的记录
data = pd.read_csv("flight-delays/flights.csv")
data = data.sample(frac=0.01, random_state=10)
data.to_csv("flight-delays/min_flights.csv")

# 读取数据
data = pd.read_csv("flight-delays/min_flights.csv")
print(data.shape)  # (58191, 31)

data = data[["MONTH", "DAY", "DAY_OF_WEEK", "AIRLINE", "FLIGHT_NUMBER", "DESTINATION_AIRPORT",
             "ORIGIN_AIRPORT", "AIR_TIME", "DEPARTURE_TIME", "DISTANCE", "ARRIVAL_DELAY"]]
data.dropna(inplace=True)

# 延误情况设置为预测变量并二值化
data["ARRIVAL_DELAY"] = (data["ARRIVAL_DELAY"] > 10) * 1

# 把航线、航班号、出发、到达机场设置为类别型数据
cols = ["AIRLINE", "FLIGHT_NUMBER", "DESTINATION_AIRPORT", "ORIGIN_AIRPORT"]
for item in cols:
    data[item] = data[item].astype("category").cat.codes + 1

# 划分训练集和测试集
train, test, y_train, y_test = train_test_split(
    data.drop(["ARRIVAL_DELAY"], axis=1),
    data["ARRIVAL_DELAY"],
    random_state=10, test_size=0.25)

# 记录类别型数据的索引号
cat_features_index = [0, 1, 2, 3, 4, 5, 6]

在CatBoost中，必须对变量进行声明，才可以让算法将其作为类别型变量处理。如果未在cat_features参数中传递任何内容，CatBoost会将所有列视为数值变量，此时如果某一列数据中包含字符串值，算法就会抛出错误。另外带有默认值的整型变量也会被当成数值数据处理。

在对CatBoost调参时，很难对类别型特征赋予评估指标。因此调参过程应该对模型不传递类别型特征，此时可以通过sklearn库用网格搜索调出最优超参数：

from sklearn.model_selection import GridSearchCV
import catboost as cb

# 调参，用网格搜索调出最优参数
params = {'depth': [4, 7, 10],
          'learning_rate': [0.03, 0.1, 0.15],
          'l2_leaf_reg': [1, 4, 9],
          'iterations': [300, 500]}
cb = cb.CatBoostClassifier()
cb_model = GridSearchCV(cb, params, scoring="roc_auc", cv=3)
cb_model.fit(train, y_train)
# 查看最佳分数
print(cb_model.best_score_)  # 0.7088001891107445
# 查看最佳参数
print(cb_model.best_params_)  # {'depth': 4, 'iterations': 500, 'l2_leaf_reg': 9, 'learning_rate': 0.15}

根据最优参数，可以向CatBoost模型中直接传入类别型特征的列标识，模型会自动将其使用One-hot编码，还可通过设置 one_hot_max_size参数来限制One-hot特征向量的长度。

from sklearn import metrics

# With Categorical features
clf = cb.CatBoostClassifier(
    eval_metric="AUC", one_hot_max_size=31,
    depth=4, iterations=500,
    l2_leaf_reg=9, learning_rate=0.15)
clf.fit(train, y_train, cat_features=cat_features_index)

print(metrics.roc_auc_score(y_train, m.predict_proba(train)[:, 1])  # 0.7817912095285117
print(metrics.roc_auc_score(y_test, m.predict_proba(test)[:, 1])  # 0.7152541135019913

类似地，使用CatBoost模型进行回归的过程为：

from catboost import CatBoostRegressor

# Initialize CatBoostRegressor
model = CatBoostRegressor(iterations=2,
                          learning_rate=1,
                          depth=2)
# Fit model
model.fit(train_data, train_labels)
# Get predictions
preds = model.predict(eval_data)
print(preds)