概念格的一種并行構造算法

李海霞,聶東明,汪慧,王興龍

（安徽新華學院通識教育部,安徽合肥230088）

20 世紀80 年代,Wille 教授提出了形式概念分析（FCA）,由形式背景,根據偏序關系,可以建立其數據結構——概念格[1].如今,概念格已經被廣泛應用于數據挖掘、角色挖掘、醫藥研究、礦藏開采等多個領域中[2-8].

隨著網絡技術和數據分布并行存儲、處理的發展,同一個數據系統,可能每天都要增加大量的數據,而海量數據需要挖掘其中蘊含的有用信息,多概念的并行構造算法也應運而生[9-11].目前概念格的并行構造一般會利用子概念格原有的信息,不需要遍歷概念格的所有節點,算法效率都有明顯提高.但不少方法是對原來子概念格的相關節點進行調整,再來確定合并之后概念格節點之間的父子關系.因為概念格中父子關系的確定非常麻煩,后合并生成的節點可能和前面合并生成的不同節點之間均有直接父子關系,所以這項工作量也是很大的.

本文討論了概念格的一種并行構造算法.構造過程中,子概念格的節點按照內涵的升序排列,并給出了節點級的概念,方便確定并行構造過程中,新生成節點之間的直接父子關系,只需要比較部分級中的部分節點即可自底而上生成新的概念格,同時生成新概念格的Hasse 圖.

1 概念格的基本概念

定義1一個形式背景K=（O,D,R）,其中O 是對象集,D 是屬性集,xRy 表示對象x 具有屬性y.設對象集,屬性集定義任意的g∈A,gRm},B"={g∈O| 任意的m∈B,gRm}.若A、B 滿足A"=B,B"=A,則稱二元組C=（A,B）為一個概念（或節點）,A 稱為概念C 的外延（記為Ext（C））,B 稱為概念C 的內涵（記為Int（C））[12].

定義2設C1=（A1,B1）和C2=（A2,B2）是兩個概念,若（等價于）,稱C1為C2的父概念（節點）,C2為C1的子概念（節點）,記為C1≥C2.形式背景K 的所有概念按照這種偏序關系形成的格稱為形式背景K 的概念格,記為L（K）.若不存在節點C3,使C1≥C3≥C2,則稱C1為C2的直接父概念（節點）,C2為C1的直接子概念（節點）,記為C1＞C2.按照這種偏序關系,所有節點構成了概念格,記為L（O,D,R）,其中最大的節點是（O,O’）,最小的節點是（D,D’）[12].

定義3設兩個形式背景K1=（O1,D,R1）和K2=（O2,D,R2）,二者有相同的屬性集,K1±K2=（O1∪O2,D,R1∪R2）稱為兩形式背景的合并[12].

2 概念格的分級合并算法

2.1 相關定義及定理

概念格的合并是將一個子概念格中的節點依次插入另一個子概念格,生成一個新概念格,然后再將一個子概念格插入這個新格中,依次下去,合并生成一個較大的概念格.概念格進行合并時,有兩個問題需要處理：新節點的生成和邊的更新.為解決上述問題,結合前期的研究工作,給出如下定義和定理.

定理1屬性集相同的形式背景對應的概念格L（K1）中的節點C1=（A1,B1）和L（K2）中的節點C2=（A2,B2）若生成一個新節點C,都有C=（A1∪A2,B1∩B2）[13].

定理1 只是解決了新節點的內涵和外延問題,但是還需要判定什么時候才會生成新節點.并行構造中,兩子概念格節點內涵的交集如果是第一次出現,一定會生成新節點.而判斷內涵的交集是不是第一次出現,如果和先前生成的新節點逐一進行比較,尤其是格結構比較龐大時,比較次數很多,會降低建格速度.為減少比較次數,提高建格效率,需要利用概念格的層次結構.下面給出判斷新節點生成和新概念格中節點之間邊的關系的相關定理.

定理2兩個子概念格的節點按照內涵基的升序排列,將兩子格進行合并,則新概念格中父節點一定在子節點之前生成.

因為父節點內涵比子節點的內涵少,即父節點內涵的基小,而兩個被合并的子概念格節點是按照內涵基的升序排列的,由兩個節點的內涵的交判斷是否生成新節點,所以若兩新節點之間有父子關系,先生成的節點內涵的基一定小,所以父節點一定在子節點之前生成.

