基于增量更新內(nèi)涵的形式概念生成算法

吳清壽,郭 磊,余文森

(1.武夷學(xué)院 a.數(shù)學(xué)與計(jì)算機(jī)學(xué)院;b.認(rèn)知計(jì)算與智能信息處理福建省高校重點(diǎn)實(shí)驗(yàn)室,福建 武夷山 354300;2.福建農(nóng)林大學(xué) 智慧農(nóng)林福建省高校重點(diǎn)實(shí)驗(yàn)室,福州 350002)

0 引 言

形式概念是形式概念分析(FCA:Formal Concept Analysis)[1]理論的核心數(shù)據(jù)結(jié)構(gòu),已在關(guān)聯(lián)分析[2]、信息檢索[3]、軟件工程[4]和推薦系統(tǒng)[5]等多個領(lǐng)域得到了廣泛應(yīng)用。形式背景中,若多個對象和多個屬性存在關(guān)系,兩者之間的搭配同時達(dá)到最大狀態(tài)就構(gòu)成一個形式概念,而概念格反映了概念之間的層次關(guān)系或泛化-特化關(guān)系[6]。在FCA的主要研究方向中,概念生成和概念格構(gòu)建算法研究是最基礎(chǔ)的研究和最根本的問題。

目前在關(guān)于概念格構(gòu)建方法的研究中,根據(jù)構(gòu)造方式的區(qū)別,主要包含3類方法：批處理構(gòu)造、漸進(jìn)式構(gòu)造和集成構(gòu)造算法。批處理算法需要先生成部分或全部格節(jié)點(diǎn)(即概念),再處理格節(jié)點(diǎn)間的層次關(guān)系[7-8]。漸進(jìn)式算法無需預(yù)先獲得概念,而是逐個將對象或?qū)傩约尤氲较刃懈拍罡裰?根據(jù)規(guī)則對先行概念格進(jìn)行格節(jié)點(diǎn)新增和更新操作,同時修改格節(jié)點(diǎn)間的連接關(guān)系[9-10]。集成算法是對漸進(jìn)式算法的泛化,Valtchev等[11]提出了基于二元關(guān)系片段并置的格構(gòu)造方法。概念格構(gòu)造的主要方式仍然以漸進(jìn)式方法為主,Zhang等[12]在AddIntent等[13]的基礎(chǔ)上提出了FastAddExtent算法,Ma等[14]提出了基于依賴空間模型的概念格構(gòu)造算法。

在應(yīng)用中,只需得到形式背景對應(yīng)的全部概念,而無需關(guān)注概念間的層次關(guān)系?；陂]包算子求所有閉包的算法NextClosure[15]是一個典型的概念生成算法,其從最小概念出發(fā),逐步選擇字典序大于前一個外延的最小外延。重復(fù)這個過程,直到找到最大外延。然而NextClosure在判斷一個對象集合是否滿足最小外延需要多次進(jìn)行求交集，并且產(chǎn)生了大量無法形成外延的對象集合,而這些對象集合也需要重復(fù)進(jìn)行交集操作,從而導(dǎo)致該算法在概念數(shù)較多的形式背景上效率較低[16]。齊紅等[17]提出的改進(jìn)算法SSPCG(Search Space Partition based Concepts Generation)對搜索空間進(jìn)行劃分,通過判斷子搜索空間的有效性,避免了對非正規(guī)子空間的搜索,生成概念的效率明顯提高。盧明等[18]將概念搜索空間組織為前綴樹,構(gòu)建了映射前綴樹的屬性表,并使用屬性表對前綴樹中的無效子空間進(jìn)行剪枝。

筆者提出一種增量更新內(nèi)涵的概念生成算法IUICG(Incremental Updating Intension based Concepts Generation)。通過任務(wù)屬性將概念劃分為先行概念集合和新增概念集合,縮減了概念比對范圍。引入一個外延過濾集合,將無效外延進(jìn)行過濾,無效外延是不會產(chǎn)生新概念或?qū)е赂拍罡碌耐庋?。遍歷任務(wù)屬性的過程中,根據(jù)相關(guān)規(guī)則產(chǎn)生新概念或?qū)σ延懈拍畹膬?nèi)涵進(jìn)行更新。該過程基于任務(wù)屬性和已有概念的內(nèi)涵進(jìn)行運(yùn)算,無需對外延中對象間的屬性求交集,提高了算法效率。

