基于NextClosure改进的概念生成算法

林志鸿，吴清寿

(1.湄洲湾职业技术学院信息工程系，福建 莆田 351111；2.武夷学院数学与计算机学院，福建 武夷山 354300；3.智慧农林福建省高校重点实验室(福建农林大学)，福建 福州 350002)

0 引言

概念是形式概念分析(formal concept analysis，FCA)[1]理论的核心数据结构，它反映的是形式背景中对象与属性之间的最大组合状态。目前，概念已在复杂网络分析[2]、关联分析[3]和文本挖掘[4]等领域得到了广泛应用。1999年，GANTER等[5]提出了一种基于当前闭包求所有正规闭包的算法——NextClosure算法，该算法能够生成背景的全部概念，且无需全局搜索匹配其他概念。NextClosure算法对于属性数量多而对象数量少的背景具有较好的适应性，但在判断闭包的正规性时，因需要进行大量的交集运算,所以时间复杂度较高。2004年，卢明等[6]将搜索空间组织为前缀树，根据闭包空间的正规性判定条件，对前缀树进行剪枝以降低搜索复杂度，提高了算法的时间性能。2005年，齐红等[7]提出一种基于搜索空间划分的概念生成方法，该算法将搜索空间划分为子空间，通过有效性判断过滤不能生成正规闭包的子空间，提高了概念生成效率。在概念格构建的研究中，增量式方法得到学者的较多关注，其中,AddIntent算法[8]是增量式方法的一种典型代表，它能够生成全部概念并构建出概念之间的层次关系。 2011年，LÜ等[9]提出了一种改进的AddIntent算法，该算法通过增加字段来实现快速定位新概念。2019年，ZHANG等[10]在AddIntent的基础上提出了FastAddExtent算法，该算法通过减少概念之间的无效比较实现概念格的快速构建。针对NextClosure算法中存在的冗余操作和交集运算时间复杂度较大的问题，本文基于哈希表和集合元素过滤的方法提出了一种改进的NextClosure算法——INCA算法(Improved NextClosure Algorithm)，并通过仿真实验证明了INCA算法的有效性。

1 基础理论

定义1[5]设O是对象的集合，A是属性的集合，R是集合O和A之间的关系，则三元组K=(O,A,R)是一个形式背景(简称背景)。对于o∈O，a∈A，(o,a)∈R表示对象o具有属性a，背景中对应的行列交叉处的值为1，(o,a)∉R表示对象o不具有属性a，背景中对应的值为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中对应位置处的值为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是概念的内涵。

对于表1中的背景，若X={3,4}，Y={b,c}，则二元组({3,4},{b,c})是一个概念，因为f(X)={b,c}，g(Y)={3,4}，满足f(X)=Y，g(Y)=X。

若X={1,2}，Y={b}，则({1,2},{b})不是一个概念，因为f(X)={b}，g(Y)={1,2,3,4,5}，f(X)=Y，而g(Y)≠X。

定义3[5]对于P,Q⊆O，且P和Q中的元素已按从小到大排序。对P和Q中的元素从左边第1个元素开始比较，若第1次出现不相等的元素位置为i，且Pi>Qi，则称P字典序地小于Q。同时规定∅的字典序最小。

若P={2,4,5}，Q={2,3,4}，则当i=2(i从1开始)时，P2>Q2。由此可知，P字典序地小于Q。

定义4[5]设S,T⊆O，i∈O，并将S

定理1[5]设K=(O,A,R)是一个背景，X,X1,X2∈O，Y,Y1,Y2∈A，则有以下性质：

