概念格維護(hù)原理與算法

智慧來(lái)，智東杰

河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作 454150

概念格維護(hù)原理與算法

智慧來(lái)，智東杰

河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南焦作 454150

將把形式背景的變化分為對(duì)象-屬性關(guān)系的增加和刪除、對(duì)象或?qū)傩缘脑黾雍蛣h除兩類(lèi)，分別研究了這兩類(lèi)變化引起的概念格的維護(hù)問(wèn)題。在對(duì)象-屬性關(guān)系的增加引起的概念格維護(hù)中，提出了父子概念對(duì)的概念，用來(lái)確定概念格維護(hù)的位置以及概念之間關(guān)系的調(diào)整。在對(duì)象-屬性關(guān)系的刪除引起的概念格維護(hù)中，提出確定概念格維護(hù)位置后用父子概念對(duì)代替被維護(hù)的概念，對(duì)父子概念對(duì)中的冗余概念進(jìn)行判別并對(duì)父子概念對(duì)進(jìn)行更新。在對(duì)象或?qū)傩缘膭h除引起的概念格維護(hù)中，提出了利用唯一路徑上的關(guān)鍵概念來(lái)調(diào)整因?yàn)楦拍畹膭h除引起的概念之間關(guān)系的變動(dòng)。

概念格；概念格維護(hù)；父子概念對(duì)；關(guān)鍵概念

1 引言

R.Wille[1]提出的形式概念分析是以序理論和完備格理論為基礎(chǔ)，依據(jù)數(shù)據(jù)庫(kù)中提供的基本信息建立起的一種刻畫(huà)對(duì)象與屬性之間關(guān)系的數(shù)學(xué)結(jié)構(gòu)。概念格是形式概念分析的核心數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)形式背景建立其對(duì)象的概念格。在動(dòng)態(tài)開(kāi)放的環(huán)境下，概念格的維護(hù)是經(jīng)常的、普遍的。

形式背景是描述現(xiàn)實(shí)世界的二維表格，形式背景的變化有多種情形，但都可以歸結(jié)為兩類(lèi)：（1）對(duì)象-屬性關(guān)系的增加和刪除；（2）對(duì)象或?qū)傩缘脑黾雍蛣h除。在本文中，稱(chēng)對(duì)象-屬性關(guān)系的增加和刪除引起的概念格維護(hù)為第一類(lèi)維護(hù)，稱(chēng)對(duì)象或?qū)傩缘脑黾雍蛣h除引起的概念格維護(hù)為第二類(lèi)維護(hù)。

概念格維護(hù)是一個(gè)重要的但少有研究的問(wèn)題?，F(xiàn)有的外文文獻(xiàn)都是基于概念格的數(shù)據(jù)庫(kù)維護(hù)，并不是關(guān)于概念格自身的維護(hù)。國(guó)內(nèi)有李云[2-3]、簡(jiǎn)宋全[4-5]等人提到概念格的維護(hù)。文獻(xiàn)[2-3]中提到是一種增量維護(hù)，即增加一個(gè)屬性或?qū)ο髸r(shí)的維護(hù)。文獻(xiàn)[4-5]中提出了對(duì)擴(kuò)展概念格和約減概念格的維護(hù)算法，文獻(xiàn)[4]的算法屬于橫向維護(hù)，即當(dāng)刪除一個(gè)對(duì)象時(shí)的維護(hù)算法；文獻(xiàn)[5]的算法屬于縱向維護(hù)，即當(dāng)屬性刪減時(shí)的維護(hù)算法。

總之，現(xiàn)有研究提及的概念格維護(hù)粒度是對(duì)象或?qū)傩裕锤拍罡竦牡诙?lèi)維護(hù)，并且很不深入，就像文獻(xiàn)[3]中的論述“主要簡(jiǎn)述概念格的橫向維護(hù)和縱向維護(hù)的大致方案”，沒(méi)有對(duì)維護(hù)位置的搜索、冗余概念的判別以及關(guān)系的調(diào)整作出細(xì)致的研究。

2 概念格的第一類(lèi)維護(hù)

概念格的第一類(lèi)維護(hù)是增加或刪除對(duì)象-屬性對(duì)的概念格維護(hù)，是最小粒度的概念格的維護(hù)。例如，在概念格的第二類(lèi)維護(hù)中刪除一個(gè)對(duì)象(1，abcd)，就可以轉(zhuǎn)化為依次刪除對(duì)象-屬性(1，a)、(1，b)、(1，c)以及(1，d)。

在概念格的第一類(lèi)維護(hù)中，增加或者刪除對(duì)象-屬性對(duì)前后其形式背景K=(U，A，I)是“準(zhǔn)正則的”，即：對(duì)于對(duì)象-屬性對(duì)(u，a)，u∈U，f(u)≠{}，且a∈A，g(a)≠{}（形式背景K=(U，A，I)是正則的[6]，若?u∈U，f(u)≠A，f(u)≠{}，且?a∈A，g(a)≠U，g(a)≠{}）。

