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

孫　佳　柴玉梅

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

?

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

孫佳柴玉梅

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

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

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

0引言

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

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

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

1相關(guān)概念

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

模糊形式背景由四元組(X,Y,I,L)表示，其中X為模糊對(duì)象集合，Y為模糊屬性集合，I為(X,Y)上的二元模糊關(guān)系，L為真值集合，取值范圍是[0,1]。對(duì)于任意的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)

其中，可認(rèn)為是A↑(y)模糊集合A中對(duì)象共有屬性y的真值度；而B↓(x)認(rèn)為是對(duì)象x擁有模糊屬性集合B中所有屬性的真值度。二元組(A,B)∈LX×LY滿足A↑=B，B↓=A，則稱(A,B)為模糊形式背景的一個(gè)模糊概念。由模糊概念格的格結(jié)構(gòu)特征，對(duì)于其中的每一個(gè)模糊概念都稱為是一個(gè)模糊概念節(jié)點(diǎn)，通常簡(jiǎn)稱為節(jié)點(diǎn)。模糊概念之間的偏序關(guān)系由模糊集合包含關(guān)系來確定,對(duì)于任意兩個(gè)模糊概念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)成一個(gè)偏序集(C,≤)，是一個(gè)完備格，稱之為模糊概念格。

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)

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

(4)

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

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

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

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

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

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

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

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

3.1理論基礎(chǔ)

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

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

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

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

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

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

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

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

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

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

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

證明：

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

在計(jì)算過程中，需要多次搜索模糊概念格F，因此模糊概念格F的搜索效率直接影響算法的效率。模糊概念格F的搜索空間的表示與搜索方法可利用已有的結(jié)論。根據(jù)文獻(xiàn)[12]，F(xiàn)的搜索空間與一維n位‖L‖進(jìn)制數(shù)集合按大小自然排序同序，而任意進(jìn)制數(shù)與十進(jìn)制數(shù)之間存在轉(zhuǎn)換關(guān)系，故一維n位‖L‖進(jìn)制數(shù)可以轉(zhuǎn)換為十進(jì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ù)，在集成計(jì)算結(jié)果時(shí)，直接查詢自然數(shù)來確定生產(chǎn)的節(jié)點(diǎn)是否在F內(nèi)存在，減少訪問F消耗的時(shí)間。詳細(xì)論述請(qǐng)參考文獻(xiàn)[9]。

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

3.2算法描述

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

算法Parallel Fuzzy Lattice

輸入模糊形式背景K；

計(jì)算節(jié)點(diǎn)個(gè)數(shù)m

輸出模糊概念格F

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

//式(4)

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

4. Return F

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

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

輸入模糊形式背景K；

集合U；

計(jì)算節(jié)點(diǎn)ID

輸出模糊概念格F

1. While(U≠?)

2. If (ID = = 0)

3. // ID=0,負(fù)責(zé)任務(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，負(fù)責(zé)子任務(wù)，計(jì)算結(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é)點(diǎn)(ID=0)執(zhí)行部分，主要負(fù)責(zé)：1)任務(wù)分配，由定義6，將同層節(jié)點(diǎn)集U拆分成m個(gè)子集，再根據(jù)ID分配子集； 2)結(jié)果集成，主節(jié)點(diǎn)接收其它計(jì)算節(jié)點(diǎn)(ID=1…m)的計(jì)算結(jié)果，執(zhí)行函數(shù)Merge集成各個(gè)子集的計(jì)算結(jié)果，與此同時(shí)更新同層節(jié)點(diǎn)集U，作為新一輪的任務(wù)集合。第12-15行是其他計(jì)算節(jié)點(diǎn)(ID=1…m)執(zhí)行部分，每個(gè)計(jì)算節(jié)點(diǎn)負(fù)責(zé)一個(gè)子集，執(zhí)行函數(shù)GenerateFrom計(jì)算子集任務(wù)，結(jié)果發(fā)送到主節(jié)點(diǎn)處集成。

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

3.3算法分析

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

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

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

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

(3) 因?yàn)椴⑿兴惴ㄔ诿總€(gè)子任務(wù)上執(zhí)行相同的串行算法，所以并行算法產(chǎn)生的節(jié)點(diǎn)也必定存在于串行算法構(gòu)造的模糊概念格內(nèi)。

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

其次，分析算法的時(shí)間復(fù)雜度。

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

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

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

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

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

4實(shí)驗(yàn)實(shí)例

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

表1　模糊形式背景K

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

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

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

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

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

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

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

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

圖1　K生成的模糊概念格

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

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

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

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

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

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

5結(jié)語

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

參考文獻(xiàn)

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

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

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

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

[5] 張卓,李石君,張乃洲，等.基于格空間的受限D(zhuǎn)eep Web數(shù)據(jù)抽取算法[J].模式識(shí)別與人工智能,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].電子學(xué)報(bào),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].模式識(shí)別與人工智能,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ù)挖掘。柴玉梅，教授。

中圖分類號(hào)TP311

文獻(xiàn)標(biāo)識(shí)碼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