摘  要： 為了提高伽羅瓦連接所有不動點(diǎn)的計算速度和效率,，在計算伽羅瓦連接不動點(diǎn)的串行算法（CbO）基礎(chǔ)上，通過處理所有不動點(diǎn)的不相交子集方法,，將串行算法并行化,，啟動P個處理器同時并行運(yùn)行，使每個處理器都并行地計算它的所有不動點(diǎn),，證明了此算法的正確性,，并分析了它的漸近式復(fù)雜性。實(shí)驗(yàn)給出了算法在各種數(shù)據(jù)集上的效率及可擴(kuò)展性,，表明PCbO并行算法效率優(yōu)于其串行算法,。

　　關(guān)鍵詞： 伽羅瓦連接；不動點(diǎn),；形式概念分析,；并行算法

0 引言

　　本文提出了計算伽羅瓦連接所有不動點(diǎn)的一個并行算法，其中伽羅瓦連接是由對象屬性關(guān)聯(lián)數(shù)據(jù)引起的,，稱為形式概念的不動點(diǎn)表示可以在數(shù)據(jù)中找到的基本矩形模式,。除了它們的幾何意義，可以將不動點(diǎn)解釋為在輸入關(guān)聯(lián)數(shù)據(jù)中發(fā)現(xiàn)的自然概念的形式化,。每個形式概念由它的外延（即屬于概念的所有對象集）和內(nèi)涵（即由概念所涵蓋的所有屬性集）給出,。用一個子概念-超概念序列裝配的所有形式概念集形成了一個完整的晶格，通常稱為一個概念格,。概念格和有關(guān)的關(guān)聯(lián)結(jié)構(gòu)由形式概念分析深入研究,，這是20世紀(jì)80年代早期由魯?shù)捞欤≧udolf Wille）成立的一個學(xué)科，從此出現(xiàn)了許多理論成果和形式概念分析（FCA）的應(yīng)用程序[1-2],。在FCA的任何應(yīng)用中所出現(xiàn)的基本任務(wù)就是輸入相關(guān)的數(shù)據(jù)并計算所有形式概念集,。本文通過將所有形式概念分成不相交的子集，從而對概念進(jìn)行并行化計算,，有助于FCA的一系列算法,。

　　本文首先介紹形式概念分析的概念，然后提出了伽羅瓦連接不動點(diǎn)的并行算法并證明其正確性,，最后討論了并行算法的復(fù)雜性,、效率及可擴(kuò)展性。

1 基本概念

　　首先介紹一下形式概念分析的基本概念，更多細(xì)節(jié)參閱參考文獻(xiàn)[1-3],。設(shè)X={0，1,，…,，m}和Y={0，1,，…,，n}分別代表對象和屬性的有限非空集。一個形式上下文是一個三元組<X,，Y,，I>，其中I?哿X×Y,，即I是X和Y之間的一個二進(jìn)制關(guān)系,。如給定<X，Y,，I>,，一對概念形式運(yùn)算符[1]↑I：2X→2Y和↓I：2Y→2X已定義，對于每個A?哿X和B?哿Y,，分別通過A↑I={y∈Y|對每個x∈A：<x,，y>∈I}和B↓I={x∈X|對每個y∈B：<x，y>∈I},。（以下省略I,，只寫↑和↓分別代替↑I和↓I。）通過具有外延A和內(nèi)涵B的一個形式概念（在<X,，Y,，I>），可以表示任何對<A,，B>∈2X×2Y,，致使A↑I=B和B↓I=A。這樣形式概念是概念形式運(yùn)算符的不動點(diǎn),，<↑I,，↓I>的所有不動點(diǎn)集合由B（X，Y,，I）表示,。在<X，Y,，I>中,，所有形式概念集合B（X，Y,，I）用一個偏序關(guān)系≤表示,，該偏序關(guān)系≤模擬子概念超概念層次：

　　如果A1A2（或B1B2）,，則<A1，B1>≤<A2,，B2>（1）

　　如果<A1,，B1>≤<A2，B2>,，那么<A1,，B1>稱為<A2，B2>的一個子概念,。由式（1）定義和≤在一起的集合B（X,，Y，I）形成了一個完整的格,，它的結(jié)構(gòu)由FCA的基本定理來描述[1],。

2 計算所有不動點(diǎn)的算法

