概念格維護原理與算法

智慧來，智東杰

河南理工大學計算機科學與技術學院，河南焦作 454150

概念格維護原理與算法

智慧來，智東杰

河南理工大學計算機科學與技術學院，河南焦作 454150

將把形式背景的變化分為對象-屬性關系的增加和刪除、對象或屬性的增加和刪除兩類，分別研究了這兩類變化引起的概念格的維護問題。在對象-屬性關系的增加引起的概念格維護中，提出了父子概念對的概念，用來確定概念格維護的位置以及概念之間關系的調整。在對象-屬性關系的刪除引起的概念格維護中，提出確定概念格維護位置后用父子概念對代替被維護的概念，對父子概念對中的冗余概念進行判別并對父子概念對進行更新。在對象或屬性的刪除引起的概念格維護中，提出了利用唯一路徑上的關鍵概念來調整因為概念的刪除引起的概念之間關系的變動。

概念格；概念格維護；父子概念對；關鍵概念

1 引言

R.Wille[1]提出的形式概念分析是以序理論和完備格理論為基礎，依據數據庫中提供的基本信息建立起的一種刻畫對象與屬性之間關系的數學結構。概念格是形式概念分析的核心數據結構，可以根據形式背景建立其對象的概念格。在動態開放的環境下，概念格的維護是經常的、普遍的。

形式背景是描述現實世界的二維表格，形式背景的變化有多種情形，但都可以歸結為兩類：（1）對象-屬性關系的增加和刪除；（2）對象或屬性的增加和刪除。在本文中，稱對象-屬性關系的增加和刪除引起的概念格維護為第一類維護，稱對象或屬性的增加和刪除引起的概念格維護為第二類維護。

概念格維護是一個重要的但少有研究的問題。現有的外文文獻都是基于概念格的數據庫維護，并不是關于概念格自身的維護。國內有李云[2-3]、簡宋全[4-5]等人提到概念格的維護。文獻[2-3]中提到是一種增量維護，即增加一個屬性或對象時的維護。文獻[4-5]中提出了對擴展概念格和約減概念格的維護算法，文獻[4]的算法屬于橫向維護，即當刪除一個對象時的維護算法；文獻[5]的算法屬于縱向維護，即當屬性刪減時的維護算法。

總之，現有研究提及的概念格維護粒度是對象或屬性，即概念格的第二類維護，并且很不深入，就像文獻[3]中的論述“主要簡述概念格的橫向維護和縱向維護的大致方案”，沒有對維護位置的搜索、冗余概念的判別以及關系的調整作出細致的研究。

2 概念格的第一類維護

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

在概念格的第一類維護中，增加或者刪除對象-屬性對前后其形式背景K=(U，A，I)是“準正則的”，即：對于對象-屬性對(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)≠{}）。

當?u∈U，f(u)={}，?a∈A，增加對象-屬性對(u，a)時，采用概念格的第二類維護，即基于對象的概念格生成算法中插入對象的方法實現概念格的維護。

且?a∈A，g(a)={}，?u∈U，增加對象-屬性對(u，a)時，采用概念格的第二類維護，即基于屬性的概念格生成算法中插入屬性的方法實現概念格的維護。

刪除對象-屬性對(u，a)時，若f(u)=a，即刪除對象-屬性對(u，a)后f(u)={}，則采用概念格的第二類維護，即刪除對象的概念格維護。

刪除對象-屬性對(u，a)時，若g(a)=u，即刪除對象-屬性對(u，a)后g(a)={}，則采用概念格的第二類維護，即刪除屬性的概念格維護。

2.1 基本原理與算法

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

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

定義2父子概念對[(A1，B1)，(A2，B2)]，任意的對象a和屬性b，若A1、A2包含對象a，B1、B2包含屬性b，那么父子概念對[(A1，B1-b)，(A1-a，B1)]、[(A2，B2-b)，(A2-a,B2)]稱為父子概念團，記做{[(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)]稱為是[(A2，B2-b)，(A2-a，B2)]的廣義父概念對，[(A2，B2-b)，(A2-a，B2)]稱為是[(A1，B1-b)，(A1-a，B1)]的廣義子概念對。

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

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

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

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

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

證明因為(A2，B2)是(A1，B1)的子概念，所以A2具有屬性B1；又因為，B2包含b，那么A2既具有屬性B1又具有屬性b。因為A1包含a，同時A1具有屬性B1，那么a具有屬性B1∪b。所以A2∪a具有屬性B1∪b，具有屬性B1∪b的對象只有A2∪a。根據概念之間的包含關系易證更新父子概念對的規律成立。故定理成立。

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

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

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

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

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

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

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

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

性質1在父子概念團{[(A1F,B1F)，(A1,B1)]，[(A2F,B2F)，(A2，B2)]}中，(A1F，B1F)與(A2F，B2F)構成直接父子關系，(A1，B1)與(A2，B2)構成直接父子關系。

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

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

（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)，則父子概念團中四個概念的連接方式不變。

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

