孫　佳　柴玉梅

(鄭州大學信息工程學院　河南 鄭州 450001)

?

基于同層節(jié)點集劃分的模糊概念格并行構造算法

孫佳柴玉梅

(鄭州大學信息工程學院河南 鄭州 450001)

摘要形式概念分析理論在諸多計算機領域得到廣泛應用。模糊概念格的構造仍是其在應用過程中的一個主要問題。為提高模糊概念格的構造效率，對串行算法進行并行化改造，提出模糊概念格的并行構造算法。該算法對節(jié)點進行層次劃分，給出了同層節(jié)點的定義，得出同層節(jié)點構造任務相互獨立的重要性質，并引入映射函數簡化搜索空間的遍歷，提高搜索模糊概念格的效率，并行構造模糊概念格，達到了提高構造效率的目的。實驗表明該算法在面對大規(guī)模的構造任務時，具有良好的性能。

關鍵詞模糊概念格構造模糊集節(jié)點分層并行算法

0引言

形式概念分析FCA(Formal Concept Analysis)由德國學者Wille提出的一種基于形式背景表示形式概念的模型，即概念格[1]。這種概念層次結構是數據分析及規(guī)則提取的有效工具，已被廣泛應用于文本處理，知識表達，知識挖掘，專家系統(tǒng)等領域[2-6]。但是在許多應用中，大多數信息都是模糊的、復雜的，傳統(tǒng)的形式概念分析很難表達這些模糊的、不確定的信息。為解決這個問題，Burusco等人提出了L-模糊形式背景[7]，并將Zadeh的模糊集合理論與形式概念分析相結合，構造模糊形式概念分析FFCA(Fuzzy formal concept analysis)，這一新研究領域[7,8]。在L-模糊形式背景規(guī)模較大時，從L-模糊形式背景構造模糊概念格通常會引起組合爆炸，模糊概念格的構造效率是其在應用過程中的一個主要問題。

對基本算法的并行化改造被用來作為提高構造效率的有效途徑，多名研究人員通過這種方法取得了并行構造算法的研究成果。在經典概念格方面，文獻[9]對形式背景進行劃分，運用概念格合并出理論，提出了一種基于子概念格合并的并行構造算法；文獻[10]提出并行化Next Closure算法，該算法將形式背景通過字典序劃分為不相交的搜索空間，然后由不同線程分別產生概念集合；文獻[11]提出了Close By One算法的并行版本，在原始CBO算法思想上進行的并行改造，多個線程并行處理，提前避免產生重復概念，無需進行線程間通信，而且無需進行盲目的空間搜索。這些經典概念格的并行構造算法都是在串行算法基礎上改造而來。在模糊概念格方面，目前并行構造算法的研究成果較少。文獻[12] 在文獻[13] 模糊概念構造算法的基礎上設計模糊概念格并行算法。該算法將模糊集合組合空間映射為自然數空間，利用并行計算能力并行構造模糊概念，缺點是它并沒有產生格結構，在實際應用中具有一定的局限性。Belohlavek在文獻[14]中設計了另一種模糊概念格構造算法，直接構造出L-模糊概念格。本文在文獻[14]的基礎上，進行并行化改造，設計出一種模糊概念格的并行構造算法。

本文設計的模糊概念格的并行構造算法將模糊概念格進行分層，利用同層節(jié)點構造子節(jié)點時任務相互獨立的重要性質，進行任務分配與結果集成。并引進映射函數簡化搜索空間的遍歷，提高模糊概念格構造效率。

1相關概念

本節(jié)簡要介紹所需要的基本概念，對模糊概念格的詳細描述見參考文獻[8,13]。

模糊形式背景由四元組(X,Y,I,L)表示，其中X為模糊對象集合，Y為模糊屬性集合，I為(X,Y)上的二元模糊關系，L為真值集合，取值范圍是[0,1]。對于任意的A∈LX，B∈LY，Belohlavek定義了它們之間的模糊伽羅瓦聯(lián)系：

A↑(y)=∧x∈X(A(x)→I(x,y))

(1)

B↓(x)=∧y∈Y(B(y)→I(x,y))

