大數據下不完備信息系統近似空間的并行算法

姜 麟，米允龍，王 添

JIANG Lin,MI Yunlong,WANG Tian

昆明理工大學 理學院，昆明 650500

Faculty of Science,Kunming University of Science and Technology,Kunming 650500,China

1 引言

隨著大數據時代的來臨，對海量數據進行挖掘已成為研究的熱點。而大數據不只是海量的數據，擁有了海量數據后，并且有能力進行處理和分析，挖掘出數據的價值才可以獲取數據的價值，從中獲取真知[1]。面對如何挖掘出海量數據的價值，Google公司提出了分布式文件系統GFS（Google File System）[2]和MapReduce并行編程模式[3]，這為數據挖掘提供了一個很好的平臺。在此基礎上，已有不少學者致力于相關研究，并取得了一定的效果。例如，文獻[4]提出的基于MapReduce的Web日志挖掘，文獻[5]對在MapReduce框架下的分布式近鄰傳播聚類算法的研究等。

對于海量數據，傳統的精確處理不再適用[1]，更多的是近似性處理。粗糙集理論是一種新的處理模糊和不確定性知識的數學工具，目前成功應用于機器學習、決策分析、模式認別和數據挖掘等領域[6]。基于粗糙集理論，目前已提出許多處理海量數據的算法。如文獻[7]對海量數據的粗糙集近似空間并行算法的研究，文獻[8-11]提出的各種處理海量數據的并行知識約簡算法。然而，以上都是基于未帶缺失信息的海量數據，在實際應用中，很多數據是帶有缺失信息的[12-13]。對于不完備的信息系統或帶缺失信息的海量數據，往往可以采用集值信息系統來處理[13]。同時，傳統的算法是假設所有數據一次性裝入到內存中去，但這并不適用于海量數據。因此，對帶缺失信息的海量數據進行研究是十分必要的。探討如何基于MapReduce并行編程框架，實現對不完備信息系統的上、下近似的并行算法研究，對帶缺失信息的海量數據進一步挖掘具有重要的促進作用。

通過深度分析不完備信息系統的特征，本文在第二部分結合MapReduce并行編程的特點，給出了對原有集值信息系統進行擴展的相關理論。在第三部分提出了一種基于MapReduce框架下不完備信息系統近似空間的并行算法。第四部分通過實驗結果表明，該并行算法對處理帶缺失信息的海量數據是可行的，高效的。

2 相關理論

在這一部分，將介紹一下MapReduce相關技術[2-3]、不完備信息系統[6-7，12，14-16]及其擴展相關理論。

2.1 MapReduce并行編程模型

MapReduce模型是Dean和Ghemawat于2008年提出的并行編程模式，描述如下[3]：

首先，接收輸入key-value對集合；再而，通過執行Map和Reduce兩個函數；最后，輸出相應的key-value對集合。因此，只需要設計出相應的Map和Reduce函數，就能將任務進行并行計算，其形式如下：

Map函數接收一組輸入鍵值對(k1，v1)，鍵值對(k1，v1)經過Map函數處理后，并按k1進行排序；combiner類把相同鍵k1關聯的值v1進行本地聚類，產生中間鍵值對(k2，v2)；在Reduce階段，鍵k2相同數據的將會被送到同一個Reducer任務中，Reduce再把相同鍵k2的數據整合在一起，進行處理。

2.2 粗糙集相關概念

信息系統 S=(U，AT，V，f)，U=(x1，x2，…，xn)是對象的非空有限集合，稱為論域；AT是屬性的非空有限集合；特別的，如果AT=U∪D，C為條件屬性的非空有限集，D為決策屬性的非空有限集，且C∩D=?，則稱S為決策信息系統。其中V=∪a∈ATVa，Va是a屬性的值域；f:U×AT→V是一個信息函數，它為每一個對象的每個屬性賦予一個信息值，即?a∈AT，x∈U，則有f(x，a)∈Va。

定義1[12]對于信息系統S=(U，AT，V，f)，若至少有一個屬性a∈AT使得Va中含有缺省值（記作*），則稱S是一個不完備信息系統，記為IS。若AT=C∪D，且有C∩D=?，則不完信息系統IS稱為不完備決策系統（或不完備決策表），記為DS。

