譚富林，姜 麟

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

·微機(jī)軟件·

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

譚富林，姜 麟

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

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

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

1 引言

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

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

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

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

2 近似概念格基本概念

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

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

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

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

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

定義5[7]在一個不完備形式背景中。令和，兩個運算和分別定義：

定義6[7]在一個不完備形式背景（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，對于任意?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的加運算。如果A1=A2，稱K1±K2=（U1∪U2，A，I1∪I2）是兩個形式背景的縱向合并，如果U1=U2，稱K1±K2=（U，A1∪A2，I1∪I2）是兩個形式背景的橫向合并。

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

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

定義9將不完備形式背景? (U, A, {1,?,0},I)的未知值“？”全部替換為“0”得到形式背景（U，A，I1），全部替換為“1”得到形式背景（U，A，I2）。通過兩個完備形式背景的橫向合并或縱向合并可以得到不完備形式背景? (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））是近似概念。由此可知，可以通過合并得到全部近似概念。

證畢。

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

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

（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）中沒有找到概念（X1，B1）（其中X1=X2），則將概念? (X1,(?,B2))加入到近似概念格中。

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

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

3.2 算法描述

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

將輸入文件設(shè)為file1,通過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é)果加入哈希表，沒有輸出

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

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

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

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

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

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

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

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

1:get object in concept1;//從哈希表concept1讀取一個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]在一個不完備形式背景?(U, A, {1,?,0},I)中，令和其中Q和T是兩個索引集。那么：

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

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

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

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

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

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

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

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

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

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

4.2 算法描述

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

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

表1 函數(shù)的描述

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

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

Output:DownIntensioni

1:if objectij=1 then

2:? DownO?j;//如果在第i個屬性中第j個對象的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 找到對象的上近似內(nèi)涵

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

Output:?UPIntensioni

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

2:? ?Downobject???j；//如果在第i個屬性中第j個對象的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)涵

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

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

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

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

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

2:? UPIntensioni???findUpConception?(Xi);//findUpConception的函數(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))；//遍歷哈希表，如果為空就加入第一個元素

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))//如果是最后一個近似概念，將概念加入哈希表

ENDIF

17:return ?concept1

5 算法實驗分析

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

實驗數(shù)據(jù)集 ElectricityLoadDiagrams20112014 Data Set（簡稱LD2011_2014）來自http://archive.ics. uci.edu/ml/datasets.html，數(shù)據(jù)集描述如表2所示。試驗環(huán)境為Hadoop集群，該集群由1個主控制節(jié)點和10個計算節(jié)點組成。每個節(jié)點的硬件配置為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平臺1.2.1版本，其他采用系統(tǒng)默認(rèn)設(shè)置。

5.2 算法效果及驗證

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

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

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

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

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

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

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

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

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

表3 并行算法運行時間(s)

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

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

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

6 結(jié)束語

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

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

[1]程廣,王曉峰.基于MapReduce的并行關(guān)聯(lián)規(guī)則增量更新算法[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]智慧來,智東杰,劉宗田.概念格合并原理與算法 [J].電子學(xué)報,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ī)科學(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

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

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

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

2016-10-09