论文部分内容阅读
数据挖掘作为知识发现过程关键技术,已逐步得到广泛应用。分类是数据挖掘及CRM的重要组成部分。SLIQ串行算法是由IBM Almaden 研究中心提出的一种高速可伸缩的分类算法,广泛应用于大型商业的CRM、信用等级分级等领域。随着应用中数据量的迅速膨胀,采用并行技术是提高数据挖掘效率的一个重要途径。本文首先分析了串行SLIQ算法的原理和特点,针对其不足提出了一些改进方法,然后在基于PVM的环境下实现了算法的并行化,分析了算法的时间复杂度和加速比,提高了SLIQ算法的效率,具有一定的理论意义和实用价值。串行SLIQ算法通过预排序和广度优先技术,能够更加快速和准确地处理大量数据集,并能同时处理离散字段和连续字段。但是,原算法在计算决策树节点的最佳分割点的时候,存在着对属性和记录的多余计算问题。本文提出应该动态的删除叶子节点的记录以及当前节点的祖先节点的分割属性,从而可以明显地减少不必要的计算以及属性表在磁盘和内存之间的IO交换操作。由于难以解决数据挖掘中任务划分的问题,SLIQ算法并行化的主要方向是实现数据的并行。SLIQ算法采用了新颖的数据结构,需要预先建立属性表,所以应该采取基于属性的数据分割策略。算法在把属性表和类表进行预先分配时采用的是静态平衡策略,对数据的分配按照数据量平均分配,将连续属性和离散属性分别平均分配到各个结点上;在执行分裂后,由于需要计算的属性不断减少,则采用了动态负载平衡的策略,通过消息传递的方式将部分计算任务分配给负载较轻的处理机单元。通过对串行和并行算法时间复杂度的计算表明,当数据集充分大时,由于连续属性的排序计算操作分散到各个处理机单元上进行,显著降低了计算时间,从而可以得到近似于处理机个数的加速比,对于离散属性,本并行算法对串行算法的性能提高有限