决策树相关算法——XGBoost原理分析及实例实现(二)

1前言

本篇博客主要记录的是XGBoost在构建决策树结构时,知道如何评定划分点的好坏的情况下,如何遍历查找出该树结构的切分点。前篇博客决策树相关算法——XGBoost原理分析及实例实现(一)介绍的是贪心查找算法,逐步遍历特征和特征取值,比较切分前后的平方误差的大小,获得最佳切分点。本篇主要介绍的是近视查找算法和稀疏感知的划分查找。

2要说的话

我们知道决策树中的ID3算法和C4.5或者是CART分类回归树的构造过程中都是有一个切分评价标准,ID3进行特征选择的是信息增益,C4.5是信息增益率。而CART分类树构造的切分点是根据选择的特征和特征值的Gini系数进行对比。CART回归树是根据切分点后的平方误差进行评价的。我们的XGBoost的决策树构建过程中切分点的选择是根据代价函数(代价函数可以是任意的一般函数)的化简值——如下图所示。具体化简过程参照上篇博客
图8

3近似查找算法(Approximate Algorithm)

原因: 完全贪心算法,贪婪的遍历所有的切分点,当所有的数据点不能全部加载到内存时,算法就会变的低效。同时在XGBoost分布式学习时也会遇到这样的问题。所以此时需要一些近似算法来获取切分点列表。
XGBoost中的近似方法框架
图18
算法讲解: 前面一个for循环做的工作是,对特征K根据该特征分布的分位数找到切割点的候选集合Sk={sk1,sk2,...,skl},这样做的目的是提取出部分的切分点不用遍历所有的切分点。其中获取某个特征K的候选切割点的方式叫proposal.主要有两种proposal方式:global proposallocal proposal.
第二个for循环的工作是,将每个特征的取值映射到由这些该特征对应的候选点集划分的分桶(buckets)区间{skv≥xjk>skv−1}中,对每个桶(区间)内的样本统计值G、H进行累加统计,最后在这些累计的统计量上寻找最佳分裂点。这样做的主要目的是获取每个特征的候选分割点的G和H量。
存在的疑惑——后面会讲解:

问题1.如何根据特征分布的分位数挑选出候选点集??
问题2.global proposallocal proposal有什么不同??

3.1分位点(quantile)介绍

举例子说明,一般来说对于一个数据列表有:
图24
ϕ−quantile表示rank=⌊ϕ−quantile×N⌋的元素
我们需要取出0.25-quantile(0.25分位点的数),即取出rank为0.25*N的数。

3.2加权分位点(Weighted quantile)介绍

举例子说明,一般来说对于一个数据列表有,取元素的方法为,指定rank(大于0小于1)即可,0.5分位点的元素为3:
图25

3.3分位数缩略图(Quantile Sketch)

原因: 当一个序列无法全部加载到内存时,常常采用分位数缩略图近似的计算分位点来近似获取特定的查询。
方式:使用随机映射(Random projections)将数据流投射在一个小的存储空间内作为整个数据流的概要,这个小空间存储的概要数据称为略图,可用于近似回答特定的查询。需要保留原序列中的最小值和最大值。

3.4近似算法中的分位数缩略图(Weighted Quantile Sketch)

