面向决策分解的MapReduce模型

李放

（大连东软信息学院数字艺术与设计学院 辽宁省大连市 116000）

及时建立大数据，并从大数据中摒弃错误数据，提取准确的、有价值的因素，将这些因素进行分类、归纳、处理，以建立准确的数学模型，再将该模型应用到实际环境中去，反复论证，这一系列过程就是影响判断依据的关键。

1 决策分解

对大数据信息的处理，需要用到决策分解，因此将数据与决策相关联就成为了一个关键[2]。将数据以数学集合的方式进行呈现，如公式U={A,B,f}所示，其中U表示数据集合，A表示条件属性，B表示决策属性，满足条件A∪B=U，A∩B=∅，f是一函数，用来将条件属性和决策属性进行映射，数据转换，f(A,B)=σ，其中σ表示任意的数字，如表1所示。

通过一系列运算，将原来复杂的数据按照一定的规则进行分解，以达到简化的目地。在表1中，U={3,2,4,4}有4个数据，A={1,1,2,3}是条件属性集合，B={2,1,2,1}是决策属性集合，σ={1,0,0,-2}是映射值集合。在实际的数据运算中，数据集合量级巨大，对于条件属性和决策属性的影响也会随之变大，造成映射值的不稳定，从而影响决策分解的准确性。

与此同时，决策系统也是影响决策分解的重要因素之一。决策系统f(A,B)=σ需要根据不同的实际情况来进行构建，同时满足对条件因素的判断和使用，例如构建公式f(A,B)=-A+B=σ进行映射，该公式的条件值A是一个有限集合，该集合具有多个相同类型的数值，即A={x1,x2,x3,……xn}，其中xn代表数据值。下面对A进行分析。A是一个条件样本，该条件样本的每一个值具有类型相同，数值不同的特点，但是在实际的数据分析中，可能会出现数值相同的情况，因此就要进行分类处理，将相同数值的情况进行分类归纳，形成子集，即{y1,y2,y3,……yn}，每个样本都将是多个子集的集合。与此类似，B是一个有限集合，是一个决策属性集合，该集合具有多个相同类型的数值，即B={c1,c2,c3,……cn}，其中cn代表数据值。下面对B进行分析。B是一个决策样本，该决策样本的每一个值具有类型相同，数值不同的特点，但是在实际的数据分析中，可能会出现数值相同的情况，因此就要进行分类处理，将相同数值的情况进行分类归纳，形成子集，即{d1,d2,d3,……dn}，每个样本都将是多个子集的集合。σ是一个任意数值的有限集合，其依托公式的计算结果，该结果将反映映射的处理结果，该结果是不确定的，从而引出决策的不确定性。

图1：运算过程

决策的不确定性可表述为[2]：相同的条件计算出不同的结果，或者不同的条件计算出相同的结果。这在数据分析中经常遇到，对此人们可通过主观分析，变相处理等方法应对处理，不过也时常遇到各种困难。对于计算机编程来说，当涉及决策的不确定性问题时，如果不能有效地给出相应的算法处理，计算机将无法解决。当决策系统的属性比较多，特别决策属性很多时，条件样本数据的决策结论将涉及很多的决策函数值。因此对众多的决策属性进行分解，分别考虑每一个决策属性，使对较多决策函数值的考虑分解为对单一决策函数值的讨论，由此对决策的确定或不确定性进行有效的判定，那么该分解方法对决策的确定与否将具有清晰化的意义。

2 MapReduce模型

在如今，数据量级的增长速度非常快，MB、GB已经成为过去，取而代之的是TB、PB，如何有效地解决数据增长带来的有效运算成为了人们关心的课题，而MapReduce模型就可以很好地解决该问题[3]，也成为了使用广泛地并行数据处理模型之一。MapReduce模型运行的环境是一群服务器电脑组成的，不用去处理底层的逻辑，也能够较好的实现细节处理，从而极大地简化开发工作，而该模型提供的接口也方便使用者调度、管理等[4]。如图1所示。

表1：映射表

其执行过程如下所示[5]：

首先，用户将若干个数据进行分类与处理，分成N份，每份的大小均为相同的数值64MB，开始进行数据的拷贝，这些数据中，需要有一份是主要程序，其余是次要程序。主要程序是为了体现逻辑的准确性。

