MapReduce框架下近似概念格的并行構(gòu)造算法*

譚富林，姜 麟

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

·微機(jī)軟件·

MapReduce框架下近似概念格的并行構(gòu)造算法*

譚富林，姜 麟

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

具有缺值的形式背景稱為不完備形式背景，相應(yīng)的概念格擴(kuò)展模型稱為近似概念格。近似概念格構(gòu)造中，在數(shù)據(jù)規(guī)模大的情況下采用串行算法效率低，完備形式背景下概念格并行構(gòu)造算法不適用于不完備形式背景。針對(duì)這些問(wèn)題，對(duì)近似概念格的特征進(jìn)行深入分析，提出了在MapReduce框架下的兩種分布式構(gòu)造算法，包括一種并行合并算法和一種增量式并行算法。實(shí)驗(yàn)結(jié)果表明，相比串行算法，兩種并行構(gòu)造算法可以提高近似概念格的建格效率。

不完備形式背景;近似概念格；概念格構(gòu)造；MapReduce框架；并行構(gòu)造算法

1 引言

MapReduce是Google公司提出的一種編程模型，廣泛應(yīng)用于數(shù)據(jù)挖掘、信息提取、機(jī)器學(xué)習(xí)等場(chǎng)景。MapReduce分布式處理框架具有容錯(cuò)控制、細(xì)節(jié)隱藏、伸縮性好等優(yōu)點(diǎn)[1]。

形式概念分析(FCA)是一種用來(lái)提取屬性和對(duì)象二元關(guān)系的方法，形式概念分析在知識(shí)發(fā)現(xiàn)、信息檢索和社會(huì)網(wǎng)絡(luò)分析應(yīng)用等領(lǐng)域中具有很高的應(yīng)用價(jià)值，其中生成概念格能夠很直觀地顯示數(shù)據(jù)[2]。處理大規(guī)模數(shù)據(jù)時(shí)，經(jīng)典的概念格構(gòu)造算法由于運(yùn)行時(shí)間太長(zhǎng)，在實(shí)際應(yīng)用中不實(shí)用，概念格分布式構(gòu)造算法能很好地解決這個(gè)問(wèn)題。Wile提出了典型的分布式構(gòu)造算法，包括疊置和并置兩種[3]。Sokuznetso提出了基于閉包的概念格分布式構(gòu)造算法[4]。BiaoXu等人提出了MapReduce架構(gòu)下的MRGanter算法和MRGanter+算法，其中MRGanter+算法極大提高了并行算法的效率[5]。

在實(shí)際應(yīng)用中，信息系統(tǒng)中常常會(huì)出現(xiàn)帶有缺失的數(shù)據(jù)。文獻(xiàn)[6]提出了不完備形式背景下的概念格定義，在不完備形式背景中，包含1，0和？三種值，其中1表示概念格中對(duì)象具有某個(gè)屬性，0表示對(duì)象不具有某個(gè)屬性，？表示對(duì)象是否具有某個(gè)屬性未知。文獻(xiàn)[7]對(duì)近似概念格進(jìn)行了定義并提出了一種近似概念格的增量式構(gòu)造算法。

完備形式背景下并行建格算法不適用于處理不完備形式背景下的概念格，串行算法在數(shù)據(jù)規(guī)模大的情況下運(yùn)行效率較低。針對(duì)近似概念格的特點(diǎn)，本文中介紹了兩種基于MapReduce框架的不完備形式背景下的并行構(gòu)造方法：并行合并算法，增量式并行構(gòu)造算法。

2 近似概念格基本概念

定義1[2]? K ?(U, A, I )為一個(gè)形式背景，其中?U 為對(duì)象集；? A 為屬性集；?I 為 ?U 和 ?A之間的二元關(guān)系；若 ?(x, a)?I， 則稱x具有屬性 ?a，用1表示，即?I( x ，a ) ? "1"，若 ?(x,a)?I， 則稱x不具有屬性 ?a，用0表示，即