1 基礎(chǔ)理論

定義1 形式背景。形式背景K定義為一個三元組K=(U,M,R),其中U是對象集合,M是屬性集合,R?U×M,表示U與M的二元關(guān)系。通常,將形式背景簡稱為背景。

對于u∈U,m∈M,若(u,m)∈R,表示對象u具有屬性m,記為uRm。

一個背景的例子[19]如表1所示。其中U={1,2,3,4,5,6,7,8},分別表示：水、鋼、木、玻璃、汽油、汞、紙和酒。M={a,b,c,d,e,f,g,h,i},分別表示：物質(zhì)、導(dǎo)電、導(dǎo)熱、固定形狀、透明、可燃、無固定形狀、揮發(fā)和可食用。

表1 形式背景示例Tab.1 The example of formal context

例如,2Ra=1表示對象2具有屬性a,而2Re=0,表示對象2不具有屬性e。

定義2 形式概念。K=(U,M,R)是一個背景,若X?U,Y?M,令

f(X)={m∈M|?u∈X,(u,m)∈R},g(Y)={u∈U|?m∈Y,(u,m)∈R}

若滿足f(X)=Y且g(Y)=X,稱二元組(X,Y)是一個形式概念(簡稱為概念)。X是概念(X,Y)的外延,Y是概念(X,Y)的內(nèi)涵。

如表1所示的背景中,存在一個對象集合X={1,5,8}和一個屬性集合Y={a,e,g}。f(X)={a,e,g}=Y,g(Y)={1,5,8}=X,所以二元組({1,5,8},{a,e,g})是一個概念,對象集合{1,5,8}是概念的外延,屬性集合{a,e,g}是概念的內(nèi)涵。

若X={1,4},Y={a,e}。f(X)={a,e}=Y,g(Y)={1,4,5,8}≠X,不滿足概念定義,所以二元組({1,4},{a,e})不是一個概念。

定理1[15]設(shè)K=(U,M,R)是一個背景,X,X1,X2∈U,Y,Y1,Y2∈M,則有

1)X1?X2?f(X2)?f(X1);

2)Y1?Y2?g(Y2)?g(Y1);

3)X?g(f(X));

4)Y?f(g(Y));

5)f(X)=f(g(f(X)));

6)g(Y)=g(f(g(Y)));

7)f(X1)∩f(X2)=f(X1∪X2);

8)g(Y1)∩g(Y2)=g(Y1∪Y2)。

定理2 設(shè)K=(U,M,R)是一個背景,若X∈U,則(g(f(X)),f(X))一定是概念,若Y∈M,則(g(Y),f(g(Y)))也一定是概念[15]。

定理3 對任意兩個概念(X1,Y1)和(X2,Y2),則Y1∩Y2=f(X1)∩f(X2)=f(X1∪X2)一定是內(nèi)涵,X1∩X2=g(Y1)∩g(Y2)=g(Y1∪Y2)一定是外延[15]。

2 增量更新內(nèi)涵的概念生成算法

2.1 算法思路

形式概念生成算法中的時間開支主要包括:基于外延求內(nèi)涵(或基于內(nèi)涵求外延)的大量交集運(yùn)算,以及概念生成過程中會產(chǎn)生大量無效的外延(或內(nèi)涵)。

針對相關(guān)問題,筆者提出一種增量更新內(nèi)涵的概念生成算法,其主要思路為:首先將M中的屬性按順序逐個設(shè)置為任務(wù)屬性,基于任務(wù)屬性將概念劃分為先行概念集合P和新增概念集合Q,分割了概念搜索空間,可避免全域概念比對,提高搜索效率。其次對每個任務(wù)屬性設(shè)置一個外延過濾集合F,利用F將無效外延(不會產(chǎn)生新概念或不會導(dǎo)致概念內(nèi)涵更新的外延)進(jìn)行過濾,解決了無效外延重復(fù)匹配的問題。提出內(nèi)涵更新規(guī)則,實(shí)現(xiàn)增量更新內(nèi)涵,避免了基于外延求內(nèi)涵的大量交集運(yùn)算。

