内涵粗糙三支概念及个性化推荐

刘忠慧,李 鑫, 闵 帆,2

(1.西南石油大学 计算机科学学院, 四川 成都 610500;2.西南石油大学 人工智能研究院, 四川 成都 610500)

形式概念分析[1](formal concept analysis, FCA)是一种高效的知识表示与处理的数学方法,由德国数学家Wille于1982年提出。其主要研究方向包括模糊概念构造[2]、概念格约简[3-5]、知识空间[6-7]、概念粒计算系统[8-9]等。近年来也在信息检索[10-12]、知识发现[13-14]、关联分析[15-16]、软件工程[17]等领域取得广泛应用。三支概念分析[19-20](three-way concept analysis, 3WCA)是将三支决策[21](three way decision, 3WD)的思想引入FCA得来,因此,形式概念分析中的研究热点也被引入3WCA中,研究内容包括:三支概念格构建[22-23]、模糊三支概念分析[24-26]、规则提取[27-29]、认知学习[30]、粒计算[31-32]、区间集概念格[33-34]、不完备背景的三支概念获取[35]、属性约简[36-37]等。在推荐系统领域,基于FCA的研究主要集中在概念格[18-19],核心思想一般是先构造完整或部分概念格,再根据格结构中的概念偏序关系实现推荐。 但概念格构造算法的时间复杂度非常高,几乎与形式背景的规模呈指数关系,限制了FCA在推荐系统领域的发展。

为了解决概念格因为构建时间复杂度高以及难以应用到实际场景，GRHC算法利用启发式方法构造概念集合代替概念格进行推荐[38]，同样采用构造概念集合进行推荐的，还有基于矩阵分解的GreConD-kNN[39],基于模拟退火法的CSPR[40]以及基于遗传算法和近似概念的ACGA[41-42]。但实际应用中数据集的稀疏度较大,如MovieLens-100k数据集的稀疏度为63%,EachMovies-3ku的稀疏度为5.1%。稀疏度大的数据集可能导致挖掘出的形式概念包含的用户和项目个数较少,影响推荐效果,同时上述算法在推荐时仅利用了概念外延,未考虑概念内涵的独特性质。

针对上述问题,本文提出了内涵粗糙三支概念和相应的启发式构建方法,以及基于内涵粗糙三支概念的推荐算法。实验包括2个阶段,①内涵粗糙三支概念构建,以概念体积作为启发式信息生成内涵粗糙三支概念集；②基于内涵粗糙三支概念的推荐,将结合外延用户偏好以及内涵特性实现个性化推荐。

1 相关工作

1.1 形式概念分析

定义1形式背景[1]。形式背景是一个三元组F=(U,M,R),其中，U和M分别表示用户集和项目集,R表示U和M之间的二元关系。对于用户u∈U和项目m∈M,若(u,m)满足二元关系R,即r(u,m)=1,则表示用户u拥有项目m，若(u,m)不满足二元关系R，即r(u,m)=0,则表示用户u不拥有项目m。

对用户集X⊆U和项目集B⊆M，分别定义如下2个运算，

f(X)={m∈M|∀u∈X,r(u,m)=1}，

(1)

g(B)={u∈U|∀m∈B,r(u,m)=1}。

(2)

定义2形式概念[1]。在形式背景F=(U,M,R)中,对于二元组(E,I),其中E⊆U，I⊆M，若满足f(E)=I,g(I)=E，则称二元组(E,I)为形式背景F中的一个形式概念,简称为概念,其中E称为概念的外延,I称为概念的内涵。

表1为一个简单的形式背景示例, 记录了9位用户对于7个项目的拥有情况。若r(ui,mj)=1(0≤i≤8,0≤j≤6),则表示用户ui拥有项目mj;若r(ui,mj)=0，则表示不拥有。

表1 一个形式背景的例子

例1在表1的形式背景F中，令X={u0,u2,u6},那么f(X)={m0,m3,m5};令B={m0,m3,m5},那么g(B)={u0,u2,u6}。称({u0,u2,u6},{m0,m3,m5})为形式背景F中的一个形式概念,{u0,u2,u6}和{m0,m3,m5}分别为此概念的外延和内涵。

