概念格的對象漸減更新算法

王靜宇 鄭雪巖

(內蒙古科技大學信息工程學院 內蒙古 包頭 014010)

0 引 言

形式概念分析是Wille[1]于1982年提出的，它的核心數據結構是概念格，是根據描述現實世界的形式背景建立起來的，描述了對象和屬性之間的關系。在現實生活中，對象和屬性不斷發(fā)生變化，概念格也隨之改變，因此研究概念格的維護是十分必要的。Godin等[2]提出了一種漸進式的概念格構造算法；概念格的應用涉及到了多個領域，例如信息檢索、知識管理、軟件工程[3-4]等；吳剛等[5]提出了擴展概念格的維護；謝霖銓等[6]提出了粗糙概念格構造的算法；智慧來等[7]提出了概念格的第一類維護和第二類維護；劉保相等[8]提出了一種區(qū)間概念格結構；智慧來等[9]研究了以關系為更新粒度的概念格增量維護；張春英等[10]提出了基于屬性冪集的漸進式生成算法；文獻[11-12]提出了增加一個對象或屬性時的概念格維護；崔芳婷等[13]提出了基于約束的模糊概念格構造算法；王春月等[14]提出了基于二元關系消減的概念格維護算法。

刪除對象后概念格會發(fā)生改變，為了防止重新構造概念格耗費大量時間，本文借鑒了張磊[15]的構造概念格的方法，對刪除對象后概念格的結構變化以及概念之間的聯系進行改進，提出一種概念格的對象漸減更新算法。

1 相關概念

形式背景是一個矩陣圖，表示對象和屬性之間的二元關系，矩陣的行表示屬性m、列表示對象g，形式背景記為O=(G,M,R)，其中：G是對象的集合；M是屬性的集合；R表示G和M之間的關系。若g行與m列的交叉處為1，即gRm=1，則表示對象g具有屬性m，相應地，gRm=0表示對象g不具有屬性m。形式背景如表1所示。

表1 形式背景示例

定義1若X是G的子集,Y是M的子集,令：

(1)h(X)={m∈M|g∈X,gRm}。

(2)h(Y)={g∈G|m∈Y,gRm}。

如果X、Y滿足h(X)=Y、h(Y)=X，則稱(X,Y)是形式背景的概念Node，簡稱N，X(x1,x2,…,xn)是概念(X,Y)的外延，記為Extension(N)，簡稱E(N)，Y(y1,y2,…,yn)是概念(X,Y)的內涵，記為Intension(N)，簡稱I(N)，概念的集合記為NS(O)。

定義2設(X1,Y1)和(X2,Y2)是形式背景的兩個概念，如果X1?X2，且不存在X3,使得X1?X3?X2，則稱(X1,Y1)是(X2,Y2)的子概念，(X2,Y2)是(X1,Y1)的父概念，記為(X1,Y1)≤(X2,Y2)。(X1,Y1)和(X2,Y2)是一對父子概念對，所有父子概念對連在一起構成了概念格的Hasse圖，在Hasse圖中，把連接兩概念之間的線稱為邊。表1的形式背景所對應的概念格的Hasse圖如圖1所示。

圖1 表1的形式背景對應的概念格的Hasse圖

定義3對于概念(X1,Y1)和概念(X2,Y2)，X1?X2，如果(Xx,Yx)是(X1,Y1)到(X2,Y2)之間的路徑上唯一的一個概念，則稱(Xx,Yx)是(X1,Y1)和(X2,Y2)的樞紐概念。

2 概念格

2.1 概念的分類

記刪除對象x后的概念格為L(O|-{x})，原概念格為L(O)，L(O)中的概念由如下三種類型組成：

(1) 不變概念：指外延中不含刪除對象x的概念，即x?Extension(N)的概念。這一類概念的集合用FS-{x}(O)來表示。

(3) 刪除概念：指外延包含x，?Extension(N1)=E(N)-{x}的概念。這一類概念的集合用DS-{x}(O)來表示。

2.2 概念的分析

定理1刪除對象x后，原概念格中的不變概念不發(fā)生任何變化，直接保留到新的概念格中，即FS-{x}(O)?NS(O|-{x})。

定理2刪除對象x后，更新概念的外延減去x即可成為新概念格中的概念，即VS-{x}(O)?NS(O|-{x})。

定理3刪除對象x后，新概念格中的概念是由FS-{x}(O)和VS-{x}(O)組成的。

由上文可知，新概念格由不變概念和更新概念組成，刪除對象后,不變概念不發(fā)生任何變化，直接保留到L(O|-{x})中，更新概念的外延減去x,即可成為L(O|-{x})中的概念，刪除概念需刪掉。

定理4包含所有對象的概念是頭概念，頭概念必定是更新概念，因此構造L(O|-{x})時不需要判斷它的類型，直接更新外延即可。

