计算机云计算的SLIQ并行算法实践研究

孙 娟

（江海职业技术学院，江苏 扬州 225101）

计算机云计算的SLIQ并行算法实践研究

孙 娟

（江海职业技术学院，江苏 扬州 225101）

随着云计算的出现，当前的数据分析和存储变得更加方便和高效。在传统的SLIO计算方式之中有着许多的缺陷，在计算机云计算环境之中需要对这些缺陷进行有效的改进。文章对计算机云计算与SLIQ的并行算法展开了实际性的研究。

计算机；云计算；SLIQ并行算法；数据分析；数据存储

在数据挖掘的过程中必然会遇到海量的数据处理和计算，而在传统的SLIQ计算方式中更倾向于小规模的数据处理与计算，一旦数据量过大就会使得运算的速度等影响到最终的挖掘效率，甚至会让计算出现无法进行的问题，这也是传统SLIO计算方式的一大瓶颈。计算机云计算的出现正好能够改变这种现状，云计算更倾向于大数据的处理和计算，如果将其与SLIO计算方式相结合，通过并行计算将会有效地改变挖掘计算困难的问题，从而实现海量数据的处理与运算。下面根据笔者自身的经验，对计算机云计算的SLIQ并行算法展开探讨。

1 SLIQ算法的概述

SLIQ算法最早于1996年被提出，是一种高速的可调整的数据挖掘分类模式计算方法。SLIQ算法在计算设计上面采用的是预排列思路，当数据量较大的时候，又不能将所有的数据全部放入内存驻留磁盘，此时会将这些数据进行排序，同时处理离散和连续的字段。SLIQ算法是基于此点之上采取广度优先的方式完成决策树的构建，其在计算的过程中会对每层节点的属性表进行扫描，然后根据扫描的结果找出当前的最优分裂方式。在形成新的节点之中进行取值，并对列表的类型进行节点信息更新。

2 云计算的SLIQ计算改进

2.1 决策树中的Gini指标

在通常的情况下，决策树中会选用信息量来作为评价节点分裂质量的参数，在SLIQ算法之中则对此做出了改变，利用Gini指标来代替信息量的位置，其应用起来性能相对更好，让整个计算变得更加的简便、高效。在Gini指标之中，主要是用来度量数据划分或者训练元祖级的纯度。当Gini指标出现变小的情况时则预示着信息增益量变大，对于节点分裂的质量也就越好。在此过程之中也可以对数据集进行分裂，从而形成二元划分，如果其中存在着一些连续值属性和离散值属性则存在着一定的不同。在面对离散值属性时，需要选择该离散值属性产生最小指标的子集作为分裂子集。

SLIQ算法与传统算法在决策树的形式上也有着很大的不同，SLIQ使用的是二分查找树结构，对于该种结构在计算上要求更高，需要先对其中的每个节点进行计算，并从计算结果之中找到分裂的方式，然后进行分裂。可能直接这样说理解起来较为困难，现以实际距离进行分析：在一个字段之中，如果发生分裂通常都会是在其中点的位置，将该字段进行排序，一共具有N个节点，分裂发生时只会是在两节点的中间，也就是说在N个节点中会出现N-1个可能性，然后从小到大依次取其中不同的分裂节点，从中可以找出Gini指标最小的分裂点。但是其中也存在着特殊的情况，如离散字段可能的分割则是属性值中的所有子集，在展开分裂测试的时候就需要将其中存在可能的所有子集都取出来。

SLIQ算法中重要的技术优势在于事先排序和广度优先者两种技术思路上面，也正是这两种技术的运用使得SLIQ算法变得更加的高效。对于事先排序技术而言主要是为了消除在决策树中每个节点对数据集进行排序的过程，从而实现性能上的优化。对于广度优化技术主要是为了节省对每个节点扫描的时间和占用的资源，从而有效地提升SLIQ算法的运算速度。

2.2 SLIQ最佳分裂

在SLIQ计算中，Gini index通常表示的是可伸缩指标，这个指标通常被用来替代信息量，在生成新的决策树中起到非常重要的作用。对其定义为在数据集中包含多个记录，则Gini index可以用下面式子来进行表示：

如果在上式之中的集合D被分成两个部分，分别用D1和D2来进行表示，则关于Gini index可以用下面的式子来进行表达。

在上面的公式之中Pj指的是在该集合之中出现j类数据的频率。而对于Gini index来说最大的特征之处在于计算过程中需要考虑其中的数值在被划分之后的分布情况。

对于其中出现数值连续型连续字段的时候，查找其中最合理点的方法为：首先假设有字段a为数值连续字段，对其进行预排序操作，然后得到R1、R2、R3、……、Rn的排序结果，在分裂的过程中没有一定的规律，经常会出现在两个相邻节点内，也就是存在着n-1种分裂的可能性。按照正常的运算方式选取分裂的候选节点，通常会选择中间的节点，因此分裂形式可以表示为a≤Ri和a＞Ri，然后按照从小到大的顺序排列分裂点，将其中最小的分裂点定位最佳的候选节点。