定義2[14-15]設 IS=(U，AT，V，f)是一個不完備信息系統，如果 ?a∈AT，x∈U，若有 f(x，a)=*，令 f(x，a)=Va，則稱這是一個不完備信息系統向集值系統的一種轉換，為了簡便起見，稱轉換后的信息系統仍為集值信息系統，記為SIS。SIS是集值信息系統，若AT=C∪D，且有C∩D=?，則稱集值信息系統為集值決策表，記為DIS。

定義3[16]設 DIS=(U，C，D，V，f)是集值決策表，對?a∈A，x∈U，f(x，a)取值從語義方面被析取地解釋。例如：a表示屬性“語言能力”，則 f(x，a)={德語，法語，漢語}也可以解釋對象x會說德語，法語和漢語其中的一種語言。

定義4[14-15]設 DIS=(U，C，D，V，f)是集值決策表，任意屬性子集B?C，定義二元系：

顯然，RB是自反和傳遞的，未必是等價關系。

定義5[15]設 DIS=(U，C，D，V，f)是集值決策表，對于任意 X?U，記：

定義6 設 DIS=(U，C，D，V，f)是集值決策表，若對?x∈U，?a∈C ，若有 f(x，a)=Va，則取 f(x，a)=ai，其中ai∈Va，i表示Va中屬性值的取值數，其中，x=x[1]∪x[2]∪…∪x[i]。則稱為集值決策表 DIS的一個擴展，其中Uˉ=U∪x[i]。

其中，[x]B*={y∈U|(x，y)∈RB*}。對于任意 X?U ，U/RB*={E1，E2，…，Em}，為了簡便，記：U/B* 。

則定義相應的上近似和下近似如下：

例1表1為一個不完備決策信息系統，表中“*”表示缺省值。根據定義2和定義3，對不完備信息系統進行轉換。如 f(x3，a1)=*，由定義2、定義3可得，f(x3，a1)={1，2}。其余進行同樣的轉換，則可得集值決策信息系統表2。

由定義4和定義5得到(B=C={a1，a2，a3，a4})：[x1]B={x1}，[x2]B={x2}，[x3]B={x3}，[x4]B={x3，x4}，[x5]B={x3，x5}，[x6]B={x6}。取 X={x1，x2，x3}，則實際上，x5，x6很可能被分在同一類，而在此卻沒有。可以看出，下近似比較寬松，而上近似比較嚴格。為了解決這種情況和大數據的計算要求，對集值信息系統按定義6進行擴展，如表3。

表1 一個不完備決策信息系統

表2 一個集值決策信息系統

表3 決策信息系統

表3 決策信息系統

x1 x2 x3[1]x3[2]x3[3]x3[4]x4[1]x4[2]x5[1]x5[2]x6[1]x6[2]a1111122111222 a2121212121112 a3211111111111 a4221111111112 D112222111122

由定義7可得（其中 B*=C={a1，a2，a3，a4}）：[x1]B*={x1}，[x2]B*={x2}，[x3]B*={x3，x4，x5，x6}，[x4]B*={x3，x4，x5}，[x5]B*={x3，x4，x5，x6}，[x6]B*={x3，x5，x6}。取 X={x1，x2，x3}，則有上、下近似為：x4，x5，x6} 。

3 基于MapReduce的不完備信息系統近似空間的計算

在這部分，將根據第二部分的相關理論，研究在MapReduce框架下不完備信息系統近似空間的并行算法。

3.1 MapReduce框架下近似空間算法的并行性研究

于是，關于B*的二元關系定義如下：

則關于 B* 的劃分 U/B*={E1，E2，…，Em}，對任意E∈U/B*={E1，E2，…，Em}可以定義如下：

對于信息集合E1，有如下：

例3 D為決策屬性，根據定義8、9可得，U/D={D1，D2}，其中 D1={x1，x2，x4，x5}，D2={x3，x6}。則有：

根據定義10可得，不完備信息系統經過轉換成集值信息系統，并進行擴展后，可以將其劃分成n個子集值決策信息系統。這說明并行編程的可行性。