當(dāng)?u∈U，f(u)={}，?a∈A，增加對(duì)象-屬性對(duì)(u，a)時(shí)，采用概念格的第二類(lèi)維護(hù)，即基于對(duì)象的概念格生成算法中插入對(duì)象的方法實(shí)現(xiàn)概念格的維護(hù)。

且?a∈A，g(a)={}，?u∈U，增加對(duì)象-屬性對(duì)(u，a)時(shí)，采用概念格的第二類(lèi)維護(hù)，即基于屬性的概念格生成算法中插入屬性的方法實(shí)現(xiàn)概念格的維護(hù)。

刪除對(duì)象-屬性對(duì)(u，a)時(shí)，若f(u)=a，即刪除對(duì)象-屬性對(duì)(u，a)后f(u)={}，則采用概念格的第二類(lèi)維護(hù)，即刪除對(duì)象的概念格維護(hù)。

刪除對(duì)象-屬性對(duì)(u，a)時(shí)，若g(a)=u，即刪除對(duì)象-屬性對(duì)(u，a)后g(a)={}，則采用概念格的第二類(lèi)維護(hù)，即刪除屬性的概念格維護(hù)。

2.1 基本原理與算法

定義1如果概念(A1，B1)＞(A2，B2)，并且不存在(A3，B3)，使得(A1，B1)＞(A3，B3)＞(A2，B2)，那么(A1，B1)和(A2，B2)稱(chēng)為是父子概念對(duì)，記做[(A1，B1)，(A2，B2)]，并稱(chēng)(A1,B1)與(A2，B2)構(gòu)成直接父子關(guān)系，(A1，B1)是(A2，B2)的直接父概念，(A2，B2)是(A1，B1)的直接子概念。

下文中“-”代表減運(yùn)算，A-a的意思是從集合A中減去元素a。

定義2父子概念對(duì)[(A1，B1)，(A2，B2)]，任意的對(duì)象a和屬性b，若A1、A2包含對(duì)象a，B1、B2包含屬性b，那么父子概念對(duì)[(A1，B1-b)，(A1-a，B1)]、[(A2，B2-b)，(A2-a,B2)]稱(chēng)為父子概念團(tuán)，記做{[(A1,B1-b)，(A1-a,B1)]，[(A2，B2-b)，(A2-a，B2)]}。

定義3在{[(A1，B1-b)，(A1-a，B1)]，[(A2,B2-b)，(A2-a，B2)]}中，[(A1，B1-b)，(A1-a，B1)]稱(chēng)為是[(A2，B2-b)，(A2-a，B2)]的廣義父概念對(duì)，[(A2，B2-b)，(A2-a，B2)]稱(chēng)為是[(A1，B1-b)，(A1-a，B1)]的廣義子概念對(duì)。

定理1增加關(guān)系(a，b)進(jìn)行概念格的維護(hù)時(shí)，如果父子概念對(duì)[(A1，B1)，(A2，B2)]滿足A1包含a，并且B2包含b，那么生成新概念(A2∪a，B1∪b)，并更新父子概念對(duì)：

若A1=A2∪a，B1∪b=B2，則由生成概念(A2∪a，B1∪b)代替父子概念對(duì)[(A1，B1)，(A2，B2)]；

若A1=A2∪a成立，B1∪b=B2不成立，則由生成節(jié)點(diǎn)(A2∪a，B1∪b)代替父概念(A1，B1)；

若A1=A2∪a不成立，B1∪b=B2成立，則由生成節(jié)點(diǎn)(A2∪a，B1∪b)代替子概念(A2，B2)；

若A1=A2∪a不成立，B1∪b=B2不成立，添加生成的概念。

證明因?yàn)?A2，B2)是(A1，B1)的子概念，所以A2具有屬性B1；又因?yàn)椋珺2包含b，那么A2既具有屬性B1又具有屬性b。因?yàn)锳1包含a，同時(shí)A1具有屬性B1，那么a具有屬性B1∪b。所以A2∪a具有屬性B1∪b，具有屬性B1∪b的對(duì)象只有A2∪a。根據(jù)概念之間的包含關(guān)系易證更新父子概念對(duì)的規(guī)律成立。故定理成立。

定理2刪除關(guān)系(a，b)進(jìn)行概念格的維護(hù)時(shí)，如果概念(A，B)滿足A包含a并且B包含b，則生成父子概念對(duì)[(A，B-b)，(A-a，B)]，并根據(jù)父子概念對(duì)的不同情形，作以下處理：

