基于Hasse圖的概念格的一種漸減式構(gòu)造算法

李海霞

（安徽新華學(xué)院公共課教學(xué)部,安徽合肥230088）

基于Hasse圖的概念格的一種漸減式構(gòu)造算法

李海霞

（安徽新華學(xué)院公共課教學(xué)部,安徽合肥230088）

提出了基于概念格Hasse圖的一種對象漸減式構(gòu)造算法,從Hasse圖的最大節(jié)點(diǎn)開始,沿著僅包含該對象的路徑,自頂向下完成概念格的構(gòu)造,不需要遍歷所有的節(jié)點(diǎn),也不需要重新構(gòu)造概念格.

概念格；Hasse圖；節(jié)點(diǎn)；對象

自從德國的Wille教授1982年提出新式概念分析以來[1],作為其核心數(shù)據(jù)結(jié)構(gòu)——概念格,已經(jīng)在數(shù)據(jù)挖掘、知識發(fā)現(xiàn)、信息檢索、軟件工程、本體研究等很多領(lǐng)域得到廣泛的應(yīng)用[2-5].

在應(yīng)用過程中,由于數(shù)據(jù)庫中的數(shù)據(jù)是變化的、動態(tài)的,為了符合動態(tài)環(huán)境下概念格應(yīng)用的需求,概念格維護(hù)的研究也是一個重要的方面.針對概念格的維護(hù),已有的算法有：Godin提出了一種在新增對象的情況下,漸進(jìn)式更新概念格的所有概念節(jié)點(diǎn)及其Hasse圖[6]；李云、劉宗田等將原概念格節(jié)點(diǎn)按外延的勢從小到大檢查,通過不斷增加屬性完成概念格的更新[7]；曲立平等利用樹結(jié)構(gòu)組織節(jié)點(diǎn),以此來減小更新節(jié)點(diǎn)及產(chǎn)生子格節(jié)點(diǎn)的搜索范圍,提出基于屬性的概念格的一種構(gòu)造算法,減少了格的構(gòu)造時間[8].

以上這些研究關(guān)注的是增加對象或者屬性時的概念格的構(gòu)造與維護(hù),但隨著概念格應(yīng)用范圍的不斷擴(kuò)展,需要研究在概念格中減少對象或?qū)傩詴r概念格的構(gòu)造與維護(hù),比如單位員工辭職、刪除數(shù)據(jù)庫中的一條記錄等.近年,張磊等提出了自頂向下和自底向上兩種基于概念格屬性漸減的原理和算法,在原概念格的基礎(chǔ)上直接更新概念格,比重新從形式背景構(gòu)造概念格節(jié)省大量時間[9]；智慧來提出了對象漸減時概念格的維護(hù)算法[10],該算法中定義了唯一路徑上的關(guān)鍵概念,但在對節(jié)點(diǎn)定位時需遍歷所有的概念,這可能會影響算法的效率.

本文提出了基于概念格Hasse圖的一種對象漸減式構(gòu)造算法,從Hasse圖的最大節(jié)點(diǎn)開始,沿著僅包含該對象的路徑,自頂向下完成概念格的構(gòu)造,不需要遍歷所有的節(jié)點(diǎn),也不需要重新構(gòu)造概念格.

1 概念格的基本概念

研究需要用到文獻(xiàn)[1]中的以下定義：

定義1一個形式背景K=（O,D,R）,其中O是對象集,D是屬性集,xRy表示對象x具有屬性y.

定義2設(shè)對象集A?O,屬性集B?D,定義A'={m∈D|任意的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)涵（記為In（tC））.

定義3設(shè)C1=（A1,B1）和C2=（A2,B2）是兩個概念,若A1?A2（等價于B1?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.如形式背景1對應(yīng)的概念格,如圖1所示.

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

圖1 形式背景1對應(yīng)的Hasse圖Fig.1 Hasse diagram of the formal context 1

2 基于Hasse圖的概念格漸減式構(gòu)造算法

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

為了研究減少對象a后概念格變化的規(guī)律,根據(jù)原概念格中每個節(jié)點(diǎn)C的外延和被消減對象a之間的關(guān)系,給出如下定義：