在针对离散字段进行处理的时候，其情况同连续字段有着极大的相似之处。首先将分裂测试数集字段b分为两个集合，分别为b1和b－b1，然后对这两个部分分别进行计算得出Gini index数值，取Gini index数值之中的最小值，则该值对应的分裂点就是最佳的分裂点。

2.3 对SLIQ的适应性改进

在实际应用过程中为了能够让SLIQ算法适用于当前的海量数据处理和运算，需要对SLIQ算法做出适当的并行化改造，才能够让它在云计算之中获得良好的处理效果。SLIQ算法并行化改造的方法为：将整个类表复制到每个处理器的内存之上。并行算法又称为Generate decision tree，因为数据划分D的训练元组产生出决策树。在输入上面：数据划分D是训练元组对应类型标号的集合；attribute list，候选属性集合attribute selection method，作为划分最合理的数据元组，并作为个体类数据的分类准则的过程。这个准则是由分裂属性和分裂点、分裂子集构成。在输出上面：首先将一个决策树作为此次的输出目标，具体操作如下：创建一个数据节点；将d集合之中的相同类型数据都归于c集合中；返回并对c进行标记；如果其中的attribute list是一个空的集合，则需要再次返回并标记d集合中的多数情况，然后使用attribute selection method和d集合中的attribute list找出最佳的节点分裂位置。将SLIQ算法进行改进之后，取得的最大优势在于类表输入到内存的速度将会被提高，这也就使得这个过程被极大简化，让其在较短的时间内就能够完成，而且生成出来的目标数也较小。

2.4 在Map Reduce中SLIQ的改进

当然改进的方式还可以采用Map Reduce编程的方式来实现，其操作的具体步骤可以按照下面的方式实行：

第一，将所有收集到的根节点数据记录运用Map Reduce函数来进行划分，形成m个子数据集合，它们的规模基本相同，然后将数据块划分为Input Splito。

第二，将上述划分得到的m个子数据集合采取格式化操作，会产生出＜key，value＞对，格式化为＜Sn，＜idn，tn，val-Ue，则此时格式化中的Sn表示的含义是m个子数据集合中的第n个表格的第s列；to表示的是第n个表格所对应的属性值；idn则表示的是第n个表格之中的数据单元索引值；val-uel表示的是记录的类别。

第三，Map Reduce操作实质上可以分为两个操作的过程，首先是Map操作：通过该操作会将输入进来的相关记录进行仔细的扫描，然后按照特定的程序进行分类整理，把其中key相同的数据放在一起存储到相应的文件之中，然后才是将文件配置到Reduce之中，执行接下来的操作。

第四，针对其中的连续行数据段首先按照特定的顺序进行排序，生成与之相对应的直方图，并将初始阶段设置为0，极端分裂点Gini rode值就是Reduce所对应的任务，然后在操作过程中只需要实时更新类对应直方图，不需要对直方图进行更新，然后利用类直方图就可以准确地计算出相对应的Gini index值。

3 结语

综上所述，云计算在处理和计算海量的数据时表现出来的优势是无法替代的，而要想在数据挖掘中实现海量数据处理和计算，将SLIQ算法并行改进是一种十分可行的方式。因此，在本文中分析了云计算环境下的MapReduce的改进算法，说明在云计算的环境下决策规则和并行化是十分重要的基础，在实现的过程中可以通过对SLIQ算法的改进，从而获得对其高速运算的支持。

[1]贺俊．探究计算机云计算的SLIQ并行算法分析[J]．无线互联科技，2014，（2）.

[2]崔学敏，张传勇．云计算技术中计算机海量数据SLIQ算法的应用[J]．电子技术与软件工程，2015，（18）.

[3]何元．基于云计算的海量数据挖掘分类算法研究[D]．电子科技大学，2011.

[4]杜亚光．大跨度自锚式悬索桥结构并行计算算法与主梁恒载状态研究[D]．西南交通大学，2013.

[5]张敏．云计算环境下的并行数据挖掘策略研究[D]．南京邮电大学，2011.

[6]高华．计算机海量数据处理SLIQ算法研究[J]．长春工业大学学报，2016，（4）.

[7]李筱．面向异构多核系统的并行计算模型和调度算法研究[D]．湖南大学，2012.

（责任编辑：黄银芳）

TP393

1009-2374（2017）12-0011-02

10.13535/j.cnki.11-4406/n.2017.12.006

孙娟（1977-），女，江苏江都人，江海职业技术学院讲师，硕士，研究方向：计算机应用技术。

A