對(duì)于形式背景? (U, A, I) ，在對(duì)象集 ?X?U和屬性集上分別定義運(yùn)算? P (U) 與 ?P( A)上的一元運(yùn)算：表示 ?X中所有對(duì)象共同具有的屬性集合，表示具有 ?B中所有屬性的對(duì)象集合。

定義2[2]設(shè) ?(U, A, I) 是形式背景，令如果一個(gè)二元組? (X, B) 滿足則稱?(X, B)是一個(gè)形式概念。其中，X稱為形式概念的外延，?B 稱為形式概念的內(nèi)涵。

定義3[6]在形式背景?(U, A, I) 中，若?I( x ，a ) ? "1"表示對(duì)象 ?x 具有屬性 ?a，?I"0"表示對(duì)象x不具有屬性 ?a。在一些具有缺失值的信息系統(tǒng)中，用 ?I來(lái)表示對(duì)象? x是否具有屬性?a 未知，稱三元形式背景為不完備形式背景。

定義4[7]在一個(gè)不完備形式背景中，設(shè)，定義：為X中所有對(duì)象共同具有的屬性集合，為X中所有對(duì)象可能共同具有的屬性集合。

定義5[7]在一個(gè)不完備形式背景中。令和，兩個(gè)運(yùn)算和分別定義：

定義6[7]在一個(gè)不完備形式背景（U，A，｛1，？，0｝，I）中，?X ? 2U和 ?(B, C)? 2A? 2A，若 ?X ?(B, C)，以及? (B, C)?X，稱（X，（B，C））為形式背景（U，A，｛1，？，0｝，I）上的近似概念。近似概念（X，（B，C））的外延為X，（X，（B，C））的內(nèi)涵為（B，C）。

3 用合并方法構(gòu)造近似概念格的并行算法

3.1 算法基本思想

定義7[8]形式背景K1=（U1，A1，I）1和形式背景K2=（U2，A2，I）2，對(duì)于任意?12和任意滿足 ?uI1a ? uI2a，則稱K1和K2是一致的，否則稱K1和K2是不一致的。

定義8[8]如果形式背景K1=（U1，A1，I）1和K2=（U2，A2，I）2是一致的，那么它們的合并式：K1⊕K2=（U1∪U2，A1∪A2，I1∪I2），⊕稱為K1和K2的加運(yùn)算。如果A1=A2，稱K1±K2=（U1∪U2，A，I1∪I2）是兩個(gè)形式背景的縱向合并，如果U1=U2，稱K1±K2=（U，A1∪A2，I1∪I2）是兩個(gè)形式背景的橫向合并。

不完備形式背景? (U, A, {1,?,0},I) 中，若? x?X, a ?A，?I( x ，a ) ?"1"表示對(duì)象? x 具有屬性? a，?I ? x, a ??"0"表示對(duì)象? x 不具有屬性? a。?I ( x ，a ) ?"1"時(shí)，設(shè)K1=（U1，A1，I）1，?I ? x , a ??"0"時(shí)，設(shè)K2=（U2，A2，I）2。則有:若A1=A2，稱K1±K2=（U1∪U2，A，I1∪±I2）是兩個(gè)形式背景的縱向合并，若U1=U2，稱K1K2=（U，A1∪A2，I1∪I2）是兩個(gè)形式背景的橫向合并。

定理1[9]令U表示一個(gè)非空有限對(duì)象集，A表示一個(gè)非空有限屬性集。定義映射：

定義9將不完備形式背景? (U, A, {1,?,0},I)的未知值“？”全部替換為“0”得到形式背景（U，A，I1），全部替換為“1”得到形式背景（U，A，I2）。通過(guò)兩個(gè)完備形式背景的橫向合并或縱向合并可以得到不完備形式背景? (U, A, {1,?,0},I)的全部近似概念（X，（B，C））。

證明：（X，C）是形式背景（U，A，I2）的概念，由映射LIN和HIN得到? X LIN( X ),?(B, C ) ?HIN(B, C)，又由形式背景（U，A，I1）中的映射L1，H1和形式背景（U，A，I2）中的映射L2，H2滿足定理2的（L）、（H）、（LH1）、（LH2），得出L（2X）=C，H（2C）=X，根據(jù)定理2，得出?X (L1( X),L2(X))，又由L（1X）=B，有X□=（L（1X），L（2X））＝（B，C）。同理由H2≤H1，得到（B，C）□=X，則（X，（B，C））是近似概念。由此可知，可以通過(guò)合并得到全部近似概念。