定義4如果a∈Ext（C）,則稱C是不變節(jié)點(diǎn).

定義5如果a∈Ext（C）,并且節(jié)點(diǎn)C的所有子節(jié)點(diǎn)的外延均不等于Ext（C）-a,則稱C是更新節(jié)點(diǎn).

定義6如果a∈Ext（C）,并且節(jié)點(diǎn)C的某一子節(jié)點(diǎn)的外延等于Ext（C）-a,則稱C是刪除節(jié)點(diǎn).

設(shè)原概念格為L（K）,刪除對象a后對應(yīng)新概念格為L（K*）.

定理1若（A,B）為L（K）的不變節(jié)點(diǎn),則（A,B）∈L（K*）.

證明：設(shè)（A,B）∈L（K）,且為不變節(jié)點(diǎn),則a∈A,A'=B,B'=A.因?yàn)樵谠问奖尘癒和K*中,對應(yīng)關(guān)系R不變,所以在新概念格L（K*）中仍有A'=B,B'=A,即（A,B）∈L（K*）.

定理2若（A,B）為L（K）的更新節(jié)點(diǎn),則（A-{a},B）∈L（K*）.

證明：因?yàn)椋ˋ,B）∈L（K）,所以A'=B,即B為對象集A具有的所有共同屬性；由更新節(jié)點(diǎn)的定義,a∈A,所以{a'}?B；外延減小,內(nèi)涵增大,所以又有（A-{a}）'?B.

下證（A-{a}）'=B.若（A-{a}）'≠B,則（A-{a}）'∩（{a'}-B）≠椎,又因?yàn)閍∈A,所以必有A'?B,與A'=B矛盾.即對象集A-{a}具有的所有屬性為B,屬性B對應(yīng)的所有對象為A-{a},亦即（A-{a},B）∈L（K*）.

性質(zhì)1若（A,B）為L（K）的刪除節(jié)點(diǎn),則其必有一個外延為A-{a}的直接子節(jié)點(diǎn),且該直接子節(jié)點(diǎn)為不變節(jié)點(diǎn).

證明：因?yàn)榫哂懈缸雨P(guān)系的兩節(jié)點(diǎn),外延至少相差一個元素,A-{a}僅比A少一個元素；由定義6,刪除節(jié)點(diǎn)必然有一個子節(jié)點(diǎn)外延為A-{a},所以其必有一個外延為A-{a}的直接子節(jié)點(diǎn).因?yàn)閍∈A,由不變節(jié)點(diǎn)的定義,該節(jié)點(diǎn)為概念格的不變節(jié)點(diǎn).

性質(zhì)2設(shè)（A,B）為L（K）的刪除節(jié)點(diǎn),除了外延為A-{a}的直接子節(jié)點(diǎn)外,若還有其它直接子節(jié)點(diǎn),則必為刪除節(jié)點(diǎn).

證明：記C=（A,B）,因?yàn)镃若有其他直接子節(jié)點(diǎn),外延不會為A-{a},即其他直接子節(jié)點(diǎn)不會為不變節(jié)點(diǎn).設(shè)其他任一直接子節(jié)點(diǎn)為C1=（A1,B1）,若C1為更新節(jié)點(diǎn)（設(shè)在新格中對應(yīng)的更新節(jié)點(diǎn)為C1*=（A1-{a},B1））,則a∈A1且C1的子節(jié)點(diǎn)中外延均不等于A1-{a}.因?yàn)镃1

定理3設(shè)形式背景K*=K-{a},則概念格L（K）的不變節(jié)點(diǎn)和更新節(jié)點(diǎn)與新概念格L（K*）中的節(jié)點(diǎn)一一對應(yīng).

證明：設(shè)C1、C2∈L（K）,C1≠C2且為不變節(jié)點(diǎn)或更新節(jié)點(diǎn),由定理2.1、2.2,顯然在新格L（K*）中會對應(yīng)不同C1*、C2*；