　　并行算法可以看作是在概念的不相交子集上同時工作的幾個串行版本的實(shí)例，對于一個給定的形式上下文<X,，Y,，I>，集中<↑I,，↓I>的所有不動點(diǎn),，以致于X={0，1,，…,，m}和Y={0，1,，…,，n}）。

　　2.1 串行算法

　　串行算法的核心是一個遞歸過程GenerateFrom,，如算法1列出了通過形式概念空間進(jìn)行深度優(yōu)先搜索的所有形式概念,。這個過程將一個初始形式概念<A，B>和一個屬性（所處理的第一個屬性）作為它的自變量,。用形式概念<A,，B>開始，這個過程通過形式概念空間遞歸下去,。當(dāng)用<A,，B>和y∈Y調(diào)用時，GenerateFrom先處理過程<A,，B>,，然后檢查它的停機(jī)條件。根據(jù)停機(jī)條件，當(dāng)<A,，B>等于<Y↓,，Y>或y>n時，計算停止,；否則,，這個過程用完所有屬性j∈Y，以致于j≥y不包括在內(nèi)涵B中,，對于每個有這些屬性，一對<C,，D>∈2X×2Y以致于可以計算：

　　<C,，D>=<A∩{j}↓，（A∩{j}↑）>（2）

　　<C,，D>總是一個形式概念,，以致于B?奐D，在得到<C,，D>后,，算法檢查它是否應(yīng)該用<C，D>繼續(xù)遞歸地調(diào)用GenerateFrom或是否跳過<C,，D>,，這個測試基于比較B∩Yj=D∩Yj而Yj?哿Y按如下定義：

　　Yj={y∈Y|y<j>}（3）

　　算法1 Procedure GenerateFrom（<A，B>,，y）

　　Input：formal concept<A,，B>and a number y∈Y∪{n+1}such that y?埸B

　　1  process<A，B>（e.g.,，print<A,，B>on the screen）；

　　2  if B=Y or y>n then

　　3    return

　　4  end

　　5  for j from y upto n do

　　6    if j?埸B then

　　7      set C to A∩{j}↓,；

　　8      set D to C↑,；

　　9      if B∩Yj=D∩Yj then

　　10       GENERATEFROM（<C，D>,，j+1）

　　11     end

　　12   end

　　13 end

　　14 return

　　為了證明算法1的正確性,，引入了與過程GenerateFrom遞歸調(diào)用相對應(yīng)的推導(dǎo)。后面使用這個推導(dǎo)描述并行算法,。

　　定義1（形式概念推導(dǎo)）若<X,，Y，I>是一個形式上下文,，具有Y={0,，1，…，n},，對于形式概念<A1,，B1>，<A2,，B2>∈B（X,，Y，I）,，整數(shù)y1,，y2∈Y∪{n+1}使<<A1，B1>,，y1>├─<<A2,，B2>，y2>表示 m=y2-1必須滿足以下所有條件：（1）m?埸B1,；（2）y1<y2,；（3）B2=（B1∪{m}）↓↑；（4）B1∩Ym=B2∩Ym,，其中Ym由式（3）定義,。

　　長度為k+1的<A，B>∈B（X,，Y,，I）的一個推導(dǎo)是以下任何序列：

　　<<0>=<<A0，B0>,，y0>,，<<A1，B1>,，y1>,，…，<<Ak,，Bk>,，yk>=<<A，B>,，yk>（4）

　　以致于對于每個i=0,，…，k-1都有<<Ai,，Bi>,，yi>├─<<Ai+1，Bi+1>,，yi+1>,。如果<A,，B>有一個長度為k的推導(dǎo)，<A,，B>是k步可推導(dǎo)的,。如果GENERATEFROM（<A，B>,，y）的調(diào)用引起第10行調(diào)用GENERATEFROM（<C,，D>，k）,，顯而易見<<A,，B>，y>├<<C,，D>,，k>確實(shí)地：（1）確保算法1第6行的條件得到滿足；（2）對應(yīng)到5~13行之間的循環(huán)（從y向上的）,；（3）是在8行所計算的內(nèi)涵。如果第9行的條件是正確的,，那么（4）是真的,。

　　下面的論斷顯示了推導(dǎo)的存在性和唯一性。

　　引理1（推導(dǎo)的存在性）對于每個形式概念<A,，B>∈B（X,，Y，I）有一個推導(dǎo)（4）,，以致于yi=mi+1,，其中對于每個0<i≤k，都有：

