林志鴻，王李進，吳清壽

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

形式概念分析 (formal concept analysis，F(xiàn)CA)是Wille[1]提出的用于描述對象與屬性之間關(guān)系的數(shù)學(xué)理論，其中概念的生成和概念間的關(guān)系構(gòu)建是熱點的研究問題。概念能夠反映對象集合和屬性集合的最大對應(yīng)關(guān)系，可用于有效表達具有不同屬性集合所對應(yīng)的對象聚合情況。概念的這種特性在不同領(lǐng)域得到較為廣泛的應(yīng)用，如文本挖掘[2]，知識表示度量[3]，關(guān)聯(lián)規(guī)則研究[4]和大規(guī)模全局協(xié)同進化優(yōu)化[5]等。

已有的概念生成算法中，經(jīng)典的算法有Ganter 等[6]提出的基于閉包算子擴展求全部概念的NextClosure算法和Godin 等[7]提出的漸進式概念生成算法等。近幾年，研究人員提出一些新的概念格構(gòu)建方法，如竇林立等[8]提出的利用極大完全子圖及其導(dǎo)出子圖生成概念格的方法，為概念構(gòu)造提供新的思路。蔡勇等[9]根據(jù)概念外延長度將概念分層，進而實現(xiàn)分層并行搜索概念的父子節(jié)點，提高概念構(gòu)建速度。Zhang 等[10]提出FastAddExtent 算法，其通過減少概念之間的無效比較實現(xiàn)概念格的快速構(gòu)建。

在離散屬性的數(shù)據(jù)集上，廣義后綴樹有著廣泛的應(yīng)用，如文本檢索、信息聚類、網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)等[11,12]。廣義后綴樹的構(gòu)造方法較為成熟，具有線性的時間復(fù)雜度[13]，可有效提高算法的整體效率。如鄒凌君等[11]用廣義后綴樹提取出完全二分團，基于完全二分團實現(xiàn)二分網(wǎng)絡(luò)的社區(qū)劃分，算法具有較好的運行效率。

提出一種基于廣義后綴樹的概念生成算法(generalized suffix tree based concept generation algorithm，GSTCG)，首先利用Ukkonen 算法[13]將對象的屬性及其后綴序列構(gòu)建為廣義后綴樹，再利用相關(guān)規(guī)則得到候選的形式概念，經(jīng)過交叉擴展并刪除冗余的候選概念后得到形式背景的全部概念。

1 基礎(chǔ)理論

1.1 概念格基礎(chǔ)理論

定義1形式背景K 是一個三元組K=(O，A，R)，其中O 是對象集合，A 是屬性集合，R 是集合O 和A之間的關(guān)系，即R?O×A。通常，將形式背景簡稱為背景。對于o∈O，a∈A，(o，a)∈R 表示對象o 具有屬性a。背景可以用一個二維表表示，表中第一列和第一行分別是對象集合和屬性集合，行列交叉處的“×”表示該行對象具有該列屬性。

定義2對于背景K=(O，A，R)，若X?O，Y?A，定義操作為：

其中：f(X)表示X 中所有對象的共同屬性集合，g(Y)表示具有Y 中所有屬性的對象集合。

定義3對于背景K=(O，A，R)，若X?O，Y?A，且X，Y 滿足f(X)=Y，g(Y)=X，則二元組(X，Y)是一個形式概念(簡稱概念)，其中X 稱為概念的外延，Y 稱為概念的內(nèi)涵。

一個形式背景的示例如表1 所示，其中對象集合O={1，2，3，4，5}和屬性集合A={a，b，c，d}。

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

令X={3，4}，則f(X)={b，c}，令Y={b，c}，則g(Y)={3，4}。因為f(X)=Y，g(Y)=X，所以二元組({3，4}，{b，c})是一個概念。令X={2，3}，則f(X)={a，b}，令Y={a，b}，則g(Y)={2，3，5}。因 為f(X)=Y，g(Y)≠X，所以二元組({2，3}，{a，b})不是一個概念。

1.2 廣義后綴樹

表1 所示的形式背景中，對象o3的屬性序列為{a，b，c}，則其屬性序列有以下后綴：{b，c}，{c}。利用字典樹Trie 對以上屬性序列及其所有后綴進行存儲，則該樹稱為后綴樹。將一個背景中所有對象的屬性序列及其后綴組織為一棵Trie 樹，稱該樹為廣義后綴樹。本文中廣義后綴樹上的節(jié)點組織形式為二元組(對象集合，屬性集合)，其表示從根節(jié)點出發(fā)到達該節(jié)點的的對象集合，以及對象集合所對應(yīng)的屬性集合。顯然，廣義后綴樹中的節(jié)點的表示形式與形式概念有著極為密切的關(guān)系。