證畢。

若（X1，（B1，C1））和（X2，（B2，C2））是一個(gè)不完備形式背景? (U, A, {1,?,0},I)的兩個(gè)近似概念，那么將不完備背景? (U, A, {1,?,0},I)中的未知值“？”全部替換為“0”得到形式背景（U，A，I1），將其中的未知值“？”全部替換為“1”得到形式背景（U，A，I2）。

設(shè)形式背景（U，A，I2）中的一個(gè)概念為（X2，B2），遍歷（U，A，I1）中的所有概念，通過(guò)判斷和（X2，B2）的關(guān)系來(lái)找到下一個(gè)概念。三個(gè)判斷條件：

（1）若（U，A，I1）中找到概念（X1，B1）（其中（X1=X2），若B1=B2，則將概念（X1，（B1，B2））加入到近似概念格中。

（2）若（U，A，I1）中找到概念（X1，B1）（其中X1=X2），若B1≠B2，則將概念 ?(X1,(B1,?))加入到近似概念格中。

（3）若（U，A，I1）中沒(méi)有找到概念（X1，B1）（其中X1=X2），則將概念? (X1,(?,B2))加入到近似概念格中。

定義10若（U，A，I2）中所有概念為（X1，B1），（X2，B2），（X3，B3）…（Xn，Bn）通過(guò)（Xn，Bn）遍歷（U，A，I1）中的所有概念得到近似概念的集合為? {a ppron}，?{a ppro1}{ appro2} {a ppron}，可以得到不完備形式背景? (U, A, {1,?,0},I)的所有近似概念。

根據(jù)定義10，可以將近似概念格轉(zhuǎn)化為n個(gè)子集的并集，說(shuō)明了并行合并算法在MapReduce架構(gòu)中實(shí)現(xiàn)是可行的。

3.2 算法描述

將不完備背景 ?(U, A, {1,?,0},I)中的未知值“？”全部替換為“0”得到完備形式背景（U，A，I1），將其中的未知值“？”全部替換為“1”得到完備形式背景（U，A，I2）。采用MRGanter+算法生成兩個(gè)概念格[5,10-13]。由形式背景（U，A，I1）生成的概念格為概念格a,將概念格a輸出在文件file1中；由形式背景（U，A，I2）生成的概念格為概念格b,將概念格b輸出在文件file2中。

將輸入文件設(shè)為file1,通過(guò)Map函數(shù)將概念格a中所有的概念都加入到哈希表concept1[14]，其中概念格a屬性為哈希表的key,概念為哈希表的value，算法描述如下：

算法1 把概念格a加入到哈希表中

Map.把（U，A，I1）所有概念加入到哈希表concept1中Create Hashtable concept1//在Map函數(shù)之前建立哈希表Concept1

Input（:objects,concepts）.//輸入完備概念格1的屬性和概念

Output（:null）.//把結(jié)果加入哈希表，沒(méi)有輸出

1:concept.key←extension；//將概念的外延加入到哈希表

2:concept.value←intension;//將概念的內(nèi)涵加入到哈希表

3:Return null;//Map函數(shù)輸出為空值，把值加入到哈希表concept1中。

將輸入文件設(shè)為file2，通過(guò)Map函數(shù)按行讀取概念格b中的概念。通過(guò)哈希表concept1判斷概念的外延是否存在于concept1中，如果不存在，就加入概念格b到近似概念格中；如果存在，判斷內(nèi)涵是否和概念格b相同，相同就把合并的概念格加入到近似概念格中，如果內(nèi)涵不相同就把概念格1中的概念加入到近似概念格中。算法描述如下：

算法2 合并生成近似概念格

Map.把概念格進(jìn)行合并

Input:（objects，concept2）//輸入完備概念格2的對(duì)象和概念

