概念格的對(duì)象漸減更新算法

王靜宇 鄭雪巖

(內(nèi)蒙古科技大學(xué)信息工程學(xué)院 內(nèi)蒙古 包頭 014010)

0 引 言

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

刪除對(duì)象后概念格會(huì)發(fā)生改變，為了防止重新構(gòu)造概念格耗費(fèi)大量時(shí)間，本文借鑒了張磊[15]的構(gòu)造概念格的方法，對(duì)刪除對(duì)象后概念格的結(jié)構(gòu)變化以及概念之間的聯(lián)系進(jìn)行改進(jìn)，提出一種概念格的對(duì)象漸減更新算法。

1 相關(guān)概念

形式背景是一個(gè)矩陣圖，表示對(duì)象和屬性之間的二元關(guān)系，矩陣的行表示屬性m、列表示對(duì)象g，形式背景記為O=(G,M,R)，其中：G是對(duì)象的集合；M是屬性的集合；R表示G和M之間的關(guān)系。若g行與m列的交叉處為1，即gRm=1，則表示對(duì)象g具有屬性m，相應(yīng)地，gRm=0表示對(duì)象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，簡(jiǎn)稱N，X(x1,x2,…,xn)是概念(X,Y)的外延，記為Extension(N)，簡(jiǎn)稱E(N)，Y(y1,y2,…,yn)是概念(X,Y)的內(nèi)涵，記為Intension(N)，簡(jiǎn)稱I(N)，概念的集合記為NS(O)。

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

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

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

2 概念格

2.1 概念的分類

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

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

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

2.2 概念的分析

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

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

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

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

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

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

2.3 邊的分析

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

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

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

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

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

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

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

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

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

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

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

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

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

綜上所述，刪除對(duì)象后邊的關(guān)系如表2所示。

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

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

3 算法描述

3.1 算法思想

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

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

3.2 對(duì)象漸減更新算法

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

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

算法1對(duì)象漸減更新算法

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

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

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

//更新頭概念

2.WhileN.visited:=0

///當(dāng)概念未被訪問過的時(shí)候

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);

//調(diào)用算法2，刪除概念并調(diào)整相應(yīng)的邊

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的相關(guān)術(shù)語：NChild用來表示概念的子概念；NParent用來表示概念的父概念。

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

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

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

算法2刪除算法

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

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

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

2.Then 刪除與N相關(guān)的邊，添加邊NParent→NChild，刪除N;

3.Else刪除與N相關(guān)的邊，刪除N;

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

5.Then 刪除與N相關(guān)的邊，添加邊NParent→NChild，刪除N;

6.Else 刪除與N相關(guān)的邊，刪除N;

7.End

4 算法示例及實(shí)驗(yàn)驗(yàn)證

4.1 算法示例

以圖1為例，刪除對(duì)象4，算法的維護(hù)過程如下：

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

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

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

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

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

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

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

刪除對(duì)象4后的概念格對(duì)應(yīng)的Hasse圖如圖2所示。

圖2 刪除對(duì)象4后的概念格

4.2 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

實(shí)驗(yàn)一驗(yàn)證需調(diào)整的概念占總概念的比例。

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

圖3 需要調(diào)整的概念占總概念的比例

實(shí)驗(yàn)二主要從時(shí)間方面驗(yàn)證算法的有效性。

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

圖4 對(duì)象數(shù)目增大時(shí)本文算法與AddIntent算法的時(shí)間性能

圖5 對(duì)象數(shù)目增大時(shí)本文算法與In-Close算法的時(shí)間性能

5 結(jié) 語

本文根據(jù)刪除對(duì)象后，概念格中父子之間的邊以及概念的變化，提出一種概念格漸進(jìn)式更新算法，該算法減少了概念格構(gòu)造的時(shí)間。

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