面向決策分解的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模型與決策分解相結合的方式也會受到大眾的廣泛關注。