定理5包含所有屬性的概念是末概念。末概念的外延不包含任何對象，所以末概念必定是不變概念，構造L(O|-{x})時不需要判斷它的類型。

2.3 邊的分析

概念格是由概念和概念之間的邊組成的，因此刪除某一個對象后，不僅要考慮新概念格中概念的組成，還要考慮概念之間的邊的變化。邊都是存在于父概念和子概念之間的，所以我們來根據父概念和子概念之間的關系去判斷邊的變化。

定理6不變概念的子概念還是不變概念。

由定理6可知，以下兩種情況不存在：

(1) 父概念為不變概念，子概念為刪除概念。

(2) 父概念為不變概念，子概念為更新概念。

定理7如果父概念和子概念中沒有一個是刪除概念，則該父概念和子概念之間的邊不需要改變，保留到新的概念格中。

由定理6和定理7可知，以下三種情況不需要調整邊：

(1) 父概念是更新概念，子概念是不變概念。

(2) 父概念是更新概念，子概念是更新概念。

(3) 父概念是不變概念，子概念是不變概念。

定理8刪除對象x后，若Extension(N)-{x}=?，則在刪除概念的父概念與其子概念之間增加一條邊；若Extension(N)-{x}!=?，且概念是其父概念與子概念之間的樞紐概念，則在刪除概念的父概念與其子概念之間增加一條邊。

定理9一個刪除概念的子概念中只有一個不變概念，其他都是刪除概念。

由定理9可知，父子概念分別為刪除概念和更新概念的情況不存在。

綜上所述，刪除對象后邊的關系如表2所示。

表2 刪除對象后各父概念與子概念之間邊的變化

根據前文中對刪除對象后概念和邊的分析可知：刪除對象后，父概念與子概念的類型有一定的聯系，父概念與子概念之間的邊也存在一定的變化規(guī)則。據此提出一種漸進式的概念格構造算法，即對象漸減更新算法。

3 算法描述

3.1 算法思想

根據前文所述可知，不變概念的子概念依然是不變概念，刪除概念的非不變子概念是更新概念，不需要判斷這兩種概念的類型。算法主要解決的是刪除一個對象后，如何得到一個新的概念格，該算法采用廣度優(yōu)先遍歷的順序，以頭概念為頂點，依次對概念進行處理，因此訪問某個概念的時候，它的父概念已經被訪問過，進而該算法可根據父概念的類型來判斷子概念的類型。

該算法不需要判斷不變概念的子概念，所以只需要判斷更新概念和刪除概念的子概念即可。在該算法中設未被訪問過的概念的visited的值為0，被訪問過的概念的visited的值為1。概念的visited的值為0時算法向下執(zhí)行，所有概念的visited的值為1時算法結束。

3.2 對象漸減更新算法

算法1的相關術語：Child(FS)用來表示不變概念的子概念；Child(VS)用來表示更新概念的子概念；Child(DS)用來表示刪除概念的子概念。

在算法1中，直接對頭概念進行更新，然后算法向下執(zhí)行。如果是更新概念的子概念，則判斷其類型并進行相應的處理(4-17行)；如果是刪除概念的非不變子概念，則該概念必然是刪除概念，此時調用算法2對概念進行刪除操作并修改相關的邊的關系(18-22行)，直到所有概念的visited的值為1。

算法1對象漸減更新算法

輸入：原始概念格L(O),刪除對象x。

輸出：刪除對象x后的格L(O|-{x})。

1.Extension(N):=Extension(N)-{x};

//更新頭概念

2.WhileN.visited:=0

///當概念未被訪問過的時候

3.For (N?Child(FS))

4.For (N∈Child(VS))

5.If (x?Extension(N))

6.doNotChange;

//不做改變

7.N.visited:=1;

8.Else If (?Extension(N):=Extension(N)-{x})

9.Delete(L(O),N);

//調用算法2，刪除概念并調整相應的邊

10.N.visited:=1;

11.Else If

12.Extension(N):=Extension(N)-{x};

//更新概念的外延

13.N.visited:=1;

14.End If;

15.End If;

16.End If;

17.End For;

18.For (N∈Child(DS))

19.If(N∈Child(DS) and 非FN)

20.Delete(L(O),N);

21.N.visited:=1;

22.End For;

23.End For;

24.End While;

25.ReturnL(O|-{x});

算法2的相關術語：NChild用來表示概念的子概念；NParent用來表示概念的父概念。

該算法用于將概念刪除并調整其相關邊的關系，在該算法中，符合下面兩種情況的需要添加邊：

(1) 對于外延不只由x組成的概念，如果它是任意兩個概念之間的樞紐概念，則在這兩個概念之間添加邊。

(2) 對于外延只由x組成的概念，直接在其父概念與子概念之間添加邊。

算法2刪除算法