然后，进入到Map环节，程序从数据中提炼分析出<实体关系>的逻辑，将这些逻辑作为用户定义的函数进行输入，而<实体关系>逻辑被存储在计算机内存中，随时可以读取。

接着，该逻辑值会以某种频率写入到磁盘中，经过用户事先规划好的映射函数处理，一般都会有递减的过程，将本地磁盘上的内容传送给Reduce，以达到处理的目的。

最后，当每一个Reduce任务被执行后，通过某种算法或者排序将相同值的数据聚合在一起，形成数据流，进行输出。

MapReduce模型是由Google公司提出的，其初衷只是为了解决与搜索相关的问题。目前，随着使用的不断推广，MapReduce的应用范围越来越广泛，与此同时MapReduce的问题也浮出水面。为此，很多专家进行了相关的研究，对MapReduce模型进行了改进[3]。

例如，首先远程读取全部所需的数值<实体关系>对和按照数据值排序会消耗掉大量的时间。为此，文献[6]提出了Barrier-less MapReduce并行编程模型。该模型通过修改Reduce函数，使得Reduce函数能够处理数值<实体关系>对，从而来解决该问题的。但是，该模型增加了用户编程的负担，用户需要修改定义的Reduce函数才能达到上述要求。其次，MapReduce模型缺乏支持处理多个相关异构数据集的能力。为此，文献[7]提出了MapReduceMerge并行编程模型，对多个异构数据集分别执行Map和Reduce操作，之后在Merge阶段合并在前期阶段已分割和分类融合的数据。MapReduceMerge模型虽然能够处理多个相关异构数据集，但是并不能自动执行多次MapReduceMerge过程。用户需要手动执行多次MapReduce或者MapReduceMerge过程时，需要解决同步处理、调度和Bug等问题，对于用户来说，编程负担过重。为此，文献[8]提出了Oivos并行编程模型，Oivos利用抽象层来实现自动管理执行多次MapReduce或者MapReduceMerge过程。用户需要指定处理多个相关异构数据集需要的MapReduce或者MapReduceMerge过程个数，并通过时间处理函数的监测来自动发现哪些任务需要执行。与此同时，MapReduce并行编程模型不能很好地适应小规模集群。为此，基于无共享模型和消息传递，文献[9]提出了名为KPNs(Kahn process networks)的并行编程模型。KPNs模型能够自动执行迭代计算，且编程灵活。

3 迭代算法

迭代算法指的是使用相同的计算逻辑，根据某个初始值反复执行一个方法函数的过程[10]，而这个初始值也在反复计算中不断精准，逐渐逼近于最优解。迭代计算目前广泛应用于机器学习算法和数据挖掘中。MapReduce模型使用迭代算法可以用来实现包含一组或多组反复运算的MapReduce<实体关系>对，通过不断重复<实体关系>对来计算数据，从而逼近目标或结果。迭代数据分为始终不变的静态数据和计算过程中不断改变的动态数据。利用MapReduce实现迭代算法需要从以下3个方面考虑。

（1）确定迭代变量。至少应有一个直接或间接地不断由初始值推出下一个值的变量，该变量就是迭代变量。

（2）建立迭代方程式。迭代方程式的建立保证了能够从当前变量推出下一个变量，该方程式需可并行，可用MapReudce任务实现。

（3）控制迭代过程，确定迭代过程终止条件，以及如何在MapReduce任务中加入该条件。

MapReduce不支持原生的迭代算法。因此编程人员需要通过程序设计，算法结构来布置MapReduce任务，同时使用数据结构来支持迭代算法。

在大数据处理算法中，迭代算法的实际应用更加广泛。除上述算法之外，递归关系查询、HITS(超文本主题检索)、社会网络分析、神经网络分析以及网络流量分析同样需要进行迭代算法。由此分析，将迭代算法应用在MapReduce模型中，具有较好的发展前景，与此同时，结合决策分解的准确性要求，利用迭代算法中，不断地逼近初始值来计算新值的循环过程，这些都是可以用来解决MapReduce模型的并行处理问题，从而解决决策模型在进行分解过程中的计算问题，从而得到模型的最优解。在一系列的实验过程中，也证明了该理论的正确性。与此同时，随着人们越来越重视大数据计算的准确性问题，利用MapReduce模型与决策分解相结合的方式也会受到大众的广泛关注。