1.2 三支概念

区别于形式概念仅描述了用户和项目的拥有情况,三支概念同时描述了用户和项目的拥有和不拥有的情况,因此,对于形式背景F=(U,M,R)中的用户集X⊆U和项目集B⊆M,还需分别定义如下2个运算，

┐f(X)={m∈M|∀u∈X,r(u,m)=0}，

(3)

┐g(B)={u∈U|∀m∈B,r(u,m)=0}。

(4)

定义3三支概念[19]。在形式背景F=(U,M,R)中,对于任意对象集X,Y⊆U和项目集A,B⊆M。若g(A)=X,┐g(A)=Y和f(X)∩┐f(Y)=A同时成立,称((X,Y),A)为属性导出三支概念,简称为AE概念。(X,Y)和A分别称为((X,Y),A)的外延和内涵;若f(X)=A,┐f(X)=B和g(A)∩┐g(B)=X同时成立,称(X,(A,B))为对象导出三支概念,简称OE概念。X和(A，B)分别称为(X，(A，B))的外延和内涵。

例2在表1的形式背景F下，令X={u0,u2,u6},A={m0,m3,m5},B={m2,m4},计算可得f(X)=A,┐f(X)=B，同时，g(A)∩┐g(B)=X。则称({u0,u2,u6},({m0,m3,m5},{m2,m4}))为形式背景F中的一个OE概念,{u0,u2,u6}和({m0,m3,m5},{m2,m4})分别为此OE概念的外延和内涵;同理,令X={u0,u2,u4,u6},Y={u1,u8},A={m0,m3},计算可得g(A)=X,┐g(A)=Y，且f(X)∩┐f(Y)=A,则(({u0,u2,u4,u6},{u1,u8}),{m0,m3})为形式背景F中一个AE概念,({u0,u2,u4,u6},{u1,u8})和{m0,m3}分别为此AE概念的外延和内涵。

1.3 内涵粗糙三支概念

因为AE概念和OE概念的构造原理相同,因此本文选择以用户为线索进行概念构造,即内涵粗糙三支概念为一种特殊的OE概念,下面给出相关定义。

定义4正内涵。在形式背景F=(U，M，R)中,对于用户集E⊆U,正内涵阈值α∈(0.5, 1]。则E对应的正内涵可表示为

(5)

其中，|·|表示对集合·取模。

定义5负内涵。在形式背景F=(U,M,R)中,对于用户集E⊆U,负内涵阈值β∈(0.5, 1]。则E对应的负内涵可表示为

(6)

其中，|·|表示对集合·取模。

需要说明的是,正负内涵的阈值区间设置为(0.5,1]而不是(0,1],是为了保证正负内涵的可靠性,以正内涵为例,若令其阈值α≤0.5,那么有可能出现某些项目同属于正内涵和负内涵的矛盾,并且这也会导致正内涵中的项目与外延用户的关联性降低。

2 问题描述与分析

本文需要解决2个问题：①如何构造3R概念；②如何将3R概念应用于推荐系统，本节将对这2个问题逐一进行分析。

2.1 构造内涵粗糙三支概念集合

本文基于高质量的3R概念实现推荐,因此,给出衡量3R概念质量的指标。

定义7概念体积。3R概念(E，I+,I-)的体积V由概念面积[40]扩展而来,定义为

V(E,I+,I-)=|E|*|I+|*|I-|。

(7)

由定义7可知,3R概念体积由外延规模和正负内涵规模共同决定,因为形式概念中外延和内涵大小呈负相关关系,易知这一特点在3R概念中同样存在,所以用概念体积进行约束，可以有效保证生成的3R概念在外延和正负内涵规模上的平衡,从而提高推荐成功率。

问题1构造3R概念集合

输入 形式背景F=(U,M,R),正、负内涵阈值α、β。

输出 3R概念集合ST。

约束条件1:∪(E,I+,I-)∈STE=U。

约束条件2：∀(E，I+,I-)∈ST，m1∈I+,

优化目标:min|ST|。

