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

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

对决策树连续值找分割点的算法的改进

分类问题是数据研发领域里研究和使用最广泛的技术之一。近几年经济的飞速发展,分类问题在多行业和领域中被广泛使用,那么,怎样更准确、更有效地分类呢?这是多数研究工作人员的目标。决策树(decision tree)以条理清晰,程序严谨,定量、定性分析相结合,方法通俗易懂,容易掌握,应用性较强等优点,被广泛应用。现在构造决策树的算法比较多,如:ID3算法、C4.5算法、CART等。C4.5算法是在ID3算法的基础上进行改进的,C4.5算法选用信息增益率(Info Gain Ratio)为择取分枝属性的标准,此方法弥补了ID3算法在运用信息增益择取分枝属性时偏向于取值较多的属性的不足之处,但是C4.5算法也有部分缺陷,本文主要在其处理连续属性比较耗时问题上进行深入探讨,本文对其连续的处理过程进行改进来提高C4.5算法的计算效率,大大缩短算法用时。