2 基于廣義后綴樹的概念生成算法

形式概念分析中的概念生成任務(wù)需要找到全部的概念，提出一種基于廣義后綴樹的概念生成算法，其主要思想為：利用高效率的后綴樹構(gòu)建算法快速得到候選概念，由候選概念擴展得到全部概念，再對擴展概念中的冗余概念進行處理。

步驟1由形式背景得到所有對象的屬性序列及其所有后綴。

以表1 中的形式背景為例，各對象(此處對象用oi表示)對應(yīng)的屬性序列及所有后綴如下。

步驟2根據(jù)步驟1 中的所有屬性序列及后綴構(gòu)建廣義后綴樹，如圖1 所示。

圖1 廣義后綴樹Fig.1 Generalized suffix tree

圖1 中廣義后綴樹的每條邊對應(yīng)一個屬性，每個節(jié)點表示一個候選概念。候選概念包括兩個部分，一個是從根節(jié)點到當(dāng)前節(jié)點路徑上的所有屬性，另一個是包含對應(yīng)屬性集合的對象集合。如節(jié)點n7，從根節(jié)點n0到n7的路徑上有兩條邊，邊所代表的屬性分別為和{c}，表示n7包含兩個屬性{b，c}。又因為對象o3中的屬性序列的后綴{b，c}和o4中的屬性序列{b，c，d}的前綴都是{b，c}，所以有n7=({3，4}:{c，d})，其中{3，4}表示對象o3和o4。

另外，由壓縮字典樹理論和形式概念的定義可知，當(dāng)具有父子關(guān)系的兩個節(jié)點都只有一個孩子節(jié)點且節(jié)點所代表的候選概念具有相同的對象集合，則可將這兩個節(jié)點壓縮為一個節(jié)點，且邊所代表的屬性為原來兩條邊的屬性的并集。

如節(jié)點n4和n5是父子節(jié)點，且都只有一個孩子節(jié)點，n4和n5所代表的候選概念的對象集合都是{2，3，5}，可將n4和n5兩個節(jié)點進行合并，合并后的候選概念為({2，3，5}:{a，b})。因圖1 中滿足節(jié)點壓縮的只有n4和n5，其他的都不滿足條件，所以將圖1 中節(jié)點壓縮后得到如圖2 所示的廣義后綴樹。

圖2 壓縮后的廣義后綴樹Fig.2 Compressed generalized suffix tree

圖2 中的廣義后綴樹包含9 個候選概念：n1=({1，2，3，4，5}:)；n2=({1}:{b，d})；n3=({1，4}:dnlrbh5)；n4=({2，3，5}:{a，b})；n5=({3}:{a，b，c})；n6=({3，4}:{c})；n7=({3，4}:{b，c})；n8=({4}:{c，d})；n9=({4}:{b，c，d})。

由廣義后綴樹產(chǎn)生的候選概念需要經(jīng)過系列處理后才能得到最終的概念。

規(guī)則1對于ni，nj∈N，i≠j，若f(ni)=f(nj)，則將ni與nj進行合并，合并后的候選概念nk=(f(ni)，g(ni)｜g(nj))。其中，N 是候選概念集合，f(ni)表示候選概念ni的對象集合，g(ni)表示ni的屬性集合。

步驟3根據(jù)規(guī)則1 合并對象集合相同的候選概念。

步驟2 產(chǎn)生的候選概念中，n6與n7的對象集合相同，但其對應(yīng)的屬性集合不相同。根據(jù)形式概念的定義，上述候選概念不可能同時存在，所以根據(jù)規(guī)則1進行合并處理。與上述情況相同的還有n8與n9。

經(jīng)過步驟3 得到的結(jié)果如下：

規(guī)則2對于ni，nj∈N，若f(ni)∩f(nj)≠φ，則(f(ni)∩f(nj):g(ni)∪g(nj))也是候選概念。若g(ni)∩g(nj)≠φ，則(f(ni)∪f(nj):g(ni)∩g(nj))也是候選概念。

步驟4根據(jù)規(guī)則2 擴展候選概念。

擴展后的候選概念集合如下：