反設(shè)C*=（A*,B*）∈L（K*）,既不是原格L（K）中不變節(jié)點(diǎn)保留下來的,也不是更新節(jié)點(diǎn)更新過來的,而是原格L（K）中刪除節(jié)點(diǎn)C=（A,B）對應(yīng)過來的,則B*=B,A*=A-{a}.因?yàn)镃為刪除節(jié)點(diǎn),由定義2.3和性質(zhì)2.1,則a∈A,并且C有一個直接子節(jié)點(diǎn)C1=（A1,B1）,A1=A-{a}（該節(jié)點(diǎn)為不變節(jié)點(diǎn),將保留到新格L（K*）中）.外延減小,節(jié)點(diǎn)內(nèi)涵會增大,所以B?B1.對節(jié)點(diǎn)（A*,B*）、C1=（A1,B1）=（A1-{a},B1）∈L（K*）來說,二者外延相同,內(nèi)涵不同,顯然是錯誤的,所以假設(shè)不成立,即新格L（K*）中的節(jié)點(diǎn)必然是由原概念格中的不變節(jié)點(diǎn)保留下來的,或者是更新節(jié)點(diǎn)更新過來的.

由定理1、2、3,若刪除對象a,對原概念格中不變節(jié)點(diǎn)保留,更新節(jié)點(diǎn)更新（外延減去a,內(nèi)涵不變）,刪除節(jié)點(diǎn)直接刪除,就可以得到新格的所有節(jié)點(diǎn),不需要重新構(gòu)造概念格.

除了節(jié)點(diǎn)的變化,下面來確定節(jié)點(diǎn)之間邊的變化.

定理4設(shè)C1、C2為概念格L（K）的不變節(jié)點(diǎn)或更新節(jié)點(diǎn),并且二者在新概念格L（K*）中分別對應(yīng)C1*和C2*.若C1

證明：設(shè)C1=（A1,B1）,C2=（A2,B2）,則C1*=（A1,B1）或（A1-{a},B1）,C2*=（A2,B2）或（A2-{a},B2）.因?yàn)樵谠馤（K）中不存在第三個節(jié)點(diǎn)C3=（A3,B3）,使B1B3B2,由定理2.3,新格L（K*）中節(jié)點(diǎn)是由原格L（K）中節(jié)點(diǎn)對應(yīng)過來的,同樣在C1*和C2*之間不會存在第三個節(jié)點(diǎn)C3*=（B3',B3）,使B1?B3?B2,所以C1*

由定理4,若直接父子節(jié)點(diǎn)均為不變節(jié)點(diǎn)或更新節(jié)點(diǎn),則對應(yīng)節(jié)點(diǎn)在新格中保持同樣的直接父子關(guān)系,所以只要考慮刪除節(jié)點(diǎn)的直接父節(jié)點(diǎn)和直接子節(jié)點(diǎn)有無直接父子關(guān)系.因?yàn)閯h除節(jié)點(diǎn)的直接子節(jié)點(diǎn)若為刪除節(jié)點(diǎn)仍需刪除,所以只要考慮該刪除節(jié)點(diǎn)的直接子節(jié)點(diǎn)為不變節(jié)點(diǎn)（設(shè)為C1）的節(jié)點(diǎn).在刪除刪除節(jié)點(diǎn)的各相應(yīng)邊時,若某一直接父節(jié)點(diǎn)到C1仍有其他路徑連接,則不需要新增邊；若無路徑連接,則將該直接父節(jié)點(diǎn)到C1增加一條邊.

2.2 基于Hasse圖的概念格的對象漸減式構(gòu)造算法

根據(jù)以上性質(zhì)、定理,刪除對象a時,從概念格的最大節(jié)點(diǎn)（該節(jié)點(diǎn)一定包含對象a）開始,對不包含對象a的直接子節(jié)點(diǎn)及其以下節(jié)點(diǎn)、邊不做任何變化,對包含對象a的所有直接子節(jié)點(diǎn),沿著概念格的Hasse圖,自上向下,判斷節(jié)點(diǎn)的類型,若為更新節(jié)點(diǎn),外延減去a,內(nèi)涵不變即為新格的節(jié)點(diǎn),節(jié)點(diǎn)之間的邊暫且不變.若為刪除節(jié)點(diǎn),刪除該節(jié)點(diǎn)及各邊；對該節(jié)點(diǎn)的直接子節(jié)點(diǎn)中的不變節(jié)點(diǎn)C1,若其某一直接父節(jié)點(diǎn)到C1仍有其他路徑連接,則不需要新增邊,若無路徑連接,則將該直接父節(jié)點(diǎn)到C1增加一條邊；對該節(jié)點(diǎn)的其他直接子節(jié)點(diǎn)因?yàn)橐矠閯h除節(jié)點(diǎn),所以予以刪除,邊的處理同上.

