兩種概念生成算法的比較分析與實(shí)驗(yàn)仿真

吳清壽,何清恒,劉書陽

(1.武夷學(xué)院數(shù)學(xué)與計算機(jī)學(xué)院,福建 武夷山 354300;2.福建省茶產(chǎn)業(yè)大數(shù)據(jù)應(yīng)用與智能化重點(diǎn)實(shí)驗(yàn)室,福建 武夷山 354300)

0 引言

形式概念分析(Formal Concept Analysis,FCA)[1]已廣泛應(yīng)用于各種數(shù)據(jù)分析任務(wù),如文本挖掘[2]、復(fù)雜網(wǎng)絡(luò)分析[3]等。關(guān)于FCA的研究中,概念生成及概念間關(guān)系構(gòu)建是各項研究工作的基礎(chǔ),得到研究人員的長期關(guān)注[4-5]。從形式背景中生成概念,研究人員已提出了很多算法,主要包括批處理[5-6]和增量式[7-8]兩類不同的處理方法,增量式構(gòu)建概念格方法主要研究節(jié)點(diǎn)間關(guān)系的快速查找,批處理的方法則側(cè)重于從背景中快速生成所有的概念內(nèi)涵或外延。不管是哪一類概念生成算法,其首要任務(wù)是保證算法的正確性,即能對一個形式背景生成全部的概念,另一個重要任務(wù)就是提出合適的規(guī)則,以期加快概念生成的速度和概念格中概念關(guān)系的構(gòu)建。

批處理方法中,GANTER[6]提出的NextClosure算法是一種基于閉包運(yùn)算的方法,從最小外延(一個閉包)開始,基于字典序找到大于當(dāng)前閉包的最小閉包,即另一個外延,直到找到最大的閉包(所有屬性的集合)為止。NextClosure算法具有較好的時間性能,得到了研究人員的關(guān)注,如孫斌斌[9]在NextClosure算法的基礎(chǔ)上提出Tri-NextClosure算法,用于對三維數(shù)據(jù)進(jìn)行數(shù)據(jù)分析,林志鴻等[10]對NextClousea算法在實(shí)現(xiàn)方面存在的問題進(jìn)行了討論并提出改進(jìn)措施。另一種基于基本定義和基本原理導(dǎo)出的概念生成算法[11]也具有一定的代表性,其主要原理是:若X∈M,則(g(X),f(g(X)))一定是概念,其中M是形式背景的屬性集合。龐智恒等[12]運(yùn)用與上述方法相似的原理,逐層生成概念,同時構(gòu)建了格節(jié)點(diǎn)間的偏序關(guān)系。吳清壽等[5]將每個屬性導(dǎo)出的概念進(jìn)行劃分,減少了無效的搜索次數(shù),使算法具有較高的運(yùn)行效率。

以上兩種經(jīng)典算法常用于作為新提出算法的對比算法或改進(jìn)依據(jù),但在相關(guān)文獻(xiàn)中沒有得到深入全面的分析。本文擬對兩種算法進(jìn)行較為全面的分析,闡明基本原理,給出算法步驟,并結(jié)合實(shí)例分析算法的優(yōu)缺點(diǎn),最后進(jìn)行實(shí)驗(yàn)仿真,為后續(xù)的概念生成算法研究提供可靠的理論依據(jù)。

1 基本理論

定義1[11]設(shè)U是對象的集合,M是屬性的集合,R是集合U和M之間的關(guān)系,則三元組K=(U,M,R)是一個形式背景(簡稱背景)。對于u∈U,m∈M,(u,m)∈R表示對象u具有屬性m。通常,用矩陣表示背景,其中,每一行表示一個對象,每一列表示一個屬性。

一個背景的例子如表1所示。第一列是對象集合,第一行是屬性集合,行列交叉處的“×”表示該行對象具有該列對應(yīng)的屬性,如第三行,對象3具有屬性a、b、d和f,將這種對應(yīng)關(guān)系記為二元組({3},{a,b,d,f})。

表1 形式背景示例

定義2[11]對于背景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}。若X,Y滿足f(X)=Y,g(Y)=X,則二元組(X,Y)是一個形式概念(簡稱概念),記為c,其中X為概念c的外延,Y為概念c的內(nèi)涵。

