增量式快速構建概念格算法*

曾利程，張祖平，鄒力耕

中南大學 信息科學與工程學院，長沙 410012

1 引言

在20世紀80年代，科學家Wille就提出了FCA（formal concept analysis），在過去的30多年里，FCA被廣泛應用[1]。FCA是概念格的核心數據結構，該理論強調以人的認知為中心，提出了一種不同于傳統的知識表示以及數據分析的方法，在信息檢索、數據挖掘、機器學習等領域得到了廣泛而深遠的影響[2-3]。如何快速構建或更新概念格成為了當今學術界的一個熱點。對概念格進行更新的一個隱含前提是必須要有已經構造好的概念格。構造一個概念格可以看成是把所有的對象或是屬性一個個添加到空概念格的過程，因而向概念格中添加對象或是屬性的更新算法有著比其他更新算法更加獨特的地方[4-6]。概念格作為數據分析的有效工具，被應用到很多的領域，吸引了廣大研究者的長期關注[7-12]。概念格中的每一個節點都是一個形式概念，所有的形式概念都由兩部分組成：外延和內涵。外延是被這個概念覆蓋的例子，就是所有屬于這個概念的對象的集合；內涵，也就是概念的描述，用來表述這個例子在這個概念下的共同特征[7,13]。形式概念分析利用了對象與屬性之間的二元關系構建概念之間的層次結構。概念格架構從本質上描述的是對象和屬性之間的關系，在哲學的意義上實現概念的規范化[4]。

概念格的形成是一個概念聚類的過程。自從概念格被提出來，從形式背景下構建概念格在概念分析研究領域成為重點。在應用概念格的過程中，由于將要被運行的數據在大多數情況下是非常大的，因此如何有效地構建概念格是人們最關注的問題[14]。目前存在的概念格的構造算法大體上分為兩類：增量式算法[15-16]和批處理算法[17-19]。批處理算法計算概念格通常采用從上至下（top-down）或者由下至上（bottom-up）的方式，而增量式算法則是采用把形式背景中的對象（或是屬性）一個接一個地添加到概念格中的方式來構建。增量式構建算法的一個顯著特點就是尚未處理的對象（或屬性）及其相關信息對于算法來說都是未知的。因此增量式算法能夠適應形式背景的動態變化，避免重新構造概念格。

同批處理算法相比，增量式算法的這些特點使得這類算法顯然更適合應用在動態數據集的處理上。增量式構造算法中最具代表性的兩種算法分別是AddIntent算法[16]和Godin算法[20]。Valtchev等人[21]采用了Godin算法一個變體，并將其整合進了一個十分高效的增量式避頻繁項集挖掘框架中。Lv等人提出了一個改進的AddIntent算法版本，該版本中的每個概念都增加了兩個字段用來快速定位已經生成的新概念[14]。實驗結果表明，當形式背景中的對象數量沒有遠遠超過屬性時，Lv等人提出的改進版本在時間上相比AddIntent會有微弱的優勢[14]。這些增量式構造算法的基本思想都是在一個已有的概念格L1的基礎上，向形式背景插入新增對象g（或者是屬性m），并根據g擁有的屬性集（m擁有的對象集）來更新L1從而得到新的概念格L2。根據已有的研究結果，在插入新增對象g（新增屬性m）后，可以把L2中的概念分為三大類：新概念（new concepts）、舊概念（old concepts）、修正概念（modified concepts）。其中，舊概念又可以細分為普通舊概念（general old concepts）和生成器概念（generator concepts）。這些概念類別的完整定義由定義2給出，而各概念之間的關系由圖1展示。

2 概念格構建的基礎

這個模塊主要解決一些關于概念格的基礎概念，這些概念在文獻[7]都有詳細介紹。

Fig.1 Correspondences between concepts inL1andL2圖1 L1與L2中各類概念的對應關系

在形式概念分析中，形式背景由三元組K=(G,M,I)展現出來，其中G是對象的集合，M是屬性的集合，而I表示的是G和M之間的二元關系。對于任意的g∈G，任意的m∈M，如果gIm則可以說明對象g擁有屬性m（(g,m)∈I）。

