基于NextClosure改進(jìn)的概念生成算法

林志鴻，吳清壽

(1.湄洲灣職業(yè)技術(shù)學(xué)院信息工程系，福建 莆田 351111；2.武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建 武夷山 354300；3.智慧農(nóng)林福建省高校重點(diǎn)實(shí)驗(yàn)室(福建農(nóng)林大學(xué))，福建 福州 350002)

0 引言

概念是形式概念分析(formal concept analysis，F(xiàn)CA)[1]理論的核心數(shù)據(jù)結(jié)構(gòu)，它反映的是形式背景中對象與屬性之間的最大組合狀態(tài)。目前，概念已在復(fù)雜網(wǎng)絡(luò)分析[2]、關(guān)聯(lián)分析[3]和文本挖掘[4]等領(lǐng)域得到了廣泛應(yīng)用。1999年，GANTER等[5]提出了一種基于當(dāng)前閉包求所有正規(guī)閉包的算法——NextClosure算法，該算法能夠生成背景的全部概念，且無需全局搜索匹配其他概念。NextClosure算法對于屬性數(shù)量多而對象數(shù)量少的背景具有較好的適應(yīng)性，但在判斷閉包的正規(guī)性時，因需要進(jìn)行大量的交集運(yùn)算,所以時間復(fù)雜度較高。2004年，盧明等[6]將搜索空間組織為前綴樹，根據(jù)閉包空間的正規(guī)性判定條件，對前綴樹進(jìn)行剪枝以降低搜索復(fù)雜度，提高了算法的時間性能。2005年，齊紅等[7]提出一種基于搜索空間劃分的概念生成方法，該算法將搜索空間劃分為子空間，通過有效性判斷過濾不能生成正規(guī)閉包的子空間，提高了概念生成效率。在概念格構(gòu)建的研究中，增量式方法得到學(xué)者的較多關(guān)注，其中,AddIntent算法[8]是增量式方法的一種典型代表，它能夠生成全部概念并構(gòu)建出概念之間的層次關(guān)系。 2011年，Lü等[9]提出了一種改進(jìn)的AddIntent算法，該算法通過增加字段來實(shí)現(xiàn)快速定位新概念。2019年，ZHANG等[10]在AddIntent的基礎(chǔ)上提出了FastAddExtent算法，該算法通過減少概念之間的無效比較實(shí)現(xiàn)概念格的快速構(gòu)建。針對NextClosure算法中存在的冗余操作和交集運(yùn)算時間復(fù)雜度較大的問題，本文基于哈希表和集合元素過濾的方法提出了一種改進(jìn)的NextClosure算法——INCA算法(Improved NextClosure Algorithm)，并通過仿真實(shí)驗(yàn)證明了INCA算法的有效性。

1 基礎(chǔ)理論

定義1[5]設(shè)O是對象的集合，A是屬性的集合，R是集合O和A之間的關(guān)系，則三元組K=(O,A,R)是一個形式背景(簡稱背景)。對于o∈O，a∈A，(o,a)∈R表示對象o具有屬性a，背景中對應(yīng)的行列交叉處的值為1，(o,a)?R表示對象o不具有屬性a，背景中對應(yīng)的值為0。通常地，背景用矩陣表示，一行表示一個對象，一列表示一個屬性。

形式背景示例如表1所示，其中，O={1,2,3,4,5}，A={a,b,c,d}。對象1具有屬性{b,d}，則表1中對象1和屬性b和d交叉處的值為1，對象1不具有屬性{a,c}，則表1中對應(yīng)位置處的值為0。

表1 形式背景示例

定義2[5]對于背景K=(O,A,R)，若X?O，Y?A，則令

f(X)={a∈A|?o∈X,(o,a)∈R}，g(Y)={o∈O|?a∈Y,(o,a)∈R}，

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

對于表1中的背景，若X={3,4}，Y={b,c}，則二元組({3,4},{b,c})是一個概念，因?yàn)閒(X)={b,c}，g(Y)={3,4}，滿足f(X)=Y，g(Y)=X。

若X={1,2}，Y=，則({1,2},)不是一個概念，因?yàn)閒(X)=，g(Y)={1,2,3,4,5}，f(X)=Y，而g(Y)≠X。