　　mi=min{y∈B|y?埸Bi-1}（5）

　　引理2（推導(dǎo)的唯一性）每個形式概念<A,，B>∈   B（X,，Y，I）至多有一個推導(dǎo),。

　　從引理1和引理2可以得到下面的結(jié)論：

　　定理1（算法1的正確性）：當(dāng)用y=0調(diào)用時,，算法1導(dǎo)出了<X，Y,，I>中的所有形式概念,，且它們中的每一個僅有一次。

　　算法1通過一個遞歸過程GenerateFrom而不是通過回溯法來表達(dá)CbO（Close-by-One）算法[4],。這有幾個好處：（1）GenerateFrom比參考文獻(xiàn)[4]的抽象描述更接近實(shí)際的實(shí)現(xiàn),。（2）對已經(jīng)處理過的屬性無需作明確的標(biāo)注[4]。這是因?yàn)镚enerateFrom的每次調(diào)用在一個局部變量j中都有所有必要的信息,。當(dāng)計算新的閉包時,，通過Y的所有屬性的一個子集來提高這個算法的效率,。（3）無需建立CbO樹作為一個數(shù)據(jù)結(jié)構(gòu)，CbO樹與GenerateFrom的遞歸調(diào)用相對應(yīng)：定義1的推導(dǎo)對應(yīng)到CbO樹中典型路徑[4],。

　　2.2 并行算法

　　假設(shè)有能同時執(zhí)行指令的P個獨(dú)立的處理器,，這些可能表示在一個網(wǎng)絡(luò)中的獨(dú)立計算機(jī)或者是在一個共享內(nèi)存系統(tǒng)中的多處理器。每個處理器可以處理上下文<X,，Y,，I>，因?yàn)?lt;X,，Y,，I>在計算期間不允許修改，每個處理器可以有<X,，Y,，I>的拷貝或在多個處理器間共享一個拷貝。本文所提出的并行算法主要是對GenerateFrom的修改,，以致于由P個處理器同時處理調(diào)用樹的特殊子樹,。根據(jù)定義1，算法首先處理用少于L步就可推導(dǎo)的所有概念,，剩余的概念采用并行方法處理,。因此計算概念的一個并行過程可以概括為以下三個相續(xù)的階段：

　　（1）計算并處理用少于L步可推導(dǎo)的所有概念,；

　?。?）將用L步可推導(dǎo)的所有概念存儲在P個獨(dú)立的隊列中；

　?。?）啟動P個處理器,，運(yùn)行并行計算：①使每個處理器占有一個隊列；②使每個處理器計算在它的隊列里的所有概念,。

　　一個并行算法由過程ParallelGenerateFrom表示,，見算法2。在計算過程中,，算法2有兩個常參數(shù)是很重要的,，即P≥1（處理器的數(shù)量）和L≥2（遞歸的層數(shù)）。P和L值的選擇對算法的實(shí)際性能有影響,，過程ParallelGenerateFrom是GenerateFrom的一個修改,，并接收了一個附加的變量：計數(shù)值l從1到L，表示在第1階段處理的推導(dǎo)的長度,。在它啟動后,，ParallelGenerateFrom按如下進(jìn)行：模擬原始GenerateFrom直到它達(dá)到了L遞歸層，見第1~17行之間的代碼,。這與以上第1階段概述一致,。

　　算法2 Procedure ParallelGenerateFrom（<A,，B>，y,，l）

　　Input：formal concept<A,，B>

　　number y∈Y∪{n+1} such that yB

　　level of recursion L≥2

　　number of processors P≥1，and

　　counter l such that 1≤l≤L

　　1  if l=L then

　　2    select r∈{1,，…,，P}；

　　3    store<<A,，B>,，y>to queurer；

　　4    return

　　5  end

　　6  process<A,，B>（e.g.,，print<A，B>on screen）,；

　　7  if not（B=Y or y>n）then

　　8    for j from y upto n do

　　9      if jB then

　　10       set C to A∩{j}↓,；

　　11       set D to C↑；

　　12       if B∩Yj=D∩Yj then

　　13         PARALLELGENERATEFROM（<C,，D>,，j+1，l+1）,；

　　14       end

　　15     end

　　16   end

　　17 end

　　18 if l=1 then

　　19   for r from 1 upto P do

　　20     with processor r

　　21       foreach <<C,，D>,，j>∈queuer do

　　22         GENERATEFROM（<C,，D>，j）,；