2.2 算法理論

下面對算法中的符號及其含義進(jìn)行定義,同時提出了概念生成與更新規(guī)則。

定義3 任務(wù)屬性。M中的屬性已按照任意順序排列為M={m1,m2,…,m|M|},根據(jù)i=1,2,…,|M|的順序?qū)i逐個進(jìn)行處理,當(dāng)前正在處理的mi稱為任務(wù)屬性,記為m。

定義4 先行概念集P。M中處理順序先于m的所有屬性(即m1～mi-1)所產(chǎn)生的概念集合稱為先行概念集,記為P。Pk表示P中第k個概念,Pa和Pb分別表示P中概念的外延集合和內(nèi)涵集合,Pk,a和Pk,b分別表示P中第k個概念的外延和內(nèi)涵,f(Pk,a)=Pk,b,g(Pk,b)=Pk,a。

此處規(guī)定P中第1個概念的外延為U,內(nèi)涵為?,即P1,a=U,P1,b=?。

定義5 新增概念集Q。對任務(wù)屬性m,其所產(chǎn)生的所有概念稱為新增概念集,記為Q。Q的初始值為?。Qj表示Q中第j個概念,Qa和Qb分別表示Q中新增概念的外延集合和內(nèi)涵集合,Qj,a和Qj,b分別表示Q中第j個概念的外延和內(nèi)涵,f(Qj,a)=Qj,b,g(Qj,b)=Qj,a。

定義6 候選外延xi。對于任務(wù)屬性m,令xi=g(m)∩Pi,a,并稱xi為候選外延。

定義7 外延過濾集F。一個任務(wù)屬性m對應(yīng)一個F。F的初始值為?。Fr表示F中第r個元素,且F中元素為二元組Fr=(Fr,a,Fr,c),用Fa表示Fr,a的集合,Fc表示Fr,c的集合。

當(dāng)xi?Fa且xi∈Pa,新增Fr=(xi,‘P’)。當(dāng)x?Fa,且xi?Pa∪Qa,則新增Fr=(xi,‘Q’)。

命題1 對于任務(wù)屬性m,若其產(chǎn)生的候選外延xi滿足xi=Qj,a,則Pi,b?Qj,b。

證明xi=g(m)∩Pi,a=g(m)∩g(Pi,b),根據(jù)定理1中結(jié)論8),xi=g(m∪Pi,b)。因?yàn)镻i,b?m∪Pi,b,根據(jù)定理1中結(jié)論2),g(m∪Pi,b)?g(Pi,b)。因?yàn)閤i=Qj,a=g(Qj,b),可得g(Qj,b)?g(Pi,b)?Pi,b?Qj,b。

命題2 對于任務(wù)屬性m,若其產(chǎn)生的候選外延xi滿足xi=Pk,a,則m是Pk,b的新增屬性。

證明 根據(jù)定義6,xi=g(m)∩Pi,a?xi?g(m),根據(jù)定理1中結(jié)論1),可知f(g(m))?f(xi)。根據(jù)定理1中結(jié)論4),m?f(g(m)),則m?f(xi)。因xi=Pk,a,f(xi)=f(Pk,a),所以m?f(Pk,a)=Pk,b,即屬性m為概念Pk中內(nèi)涵Pk,b的新增屬性。

命題3 對于任務(wù)屬性m,xi=g(m)∩Pi,a,則xi一定是外延。

證明 因?yàn)閤i=g(m)∩Pi,a,根據(jù)定理2,g(m)一定是外延,而Pi,a也是外延。根據(jù)定理3,兩個外延的交一定是外延,所以xi一定是外延。

根據(jù)算法思路及上述理論,定義筆者算法中的概念操作規(guī)則如下。