定理3兩個子概念格的節點按照內涵基的升序排列,如果概念格L（K1）中的同一節點與概念格L（K2）中的兩個不同節點合并時都能生成新節點,則后生成的節點一定是先生成節點的子節點,并且后生成的節點一定是上一個新生成節點的直接子節點.

證明：由定理2,若生成新節點,子節點一定在父節點之后生成.所以,如果概念格L（K1）中的同一節點與概念格L（K2）中的兩個節點合并生成新節點之間若有父子關系,則后生成的節點一定是先生成節點的子節點,并且后生成的節點一定是上一個生成節點的直接子節點,所以只要證明生成的兩個新節點之間必有父子關系即可.

設節點D1∈L（K1）,節點E1、E2∈L（K2）,D1與E1,D1與E2合并先后生成新節點C1=（A1,B1）和C2=（A2,B2）,所以有B1=int（D1）∩int（E1）,B2=int（D1）∩int（E2）,因為節點是按照內涵升序排列,所以有B1B2,否則不會合并生成新節點,所以節點C1和C2之間有父子關系.假設C2不是節點C1的直接子節點,即二者之間還存在一個新生成的節點C3=（A3,B3）,使得C2＜C3＜C1,其中節點C3也是由格L（K1）中的同一個節點D1和概念格L（K2）中的另一個節點E3合并生成的,則有B3=int（D1）∩int（E3）,且B1B3B2.又因為B1=int（D1）∩int（E1）,B2=int（D1）∩int（E2）,B3=int（D1）∩int（E3）,并且節點C1,C3和C1都是和子格L（K1）中的同一個節點D1合并生成的,所以int（E3）一定比int（E2）少,比int（E1）多,概念格的性質,則在子概念格L（K2）中一定存在節點E2和E3的父節點E,節點E 和子格L（K1）中的同一個節點D1一定也能在新節點C1和C2之間合并生成一個新節點C3,與題設矛盾,所以C2一定是新節點C1的直接子節點.

由定理3,若同一節點與另一子格L（K2）中的兩個不同節點合并時都能生成新節點,后生成的節點一定是上一個生成節點的直接子節點,則在Hasse 圖中二者即可連邊.為方便概念格的合并及其Hasse圖的構建,下面給出節點級的定義.

定義4兩個子概念格的節點按照內涵基的升序排列,如果子格L（K1）中的節點&i 和另一子格L（K2）中的節點合并能生成一個新節點,則該新節點稱為i 級節點,其中i 表示子格L（K1）中的第i 節點.

例如,子概念格L（K1）中的節點&1 和子格L（K2）中的節點合并,若生成新節點,稱該節點為1 級節點,為方便格的合并,根據生成的先后次序,分別標記為C1,1,C1,2….

定理4兩個子概念格的節點按照內涵基的升序排列,概念格L（K1）中的一個節點與概念格L（K2）中的兩個不同節點合并,如果生成的新節點位于同一級,則后生成的節點是先生成節點的子節點,并且后生成的一定是上一個新生成節點的直接子節點.

證明：顯然,如果新節點位于同一級,則新節點一定是由一個子格中的同一節點和另一子格中的兩個不同節點合并生成的,所以由定理3,即證.

因此,當一個子格中的節點和另一子格中的不同節點合并生成新節點時,它們必然屬于同一級,根據標記Ci,j,同一級節點之間只要根據j 的大小次序,即可判斷它們之間的父子關系并連邊,這將會提高概念格的建格效率.

2.2 算法原理與分析

一般來講,概念格的時間復雜度是隨著節點的個數呈指數級增長,所以在構造過程中應盡量降低節點之間的比較次數來提高建格效率.