3.2 基于MapReduce框架下的并行算法

3.2.1 基于MapReduce下不完備信息系統的二元關系B*的劃分類U/B*計算

算法1 Map（）與Reduce（）函數

算法1是在MapReduce框架下把不完備信息系統轉化成集值信息系統，并求出相應二元關系劃分類。此算法除Map（）和Rduce（）函數外，還有對不完備信息進行集值化的splitMap（）遞歸函數。

3.2.2 基于MapReduce下不完備決策信息系統決策類的計算

算法2 Map（）與Reduce（）函數

算法2是根據決策屬性來劃分決策關系類，把決策屬性相同的對象劃分到同一類中。

3.2.3 不完備信息系統近似空間的并行計算

算法3 上近似Map（）與Reduce（）函數

算法3是處理上近似并行算法，此處存儲的是上近似的索引值，以防止內存溢出。下面算法4關于下近似并行算法存儲的也是索引值。

算法4 下近似Map（）與Reduce（）函數

4 實驗結果及分析

4.1 數據集及實驗環境描述

在這部分，將選用UCI機器學習數據庫（http：//archive.ics.uci.edu/ml/datasets.html）中帶缺失信息的兩個數據集Mammographic Mass Data Set和Breast Cancer Wisconsin Data Set；為了簡便，分別記為：MMDS、BCDS。現在，將MMDS分別復制800次和8 000次，得到新的數據集記為：MMDS1、MMDS2；將BCDS分別復制8 000次和80 000次，得到新的數據集記為：BCDS1、BCDS2。具體數據集描述如表4所示。

表4 數據集的描述

本實驗環境采用Hadoop集群（http：//hadoop.apache.org/），該集群由1臺主控制節點和8個計算節點構成。每個節點配置為Intel?Pentium?D CPU 2.80 GHz，2 GB內存和150 GB硬盤。操作系統為Linux Centos 6.3，JDK為Java 1.7.0_17，Eclipse采用32位的Linux版本eclipse-3.3.2。MapReduce框架基于Hadoop平臺0.20.2，其他采用系統默認設置。

4.2 算法效果及驗證

此節，將主要從加速比（speedup）、可擴展性（scaleup）[17]和運行時間3個方面對并行算法進行評價及驗證。

（1）運行時間

數據集 MMDS1，BCDS1，MMDS2，BCDS2分別在1～8個計算節點運行，運行結果如表5所示。

表5 并行算法的運行時間 s

如表5所示，同一數據集隨節點數增加而運行時間不斷減少。并且，數據量越大，遞減的效果越好。這表明，對于大數據，基于MapReduce并行編程取得很好效果。表5還顯示出，雖然數據集BCDS1記錄數比數據集MMDS2少，但是其屬性項數比數據集MMDS2多，導致其運行時間比數據集MMDS2長。易得出，屬性集在上、下近似算法是至關重要的。

以下給出與計算節點數成比例增長的數據集的運行時間。為了計算方便，取記錄數為100 000的數據集MMDS1于一個計算節點上運行，仍記為：MMDS1。同樣，BCDS1，MMDS2，BCDS2在一個計算節點上運行的數據量分別為：700 000，1 000 000，7 000 000。

具體如對于數據集BCDS1來講，用700 000記錄數在一個計算節點上運行，則用700 000×2記錄數在兩個計算節點上運行，并依次下去，可得運行時間如表6所示。

（2）加速比（speedup）

為了測試加速比，固定數據集規模，不斷增加數據的計算節點數。通常，線性加速比是十分理想的；但是，由于節點數增加，集群之間的通信時間會不斷增加。因此，一般很難達到理想的線性加速比。公式如下[17]：

表6 并行算法可擴展性的運行時間 s

其中，T1是固定規模數據集在一個節點上運行時間，Tm是同樣固定規模數據集在m個節點運行時間。

根據表5提供的并行算法運行時間，運用加速比公式（1），可得圖1。

圖1 加速比