規(guī)則1 外延過濾規(guī)則。若xi=Fr,a且Fr,c=‘P’,則無需進(jìn)行概念操作。

若xi=Fr,a且Fr,c=‘P’,表示xi?Pa,且任務(wù)屬性m已更新到Pb中(xi第1次出現(xiàn)時),所以無需進(jìn)行概念操作。

規(guī)則2Q更新規(guī)則。若xi?Fa,令Δb=Pi,b-Qj,b,Δb≠?,則更新Qj,b←Qj,b∪Δb,否則無需進(jìn)行概念操作。

當(dāng)xi=Qj,a,根據(jù)命題1,Qj,b=Qj,b∪Pi,b。令Δb=Pi,b-Qj,b,若Δb≠?,則Qj,b←Qj,b∪Δb,否則無需進(jìn)行概念操作。

規(guī)則3P更新規(guī)則。當(dāng)xi?Fa,若xi=Pk,a,則更新概念Pk的內(nèi)涵為Pk,b←Pk,b∪m,同時更新F←F∪(xi,‘P’)。

xi?Fa即xi首次出現(xiàn)時,若xi=Pk,a,根據(jù)命題2,m是Pk,b的新增屬性,所以更新Pk,b←Pk,b∪m。因?yàn)閤i?Fa,需要將xi加入Fa,即Fr,a=xi。又因?yàn)閤i∈Pa,所以對應(yīng)的Fr,c值為‘P’。

規(guī)則4 新增概念規(guī)則。若xi?Fa且xi?Pa,則新增概念Ql,Ql,a←xi,Ql,b←Pi,b∪m。其中l(wèi)=|Q|。同時更新F←F∪(xi,‘Q’)。

根據(jù)命題3,xi是一個外延。若xi?Fa且xi?Pa,則xi是一個新的外延,必然導(dǎo)致新增一個概念。根據(jù)命題2的證明可知,m?f(xi),同理可得Pi,b?f(xi),則m∪Pi,b?f(xi)。可知外延xi對應(yīng)的內(nèi)涵包含m和Pi,b,所以新增概念為(xi,Pi,b∪m)。

2.3 算法描述

基于上述算法思路和概念操作規(guī)則,IUICG的實(shí)現(xiàn)步驟如算法1所示。

算法1 IUICG

輸入：背景K=(U,M,R)。

輸出：概念集合P。

1)P←?;Q←?

2)F←?

3)P1,a←U;P1,b←?

4) FOREACHmINMDO:

5)g_m←g(m)

6) FOREACHiIN{1..|P|} DO

7)xi←g_m∩Pi,a

8)r←find(Fa,xi)

9) IFr≠0 THEN

10) IFFr,c=‘P’ THEN

11) CONTINUE

12) ELSE

13)j←find(Qa,xi)

14) IFj≠0 THEN

15) Δb←Pi,b-Qj,b

16) IFΔb≠? THEN

17)Qj,b←Qj,b∪Δb

18) ENDIF

19) ENDIF

20) ENDIF

21) ELSE

22)k←find(Pa,xi)

23) IFk≠0 THEN

24)Pk,b←Pk,b∪m

25)F|F|+1,a←xi;F|F|+1,c←‘P’

26) ELSE

27)l←|Q|

28)Ql+1,a←xi

29)Ql+1,b←Pi,b∪m

30)F|F|+1,a←xi;F|F|+1,a←‘Q’

31) ENDIF

32) ENDIF

33) ENDFOR

34)P←P∪Q

35)Q←?

36)F←?

37) ENDFOR

38) RETURNP。

該算法中,第5行的g(m)用于獲取所有包含屬性m的對象集合,第10～12行對同一任務(wù)屬性中重復(fù)的外延進(jìn)行過濾,第13～19行根據(jù)規(guī)則2判斷是否更新Q中的概念內(nèi)涵。第8行、第13行和第22行的find()函數(shù)用于查找xi在F、P或Q中對應(yīng)的位置,若未找到,返回0,否則返回匹配的元素索引。第22～25行根據(jù)規(guī)則3判斷是否更新P中的概念內(nèi)涵,第27～30行根據(jù)規(guī)則4對新增內(nèi)涵進(jìn)行操作。