约束条件1的作用是令ST中外延集合包含用户集U的所有用户,即令每个用户都至少包含于一个3R概念,进而确保之后的推荐可以实现。 约束条件2表示利用阈值α、β控制3R概念的正负内涵规模,并保证得到最大概念体积,针对不同的推荐场景,α、β的值可以根据经验进行调整。优化目标为满足条件的3R概念集合ST的规模最小,其目的是提高3R概念的应用效率,获得更好的模型泛化能力。

2.2 基于内涵粗糙三支概念的推荐应用

为评估中间域中项目的推荐可能性，给出推荐置信度的定义如下。

定义8推荐置信度。在形式背景F=(U,M,R)中,有3R概念(E,I+,I-),用户u∈E,项目m∈Io，r(u,m)=0。则基于3R概念向u推荐m的推荐置信度为

rf3WCRI(u,m)=

(8)

问题2基于3R概念集合的推荐。

输入 形式背景F=(U,M,R),3R概念集合ST,推荐阈值γ∈[0,1]。

输出 推荐矩阵L。

约束条件1:∀u∈U,m∈M,∃(E,I+,I-)∈ST满足u∈E，且r(u,m)=0,如果m∈I+,则L(u,m)=1,如果m∈I-,则L(u,m)=0。

约束条件2:∀u∈U,m∈M-I+-I-，∃(E，I+，I-)∈ST满足u∈E，且r(u,m)=0，如果rf3WCRI(u,m)≥γ,则L(u,m)=1。

优化目标:max(F1)。

输入中的ST为问题1中构造的3R概念集合,推荐阈值γ用于控制推荐过程,γ越大则推荐数量越少。推荐结果用一个|U|*|M|的布尔矩阵表示,若向用户u推荐属性m,则将L当前位置的值置为1,反之则置为0。约束条件1表示若待推荐项目属于正内涵则推荐,若它属于负内涵则不推荐。约束条件2表示若存在用户u参与生成的3R概念,使项目m的推荐置信度大于等于γ,则向用户u推荐该项目。优化目标是使推荐结果的综合评价指标F1最大。

3 算法设计

在本小节中,我们提出了解决上述2个问题的3个算法,并分别对算法复杂度进行分析,算法1实现3R概念的生成,算法2基于算法1实现3R概念集合的构造,算法3则实现基于3R概念集合的推荐。 最后,给出运行实例。

3.1 内涵粗糙三支概念的生成算法

算法13R概念生成算法

输入 形式背景F=(U,M,R),用户u,正负内涵阈值α、β。

输出 用户u的3R概念。

方法:3WCRIG(3WCRI Generation)。

1)E←∅，I+←Q，I-←∅,I←∅；

2)m0=arg maxm∈f({u})(|g({m})|);

3)I←I∪{m0};

4)Vmax=0;/*保存3R概念最大体积*/

5) while(true)do

6) for eachm*∈(f({u})-I)do

7) tmpE*=g(I∪{m*});

8)i=m*,E*=tmpE*when |tmpE*|is biggest;

9) end for

12)Vmax=V(E,I+,I-);

13)I=I∪{i};

14) else

15) break;

16) end if

17) end while

18) 3WCRI=(E,I+,I-);

19) return 3WCRI

算法1基于启发式思想为用户u生成一个3R概念。1～4行实现对一些变量的初始化，算法核心功能在5～18行中实现,目的是使生成的3R概念具有最大概念体积。主要分为2步,在6～9行中,逐步添加临时项目,并比较对应的用户集大小,进而获得最优候选外延。第10行则表示通过候选外延以及相应的正负内涵阈值计算得到候选正负内涵,并计算对应的概念体积,第11～13行则用于更新最大概念体积、外延以及正负内涵,如果当前概念体积已经达到最大值,则中止循环,返回用户u的一个3R概念。

3.2 内涵粗糙三支概念集合的构造算法

基于形式背景F,利用算法1为每个用户生成对应的3R概念,构造3R概念集合。

算法23R概念集合的构造算法

输入 形式背景F=(U,M,R),正负内涵阈值α、β。

输出 3R概念集合ST。

方法:3WCSC(3WCRI Set Construction)。

1) ST←∅；

2) for eachu∈Udo

3) 3WCRI=3WCRIG(u,α,β);