Output:ApproConcept.//近似概念格外延為key,內(nèi)涵為value

1:get object in concept1;//從哈希表concept1讀取一個(gè)object，object即是extension

2:if extension is exist

3:if（concept2.Intension is equal to concept1.Intension）//如果外延相等

4:ApproConcept←（object，（concept1.Intension，concept2.Intension））；//進(jìn)行合并

ENDIF

5:else

6:?ApproConcept ?（object,( c oncept1. I ntension,?));ENDELSE

7:else

8:?ApproConcept? (o bject, (?,c oncept2.Intension））；ENDIF

9:Return ApproConcept；

Reduce.輸出所有Map中Key和Value

Input:（key，value）；//Map中Key和Value

Output（:key，value）；

1:context←（key，value）；

2:Return context；

4 一種增量式并行建格算法

4.1 算法基本思想

定理2[7]在一個(gè)不完備形式背景?(U, A, {1,?,0},I)中，令和其中Q和T是兩個(gè)索引集。那么：

推論1[7]在一個(gè)不完備形式背景中那么?( X ,X )和（（B， C）□，（B，C）□□）是的兩個(gè)近似概念。

證明：通過(guò)定理2和定義6可以得到推論1。

定理3[7]若是一個(gè)不完備形式背景，則偏序集在下確界? (?)和上確界 ?(?)作為一個(gè)完備格的近似概念分別為：

證明：通過(guò)推論1和定理2可以得出定理3。

近似概念格的結(jié)構(gòu)特點(diǎn)與經(jīng)典概念格的結(jié)構(gòu)特點(diǎn)一致。在一種經(jīng)典概念格構(gòu)造算法的基礎(chǔ)上[15]，文獻(xiàn)[7]提出了一種近似概念格串行增量式算法。采用增量算法的特點(diǎn)是將插入的概念與已有的近似概念進(jìn)行比較，滿足條件就生成新的近似概念。在串行增量式算法基礎(chǔ)上提出了一種增量式并行構(gòu)造算法。

設(shè) ??表示已生成的近似概念， 表示第1到第n個(gè)屬性，第一個(gè)近似概念加入到 ??中，設(shè) ?S??，?(X ,(B, C))為從S中取出的一個(gè)近似概念。

?Xi中 ?i 不為1時(shí)，設(shè)?S??，遍歷S，（X，（B，C））為從S中取出的一個(gè)近似概念。判斷條件如下：

（1） 若那么將（X∪xi，（B，C））加入到 ??中，并且將（x，（B，C））從??中移除。如果滿足到步驟2，否則到步驟3。

定義11若在屬性為xi中找到的近似概念集合為 ?approi,?{ appro1} {a ppro2}{ approi}可以得到不完備形式背景? (U, A, {1,?,0},I)所有的近似概念。

根據(jù)定義11，可以把近似概念格分為很多子集的并集，說(shuō)明了將增量式算法在并行環(huán)境中運(yùn)行是可行的。

4.2 算法描述

因?yàn)镸apReduce架構(gòu)是按行讀取，求出每一個(gè)屬性的上近似內(nèi)涵和下近似內(nèi)涵，并把屬性的上近似內(nèi)涵和下近似內(nèi)涵放在一行。通過(guò)一次Map和Reduce生成所有近似概念。

算法5生成所有的近似概念。算法5中Map類生成每一行（即每個(gè)屬性）的內(nèi)涵，其中內(nèi)涵包括上近似內(nèi)涵和下近似內(nèi)涵，每個(gè)屬性的近似概念保存在一行之中，方便Reduce函數(shù)的計(jì)算[16]。在Reduce類之前，首先構(gòu)造一個(gè)Hash表concept1。Reduce類中把第一次的近似概念加入concept1,然后生成一個(gè)list1，把concept1中的元素放入list1。遍歷list1，進(jìn)行判斷，如果滿足條件就插入新的元素。到了最后一個(gè)近似概念時(shí)，插入? {?,{U, U}}。

表1 函數(shù)的描述

算法3找到對(duì)象的下近似內(nèi)涵

Input:(objecti,Xi).//Xi表示第i個(gè)屬性,objecti表示第i個(gè)屬性中所有的bool值

Output:DownIntensioni

1:if objectij=1 then

2:? DownO?j;//如果在第i個(gè)屬性中第j個(gè)對(duì)象的boolean值為1，那么就將j的下標(biāo)加入到DownO中

3:? OConcept ?findOconcept? D ownO ?;//找到Downobject的內(nèi)涵

4：?A Concept ?findAConcep（t OConcept）； //找到OConcept的外延

5：?U PIntension ?findOConcept? AConcept ?；//找 到AConcept的內(nèi)涵

ENDIF

6:Return ?UPIntension//返回下近似內(nèi)涵

算法4 找到對(duì)象的上近似內(nèi)涵

Input: ?(o bjecti, Xi).// ?Xi表示第 i個(gè)屬性, objecti表示第i個(gè)屬性中所有bool值

Output:?UPIntensioni

1:if? objectij? 1?||?o bjectij= ?"?"then

2:? ?Downobject???j；//如果在第i個(gè)屬性中第j個(gè)對(duì)象的boolean值為1或者為“？”，那么就將j的下標(biāo)加入到Downobject中

3:?O Concept???f indOconcept? D ownobject?；//如果滿足?((D ownIntensioni?B,U PIntensioni?C)?(D ownIntensio ni, UPIntension）i，則找到Downobject的內(nèi)涵??

4:? AConcept?? findAConcep（t OConcept）；//找 到OConcept的外延

5:? UPIntension???f indOConcept? A Concept?.//找 到AConcept的內(nèi)涵

6:Return ?UPIntension//返回上近似內(nèi)涵

最后通過(guò)算法4生成所有的近似概念格，用Map函數(shù)生成所有概念的上近似和下近似，用Reduce函數(shù)生成所有的近似概念。

算法5 生成所有的近似概念（主程序）

Map.找到對(duì)象的上近似內(nèi)涵和下近似內(nèi)涵Input:?( o bjecti?,Xi).//?Xi表 示第i個(gè)屬性, ?o bjecti表示第i個(gè)屬性中所有bool值

Output:? (Xi,(?D ownIntensioni,? U PIntensioni)).

1:?D ownIntensioni???f indDownConcepti on(o bjecti); //findDownConception的函數(shù)實(shí)現(xiàn)在算法3

2:? UPIntensioni???findUpConception?(Xi);//findUpConception的函數(shù)實(shí)現(xiàn)在算法4

3:Return ?(Xi,?(D ownIntensioni,?U PIntensioni))；

Reduce.生成所有的近似概念

Create Hashtable ?concept1//在Reduce函數(shù)之前建立哈希表

Input: ?(Xi,?(D ownIntensioni,?U PIntensioni)).//輸入Map函數(shù)輸出的key和value

Output: ?concept1．//屬性為key,概念的外延和內(nèi)涵為value

1:foreach?concept1

2:if ?concept1is null then

3:? concept1??(Xi,?(D ownIntensioni,?U PIntensioni))；//遍歷哈希表，如果為空就加入第一個(gè)元素

ENDIF

4: ?list1???c oncept1；//新建list類型list1，并賦值

5:foreach ?(B, C) in ?list1do //遍歷list1

6:if? (DownIntensioniB,UPI nte niC) (,C)then

7:concept1 ?X ?XiB, C

ENDIF

8:if?((D ownIntensioni,UPIntensioni) ??(DownIntensionj,UPIntensionj))(?j?i)then

9:?concept1 ?(Xi,(DownIntensioni,UPIntensioni))

ENDIF

10:else

11:if?((DownIntensioni?B,UPIntensioni??C )?(DownIntensioni,（DownIntensioni，?UPIntensioni)(?j?i )then

12:?concept1 ?(X?{Xi},(DownIntensioni??B,UPInte-nsioni?C B,UPIntensioni?C))

ENDIF

ENDELSE

13:if ?(D ownIntensioni,UPIntensioni)??(DownIntensionj,UPIntensionj)(?j?i) then

14:?concept1 ?(Xi（,DownIntensioni, UPIntensioni))ENDIF

15:if ?Xiis lastthen

16:? concept1 ?(?,(A,A))//如果是最后一個(gè)近似概念，將概念加入哈希表

ENDIF

17:return ?concept1

5 算法實(shí)驗(yàn)分析

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

實(shí)驗(yàn)數(shù)據(jù)集 ElectricityLoadDiagrams20112014 Data Set（簡(jiǎn)稱LD2011_2014）來(lái)自http://archive.ics. uci.edu/ml/datasets.html，數(shù)據(jù)集描述如表2所示。試驗(yàn)環(huán)境為Hadoop集群，該集群由1個(gè)主控制節(jié)點(diǎn)和10個(gè)計(jì)算節(jié)點(diǎn)組成。每個(gè)節(jié)點(diǎn)的硬件配置為Intel? Pentium? D CPU2.80GHz，2GB內(nèi)存和150G硬盤。操作系統(tǒng)為 LinuxCentos 6.3，JDk為 Java 1.7.0_17，Eclipse采用32位的Linux版本eclipse-3.3.2。MapReduce框架基于Hadoop平臺(tái)1.2.1版本，其他采用系統(tǒng)默認(rèn)設(shè)置。

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

第一次試驗(yàn)從數(shù)據(jù)集LD2011_2014中選定對(duì)象數(shù)為15000，屬性數(shù)為100，隨機(jī)生成20%的缺失數(shù)據(jù)，將新數(shù)據(jù)集命名為L(zhǎng)D1。從LD1中選取1000個(gè)對(duì)象，每次增加1000個(gè)對(duì)象，增加到10000個(gè)對(duì)象，一共10次，最后一次對(duì)象為15000個(gè)對(duì)象,其中選取屬性數(shù)固定為100，試驗(yàn)結(jié)果如圖1-2所示，其中并行算法運(yùn)行的節(jié)點(diǎn)為10個(gè)。

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

圖1 對(duì)象數(shù)從1000到6000，屬性數(shù)100，數(shù)據(jù)缺失率為20%時(shí)的試驗(yàn)結(jié)果

第二次試驗(yàn)從數(shù)據(jù)集LD2011_2014中選取10000個(gè)對(duì)象，150個(gè)屬性，隨機(jī)生成20%的缺失數(shù)據(jù)，將新數(shù)據(jù)集命名為L(zhǎng)D2，分別運(yùn)行得出在不同節(jié)點(diǎn)情況下兩種并行算法的運(yùn)行時(shí)間，試驗(yàn)結(jié)果如圖3所示。

第三次試驗(yàn)從數(shù)據(jù)集 LD2011_2014中選取30000個(gè)對(duì)象，320個(gè)屬性，隨機(jī)生成20%的缺失數(shù)據(jù)，將新數(shù)據(jù)集命名為L(zhǎng)D3，分別求出在不同節(jié)點(diǎn)情況下兩種算法的運(yùn)行時(shí)間。試驗(yàn)結(jié)果如表3所示。

圖2 對(duì)象數(shù)從1000到15000，屬性數(shù)為100，數(shù)據(jù)缺失率為20%時(shí)的試驗(yàn)結(jié)果

圖3 節(jié)點(diǎn)數(shù)從1到10，對(duì)象數(shù)為10000，屬性數(shù)為150，數(shù)據(jù)缺失率為20%時(shí)的試驗(yàn)結(jié)果

第四次試驗(yàn)從數(shù)據(jù)集LD2011_2014中選取80000個(gè)對(duì)象，200個(gè)屬性，隨機(jī)生成20%的缺失數(shù)據(jù)，將新的數(shù)據(jù)集命名為L(zhǎng)D4，分別求出在不同節(jié)點(diǎn)情況下兩種并行算法的運(yùn)行時(shí)間。試驗(yàn)結(jié)果如表3所示。

第五次試驗(yàn)從數(shù)據(jù)集LD2011_2014中選取80000個(gè)對(duì)象，200個(gè)屬性，隨機(jī)生成30%的缺失數(shù)據(jù)，將新的數(shù)據(jù)集命名為L(zhǎng)D5，分別求出在不同節(jié)點(diǎn)情況下兩種并行算法的運(yùn)行時(shí)間。試驗(yàn)結(jié)果如表3所示。

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

如圖1-2所示，對(duì)象數(shù)數(shù)據(jù)量較小時(shí)，串行算 法比并行算法運(yùn)行更快，增量式并行算法與合并并行算法運(yùn)行時(shí)間相差不大；當(dāng)數(shù)據(jù)量具有一定規(guī)模時(shí)，并行算法的運(yùn)行時(shí)間開(kāi)始少于串行算法的運(yùn)行時(shí)間，并且隨著數(shù)據(jù)集的增大，差距越來(lái)越明顯；隨著數(shù)據(jù)集的增大，增量式并行算法運(yùn)行時(shí)間相對(duì)合并算法差距增大。如表3所示，當(dāng)數(shù)據(jù)集規(guī)模大時(shí)，隨著節(jié)點(diǎn)數(shù)的增加，增量式并行算法的運(yùn)行時(shí)間相比合并并行算法運(yùn)行時(shí)間的優(yōu)勢(shì)更加明顯。

對(duì)比表3中LD3和LD4數(shù)據(jù)集，雖然數(shù)據(jù)集LD4相對(duì)LD3對(duì)象數(shù)增加,但是屬性數(shù)LD4相對(duì)LD3減少，導(dǎo)致數(shù)據(jù)集LD4的運(yùn)行時(shí)間低于LD3的運(yùn)行時(shí)間。

對(duì)比表3中LD4和LD5數(shù)據(jù)集。數(shù)據(jù)集LD4和LD5的對(duì)象數(shù)和屬性數(shù)相同，但是數(shù)據(jù)集LD4和LD5的數(shù)據(jù)缺失率不同，導(dǎo)致LD5相對(duì)LD4的運(yùn)行時(shí)間大幅度增加。

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

針對(duì)不完備形式背景，本文提出了MapReduce框架下的近似概念格并行合并算法和增量式并行算法。并行合并算法生成兩個(gè)經(jīng)典概念格后進(jìn)行合并，增量式并行算法通過(guò)插入對(duì)象的內(nèi)涵與已有的近似概念求交集和比較生成新的近似概念。試驗(yàn)結(jié)果表明，在數(shù)據(jù)規(guī)模較大時(shí)，并行算法相對(duì)串行算法大幅度減少了運(yùn)行時(shí)間，計(jì)算節(jié)點(diǎn)越多并行算法相對(duì)串行算法的優(yōu)勢(shì)越明顯。并行增量式算法比并行合并算法效率更高，數(shù)據(jù)規(guī)模越大，并行增量式算法優(yōu)勢(shì)越明顯；節(jié)點(diǎn)越多，并行增量式算法優(yōu)勢(shì)越明顯。并行合并算法相比增量式并行算法運(yùn)行時(shí)間較慢。

構(gòu)造近似概念格的下一步工作是不完備形式背景中知識(shí)的獲取和決策分析，進(jìn)一步將并行算法應(yīng)用到這些工作中能夠提高算法運(yùn)行的效率。

[1]程廣,王曉峰.基于MapReduce的并行關(guān)聯(lián)規(guī)則增量更新算法[J].計(jì)算機(jī)工程,2016,42(2):21-25. Cheng Guang,Wang Xiaofeng.Incremental Updating Algorithmof Parallel Association Rule Based on MapReduce[J]．Computer Engineering,2016，42(2):21-25,32.

[2]Stumme G.Formal Concept Analysis[J].Electronic Notes in Discrete Mathematics,1999,2(3):199-200.

[3]Ganter B,Wille R.Formal concept analysis:mathematical foundations[M].Springer Science&Business Media,2012.

[4]Kuznetsov S O.Machine Learning on the Basis of Formal Concept Analysis[J].Automation&Remote Control,2001, 62(10):1543-1564.

[5]Xu B,Fréin R D,Robson E,et al.Distributed Formal Concept Analysis Algorithms Based on an Iterative MapReduce Framework[M].Formal Concept Analysis.Springer Berlin Heidelberg,2012:292-308.

[6]Wille R.RESTRUCTURING LATTICE THEORY:AN APPROACH BASED ON HIERARCHIES OF CONCEPTS[C]. International Conference on Formal Concept Analysis. Springer-Verlag,2009:445-470.

[7]Li J,Mei C,LvY.Incomplete decision contexts:Approximate concept construction,rule acquisition and knowledge reduction[J].International Journal of Approximate Reasoning, 2013,54(54):149-165.

[8]智慧來(lái),智東杰,劉宗田.概念格合并原理與算法 [J].電子學(xué)報(bào),2010,38(2):455-459. Zhi H L,Zhi D J,Liu Z T.Theory and Algorithm of Concept Lattice Union [J].Acta Electronica Sinica,2010,38(2): 455-459.

[9]張慧雯,劉文奇,李金海.不完備形式背景下近似概念格的公理化方法[J].計(jì)算機(jī)科學(xué),2015,42(6):67-70. Zhang Huiwen,Liu Wenqi,Li Jinhai.Axiomatic Characterizations of Approximate Concept Lattices in Incomplete Contexts[J].Computer Science,2015,42(6):67-70.

[10]Ganter B.Two Basic Algorithms in Concept Analysis[C]. Formal Concept Analysis,International Conference,Icfca 2010,Agadir,Morocco,March 15-18,2010.Proceedings. 2010:312-340.

[11]Dean J,Ghemawat S.MapReduce:Simplified Data Processing on Large Clusters[J].In Proceedings of Operating Systems Design and Implementation(OSDI),2004,51(1): 107-113..

[12]Jin W,Wang C.Iteration MapReduce framework for evolution algorithm[J].Journal of Computer Applications,2013, 33(12):3591-3595.

[13]Rosen J,Polyzotis N,Borkar V,et al.Iterative MapReduce for Large Scale Machine Learning[J].Computer Science, 2013.

[14]Ruixia LI,Liu R,Zhou X.Optimization on MapReduce algorithm based on Hash table[J].Journal of Shandong University(Natural Science),2015,50(7):66-70.

[15]Godin R,Missaoui R,Alaoui H.INCREMENTAL CONCEPT FORMATION ALGORITHMS BASED ON GALOIS (CONCEPT)LATTICES[J].Computational Intelligence, 2010,11(2):246–267.

[16]Tonsmann G.Sequential and Parallel Rule Extraction from a Concept Lattice[C].International Conference on Data Mining,Dmin 2006,Las Vegas,Nevada,Usa,June.2006.

Parallel Constructing Algorithm of Approximation Concept Lattice Based on MapReduce Framework

Tan Fulin,Jiang Lin

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

Formal context with missing values is called incomplete context,and the concept lattice expansion model in incomplete context is called approximation concept lattice.In the approximation concept lattice construction,serial algorithm is low efficiency in the case of large data and parallel constructing algorithm under complete context is not appropriate for incomplete context.In order to solve these problems,through deep analysis of the characteristics of approximation concept lattice,the paper introduces two parallel constructing algorithms of approximation concept lattice based on MapReduce framework,including a parallel union algorithm and a parallel constructing algorithm based on an incremental constructing algorithm.The experimental results demonstrated that the two constructing algorithms had improved the efficiency of construction comparing with the serial algorithm.

Incomplete context；Approximation concept lattice；Construction of concept lattice；MapReduce framework；Parallel constructing algorithm

10.3969/j.issn.1002-2279.2017.02.011

TP301.6

A

1002-2279-（2017）02-0045-07

國(guó)家自然科學(xué)基金地區(qū)基金（KKGD201203003）;云南省教育廳重大項(xiàng)目（KKJI201203002）

譚富林（1992-），男，湖南省郴州市宜章縣人，碩士研究生，主研方向：并行數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)。

姜麟（1969-），男，副教授，主研方向：智能計(jì)算和并行計(jì)算。

2016-10-09