在對象集合A∈G以及B∈M中定義兩種映射關系，G和M都是形式背景下的對象集合和屬性集合，映射關系如下：

在形式背景中，如果一個二元組滿足C=(O,D)，并且f(O)=D以及g(D)=O，則稱C=(O,D)為一個形式概念。這里O是形式背景G中的子集，是一些對象集合，被稱為形式概念的外延；D是形式背景M中的子集，是一些屬性的集合，被稱為形式概念的內涵。

形式背景K下的所有形式概念集合用CS(K)表示。給定概念C1=(A1,B1)和概念C2=(A2,B2)，如果A1?A2，則稱C1是C2的子概念，而C2稱為C1的超概念，另外這種關系可以表示為(A1,B1)≦(A2,B2)。如果這里不存在C3=(A3,B3)，使得 (A1,B1)＜(A3,B3)＜(A2,B2)，則稱C1為孩子概念，而C2為父親概念。關系“≦”稱為概念的序，(G,M,I)上所有的概念用這種序組成的集合，稱為背景(G,M,I)上的概念格。

父親概念將置于孩子概念的上方，通過獲得哈斯圖的方式得到概念格，將概念格可視化。這種哈斯圖是在父親和孩子概念之間畫一條直線或者是曲線來表示他們之間的父親-孩子關系的。

接下來，主要介紹一些關于增量構造算法基礎的定義和理論。

Mi為前i個屬性的集合，Ii為集合G與前i個屬性之間的二元關系，“×”為笛卡爾積。使Mi={m1,m2,…,mi}?M，Ii=I?(G×Mi)，Mi+1=Mi?{m′}，Ii+1=I?(G×Mi+1)，其m′是新增屬性。對于形式背景K=(G,M,I)，給定一個形式背景Ki=(G,Mi,Ii)，與之相對應的概念格為L(Ki)。而通過屬性增量算法將會構建概念格L(Ki+1)，相對應的形式背景為Ki+1=(G,Mi+1,Ii+1)。

定義1（修正概念更新過程）對于一個概念C=(A,B)，如果A=g(m′)，則C概念將會被定義為一個修正概念，如果C是一個修正概念，則概念在概念格L(Ki+1)將會被更新為(A,B?{m′})。

定義2（四大基本概念）L1和L2分別表示新屬性m插入前后形式背景所對應的概念格。m所具有的對象集g(m′)。(A,B)是L2中的一個形式概念，則：

如果A不是L1中任何概念的外延，那么稱(A,B)為新概念[4]；

如果A?g(m′)，且A是L1中某個概念的外延，那么稱(A,B)為修正概念[4]；

如果(A,B)也是概念L1中的形式概念，那么稱(A,B)為舊概念[4]。

設(X,Y)是新概念，而(A,B)為舊概念，如果A?g(m′)=X≠A，那么稱 (A,B)為 (X,Y)的生成器；反之，(A,B)就稱為普通舊概念[4]。

命題1如果(A1,B1)是新概念(A2,B2)的一個標準生成器，與此同時，(A3,B3)是新概念(A2,B2)的一個非標準生成器，在A1?A3的情況下，如果A?A3并且A?A1，概念(A,B)既不是修正概念也不是任何新概念的標準生成器[13]。

命題2如果(A3,B3)是一個舊概念并且A3?g(m′)=A1，并且 (A1,B1)∈L(Ki+1)是一個修正概念的情況下，如果A?A3并且，概念(A,B)既不是修正概念也不是任何新概念的標準生成器[13]。

3 改進的AddExtent算法：FastAddExtent算法

3.1 AddExtent算法分析