如有X={2,5},則f(X)表示對象2和對象5共同具有的屬性集合,由表1可知,f(X)={a,e}。若有Y={a,e},則g(Y)表示具有屬性a和e的對象集合,所以g(Y)={2,5,6},這里f(X)≠g(Y),則二元組({2,5},{a,e})不是概念。若X={2,5,6},Y=({a,e},f(X)=g(Y),則二元組({2,5,6},{a,e})是一個概念,{2,5,6}是外延,{a,e}是內(nèi)涵。

2 基于基本定義的概念生成算法

定理1[11]對于背景K=(U,M,R),若P∈U,則(g(f(P)),f(P))一定是概念;若Q∈M,則(g(Q),f(g(Q)))也一定是概念。

如有P={1},f(P)={a,f},g(f(P))={1,3},則({1,3},{a,f})一定是一個概念。

根據(jù)定理1,只要找到所有的內(nèi)涵或所有的外延,則可找到所有的概念。要找到所有的外延,只需對M的所有子集進(jìn)行窮舉即可,進(jìn)而生成所有概念。然而,對M的子集進(jìn)行窮舉的時間復(fù)雜度是O(2n),其中,n是屬性數(shù)量。顯然,窮舉法在屬性數(shù)量較大的情況下是難以實(shí)現(xiàn)的。為了找到全部未出現(xiàn)的外延,對于每一個可能的外延都需要判斷其是否已經(jīng)出現(xiàn)在已求得的外延集合中,需要設(shè)計一種合理的方法。因此,從概念的定義出發(fā),設(shè)計以下步驟:設(shè)置一個初始概念(U,?),將初始概念加入概念表C中,將U加入外延表E中。對于?m∈M,首先計算g(m),再逐一計算s=g(m)∩ei,其中ei∈E。若s?E,則s是一個外延,將s加入E中,計算f(s),將(s,f(s))加入概念表C中。重復(fù)以上過程,直到所有屬性m都處理完畢。為方便敘述,將以上算法簡記為CGA(Concept Generation Algorithm)。

2.1 算法描述

具體的計算過程如算法1所示。

算法1:CGA

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

輸出:所有概念集合C

1C←{(U,?)}

2E←{U}

3 for eachm∈Mdo:

4T←E

5 for eache∈Edo:

6s←g(m)∩e

7 ifs?Tthen:

8T←T∪s

9C←C∪(s,f(s))

10 endif

11 endfor

12E←T

13 endfor

14 returnC

算法1中,遍歷E時,E是由當(dāng)前屬性前面的其他屬性所生成的外延集合,但在判斷s∈E時,需要對由當(dāng)前屬性生成的外延也進(jìn)行判斷,所以用T保存E中的外延,并在有新的外延生成時將其加入T中,當(dāng)前屬性處理完畢后,再將T中的外延更新到E中,作為下一個屬性的前置外延。

2.2 實(shí)例分析

根據(jù)算法1,首先設(shè)置兩個集合C和E,分別用于存放已生成的概念和外延,再根據(jù)算法逐步查找外延,從表1的背景生成全部概念的過程如表2所示。

表2 CGA算法生成全部概念

以從屬性e生成概念的計算過程為例進(jìn)行說明。在對屬性e進(jìn)行處理之前,外延表E中已有8個外延,同時將E中外延保存到T中。首先計算g(e)={2,5,6},再計算s=g(e)∩e1={2,5,6},因?yàn)閟?T,將s加入T中,此時T中的外延集合為{{1,2,3,4,5,6},{1,2,3,5,6},{3,4,6},{3,6},{5,6},{6},{3},?,{2,5,6}}。然后,g(e)與e2～e8進(jìn)行交運(yùn)算得到的{2,5,6}、{6}、{5,6}和?都已在T中,沒有產(chǎn)生新的外延。至此,由屬性e生成概念的操作結(jié)束,進(jìn)行下一個屬性的操作。

3 Nextclosure算法

3.1 算法理論

定義3[11]對于背景K=(U,M,R),有X,Y?U,X和Y中的元素按升序排序。對X和Y中的元素從第1個元素開始比較,若首次出現(xiàn)不相等元素的位置為i,且Xi>Yi,則稱X字典序地小于Y。這里規(guī)定?的字典序最小。

定義4[11]對于X,Y?U,i∈U,將X

定理2[11]對于X?O,字典序地大于X的最小外延是X?i,i是滿足X

根據(jù)以上原理,Nextclosure算法的主要步驟如下:首先設(shè)一個最小外延E=?及最小概念(?,U),根據(jù)E

3.2 算法描述

算法2:NextClousure

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

輸出:所有概念集合C

1C←{(?,U)}

2E←?

3U’←sort(U,DESC)

4 whileE≠Udo:

5I←U’-E

6 for eachi∈Ido:

酒精性肝病的治療方面，馬薩諸塞大學(xué)醫(yī)學(xué)院Szabo（摘要LB-1）一項多中心隨機(jī)雙盲安慰劑對照的臨床試驗(yàn)報道了IL-1受體激動劑聯(lián)合己酮可可堿和鋅治療重癥酒精性肝炎28 d，終點(diǎn)指標(biāo)為30 d、90 d及180 d的病死率，與甲潑尼龍（32 mg每日口服，28 d）比較，短期療效相近，長期療效新的治療更有優(yōu)勢。

7X←E∩{1,…,i-1}∪{i}

8T←f(X)

9F←g(T)

10 ifE∩{1,…,i-1}=F∩{1,…,i-1} then:

11E←F

12C←C∪(F,T)

13 break

14 endif

16 endwhile

17 returnC

3.3 實(shí)例分析

根據(jù)算法2,首先設(shè)置一個最小概念(?∶{a,b,c,d,e,f}),再根據(jù)S

表3 NextClosure算法生成全部概念

下面以從概念({2,5,6}∶{a,e})產(chǎn)生下一個概念的計算過程為例進(jìn)行說明。

當(dāng)生成概念({2,5,6}∶{a,e})后,開始生成下一個概念。首先需要確定i的取值范圍,根據(jù)定義4,i∈U-E={1,2,3,4,5,6}- {2,5,6}={4,3,1},所以從i=4開始。

當(dāng)i=4時,首先求E?i。令X=E∩ {1,…,i-1}∪{i}={2,5,6}∩{1,2,3}∪{4}={2,4},f(X)=?,

E?i=g(f(X))={1,2,3,4,5,6}。再判斷E

當(dāng)i=3時,首先求E?i。令X=E∩ {1,…,i-1}∪{i}={2,5,6}∩ {1,2}∪{3}={2,3},f(X)={a},E?i=g(f(X))= {1,2,3,5,6}。再判斷E

E?i∩{1,…,i-1}= {1,2,3,5,6}∩{1,2}={1,2},E?i∩{1,…,i-1}≠E∩{1,…,i-1},即E

當(dāng)i=1時,首先求E?i。令X=E∩{1,…,i-1}∪ {i}={2,5,6}∩?∪{1}={1},f(X)={a,f},E?i=g(f(X))= {1,3}。再判斷E

4 兩種算法的對比分析

通過對以上兩個算法在同一背景上生成概念過程進(jìn)行分析,可知兩個算法在方法和步驟上都存在較大的差異,這些差異對算法的運(yùn)行效率有較大的影響。下面對兩個算法的區(qū)別進(jìn)行討論。

CGA算法中,每一趟判斷需要的集合操作有:計算g(m),因?yàn)閙是單個屬性,求解g(m)的時間基本可以忽略。求解s需要一次交集運(yùn)算g(m)∩ei,若s不是外延,則無需計算f(s),否則需要計算f(s),這里計算f(s)的次數(shù)與概念數(shù)量相同。由上述算法步驟及實(shí)例分析過程可知,CGA算法思想簡單,易于實(shí)現(xiàn)。但該算法也存在以下問題:(1)CGA算法的運(yùn)行效率與屬性數(shù)量緊密相關(guān),每增加一個屬性,就需要多一輪概念生成的求解過程,需要將新的屬性對應(yīng)的對象集合與已生成的全部概念外延進(jìn)行逐一比較,越處在表格后端的屬性,需要比對的次數(shù)就越多;(2)在生成概念的過程中存在較多的冗余計算,如對于屬性e的計算中,只生成1個概念,而其余的7次計算產(chǎn)生的結(jié)果都是與已有外延重復(fù)的。

Nextclosure算法存在的一個問題是在生成下一個概念的過程中,可能需要多次改變i值才能找到滿足條件的外延,即對于對象數(shù)量多的背景,其運(yùn)行效率可能較差。另外,Nextclosure算法的一趟求解需要大量的集合操作,從當(dāng)前概念出發(fā),首先需要進(jìn)行一次差集運(yùn)算U’-E,求解X需要一次交集運(yùn)算E∩ {1,…,i-1},然后進(jìn)行f(X)(記為T)和g(T)操作,最后判斷E

5 實(shí)驗(yàn)仿真

為了驗(yàn)證兩種算法的時間性能,下面對兩種算法進(jìn)行實(shí)驗(yàn)仿真。實(shí)驗(yàn)環(huán)境:Intel Core i7-8650U CPU,16 G RAM,Windows10操作系統(tǒng)。算法均采用Python語言實(shí)現(xiàn)。

5.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集采用人工生成的形式背景,生成背景的主要參數(shù)包括:對象數(shù)量|U|、屬性數(shù)量|M|和每個對象的平均屬性填充率f。