此部分便是讲述疑惑中的问题1:如何根据特征分布的分位数挑选出候选点集???
通常,一个特征的百分位数可以被用来让候选在数据上进行均匀地分布。我们用一个multi-set: Dk=(x1k,h1),(x2k,h2),…(xnk,hn),来表示每个训练实例的第k个特征值以及它的二阶梯度值统计。其中hi表示i个实例的第k个特征值对应的二阶梯度值统计,可看作i个实例的第k个特征值的权重。至于为什么可以看作是权重作为疑惑问题3后面会提到。
如下示例有:
图26
一般来说对于加权分位数缩略图的取值是根据Rank的值进行的,Rank计算公式为:
图20
Rank函数,输入为某个特征值z,计算的是该特征所有可取值中小于z的特征值的总权重占总的所有可取值的总权重和的比例,输出为一个比例值。于是我们就能用下面这个不等式来寻找候选分离点{sk1,sk2,sk3,⋅,⋅,skl}
图21
其中sk1是特征k的取值中最小的值xik,其中skl是特征k的取值中最大的值xik,这是分位数缩略图的要求需要保留原序列中的最小值和最大值。ϵ是一个近似比例,或者说是扫描步幅。可以理解为在特征K的取值范围上,按照步幅ϵ挑选出特征K的取值候选点,组成候选点集。起初是从sk1起,每次增加ϵ∗(skl−sk1)作为候选点,加入到候选集中。如此计算的话,这意味着大约是 1/ϵ个候选点。
此时特征k的取值中最小的值xik和特征k的取值中最大的值xik来自的数据集Dk,对于Dk的数据集有两种定义,一种是一开始选好,然后每次树切分都不变,也就是说是在总体样本里选最大值skl和最小值sk1,这就是我们之前定义的global proposal。另外一种是树每次确定好切分点的分割后样本也需要进行分割,最大值skl和最小值sk1来自子树的样本集Dk,这就是local proposal
疑惑问题3,对于特征K的取值为什么权权可以表示为hi为二阶梯度的值?
首先,将代价函数公式进行转换:
图27
最后的代价函数就是一个加权平方误差,权值为hi,labels为-gi/hi.所以可以将特征K的取值的权重看成对应的hi
分布式加权分位数缩略图:对于需要并行的获取候选集切割点,需要使用分布式加权分位数缩略图,必须包含两个操作m合并erge和修剪prune。分布式加权分位数缩略图具体如何操作需要查看论文XGBoost: A Scalable Tree Boosting System附录1.

4稀疏感知的划分查找算法(Sparsity-aware Split Finding)

数据集稀疏的原因:1.样本中的部分数据缺失。2.统计中过多的 zero entries。3.特征工程中的one-hot encoding。
于是XGBoost中提出了稀疏感知的划分查找算法,如下:
图19
如下为带缺省方向的树结构。当在split时相应的feature值缺失时,一个样本可以被归类到缺省方向上。
图28
大体思想流程是:在每个树节点上增加一个缺省的方向(default direction),如上图所示,当稀疏矩阵x中的某个特征值缺失时,该样本实例被归类到缺省方向上。默认的缺省方向有两种,一个是左分支和右分支。XGBoost指定的默认缺省方向是从数据中学习到的,并不是随机指定的。
稀疏感知的划分查找算法的理解:至于缺省值的实例分到哪个分支方向,如何学习的问题,稀疏感知的划分查找算法计算切分后的评判标准(公式六)时只关注没有缺失的条目Ik.然后再通过将实例以枚举的方式,枚举项为默认分到左分支和默认分到右分支,计算切分前后相差最大的Score,然后将缺失值的实例分到该分支上。

5总结

1.传统的GBDT是以CART作为基分类器,XGBoost支持其他分类器。
2.XGBoost是带着代价函数的正则化进行切分查找,易于防止过拟合。
3.XGBoost的决策树的生成过程是先确定好每个叶子的权重,再寻找切割点来构造树结构。

6参考链接

xgboost之分位点算法
决策树相关算法——XGBoost原理分析及实例实现(一)
XGBoost: A Scalable Tree Boosting System

-------------本文结束感谢您的阅读-------------

本文标题:决策树相关算法——XGBoost原理分析及实例实现(二)

文章作者:ComeOnJian

发布时间:2018年04月27日 - 11:04

最后更新:2018年04月28日 - 19:04

原始链接:https://jianwenjun.xyz/2018/04/27/决策树相关算法——XGBoost原理分析及实例实现-二/

许可协议: 转载请保留原文链接及作者。

显示 Gitment 评论