(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，关于字典序地大于S的最小外延是S⊕i，i是满足S

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

以上定理的证明见文献[5]，本文在此省略。

2 NextClosure算法及问题分析

2.1 NextClosure算法

由定义4和定理2可得到NextClosure算法的主要步骤：(1)从最小概念(g(f(∅)),f(∅))开始查找下一个外延；(2)假设S是当前外延；(3)根据定理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中的元素进行降序排列，以方便按字典序查找满足S

2.2 实例分析

利用NextClosure算法生成概念的过程如表2所示(以表1中的背景为例)。根据算法1中的第2行，设置初始概念为(g(f(∅)),f(∅))，其中，f(∅)={a,b,c,d}，g(f(∅))=∅。

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

为了更好地说明NextClosure算法的执行过程，下面以两个例子进行说明。

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

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

i的值从5开始。令u=S∩{1,…,i-1}∪{i}={3}∩{1,2,3,4}∪{5}={3,5}。从表1的背景可知，F=f(u)=f({3,5})={a,b}，T=g(F)={2,3,5}。根据定义4，S

取i的下一个值(i=4)。因u={3}∩{1,2,3}∪{4}={3,4}，F=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={b}，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={b}，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={b}，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 存在问题分析

由上述两个实例的计算过程可知，NextClosure算法在以下步骤中存在大量的重复运算和低效率操作，进而影响算法的运行速度，并且形式背景规模越大，其对算法的运行速度影响越大。

(1)基于字典序求外延S的下一个外延时，对于每一个i，需重新计算F和T。在表2所示的概念生成过程中，第3、7、9、11、12、13行的F={b}重复6次，则g(F)也需要重复计算6次，第1、5、8行中的F={a,b}重复3次，其对应的g(F)也重复计算3次。求解g(F)的时间复杂度为O(rknlog2n)，其中，r是重复求g(F)的次数，k是F中包含的元素数量，nlog2n是两个集合求交集的时间复杂度。

(2)对于任意的一对S和i，算法1都要进行2次的S∩{1,…,i-1}(第8行和第11行)和1次的T∩{1,…,i-1}(第10行)运算。求解两个集合交集的时间复杂度为O(nlog2n)。

(3)对于任意的一对S和i，需要进行1次S∩{1,…,i-1}与T∩{1,…,i-1}的等价判断。集合等价判断的时间复杂度为O(nlog2n)。

(4)对于任意的一对S和i，需要进行1次的i∈T-S判断。i∈T-S判断的时间复杂度为O(nlog2n)。

3 改进算法INCA

3.1 改进思路

(1)针对同一个F值多次重复求g(F)的问题，通过增加一个Hash表用以消除重复计算问题。其主要方法为：对于首次出现的F值，将F和F中属性集合对应的最大对象集合(g(F)二元组(F,g(F)))存储到一个Hash表中。当F重复出现时，直接取出其对应的g(F)值可避免g(F)的重复计算。本文采用Python作为两个算法的实现语言，并采用Python语言中的字典(dict)类型实现消除上述重复计算g(F)的问题，即增加空字典H，通过get(F,0)函数查询F是否已在H中，若不存在，则将{F,g(F)}加入到H中，否则直接返回g(F)的值。

(2)针对交集运算时间复杂度较高的问题，本文采用元素过滤的方法提高其效率，具体操作如下：对于S∩{1,…,i-1}运算，注意到{1,…,i-1}包含了小于i的所有元素，因此该问题可以转换为求S中所有小于i的元素。如表2的第9行，S={2,3,5}，i=4，直接用交集方法求解S∩{1,…,i-1}，其结果为{2,3,5}∩{1,2,3,4}={2,3}，该过程需要对S重复扫描4次，目前已知方法中，求解两个无序集合交集的时间复杂度为O(nlog2n)；而采用元素过滤的方法，只需对S进行一趟扫描即可得到S中小于i的元素集合为{2,3}，其时间复杂度为O(n)。因此，S∩{1,…,i-1}和T∩{1,…,i-1}都可以根据此方法改进，以提高闭包正规性判断条件的求解效率。

(3)对于S∩{1,…,i-1}与T∩{1,…,i-1}的等价判断问题，采用下述方法进行改进：令P=S∩{1,…,i-1}，Q=T∩{1,…,i-1}，若|P|≠|Q|，则集合P和Q必然不等价。利用两个集合的长度可以快速排除大量P和Q不相等的情况。求集合长度的时间复杂度为O(n)，而判断集合等价的时间复杂度为O(nlog2n),所以上述通过判断集合长度相等的措施可有效降低判断集合等价的时间开支。若|P|=|Q|，将P建立为Hash表，将Q中的元素在Hash表中检测冲突，若存在不冲突的元素，则P≠Q，否则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))，根据定理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 改进算法

根据以上改进思路，本文提出的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|≠|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。根据改进思路(2)可知，第8、16行的filter函数从S中过滤出所有小于i的元素集合，代替了交集运算。根据改进思路(1)，第10～15行通过查询F是否在字典H中，若F已存在，则直接从字典H中取出F对应的T值，否则将F与对应的T组成的键值对{F,T}加入字典H中。第17、18行根据集合元素长度对S

4 实验仿真与结果分析

为了评估INCA算法和NextClosure算法的时间性能，对其进行仿真实验。实验环境：Intel Core i7-8650U CPU，16 G RAM，Windows 10操作系统，算法采用Python3.8。两个算法在所有背景上的都分别运行10次，实验结果取10次运行时间的平均值。