4) if(|I+|*|I-|>1∧3WCRI∉

ST)then

5) ST=ST∪{3WCRI};

6) end if

7) end for

8) return ST

算法2基于算法1生成3R概念集。第1行进行3R概念集的初始化,第2行表示遍历整个用户集,第3行调用算法1为当前用户生成3R概念,第4行到第5行即筛选的过程,表示若3R概念的正负内涵不为空且集合ST中不存在此概念,则将其添加到ST中,当循环结束则得到最后的3R概念集合ST。

3.3 基于内涵粗糙三支概念集合的推荐算法

在形式背景F中,算法3利用算法2生成的3R概念集合对用户进行个性化推荐。

算法3基于3R概念集合的推荐算法

输入 形式背景F=(U,M,R),3R概念集合ST,推荐阈值γ。

输出 推荐矩阵L|U|×|M|。

方法:3WCRIR(3WCRI Recommend)。

1)L|U|×|M|←0；

2) for eachu∈U,m∈Mdo

3) for each 3WCRI∈ST,s.t.u∈E3WCRIdo

4) ifr(u,m)=0∧L(u,m)=0 then

5) ifm∈I+then

6)L(u,m)=1;

7) else ifm∈I-then

8)L(u,m)=0;

9) else ifrf3WCRI(u,m)≥γthen

10)L(u,m)=1;

11) else

12)L(u,m)=0;

13) end if

14) end if

15) end for

16) end for

17) returnL|U|×|M |

在算法3中,第1行完成对推荐结果矩阵的初始化。第2行表示遍历整个形式背景,然后根据算法2得到的3R概念集,对用户u进行个性化推荐。第3～12行利用包含了u的3R概念判断是否向u推荐项目m的4种情况。其中3～6行表示项目m包含在3WCRI正内涵中,则直接推荐;7～8行表示若项目m包含在3WCRI负内涵中,则直接不推荐;9～10行计算项目m的推荐置信度,当大于等于推荐阈值时进行项目推荐；11～12行表示不满足上述3个条件的情况不进行推荐。最后返回针对所有用户和项目的推荐矩阵L|U|×|M |。

3.4 算法复杂度分析

假设文中用到的形式背景的大小n×k,用户个数为n,项目个数为k。

在算法1中,3R概念的生成采用了基于体积的启发式方法,算法核心是通过不断迭代获得最大概念体积来筛选生成的3R概念。考虑最坏情况,即用户需遍历数据集中所有项目后才可获得最优候选外延,复杂度为O(nk)。接着需要根据候选外延计算正负内涵,根据上一步结算,外延规模最大可以为n,因此复杂度为O(2nk)。在最后的更新操作中,3R概念外延、正负内涵的赋值运算的复杂度为O(n+k)。按照最外层循环最多次计算,即循环k次,那么算法1的整体时间复杂度即为O(k*(2nk+nk+n+k)),最终表示为O(nk2)。算法2对每个用户都生成一个3R概念,因此构造3R概念集的时间复杂度为O(n2k2)。 算法3实现基于3R概念集合的推荐,对于每一个用户都需要遍历所有的项目以及该用户的所有3R概念。在最坏情况下,即该用户拥有所有的3R概念,此时对其进行推荐的时间复杂度为O(nk)。因此,对所有用户进行推荐的时间复杂度为O(n2k)。

3.5 运行实例

以表1为例,进行3R概念生成以及推荐的实例分析,正负内涵阈值设置为α=β=0.5，以及推荐阈值γ=0.5。

基于({u0,u4,u6},{m0,m1,m3,m5}{m2,m4,m6})对用户u0进行推荐。首先,由于u0已经拥有项目{m0,m3,m5},因此待推荐项目为{m1,m2,m4,m6}。因为项目{m1}包含于正内涵中,所以直接判定为推荐;项目{m2,m4,m6}包含于负内涵中,直接判定为不推荐。故最终基于此3R概念为用户u0推荐一个项目m1。

4 实验及结果

4.1 实验数据集

本文选用6个数据集进行实验,分别为FilmTrust、Amazon-s、Movielens-1m、DouBan-s、EachMovie-3ku以及MovieLens-100k,其中Amazon-s和DouBan-s是基于原始数据集随机抽样得到,数据集按4∶1比例划分成训练集和测试集,详细实验数据集信息如表2所示。