假定(A1，B1)是(A，B)的一個(gè)父概念，(A2，B2)是(A，B)的一個(gè)子概念，則：

若(A，B-b)的內(nèi)涵與概念(A1，B1)的內(nèi)涵不相同，并且(A-a，B)的外延與(A2，B2)的外延不相同，則同時(shí)保留生成的父概念和子概念；

若(A，B-b)的內(nèi)涵與(A1，B1)的內(nèi)涵相同，則刪除已經(jīng)生成的父概念，只保留子概念(A-a，B)；

若(A-a，B)的外延與(A2，B2)的外延相同，則刪除已經(jīng)生成的子概念，只保留父概念(A，B-b)；

若(A，B-b)的內(nèi)涵與(A1，B1)的內(nèi)涵相同，并且(A-a，B)的外延與(A2，B2)的外延相同，則同時(shí)刪除生成的父概念和子概念。

證明A具有屬性B，刪除關(guān)系(a，b)后，A中的a不具有屬性b，但A-a具有屬性B，因此生成概念(A-a，B)；刪除關(guān)系(a，b)后，A不再具有共同屬性B，但具有屬性B-b，因此生成概念(A，B-b)。綜上所述，生成父子概念對(duì)[(A，B-b)，(A-a，B)]。

生成的父子概念對(duì)的處理與順序無(wú)關(guān)，證明如下：假設(shè)任意兩個(gè)概念(A1，B1)與(A2，B2)是直接父子，并且都滿足更新條件，那么由(A1，B1)生成[(A1，B1-b)，(A1-a,B1)]，由(A2,B2)生成[(A2,B2-b)，(A2-a,B2)]。假設(shè)先生成[(A1，B1-b)，(A1-a，B1)]，容易知道(A1-a，B1)的刪除與(A2,B2)無(wú)關(guān)；假設(shè)先生成[(A2,B2-b)，(A2-a,B2)]，容易知道(A2，B2-b)的刪除也與(A1，B1)無(wú)關(guān)。因此，父子概念對(duì)的處理只和不需要維護(hù)的概念有關(guān)，也就是與維護(hù)的順序無(wú)關(guān)。根據(jù)概念之間的包含關(guān)系易證更新父子概念對(duì)的規(guī)律成立。

性質(zhì)1在父子概念團(tuán){[(A1F,B1F)，(A1,B1)]，[(A2F,B2F)，(A2，B2)]}中，(A1F，B1F)與(A2F，B2F)構(gòu)成直接父子關(guān)系，(A1，B1)與(A2，B2)構(gòu)成直接父子關(guān)系。

性質(zhì)2對(duì)于父子概念團(tuán){[(A1F,B1F)，(A1,B1)]，[(A2F,B2F)，(A2，B2)]}滿足A1F、A2F包含a，B1、B2包含b，增加對(duì)象-屬性對(duì)(a，b)時(shí)，生成概念(A1∪a，B1F∪b)、(A2∪a，B2F∪b)，父子概念團(tuán)的更新方式如下：

（1）父子概念團(tuán)更新為(A1∪a，B1F∪b)、(A2∪a，B2F∪b)，則建立(A1∪a，B1F∪b)與(A2∪a，B2F∪b)的直接父子關(guān)系。

（2）若(A1，B1)更新為(A1∪a，B1F∪b)且(A2，B2)更新為(A2∪a，B2F∪b)，或者(A1F，B1F)更新為(A1∪a，B1F∪b)且(A2F，B2F)更新為(A2∪a，B2F∪b)，則父子概念團(tuán)中四個(gè)概念的連接方式不變。

（3）若[(A1F,B1F)，(A1，B1)]被更新為[(A1∪a，B1F∪b)，(A1，B1)]，[(A2F，B2F)，(A2，B2)]被更新為[(A2F，B2F)，(A2∪a，B2F∪b)]，則父子概念團(tuán)中四個(gè)概念的連接方式不變。

（4）若[(A1F,B1F)，(A1，B1)]被更新為[(A1F,B1F)，(A1∪a，B1F∪b)]，[(A2F，B2F)，(A2，B2)]被更新為[(A2∪a，B2F∪b)，(A2，B2)]，則刪除(A1F，B1F)與(A2∪a，B2F∪b)的直接父子關(guān)系，建立(A1∪a，B1F∪b)與(A2∪a，B2F∪b)的直接父子關(guān)系。

（5）若[(A1F，B1F)，(A1，B1)]被更新為[(A1∪a，B1F∪b)，(A1，B1)]或[(A1F,B1F)，(A1∪a，B1F∪b)]，[(A2F，B2F)，(A2，B2)]被更新為(A2∪a，B2F∪b)，則(A2∪a，B2F∪b)的位置，并刪除(A1F，B1F)與(A2F，B2F)的直接父子關(guān)系。