（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)的直接父子關系，建立(A1∪a，B1F∪b)與(A2∪a，B2F∪b)的直接父子關系。

（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)的直接父子關系。

（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)的直接父子關系。

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

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

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

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

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

根據上面的基本原理和性質，可以得到下面的算法。

算法1增加關系(a，b)時概念格的維護算法

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

對每一對找到的父子概念對執行步驟2～4：

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

步驟3父子概念對中概念的更新：根據定理1更新父子概念對中的概念。

步驟4修改父子概念對與鄰接的父子概念對的關系：根據性質2調整父子概念對與鄰接的父子概念對的關系。

步驟5算法結束，返回。

算法2刪除關系(a，b)時概念格的維護算法

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

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

步驟3更新父子概念對：判斷并執行其中的一個動作：

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

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

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

步驟4建立更新后的父子概念對之間的關系：

如果步驟3執行動作1，則：若父子概念對連接到父子概念對，則父概念之間建立連接，子概念之間建立連接。

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

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

步驟5算法結束，返回。

2.2 實例研究與分析

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

表1 形式背景K1

形式背景K1對應的概念格L1如圖1所示。

圖1 形式背景K1對應的概念格L1

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

概念格L1刪除關系（3，7）時概念格的維護過程：

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

步驟2生成父子概念對：[（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）]。

然后由更新后的概念對代替維護位置的概念。

步驟4建立父子關系：（根據算法1，略）。

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

概念格L2增加關系（3，7）時概念格的維護過程：

