Sparsity-aware Split Finding¹

在许多现实问题中，输入xxx是稀疏的是很常见的。造成稀疏性的可能原因有很多:

1)数据中存在缺失值；

2)统计中频繁出现零项；

3)特征工程的处理结果，如独热编码。

重要的是使算法意识到数据中的稀疏模式。为此，在每个树节点上增加一个默认方向，如图所示。当稀疏矩阵x中缺少一个值时，实例将被分类到默认方向。

图中是具有默认方向的树结构。当缺少拆分所需的特征时，示例将被分类到默认方向。

在每个分支中有两个默认方向的选择。从数据中学习最优默认方向。算法如图3所示。关键的改进是只访问未丢失的特征IkI_kIk​。该算法将不存在作为缺失值，并学习处理缺失值的最佳方向。

据我们所知，大多数现有的树学习算法要么只是针对密集数据进行优化，要么需要特定的过程来处理有限的情况，比如分类编码。XGBoost以统一的方式处理所有稀疏模式。更重要的是，我们的方法利用稀疏性使计算复杂度与输入中非缺失项的数量成线性。图5显示了在Allstate-10K数据集上稀疏感知和naive实现的比较(第6节给出了数据集的描述)。我们发现稀疏感知算法比naive版本的运行速度快50倍。这证实了稀疏感知算法的重要性。

图5:稀疏感知算法对Allstate-10K的影响。数据集稀疏主要是由于独热编码。稀疏性感知算法比不考虑稀疏性的原来版本快50倍以上。[]

参考：