　　23       end

　　24     end

　　25   wait for all processors

　　27 end

　　28 return

　　算法2的關(guān)鍵問題是如何分配在L步可推導(dǎo)的形式概念進(jìn)入P個隊列,。通過選擇放<<C，D>,，y>的一個隊列,，選擇將列出所有形式概念后項(xiàng)的一個處理器到 <C，D>,，最優(yōu)的選擇方法應(yīng)該是將所有的形式概念均勻地分配到處理器,。然而，這是很難完成的,，因?yàn)橹钡綄?shí)際計算并顯示出調(diào)用樹的結(jié)構(gòu)后才知道在所有形式概念的研究空間中形式概念的分配情況,。這個算法選擇基于一個簡單循環(huán)原則的queuer，r=（N mod P）+1,，其中N為到目前為止所存儲的形式概念數(shù),。

　　本文的算法有兩個部分：一部分將概念分配進(jìn)隊列,，另一部分以并行形式運(yùn)行幾個普通的Close-by-One。下面給出了PCbO的正確性,。

　　定理2（PCbO的正確性）,，y=0和l=1調(diào)用時，算法2導(dǎo)出了<X,，Y,，I>中的所有形式概念，且它們中的每一個僅有一次,。

　　算法2的參數(shù)P和L對所計算的形式概念在處理器中的分配有影響,，參數(shù)P的實(shí)際范圍是由所運(yùn)行算法的硬件限制（由硬件處理器或網(wǎng)絡(luò)節(jié)點(diǎn)限制），而L設(shè)成≥2的任何值,。L值依賴的算法性能在后文由實(shí)驗(yàn)評價,，如果L=2，大多數(shù)形式概念由一兩個處理器計算,，隨著L值增加,，形式概念均勻地分配到更多的處理器上。大的L值會退化并行計算,，例如,，如果L≥|Y|+1，則所有的概念將在第1階段按次序地計算,，因?yàn)檎{(diào)用樹的深度最多是|Y|+1,，從經(jīng)驗(yàn)看，假如|Y|是大的,，平均一個好的權(quán)衡值是L=3,。在這種情況下，幾乎所有形式概念并行計算并最優(yōu)地分配到各處理器上,。

3 實(shí)驗(yàn)結(jié)果

　　從最壞情況下的復(fù)雜性角度來看,，PCbO是一個漸進(jìn)復(fù)雜性為O（|B||Y|2|X|）的多項(xiàng)式時間延遲算法[5]，因?yàn)樵谧顗那闆r下PCbO可退化為串行CbO[4,，6],，在處理器的最佳利用情況下，PCbO能比CbO快P倍,，實(shí)際上達(dá)不到p倍,，因?yàn)椋海?）概念是不均勻地分布在處理器上的；（2）并行化本身也有一定的開銷,。本文給出了具有隨機(jī)生成的一組真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果,，首先把PCbO與其他計算形式概念的算法進(jìn)行比較，即把它與Ganter,、Lindig和Berry的算法進(jìn)行比較（所有算法都是在ANSI C上實(shí)現(xiàn)的）,。將參考文獻(xiàn)[7],、[8]使用的數(shù)據(jù)集與Debian GNU/Linux軟件包描述產(chǎn)生的數(shù)據(jù)集進(jìn)行比較。有關(guān)使用數(shù)據(jù)集的規(guī)模和密度信息結(jié)果如表1所示,，前4行是在1,、2、4和8個處理器上運(yùn)行的PCbO運(yùn)行時間,。測量是在具有8個獨(dú)立處理器空閑的64位硬件上進(jìn)行的,。對于P>1，表1中包含計算所有形式概念的總處理器時間,。允許對管理多線程計算的開銷進(jìn)行粗略的估計：開銷可以通過真實(shí)處理器時間減去總處理器時間除以P計算,，而更大的P值會導(dǎo)致更大的開銷，處理器的利用率可以從由每個處理器處理概念的數(shù)量研究,。表2顯示了特定處理器計算概念間的分布,。處理器標(biāo)號#0是算法的初始階段，每個處理器計算概念的數(shù)量是完全由參數(shù)P,、L和通過上下文決定的,，這意味著如果一個處理器完成計算，它不能幫助其他處理器處理負(fù)載,。