根據第1章的分析，最經典的概念格增加算法為AddExtent算法（AddIntent算法的變形），AddExtent算法概述如下：為了增加一個屬性m（m屬性對應的對象集合Extent），從概念格的最大上界開始遞歸地查找新概念和修正概念。在遞歸函數中，不斷尋找這個命名為MaximalConcept的普通概念，這個普通概念的外延值包含Extent。如果查找結果返回的MaximalConcept的外延值等于當前傳入AddExtent的Extent，則這個MaximalConcept將會作為所有修正概念和包含外延Extent的新概念的最大上界。與之相反的是，如果查找結果返回的MaximalConcept的外延值不等于當前傳入AddExtent的Extent，那么這個MaximalConcept一定是一個標準生成器，而這個標準生成器能夠產生一個命名為NewConcept的新概念。同樣，MaximalConcept將會作為所有修訂概念和包含外延Extent的新概念的最大上界。把MaximalConcept的所有孩子節點作為最原始的GeneratorConcept以及MaximalConcept.Extent?Extent作為新對象集合Extent，把這兩個參數傳入到AddExtent中遞歸查找新的生成概念和修正概念。接下來分別建立NewConcept和父親節點以及孩子節點之間的關系。根據命題1以及命題2，任何比MaximalConcept小的概念不可能是生成器也不可能是修正概念。修正概念和新概念的標準生成器一定是MaximalConcept。因此，通過查找MaximalConcept，AddExtent算法能夠在每一次遞歸時快速找到標準生成器或者是修正概念。為了能夠找到其他標準生成器或者修正概念，AddExtent對每一個MaximalConcept的孩子節點進行遞歸調用。因為改進算法FastAddExtent避免了很大一部分的無用比較，這個算法具有更高的效率。相比AddExtent算法，運行時間大大縮減。

3.2 FastAddExtent算法的思路

在一次遞歸的過程中，MaximalConcept的所有孩子節點的子孫節點有可能是相同的概念。因此，一個概念有可能會被比較幾次，由此將會造成時間上的消耗；在查找MaximalConcept的函數中，使用的也是遞歸調用的方式，這種方式耗時較大，為了能夠減少遞歸的次數，增加了字段，減少了遞歸調用的次數，對減少運行時間上也起到了一定的效果；GetClosure-Concept函數使用遞歸調用，如果以某個外延值為外延的概念在概念格中本身就存在，在原始的AddExtent算法中，函數也會進行遞歸調用直至找到該概念，耗時較大。為了能夠快速找到并返回該概念，這里通過Hash查找的方式（L.Find(extent)）迅速找到已經存在概念格的概念，極大減少了運行時間。

本文中提出的改進后的FastAddExtent算法和原始的AddExtent算法一樣，都使用了遞歸的方式構造概念格。不同的是，FastAddExtent為每個概念增加了四個字段：visited、NewConcept、doExtent、MaximalConcept。visited是一個存儲整型數字的字段，在每一次增加一個新的屬性時，都會將該屬性值的id傳入到FastAdd-Extent中，如果某次調用FastAddExtent，在比較visited時，發現某個概念的visited值等于此輪新增屬性的id值，則表示該概念已經訪問過。NewConcept字段存儲的是由candidate傳入FastAddExtent函數之后返回的新概念，一次增加一次屬性的過程中，某個概念已經被訪問過，則把該候選子節點的NewConcept指向的概念賦給candidate，減少了不必要的遞歸調用以及不必要的比較。doExtent字段存儲的是傳入FastAddExtent的extent值，使得傳入FastAddExtent的generatorConcept的doExtent字段等于extent，通過GetClosureConcept函數，將會得到一個標準生成器或者是一個修訂概念。將該標準生成器或者是修訂概念存儲在generatorConcept的MaximalConcept字段，因為在遞歸調用的過程中需要傳入candidate值，如果傳入的candidate越靠近ClosureConcept，則遞歸查找標準生成器的次數就會越少，增加doExtent字段和MaximalConcept字段，就是為了使傳入FastAddExtent的generatorConcept更加接近ClosureConcept。

3.3 FastAddExtent算法描述與分析

FastAddExtent算法主要由三個函數組成，分別是 FastAddExtent、GetClosureConcept、CreateLattice-Incrementally，下面將對每個函數的修改部分進行詳細的描述。

3.3.1 函數FastAddExtent描述