(2)

其中，可認為是A↑(y)模糊集合A中對象共有屬性y的真值度；而B↓(x)認為是對象x擁有模糊屬性集合B中所有屬性的真值度。二元組(A,B)∈LX×LY滿足A↑=B，B↓=A，則稱(A,B)為模糊形式背景的一個模糊概念。由模糊概念格的格結構特征，對于其中的每一個模糊概念都稱為是一個模糊概念節(jié)點，通常簡稱為節(jié)點。模糊概念之間的偏序關系由模糊集合包含關系來確定,對于任意兩個模糊概念C1(x1,y1)與C2(x2,y2)，如果x1?x2(或y1?y2)則有C1 (x1,y1)≤C2 (x2,y2)。模糊形式背景K=(X,Y,I,L)上的所有模糊概念及其上的偏序關系構成一個偏序集(C,≤)，是一個完備格，稱之為模糊概念格。

定義1父子節(jié)點在模糊概念格的格結構中，模糊概念C1(A1,B1)和C2(A2,B2)，如果C1≤C2且不存在模糊概念C3(A3,B3)C1≤C3≤C2，則稱C2為C1的直接父節(jié)點，相應的C1稱為C2直接子節(jié)點。

對于一個模糊概念格，其由全部的模糊概念以及父子關系構成。根據這種結構特點，每個模糊概念在模糊概念格內都具有深度特征。

定義2節(jié)點深度在模糊概念格中，模糊概念節(jié)點C1(A,B)到最小內涵模糊概念節(jié)點C2(X,?)之間最短路徑上有k-1個模糊概念相鏈接，記模糊概念C1(A,B)的深度為K，記為Dep(C1)=K。

模糊概念格內每個節(jié)點都具有唯一深度，由深度可以很好地描述其在模糊概念格內的結構特征。

定理1模糊概念格內每個節(jié)點的深度唯一。

證明：任意節(jié)點C的深度Dep(C)=K1，根據定義節(jié)點C到最小內涵節(jié)點之間最短路徑鏈的長度為k1-1；若其深度有多值，假設C的另一深度Dep(C)=K2(K2≠K1)，根據定義此時最短路徑鏈的長度為k2-1。若k2>k1(或k1>k2)，k2-1(或k1-1)的路徑長度不是最短，與定義矛盾，故模糊概念格內每個節(jié)點的深度唯一。

模糊概念格的結構具有明顯的層次性，根據節(jié)點深度可以對模糊概念進行層次劃分，每個節(jié)點都具有相應的層次。

定義3節(jié)點層次模糊概念C1(A,B)的深度為k，則稱模糊概念C1(A,B)在模糊概念格中層次為k。

推論1在模糊概念格中，每個節(jié)點都具有唯一的層次。

證明：節(jié)點的深度決定節(jié)點的層次，根據定理1，在模糊概念格內每個節(jié)點的深度唯一，故可證每個節(jié)點具有唯一的層次。

在模糊概念格內，模糊概念具有明顯的深度、層次特征，由此也可以更清楚地表示出模糊概念格的層次結構特點。

2串行構造算法

基于對模糊概念格的定義，文獻[14]中給出模糊概念串行格構造算法。下面簡要介紹計算方法。

(3)

最終B的父節(jié)點的集合為：

(4)

B*表示B的父節(jié)點集合，具體的證明在參考文獻中已有詳細描述。結合父節(jié)點集合計算方法，模糊概念格的串行構造算法(Fuzzy Lattice算法)具體過程如下：

Step1 初始化F=?，從最小內涵B=?開始；

Step3 從父節(jié)點集合內選取一個節(jié)點E，搜索模糊概念格F判定是否已存在，若存在只需記錄父子關系；若不存在將E插入F并生成格結構，且E作為父節(jié)點調用式(4)計算其子節(jié)點集合N；

Step4 父節(jié)點集合內的每個節(jié)點遞歸執(zhí)行第三步，直到全部計算完畢為止，求出所有的模糊概念并形成格結構。