（6）若[(A1F，B1F)，(A1，B1)]被更新為(A1∪a，B1F∪b)，[(A2F，B2F)，(A2，B2)]被更新為[(A2∪a，B2F∪b)，(A2，B2)]或[(A2F，B2F)，(A2∪a，B2F∪b)]，則(A1∪a，B1F∪b)取代(A1F，B1F)的位置，并刪除(A1，B1)與(A2，B2)的直接父子關(guān)系。

（7）若[(A1F,B1F)，(A1,B1)]中的概念不被(A1∪a,B1F∪b)更新，則建立(A1F，B1F)與(A1∪a，B1F∪b)的直接父子關(guān)系，建立(A1∪a，B1F∪b)與(A1，B1)的直接父子關(guān)系。若[(A2F，B2F)，(A2，B2)]也不被(A2∪a，B2F∪b)更新，則建立(A2F，B2F)與(A2∪a，B2F∪b)的直接父子關(guān)系，則建立(A2∪a，B2F∪b)與(A2，B2)的直接父子關(guān)系。最后建立(A1∪a，B1F∪b)與(A2∪a，B2F∪b)的直接父子關(guān)系。

（8）若[(A1F,B1F)，(A1,B1)]中的概念不被(A1∪a,B1F∪b)更新，則建立(A1F，B1F)與(A1∪a，B1F∪b)的直接父子關(guān)系，建立(A1∪a，B1F∪b)與(A1，B1)的直接父子關(guān)系。

若[(A2F,B2F)，(A2,B2)]更新為[(A2∪a,B2F∪b)，(A2,B2)]，則刪除(A1F，B1F)與(A2F，B2F)的直接父子關(guān)系，并建立(A1∪a,B1F∪b)與(A2F,B2F)的直接父子關(guān)系；若[(A2F,B2F)，(A2,B2)]更新為[(A2F,B2F)，(A2∪a,B2F∪b)]，則不調(diào)整概念關(guān)系。

（9）若[(A2F，B2F)，(A2，B2)]也不被(A2∪a，B2F∪b)更新，則建立(A2F，B2F)與(A2∪a，B2F∪b)的直接父子關(guān)系，則建立(A2∪a，B2F∪b)與(A2，B2)的直接父子關(guān)系。

若[(A1F,B1F)，(A1,B1)]更新為[(A1F,B1F),(A1∪a，B1F∪b)]，則刪除(A1，B1)與(A2，B2)的直接父子關(guān)系，同時(shí)建立(A1∪a，B1F∪b)與(A2∪a，B2F∪b)的直接父子關(guān)系；若[(A1F，B1F)，(A1，B1)]更新為[(A1∪a，B1F∪b)，(A1，B1)]，則不調(diào)整概念關(guān)系。

根據(jù)上面的基本原理和性質(zhì)，可以得到下面的算法。

算法1增加關(guān)系(a，b)時(shí)概念格的維護(hù)算法

步驟1確定概念格的維護(hù)位置：尋找這樣的父子概念對(duì)[(A1，B1)，(A2，B2)]，其中A1包含a，B2包含b。

對(duì)每一對(duì)找到的父子概念對(duì)執(zhí)行步驟2～4：

步驟2生成新概念：生成概念(A2∪a，B1∪b)。

步驟3父子概念對(duì)中概念的更新：根據(jù)定理1更新父子概念對(duì)中的概念。

步驟4修改父子概念對(duì)與鄰接的父子概念對(duì)的關(guān)系：根據(jù)性質(zhì)2調(diào)整父子概念對(duì)與鄰接的父子概念對(duì)的關(guān)系。

步驟5算法結(jié)束，返回。

算法2刪除關(guān)系(a，b)時(shí)概念格的維護(hù)算法

步驟1確定概念格的維護(hù)位置：尋找這樣的(A，B)，其中A包含a，B包含b；假定(A1，B1)是(A，B)的一個(gè)父概念，(A2，B2)是(A，B)的一個(gè)子概念。

步驟2生成父子概念對(duì)：生成父子概念對(duì)[(A,B-b)，(A-a,B)]。

步驟3更新父子概念對(duì)：判斷并執(zhí)行其中的一個(gè)動(dòng)作：

動(dòng)作1若(A，B-b)的屬性與概念(A1，B1)的屬性不相同，并且(A-a，B)的外延與(A2，B2)的外延不相同，則同時(shí)保留生成的父概念和子概念。

動(dòng)作2若(A，B-b)的屬性與概念(A1，B1)的屬性相同，則刪除已經(jīng)生成的父概念，只保留子概念(A-a,B)；若(A-a，B)的外延與(A2，B2)的外延相同，則刪除已經(jīng)生成的子概念，只保留父概念(A，B-b)。

