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

　　關鍵詞： 伽羅瓦連接；不動點；形式概念分析；并行算法

0 引言

　　本文提出了計算伽羅瓦連接所有不動點的一個并行算法，其中伽羅瓦連接是由對象屬性關聯數據引起的，稱為形式概念的不動點表示可以在數據中找到的基本矩形模式。除了它們的幾何意義，可以將不動點解釋為在輸入關聯數據中發現的自然概念的形式化。每個形式概念由它的外延（即屬于概念的所有對象集）和內涵（即由概念所涵蓋的所有屬性集）給出。用一個子概念-超概念序列裝配的所有形式概念集形成了一個完整的晶格，通常稱為一個概念格。概念格和有關的關聯結構由形式概念分析深入研究，這是20世紀80年代早期由魯道天（Rudolf Wille）成立的一個學科，從此出現了許多理論成果和形式概念分析（FCA）的應用程序[1-2]。在FCA的任何應用中所出現的基本任務就是輸入相關的數據并計算所有形式概念集。本文通過將所有形式概念分成不相交的子集，從而對概念進行并行化計算，有助于FCA的一系列算法。

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

1 基本概念

　　首先介紹一下形式概念分析的基本概念，更多細節參閱參考文獻[1-3]。設X={0，1，…，m}和Y={0，1，…，n}分別代表對象和屬性的有限非空集。一個形式上下文是一個三元組<X，Y，I>，其中I?哿X×Y，即I是X和Y之間的一個二進制關系。如給定<X，Y，I>，一對概念形式運算符[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和內涵B的一個形式概念（在<X，Y，I>），可以表示任何對<A，B>∈2X×2Y，致使A↑I=B和B↓I=A。這樣形式概念是概念形式運算符的不動點，<↑I，↓I>的所有不動點集合由B（X，Y，I）表示。在<X，Y，I>中，所有形式概念集合B（X，Y，I）用一個偏序關系≤表示，該偏序關系≤模擬子概念超概念層次：

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

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

2 計算所有不動點的算法

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

　　2.1 串行算法

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

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

　　<C，D>總是一個形式概念，以致于B?奐D，在得到<C，D>后，算法檢查它是否應該用<C，D>繼續遞歸地調用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遞歸調用相對應的推導。后面使用這個推導描述并行算法。

　　定義1（形式概念推導）若<X，Y，I>是一個形式上下文，具有Y={0，1，…，n}，對于形式概念<A1，B1>，<A2，B2>∈B（X，Y，I），整數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）的一個推導是以下任何序列：

　　<<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的推導，<A，B>是k步可推導的。如果GENERATEFROM（<A，B>，y）的調用引起第10行調用GENERATEFROM（<C，D>，k），顯而易見<<A，B>，y>├<<C，D>，k>確實地：（1）確保算法1第6行的條件得到滿足；（2）對應到5~13行之間的循環（從y向上的）；（3）是在8行所計算的內涵。如果第9行的條件是正確的，那么（4）是真的。

　　下面的論斷顯示了推導的存在性和唯一性。

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

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

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

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

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

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

　　2.2 并行算法

　　假設有能同時執行指令的P個獨立的處理器，這些可能表示在一個網絡中的獨立計算機或者是在一個共享內存系統中的多處理器。每個處理器可以處理上下文<X，Y，I>，因為<X，Y，I>在計算期間不允許修改，每個處理器可以有<X，Y，I>的拷貝或在多個處理器間共享一個拷貝。本文所提出的并行算法主要是對GenerateFrom的修改，以致于由P個處理器同時處理調用樹的特殊子樹。根據定義1，算法首先處理用少于L步就可推導的所有概念，剩余的概念采用并行方法處理。因此計算概念的一個并行過程可以概括為以下三個相續的階段：

　　（1）計算并處理用少于L步可推導的所有概念；

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

　　（3）啟動P個處理器，運行并行計算：①使每個處理器占有一個隊列；②使每個處理器計算在它的隊列里的所有概念。

　　一個并行算法由過程ParallelGenerateFrom表示，見算法2。在計算過程中，算法2有兩個常參數是很重要的，即P≥1（處理器的數量）和L≥2（遞歸的層數）。P和L值的選擇對算法的實際性能有影響，過程ParallelGenerateFrom是GenerateFrom的一個修改，并接收了一個附加的變量：計數值l從1到L，表示在第1階段處理的推導的長度。在它啟動后，ParallelGenerateFrom按如下進行：模擬原始GenerateFrom直到它達到了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的關鍵問題是如何分配在L步可推導的形式概念進入P個隊列。通過選擇放<<C，D>，y>的一個隊列，選擇將列出所有形式概念后項的一個處理器到 <C，D>，最優的選擇方法應該是將所有的形式概念均勻地分配到處理器。然而，這是很難完成的，因為直到實際計算并顯示出調用樹的結構后才知道在所有形式概念的研究空間中形式概念的分配情況。這個算法選擇基于一個簡單循環原則的queuer，r=（N mod P）+1，其中N為到目前為止所存儲的形式概念數。

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

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

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

3 實驗結果

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

　　接下來的實驗研究PCbO的可擴展性，使用多個處理器減少運行時間的能力。該實驗使用配備八核UltraSPARC Ⅱ處理器可以處理多達32個同時運行的線程的計算機。

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

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

4 結論

　　本文提出了一種稱為PCbO的并行算法，該算法在對象屬性數據表中計算形式概念，并行算法的結果是CbO的并行化和模擬普通CbO的遞歸過程的形式化。它叉分成多個過程，且每個過程計算形式概念的不相交集。該算法具有最小的開銷，因為計算不相交的概念集合的并行進程是完全獨立的，這大大提高了算法的效率。該算法是可擴展的，隨著CPU數量的增加，通過增加CPU數量計算加速比就接近理論極限。未來的研究將集中在以下幾方面：

　?。?）減少計算多次概念的數量；

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

　?。?）與其他并行算法的性能比較，各種數據結構的可伸縮性測試的程度和意圖；

　?。?）算法的專門變種集中解決有關FCA的特定問題，例如二進制矩陣分解。

　　參考文獻

　　[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.