3 實(shí)例分析

以表1中的形式背景為例。假設(shè)M中的屬性處理順序?yàn)閧a,b,c,d,e,f,g,h,i}。下面3個例子演示算法的主要思路,涉及對一個任務(wù)屬性進(jìn)行操作的各步驟計(jì)算方法,以及相應(yīng)規(guī)則的應(yīng)用。完整的概念生成過程見附錄A。為敘述方便,將任務(wù)屬性{m}簡記為m,如將g({a})表示為g(a)。

例1 對任務(wù)屬性a進(jìn)行操作。

初始化P1,a←U,P1,b←?,并初始化Q和F為空。

g(a)←{1,2,3,4,5,6,7,8},x1←g(a)∩P1,a={1,2,3,4,5,6,7,8}。x1?Fa且x1=P1,a,根據(jù)規(guī)則3,更新P1′,b←P1,b∪m={a},同時更新F←{{{1,2,3,4,5,6,7,8},‘P’}}。因?yàn)镻中只有一個概念,與任務(wù)屬性a相關(guān)的概念操作結(jié)束。最后,將Q中的新增概念更新到P中,并清空Q和F。

例2 對任務(wù)屬性e進(jìn)行操作。對于任務(wù)屬性m=e,P中已有4個概念(由e之前的任務(wù)屬性a,b,c,d所生成),如表2所示。其中P1′表示概念P1已動態(tài)更新一次內(nèi)涵,P2″表示概念P2已動態(tài)更新兩次內(nèi)涵。另外,一個任務(wù)屬性開始時,Q為空,F為空。

表2 任務(wù)屬性(e)的先行概念集合PTab.2 The privious concept set P of task attribute(e)

操作步驟如下。

S1求任務(wù)屬性e的對象集合：g(e)←{1,4,5,8}。

S2將g(e)與表2中的外延集合Pa元素逐個求交集,并根據(jù)規(guī)則進(jìn)行概念操作。

S2.1x1←g(e)∩P1′,a={1,4,5,8}∩{1,2,3,4,5,6,7,8}={1,4,5,8}。

首先,因?yàn)镕為空,x1?F。將x1與Pa中的外延逐個比較,沒有與x1匹配的外延,即x1?Pa。根據(jù)規(guī)則4,在Q中新增概念Q1,其中Q1,a←x1={1,4,5,8},Q1,b←P1′,b∪m={a,e}。同時更新F←{{{1,4,5,8},‘Q’}}。

S2.2x2←g(e)∩P2″,a={1,4,5,8}∩{2,6}=?,x2?Fa且x2?Pa。根據(jù)規(guī)則4,在Q中新增概念Q2,其中Q2,a←x2=?,Q2,b←P2″,b∪m={a,b,c,e}。同時更新F←{{{1,4,5,8},‘Q’},{?,‘Q’}}。

S2.3x3←g(e)∩P3,a={4}。x3?Fa且x3?Pa,根據(jù)規(guī)則4,在Q中新增概念Q3,Q3,a←x3={4},Q3,b←P3,b∪m={a,d,e}。同時更新F←{{{1,4,5,8},‘Q’},{?,‘Q’},{{4},‘Q’}}。

S2.4x4←g(e)∩P4,a={1,4,5,8}∩{2}=?。x4∈Fa且x4=Q2,a(由步驟S2.2生成),Δb←P4,b-Q2,b={a,b,c,d}-{a,b,c,e}=j5i0abt0b,Δb≠?。根據(jù)規(guī)則2,更新Q2′,b←Q2,b∪Δb={a,b,c,d,e}。因x4∈Fa,所以此處無需更新F。

至此,由任務(wù)屬性e生成的新增概念集合Q處理完畢。Q中的概念如表3所示。

表3 任務(wù)屬性(e)的新增概念集合QTab.3 The newly-add concept set Q of task attribute (e)

S3將Q更新到P中,并清空Q和F。最后,P中的概念如表4所示。