動(dòng)作3若(A，B-b)的屬性與概念(A1，B1)的屬性相同，并且(A-a，B)的外延與(A2，B2)的外延相同，則同時(shí)刪除生成的父概念和子概念。

步驟4建立更新后的父子概念對(duì)之間的關(guān)系：

如果步驟3執(zhí)行動(dòng)作1，則：若父子概念對(duì)連接到父子概念對(duì)，則父概念之間建立連接，子概念之間建立連接。

如果步驟3執(zhí)行動(dòng)作2，則：對(duì)于當(dāng)前處理的父子概念對(duì)，若指向的父子概念對(duì)中的(A，B-b)在步驟3被刪除，則建立指向(A，B-b)的父概念的連接。若指向的父子概念對(duì)中的(A，B-b)在步驟3被刪除，則建立指向(A，B-b)的子概念的連接。

如果步驟3執(zhí)行動(dòng)作3，則：(A，B)的父概念和子概念建立連接。

步驟5算法結(jié)束，返回。

2.2 實(shí)例研究與分析

例1對(duì)于表1中的形式背景K1，先刪除關(guān)系（3，7），然后再增加關(guān)系（3，7），研究概念格的變化過(guò)程。

表1 形式背景K1

形式背景K1對(duì)應(yīng)的概念格L1如圖1所示。

圖1 形式背景K1對(duì)應(yīng)的概念格L1

刪除關(guān)系（3，7）后g(7)≠{}，形式背景是正則的，因此可以采用概念格的第一類(lèi)維護(hù)；同理，再增加關(guān)系（3，7）也可以采用概念格的第一類(lèi)維護(hù)。

概念格L1刪除關(guān)系（3，7）時(shí)概念格的維護(hù)過(guò)程：

步驟1確定概念格的維護(hù)位置：（1234，17），（123，127），（234，178），（23，1278），（34，1378），（3，12378）。

步驟2生成父子概念對(duì)：[（1234，1），（124，17）]，[（123，12），（12，127）]，[（234，18），（24，178）]，[（23，128），（2，1278）]，[（34，138），（4，1378）]，[（3，1238），（{}，12378）]。

步驟3概念的更新：[（1234，1），（124，17）]，[（123，12），（12，127）]，[（234，18），（24，178）]，[（23，128），（2，1278）]， [（34，138），（4，1378）]，[（3，1238），（{}，12378）]。

然后由更新后的概念對(duì)代替維護(hù)位置的概念。

步驟4建立父子關(guān)系：（根據(jù)算法1，略）。

步驟5算法結(jié)束，返回結(jié)果概念格L2。

概念格L2增加關(guān)系（3，7）時(shí)概念格的維護(hù)過(guò)程：

步驟1確定概念格的維護(hù)位置：[（123456，1），（124，17）]，[（12356，12），（12，127）]，[（234，18），（24，178）]，[（23，128），（2，1278）]，[（34，138），（4，13789）]，[（3，1238），（{}，M）]。

步驟2生成新概念：（1234，17），（123，127），（234，178），（23，1278），（34，1378），（3，12378）。

步驟3概念的更新：（1234，17）代替[（123456，1），（124，17）]中的（124，17）；（123，127）代替[（12356，12），（12，127）]中的（12，127）；（234，178）代替[（234，18），（24，178）]；（23，1278）代替[（23，128），（2，1278）]；（34，1378）代替[（34，138），（4，13789）]中的（34，138）；（3，12378）代替[（3，1238），（{}，M）]中的（3，1238）。

步驟4修改父子關(guān)系：（根據(jù)算法2，略）。

步驟5算法結(jié)束，返回結(jié)果概念格L1。

形式背景K2對(duì)應(yīng)的概念格L2如圖2所示。

圖2 形式背景K2對(duì)應(yīng)的概念格L2

特別地，如果增加對(duì)象-屬性關(guān)系(u，5)，?u∈{1，2，3，4，5，6}，因?yàn)間(5)={}，不符合前文形式背景為“準(zhǔn)正則的”的約定，因此不能采用概念格的第一類(lèi)維護(hù)，須采用概念格的第二類(lèi)維護(hù)，即增加一個(gè)屬性。

在概念格中增加一個(gè)對(duì)象-屬性關(guān)系時(shí)需要維護(hù)的父子概念對(duì)有多少呢？在概念格中刪除一個(gè)對(duì)象-屬性關(guān)系時(shí)需要更新的概念有多少呢？這兩個(gè)問(wèn)題可以用實(shí)驗(yàn)進(jìn)行回答。實(shí)際上上述兩個(gè)問(wèn)題是等價(jià)的，有多少需要維護(hù)的父子概念對(duì)就有多少需要更新的概念（這是因?yàn)樵黾雍蛣h除一個(gè)對(duì)象-屬性關(guān)系是互逆的操作）。