表2 实验数据集

4.2 评价指标

为有效评估本文算法,采用推荐系统中常用的评价指标:精确度(Precision)、召回率(Recall)以及F1。其中,TP、FP、FN分别代表推荐成功、推荐失败、被误判为不推荐的数量，则有计算公式分别如下，

(9)

Precision表示推荐成功的项目数量在总推荐项目数中所占比例。

(10)

Recall表示推荐成功的项目数量在实际应该推荐项目中所占比例。

(11)

F1表示对Precision和Recall的加权调和平均值,当F1值较高时,可说明算法比较有效。

4.3 算法对比实验

为了验证本文算法的有效性,我们选择了kNN、IBCF、MF等推荐领域的经典算法进行对比,同时比较了基于形式概念的推荐算法GreConD-kNN[38]与GRHC[40]以及基于生成对抗网络的协同过滤算法CFGAN[39]。

GreConD-kNN算法将GreConD生成的用户概念矩阵作为kNN输入实现推荐,其中用户概念矩阵由初始形式背景对应的布尔矩阵分解得到。GRHC算法基于概念集合利用外延用户的偏好实现推荐,其中，概念集合由概念面积较大的概念组成。CFGAN算法将生成对抗网络(GAN)引入协同过滤,用向量对的方式对模型进行训练,进而实现推荐。

4. 3. 1正负内涵阈值以及GRHC对比 对比不同正负内涵阈值下3WCRIR算法的运行结果。在Amazon-s数据集上F1值及推荐时间的对比结果分别如图1和图2所示。横坐标表示以步长为0.1控制正负内涵阈值从(0.5,0.5)逐步递增到(1.0,1.0), 纵坐标为当前阈值下的最大F1值和推荐耗时,需要注意的是, 根据定义5和定义6, 正负内涵阈值的取值只能大于0.5, 因此,实验中阈值从大于0.5开始设置。

图1 不同正负内涵阈值方案下的F1比较

图2 不同正负内涵阈值下的推荐时间比较

可以看出在不同阈值条件下F1值以及运行耗时的变化较大。与GRHC相比,正负内涵阈值设置为0.7和0.9时的3WCRIR的时间消耗仅为前者的0.4倍,而且正负内涵阈值分别设置为其他值时,3WCRIR算法的运行耗时也远低于GRHC,同时本文算法在大多数阈值设置下的F1值也远高于GRHC。因此，说明在一定的正负内涵阈值下的3WCRIR算法在时间效率以及推荐性能上均优于GRHC算法。

4.3.2 与其他算法推荐效果对比 表3为3WCRIR与其他算法推荐结果的对比实验结果。从表中可以看出,在综合评价指标F1方面,本文算法在FilmTrust、EachMovie-3ku、Amazon-s和DouBan-S 4个数据集上的F1最高,在MovieLens-100k和MovieLens-1m上与其他算法相当;在精确度方面,3WCRIR在FilmTrust和EachMovie-3ku上具有明显优势,而在其他数据集上的表现一般;在召回率方面,3WCRIR在数据集Amazon-s上表现很突出,远高于其他算法,同时在FilmTrust中也有较好表现。

表3 3WCRIR与其他算法推荐结果的对比

5 总结与展望

本文提出内涵粗糙三支概念, 并将其用于推荐系统。 内涵粗糙三支概念在形式概念的基础上进行扩展, 正负内涵由外延中用户根据相应阈值计算得到, 使得概念外延与内涵的映射关系模糊。 用到推荐系统中时, 可以充分利用正负内涵中的项目, 较传统形式概念只利用外延用户更具有效性。 同时, 在实际应用中的数据集往往稀疏度很高, 基于此类数据集挖掘出的内涵粗糙三支概念具有比形式概念更丰富的信息。 下一步的工作主要包括2个方面： ①本文的内涵粗糙三支概念是基于完备形式背景提出的, 希望能将其进一步应用到不完备背景中； ②设计合适的内涵粗糙三支概念构造方案, 使之在分类任务中也有较好表现。