#paper DOI: 10.1145/2939672.2939785，XGBoost: A Scalable Tree Boosting System 陈天奇这篇论文是16年在KDD上提出的，目前在树模型有更快更强的LightGBM，也有魔改catboost。大忙但是我们想要找到从GBDT到更快更强的树模型，还是要从这篇XGBoost开始。 XGBoost算法的在性能，速度方面都超越了其他算法。之所以这么好，主要得益于以下几个方面： 是一个基于多个弱分类器组成的模型，可以有降低防过拟合的风险。 提出了一种加权分桶，减少计算量。 对稀疏数据进行默认划分，减少计算量。 对内存的优化和做了并行化处理、 对CPU缓存的优化 对存储的优化 1. 正则化的目标函数来看，XGBoost 是一种加法模型，它包含多个个基学习器，每个基学习器可以选择 CART 或者线性函数，损失函数包含损失函数和正则项，防止过拟合。 2. 二阶泰勒展开求解来看，在求得使得目标函数最小化时，可以像 GBDT 一样计算目标函数梯度，然后让新的 CART 去拟合负梯度。不过 XGBoost 用了更优的方法，有点类似牛顿法，但又不完全一样。牛顿法是把目标函数在当前点做二阶泰勒展开，然后求解二次方程最优点。而 XGBoost 是在上一步处只对损失函数这项做了二阶泰勒展开，之后再求解最优点。 3. 缩减（shrinkage）和列抽样：这里的缩减和 GBDT 里的缩减一样，都是为了降低单棵树的影响，给后面的树留有空间。因此引入一个学习率，用它去乘每步生成的目标函数。列抽样在 GBDT 和随机森林里都有用到，它可以牺牲偏差来降低方差。实现方法就是在分裂节点的时候只用一部分特征。 4.树节点分裂：节点分裂的目标是找出一个特征，按照这个特征的某个节点分裂后，能够使目标函数降低最多。所以这里面有两层循环，外层是特征遍历，内层是特征值遍历。特征遍历没得说了，只能一个一个找，但是特征值遍历可以优化一些，缩短寻找最优分裂节点的耗时。 5. 稀疏感知：机器学习经常会碰到数据稀疏的问题，有三种情况会导致数据稀疏：1.数据存在大量缺失值2.数据中存在大量的 0 元素3.特征工程中使用了 one-hot 编码，产生了大量的 0；所以让算法能够感知数据的稀疏模式是非常重要的。XGBoost 的解决方法是在每个节点中设置一个默认方向，缺失值或者 0 元素直接走默认方向，不参与树模型的学习。 6.效率优化之分块并行：决策树学习过程中，最耗时的部分是分裂时对数据的反复排序。为了提高速度，XGBoost 用了空间换时间的方法。对于一列特征，它创建了等量的指针，每个指针都跟一个特征值绑定，采并指向对应样本，按照特征大小排序，把每一个特征的排好序的指针保存在块结构中，就实现了训练前对特征排序的目标，这样速度提升了，但是也因此需要额外空间存储指针。分条来说，块结构的设计有以下特点：1.采用 CSC（Compressed Sparse Column Format）这种稀疏格式存储数据 2.存储的特征已排好序。3.存储了指向样本的指针，因为要存取一阶导和二阶导等信息。4.由于 CSC 是按列存储的，所以可以在每次分裂时对特征使用多线程并行计算 7.缓存感知（Cache-aware）访问：提出的块结构能够优化节点分裂的时间复杂度，但是在索引样本时，存在对内存的非连续访问问题。这是因为我们是按特征大小顺序对样本进行访问，但样本不按这个顺序。对内存的非连续访问将降低 CPU 的缓存命中率。XGBoost 针对精准贪心算法和近似算法设计了两种不同的优化策略。 8.块的核外（Out-of-core）计算：当数据没办法被一次全部读入内存时，就需要用到核外计算方法，单开一个线程从硬盘上读取需要用到的数据，解决内存不够地问题。但是从硬盘读取数据相对于处理器来说是很慢的，所以 XGBoost 采用了两种方法平衡两者速度：块压缩。对于行索引，用当前索引减去开始的块索引，前面提到块大小为所以用 16 位的整数存储这个算出来的偏移，用这个偏移替代原先更占空间的索引。块分片。把数据分开存储到不同的硬盘上，等用的时候多个硬盘一起开工，提高读取速度。