步驟1確定概念格的維護位置：[（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修改父子關系：（根據算法2，略）。

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

形式背景K2對應的概念格L2如圖2所示。

圖2 形式背景K2對應的概念格L2

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

在概念格中增加一個對象-屬性關系時需要維護的父子概念對有多少呢？在概念格中刪除一個對象-屬性關系時需要更新的概念有多少呢？這兩個問題可以用實驗進行回答。實際上上述兩個問題是等價的，有多少需要維護的父子概念對就有多少需要更新的概念（這是因為增加和刪除一個對象-屬性關系是互逆的操作）。

下面有一組數據來說明：實驗中的形式背景對象個數為100，屬性個數為20，對象屬性間存在關系的概率為0.2、0.25、0.33。增加或者刪除一個對象-屬性關系，對于每一個概率，記錄下5次隨機的結果，如表2。

表2 一次概念格第一類維護的維護數量統計

從表2可以得到結論：概念格的第一類維護中，需要維護的父子概念對（或者需要更新的概念）數量少，占全體概念總數的比例很小。

3 概念格的第二類維護

概念格的第二類維護的內容是對象或者屬性的增加和刪除，包括基于單個對象或單個屬性的概念格維護和基于多對象或多屬性的概念格維護。

在基于單個對象或單個屬性的概念格維護中，其中對象或者屬性的增加其實是概念格的漸進式生成[7]的一個步驟，因此需要研究的是對象或者屬性的刪除。

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

3.1 基于單個對象或單個屬性的概念格維護

在概念格的維護過程中，刪除對象或者屬性概念中的概念發生相應的改變，改變分為兩種類型：一種是原有概念的更新，不需要刪除概念；另一種是原有概念更新后成為了冗余的概念，需要將更新后的概念刪除。前一種情形只需要改變概念的內涵或者外延，后一種情形需要刪除概念并調整概念之間的連接關系。

定義4對于概念(A1，B1)和概念(A2，B2)，(A1，B1)＞(A2，B2)，如果只存在唯一的一個概念(Ax，Bx)，使得(A1，B1)＞(Ax，Bx)＞(A2，B2)，那么(Ax，Bx)稱為概念(A1，B1)和概念(A2，B2)的唯一路徑上的關鍵概念。

性質3(Ax，Bx)是概念(A1，B1)和概念(A2，B2)的唯一路徑上的關鍵概念，那么刪除(Ax，Bx)后，則(A1，B1)和(A2，B2)成為父子節點對。

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

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

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

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

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

步驟4關系的刪除：若刪除的概念不是任何兩個概念的唯一路徑上的關鍵概念，則刪除所有與冗余概念關聯的指針；若刪除的概念是兩個概念的唯一路徑上的關鍵概念，那么這兩個概念建立連接，成為父子節點對。

步驟5算法結束返回。

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

建立結果鏈表L。

建立空隊列Q，把最大概念放入隊列Q。

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

返回結果鏈表L。

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

3.2 基于多對象或多屬性的概念格維護

基于多對象或多屬性的概念格維護，顧名思義，就是一次增加或者刪除多個對象或者多個屬性的概念格維護。至于增加多對象或者多屬性的概念格維護，實際上是概念格縱向合并和橫向合并[8]的研究內容，這里不再贅述。本文只研究多對象或多屬性的刪除的概念格維護。

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

算法5概念格中刪除的對象集合M的維護

對概念格中的每一個概念(A，B)，執行下列步驟：

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

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

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

步驟4關系的刪除：若刪除的概念不是任何兩個概念的唯一路徑上的關鍵概念，則刪除所有與冗余概念關聯的指針；若刪除的概念是兩個概念的唯一路徑上的關鍵概念，那么這兩個概念建立連接，成為父子節點對。

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

3.3 實例研究與分析

例2刪除形式背景K1（表3）中的屬性e的概念格維護。形式背景K1對應的概念格L1如圖3。

刪除屬性e的概念格的維護過程：對于概念格L1

表3 形式背景K1

圖3 形式背景K1對應的概念格L1

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

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

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

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

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

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

對于刪除對象的概念格維護，實際上是刪除屬性的概念格維護的對偶操作，根據算法3和算法4可以得到，本文不再舉例說明。至于增加對象或者屬性的概念格維護，實際上是概念格漸進式生成[7]的研究內容，這里不再贅述。

增加多對象或者多屬性的概念格維護，實際上是概念格縱向合并和橫向合并的研究內容[8]，這里不再贅述。

當概念格中刪除一個對象或者屬性，概念格中有多少概念需要更新呢？實際上，這個問題和增加一個對象或者屬性概念格中增加多少新生概念是等價的。刪除一個對象或者屬性概念格中有多少概念需要更新，在基于對象或者屬性漸進式生成中就有多少個新生概念生成。這是概念格漸進式生成[7]的研究內容，故這里不再贅述。

基于多對象或多屬性刪除的概念格維護可以轉化為單個對象或單個屬性刪除的概念格維護。

4 結束語

本文對概念格維護進行深入細致的研究。在研究中，將把形式背景的變化分為兩類：（1）對象-屬性關系的增加和刪除；（2）對象或屬性的增加和刪除。在對象-屬性關系的增加引起的概念格維護中，提出了父子概念對的概念，用來確定概念格維護的位置以及概念之間關系的調整。在對象-屬性關系的刪除引起的概念格維護中，提出確定概念格維護位置后用父子概念對代替被維護的概念，對父子概念對中的冗余概念進行判別并對父子概念對進行更新。在對象或屬性的刪除引起的概念格維護中，提出了利用唯一路徑上的關鍵概念來調整因為概念的刪除引起的概念之間關系的變動。并將對象或屬性的刪除引起的概念格維護分成兩種類型加以研究，即基于單個對象或單個屬性的刪除概念格維護，以及基于多對象或多屬性的刪除概念格維護，并指出兩者的聯系。

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

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

[3]李云.概念格分布處理及其框架下的知識發現研究[D].上海：上海大學，2005.

[4]吳剛，簡宋全，胡學鋼，等.擴展概念格的維護[J].計算機工程與應用，2002，38（4）：76-78.

[5]趙文兵，簡宋全，蔣美華，等.約簡概念格的縱向維護算法[J].計算機工程與應用，2002，38（7）：209-2l1.

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

[7]謝志鵬，劉宗田.概念格的快速漸進式構造算法[J].計算機學報，2002，25（5）：490-496.

[8]智慧來，智東杰，劉宗田.概念格合并原理與算法[J].電子學報，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.

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

智慧來（1981—），男，講師，研究領域：粗糙集合、本體、形式概念分析等；智東杰（1952—），男，高級實驗師，研究領域：形式概念分析、符號計算等。

2012-05-10

2012-06-25

1002-8331（2014）06-0096-06

CNKI網絡優先出版：2012-08-01，http://www.cnki.net/kcms/detail/11.2127.TP.20120801.1652.016.html