算法步驟描述如下：

（1）從概念格的Hasse圖取出最大節(jié)點(diǎn),令A(yù)=A-{a}、B=B；

（2）取出節(jié)點(diǎn)（A,B）的一個不帶標(biāo)記“Y”的直接子節(jié)點(diǎn),記為（A,B）；（標(biāo)示“Y”表示該節(jié)點(diǎn)已經(jīng)處理）

（4）若a∈A,并且節(jié)點(diǎn)（A,B）的所有子節(jié)點(diǎn)的外延均不等于A-{a}（,A,B）給以標(biāo)示“Y”,令A(yù)=A-{a}, B=B,轉(zhuǎn)向⑵；

（5）若a∈A,并且節(jié)點(diǎn)（A,B）的某一直接子節(jié)點(diǎn)的外延等于A-{a},節(jié)點(diǎn)（A,B）給以標(biāo)示“Y”“S”,將外延為A-{a}的直接子節(jié)點(diǎn)標(biāo)示為“Y”“B”,并判斷該直接子節(jié)點(diǎn)與節(jié)點(diǎn)（A,B）的直接父節(jié)點(diǎn)有無路徑連接,若有則不需要新增邊,若無路徑連接,則將該直接父節(jié)點(diǎn)到該直接子節(jié)點(diǎn)增加一條邊,然后刪除標(biāo)示為“Y”“S”的節(jié)點(diǎn)；將其它直接子節(jié)點(diǎn)標(biāo)記為“Y”“S”,均記為（A,B）,重復(fù)步驟⑸；

⑹若節(jié)點(diǎn)（A,B）的內(nèi)涵B等于屬性集D,將其和對應(yīng)的直接父節(jié)點(diǎn)連邊,結(jié)束.

這樣就得到刪除對象a后,新概念格的Hasse圖,圖中各節(jié)點(diǎn)即為新格的各個概念,不需要遍歷所有的節(jié)點(diǎn),不需要重新構(gòu)造概念格,在原概念格Hasse圖的基礎(chǔ)上就得到新概念格的Hasse圖,極大提高了概念格維護(hù)的效率.

3 舉例

從形式背景1中刪除對象{5},根據(jù)該算法,首先取出最大節(jié)點(diǎn)（12345,椎）,將其更新為（1234,椎）；沿著Hasse圖向下,依次判斷各個直接子節(jié)點(diǎn)：5∈{125}、5∈{1345}且節(jié)點(diǎn)（125,ad）、（1345,c）的各直接子節(jié)點(diǎn)外延均不等于A-{5},即二者為更新節(jié)點(diǎn),分別更新為（12,ad）、（134,c）,均標(biāo)示為“Y”；5∈{234},節(jié)點(diǎn)（234,b）為不變節(jié)點(diǎn),標(biāo)示為“Y”,其對應(yīng)的Hasse圖以下部分不作任何變化,也不再考慮；再取出帶標(biāo)示“Y”節(jié)點(diǎn)的各直接子節(jié)點(diǎn)：5∈{15}且其各子節(jié)點(diǎn)外延均不等于A-{5},即（15,acd）為更新節(jié)點(diǎn),更新為（1, acd）標(biāo)示為“Y”,5∈{34},（34,bc）為不變節(jié)點(diǎn),標(biāo)示為“Y”,其對應(yīng)的Hasse圖以下部分不作任何變化,也不再考慮；5∈{45},且有一直接子節(jié)點(diǎn)（4,bce）的外延等于A-{5}（為刪除節(jié)點(diǎn)）,將節(jié)點(diǎn)（4,bce）標(biāo)示為“Y”“B”,因?yàn)椋?,bce）與該刪除節(jié)點(diǎn)的直接父節(jié)點(diǎn)（1345,c）有路徑連接,所以不增加邊,然后直接將（45,ce）刪除,最后將節(jié)點(diǎn)（45,ce）的其它直接子節(jié)點(diǎn)亦即（5,acde）標(biāo)示“Y”“S”；取出（5,acde）所有直接子節(jié)點(diǎn)（只有一個（椎,abcde））5∈椎,即（椎,abcde）為不變節(jié)點(diǎn),標(biāo)示為“Y”“B”,將節(jié)點(diǎn)（1,acd）、（椎,abcde）之間連邊,并刪除（5,acde）又因?yàn)楣?jié)點(diǎn)（椎,abcde）的內(nèi)涵等于屬性集{abcde},算法結(jié)束.