如圖1所示，不同數據集隨著計算節點數增加的加速比趨勢。從圖可以看出，數據集的記錄數越多加速比越好，如數據集BCDS2與數據集MMDS1相比，其加速比要好。因此，對于帶缺失信息的海量數據集，基于MapReuce編程模型的并行算法有效性得到證實。

（3）可擴展性（scaleup）

可擴展性指的是同計算節點數成比例增長的數據集的性能比，公式如下[17]：

其中，TDB1是數據集DB在一個計算節點上運行時間，TDBm是數據集m×DB在m個計算節點上運行時間。根據表6提供的并行算法可擴展性的運行時間，運用可擴展性公式（2），可得圖2。

如圖2所示，各數據集隨著計算節點數增加的可擴展性趨勢。從圖2可以看出，各數據集都有較好的可擴展性。同時，圖2還顯示出，數據集規模越大，可擴展性越好，越趨于穩定。

5 結束語

圖2 可擴展性

隨著數據的重要性和不確定性增加，粗糙集已經成為數據挖掘的一種有效工具。運用粗糙集進行數據處理時，上、下近似是其必要的步驟。然而，傳統的上、下近似算法不適合處理海量數據，更不適合對帶缺失信息的海量數據進行挖掘。為了促進對帶缺失信息的海量數據研究，提出了MapReduce框架下不完備信息系統的一種近似空間并行算法。通過對并行算法的時間、加速性和可擴展性的實驗，表明對缺失信息不是很多的情況下，該算法是高效的，能夠處理帶缺失信息的大規模數據集。這對進一步研究帶缺失信息的海量數據具有重要的參考價值。

[1]懷進鵬.大數據及大數據的科學與技術問題[C/OL]//第五屆中國云計算大會，北京，2013.http：//www.ciecloud.org/2013/index.html.

[2]Ghemawat S，Gobioff H，Leung S T.The google file system[C]//SOSP’03，2003：29-43.

[3]Dean J，Ghemawat S.MapReduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

[4]李彬，劉莉莉.基于MapReduce的Web日志挖掘[J].計算機工程與應用，2012，48（22）：95-98.

[5]魯偉明，杜晨陽，魏寶剛，等.基于MapReduce的分布式近鄰傳播聚類算法[J].計算機研究與發展，2012，49（8）：1762-1772.

[6]張文修，吳偉志，梁吉業，等.粗糙集理論與方法[M].北京：科學出版社，2001.

[7]Zhang Junbo，Li Tianrui.A parallel method for computing rough set approximations[J].Information Sciences，2012，194（1）：209-223.

[8]Yang Y，Chen Z，Liang Z，et al.Attribute reduction for massive data based on rough set theory and MapReduce[C]//Yu J.The Fifth International Conference on Rough Set and Knowledge Technology.Berlin Heidelberg：Springer-Verlag，2010：672-678.

[9]錢進，苗奪謙，張澤華.云計算環境下知識約簡算法[J].計算機學報，2011，34（12）：2332-2343.

[10]錢進，苗奪謙，張澤華.云計算環境下差別矩陣知識約簡算法研究[J].計算機科學，2011，38（8）：193-196.

[11]錢進，苗奪謙，張澤華，等.MapReduce框架下并行知識約簡算法模型研究[J].計算機科學與探索，2013，7（1）：35-45.

[12]Kryszkiewicz M.Rough set approach to incomplete information systems[J].Information Sciences，1998，112（1）：39-49.

[13]張文修，梁怡，吳偉志.信息系統與知識發現[M].北京：科學出版社，2003.

[14]宋笑雪，李鴻儒，張文修.集值決策信息系統的知識約簡與屬性特征[J].計算機科學，2006，33（7）：179-181.

[15]宋笑雪，李鴻儒，張文修.集值信息系統的知識約簡與屬性特征[J].計算機工程，2006，32（22）：26-36.

[16]Qian Y，Dang C，Liang J，et al.Set-valued ordered information systems[J].Information Sciences，2009，179（16）：2809-2832.

[17]Xu Xiaowei，Jager J，Kriegel H P.A fast parallel clustering algorithm for large spatial databases[J].Data Mining and Knowledge Discovery，1999，3（3）：263-290.