MapReduce框架下近似概念格的并行構造算法*

譚富林，姜 麟

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

·微機軟件·

MapReduce框架下近似概念格的并行構造算法*

譚富林，姜 麟

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

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

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

1 引言

MapReduce是Google公司提出的一種編程模型，廣泛應用于數據挖掘、信息提取、機器學習等場景。MapReduce分布式處理框架具有容錯控制、細節隱藏、伸縮性好等優點[1]。

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

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

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

2 近似概念格基本概念

定義1[2]? K ?(U, A, I )為一個形式背景，其中?U 為對象集；? A 為屬性集；?I 為 ?U 和 ?A之間的二元關系；若 ?(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]設 ?(U, A, I) 是形式背景，令如果一個二元組? (X, B) 滿足則稱?(X, B)是一個形式概念。其中，X稱為形式概念的外延，?B 稱為形式概念的內涵。

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

定義4[7]在一個不完備形式背景中，設，定義：為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））的內涵為（B，C）。

3 用合并方法構造近似概念格的并行算法

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"時，設K1=（U1，A1，I）1，?I ? x , a ??"0"時，設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，根據定理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）。

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

（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)的所有近似概念。

根據定義10，可以將近似概念格轉化為n個子集的并集，說明了并行合并算法在MapReduce架構中實現是可行的。

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中。

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

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

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

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

Output（:null）.//把結果加入哈希表，沒有輸出

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

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

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

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

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

Map.把概念格進行合并

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

Output:ApproConcept.//近似概念格外延為key,內涵為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））；//進行合并

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。

近似概念格的結構特點與經典概念格的結構特點一致。在一種經典概念格構造算法的基礎上[15]，文獻[7]提出了一種近似概念格串行增量式算法。采用增量算法的特點是將插入的概念與已有的近似概念進行比較，滿足條件就生成新的近似概念。在串行增量式算法基礎上提出了一種增量式并行構造算法。

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

?Xi中 ?i 不為1時，設?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)所有的近似概念。

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

4.2 算法描述

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

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

表1 函數的描述

算法3找到對象的下近似內涵

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

Output:DownIntensioni

1:if objectij=1 then

2:? DownO?j;//如果在第i個屬性中第j個對象的boolean值為1，那么就將j的下標加入到DownO中

3:? OConcept ?findOconcept? D ownO ?;//找到Downobject的內涵

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

5：?U PIntension ?findOConcept? AConcept ?；//找 到AConcept的內涵

ENDIF

6:Return ?UPIntension//返回下近似內涵

算法4 找到對象的上近似內涵

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的下標加入到Downobject中

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

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

5:? UPIntension???f indOConcept? A Concept?.//找 到AConcept的內涵

6:Return ?UPIntension//返回上近似內涵

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

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

Map.找到對象的上近似內涵和下近似內涵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的函數實現在算法3

2:? UPIntensioni???findUpConception?(Xi);//findUpConception的函數實現在算法4

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

Reduce.生成所有的近似概念

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

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

Output: ?concept1．//屬性為key,概念的外延和內涵為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 數據集及實驗環境描述

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

5.2 算法效果及驗證

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

表2 數據集的描述

圖1 對象數從1000到6000，屬性數100，數據缺失率為20%時的試驗結果

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

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

圖2 對象數從1000到15000，屬性數為100，數據缺失率為20%時的試驗結果

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

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

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

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

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

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

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

6 結束語

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

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

[1]程廣,王曉峰.基于MapReduce的并行關聯規則增量更新算法[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].電子學報,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].計算機科學,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

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

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

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

2016-10-09