CatBoost之算法解析（Kaggle常用模型）
catboost 简介
CatBoost据说是超越LightGBM和XGBoost的一大神器。
catboos的三个贡献点
- 它自动采用特殊的方式处理类别型特征（categorical features）。首先对categorical features做一些统计，计算某个类别特征（category）出现的频率，之后加上超参数，生成新的数值型特征（numerical features）。这也是我在这里介绍这个算法最大的motivtion，有了catboost，再也不用手动处理类别型特征了。
- catboost还使用了组合类别特征，可以利用到特征之间的联系，这极大的丰富了特征维度。
- catboost的基模型采用的是对称树，同时计算leaf-value方式和传统的boosting算法也不一样，传统的boosting算法计算的是平均数，而catboost在这方面做了优化采用了其他的算法，这些改进都能防止模型过拟合。
CatBoost详细内容技术介绍
1、类别型特征的处理
CatBoost采用了一种有效的策略，降低过拟合的同时也保证了全部数据集都可用于学习。也就是对数据集进行随机排列，计算相同类别值的样本的平均标签值时，只是将这个样本之前的样本的标签值纳入计算。
2、特征组合
为当前树构造新的分割点时，CatBoost会采用贪婪的策略考虑组合。对于树的第一次分割，不考虑任何组合。对于下一个分割，CatBoost将当前树的所有组合、类别型特征与数据集中的所有类别型特征相结合。组合被动态地转换为数字。CatBoost还通过以下方式生成数值型特征和类别型特征的组合：树选择的所有分割点都被视为具有两个值的类别型特征，并且组合方式和类别型特征一样。
3、克服梯度偏差
CatBoost，和所有标准梯度提升算法一样，都是通过构建新树来拟合当前模型的梯度。然而，所有经典的提升算法都存在由有偏的点态梯度估计引起的过拟合问题。许多利用GBDT技术的算法（例如，XGBoost、LightGBM），构建一棵树分为两个阶段：选择树结构和在树结构固定后计算叶子节点的值。为了选择最佳的树结构，算法通过枚举不同的分割，用这些分割构建树，对得到的叶子节点中计算值，然后对得到的树计算评分，最后选择最佳的分割。两个阶段叶子节点的值都是被当做梯度或牛顿步长的近似值来计算。CatBoost第一阶段采用梯度步长的无偏估计，第二阶段使用传统的GBDT方案执行。
4、快速评分
CatBoost使用oblivious树作为基本预测器，这种树是平衡的，不太容易过拟合。oblivious树中，每个叶子节点的索引可以被编码为长度等于树深度的二进制向量。CatBoost首先将所有浮点特征、统计信息和独热编码特征进行二值化，然后使用二进制特征来计算模型预测值。
5、基于GPU实现快速学习
5.1 密集的数值特征
任何GBDT算法，对于密集的数值特征数据集来说，搜索最佳分割是建立决策树时的主要计算负担。CatBoost利用oblivious决策树作为基础模型，并将特征离散化到固定数量的箱子中以减少内存使用。就GPU内存使用而言，CatBoost至少与LightGBM一样有效。主要改进之处就是利用了一种不依赖于原子操作的直方图计算方法。
5.2 类别型特征
CatBoost使用完美哈希来存储类别特征的值，以减少内存使用。由于GPU内存的限制，在CPU RAM中存储按位压缩的完美哈希，以及要求的数据流、重叠计算和内存等操作。通过哈希来分组观察。在每个组中，我们需要计算一些统计量的前缀和。该统计量的计算使用分段扫描GPU图元实现。
5.3 多GPU支持
CatBoost中的GPU实现可支持多个GPU。分布式树学习可以通过数据或特征进行并行化。CatBoost采用多个学习数据集排列的计算方案，在训练期间计算分类特征的统计数据。
CatBoost的优点
- 性能卓越：在性能方面可以匹敌任何先进的机器学习算法；
- 鲁棒性/强健性：它减少了对很多超参数调优的需求，并降低了过度拟合的机会，这也使得模型变得更加具有通用性；
- 易于使用：提供与scikit集成的Python接口，以及R和命令行界面；
- 实用：可以处理类别型、数值型特征；可扩展：支持自定义损失函数；
更为详细的一点内容
1、Catboost使用对称树
XGboost一层一层地建立节点，lightGBM一个一个地建立节点，而Catboost总是使用完全二叉树。它的节点是镜像的。Catboost称对称树有利于避免overfit，增加可靠性，并且能大大加速预测等等。
2、它用特殊的方式处理categorical features
首先他们会计算一些数据的statistics。计算某个category出现的频率，加上超参数，生成新的numerical features。这一策略要求同一标签数据不能排列在一起（即先全是0之后全是1这种方式），训练之前需要打乱数据集。第二，使用数据的不同排列（实际上是4个）。在每一轮建立树之前，先扔一轮骰子，决定使用哪个排列来生成树。第三，考虑使用categorical features的不同组合。例如颜色和种类组合起来，可以构成类似于blue dog这样的feature。当需要组合的categorical features变多时，catboost只考虑一部分combinations。在选择第一个节点时，只考虑选择一个feature，例如A。在生成第二个节点时，考虑A和任意一个categorical feature的组合，选择其中最好的。就这样使用贪心算法生成combinations。第四，除非向gender这种维数很小的情况，不建议自己生成one-hot vectors，最好交给算法来处理。
3、catboost和其他算法计算leaf-value的方法不同
传统的boosting使用平均数，但这个估计是有偏的，会导致过拟合。而Catboost则采用另外的计算方法。