4 小結(jié)

本文提出了基于概念格Hasse圖的一種對象漸減式構(gòu)造算法,從Hasse圖的最大節(jié)點(diǎn)開始,根據(jù)節(jié)點(diǎn)的類型,只需要沿著Hasse圖的僅包含該對象的路徑,自頂向下即可完成概念格的構(gòu)造,不需要遍歷所有的節(jié)點(diǎn),極大提高了刪除對象后概念格的構(gòu)造效率.當(dāng)然,實(shí)際工作中可能需要同時刪除兩個及以上的對象,這將是下一步的研究工作.

[1]Ganter B,Wille R.Formal concept analysis：mathematical foundation[M].New York：Springer-Verlag,1999.

[2]Li J Y,Mei C L,Lv Y J.Knowledge reduction in real decision formal contexts[J].Information Sciences,2012,189（15）：191-207.

[3]Mehdi K,Sergei O K,Amedeo N,et al.Mining gene expression data with pattern structure in formal concept analysis[J].Information Sciences,2011,181（10）：1989-2001.

[4]Qu K S,Zhai Y H,Liang J Y,et all.Study of decision implications based on formal concept analysis[J].Journal of General Systems, 2007,36（2）：147-156.

[5]Fethi F,Samir E,Ali J,et al.Formal context coverage based on isolated labels：An efficient solution for text feature extraction[J]. Information Sciences,2012,188（1）：198-214.

[6]Godin R,Missaoui R,Alaoui H.Incremental concept formation algorithms based on Galois（concept）lattices[J].Computational Intelligence,1995,11（2）：246-267.

[7]李云,劉宗田,陳崚,等.基于屬性的概念格漸進(jìn)式生成算法[J].小型微型計(jì)算機(jī)系統(tǒng),2004,25（10）：1768-1771.

[8]曲立平,劉大昕,楊靜,等.基于屬性的概念格快速漸進(jìn)式構(gòu)造算法[J].計(jì)算機(jī)研究與發(fā)展,2007,44（S）：251-256.

[9]張磊,張宏莉,殷麗華,等.概念格的屬性漸減原理與算法研究[J].計(jì)算機(jī)研究與發(fā)展,2013,50（2）：248-259.

[10]智慧來.概念格對象漸減維護(hù)與關(guān)聯(lián)規(guī)則更新[J].計(jì)算機(jī)工程與用,2014,50（1）：21-23,35.

（責(zé)任編輯：盧奇）

A decreasing algorithm of concept lattice based on Hasse diagram

Li Haixia
（Department of Public Teaching,Anhui Xinhua University,Hefei 230088,China）

One decreasing algorithm of concept lattice was proposed,when one object was deleted.Based on the Hasse diagram,starting from the greatest node,along the path which only contains the object deleted,from top to down, the new concept lattice could be completed,without travelling all the nodes of the original concept lattice and reconstructing the new concept lattice from its corresponding formal context.At the same time,the new Hasse diagram can be obtained,too.

concept lattice；Hasse diagram；node；object

O153,TP301

A

1008-7516（2015）03-0057-04

10.3969/j.issn.1008-7516.2015.03.012

2015-04-07

安徽省自然科學(xué)項(xiàng)目（KJ2013B107）；安徽新華學(xué)院項(xiàng)目（2014zr011,2014zr014）

李海霞（1982―）,女,碩士,講師.主要從事概念格堯智能信息處理研究.