為了讓人工生成的背景更加接近真實(shí)場景,每行填充的屬性數(shù)量按高斯分布生成,填充數(shù)量的均值μ=|M|×f,標(biāo)準(zhǔn)差δ=μ/2,最小值為1。兩組數(shù)據(jù)集的參數(shù)設(shè)定如下:

Bg1:|U|=500～2 500,|M|=50,f=0.1;

Bg2:|U|=50,|M|=500～2 500,f=0.1;

以上兩組數(shù)據(jù)集的參數(shù)設(shè)置主要考慮以下實(shí)驗(yàn)場景:Bg1用于測試算法對|U|增長下的適應(yīng)性,Bg2用于測試算法對|M|變化的適應(yīng)性。其中,Bg2是對Bg1中背景的轉(zhuǎn)置,兩者生成的概念數(shù)量一致,但每個概念中的內(nèi)涵和外延是調(diào)換位置的。

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

通過實(shí)驗(yàn)對以下三個方面進(jìn)行比較:一是生成的概念數(shù)量;二是生成概念過程中的總迭代次數(shù);三是在不同背景上的運(yùn)行時間。

首先,兩種算法在兩個背景上生成的數(shù)量是一致的。因?yàn)閮蓚€背景中包含的概念數(shù)量相同,這里只列出在Bg1上的概念數(shù)量,結(jié)果如表4所示。

表4 兩個算法在Bg1上得到的概念數(shù)量

表4中,概念的數(shù)量總體上是隨著|U|的增大而增加的,在|U|值為700和800時概念數(shù)量有所下降,主要是由背景中屬性填充的隨機(jī)性導(dǎo)致的。

其次,對兩個算法中求解外延的迭代次數(shù)進(jìn)行比較,具體地,在CGA算法中對s=g(m)∩ei的計算次數(shù)進(jìn)行統(tǒng)計,在NextClosure算法中對每個E

表5 兩個算法在Bg1上的迭代次數(shù)

表6 兩個算法在Bg2上的迭代次數(shù)

表5為兩種算法在Bg1上的實(shí)驗(yàn)結(jié)果,其中|M|很小,而|U|不斷增大,所以CGA算法的計算次數(shù)少,而NextClosure算法的計算次數(shù)多,且隨著|U|的增大,NextClosure算法的計算次數(shù)快速增加。表6中呈現(xiàn)的實(shí)驗(yàn)結(jié)果剛好與表5相反,這是因?yàn)楸尘稗D(zhuǎn)置后,Bg2中|U|很小,而|M|不斷增大引起的。可見,CGA算法和NextClosure算法兩者適應(yīng)的背景是不一樣的。

最后,對兩個算法的運(yùn)行時間進(jìn)行對比,如圖1和圖2所示。在Bg1上,CGA算法對所有的背景都在1 s內(nèi)完成計算,而NextClosure算法需要大量的計算時間;在Bg2上,兩種算法的運(yùn)行時間較為接近,但CGA算法仍然比NextClosure算法具有時間性能上的優(yōu)勢。

圖1 兩個算法在Bg1上的運(yùn)行時間

圖2 兩個算法在Bg2上的運(yùn)行時間

以上實(shí)驗(yàn)結(jié)果表明,CGA算法在時間性能上優(yōu)于NextClosure算法,尤其是在對象數(shù)量多而屬性數(shù)量少的背景上,CGA算法的優(yōu)勢更加明顯。兩種算法的運(yùn)行時間都隨著尋找概念外延的次數(shù)增加而相應(yīng)增加,但影響算法時間性能的最主要因素是尋找一個外延所需的集合運(yùn)算次數(shù)。由表6可見,在同一背景上(如|M|=1 000),CGA算法運(yùn)算次數(shù)是NextClosure算法運(yùn)算次數(shù)的40倍,但CGA算法總體運(yùn)行時間仍少于NextClosure算法總體運(yùn)行時間,主要原因是CGA算法中集合操作次數(shù)少,大大節(jié)省了一次查找外延的時間,所以CGA算法總體上有更好的時間優(yōu)勢。

6 結(jié)語

本文介紹了兩種經(jīng)典的概念生成算法,從算法原理、算法步驟和實(shí)例等方面進(jìn)行了對比分析,并用Python語言實(shí)現(xiàn)了兩種算法,在兩類數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)仿真。結(jié)果表明,要提高概念生成算法的運(yùn)行效率,首要任務(wù)是減少概念外延生成過程中的交集運(yùn)算,然后進(jìn)一步尋找規(guī)律,減少無用運(yùn)算次數(shù)。下一步的工作中,進(jìn)一步提高概念生成效率將是我們研究的重點(diǎn)。