定義3[5]對于P,Q?O，且P和Q中的元素已按從小到大排序。對P和Q中的元素從左邊第1個元素開始比較，若第1次出現(xiàn)不相等的元素位置為i，且Pi>Qi，則稱P字典序地小于Q。同時規(guī)定?的字典序最小。

若P={2,4,5}，Q={2,3,4}，則當(dāng)i=2(i從1開始)時，P2>Q2。由此可知，P字典序地小于Q。

定義4[5]設(shè)S,T?O，i∈O，并將S

定理1[5]設(shè)K=(O,A,R)是一個背景，X,X1,X2∈O，Y,Y1,Y2∈A，則有以下性質(zhì)：

(1)X1?X2?f(X2)?f(X1)，(1’)Y1?Y2?g(Y2)?g(Y1)；

(2)X?g(f(X))，(2’)Y?f(g(Y))。

定理2[5]對于S?O，關(guān)于字典序地大于S的最小外延是S⊕i，i是滿足S

定理3[5]設(shè)K=(O,A,R)是一個背景，若X∈U，則(g(f(X)),f(X))一定是概念；若Y∈M，則(g(Y),f(g(Y)))也一定是概念。

以上定理的證明見文獻(xiàn)[5]，本文在此省略。

2 NextClosure算法及問題分析

2.1 NextClosure算法

由定義4和定理2可得到NextClosure算法的主要步驟：(1)從最小概念(g(f(?)),f(?))開始查找下一個外延；(2)假設(shè)S是當(dāng)前外延；(3)根據(jù)定理2逐個尋找滿足S

輸入：形式背景K=(O,A,R)

輸出：全部概念集合C

C←?

C←C∪{g(f(?)),f(?)}

D←sort(O,DESC)