表4 更新后的先行概念集合PTab.4 The updated privious concept set P

例2中Fa與Qa相同,未體現(xiàn)F作為過濾器的作用。如前所述,Qa?Fa,大部分情況下Fa中包含的元素多于Qa。實(shí)際上,F可以快速檢測出無需更新的操作,尤其是對M中位置靠后的任務(wù)屬性,F的過濾作用比較明顯,如例3所示。

例3 對任務(wù)屬性h進(jìn)行操作。因?yàn)榍蠼獠襟E與例2相似,此處進(jìn)行簡要說明,不再列出詳細(xì)計(jì)算過程。

首先g(h)←{5,8},此時先行概念表P中由屬性a～g生成的概念共有10個,具體請參考附錄A。

將g(h)與P中外延集合Pa的元素逐個求交集

x1=x5=x8=x10=x11=x13={5,8}=P10′,a,

x2=x3=x4=x6=x7=x9=x12=?=P6?,a

先處理x1。因?yàn)殚_始時F為空,x1?Fa,且x1=P10′,a,根據(jù)規(guī)則3,更新P10″,b←P10′,b∪m={a,e,f,g,h},同時更新F←{{{5,8},‘P’}}。此后,因?yàn)閤5,x8,x10,x11,x13都等于F1,a,且滿足F1,c=‘P’,根據(jù)規(guī)則1,無需對概念進(jìn)行操作。

同樣,x2?Fa,且x2=P6?,a,根據(jù)規(guī)則3,更新P6″″,b←P6?,b∪m={a,b,c,d,e,f,g,h}。同時更新F←{{{5,8},‘P’},{?,‘P’}}。此后,因?yàn)閤3,x4,x6,x7,x9,x12都等于F2,a,且F2,c=‘P’,根據(jù)規(guī)則1,無需對概念進(jìn)行操作。

從例3可見,這里F={{5,8},?},而Q為空,兩者之間并不相等。根據(jù)xi是否屬于Fa,可快速判斷當(dāng)前應(yīng)執(zhí)行哪種操作,且每次只需搜索Pa和Qa兩個集合之一,節(jié)省了大量搜索與匹配的時間。

4 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)對比算法是NextClosure。實(shí)驗(yàn)環(huán)境：Intel Xeon E-2224G CPU,64 Gbyte RAM,Windows 10操作系統(tǒng),算法采用Python3.8實(shí)現(xiàn)。

為提高NextClosure運(yùn)行效率,設(shè)置了一個查重字典,對第1次出現(xiàn)的f(u)及g(f(u))寫入字典,后續(xù)出現(xiàn)相同的f(u)時直接查表,以避免多次重復(fù)計(jì)算,其中u=A∩{1,2,…,i-1}∪{i},A是待判斷的外延。另外,Python中字典類型利用Hash查找,能快速定位元素,所以NextClosure和筆者算法IUICG都采用字典存儲概念,外延對應(yīng)Key,內(nèi)涵對應(yīng)Value。背景中的每個對象對應(yīng)的屬性,以及每個屬性對應(yīng)的對象都采用預(yù)先存儲的形式,以加快后續(xù)的交集運(yùn)算速度。

為更好評估算法的時間性能,兩個算法在不同數(shù)據(jù)集上都運(yùn)行15次,并以各次的運(yùn)行時間平均值作為實(shí)驗(yàn)結(jié)果。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集采用人工隨機(jī)數(shù)據(jù)集。與其他文獻(xiàn)類似,數(shù)據(jù)集主要考慮背景的對象數(shù)量|U|,屬性數(shù)量|M|和屬性的填充率|f| 3個參數(shù)。數(shù)據(jù)集各參數(shù)的值設(shè)置如表5所示。

表5 數(shù)據(jù)集參數(shù)Tab.5 The data set parameters

