大數(shù)據(jù)下不完備信息系統(tǒng)近似空間的并行算法

姜 麟，米允龍，王 添

JIANG Lin,MI Yunlong,WANG Tian

昆明理工大學(xué) 理學(xué)院，昆明 650500

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

1 引言

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

對于海量數(shù)據(jù)，傳統(tǒng)的精確處理不再適用[1]，更多的是近似性處理。粗糙集理論是一種新的處理模糊和不確定性知識的數(shù)學(xué)工具，目前成功應(yīng)用于機器學(xué)習(xí)、決策分析、模式認(rèn)別和數(shù)據(jù)挖掘等領(lǐng)域[6]?；诖植诩碚摚壳耙烟岢鲈S多處理海量數(shù)據(jù)的算法。如文獻[7]對海量數(shù)據(jù)的粗糙集近似空間并行算法的研究，文獻[8-11]提出的各種處理海量數(shù)據(jù)的并行知識約簡算法。然而，以上都是基于未帶缺失信息的海量數(shù)據(jù)，在實際應(yīng)用中，很多數(shù)據(jù)是帶有缺失信息的[12-13]。對于不完備的信息系統(tǒng)或帶缺失信息的海量數(shù)據(jù)，往往可以采用集值信息系統(tǒng)來處理[13]。同時，傳統(tǒng)的算法是假設(shè)所有數(shù)據(jù)一次性裝入到內(nèi)存中去，但這并不適用于海量數(shù)據(jù)。因此，對帶缺失信息的海量數(shù)據(jù)進行研究是十分必要的。探討如何基于MapReduce并行編程框架，實現(xiàn)對不完備信息系統(tǒng)的上、下近似的并行算法研究，對帶缺失信息的海量數(shù)據(jù)進一步挖掘具有重要的促進作用。

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

2 相關(guān)理論

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

2.1 MapReduce并行編程模型

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

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

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

2.2 粗糙集相關(guān)概念

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

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

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

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

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

顯然，RB是自反和傳遞的，未必是等價關(guān)系。

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

定義6 設(shè) DIS=(U，C，D，V，f)是集值決策表，若對?x∈U，?a∈C ，若有 f(x，a)=Va，則取 f(x，a)=ai，其中ai∈Va，i表示Va中屬性值的取值數(shù)，其中，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* 。

則定義相應(yīng)的上近似和下近似如下：

例1表1為一個不完備決策信息系統(tǒng)，表中“*”表示缺省值。根據(jù)定義2和定義3，對不完備信息系統(tǒng)進行轉(zhuǎn)換。如 f(x3，a1)=*，由定義2、定義3可得，f(x3，a1)={1，2}。其余進行同樣的轉(zhuǎn)換，則可得集值決策信息系統(tǒng)表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很可能被分在同一類，而在此卻沒有?？梢钥闯?，下近似比較寬松，而上近似比較嚴(yán)格。為了解決這種情況和大數(shù)據(jù)的計算要求，對集值信息系統(tǒng)按定義6進行擴展，如表3。

表1 一個不完備決策信息系統(tǒng)

表2 一個集值決策信息系統(tǒng)

表3 決策信息系統(tǒng)

表3 決策信息系統(tǒng)

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的不完備信息系統(tǒng)近似空間的計算

在這部分，將根據(jù)第二部分的相關(guān)理論，研究在MapReduce框架下不完備信息系統(tǒng)近似空間的并行算法。

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

于是，關(guān)于B*的二元關(guān)系定義如下：

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

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

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

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

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

3.2.1 基于MapReduce下不完備信息系統(tǒng)的二元關(guān)系B*的劃分類U/B*計算

算法1 Map（）與Reduce（）函數(shù)

算法1是在MapReduce框架下把不完備信息系統(tǒng)轉(zhuǎn)化成集值信息系統(tǒng)，并求出相應(yīng)二元關(guān)系劃分類。此算法除Map（）和Rduce（）函數(shù)外，還有對不完備信息進行集值化的splitMap（）遞歸函數(shù)。

3.2.2 基于MapReduce下不完備決策信息系統(tǒng)決策類的計算

算法2 Map（）與Reduce（）函數(shù)

算法2是根據(jù)決策屬性來劃分決策關(guān)系類，把決策屬性相同的對象劃分到同一類中。

3.2.3 不完備信息系統(tǒng)近似空間的并行計算

算法3 上近似Map（）與Reduce（）函數(shù)

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

算法4 下近似Map（）與Reduce（）函數(shù)

4 實驗結(jié)果及分析

4.1 數(shù)據(jù)集及實驗環(huán)境描述

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

表4 數(shù)據(jù)集的描述

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

4.2 算法效果及驗證

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

（1）運行時間

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

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

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

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

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

（2）加速比（speedup）

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

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

其中，T1是固定規(guī)模數(shù)據(jù)集在一個節(jié)點上運行時間，Tm是同樣固定規(guī)模數(shù)據(jù)集在m個節(jié)點運行時間。

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

圖1 加速比

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

（3）可擴展性（scaleup）

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

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

如圖2所示，各數(shù)據(jù)集隨著計算節(jié)點數(shù)增加的可擴展性趨勢。從圖2可以看出，各數(shù)據(jù)集都有較好的可擴展性。同時，圖2還顯示出，數(shù)據(jù)集規(guī)模越大，可擴展性越好，越趨于穩(wěn)定。

5 結(jié)束語

圖2 可擴展性

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

[1]懷進鵬.大數(shù)據(jù)及大數(shù)據(jù)的科學(xué)與技術(shù)問題[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].計算機工程與應(yīng)用，2012，48（22）：95-98.

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

[6]張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學(xué)出版社，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]錢進，苗奪謙，張澤華.云計算環(huán)境下知識約簡算法[J].計算機學(xué)報，2011，34（12）：2332-2343.

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

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

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

[13]張文修，梁怡，吳偉志.信息系統(tǒng)與知識發(fā)現(xiàn)[M].北京：科學(xué)出版社，2003.

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

[15]宋笑雪，李鴻儒，張文修.集值信息系統(tǒng)的知識約簡與屬性特征[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.