4.1 实验数据集

实验数据集采用人工数据集，数据集的大小和稠密程度由三个参数决定：背景的对象数量|O|，每个对象最大的属性数量|A|，每行属性的填充率f。实验数据集(Ds1、Ds2和Ds3)中的参数值设置如表3所示。Ds1包含10个背景，用于测试算法在|O|不变而|A|值逐渐增大时的时间性能。将Ds1中背景的对象与属性进行转置，得到Ds2。如Ds1中的第10个背景(|O|=100，|A|=1 000)，将其转置后，对应Ds2中的第10个背景(|O|=1 000，|A|=100)。同样地，Ds2中也包含10个背景，且10个背景|A|不变，而|O|逐渐增大，用于测试算法在|O|发生变化时的适应性。Ds3中包含7个背景，各个背景的|O|和|A|均不变，而属性填充率f逐渐变大(每次增加5%)，用于测试属性填充率变化对算法性能的影响。

表3 随机数据集参数值

4.2 实验仿真与分析

以表3中的27个背景对INCA算法和NextClosure算法生成的概念数量进行实验对比(表4)。

表4 两种算法生成的概念数量

由表4可以看出，两个算法在所有背景上得到的概念数量相同，由此表明INCA算法具有良好的准确性。在表4中，数据集Ds1和Ds2中对应的背景(如Ds1_1与Ds2_1)概念数量相同，其原因是形式背景转置的本质是将同一概念的内涵与外延进行交换，所以两者对应的概念数量相同。表4中，|A|对应Ds1中10个背景的属性数量，|O|对应Ds2中10个背景的对象数量，f对应Ds3中7个背景的属性填充率。

表4中小括号内的值为数据集的参数及对应的值。

INCA算法和NextClosure算法在Ds1数据集上的仿真结果如图1所示。由图1可以看出，INCA算法在各个背景上的时间性能都优于NextClosure算法。经计算，INCA算法的平均运行时间比NextClosure算法的平均运行时间降低了15.4%。

图1 INCA算法和NextClosure算法在Ds1数据集上的仿真结果

INCA算法和NextClosure算法在Ds2数据集上的仿真结果如图2所示。由图2可以看出，INCA算法在该数据集在10个背景上的时间性能显著优于NextClosure算法。经计算，INCA算法在10个背景上的平均时间性能比NextClosure算法减少了50%。

对比图1和图2可知，两种算法在数据集Ds1和Ds2上生成的概念数量虽然一样，但运行时间存在很大差异，即NextClosure算法和INCA算法在数据集Ds2的运行时间大幅低于在数据集Ds1的运行时间。例如，NextClosure在Ds1中的第10个背景(|O|=100，|A|=1 000)上的平均运行时间约为960 s(INCA的平均运行时间约为811 s)，而在Ds2的第10个背景(|O|=1 000，|A|=100)上的运行时间约为125 s(INCA的平均运行时间约为63 s)。上述表明，NextClosure算法和INCA算法对|A|>|O|的背景具有更好的适应性。

|A|图2 INCA算法和NextClosure算法在Ds2数据集上的仿真结果

图3为INCA算法和NextClosure算法在Ds3数据集上的仿真结果。由图3可以看出，两种算法的运行时间都随背景属性填充数量的增加而快速增加，但INCA算法的运行时间显著优于NextClosure算法。经计算，INCA算法的运行时间比NextClosure算法平均降低了20.3%。

图3 INCA算法和NextClosure算法在Ds3数据集上的仿真结果

5 结语

实验表明，本文提出的INCA算法在生成概念的效率上明显优于NextClosure算法。在三类不同类型数据集的背景上，INCA算法的平均运行时间比NextClosure算法分别减少了15.4%(Ds1)、50%(Ds2)和20.3%(Ds3)，该结果表明INCA算法具有较好的适应性，尤其是在对象数量远大于属性数量且属性填充较为稀疏的背景上。因此，本文提出的INCA算法在网络分析和推荐系统等领域具有较好的应用价值，如对于|O|和|A|差异较大的背景，若|O|>|A|，则可将该背景转置后使用INCA算法生成以属性集合为外延、以对象集合为内涵的概念(称为属性概念)，再将属性概念中的外延与内涵交换，就可以得到以对象集合为外延、以属性集合为内涵的概念(称为概念属性)。今后的研究将根据概念生成过程中的相关信息探究概念间的层次结构，在生成概念的同时构建出概念格。