輸入：新建概念的外延extent，新建概念格的初始生成器generatorConcept，已建好的概念格L，添加屬性的id值n。

輸出：新概念newConcept。

步驟1對初始生成器的doExtent以及Maximal-Concept字段進行標記。

步驟2通過GetClosureConcept函數獲得外延值包含于該概念的最小的概念并賦值給generator-Concept，判斷該外延值是否等于extent，如果是，則返回該概念；否則繼續步驟3。

步驟3獲得該generatorConcept的所有孩子節點，這些孩子節點作為newConcept的候選孩子節點candidate。

步驟4對每一個候選孩子節點candidate，如果外延值與extent值存在包含關系，則為修改概念；否則需要新建概念，繼續步驟5。

步驟5如果該candidate在添加屬性過程中已經被訪問過，則直接將候選孩子節點賦值為以該候選節點為生成器生成的新概念；否則以extent與候選節點的外延值的交集、候選節點candidate、已建好的概念格L、n值傳入，進入步驟1，將返回的新概念賦值于candidate的NewConcept，并對該概念進行被訪問標記，此時的候選節點candidate變為新生成的新概念。

步驟6對newConcept中每一個孩子節點進行判斷，如果該candidate外延值包含于孩子節點，則跳出循環；如果該child外延值包含于候選孩子節點的外延值，則刪除該child，將候選孩子節點加入到正式孩子節點中。完成步驟4。

步驟7將newConcept與每一個孩子節點建立關系，同時刪除每一個孩子節點與生成器generatorConcept之間的聯系。建立生成器與newConcept的聯系。

步驟8返回newConcept。

在接下來的段落里，將會主要介紹FastAddExtent算法相對AddExtent算法修改部分。至于AddExtent算法的不做修改部分以及使用不變的函數，可以查閱文獻[11]。

3.3.2 函數GetClosureConcept描述

輸入：外延值extent，查找最小概念的起點generator-Concept，已生成的概念格。

輸出：標準生成器generatorConcept。

步驟1在Hash表中查找是否存在以extent為外延值的概念。如果存在，則返回該概念；否則步驟2。

步驟2對已建好的概念格L中，以generator-Concept為起點，從上往下查找，找到外延值包含extent的最小概念。

步驟3返回generatorConcept。

3.3.3 函數CreateLatticeIncrementally描述

輸入：形式背景G、M、I。

輸出：概念格L。

步驟1讀取形式背景的信息，新建第一個概念topConcept(G, ? )。

步驟2對形式背景中的M的每一個屬性，調用FastAddExtent，添加屬性至概念格。并將屬性添加至修改概念中。

步驟3返回概念格L。

3.4 FastAddExtent算法案例分析

下面用一個案例來分析FastAddExtent算法是如何減少運行時間的。表1、表2為增加屬性前后的形式背景，圖2、圖3為增加屬性前后的概念格。

Table 1 Example of formal context before adding attributee表1 增加屬性e之前的背景

Table 2 Example of formal context after adding attributee表2 增加屬性e之后的背景

Fig.2 Concept lattice of formal context in Table 1圖2 表1形式背景的概念格

Fig.3 Concept lattice of formal context in Table 2圖3 表2形式背景的概念格

為了方便查看對圖3中的各個概念進行標號，標號情況如下：

在一次增加屬性e的過程中，C1為新概念C5的標準生成器，由于C1有兩個候選子節點分別對兩個候選子節點的外延與{1,2,3}進行交集，此時C2.NewConcept=C6，C3.NewConcept=C7，并且C2、C3的visited值為5，假設C6概念相比C7概念先創建。C4是C2的候選子節點，并且由C4作為標準生成器生成了概念C8，并且返回C8，則C4.NewConcept=C8，C4.visited=5。當創建C7概念時，C7的候選子節點為C4，由于C4.visited=5，C4是第二次訪問，則直接把C4.NewConcept賦給C7的候選子節點candidate。這一過程中，省去了一次遞歸調用和后續諸多的比較，極大減少了運行時間。在概念格規模龐大的時候，此時的效果更加明顯。

3.5 實驗評估及分析