分析Fuzzy Lattice算法，其從最小內涵開始，由式(4)逐個計算節(jié)點的子節(jié)點集合，并形成格結構，其時間復雜度為Τ1=O(|X|×|Y|2×|F|),其中|F|為模糊概念格中模糊概念的總數量[14]。在實際應用中，模糊形式背景的規(guī)模較大，|X|和|Y|都會增大，模糊概念的數量|F|大規(guī)模增大，構造模糊概念格的時間指數倍增加，構造效率低下，此時Fuzzy Lattice算法具有一定的局限性。

進一步分析Fuzzy Lattice算法過程，其逐層計算節(jié)點的子節(jié)點集合，并構造模糊概念格，且計算每個子節(jié)點集合的任務相互獨立。此時，獨立的計算任務為設計并行構造算法提供了思路，進而由并行算法提高模糊概念格的構造效率，解決其在實際應用中的問題。

3模糊概念格并行構造算法

根據上節(jié)Fuzzy Lattice算法，本節(jié)對其進行并行化改進，設計出模糊概念格并行構造算法ParaFuLa(Parallel Fuzzy Lattice)。下面詳細介紹相關的理論基礎和算法。

3.1理論基礎

研究模糊概念格的結構知其具有明顯的層次性，根據層次性可以對模糊概念進行層次劃分，從而更深入地研究模糊概念格的構造特點，設計相應的并行算法，提高構造效率。下面對以上分析結果進行形式化證明。

定義4同層節(jié)點兩個模糊概念C1和C2具有相同層次，則C1和C2互為同層節(jié)點。

命題1同層節(jié)點在構造父節(jié)點時，任務相互獨立。

證明節(jié)點在構造父節(jié)點時，執(zhí)行式(4)計算其全部父節(jié)點，且同層節(jié)點不可比，不存在父子關系，在構造父節(jié)點時任務相互獨立。

定義5同層節(jié)點集在同一模糊概念格內，具有相同層次的模糊概念的集合，稱為同層節(jié)點集。

同層節(jié)點集在構造過程中作為任務集合，可以從任意點進行拆分，作為并行計算的子任務。

定義6子集與分割點同層節(jié)點集U中任意兩個元素U[n1]和U[n2](0≤n1≤n2≤U.length-1)，在它們之間所有元素的集合稱為一個子集，表示為U[n1,n2]，其中n1、n2稱為子集的左、右分割點。

定義7集合U內所有節(jié)點的子節(jié)點集合的并表示為U*。

例如，U={E1,E2,…，En}，則所有節(jié)點的子節(jié)點集合的并為E1*∪E2*∪…∪En-1*∪En*，為了便于論述通常由U*來表示，即U*=E1*∪E2*∪…∪En-1*∪En*。

各個并行計算節(jié)點獲取到子集后，計算子集內每個節(jié)點的子節(jié)點集合，子集Ui的計算結果表示為Ui*，而同層節(jié)點集合U的計算結果表示為U*。各子集計算結果的并應與全集的計算結果相等，命題如下。

命題2同層節(jié)點集U拆分成n個子集(U=U1∪U2∪…∪Un-1∪Un)，則U*=U1*∪U2*∪…∪Un-1*∪Un*。

證明：

計算子集任務時，各計算節(jié)點并行計算，之間不需要通信。完成計算后與主節(jié)點(ID=0)通信，將結果發(fā)送到主節(jié)點處，由主節(jié)點集成各個子集的計算結果。模糊概念格內會出現一個子節(jié)點擁有多個父節(jié)點的情況，故一個子節(jié)點可被不同父節(jié)點多次計算出來，在結果集成時，每個子節(jié)點都需要搜索模糊概念格F以判斷是否已存在。

在計算過程中，需要多次搜索模糊概念格F，因此模糊概念格F的搜索效率直接影響算法的效率。模糊概念格F的搜索空間的表示與搜索方法可利用已有的結論。根據文獻[12]，F的搜索空間與一維n位‖L‖進制數集合按大小自然排序同序，而任意進制數與十進制數之間存在轉換關系，故一維n位‖L‖進制數可以轉換為十進制數，映射函數ρ為：

ρ(s)=m1‖L‖n-1+m2‖L‖n-2+…+mn-1‖L‖1+mn‖L‖0

