软件学报

作者：江佳伟,符芳诚,邵蓥侠,崔斌

单位：江佳伟，高可信软件技术教育部重点实验室(北京大学), 北京 10087111,符芳诚，高可信软件技术教育部重点实验室(北京大学), 北京 10087102,邵蓥侠，北京邮电大学 计算机学院, 北京 10087603,崔斌，高可信软件技术教育部重点实验室(北京大学), 北京 10087104

关键词：梯度提升树;数据并行;特征并行;系统实现;算法比较

基金：国家自然科学基金（61832001，61702015，61702016）；国家重点研发计划（2018YFB1004403）

梯度提升树算法由于其高准确率和可解释性，被广泛地应用于分类、回归、排序等各类问题.随着数据规模的爆炸式增长，分布式梯度提升树算法成为研究热点.虽然目前已有一系列分布式梯度提升树算法的实现，但是它们在高维特征和多分类任务上性能较差，原因是它们采用的数据并行策略需要传输梯度直方图，而高维特征和多分类情况下梯度直方图的传输成为性能瓶颈.针对这个问题，研究更加适合高维特征和多分类的梯度提升树的并行策略，具有重要的意义和价值.首先比较了数据并行与特征并行策略，从理论上证明特征并行更加适合高维和多分类场景.根据理论分析的结果，提出了一种特征并行的分布式梯度提升树算法FP-GBDT.FP-GBDT设计了一种高效的分布式数据集转置算法，将原本按行切分的数据集转换为按列切分的数据表征；在建立梯度直方图时，FP-GBDT使用一种稀疏感知的方法来加快梯度直方图的建立；在分裂树节点时，FP-GBDT设计了一种比特图压缩的方法来传输数据样本的位置信息，从而减少通信开销.通过详尽的实验，对比了不同并行策略下分布式梯度提升树算法的性能，首先验证了FP-GBDT提出的多种优化方法的有效性；然后比较了FP-GBDT与XGBoost的性能，在多个数据集上验证了FP-GBDT在高维特征和多分类场景下的有效性，取得了最高6倍的性能提升.

来源：2019年第3期

《软件学报》期刊编辑部

查看软件学报杂志2019年第3期