數(shù)據(jù)集包含4種類型,Net1數(shù)據(jù)集用于測試算法在不同屬性數(shù)量上的時間性能。Net2數(shù)據(jù)集是Net1中對應(yīng)網(wǎng)絡(luò)的轉(zhuǎn)置,|M|不變,而|U|逐漸增大,用于測試算法對|U|變化的適應(yīng)性。Net3考慮了|U|和|M|不變的情況下,屬性填充率變化對算法的影響。Net4用于測試筆者算法在較大規(guī)模數(shù)據(jù)集上的時間性能。各數(shù)據(jù)集對應(yīng)的概念數(shù)量如表6所示。

表6 所有背景的概念數(shù)Tab.6 Number of concepts in all contexts

由表6可見,Net1和Net2數(shù)據(jù)集對應(yīng)的概念數(shù)量一致,這是因?yàn)閷⑿问奖尘稗D(zhuǎn)置,僅是將對象概念轉(zhuǎn)換為屬性概念,本質(zhì)上對應(yīng)的概念一致。

4.2 實(shí)驗(yàn)結(jié)果與分析

在Net1和Net2上的實(shí)驗(yàn)結(jié)果如圖1所示。因?yàn)镹et1和Net2是同一形式背景上的對象概念和屬性概念的關(guān)系,將兩者的實(shí)驗(yàn)結(jié)果對比,可以更好地了解算法的時間性能和適應(yīng)場景。其中,圖例后綴為|U|的表示該折線是關(guān)于背景中對象數(shù)量|U|變化的實(shí)驗(yàn)結(jié)果,即在Net2上的實(shí)驗(yàn)結(jié)果。相應(yīng)的,圖例后綴為|M|的是在Net1上的實(shí)驗(yàn)結(jié)果。因NextClosure-|U|在|U|變大時運(yùn)行時間快速增長,此處只列出其在Net2前3個網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果。

圖1 在Net1和Net2上的運(yùn)行時間性能比較Fig.1 Runtime performance comparison on Net1 and Net2

圖1結(jié)果表明,在Net1和Net2上,IUICG算法的時間性能都優(yōu)于NextClosure算法,且在Net2上兩者的運(yùn)行時間有很大差異。這是因?yàn)镹extClosure每生成一個外延都要進(jìn)行以下運(yùn)算：首先計(jì)算u=A⊕i,再進(jìn)行f(u)和g(f(u))運(yùn)算,最后再對A

NextClosure算法在Net1上的時間耗費(fèi)遠(yuǎn)小于在Net2上的。與NextClosure相反的是,IUICG在Net2上具有更好的時間性能,其在Net2上的時間復(fù)雜度接近線性,其中,在Net26(|U|=3 000)上的運(yùn)行時間約為4.5 s。

通過分析兩種算法的實(shí)現(xiàn)過程,可以看出,NextClosure中,生成大于上一個外延的最小外延,可能需要遍歷全部對象,且存在大量的交集操作,隨著對象數(shù)量增加,其所需的時間也快速增加。IUICG在每個屬性上進(jìn)行概念操作,每增加一個屬性,就需要與已有的概念進(jìn)行一輪交集運(yùn)算,所以隨著屬性數(shù)量增加,IUICG的運(yùn)行時間也隨之增加。

兩種算法具有不同的適應(yīng)性,NextClosure對|U|的變化更為敏感,而IUICG對|M|的變化更為敏感。但總體上,IUICG比NextClosure具有更優(yōu)的時間性能。

基于上述實(shí)驗(yàn)結(jié)果,筆者提出以下操作方案。對對象數(shù)量和屬性數(shù)量有較大差異的數(shù)據(jù)集,若屬性數(shù)量大于對象數(shù)量,將形式背景進(jìn)行轉(zhuǎn)置,用IUICG算法先得到背景的屬性概念,再將其轉(zhuǎn)換為對象概念,這將有效提高概念生成速度。

Net3中,在|U|和|M|不變的情況下,逐漸增加屬性的填充率,其對應(yīng)的概念數(shù)量快速增長。如表6所示,Net35的概念數(shù)量還不到100萬,而Net36的概念數(shù)接近400萬。兩個算法在Net3上的的運(yùn)行時間對比結(jié)果如圖2所示。圖3給出了IUICG算法在較大規(guī)模|U|的數(shù)據(jù)集上的運(yùn)行效率。

