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

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

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

2 相關(guān)理論

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

2.1 MapReduce并行編程模型

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

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

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

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

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

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

定義2[14-15]設(shè) IS=(U，AT，V，f)是一個(gè)不完備信息系統(tǒng)，如果 ?a∈AT，x∈U，若有 f(x，a)=*，令 f(x，a)=Va，則稱這是一個(gè)不完備信息系統(tǒng)向集值系統(tǒng)的一種轉(zhuǎn)換，為了簡(jiǎn)便起見(jià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)是集值決策表，對(duì)?a∈A，x∈U，f(x，a)取值從語(yǔ)義方面被析取地解釋。例如：a表示屬性“語(yǔ)言能力”，則 f(x，a)={德語(yǔ)，法語(yǔ)，漢語(yǔ)}也可以解釋對(duì)象x會(huì)說(shuō)德語(yǔ)，法語(yǔ)和漢語(yǔ)其中的一種語(yǔ)言。

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

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

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

定義6 設(shè) DIS=(U，C，D，V，f)是集值決策表，若對(duì)?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的一個(gè)擴(kuò)展，其中Uˉ=U∪x[i]。

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

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

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

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

表2 一個(gè)集值決策信息系統(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ì)算

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

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

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

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

對(duì)于信息集合E1，有如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

在這部分，將選用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)（http：//archive.ics.uci.edu/ml/datasets.html）中帶缺失信息的兩個(gè)數(shù)據(jù)集Mammographic Mass Data Set和Breast Cancer Wisconsin Data Set；為了簡(jiǎn)便，分別記為：MMDS、BCDS。現(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ù)集的描述

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

4.2 算法效果及驗(yàn)證

此節(jié)，將主要從加速比（speedup）、可擴(kuò)展性（scaleup）[17]和運(yùn)行時(shí)間3個(gè)方面對(duì)并行算法進(jìn)行評(píng)價(jià)及驗(yàn)證。

（1）運(yùn)行時(shí)間

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

表5 并行算法的運(yùn)行時(shí)間 s

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

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

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

（2）加速比（speedup）

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

表6 并行算法可擴(kuò)展性的運(yùn)行時(shí)間 s

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

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

圖1 加速比

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

（3）可擴(kuò)展性（scaleup）

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

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

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

5 結(jié)束語(yǔ)

圖2 可擴(kuò)展性

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

[1]懷進(jìn)鵬.大數(shù)據(jù)及大數(shù)據(jù)的科學(xué)與技術(shù)問(wèn)題[C/OL]//第五屆中國(guó)云計(jì)算大會(huì)，北京，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].計(jì)算機(jī)工程與應(yīng)用，2012，48（22）：95-98.

[5]魯偉明，杜晨陽(yáng)，魏寶剛，等.基于MapReduce的分布式近鄰傳播聚類算法[J].計(jì)算機(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]錢(qián)進(jìn)，苗奪謙，張澤華.云計(jì)算環(huán)境下知識(shí)約簡(jiǎn)算法[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（12）：2332-2343.

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

[11]錢(qián)進(jìn)，苗奪謙，張澤華，等.MapReduce框架下并行知識(shí)約簡(jiǎn)算法模型研究[J].計(jì)算機(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)與知識(shí)發(fā)現(xiàn)[M].北京：科學(xué)出版社，2003.

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

[15]宋笑雪，李鴻儒，張文修.集值信息系統(tǒng)的知識(shí)約簡(jiǎn)與屬性特征[J].計(jì)算機(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.