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

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

0 引言

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

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

1 基本概念

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

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

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

2 計(jì)算所有不動(dòng)點(diǎn)的算法

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

　　2.1 串行算法

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

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

　　<C，D>總是一個(gè)形式概念，以致于B?奐D，在得到<C，D>后，算法檢查它是否應(yīng)該用<C，D>繼續(xù)遞歸地調(diào)用GenerateFrom或是否跳過<C，D>，這個(gè)測試基于比較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)。后面使用這個(gè)推導(dǎo)描述并行算法。

　　定義1（形式概念推導(dǎo)）若<X，Y，I>是一個(gè)形式上下文，具有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）的一個(gè)推導(dǎo)是以下任何序列：

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

　　以致于對于每個(gè)i=0，…，k-1都有<<Ai，Bi>，yi>├─<<Ai+1，Bi+1>，yi+1>。如果<A，B>有一個(gè)長度為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行所計(jì)算的內(nèi)涵。如果第9行的條件是正確的，那么（4）是真的。

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

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

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

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

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

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

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

　　2.2 并行算法

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

　?。?）計(jì)算并處理用少于L步可推導(dǎo)的所有概念；

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

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

　　一個(gè)并行算法由過程ParallelGenerateFrom表示，見算法2。在計(jì)算過程中，算法2有兩個(gè)常參數(shù)是很重要的，即P≥1（處理器的數(shù)量）和L≥2（遞歸的層數(shù)）。P和L值的選擇對算法的實(shí)際性能有影響，過程ParallelGenerateFrom是GenerateFrom的一個(gè)修改，并接收了一個(gè)附加的變量：計(jì)數(shù)值l從1到L，表示在第1階段處理的推導(dǎo)的長度。在它啟動(dòng)后，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個(gè)隊(duì)列。通過選擇放<<C，D>，y>的一個(gè)隊(duì)列，選擇將列出所有形式概念后項(xiàng)的一個(gè)處理器到 <C，D>，最優(yōu)的選擇方法應(yīng)該是將所有的形式概念均勻地分配到處理器。然而，這是很難完成的，因?yàn)橹钡綄?shí)際計(jì)算并顯示出調(diào)用樹的結(jié)構(gòu)后才知道在所有形式概念的研究空間中形式概念的分配情況。這個(gè)算法選擇基于一個(gè)簡單循環(huán)原則的queuer，r=（N mod P）+1，其中N為到目前為止所存儲(chǔ)的形式概念數(shù)。

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

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

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

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

　　從最壞情況下的復(fù)雜性角度來看，PCbO是一個(gè)漸進(jìn)復(fù)雜性為O（|B||Y|2|X|）的多項(xiàng)式時(shí)間延遲算法[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ì)算形式概念的算法進(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個(gè)處理器上運(yùn)行的PCbO運(yùn)行時(shí)間。測量是在具有8個(gè)獨(dú)立處理器空閑的64位硬件上進(jìn)行的。對于P>1，表1中包含計(jì)算所有形式概念的總處理器時(shí)間。允許對管理多線程計(jì)算的開銷進(jìn)行粗略的估計(jì)：開銷可以通過真實(shí)處理器時(shí)間減去總處理器時(shí)間除以P計(jì)算，而更大的P值會(huì)導(dǎo)致更大的開銷，處理器的利用率可以從由每個(gè)處理器處理概念的數(shù)量研究。表2顯示了特定處理器計(jì)算概念間的分布。處理器標(biāo)號#0是算法的初始階段，每個(gè)處理器計(jì)算概念的數(shù)量是完全由參數(shù)P、L和通過上下文決定的，這意味著如果一個(gè)處理器完成計(jì)算，它不能幫助其他處理器處理負(fù)載。

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

　　圖1（a）包含選定的數(shù)據(jù)集的結(jié)果，而圖1（b）包含隨機(jī)生成的表的結(jié)果（具有10 000個(gè)對象和5%密度）。縱軸上顯示一個(gè)相對加速比，理論加速是由硬件處理器數(shù)決定的（即如果有4個(gè)處理器，執(zhí)行速度能快4倍）。因此相對加速比是使用單一處理器的運(yùn)行時(shí)間（串行算法）和使用多個(gè)處理器的運(yùn)行時(shí)間的比值。加速比的理論最大值等于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)是非常有效的。計(jì)算閉包的數(shù)據(jù)結(jié)構(gòu)和優(yōu)化算法需進(jìn)一步討論。

4 結(jié)論

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

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

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

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

　?。?）算法的專門變種集中解決有關(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.