為了證明文中提出的改進算法的有效性，使用了Python語言分別實現了改進的FastAddExtent和原始的AddExtent算法。所有的實驗都是在一臺裝有64位操作系統，core i5 4590（3.7 GHz），8.0 GB內存的計算機上運行。

FastAddExtent算法雖然相比AddExtent算法在時間復雜度上并未作出改進，時間復雜度仍是O(|L||G||M|3)[4]，但是通過增加四個字段以及改變數據存儲結構，以減少不必要的比較，能夠快速定位標準生成器，大大減少運行時間。

整個實驗所使用的數據集均為隨機生成，這幾種數據集的填充率(|I|/|G||M|)各不相同，分別為10%、24%和40%。對象個數固定為50，但是屬性的個數則是變化的，而且每個屬性所對應的對象個數也不一樣。

圖4展示了FastAddExtent算法和AddExtent算法在填充率為10%（低密度）的數據集上的運行時間對比。實驗數據從100個屬性開始增加到30 000，對象個數保持在50不變，由實驗結果得到的折線圖可知，在低密度下并且對象保持個數為50不變，屬性個數相對較少的情況下，FastAddExtent算法和AddExtent算法在時間上沒有明顯的差別。但是，隨著屬性個數的不斷增加，FastAddExtent算法相比AddExtent算法在運行時間的優勢明顯，并且有逐漸拉大差距的趨勢（當|M|大約在2 500時，FastAddExtent算法運行時間低于AddExtent算法）。

Fig.4 Comparison results of concept lattice construction with low density圖4 低填充率下概念格構建結果比較

Fig.5 Comparison results of concept lattice construction with medium density圖5 中等填充率下概念格構建結果比較

圖5顯示了FastAddExtent算法和AddExtent在填充率為24%（中等密度）的數據集上運行時間結果的比較。實驗從屬性個數25開始增加到10 000，實驗期間，對象個數保持50不變。從折線圖5中可以看出，相比填充率為10%的結果圖，在中等填充率下，相同對象個數、相同屬性個數之間運行時間差距拉大。同時，FastAddExtent算法在屬性個數較少的情況下也能獲得運行時間上的較大優勢（當|M|大約在1 250時，FastAddExtent算法運行時間低于AddExtent算法）。

圖6展示了FastAddExtent算法和AddExtent算法在填充率為40%（高密度）的隨機數據集上的運行時間的比較結果。實驗從屬性個數為10個開始進行，直至增加到1 000個，期間對象個數保持50不變。由于在高密度的數據集下，產生的概念的個數巨大，概念格的規模龐大，對內存資源的消耗非常迅速。于是，在現有的實驗條件下，只能對屬性個數較少的部分進行測試。從實驗得到的折線圖可以直觀地看出，相比填充率為10%和24%的情況，FastAdd-Extent算法和AddExtent算法在運行時間上都快速上升。相比圖4和圖5的實驗顯示，相交的點在橫坐標下提前了許多，并且FastAddExtent算法和AddExtent算法在交匯點之后的每一個測試點都具有明顯的優勢（當|M|大約在100時，FastAddExtent算法運行時間低于AddExtent算法）。

Fig.6 Comparison results of concept lattice construction with high density圖6 高填充率下概念格構建結果比較

4 結束語

向概念格中添加屬性的增量式算法可以用來構造概念格也可以用來更新概念格。介紹了一種快速有效的增量式概念格構造算法FastAddExtent。該算法是在已有的AddExtent算法下增加了字段，在GetClosureConcept函數下引用Hash查找函數的方法，減少了不必要的比較，從而減少了運行時間。

FastAddExtent算法采用哈希表的方式存儲概念，它幾乎能在所有的測試點上獲得明顯的優勢，而且即便是在屬性個數較少的稀疏數據集上也能花費比AddExtent算法更少的時間，而且雙方之間的性能差距會隨著屬性個數的增大而增大。理論分析和性能測試都有說明，在對象個數較大的情況下應用FCA方法時，FastAddExtent算法是一種相比AddExtent算法更好的選擇。