数据挖掘网格中决策树并行算法设计及性能分析

作者：余新华

来源：《中国新通信》 2018年第4期

目前采用数据纵横剖分配合递归过程的基本方法能够实现数据网格中决策树的并行化，满足可扩展的高性能并行计算条件，对优化并行分类算法，解决海量数据信息非常有帮助。所以首先应该分析并行算法并对其数据进行试验。

一、关于数据挖掘网格与决策树

当前所存在的数据挖掘算法主要涵盖了非常经典的关联、分类与聚类分析方法，同时也包括神经网络算法。而本文中所提到的是决策树算法，它属于预测算法类型，目前已经被广泛应用。决策树算法的核心是复杂并行计算，它围绕数据挖掘网格计算开展开研究并解决问题，可实现对海量数据的有效计算处理、挖掘以及存储，而且相比传统计算方法对现有的PC、服务器等设备利用率更高但使用成本更低，能够满足规模化动态扩展功能，可以解决数据挖掘过程中所出现的各种计算密集需求难题。在决策树算法的并行化研究过程中，需要结合其算法的具体特征来展开分析，保证并行化程度高水平发挥。但考虑不同并行方法的结构、特征都有所不同，所以应该根据实际情况来采用并行方法，例如某些侧重于节省系统内存、有些则侧重于减少计算节点通信负担等等，可以通过综合多种方式来实现综合并行（至少两种）。

二、决策树并行算法的设计与数据验证

2.1 决策树并行算法的设计

决策树并行算法在设计过程中一定要将并行化作为重点，根据重点来训练数据的横向并行分割条件，还要考虑在不同计算节点上进行有效分配，对其中不同的属性信息熵进行针对性计算。不过在计算设计过程中，信息熵的并行度会受到属性个数限制影响而分裂深入，其计算属性会相应锐减，此时并行任务调度会出现一定困难，所以要进一步优化决策树并行算法的设计流程。首先设计决策树的并行算法输入部分，主要是整合所有记录数据做成一个集合，然后明确其中各项分类属性；其次是输出部分，建立一棵完整的决策树，此时可以对其算法处理流程进行计算设计如下：

Begin

Partition(T);

Partition(Data S);//the record number of S is sEach Computing Nodes read their own data according to thedivided method,Node i read data set

If the pruning situation is true then return;// 实行预剪枝处理 Pre-pruning通过上述设计来计算出该处理流程的并行结果，保证其适合本处理流程循环，并根据最大并行度来作为参与分裂的基本指标。随后收尾设计：

Use best split found to partition S into S1 and S2;

Pratition(S1);//

Pratition(S2);//

End

2.2 决策树并行算法的数据试验

对决策树并行算法进行数据试验就要设置假定训练集，这里将假定训练集的数据量设置为N，如果N 值到达足够大时，就可以针对一棵决策树。满足以上条件后pttt 达到最小值。

为了进一步明确试验结果，还要继续实施以下4 步骤：第一，假设根节点第i 层上的所有节点分裂属性均为Ai。第二，在最靠近根节点位置的叶节点首层上再设置一个1 节点。第三，保证其它叶节点都处于第i 层上，并保证每个叶节点的数据量均等都为dmin。

根据上述试验步骤，就可推理出在第k 层的叶节点数据量总和应该为[1]：

三、决策树并行算法的性能简析

对数据挖掘网格中决策树并行算法的性能进行分析，主要有以下3 点。首先，要在并行算法中对系统的最佳CPU数量进行分析，明确其CPU 个数与多个因素之间的关系，例如数据挖掘网格的时间特性参数，包括各个时间特性参数的分段数数量等等。其次，在基于某种特殊系统特征下对其网格系统参数进行确定，保证数据记录数目N 与最佳CPU个数相互匹配，且个数n ＞ 1。围绕该数据挖掘网格环境进行计算，得出并行计算结果。第三，要根据N 的变化情况与数据挖掘网格环境进行计算，提前了解它可能会对n 值产生一定影响。所以如果出现n ≤ 1 的情况，就说明在并行计算后数据挖掘网格中决策树的性能效率变低，说明在该种数据挖掘网格环境中，不适合采用并行算法[2]。

总结：总而言之，在决策树算法中采用并行算法能够对数据挖掘网格产生线性加速作用，而并行化本身在加速比与效率方面需要考虑多方面因素，所以在合适的环境下可以采用并行计算来实现对数据挖掘网格的有效部署。