下面有一組數(shù)據(jù)來(lái)說(shuō)明：實(shí)驗(yàn)中的形式背景對(duì)象個(gè)數(shù)為100，屬性個(gè)數(shù)為20，對(duì)象屬性間存在關(guān)系的概率為0.2、0.25、0.33。增加或者刪除一個(gè)對(duì)象-屬性關(guān)系，對(duì)于每一個(gè)概率，記錄下5次隨機(jī)的結(jié)果，如表2。

表2 一次概念格第一類(lèi)維護(hù)的維護(hù)數(shù)量統(tǒng)計(jì)

從表2可以得到結(jié)論：概念格的第一類(lèi)維護(hù)中，需要維護(hù)的父子概念對(duì)（或者需要更新的概念）數(shù)量少，占全體概念總數(shù)的比例很小。

3 概念格的第二類(lèi)維護(hù)

概念格的第二類(lèi)維護(hù)的內(nèi)容是對(duì)象或者屬性的增加和刪除，包括基于單個(gè)對(duì)象或單個(gè)屬性的概念格維護(hù)和基于多對(duì)象或多屬性的概念格維護(hù)。

在基于單個(gè)對(duì)象或單個(gè)屬性的概念格維護(hù)中，其中對(duì)象或者屬性的增加其實(shí)是概念格的漸進(jìn)式生成[7]的一個(gè)步驟，因此需要研究的是對(duì)象或者屬性的刪除。

在基于多對(duì)象或多屬性的概念格維護(hù)中，多對(duì)象或多屬性的增加其實(shí)是概念格的縱向合并或橫向合并[8]，因此需要研究的是多對(duì)象或者多屬性的刪除引起的概念格維護(hù)。

3.1 基于單個(gè)對(duì)象或單個(gè)屬性的概念格維護(hù)

在概念格的維護(hù)過(guò)程中，刪除對(duì)象或者屬性概念中的概念發(fā)生相應(yīng)的改變，改變分為兩種類(lèi)型：一種是原有概念的更新，不需要?jiǎng)h除概念；另一種是原有概念更新后成為了冗余的概念，需要將更新后的概念刪除。前一種情形只需要改變概念的內(nèi)涵或者外延，后一種情形需要?jiǎng)h除概念并調(diào)整概念之間的連接關(guān)系。

定義4對(duì)于概念(A1，B1)和概念(A2，B2)，(A1，B1)＞(A2，B2)，如果只存在唯一的一個(gè)概念(Ax，Bx)，使得(A1，B1)＞(Ax，Bx)＞(A2，B2)，那么(Ax，Bx)稱(chēng)為概念(A1，B1)和概念(A2，B2)的唯一路徑上的關(guān)鍵概念。

性質(zhì)3(Ax，Bx)是概念(A1，B1)和概念(A2，B2)的唯一路徑上的關(guān)鍵概念，那么刪除(Ax，Bx)后，則(A1，B1)和(A2，B2)成為父子節(jié)點(diǎn)對(duì)。

定義5概念格中刪除對(duì)象(a，f(a))，對(duì)于任意一個(gè)概念(A，B)，刪除對(duì)象(a，f(a))后更新為(A-a，B)，若A-a={}，或者存在一個(gè)子概念(As，Bs)使得A-a=As，則稱(chēng)(A-a，B)為冗余概念。

算法3概念格中刪除對(duì)象(a，f(a))的維護(hù)算法

步驟1概念的定位：從最大概念開(kāi)始查找外延中包含a的概念(A，B)。

步驟2概念的更新：對(duì)于每一個(gè)在步驟1得到的概念(A，B)，(A，B)更新為(A-a，B)。

步驟3冗余概念的刪除：若A-a={}或者A-a與其子概念的外延相等，則刪除這個(gè)概念。

步驟4關(guān)系的刪除：若刪除的概念不是任何兩個(gè)概念的唯一路徑上的關(guān)鍵概念，則刪除所有與冗余概念關(guān)聯(lián)的指針；若刪除的概念是兩個(gè)概念的唯一路徑上的關(guān)鍵概念，那么這兩個(gè)概念建立連接，成為父子節(jié)點(diǎn)對(duì)。

步驟5算法結(jié)束返回。

算法4（算法3步驟1）概念的定位

建立結(jié)果鏈表L。

建立空隊(duì)列Q，把最大概念放入隊(duì)列Q。

當(dāng)隊(duì)列Q不空時(shí)執(zhí)行下面的動(dòng)作：隊(duì)首的概念出列，記做(A，B)；如果A包含a，則把(A，B)加入到鏈表L；并把(A，B)的子概念放入隊(duì)列Q中。

返回結(jié)果鏈表L。

對(duì)偶地，可以得到概念格中刪除屬性的維護(hù)算法，本文從略。

