【作者】 杨碧姗； 王腾蛟； 常雷； 杨冬青； 唐世渭；

【Author】 Yang Bishan,Wang Tengjiao,Chang Lei,Yang Dongqing,and Tang Shiwei (Joint Laboratory of Mobile Communication Data Warehouse,School of Electronics Engineering and Computer Science,Peking University,Beijing 100871)

【机构】 北京大学信息科学技术学院移动通信数据仓库联合实验室；

【摘要】 ADTree是一种基于boosting的决策树学习算法,其预测准确率比一般决策树高并可以给出预测置信度,在实际中有广泛的应用.已有的ADTree构建算法能有效地处理小规模数据,但对于大规模数据的处理非常低效.因此提出了一种新的ADTree构建算法——BICA(bottom-up induction forconstructing ADTree),设计了新的数据结构和自底向上的归纳方法,并将其结合到ADTree建树过程中,能够快速地进行分裂测试评估,从而有效地提高ADTree的构建效率.实验证明,BICA对大规模数据集的处理效率明显优于已有ADTree构建算法,能够进行高效的处理.更多还原

【Abstract】 Alternating decision tree(ADTree) is a decision tree algorithm based on boosting.ADTree has a wide range of applications,because it can attain a more accurate hypothesis than other general decision tree algorithms and output confidence-rated predictions.While the existing ADTree constructing algorithm is effective on small datasets,it shows low efficiency on large ones.So a new scalable algorithm for constructing ADTree—BICA(bottom-up induction for constructing ADTree) is proposed.By using a new data structure AVW-set and a bottom-up induction approach,BICA can reduce much sorting cost and cache some of the statistics that will be recomputed over and over again,thus it can evaluate split tests very quickly and enhance the efficiency of ADTree construction obviously.Experiment results show that BICA outperforms the existing ADTree constructing algorithm by a large margin and achieves high performance on handling massive training data.更多还原