圖2 在Net3上的運(yùn)行時間性能比較 圖3 在Net4上的實(shí)驗(yàn)結(jié)果Fig.2 Runtime performance comparison on Net3 Fig.3 Experimental results on Net4

其中NextClosure只列出前4個網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果,其在Net35(|f|=0.25)和Net36(|f|=0.3)上的運(yùn)行時間分別約為8 000 s和30 000 s。而IUICG算法在Net36上的運(yùn)行時間約為110 s。兩者之間的差異較大,原因與前面的分析相同?？梢?IUICG對屬性高填充率的網(wǎng)絡(luò)仍有較好的適應(yīng)性。

因?yàn)镹extClosure在此類數(shù)據(jù)集上的性能較差,此處不予比較。IUICG的運(yùn)行時間會隨著|U|增大,但仍呈現(xiàn)接近線性的時間復(fù)雜度。

5 結(jié) 語

筆者提出一種增量更新內(nèi)涵的概念生成算法IUICG。算法根據(jù)任務(wù)屬性對概念搜索空間進(jìn)行劃分,并引入外延過濾集合,加快了候選外延的判斷速度。提出概念操作規(guī)則,證明了規(guī)則的正確性,為快速更新內(nèi)涵和新增概念提供了理論依據(jù)。在各種人工隨機(jī)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,IUICG具有較好的時間性能。

IUICG中,生成候選外延仍然需要遍歷已有概念,如何有效縮減候選外延是下一步的研究重點(diǎn)。另外,分析概念間的生成與包含關(guān)系,在高效生成概念的過程同時構(gòu)建概念間的層次結(jié)構(gòu)也有待于研究。

附錄A IUICG算法在表1背景上的運(yùn)行步驟。

mg(m)xi滿足條件適用規(guī)則{12345678}a{12345678}x1={12345678}x1notinFaandx1=P1,a規(guī)則3b{26}x1={26}x1notinFaandx1notinPa規(guī)則4c{26}x1={26}x1notinFaandx1=P2,a規(guī)則3x2={26}x2=F1,aandF1,c=‘P’規(guī)則1d{2347}x1={2347}x1notinFaandx1notinPa規(guī)則4x2={2}x2notinFaandx2notinPa規(guī)則4e{1458}x1={1458}x1notinFaandx1notinPa規(guī)則4x2=?x2notinFaandx2notinPa規(guī)則4x3={4}x3notinPaandx3notinQa規(guī)則4x4=?x4inFaandx4=Q2,aandΔb=P4,b-Q2,b=j5i0abt0b規(guī)則2f{3578}x1={3578}x1notinFaandx1notinPa規(guī)則4x2=?x2notinFaandx2=P6′,a規(guī)則3x3={37}x3notinFaandx3notinPa規(guī)則4x4=?x4=F2,aandF2,c=‘P’規(guī)則1x5={58}x5notinFaandx5notinPa規(guī)則4x6=?x6=F2,aandF2,c=‘P’規(guī)則1x7=?x7=F2,aandF2,c=‘P’規(guī)則1g{1568}x1={1568}x1notinFaandx1notinPa規(guī)則4x2={6}x2notinFaandx2notinPa規(guī)則4x3=?x3notinFaandx3=P6″,a規(guī)則3x4=?x4=F3,aandF3,c=‘P’規(guī)則1x5={158}x5notinFaandx5notinPa規(guī)則4x6=?x6=F3,aandF3,c=‘P’規(guī)則1x7=?x7=F3,aandF3,c=‘P’規(guī)則1x8={58}x8notinFaandx8=P10,a規(guī)則3x9=?x9=F3,aandF3,c=‘P’規(guī)則1x10={58}x10=F5,aandF5,c=‘P’規(guī)則1h58x1={58}x1notinFaandx1=P10′,a規(guī)則3x2=?x2notinFaandx2=P6?,a規(guī)則3x3=?x3=F2,aandF2,c=‘P’規(guī)則1x4=?x4=F2,aandF2,c=‘P’規(guī)則1

(續(xù)表)

(續(xù)表)