　　接下來的實(shí)驗(yàn)研究PCbO的可擴(kuò)展性,，使用多個處理器減少運(yùn)行時間的能力。該實(shí)驗(yàn)使用配備八核UltraSPARC Ⅱ處理器可以處理多達(dá)32個同時運(yùn)行的線程的計算機(jī),。

　　圖1（a）包含選定的數(shù)據(jù)集的結(jié)果,，而圖1（b）包含隨機(jī)生成的表的結(jié)果（具有10 000個對象和5%密度）?？v軸上顯示一個相對加速比,，理論加速是由硬件處理器數(shù)決定的（即如果有4個處理器，執(zhí)行速度能快4倍）,。因此相對加速比是使用單一處理器的運(yùn)行時間（串行算法）和使用多個處理器的運(yùn)行時間的比值,。加速比的理論最大值等于P,，但由于線程管理帶來的開銷,，真正加速比要小些（參見表1）。

　　圖2（a）的實(shí)驗(yàn)顯示了數(shù)據(jù)密度的影響結(jié)果,，已經(jīng)產(chǎn)生了具有不同密度的數(shù)據(jù)表,，并觀察到可擴(kuò)展性的影響。使用數(shù)據(jù)表大小為5 000×100,，圖2（b）說明了在不同數(shù)據(jù)表和處理器下參數(shù)L的影響,，實(shí)驗(yàn)結(jié)果表明，好的選擇是L∈{3,，4},。該算法實(shí)現(xiàn)的實(shí)際性能取決于所使用的數(shù)據(jù)結(jié)構(gòu),，這里已經(jīng)使用布爾向量作為基本數(shù)據(jù)結(jié)構(gòu)，并證明此數(shù)據(jù)結(jié)構(gòu)是非常有效的,。計算閉包的數(shù)據(jù)結(jié)構(gòu)和優(yōu)化算法需進(jìn)一步討論,。

4 結(jié)論

　　本文提出了一種稱為PCbO的并行算法，該算法在對象屬性數(shù)據(jù)表中計算形式概念,，并行算法的結(jié)果是CbO的并行化和模擬普通CbO的遞歸過程的形式化,。它叉分成多個過程，且每個過程計算形式概念的不相交集,。該算法具有最小的開銷,，因?yàn)橛嬎悴幌嘟坏母拍罴系牟⑿羞M(jìn)程是完全獨(dú)立的，這大大提高了算法的效率,。該算法是可擴(kuò)展的,，隨著CPU數(shù)量的增加，通過增加CPU數(shù)量計算加速比就接近理論極限,。未來的研究將集中在以下幾方面：

　?。?）減少計算多次概念的數(shù)量；

　?。?）用于選擇隊列和防止退化計算的先進(jìn)條件下的各種策略的比較,；

　　（3）與其他并行算法的性能比較,，各種數(shù)據(jù)結(jié)構(gòu)的可伸縮性測試的程度和意圖,；

　　（4）算法的專門變種集中解決有關(guān)FCA的特定問題,，例如二進(jìn)制矩陣分解,。

　　參考文獻(xiàn)

　　[1] GANTER B， WILLE R. Formal concept analysis： mathematical foundations[M]. Berlin： Springer,，1999.

　　[2] CARPINETO C,， ROMANO G. Concept data analysis： theory and applications[M]. New York： Wiley， 2004.

　　[3] GRATZER G. General Lattice theory（2nd end）[M]. Basel：Birkhauser,， 2003.

　　[4] KUZNETSOV S O. Learning of simple conceptual graphs from positive and negative examples[C]. Proceedings of the Third European Conference on Principles and Practice of Knowlege Discovery in Databases,， PKDD 1999，1999,，1704：384-392.

　　[5] JOHNSON D S,， YANNAKAKIS M， PAPADIMITRIOU C H. On generating all maximal independent sets[C]. Information Processing Letters,， 1988,，27（3），119-123.

　　[6] KUZNETSOV S O. A fast algorithm for computing all intersections of objects in finite semilattice[C]. Automatic Documentation and Mathematical Linguistics，1993,，27（5）：11-21.

　　[7] HETTICH S,， BAY S D. The UCI KDD Archive.[2014-04-10].http：//kdd.ics.uci.eut. School of Information and Computer Sciences，University of California,， Irvine,， 1999.

　　[8] ASUNCION A， NEWMAN D. UCI Machine learning repository.[2014-04-10].http：//archive.ics.uci.edu. School of Information and Computer Sciences,， University of California,， Irvine， 2007.