(5)

通過式(5)可將F的搜索空間內模糊概念映射為自然數，在集成計算結果時，直接查詢自然數來確定生產的節(jié)點是否在F內存在，減少訪問F消耗的時間。詳細論述請參考文獻[9]。

在集成計算結果時，子節(jié)點被不同父節(jié)點多次計算生成，具有一定的冗余，但由于建立模糊概念格的格結構，需要所有節(jié)點的父子關系，因此不可避免。

3.2算法描述

由上文理論分析，同層節(jié)點的構造任務相互獨立，同層節(jié)點集U根據計算節(jié)點個數拆分為多個子集，每個計算節(jié)點完成一個子集的計算任務，結果U*在主節(jié)點處集成，并更新U(U=U*)作為新的同層節(jié)點集，遞歸重復計算，直到全部計算完畢形成模糊概念格。模糊概念格的并行構造算法描述如下：

算法Parallel Fuzzy Lattice

輸入模糊形式背景K；

計算節(jié)點個數m

輸出模糊概念格F

1. F=(，U=(，B=(↓↑；

//式(4)

3. Parallel Generate From(F,U,ID=0);

4. Return F

ParaFuLa算法的主程序主要負責初始化程序入口，具體的計算由函數ParallelGenerateFrom來完成。函數ParallelGenerateFrom描述如下：

函數ParallelGenerateFrom (K,U,ID)

輸入模糊形式背景K；

集合U；

計算節(jié)點ID

輸出模糊概念格F

1. While(U≠?)

2. If (ID = = 0)

3. // ID=0,負責任務分配與結果集成

4. For ID=1 to m

5. Receive(ID,U*)

6. (U,F)=Merge(U*)

8. n2= n2>U.length-1? (U.length-1)∶n2

9. Send(K,U[n1,n2],ID)

10. End for

11. Else

12. // ID=1…m，負責子任務，計算結果發(fā)送到ID=0處

13. Receive(K,U[n1,n2])

14. U*=Generate From(K,U);

15. Send(ID=0,U*);

16. End if

17. End while

函數ParallelGenerateFrom是算法的主體，第2-11行是主節(jié)點(ID=0)執(zhí)行部分，主要負責：1)任務分配，由定義6，將同層節(jié)點集U拆分成m個子集，再根據ID分配子集； 2)結果集成，主節(jié)點接收其它計算節(jié)點(ID=1…m)的計算結果，執(zhí)行函數Merge集成各個子集的計算結果，與此同時更新同層節(jié)點集U，作為新一輪的任務集合。第12-15行是其他計算節(jié)點(ID=1…m)執(zhí)行部分，每個計算節(jié)點負責一個子集，執(zhí)行函數GenerateFrom計算子集任務，結果發(fā)送到主節(jié)點處集成。

函數GenerateFrom (K,U)

輸入模糊形式背景K；

集合U

輸出結果集U*

1. If(U≠()

2. For each E∈U && E≠Y

3. U*=U*∪E*

4. For each D∈ E*

5. //記錄偏序關系

6. Add E to D*

7. End for

8. End If

9. Return U*

函數GenerateFrom的功能是計算子集任務。計算子集U內每個節(jié)點的子節(jié)點集合，并在計算過程中記錄偏序關系，計算結果形成U*作為函數的返回值。

函數Merge (U*)

輸入結果集U*

輸出更新集合U，更新F

1. For each E∈U*

2. n=ρ(E)

//定義7

3. If F. flag[n]=false

4. //為新生成節(jié)點加入F，否則只記錄偏序關系

5. F∪{E,E*,E*};

6. Else add E to F[n].element*

7. End if

9. Add E to U

10. End if

11. Return

函數Merge負責集成子集的計算結果并更新U。對于子集的計算結果U*，由式(5)的映射函數將子節(jié)點轉化為自然數，進而在F內快速查詢，若不存在，為新生成節(jié)點加入F；若存在，則只需記錄相應的偏序關系。與此同時，U*內的子節(jié)點逐個加入U，并避免重復,U完成更新后作為新的同層節(jié)點集，拆分成子集進行任務分配，重復執(zhí)行直至模糊概念格構造完畢。

3.3算法分析

對于以上描述ParaFuLa算法的正確性可通過其構造出的模糊概念格是否同構予以證明。

定理2并行算法ParaFuLa構造的模糊概念格與原串行算法構造出的模糊概念格同構。

證明：(1) 最小內涵節(jié)點同時被兩種算法構造出來。

(2) 對于每一個由原算法構造出的節(jié)點(AK,BK)，在模糊概念格中由偏序關系存在(A,φ)≥(A1,B1)≥…≥(AK-1,BK-1)≥(AK,BK)。若(AK,BK)為(A,φ)的直接父節(jié)點，則在并行算法中必定會生成；若(AK,BK)不是(A,φ)的直接父節(jié)點，但存在一條鏈接(A1,B1)≥…≥(AK-1,BK-1)，其中必有(AK,BK)的父節(jié)點，由并行算法可知(AK,BK)必由其父節(jié)點計算生成，故(AK,BK)必定也存在于并行構造算法構造的模糊概念格內。

(3) 因為并行算法在每個子任務上執(zhí)行相同的串行算法，所以并行算法產生的節(jié)點也必定存在于串行算法構造的模糊概念格內。

由定理2的證明即可知，本文提出的模糊概念格并行構造算法能夠正確地構造出模糊概念格。

其次，分析算法的時間復雜度。

證明：(1)各個并行計算節(jié)點在并行執(zhí)行GenerateFrom函數時，由公式(4)計算子節(jié)點集合，需要進行閉包運算和屬性集的遍歷，計算子節(jié)點集合的時間復雜度為O(|X|×|Y|2×|F|)。

(2) 在結果集成時遍歷模糊概念格，由式(5)模糊概念格F的搜索空間表示為Y的冪集LY，映射函數ρ將任意模糊概念轉換為十進制數，其時間復雜度為O(|X|×|L|)[12]。

(3) 通信量主要為各個并行計算節(jié)點與主節(jié)點間的通信，由模糊概念的數量和生成次數決定。最壞情況下，任意節(jié)點是其下層所有節(jié)點的子節(jié)點，在構造過程中被下層每個節(jié)點重復生成一次，此時完整概念格在構造過程中通信量的時間復雜度為O(2|F|)。

(4) 作為并行算法ParaFuLa算法的時間復雜度由各個計算節(jié)點的復雜度決定，主體部分負責任務分配與結果集成。構造模糊概念格由m個計算節(jié)點執(zhí)行GenerateFrom函數，由(1)、(2)和(3)分析，ParaFuLa算法的時間復雜度為：

由以上時間復雜度的分析，ParaFuLa算法利用并行計算方法，在一定程度上提高了模糊概念格的構造效率。

4實驗實例

如表1所示模糊形式背景，該模糊形式背景具有4個對象，5個屬性。設此時計算節(jié)點個數為4，ID等于0為主節(jié)點，負責任務分配與結果集成，其它節(jié)點計算子任務。

表1　模糊形式背景K

由ParaFuLa算法構造出的模糊格如圖1所示，其過程為:

(1) 由程序入口進行閉包運算，得到C1，再由C1計算出其全部子節(jié)點集合為U={C2，C3}，記錄偏序關系。此時C2和C3為同層節(jié)點集。

(2) 此時由定義6對同層節(jié)點集U進行拆分，主節(jié)點將C2分配給1號(ID=1)計算節(jié)點，計算子節(jié)點集合為{C4}，C3分配給2號計算節(jié)點，計算子節(jié)點集合為{C5}，此時集合較小3號計算節(jié)點空閑。主節(jié)點集成結果為{C4，C5}，更新U={C4，C5}，并記錄偏序關系。

(3) 主節(jié)點再次對U劃分并進行任務分配，1號計算節(jié)點計算出{C4}子節(jié)點集合{C6，C7，C8}，2號計算節(jié)點計算出{C5}子節(jié)點集合{C9}，然后主節(jié)點集成結果并更新U={C6，C7，C8，C9}，并記錄偏序關系。

(4) 由定義6再次對U劃分，主節(jié)點將{C6}分配給1號計算節(jié)點，{C7}分配給2號計算節(jié)點，{C8，C9}分配給3號計算節(jié)點。各個計算節(jié)點計算完畢，主節(jié)點集成結果為U={C10，C11，C12，C13}，并記錄偏序關系。

(5) 主節(jié)點繼續(xù)進行任務分配，{C10}分配給1號計算節(jié)點，{C11}分配給2號計算節(jié)點，{C12，C13}分配給3號計算節(jié)點，主節(jié)點集成結果為U={C14，C15 }，并記錄偏序關系。

(6) 主節(jié)點將同層節(jié)點集{C14，C15 }劃分，{C14}分配給1號計算節(jié)點，{C15}分配給2號計算節(jié)點，主節(jié)點集成結果U={C16}，并記錄偏序關系。

(7) 此時U={C16}，主節(jié)點將{C16}分配給1號計算節(jié)點，C16為內涵最大節(jié)點，計算得其子節(jié)點為空，主節(jié)點集成結果U=?，此時算法結束。

圖1　K生成的模糊概念格

圖1中同層模糊概念節(jié)點由橫線標示，同層模糊概念節(jié)點任務獨立例如同層節(jié)點集{C4，C5}和同層節(jié)點集{C6，C7，C8，C9}，它們由主節(jié)點分分配給不同的計算節(jié)點，進行并行計算，且在計算過程中記錄偏序關系，最終形成格結構。

為了驗證本文提出的并行算法的性能，通過Java編程語言和MPJ平臺實現本文所涉及的算法，實驗時，程序運行在Intel Xeon 8 Core 多核單處理器計算環(huán)境上。首先，以加速比來度量該并行算法的性能，即在相同數據集相同精度下ParaFuLa算法相對于文獻[14]Fuzzy Lattice算法構造模糊概念格效率提升程度，實驗結果如圖2所示。真值集合L 精度分別設置為L3、 L5、L11、L101，4種不同精度，并在不同計算節(jié)點數目上進行試驗。在L3={0,0.5,1}精度時，計算任務較少，由于在計算過程需要任務分配，結果匯總等額外消耗，使得并行算法的效益無法顯現，出現以上結果。精度L5={0,0.25,0.5,0.75,1}時，加速比隨節(jié)點數正比例增加，而后保持在4左右，精度L11={0,0.1,0.2,…,1}時加速比隨節(jié)點數小幅增加；精度為L101={0,0.01,0.02,…,0.99,1}時，任務規(guī)模增大，加速比隨節(jié)點數正比例增加，并行算法的效益遠大于額外消耗，說明在較大規(guī)模模糊概念格構造任務時，并行算法具有良好的性能。

圖2　不同節(jié)點下的加速比

本文ParaFuLa算法和文獻[12] Parallel Fuzzy Next Closure算法的比較實驗結果如圖3所示。由圖3可知在不管是L3精度還是L5精度下，Parallel Fuzzy Next Closure算法的效果都比本文ParaFuLa算法要好，分析原因是本文ParaFuLa算法產生格結構，在構造模糊概念格時需要記錄模糊概念節(jié)點之間的偏序關系，從而產生通信和部分重復計算；而Parallel Fuzzy Next Closure算法只是產生模糊概念全集，并不產生格結構，沒有計算模糊概念之間偏序關系。故由以上原因產生該實驗結果。

圖3　L3和L5精度下的加速比比較

ParaFuLa算法對模糊概念進行層次劃分，同層節(jié)點集拆分為多個子集，多個計算節(jié)點同時參與計算，充分發(fā)揮并行計算的優(yōu)勢。但在算法過程中，由于需要記錄偏序關系并產生格結構，計算冗余和通信都是有待改進的地方。

5結語

模糊概念格是一種有效的數據挖掘工具，已被廣泛應用于模糊數據分析、規(guī)則提前等領域?；谀：拍罡竦膽枚夹枰云錁嬙鞛榛A，面對構造效率問題，并行算法是解決構造效率問題的有效辦法。本文提出了一種模糊概念格并行構造算法。該算法從同層節(jié)點的構造任務相互獨立出發(fā)，拆分同層節(jié)點集，子集任務并行進行，結果集成時簡化搜索空間的遍歷，使得充分利用并行計算的優(yōu)點，并行構造模糊概念格。下一步將繼續(xù)研究模糊形式概念分析技術及其在數據挖掘等領域的應用。

參考文獻

[1] Ganter B,Wille R.Formal Concept Analysis:Mathematical Foundations[M].Springer Verlag,Berlin,1999.

[2] 柴玉梅,王春麗,王黎明.基于頻繁項集的互補替代關系挖掘算法[J].模式識別與人工智能,2012,25(1):157-165.

[3] 柴玉梅,張卓,王黎明.基于頻繁概念直乘分布的全局閉頻繁項集挖掘算法[J].計算機學報,2012,35(5):990-1001.

[4] 王黎明，張卓.基于iceberg概念格并置集成的閉頻繁項集挖掘算法[J].計算機研究與發(fā)展,2007,44(7):1184-1190.

[5] 張卓,李石君,張乃洲，等.基于格空間的受限Deep Web數據抽取算法[J].模式識別與人工智能,2011,24(1):130-137.

[6] Zhang Z,Du J,Wang L.Formal concept analysis approach for data extraction from a limited deep web database[J].Journal of Intelligent Information Systems,2013,41(2):211-234.

[7] Burusco A,Fuentes-Gonzalez R.The Study of the L-Fuzzy Concept Lattice[J].Math ware & Soft Computer,1994,1(3):209-218.

[8] Belohlavek R.What is a fuzzy concept lattice? II[M]//Rough Sets,Fuzzy Sets,Data Mining and Granular Computing.Springer Berlin Heidelberg,2011:19-26.

[9] 智慧來,智東杰,劉宗田,等.概念格合并原理與算法[J].電子學報,2010,38(2):455-459.

[10] Fu H,Nguifo E M.A parallel algorithm to generate formal concepts for large data[M]//Concept Lattices.Springer Berlin Heidelberg,2004:394-401.

[11] Krajca P,Outrata J,Vychodil V.Parallel recursive algorithm for FCA[C]//CLA.2008,2008:71-82.

[12] 張卓,柴玉梅,王黎明,等.模糊形式概念并行構造算法[J].模式識別與人工智能,2013,26(3):260-269.

[13] Belohlavek R.Algorithms for fuzzy concept lattices[C]//Proc.Fourth Int.Conf.on Recent Advances in Soft Computing.Nottingham,United Kingdom.2002:200-205.

[14] Belohlavek R,De Baets B,Outrata J,et al.Computing the lattice of all fixpoints of a fuzzy closure operator[J].Fuzzy Systems,IEEE Transactions on,2010,18(3):546-557.

收稿日期：2015-03-09。孫佳，碩士，主研領域：形式概念分析、數據挖掘。柴玉梅，教授。

中圖分類號TP311

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.07.060

PARALLEL CONSTRUCTION ALGORITHM FOR FUZZY CONCEPT LATTICE BASED ON PARTITIONING OF SAME-LAYER NODES SET

Sun JiaChai Yumei

(SchoolofInformationEngineering,ZhengzhouUniversity,Zhengzhou450001,Henan,China)

AbstractThe theory of formal concept analysis (FCA) is extensively applied in various computer fields.Constructing fuzzy concept lattice is still a major issue in its application process.In order to improve the efficiency of fuzzy concept lattice construction,we presented a parallel construction algorithm for fuzzy concepts lattice by reforming the serial construction algorithm to the parallelised one.The proposed algorithm stratifies the nodes,by defining the concept of same-layer nodes,we derived the important nature of the same-layer nodes that their construction tasks are independent each other,and the introduction of mapping function simplifies the search space traversal,the efficiency of searching fuzzy concept lattice is thus improved.The parallel construction of fuzzy concept lattice achieves the goal of improving the construction efficiency.Experiments show that the algorithm has good performance when facing with the large scale construction tasks.

KeywordsFuzzy concept lattice constructionFuzzy setNodes stratificationParallel algorithm