輸入：概念格L(O),刪除概念N。

輸出：刪除概念N后的格L(O|-{x})。

1.If (Extension(N)-{x} !=? andN是NParent→NChild的樞紐概念)

2.Then 刪除與N相關的邊，添加邊NParent→NChild，刪除N;

3.Else刪除與N相關的邊，刪除N;

4.If (Extension(N)-{x}=?)

5.Then 刪除與N相關的邊，添加邊NParent→NChild，刪除N;

6.Else 刪除與N相關的邊，刪除N;

7.End

4 算法示例及實驗驗證

4.1 算法示例

以圖1為例，刪除對象4，算法的維護過程如下：

(1) 頭概念是更新概念，直接更新。

(2) 概念2*的外延去除對象4后與概念4*的外延相同，因此2*是刪除概念，刪除2*，刪除邊(1*,2*)，刪除邊(2*，4*)，刪除邊(2*，5*)，且2*是1*與4*之間的樞紐概念，故添加邊(1*，4*)。

(3) 3*的外延減去4后與其任何一個子概念延都不相等，故3*為更新概念，更新3*的外延。

(4) 因為4*和5*都是2*的子概念，且4*是不變概念，故5*為刪除概念，刪除5*，刪除邊(3*，5*)，刪除邊(5*，7*)，刪除邊(5*，8*)，因為5*是3*和7*之間的樞紐概念，故增加邊(3*，7*)。

(5) 6*的外延減去x后與其任何一個子概念延都不相等，故6*為更新概念，更新6*的外延。

(6) 7*的外延不包含對象4，故7*為不變概念，不作任何改變。

(7) 8*的外延只包含對象4，符合E(N)-{x}=?，故刪除概念8*，添加邊(6*，9*)，刪除邊(6*，8*)，刪除邊(8*，9*)。

刪除對象4后的概念格對應的Hasse圖如圖2所示。

圖2 刪除對象4后的概念格

4.2 實驗驗證

刪除某一對象后，該漸進式維護算法不需要重新構造概念格，只需對更新概念、刪除概念及其相關的邊進行處理，因此在很大程度上減少了概念格的維護時間。該算法還包含以下幾個優(yōu)點：

(1) 不需要判斷頭概念的類型，可直接更新頭概念。

(2) 該算法可根據父概念的類型來判斷子概念的類型，所以可以減少概念類型的判斷次數。

(3) 若概念的外延中只包含刪除對象x,則不必判斷概念是否是兩個概念之間的樞紐概念，可直接在概念的父概念和其子概念之間添加邊。

實驗一驗證需調整的概念占總概念的比例。

隨機生成形式背景，屬性個數固定為20，對象數目從10到100，每次增加10個對象來進行實驗。實驗結果如圖3所示，縱軸表示需要調整的概念占全體概念的比例；橫軸表示對象的數量；兩條折線的對象屬性間存在關系的概率分別為0.20和0.25。當刪除一個對象時，需要調整的概念所占比例較小，而且隨著對象數的增加，這個比例會更小，所以相對于重新構造概念格，本文這種漸進式的方式的效率會比較高。

圖3 需要調整的概念占總概念的比例

實驗二主要從時間方面驗證算法的有效性。

為了驗證本文優(yōu)化算法的結果，與AddIntent[16]算法和In-Close[17]算法進行對比。AddIntent算法是最快的基于對象的概念格構造算法之一，In-Close算法是近年出現的最快的概念格構造算法之一。我們隨機產生了三組數據，三個算法的性能都是這三組數據的平均值，屬性的數目都為20，對象數目從100到900，每次增加50個對象來測試算法的執(zhí)行時間。相對于In-Close算法和本文算法，AddIntent算法消耗的時間比較多，放在同一個圖中對比不明顯，因此分開來對比。圖4是本文算法與AddIntent算法的對比，圖5是本文算法與In-Close算法的對比，兩個圖的橫軸都表示對象，縱軸都表示算法執(zhí)行所用的時間。實驗結果表明，隨著對象數目的增加，三個算法所花費的時間都在增長，但本文算法所用時間明顯低于AddIntent算法和In-Close算法。因此本文的算法明顯減少了構造概念格所花費的時間。

圖4 對象數目增大時本文算法與AddIntent算法的時間性能

圖5 對象數目增大時本文算法與In-Close算法的時間性能

5 結 語

本文根據刪除對象后，概念格中父子之間的邊以及概念的變化，提出一種概念格漸進式更新算法，該算法減少了概念格構造的時間。

該算法對刪除概念的子概念的訪問是有序的，而刪除概念的非不變子概念肯定是刪除概念，如果先找出不變子概念，就不需要判斷其余子概念的類型。對于同一個概念的子概念，如果刪除概念在不變概念前的情況較多，則算法的執(zhí)行速度可能會更快，下一步將研究這一方面的內容。