潍坊建设厅官方网站,珠海电脑自己建网站,自助广告位网站源码,陕西省二级建造师官网工程实现
块结构设计
我们知道#xff0c;决策树的学习最耗时的一个步骤就是在每次寻找最佳分裂点是都需要对特征的值进行排序。而 XGBoost 在训练之前对根据特征对数据进行了排序#xff0c;然后保存到块结构中#xff0c;并在每个块结构中都采用了稀疏矩阵存储格式…工程实现
块结构设计
我们知道决策树的学习最耗时的一个步骤就是在每次寻找最佳分裂点是都需要对特征的值进行排序。而 XGBoost 在训练之前对根据特征对数据进行了排序然后保存到块结构中并在每个块结构中都采用了稀疏矩阵存储格式Compressed Sparse Columns FormatCSC进行存储后面的训练过程中会重复地使用块结构可以大大减小计算量。
每一个块结构包括一个或多个已经排序好的特征缺失特征值将不进行排序每个特征会存储指向样本梯度统计值的索引方便计算一阶导和二阶导数值
这种块结构存储的特征之间相互独立方便计算机进行并行计算。在对节点进行分裂时需要选择增益最大的特征作为分裂这时各个特征的增益计算可以同时进行这也是 Xgboost 能够实现分布式或者多线程计算的原因。
缓存访问优化算法
块结构的设计可以减少节点分裂时的计算量但特征值通过索引访问样本梯度统计值的设计会导致访问操作的内存空间不连续这样会造成缓存命中率低从而影响到算法的效率。
为了解决缓存命中率低的问题XGBoost 提出了缓存访问优化算法为每个线程分配一个连续的缓存区将需要的梯度信息存放在缓冲区中这样就是实现了非连续空间到连续空间的转换提高了算法效率。
此外适当调整块大小也可以有助于缓存优化。
“核外”块计算
当数据量过大时无法将数据全部加载到内存中只能先将无法加载到内存中的数据暂存到硬盘中直到需要时再进行加载计算而这种操作必然涉及到因内存与硬盘速度不同而造成的资源浪费和性能瓶颈。为了解决这个问题XGBoost 独立一个线程专门用于从硬盘读入数据以实现处理数据和读入数据同时进行。
此外XGBoost 还用了两种方法来降低硬盘读写的开销
块压缩对 Block 进行按列压缩并在读取时进行解压 块拆分将每个块存储到不同的磁盘中从多个磁盘读取可以增加吞吐量。
优点
精度更高GBDT 只用到一阶泰勒展开而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度另一方面也是为了能够自定义损失函数二阶泰勒展开可以近似大量损失函数灵活性更强GBDT 以 CART 作为基分类器XGBoost 不仅支持 CART 还支持线性分类器使用线性分类器的 XGBoost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归分类问题或者线性回归回归问题。此外XGBoost 工具支持自定义损失函数只需函数支持一阶和二阶求导正则化XGBoost 在目标函数中加入了正则项用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差使学习出来的模型更加简单有助于防止过拟合Shrinkage缩减相当于学习速率。XGBoost 在进行完一次迭代后会将叶子节点的权重乘上该系数主要是为了削弱每棵树的影响让后面有更大的学习空间列抽样XGBoost 借鉴了随机森林的做法支持列抽样不仅能降低过拟合还能减少计算缺失值处理XGBoost 采用的稀疏感知算法极大的加快了节点分裂的速度可以并行化操作块结构可以很好的支持并行计算。
缺点
虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量但在节点分裂过程中仍需要遍历数据集预排序过程的空间复杂度过高不仅需要存储特征值还需要存储特征对应样本的梯度统计值的索引相当于消耗了两倍的内存。