3.2 基于多對(duì)象或多屬性的概念格維護(hù)

基于多對(duì)象或多屬性的概念格維護(hù)，顧名思義，就是一次增加或者刪除多個(gè)對(duì)象或者多個(gè)屬性的概念格維護(hù)。至于增加多對(duì)象或者多屬性的概念格維護(hù)，實(shí)際上是概念格縱向合并和橫向合并[8]的研究?jī)?nèi)容，這里不再贅述。本文只研究多對(duì)象或多屬性的刪除的概念格維護(hù)。

定義6概念格中刪除的對(duì)象集合為M，對(duì)于任意一個(gè)概念(A,B)，刪除對(duì)象集合為M后更新為(A-M,B)，若A-M={}，或存在一個(gè)子概念(As，Bs)使得A-M=As，則稱(chēng)(A-M，B)為冗余概念。

算法5概念格中刪除的對(duì)象集合M的維護(hù)

對(duì)概念格中的每一個(gè)概念(A，B)，執(zhí)行下列步驟：

步驟1概念的定位：若概念(A，B)外延與M交集不空，則順序執(zhí)行步驟2到步驟4，否則判斷下一個(gè)概念。

步驟2概念的更新：對(duì)于每一個(gè)在步驟1得到的概念(A，B)，(A，B)更新為(A-M，B)。

步驟3冗余概念的刪除：A-M={}，或存在一個(gè)子概念(As，Bs)使得A-M=As，則刪除這個(gè)概念。

步驟4關(guān)系的刪除：若刪除的概念不是任何兩個(gè)概念的唯一路徑上的關(guān)鍵概念，則刪除所有與冗余概念關(guān)聯(lián)的指針；若刪除的概念是兩個(gè)概念的唯一路徑上的關(guān)鍵概念，那么這兩個(gè)概念建立連接，成為父子節(jié)點(diǎn)對(duì)。

對(duì)偶地，可以得到概念格中刪除屬性集合的維護(hù)算法，本文從略。

3.3 實(shí)例研究與分析

例2刪除形式背景K1（表3）中的屬性e的概念格維護(hù)。形式背景K1對(duì)應(yīng)的概念格L1如圖3。

刪除屬性e的概念格的維護(hù)過(guò)程：對(duì)于概念格L1

表3 形式背景K1

圖3 形式背景K1對(duì)應(yīng)的概念格L1

步驟1概念的定位：對(duì)于概念格L1，需要更新的概念為(2，ace)，(3，bce)，(25，ae)，(23，ce)，(235，e)。

步驟2概念的更新：依次更新為(2，ac)，(3，bc)，(25，a)，(23，c)，(235，{})。

步驟3冗余概念的刪除：需要?jiǎng)h除的概念依次為(25，a)，(235，{})。

步驟4關(guān)系的刪除：(25，a)是(1245，a)和(2，ac)的唯一路徑上的關(guān)鍵節(jié)點(diǎn)，建立(1245，a)和(2，ac)的父子關(guān)系，使得(1245，a)和(2，ac)成為父子節(jié)點(diǎn)對(duì)；同時(shí)刪除所有與關(guān)聯(lián)的(25，a)連接關(guān)系；(235，{})是(12345，{})和(23，c)的唯一路徑上的關(guān)鍵節(jié)點(diǎn)，建立(12345，{})和(23，c)的父子關(guān)系，使得(12345，{})和(23，c)成為父子節(jié)點(diǎn)對(duì)；同時(shí)刪除所有與關(guān)聯(lián)的(235，{})連接關(guān)系。

步驟5算法結(jié)束返回概念格L2（圖4）。

圖4 屬性集合為{a，b，c，d}時(shí)的概念格L2

對(duì)于刪除對(duì)象的概念格維護(hù)，實(shí)際上是刪除屬性的概念格維護(hù)的對(duì)偶操作，根據(jù)算法3和算法4可以得到，本文不再舉例說(shuō)明。至于增加對(duì)象或者屬性的概念格維護(hù)，實(shí)際上是概念格漸進(jìn)式生成[7]的研究?jī)?nèi)容，這里不再贅述。

增加多對(duì)象或者多屬性的概念格維護(hù)，實(shí)際上是概念格縱向合并和橫向合并的研究?jī)?nèi)容[8]，這里不再贅述。

當(dāng)概念格中刪除一個(gè)對(duì)象或者屬性，概念格中有多少概念需要更新呢？實(shí)際上，這個(gè)問(wèn)題和增加一個(gè)對(duì)象或者屬性概念格中增加多少新生概念是等價(jià)的。刪除一個(gè)對(duì)象或者屬性概念格中有多少概念需要更新，在基于對(duì)象或者屬性漸進(jìn)式生成中就有多少個(gè)新生概念生成。這是概念格漸進(jìn)式生成[7]的研究?jī)?nèi)容，故這里不再贅述。

