概念格的一種并行構(gòu)造算法

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

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

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

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

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

1 概念格的基本概念

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

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

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

2 概念格的分級合并算法

2.1 相關(guān)定義及定理

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

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

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

定理2兩個子概念格的節(jié)點(diǎn)按照內(nèi)涵基的升序排列,將兩子格進(jìn)行合并,則新概念格中父節(jié)點(diǎn)一定在子節(jié)點(diǎn)之前生成.

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

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

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

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

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

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

例如,子概念格L（K1）中的節(jié)點(diǎn)&1 和子格L（K2）中的節(jié)點(diǎn)合并,若生成新節(jié)點(diǎn),稱該節(jié)點(diǎn)為1 級節(jié)點(diǎn),為方便格的合并,根據(jù)生成的先后次序,分別標(biāo)記為C1,1,C1,2….

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

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

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

2.2 算法原理與分析

一般來講,概念格的時間復(fù)雜度是隨著節(jié)點(diǎn)的個數(shù)呈指數(shù)級增長,所以在構(gòu)造過程中應(yīng)盡量降低節(jié)點(diǎn)之間的比較次數(shù)來提高建格效率.

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

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

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

2.3 算法描述

算法描述如下：

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

3 實例

假設(shè)有兩個形式背景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）節(jié)點(diǎn)按內(nèi)涵升序排列,L（K1）中節(jié)點(diǎn)（45,ce）、（4,bce）、（5,acde）編號分別為&1、&2、&3、&4,L（K2）中節(jié)點(diǎn)、（23,b）、（13,c）、（12,ad）、（3,bc）、（1,acd）、（2,abd）a-e）編號分別為#1、#2、#3、#4、#1、#5、#6、#7、#8.根據(jù)上述算法,將L（K1）中的點(diǎn)和L（K2）中的節(jié)點(diǎn)依次進(jìn)行合并,合并過程如表3 所示.

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

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

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

4 小結(jié)

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