您现在的位置是:海之睿健康网 > 血hCG检查数据解读 > XGBoost解读

XGBoost解读

时间:2018-09-29 13:45  来源:未知  阅读次数:138 复制分享 我要评论

  XGBoost是陈天奇在博士期间研究成果,近年来也是数据挖掘比赛的一大神器,几乎任何比赛都会使用。

  Xgboost是GBDT算法的高效实现,xgboost中的基学习器除了可以是CART(gbtree)也可以是线性分类器(gblinear)。下面所有的内容来自原始paper,包括公式。

  (1). xgboost在目标函数中显示的加上了正则化项,基学习器为CART时,正则化项与树的叶子节点的数量T和叶子节点的权值有关。

  (2). GBDT中使用Loss Function对f(x)的一阶导数计算出伪残差用于学习生成fm(x),xgboost不仅使用到了一阶导数,还使用二阶导数。

  第t次的loss:

  对上式做二阶泰勒展开:g为一阶导数,h为二阶导数

  (3). 上面提到CART回归树中寻找最佳分割点的衡量标准是最小化均方差,xgboost寻找分割点的标准是最大化,lamda,gama与正则化项相关

  xgboost与gdbt除了上述三点的不同,xgboost在实现时还做了许多优化:

  在寻找最佳分割点时,考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低,xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者,然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。xgboost考虑了训练数据为稀疏值的情况,可以为缺失值或者指定的值指定分支的默认方向,这能大大提升算法的效率,paper提到50倍。特征列排序后以块的形式存储在内存中,在迭代中可以重复使用;虽然boosting算法迭代必须串行,但是在处理每个特征列时可以做到并行。按照特征列方式存储能优化寻找最佳的分割点,但是当以行计算梯度数据时会导致内存的不连续访问,严重时会导致cache miss,降低算法效率。paper中提到,可先将数据收集到线程内部的buffer,然后再计算,提高算法的效率。xgboost 还考虑了当数据量比较大,内存不够时怎么有效的使用磁盘,主要是结合多线程、数据压缩、分片的方法,尽可能的提高算法的效率。

相关内容