規(guī)則2對候選概念集合進行擴展，但其中可能產(chǎn)生新的冗余候選概念，所以在擴展后需要利用規(guī)則3再次進行處理。

規(guī)則3對于ni，nj∈N，i≠j，若f(ni)?f(nj)且g(ni)?g(nj)記為ni?nj，稱ni是冗余候選概念，將其從N 中刪除。

步驟5根據(jù)規(guī)則3 刪除冗余候選概念。

步驟4 中的候選概念中，n8，n9，n10，n11?n1，n2?n5，根據(jù)規(guī)則3，刪除n2，n8，n9，n10和n11，得到的概念如下：

步驟6增加最大概念(O∶f(O)和最小概念(g(A)∶A)。

表1 中，O={1，2，3，4，5}，f(O)=，步驟5 中已存在對應(yīng)的最大概念，所以不用加入。又因為A={a，b，c，d}，g (A)=φ，步驟5 中的概念集合不包含(φ，{a，b，c，d})，將其加入概念集合，最終結(jié)果如下：

3 實驗結(jié)果與分析

為評估算法(GSTCG)的時間性能，將其和經(jīng)典算法NextClosure 算法進行對比仿真實驗。實驗軟硬件:Intel Core i7-8650U CPU，16 GB RAM，Windows 10 操作系統(tǒng)。算法采用Python3 實現(xiàn)。兩個算法在所有背景上都分別運行15 次，實驗結(jié)果取15 次運行時間的平均值。

3.1 數(shù)據(jù)集

實驗數(shù)據(jù)集采用人工生成的隨機數(shù)據(jù)集，用3 個參數(shù)對數(shù)據(jù)集進行調(diào)節(jié)，第一個參數(shù)是背景中所包含的對象數(shù)|O|，第二個參數(shù)是背景中屬性集合的長度|A|，第三個參數(shù)是屬性的填充率f，f∈(0，1)。這里規(guī)定每個對象實際擁有的屬性數(shù)量相同，即每個對象有|A|×f 個屬性。

實驗數(shù)據(jù)集有兩組，第一組(Bg1)的參數(shù)設(shè)置為|O|=100～600，每次增加100 個對象，|A|=60，f=0.15，Bg1 中共包含6 個背景。第二組(Bg2)的參數(shù)設(shè)置為|O|=50，|A|=200，f=0.05～0.3，f 的值每次增加0.05，Bg2 中也包含6 個背景。

3.2 實驗仿真

GSTCG 算法和NextClosure(簡稱NC)算法在數(shù)據(jù)集Bg1 和Bg2 上的實驗結(jié)果如表2、圖3 和圖4 所示。其中表2 是兩個算法在12 個形式背景上生成的概念數(shù)量情況，結(jié)果顯示兩個算法生成的概念數(shù)量一致，證明GSTCG 算法的正確性。

圖3 背景1 上的實驗結(jié)果Fig.3 Results on context 1

圖4 在背景2 上的實驗結(jié)果Fig.4 Results on context 2

表2 概念數(shù)量Tab.2 Number of concepts

圖3 是兩個算法在Bg1 的6 個背景上的運行時間，圖4 是兩個算法在Bg2 的6 個背景上的運行時間。

圖3 和圖4 的結(jié)果顯示，GSTCG 算法在所有12個背景上的運行時間都少于NextClosure 算法。在Bg1和Bg2 數(shù)據(jù)集上，GSTCG 算法的平均運行時間分別比NextClosure 算法減少33%和43%。

分析其原因，NextClosure 算法需要逐個生成正規(guī)閉包，在查找下一個正規(guī)閉包的過程中，重復(fù)計算大量無效的閉包，這導(dǎo)致NextClosure 算法運行效率較差。GSTCG 算法中，構(gòu)建后綴樹的時間復(fù)雜度是線性的，算法主要的時間開支是步驟4 中的慨念擴展。所以，GSTCG 算法具有比NextClousure 算法更好的時間性能。

4 結(jié)語

提出一種新的概念生成算法，其利用廣義后綴樹生成候選概念，對候選概念進行擴展后刪除冗余概念，最終得到形式背景的全部概念。實驗結(jié)果表明，所提算法能正確生成全部概念，且比經(jīng)典的NextClosure 算法具有更好的時間性能。下一步的研究中，我們將對廣義后綴樹生成的候選概念間的關(guān)系和候選概念擴展方法進行深入分析，以期更好地提高算法的效率。