兩種概念生成算法的比較分析與實驗仿真

吳清壽,何清恒,劉書陽

(1.武夷學院數學與計算機學院,福建 武夷山 354300;2.福建省茶產業大數據應用與智能化重點實驗室,福建 武夷山 354300)

0 引言

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

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

以上兩種經典算法常用于作為新提出算法的對比算法或改進依據,但在相關文獻中沒有得到深入全面的分析。本文擬對兩種算法進行較為全面的分析,闡明基本原理,給出算法步驟,并結合實例分析算法的優缺點,最后進行實驗仿真,為后續的概念生成算法研究提供可靠的理論依據。

1 基本理論

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

一個背景的例子如表1所示。第一列是對象集合,第一行是屬性集合,行列交叉處的“×”表示該行對象具有該列對應的屬性,如第三行,對象3具有屬性a、b、d和f,將這種對應關系記為二元組({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的內涵。

如有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}是內涵。

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})一定是一個概念。

根據定理1,只要找到所有的內涵或所有的外延,則可找到所有的概念。要找到所有的外延,只需對M的所有子集進行窮舉即可,進而生成所有概念。然而,對M的子集進行窮舉的時間復雜度是O(2n),其中,n是屬性數量。顯然,窮舉法在屬性數量較大的情況下是難以實現的。為了找到全部未出現的外延,對于每一個可能的外延都需要判斷其是否已經出現在已求得的外延集合中,需要設計一種合理的方法。因此,從概念的定義出發,設計以下步驟:設置一個初始概念(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中。重復以上過程,直到所有屬性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是由當前屬性前面的其他屬性所生成的外延集合,但在判斷s∈E時,需要對由當前屬性生成的外延也進行判斷,所以用T保存E中的外延,并在有新的外延生成時將其加入T中,當前屬性處理完畢后,再將T中的外延更新到E中,作為下一個屬性的前置外延。

2.2 實例分析

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

表2 CGA算法生成全部概念

以從屬性e生成概念的計算過程為例進行說明。在對屬性e進行處理之前,外延表E中已有8個外延,同時將E中外延保存到T中。首先計算g(e)={2,5,6},再計算s=g(e)∩e1={2,5,6},因為s?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進行交運算得到的{2,5,6}、{6}、{5,6}和?都已在T中,沒有產生新的外延。至此,由屬性e生成概念的操作結束,進行下一個屬性的操作。

3 Nextclosure算法

3.1 算法理論

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

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

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

根據以上原理,Nextclosure算法的主要步驟如下:首先設一個最小外延E=?及最小概念(?,U),根據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:

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

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 實例分析

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

表3 NextClosure算法生成全部概念

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

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

當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

當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

當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 兩種算法的對比分析

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

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

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

5 實驗仿真

為了驗證兩種算法的時間性能,下面對兩種算法進行實驗仿真。實驗環境:Intel Core i7-8650U CPU,16 G RAM,Windows10操作系統。算法均采用Python語言實現。

5.1 實驗環境與數據集

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

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

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

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

以上兩組數據集的參數設置主要考慮以下實驗場景:Bg1用于測試算法對|U|增長下的適應性,Bg2用于測試算法對|M|變化的適應性。其中,Bg2是對Bg1中背景的轉置,兩者生成的概念數量一致,但每個概念中的內涵和外延是調換位置的。

5.2 實驗仿真及結果分析

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

首先,兩種算法在兩個背景上生成的數量是一致的。因為兩個背景中包含的概念數量相同,這里只列出在Bg1上的概念數量,結果如表4所示。

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

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

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

表5 兩個算法在Bg1上的迭代次數

表6 兩個算法在Bg2上的迭代次數

表5為兩種算法在Bg1上的實驗結果,其中|M|很小,而|U|不斷增大,所以CGA算法的計算次數少,而NextClosure算法的計算次數多,且隨著|U|的增大,NextClosure算法的計算次數快速增加。表6中呈現的實驗結果剛好與表5相反,這是因為背景轉置后,Bg2中|U|很小,而|M|不斷增大引起的。可見,CGA算法和NextClosure算法兩者適應的背景是不一樣的。

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

圖1 兩個算法在Bg1上的運行時間

圖2 兩個算法在Bg2上的運行時間

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

6 結語

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