基于SPMD的C4.5并行决策树加速分析

来源：计算机技术与发展杂志2015年第01期北京时间：

作者：张莹;毕卓

摘要：决策树分类方法是解决数据挖掘、模式识别中分类任务的有效方法，然而，在大规模的数据集上运行时，其运行效率受到严重影响。文中选取决策树的代表算法C4.5算法为研究对象，利用算法固有的并行性对其进行优化研究。文中利用MATLAB实现串行的C4.5决策树，并对构成该决策树的子函数进行运行时间分析，从而确定信息增益率计算的复杂性为限制算法速度的关键因素。针对此计算瓶颈，结合决策树算法在子节点分割以及最优分裂属性选择等方面的并行性，纵向划分数据，构建了并行的C4.5决策树，并利用MATLAB并行计算池功能以及SPMD设计实现。对并行后决策树运行时间验证结果表明，将C4.5决策树并行化后，并行决策树的构建时间显著缩短，实现了算法的加速。

关键词：C4. 5;并行;决策树;MATLAB