S←g(f(?)

whileS≠Odo

J←D-S

foreachiinJdo

F←f(S∩{1,…,i-1}∪i)

T←g(F)

K←T∩{1,…,i-1}

ifi∈T-SandS∩{1,…,i-1}=Kthen

C←C∪{T,F}

S←T

break

endif

endfor

endwhile

returnC

在算法1中，第3行將對象集合O中的元素進(jìn)行降序排列，以方便按字典序查找滿足S

2.2 實(shí)例分析

利用NextClosure算法生成概念的過程如表2所示(以表1中的背景為例)。根據(jù)算法1中的第2行，設(shè)置初始概念為(g(f(?)),f(?))，其中，f(?)={a,b,c,d}，g(f(?))=?。

表2 NextClosure算法生成概念的過程

為了更好地說明NextClosure算法的執(zhí)行過程，下面以兩個例子進(jìn)行說明。

例1 求概念({3},{a,b,c})的下一個按字典序外延大于{3}的最小外延。

初始時，S={3}，J={5,4,2,1}，J中的元素已按照字典序排列(即按降序排列)，但不包括S中的元素3(根據(jù)算法1的第6行)。

i的值從5開始。令u=S∩{1,…,i-1}∪{i}={3}∩{1,2,3,4}∪{5}={3,5}。從表1的背景可知，F(xiàn)=f(u)=f({3,5})={a,b}，T=g(F)={2,3,5}。根據(jù)定義4，S

取i的下一個值(i=4)。因u={3}∩{1,2,3}∪{4}={3,4}，F(xiàn)=f(u)={b,c}，T=g(F)={3,4}。S∩{1,…,i-1}={3}，T∩{1,…,i-1}={3}，S∩{1,…,i-1}=T∩{1,…,i-1}，且i∈T-S，滿足S

例2 求概念({1,4},{b,d})的下一個外延。

初始時，S={1,4}，D’={5,3,2}。

i=5。因u={1,4}∩{1,2,3,4}∪{5}={1,4,5}，F(xiàn)=，T=g(F)={1,2,3,4,5}，且S∩{1,…,i-1}={1,4}，T∩{1,…,i-1}={1,2,3,4}，不滿足S

i=3。因u={1,4}∩{1,2}∪{3}={1,3}，F(xiàn)=，T=g(F)={1,2,3,4,5}，且S∩{1,…,i-1}={1}，T∩{1,…,i-1}={1,2}不滿足S

i=2。因u={1,2}，F(xiàn)=，T=g(F)={1,2,3,4,5}。S∩{1,…,i-1}={1}，T∩{1,…,i-1}={1}，S∩{1,…,i-1}=T∩{1,…,i-1}，且i∈T-S滿足S

2.3 存在問題分析

由上述兩個實(shí)例的計(jì)算過程可知，NextClosure算法在以下步驟中存在大量的重復(fù)運(yùn)算和低效率操作，進(jìn)而影響算法的運(yùn)行速度，并且形式背景規(guī)模越大，其對算法的運(yùn)行速度影響越大。

(1)基于字典序求外延S的下一個外延時，對于每一個i，需重新計(jì)算F和T。在表2所示的概念生成過程中，第3、7、9、11、12、13行的F=重復(fù)6次，則g(F)也需要重復(fù)計(jì)算6次，第1、5、8行中的F={a,b}重復(fù)3次，其對應(yīng)的g(F)也重復(fù)計(jì)算3次。求解g(F)的時間復(fù)雜度為O(rknlog2n)，其中，r是重復(fù)求g(F)的次數(shù)，k是F中包含的元素數(shù)量，nlog2n是兩個集合求交集的時間復(fù)雜度。

(2)對于任意的一對S和i，算法1都要進(jìn)行2次的S∩{1,…,i-1}(第8行和第11行)和1次的T∩{1,…,i-1}(第10行)運(yùn)算。求解兩個集合交集的時間復(fù)雜度為O(nlog2n)。

(3)對于任意的一對S和i，需要進(jìn)行1次S∩{1,…,i-1}與T∩{1,…,i-1}的等價判斷。集合等價判斷的時間復(fù)雜度為O(nlog2n)。

(4)對于任意的一對S和i，需要進(jìn)行1次的i∈T-S判斷。i∈T-S判斷的時間復(fù)雜度為O(nlog2n)。

3 改進(jìn)算法INCA

3.1 改進(jìn)思路

(1)針對同一個F值多次重復(fù)求g(F)的問題，通過增加一個Hash表用以消除重復(fù)計(jì)算問題。其主要方法為：對于首次出現(xiàn)的F值，將F和F中屬性集合對應(yīng)的最大對象集合(g(F)二元組(F,g(F)))存儲到一個Hash表中。當(dāng)F重復(fù)出現(xiàn)時，直接取出其對應(yīng)的g(F)值可避免g(F)的重復(fù)計(jì)算。本文采用Python作為兩個算法的實(shí)現(xiàn)語言，并采用Python語言中的字典(dict)類型實(shí)現(xiàn)消除上述重復(fù)計(jì)算g(F)的問題，即增加空字典H，通過get(F,0)函數(shù)查詢F是否已在H中，若不存在，則將{F,g(F)}加入到H中，否則直接返回g(F)的值。

(2)針對交集運(yùn)算時間復(fù)雜度較高的問題，本文采用元素過濾的方法提高其效率，具體操作如下：對于S∩{1,…,i-1}運(yùn)算，注意到{1,…,i-1}包含了小于i的所有元素，因此該問題可以轉(zhuǎn)換為求S中所有小于i的元素。如表2的第9行，S={2,3,5}，i=4，直接用交集方法求解S∩{1,…,i-1}，其結(jié)果為{2,3,5}∩{1,2,3,4}={2,3}，該過程需要對S重復(fù)掃描4次，目前已知方法中，求解兩個無序集合交集的時間復(fù)雜度為O(nlog2n)；而采用元素過濾的方法，只需對S進(jìn)行一趟掃描即可得到S中小于i的元素集合為{2,3}，其時間復(fù)雜度為O(n)。因此，S∩{1,…,i-1}和T∩{1,…,i-1}都可以根據(jù)此方法改進(jìn)，以提高閉包正規(guī)性判斷條件的求解效率。

(3)對于S∩{1,…,i-1}與T∩{1,…,i-1}的等價判斷問題，采用下述方法進(jìn)行改進(jìn)：令P=S∩{1,…,i-1}，Q=T∩{1,…,i-1}，若|P|≠|(zhì)Q|，則集合P和Q必然不等價。利用兩個集合的長度可以快速排除大量P和Q不相等的情況。求集合長度的時間復(fù)雜度為O(n)，而判斷集合等價的時間復(fù)雜度為O(nlog2n),所以上述通過判斷集合長度相等的措施可有效降低判斷集合等價的時間開支。若|P|=|Q|，將P建立為Hash表，將Q中的元素在Hash表中檢測沖突，若存在不沖突的元素，則P≠Q(mào)，否則P=Q。

(4)對于i∈T-S的判斷問題，由以下說明可知i∈T-S必然成立：算法1第6、7行有J=D-S，且i∈J，可知i?S。如D={5,4,3,2,1},S={3,4},則J=D-S={5,2,1},而顯然i?S。算法第8、9行有T=g(f(S∩{1,…,i-1}∪i))，根據(jù)定理1，S∩{1,…,i-1}∪i?g(f(S∩{1,…,i-1}∪i))，可得i∈T。由于i∈T且i?S，則i∈T-S一定成立。所以，S

3.2 改進(jìn)算法

根據(jù)以上改進(jìn)思路，本文提出的INCA算法(算法2)如下：

輸入：形式背景K=(O,A,R)

輸出：全部概念集合C

C←{g(f(?)):f(?)}

H←{f(?):g(f(?))}

D←sort(O,DESC)

S←g(f(?)

whileS≠Odo

J←D-S

foreachiinJdo

P←filter(S,i)

F←f(P∪i)

ifFinH.keys() then

T∪H[F].value

else

T←g(F)

H←H∪{F,T}

endif

Q←filter(T,i)

if |P|≠|(zhì)P| then

continue

else

if equal(P,Q) then

C←C{T,F}

S←T

break

endif

endif

endfor

endwhile

returnC

INCA算法中，第2行用以初始化字典H，初始化時以F(初始值為f(?))作為字典H中元素的key，以T(初始值為g(f(?)))作為value。根據(jù)改進(jìn)思路(2)可知，第8、16行的filter函數(shù)從S中過濾出所有小于i的元素集合，代替了交集運(yùn)算。根據(jù)改進(jìn)思路(1)，第10～15行通過查詢F是否在字典H中，若F已存在，則直接從字典H中取出F對應(yīng)的T值，否則將F與對應(yīng)的T組成的鍵值對{F,T}加入字典H中。第17、18行根據(jù)集合元素長度對S

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

為了評估INCA算法和NextClosure算法的時間性能，對其進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境：Intel Core i7-8650U CPU，16 G RAM，Windows 10操作系統(tǒng)，算法采用Python3.8。兩個算法在所有背景上的都分別運(yùn)行10次，實(shí)驗(yàn)結(jié)果取10次運(yùn)行時間的平均值。

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

實(shí)驗(yàn)數(shù)據(jù)集采用人工數(shù)據(jù)集，數(shù)據(jù)集的大小和稠密程度由三個參數(shù)決定：背景的對象數(shù)量|O|，每個對象最大的屬性數(shù)量|A|，每行屬性的填充率f。實(shí)驗(yàn)數(shù)據(jù)集(Ds1、Ds2和Ds3)中的參數(shù)值設(shè)置如表3所示。Ds1包含10個背景，用于測試算法在|O|不變而|A|值逐漸增大時的時間性能。將Ds1中背景的對象與屬性進(jìn)行轉(zhuǎn)置，得到Ds2。如Ds1中的第10個背景(|O|=100，|A|=1 000)，將其轉(zhuǎn)置后，對應(yīng)Ds2中的第10個背景(|O|=1 000，|A|=100)。同樣地，Ds2中也包含10個背景，且10個背景|A|不變，而|O|逐漸增大，用于測試算法在|O|發(fā)生變化時的適應(yīng)性。Ds3中包含7個背景，各個背景的|O|和|A|均不變，而屬性填充率f逐漸變大(每次增加5%)，用于測試屬性填充率變化對算法性能的影響。

表3 隨機(jī)數(shù)據(jù)集參數(shù)值

4.2 實(shí)驗(yàn)仿真與分析

以表3中的27個背景對INCA算法和NextClosure算法生成的概念數(shù)量進(jìn)行實(shí)驗(yàn)對比(表4)。

表4 兩種算法生成的概念數(shù)量

由表4可以看出，兩個算法在所有背景上得到的概念數(shù)量相同，由此表明INCA算法具有良好的準(zhǔn)確性。在表4中，數(shù)據(jù)集Ds1和Ds2中對應(yīng)的背景(如Ds1_1與Ds2_1)概念數(shù)量相同，其原因是形式背景轉(zhuǎn)置的本質(zhì)是將同一概念的內(nèi)涵與外延進(jìn)行交換，所以兩者對應(yīng)的概念數(shù)量相同。表4中，|A|對應(yīng)Ds1中10個背景的屬性數(shù)量，|O|對應(yīng)Ds2中10個背景的對象數(shù)量，f對應(yīng)Ds3中7個背景的屬性填充率。

表4中小括號內(nèi)的值為數(shù)據(jù)集的參數(shù)及對應(yīng)的值。

INCA算法和NextClosure算法在Ds1數(shù)據(jù)集上的仿真結(jié)果如圖1所示。由圖1可以看出，INCA算法在各個背景上的時間性能都優(yōu)于NextClosure算法。經(jīng)計(jì)算，INCA算法的平均運(yùn)行時間比NextClosure算法的平均運(yùn)行時間降低了15.4%。

圖1 INCA算法和NextClosure算法在Ds1數(shù)據(jù)集上的仿真結(jié)果

INCA算法和NextClosure算法在Ds2數(shù)據(jù)集上的仿真結(jié)果如圖2所示。由圖2可以看出，INCA算法在該數(shù)據(jù)集在10個背景上的時間性能顯著優(yōu)于NextClosure算法。經(jīng)計(jì)算，INCA算法在10個背景上的平均時間性能比NextClosure算法減少了50%。

對比圖1和圖2可知，兩種算法在數(shù)據(jù)集Ds1和Ds2上生成的概念數(shù)量雖然一樣，但運(yùn)行時間存在很大差異，即NextClosure算法和INCA算法在數(shù)據(jù)集Ds2的運(yùn)行時間大幅低于在數(shù)據(jù)集Ds1的運(yùn)行時間。例如，NextClosure在Ds1中的第10個背景(|O|=100，|A|=1 000)上的平均運(yùn)行時間約為960 s(INCA的平均運(yùn)行時間約為811 s)，而在Ds2的第10個背景(|O|=1 000，|A|=100)上的運(yùn)行時間約為125 s(INCA的平均運(yùn)行時間約為63 s)。上述表明，NextClosure算法和INCA算法對|A|>|O|的背景具有更好的適應(yīng)性。

|A|圖2 INCA算法和NextClosure算法在Ds2數(shù)據(jù)集上的仿真結(jié)果

圖3為INCA算法和NextClosure算法在Ds3數(shù)據(jù)集上的仿真結(jié)果。由圖3可以看出，兩種算法的運(yùn)行時間都隨背景屬性填充數(shù)量的增加而快速增加，但I(xiàn)NCA算法的運(yùn)行時間顯著優(yōu)于NextClosure算法。經(jīng)計(jì)算，INCA算法的運(yùn)行時間比NextClosure算法平均降低了20.3%。

圖3 INCA算法和NextClosure算法在Ds3數(shù)據(jù)集上的仿真結(jié)果

5 結(jié)語

實(shí)驗(yàn)表明，本文提出的INCA算法在生成概念的效率上明顯優(yōu)于NextClosure算法。在三類不同類型數(shù)據(jù)集的背景上，INCA算法的平均運(yùn)行時間比NextClosure算法分別減少了15.4%(Ds1)、50%(Ds2)和20.3%(Ds3)，該結(jié)果表明INCA算法具有較好的適應(yīng)性，尤其是在對象數(shù)量遠(yuǎn)大于屬性數(shù)量且屬性填充較為稀疏的背景上。因此，本文提出的INCA算法在網(wǎng)絡(luò)分析和推薦系統(tǒng)等領(lǐng)域具有較好的應(yīng)用價值，如對于|O|和|A|差異較大的背景，若|O|>|A|，則可將該背景轉(zhuǎn)置后使用INCA算法生成以屬性集合為外延、以對象集合為內(nèi)涵的概念(稱為屬性概念)，再將屬性概念中的外延與內(nèi)涵交換，就可以得到以對象集合為外延、以屬性集合為內(nèi)涵的概念(稱為概念屬性)。今后的研究將根據(jù)概念生成過程中的相關(guān)信息探究概念間的層次結(jié)構(gòu)，在生成概念的同時構(gòu)建出概念格。