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

孫　佳　柴玉梅

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

?

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

孫佳柴玉梅

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

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

關(guān)鍵詞模糊概念格構(gòu)造模糊集節(jié)點分層并行算法

0引言

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

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

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

1相關(guān)概念

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

模糊形式背景由四元組(X,Y,I,L)表示，其中X為模糊對象集合，Y為模糊屬性集合，I為(X,Y)上的二元模糊關(guān)系，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é)構(gòu)特征，對于其中的每一個模糊概念都稱為是一個模糊概念節(jié)點，通常簡稱為節(jié)點。模糊概念之間的偏序關(guān)系由模糊集合包含關(guān)系來確定,對于任意兩個模糊概念C1(x1,y1)與C2(x2,y2)，如果x1?x2(或y1?y2)則有C1 (x1,y1)≤C2 (x2,y2)。模糊形式背景K=(X,Y,I,L)上的所有模糊概念及其上的偏序關(guān)系構(gòu)成一個偏序集(C,≤)，是一個完備格，稱之為模糊概念格。

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

對于一個模糊概念格，其由全部的模糊概念以及父子關(guān)系構(gòu)成。根據(jù)這種結(jié)構(gòu)特點，每個模糊概念在模糊概念格內(nèi)都具有深度特征。

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

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

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

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

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

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

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

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

在模糊概念格內(nèi)，模糊概念具有明顯的深度、層次特征，由此也可以更清楚地表示出模糊概念格的層次結(jié)構(gòu)特點。

2串行構(gòu)造算法

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

(3)

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

(4)

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

Step1 初始化F=?，從最小內(nèi)涵B=?開始；

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

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

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

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

3模糊概念格并行構(gòu)造算法

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

3.1理論基礎(chǔ)

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

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

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

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

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

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

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

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

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

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

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

證明：

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

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

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

(5)

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

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

3.2算法描述

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

算法Parallel Fuzzy Lattice

輸入模糊形式背景K；

計算節(jié)點個數(shù)m

輸出模糊概念格F

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

//式(4)

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

4. Return F

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

函數(shù)ParallelGenerateFrom (K,U,ID)

輸入模糊形式背景K；

集合U；

計算節(jié)點ID

輸出模糊概念格F

1. While(U≠?)

2. If (ID = = 0)

3. // ID=0,負責任務(wù)分配與結(jié)果集成

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，負責子任務(wù)，計算結(jié)果發(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

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

函數(shù)GenerateFrom (K,U)

輸入模糊形式背景K；

集合U

輸出結(jié)果集U*

1. If(U≠()

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

3. U*=U*∪E*

4. For each D∈ E*

5. //記錄偏序關(guān)系

6. Add E to D*

7. End for

8. End If

9. Return U*

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

函數(shù)Merge (U*)

輸入結(jié)果集U*

輸出更新集合U，更新F

1. For each E∈U*

2. n=ρ(E)

//定義7

3. If F. flag[n]=false

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

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

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

3.3算法分析

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

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

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

(2) 對于每一個由原算法構(gòu)造出的節(jié)點(AK,BK)，在模糊概念格中由偏序關(guān)系存在(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)必定也存在于并行構(gòu)造算法構(gòu)造的模糊概念格內(nèi)。

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

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

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

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

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

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

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

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

4實驗實例

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

表1　模糊形式背景K

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

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

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

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

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

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

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

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

圖1　K生成的模糊概念格

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

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

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

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

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

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

5結(jié)語

模糊概念格是一種有效的數(shù)據(jù)挖掘工具，已被廣泛應用于模糊數(shù)據(jù)分析、規(guī)則提前等領(lǐng)域。基于模糊概念格的應用都需要以其構(gòu)造為基礎(chǔ)，面對構(gòu)造效率問題，并行算法是解決構(gòu)造效率問題的有效辦法。本文提出了一種模糊概念格并行構(gòu)造算法。該算法從同層節(jié)點的構(gòu)造任務(wù)相互獨立出發(fā)，拆分同層節(jié)點集，子集任務(wù)并行進行，結(jié)果集成時簡化搜索空間的遍歷，使得充分利用并行計算的優(yōu)點，并行構(gòu)造模糊概念格。下一步將繼續(xù)研究模糊形式概念分析技術(shù)及其在數(shù)據(jù)挖掘等領(lǐng)域的應用。

參考文獻

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

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

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

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

[5] 張卓,李石君,張乃洲，等.基于格空間的受限D(zhuǎn)eep Web數(shù)據(jù)抽取算法[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] 張卓,柴玉梅,王黎明,等.模糊形式概念并行構(gòu)造算法[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。孫佳，碩士，主研領(lǐng)域：形式概念分析、數(shù)據(jù)挖掘。柴玉梅，教授。

中圖分類號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