林志鴻，吳清壽

(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ī)性時(shí)，因需要進(jìn)行大量的交集運(yùn)算,所以時(shí)間復(fù)雜度較高。2004年，盧明等[6]將搜索空間組織為前綴樹，根據(jù)閉包空間的正規(guī)性判定條件，對前綴樹進(jìn)行剪枝以降低搜索復(fù)雜度，提高了算法的時(shí)間性能。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)算時(shí)間復(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)是一個(gè)形式背景(簡稱背景)。對于o∈O，a∈A，(o,a)∈R表示對象o具有屬性a，背景中對應(yīng)的行列交叉處的值為1，(o,a)?R表示對象o不具有屬性a，背景中對應(yīng)的值為0。通常地，背景用矩陣表示，一行表示一個(gè)對象，一列表示一個(gè)屬性。

形式背景示例如表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)是一個(gè)形式概念(簡稱概念)，其中，X是概念的外延，Y是概念的內(nèi)涵。

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

若X={1,2}，Y=，則({1,2},)不是一個(gè)概念，因?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個(gè)元素開始比較，若第1次出現(xiàn)不相等的元素位置為i，且Pi>Qi，則稱P字典序地小于Q。同時(shí)規(guī)定?的字典序最小。

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

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

定理1[5]設(shè)K=(O,A,R)是一個(gè)背景，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)是一個(gè)背景，若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(?))開始查找下一個(gè)外延；(2)假設(shè)S是當(dāng)前外延；(3)根據(jù)定理2逐個(gè)尋找滿足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í)行過程，下面以兩個(gè)例子進(jìn)行說明。

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

初始時(shí)，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的下一個(gè)值(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})的下一個(gè)外延。

初始時(shí)，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 存在問題分析

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

(1)基于字典序求外延S的下一個(gè)外延時(shí)，對于每一個(gè)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)的時(shí)間復(fù)雜度為O(rknlog2n)，其中，r是重復(fù)求g(F)的次數(shù)，k是F中包含的元素?cái)?shù)量，nlog2n是兩個(gè)集合求交集的時(shí)間復(fù)雜度。

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

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

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

3 改進(jìn)算法INCA

3.1 改進(jìn)思路

(1)針對同一個(gè)F值多次重復(fù)求g(F)的問題，通過增加一個(gè)Hash表用以消除重復(fù)計(jì)算問題。其主要方法為：對于首次出現(xiàn)的F值，將F和F中屬性集合對應(yīng)的最大對象集合(g(F)二元組(F,g(F)))存儲(chǔ)到一個(gè)Hash表中。當(dāng)F重復(fù)出現(xiàn)時(shí)，直接取出其對應(yīng)的g(F)值可避免g(F)的重復(fù)計(jì)算。本文采用Python作為兩個(gè)算法的實(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)算時(shí)間復(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次，目前已知方法中，求解兩個(gè)無序集合交集的時(shí)間復(fù)雜度為O(nlog2n)；而采用元素過濾的方法，只需對S進(jìn)行一趟掃描即可得到S中小于i的元素集合為{2,3}，其時(shí)間復(fù)雜度為O(n)。因此，S∩{1,…,i-1}和T∩{1,…,i-1}都可以根據(jù)此方法改進(jìn)，以提高閉包正規(guī)性判斷條件的求解效率。

(3)對于S∩{1,…,i-1}與T∩{1,…,i-1}的等價(jià)判斷問題，采用下述方法進(jìn)行改進(jìn)：令P=S∩{1,…,i-1}，Q=T∩{1,…,i-1}，若|P|≠|(zhì)Q|，則集合P和Q必然不等價(jià)。利用兩個(gè)集合的長度可以快速排除大量P和Q不相等的情況。求集合長度的時(shí)間復(fù)雜度為O(n)，而判斷集合等價(jià)的時(shí)間復(fù)雜度為O(nlog2n),所以上述通過判斷集合長度相等的措施可有效降低判斷集合等價(jià)的時(shí)間開支。若|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，初始化時(shí)以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é)果分析

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

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

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

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

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

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

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

由表4可以看出，兩個(gè)算法在所有背景上得到的概念數(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個(gè)背景的屬性數(shù)量，|O|對應(yīng)Ds2中10個(gè)背景的對象數(shù)量，f對應(yīng)Ds3中7個(gè)背景的屬性填充率。

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

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

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

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

對比圖1和圖2可知，兩種算法在數(shù)據(jù)集Ds1和Ds2上生成的概念數(shù)量雖然一樣，但運(yùn)行時(shí)間存在很大差異，即NextClosure算法和INCA算法在數(shù)據(jù)集Ds2的運(yùn)行時(shí)間大幅低于在數(shù)據(jù)集Ds1的運(yùn)行時(shí)間。例如，NextClosure在Ds1中的第10個(gè)背景(|O|=100，|A|=1 000)上的平均運(yùn)行時(shí)間約為960 s(INCA的平均運(yùn)行時(shí)間約為811 s)，而在Ds2的第10個(gè)背景(|O|=1 000，|A|=100)上的運(yùn)行時(shí)間約為125 s(INCA的平均運(yùn)行時(shí)間約為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í)間都隨背景屬性填充數(shù)量的增加而快速增加，但I(xiàn)NCA算法的運(yùn)行時(shí)間顯著優(yōu)于NextClosure算法。經(jīng)計(jì)算，INCA算法的運(yùn)行時(shí)間比NextClosure算法平均降低了20.3%。

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

5 結(jié)語

實(shí)驗(yàn)表明，本文提出的INCA算法在生成概念的效率上明顯優(yōu)于NextClosure算法。在三類不同類型數(shù)據(jù)集的背景上，INCA算法的平均運(yùn)行時(shí)間比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)用價(jià)值，如對于|O|和|A|差異較大的背景，若|O|>|A|，則可將該背景轉(zhuǎn)置后使用INCA算法生成以屬性集合為外延、以對象集合為內(nèi)涵的概念(稱為屬性概念)，再將屬性概念中的外延與內(nèi)涵交換，就可以得到以對象集合為外延、以屬性集合為內(nèi)涵的概念(稱為概念屬性)。今后的研究將根據(jù)概念生成過程中的相關(guān)信息探究概念間的層次結(jié)構(gòu)，在生成概念的同時(shí)構(gòu)建出概念格。