由定義4 和以上定理可知,在概念格的合并過程中,子節點會在父節點之后生成.當兩個子概念格中的節點按內涵基的升序排列,子格L（K1）中的節點和子格L（K2）中的不同節點都能生成新節點時,后生成的節點一定是上一個生成節點的直接子節點.所以,L（K1）中同一節點和L（K2）進行合并運算時,如果兩個子格節點內涵的交集包含于上一個新生成的節點的內涵時,合并運算不會生成新節點；如果內涵的交集包含上一個新生成的節點的內涵時,將會生成一個新節點,并且是該新節點的直接子節點.所以,在同一級中,只需要比較兩個要合并的節點內涵的交集與上一個新生成的節點的內涵之間的包含關系,就可以判斷是否有新節點生成.另一方面,在不同的級中,節點之間可能也有父子關系,因此也有必要判斷兩個要合并節點的內涵的交集與其它層節點內涵之間的包含關系,以此來判斷是否有新節點生成,及它們之間的之間父子關系.因為合并運算時,子格節點是按內涵基的升序排列的,所以只要和不同級最下面的節點內涵進行比較判斷,即可以確定是否有必要進行后續的比較,這也會提高合并運算的效率.

本文定義了概念格節點級的節點,子概念格的節點按照內涵的升序排列,在合并的過程中,兩個被合并的節點的內涵的交集（記為集合B）僅與上一個新合并生成的節點作比較,或者自底向上和其他級的部分節點作比較；判斷是否生成一個新節點,也不需要和之前生成的所有節點作比較.在同一級中,只要和上一個新生成的節點做比較；在不同的級中,首先和該級最下面的節點作比較以決定是否需要進一步的比較,如果不需要,則轉向下一級,如果需要,自底而上進行比較,直到一個節點的內涵包含于集合B（當然此時也一定合并生成一個新節點）,該節點和新生成的節點之間連邊,即可轉向下一級,直到所有前面定義的級都比較完畢,然后開始下一個合并運算.

在判斷一個新節點是否生成時,兩新節點之間的直接父子關系也進行了判斷,也就是說,節點之間的邊進行了更新.因此,不但可以得到所有合并的節點,并且還能得到合并之后的概念格的Hasse 圖,此過程也不會產生冗余節點.

2.3 算法描述

算法描述如下：

首先,將子概念格L（K1）和L（K2）中的節點按照內涵的升序排列,生成的新節點標注級.然后,將L（K1）中的每個節點和L（K2）中的每個節點依次合并,在合并過程中,只要判斷兩節點內涵的交集.如果生成新節點,它的內涵和外延即為兩個被合并節點內涵的交集及外延的并集.設兩個被合并節點內涵的交集為B,緊鄰著剛生成節點為Ci,j=（Aj,Bj）,將會有以下4 種情況：

3 實例

假設有兩個形式背景K1=（O1,D,R）和K2=（O2,D,R）,其中對象集O1={1,2,3},O2={4,5},屬性集D={a,b,c,d,e},形式背景如表1 和2.

表2 形式背景2Tab.2 Formal context 2

二者的Hasse 圖如圖1 和圖2.

圖1 概念格L（K1）的Hasse 圖 Fig.1 Hasse diagram of the concept lattice of L（K1）

圖2 概念格L（K2）的Hasse 圖Fig.2 Hasse diagram of the concept lattice of L（K2）

將概念格L（K1）和L（K2）節點按內涵升序排列,L（K1）中節點（45,ce）、（4,bce）、（5,acde）編號分別為&1、&2、&3、&4,L（K2）中節點、（23,b）、（13,c）、（12,ad）、（3,bc）、（1,acd）、（2,abd）a-e）編號分別為#1、#2、#3、#4、#1、#5、#6、#7、#8.根據上述算法,將L（K1）中的點和L（K2）中的節點依次進行合并,合并過程如表3 所示.

表3 概念格L（K1）和L（K2）的合并過程Tab.3 the merging process of concept lattice L（K1）and L（K1）

由生成節點的級與編號,即可得合并之后新概念格的Hasse 圖,見圖3.在此過程中,不需要將新生成的節點和前面生成的所有節點進行比較,即可判定是否生成一個新節點及新節點的所有直接父節點,可以極大的提高建格效率.

圖3 新概念格L（K）的Hasse 圖Fig.3 Hasse diagram of the new concept lattice L（K）

4 小結

本文提出了基于節點級的概念格的一種并行構造算法,只需要將新節點和前面剛生成的節點或者部分級中的部分節點自下而上作比較,即可以判定是否生成新節點及節點之間的父子關系,從而得到合并之后概念格的Hasse 圖,自上而下構造出新概念格.當然,對概念格的并行構造來講,如何進一步提高構造效率需繼續展開研究.