王靜宇 鄭雪巖
(內蒙古科技大學信息工程學院 內蒙古 包頭 014010)
形式概念分析是Wille[1]于1982年提出的,它的核心數據結構是概念格,是根據描述現實世界的形式背景建立起來的,描述了對象和屬性之間的關系。在現實生活中,對象和屬性不斷發(fā)生變化,概念格也隨之改變,因此研究概念格的維護是十分必要的。Godin等[2]提出了一種漸進式的概念格構造算法;概念格的應用涉及到了多個領域,例如信息檢索、知識管理、軟件工程[3-4]等;吳剛等[5]提出了擴展概念格的維護;謝霖銓等[6]提出了粗糙概念格構造的算法;智慧來等[7]提出了概念格的第一類維護和第二類維護;劉保相等[8]提出了一種區(qū)間概念格結構;智慧來等[9]研究了以關系為更新粒度的概念格增量維護;張春英等[10]提出了基于屬性冪集的漸進式生成算法;文獻[11-12]提出了增加一個對象或屬性時的概念格維護;崔芳婷等[13]提出了基于約束的模糊概念格構造算法;王春月等[14]提出了基于二元關系消減的概念格維護算法。
刪除對象后概念格會發(fā)生改變,為了防止重新構造概念格耗費大量時間,本文借鑒了張磊[15]的構造概念格的方法,對刪除對象后概念格的結構變化以及概念之間的聯系進行改進,提出一種概念格的對象漸減更新算法。
形式背景是一個矩陣圖,表示對象和屬性之間的二元關系,矩陣的行表示屬性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)的樞紐概念。
記刪除對象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)來表示。
定理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})時不需要判斷它的類型。
概念格是由概念和概念之間的邊組成的,因此刪除某一個對象后,不僅要考慮新概念格中概念的組成,還要考慮概念之間的邊的變化。邊都是存在于父概念和子概念之間的,所以我們來根據父概念和子概念之間的關系去判斷邊的變化。
定理6不變概念的子概念還是不變概念。
由定理6可知,以下兩種情況不存在:
(1) 父概念為不變概念,子概念為刪除概念。
(2) 父概念為不變概念,子概念為更新概念。
定理7如果父概念和子概念中沒有一個是刪除概念,則該父概念和子概念之間的邊不需要改變,保留到新的概念格中。
由定理6和定理7可知,以下三種情況不需要調整邊:
(1) 父概念是更新概念,子概念是不變概念。
(2) 父概念是更新概念,子概念是更新概念。
(3) 父概念是不變概念,子概念是不變概念。
定理8刪除對象x后,若Extension(N)-{x}=?,則在刪除概念的父概念與其子概念之間增加一條邊;若Extension(N)-{x}!=?,且概念是其父概念與子概念之間的樞紐概念,則在刪除概念的父概念與其子概念之間增加一條邊。
定理9一個刪除概念的子概念中只有一個不變概念,其他都是刪除概念。
由定理9可知,父子概念分別為刪除概念和更新概念的情況不存在。
綜上所述,刪除對象后邊的關系如表2所示。
表2 刪除對象后各父概念與子概念之間邊的變化
根據前文中對刪除對象后概念和邊的分析可知:刪除對象后,父概念與子概念的類型有一定的聯系,父概念與子概念之間的邊也存在一定的變化規(guī)則。據此提出一種漸進式的概念格構造算法,即對象漸減更新算法。
根據前文所述可知,不變概念的子概念依然是不變概念,刪除概念的非不變子概念是更新概念,不需要判斷這兩種概念的類型。算法主要解決的是刪除一個對象后,如何得到一個新的概念格,該算法采用廣度優(yōu)先遍歷的順序,以頭概念為頂點,依次對概念進行處理,因此訪問某個概念的時候,它的父概念已經被訪問過,進而該算法可根據父概念的類型來判斷子概念的類型。
該算法不需要判斷不變概念的子概念,所以只需要判斷更新概念和刪除概念的子概念即可。在該算法中設未被訪問過的概念的visited的值為0,被訪問過的概念的visited的值為1。概念的visited的值為0時算法向下執(zhí)行,所有概念的visited的值為1時算法結束。
算法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
以圖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后的概念格
刪除某一對象后,該漸進式維護算法不需要重新構造概念格,只需對更新概念、刪除概念及其相關的邊進行處理,因此在很大程度上減少了概念格的維護時間。該算法還包含以下幾個優(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算法的時間性能
本文根據刪除對象后,概念格中父子之間的邊以及概念的變化,提出一種概念格漸進式更新算法,該算法減少了概念格構造的時間。
該算法對刪除概念的子概念的訪問是有序的,而刪除概念的非不變子概念肯定是刪除概念,如果先找出不變子概念,就不需要判斷其余子概念的類型。對于同一個概念的子概念,如果刪除概念在不變概念前的情況較多,則算法的執(zhí)行速度可能會更快,下一步將研究這一方面的內容。