基于多對(duì)象或多屬性刪除的概念格維護(hù)可以轉(zhuǎn)化為單個(gè)對(duì)象或單個(gè)屬性刪除的概念格維護(hù)。

4 結(jié)束語(yǔ)

本文對(duì)概念格維護(hù)進(jìn)行深入細(xì)致的研究。在研究中，將把形式背景的變化分為兩類(lèi)：（1）對(duì)象-屬性關(guān)系的增加和刪除；（2）對(duì)象或?qū)傩缘脑黾雍蛣h除。在對(duì)象-屬性關(guān)系的增加引起的概念格維護(hù)中，提出了父子概念對(duì)的概念，用來(lái)確定概念格維護(hù)的位置以及概念之間關(guān)系的調(diào)整。在對(duì)象-屬性關(guān)系的刪除引起的概念格維護(hù)中，提出確定概念格維護(hù)位置后用父子概念對(duì)代替被維護(hù)的概念，對(duì)父子概念對(duì)中的冗余概念進(jìn)行判別并對(duì)父子概念對(duì)進(jìn)行更新。在對(duì)象或?qū)傩缘膭h除引起的概念格維護(hù)中，提出了利用唯一路徑上的關(guān)鍵概念來(lái)調(diào)整因?yàn)楦拍畹膭h除引起的概念之間關(guān)系的變動(dòng)。并將對(duì)象或?qū)傩缘膭h除引起的概念格維護(hù)分成兩種類(lèi)型加以研究，即基于單個(gè)對(duì)象或單個(gè)屬性的刪除概念格維護(hù)，以及基于多對(duì)象或多屬性的刪除概念格維護(hù)，并指出兩者的聯(lián)系。

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

[2]屠莉，陳峻，李云.一種基于屬性的概念格生成及維護(hù)算法[J].計(jì)算機(jī)應(yīng)用，2004，24（10）：116-118.

[3]李云.概念格分布處理及其框架下的知識(shí)發(fā)現(xiàn)研究[D].上海：上海大學(xué)，2005.

[4]吳剛，簡(jiǎn)宋全，胡學(xué)鋼，等.擴(kuò)展概念格的維護(hù)[J].計(jì)算機(jī)工程與應(yīng)用，2002，38（4）：76-78.

[5]趙文兵，簡(jiǎn)宋全，蔣美華，等.約簡(jiǎn)概念格的縱向維護(hù)算法[J].計(jì)算機(jī)工程與應(yīng)用，2002，38（7）：209-2l1.

[6]張文修，魏玲，祁建軍.概念格的屬性約簡(jiǎn)理論與方法[J].中國(guó)科學(xué)E輯：信息科學(xué)，2005，35（6）：628-639.

[7]謝志鵬，劉宗田.概念格的快速漸進(jìn)式構(gòu)造算法[J].計(jì)算機(jī)學(xué)報(bào)，2002，25（5）：490-496.

[8]智慧來(lái)，智東杰，劉宗田.概念格合并原理與算法[J].電子學(xué)報(bào)，2010，38（2）：455-459.

ZHI Huilai,ZHI Dongjie

School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454150,China

The changes of formal context are divided into two types.One is object-attribute relation’s add and delete, another is object or attribute’s add and delete.This paper studies concept lattice maintenance that is caused by these two types of changes of formal context respectively.In the maintenance caused by object-attribute relations’add,it puts forward the term“father-son concept pair”to identify maintenance place,and to deal with relation adjustment.In the maintenance caused by object-attribute relations’delete,after identifying maintenance place,it generates father-son concept pair to take place the concepts which need to be altered,and deletes redundant concepts in father-son concept pair.In the maintenance caused by objects or attributes’delete,it puts forward the term“critical concept”,and uses it to adjust relationship between concepts.

concept lattice;concept lattice maintenance;father-son concept pair;critical concept

A

TP18

10.3778/j.issn.1002-8331.1204-0776

ZHI Huilai,ZHI Dongjie.Theory and algorithm of concept lattice maintenance.Computer Engineering and Applications,2014,50（6）：96-101.

國(guó)家自然科學(xué)基金（No.60975033）；河南理工大學(xué)博士基金（No.B2011-102）。

智慧來(lái)（1981—），男，講師，研究領(lǐng)域：粗糙集合、本體、形式概念分析等；智東杰（1952—），男，高級(jí)實(shí)驗(yàn)師，研究領(lǐng)域：形式概念分析、符號(hào)計(jì)算等。

2012-05-10

2012-06-25

1002-8331（2014）06-0096-06

CNKI網(wǎng)絡(luò)優(yōu)先出版：2012-08-01，http://www.cnki.net/kcms/detail/11.2127.TP.20120801.1652.016.html