面向高维特征和多分类的分布式梯度提升树

作     者：江佳伟 符芳诚 邵蓥侠 崔斌 JIANG Jia-Wei;FU Fang-Cheng;SHAO Ying-Xia;CUI Bin

作者机构：高可信软件技术教育部重点实验室(北京大学)北京100871 北京邮电大学计算机学院北京100876 

基　　金：国家自然科学基金(61832001 61702015 61702016) 国家重点研发计划(2018YFB1004403)~~ 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2019年第30卷第3期

页      码：784-798页

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

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

学科分类：08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.13328/j.cnki.jos.005690

馆 藏 号：203607285...