定义1 形式背景^[1] 形式背景是一个三元组K=(U, M, R), 其中, U为用户集合, M为项目集合, R为U和M之间的二元关系.∀ u∈ U, m∈ M, 如果有uRm, 则表示用户u拥有项目m, r(u, m)=1.

对于U的幂集和M的幂集之间可定义如下2个映射f和g:

表1所示的形式背景记录10位用户对于6个项目的拥有情况.其中:u₁拥有m₂, 则r(u₁, m₂)=1; u₁未拥有m₁, 则r(u₁, m₁)=0.

表1

Table 1

表1(Table 1)

表1 形式背景 Table 1 Formal context U M m1 m2 m3 m4 m5 m6 u1 0 1 0 1 1 1 u2 0 0 1 0 1 0 u3 1 1 1 0 0 0 u4 0 1 1 0 1 1 u5 1 0 0 1 0 0 u6 1 0 0 1 1 1 u7 1 1 0 0 0 1 u8 0 1 0 0 1 1 u9 1 0 1 1 0 1 u10 0 1 1 1 0 0

表1 形式背景 Table 1 Formal context

定义2 评分形式背景^[34] 评分形式背景是一个三元组F=(U, M, V), 其中, U为用户集合, M为项目集合, V为U和M之间的二元关系.∀ u∈ U, m∈ M, v∈ V, v(u, m)≥ 0.如果v(u, m)> 0, 表示用户u拥有项目m, 并且v(u, m)值越高, 表示用户u对项目m的喜爱程度越高; 否则, 表示用户u未拥有项目m.

评分形式背景与形式背景相似, 不同之处在于形式背景是一个二值表, 而评分形式背景的取值范围更广, 包含更多信息.表2是与表1对应的评分形式背景, 表中v(u₁, m₄)=3不仅表示u₁拥有m₄, 还表示u₁对m₄的喜爱程度.

表2

Table 2

表2(Table 2)

表2 评分形式背景 Table 2 Rating formal context U M m1 m2 m3 m4 m5 m6 u1 0 1 0 3 5 2 u2 0 0 4 0 2 0 u3 2 1 5 0 0 0 u4 0 4 3 0 1 5 u5 3 0 0 2 0 0 u6 4 0 0 3 1 5 u7 2 4 0 0 0 3 u8 0 3 0 0 2 3 u9 5 0 2 4 0 2 u10 0 3 1 4 0 0

表2 评分形式背景 Table 2 Rating formal context

定义3 形式概念^[1] 在形式背景K=(U, M, R)中, 如果存在二元组C=(E, I), 满足f(E)=I, g(I)=E, 其中, E⊆U, I⊆M, 则称C为形式背景K中的一个形式概念, 简称为概念.这里E表示概念的外延, I表示概念的内涵.

从表1中可得到概念C=({u₃, u₄, u₁₀}, {m₂, m₃}), 其中E={u₃, u₄, u₁₀}, I={m₂, m₃}.

定义4 偏序关系^[1] 给定形式背景K中的2个概念C₁=(E₁, I₁), C₂=(E₂, I₂), 若满足E₁⊆E₂ (⇔ I₁⊇I₂), 则有C₁≤ C₂, 称≤ 为概念之间的偏序关系.

若2个概念满足C₁≤ C₂, 称C₁为C₂的子概念, C₂为C₁的父概念.

定义5 概念格^[1] 将形式背景K中的所有概念按照定义4的偏序关系进行连接得到的格称为概念格, 记为L(U, M, R).

Hasse图是用来表示有限偏序集的一种数学图表.图1为表1对应的概念格Hasse图.该概念格中有2个概念

C₁=({u₁₀}, {m₂, m₃, m₄}), C2₌({u9_, u1_0}, {m3_, m4_}),

C₁≤ C₂, 则C₁为C₂的子概念, C₂为C₁的父概念.

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 概念格Hasse图Fig.1 Concept lattice Hasse diagram

模拟退火算法^{[32, 33]}是一种启发式算法, 源于对固体退火降温过程的模拟.算法核心是Metropolis准则, 以一定的概率接受劣质解, 使算法在搜索最优解时能以一定概率跳出局部最优, 达到全局最优.

定义6 Metropolis准则^{[32, 33]}:

P(Δ E)= 1, ΔE≤0exp(-ΔEkbT), ΔE> 0

其中, Δ E为前后状态系统能量差, P(Δ E)为接受新状态的概率, k_b为玻尔兹曼常数, T为当前绝对温度.

Metropolis准则表示:若新状态解对应的系统能量更低, 以1的概率接受新状态解; 否则, 通过exp[ -ΔEkbT]计算接受概率P(Δ E).如果P(Δ E)≥ ξ , ξ 为[0, 1]内的随机数, 接受新状态解; 否则, 保留原状态解.

在描述概念集合构造之前, 首先给出相关定义.

定义7 用户相似度 给定形式背景F=(U, M, V), 用户u_i∈ U, u_j∈ U, 项目集A⊆M, 用户u_i、u_j基于项目集A的相似度表示如下:

Sim_A(u_i, u_j)= 1|A|∑k=1|A||v(u_i, a_k)-v(u_j, a_k) |,

其中, a_k∈ A, |· |表示集合的基数, v(u_i, a_k)、v(u_j, a_k)分别表示用户u_i、u_j对项目a_k的评分.特殊地, 如果i=j, Sim_A(u_i, u_j)=0.该相似度表示2位用户关于给定项目集合的曼哈顿距离.

定义8 外延相似度 给定概念C=(E, I), 基于概念C的外延相似度表示如下:

Sim(C)= 2|E|(|E|-1)∑j=1|E|∑k=j|E|Sim_I(u_j, u_k),

其中, u_j∈ E, u_k∈ E.该相似度表示外延集合中用户之间关于内涵I的曼哈顿距离的平均值.因此, 外延相似度越高, 外延中用户之间的平均距离越短, Sim(C)值越小.

本文中目标函数的设置基于外延相似度.前后概念分别对应流程图3中的C和C', C为当前概念, C'为添加一个项目后得到的新概念.前后概念之间的外延相似度之差记为Δ Sim.在此基础上, Metro-polis准则可调整为

P(Δ Sim)= 1, ΔSim≤0exp(-ΔSimSim(C)), ΔSim> 0

其中Δ Sim=Sim(C')-Sim(C).

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 强概念生成算法框图Fig.3 Flowchart of strongest concept generation algorithm

调整后的准则表示:如果新概念的外延相似度更高, 有Sim(C')< Sim(C), 此时Δ Sim≤ 0, 直接接受新概念; 否则, 通过exp[ -ΔSimSim(C')]计算接受概率P(Δ Sim), 并以一定概率接受新概念.

定义9 强概念 令C=(E, I)为基于用户u生成的一个候选概念, 若在用户u的其它候选概念中不存在C'=(E', I'), 使得Sim(C')< Sim(C), 则称C为用户u的强概念.

本文对文献[31]中的强概念进行重新定义, 使用概念外延相似度代替概念面积, 强概念为基于用户u的候选概念中外延相似度最高的概念.

问题1 模拟退火算法构造概念集合

输入 评分形式背景F=(U, M, V), 内涵阈值α

输出 概念集合S={C_i|i=1, 2, 3, …}

约束条件 ∀ (E, I)∈ S, |I|≥ α

优化目标 min(Sim(C_i)), C_i∈ S

输入中的阈值α 由经验值确定, 主要有2个作用:1)确保概念外延中的用户有足够多的共同项目, 2)调整外延集合中用户数量.一般而言:α 越大, 外延集合中用户数量越少, 但用户共同拥有的项目越多, 用户之间更相似; 否则, 外延集合中用户数量越多, 用户共同拥有的项目越少, 用户之间差异越大.输出中的概念集合S为每位用户的强概念构成的集合.约束条件表示强概念外延中用户共同拥有的项目数量至少为α .优化目标表示每个强概念外延内用户的平均距离尽可能短, 即用户之间的相似度尽可能高.

在描述推荐问题之前, 首先给出推荐置信度的定义.

定义10 推荐置信度 给定形式背景F=(U, M, V), 目标用户u参与生成的概念C=(E, I), 待推荐项目m∈ M, v(u, m)=0, 推荐置信度

RF_C(u, m)= |{u'∈E|v(u', m)> 0}||E|-1,

其中, |· |表示集合的基数, v(u', m)表示用户u'对项目m的评分, RF_C(u, m)表示在概念C中u的邻居用户拥有项目m的占比.

问题2 利用概念集合进行个性化推荐

输入 形式背景F=(U, M, V), 概念集合S,

推荐阈值β

输出 推荐矩阵L

约束条件 ∀ u∈ U, m∈ M, 如果v(u, m)=0且∃C∈ S_u使RF_C(u, m)> β , 则l_{(u, m)}=1

优化目标 max(F₁)

输入中的概念S为问题1中构造的概念集合.推荐阈值β ∈ [0, 1], 由经验值确定, 作用是控制推荐项目的数量.一般而言:推荐阈值越大, 推荐的项目数量越少; 否则, 推荐的项目数量就越多.输出是一个大小为|U|× |M|的二维布尔矩阵L, 记录每位用户的推荐结果, 矩阵的值初始时设置为0.约束条件中S_u为S中包含有目标用户u的概念子集合.

约束条件表示:若同时满足1)用户u未拥有项目m, 2)基于概念C的推荐置信度大于推荐阈值, 则向用户u推荐项目m, 通过将L中对应位置的值改为1(l_{(u, m)}=1), 记录推荐结果.

问题的优化目标是获得更高的F₁值, 即更优的推荐效果.

概念集构造算法由强概念生成算法(Strongest Concept Generation Algorithm, SCGA)和基于模拟退火法的概念集构造算法(Concept Set Construction Based on Simulated Annealing, CSSA)共同完成, SCGA针对给定用户生成一个强概念, CSSA完成概念集合的构造.SCGA流程如图3所示.为了生成一个强概念, 首先会基于模拟退火算法生成γ 个候选概念, 再从候选概念中筛选得到外延相似度最大的概念, 即为给定用户的强概念.

算法1 SCGA

输入 评分形式背景F=(U, M, V), 内涵阈值α ,

给定用户u∈ U, 候选概念个数阈值γ

输出 强概念C_s

1.C_s← Ø ;

2.Sim_s← +¥ ;

3.while (γ --) do

4. E=g({m}), m∈ f({u});

5. I=f(E);

6. C=(E, I);

7. E'=E, I'=I, C'=(E', I');

8. M_u=f({u})-{m};

本文利用概念集合对每位用户进行个性化推荐, 提出基于概念集的个性化推荐算法(Concept Set Based-Personalized Recommendation Algorithm, CSPR), 具体步骤如下.

算法3 CSPR

输入 评分形式背景F=(U, M, V), 概念集合S,

推荐阈值β

输出 推荐预测矩阵L

1.L_{|U|× |M|}← 0;

2.for (each u∈ U) do

3. S_u={C|u∈ E, C∈ S};

下面分析算法1~算法3的时间复杂度.假设评分形式背景中有n位用户和m个项目, 基于每位用户生成的候选概念个数γ =k.在生成候选概念时, 对于过程中出现的每个概念都需要计算外延相似度, 最坏的情况是一个概念包含所有用户与项目, 因此时间复杂度为O(n²m).在内涵添加过程中, 内涵阈值最大设置为α =m, 因此最坏情况需要添加m次.为了生成一个强概念, 需要生成k个候选概念, 因此算法1的时间复杂度为O(kn²m²).

为了构成概念集合, 需要基于每位用户生成一个强概念, 因此算法2的时间复杂度为O(kn³m²).

在推荐过程中, 需要遍历每位用户的每个项目, 遍历的时间复杂度为O(nm).对于每个项目, 最坏情况需要遍历所有概念才能得出最终推荐结果, 而概念个数和外延长度至多为n, 此过程的时间复杂度为O(n²).因此算法3的时间复杂度为O(n³m).

实际上, 在概念生成过程中, 项目添加的次数远小于m, 并且概念外延的长度远小于n, 内涵的长度远小于m, 因此算法2实际的执行时间远小于O(kn³m²).概念集合构造的复杂度远低于概念格构造的时间复杂度O(n2^m)^[6].在推荐过程中, 由于概念数量和内涵长度远小于n, 算法3的执行时间也远小于O(n³m).

以表2所示的评分形式背景为例, 并结合图4所示的概念生成和推荐流程, 描述基于用户u₁的强概念生成及针对其的推荐过程.设置内涵阈值α =2, 候选概念个数阈值γ =4, 推荐阈值β =0.6.

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 运行实例流程图Fig.4 Flowchart of a running instance

强概念生成过程见图4中概念生成部分.初始化概念C=C'=(U, Ø ).根据图4评分形式背景得到用户u₁拥有的项目集合 Mu1={m₂, m₄, m₅, m₆}, 随机选取项目m₄加入内涵集合后, 可得到概念

C=({u₁, u₅, u₆, u₉, u₁₀}, {m₄}),

第1个概念直接更新C'=C.此时, 最高相似度

Sim_s=Sim(C')=1.00,

概念内涵长度为1, 小于内涵阈值α , 则继续随机选取项目m₆加入内涵,

C=({u₁, u₆, u₉}, {m₄, m₆}),

计算外延相似度之差

Δ Sim=Sim(C')-Sim(C)=-0.33,

计算接受概率

P(Δ Sim)=0.718,

这里假设P(Δ Sim)> ξ , 更新概念

C'=({u₁, u₆, u₉}, {m₄, m₆}),

此时内涵长度为2, 满足阈值α , 结束添加内涵, 得到一个候选概念.重复上述过程, 生成4个候选概念C₁、C₂、C₃、C₄.再根据概念外延相似度进行筛选, 得到基于用户u₁的强概念:

C=({u₁, u₆, u₉}, {m₄, m₆}).

对于用户集合中的所有用户, 都按照上述过程生成一个强概念, 最终构成概念集合, 如表3所示.用户集上某些用户会生成相同的强概念, 因此集合中概念数量总是小于等于用户数量.

表3

Table 3

表3(Table 3)

表3 概念集合 Table 3 Concept set 概念编号 外延 内涵 1 {u1, u6, u9} {m4, m6} 2 {u2, u4} {m3, m5} 3 {u3, u7} {m1, m2} 4 {u5, u6, u9} {m1, m4} 5 {u1, u4, u7, u8} {m2, m6} 6 {u9, u10} {m3, m4}

表3 概念集合 Table 3 Concept set

强概念生成过程见图4中个性化推荐部分.以强概念C=({u₁, u₆, u₉}, {m₄, m₆})为例, 描述针对用户u₁的推荐过程.从形式背景中可得待推荐项目为{m₁, m₃}.用户u₁基于该概念的邻居用户为{u₆, u₉}.2位邻居用户都拥有项目m₁, 故推荐置信度RF_C(u₁, m₁)=1, 大于推荐阈值β , 向用户u₁推荐项目m₁, l(u1, m1)=1.用户u₆拥有项目m₃, 而用户u₉未拥有m₃, 故置信度RF_C(u₁, m₃)=0.5, 小于推荐阈值β , 则不推荐项目m₃, l(u1, m3)=0.

本文实验选用电影和笑话两类评分数据集, 以及基于它们随机抽样得到的6个抽样数据集, 其中ML-100k、ML-1m、ML-10m、Filmtrust数据集为电影评分数据集, Jester数据集为笑话评分数据集.数据集详细信息如表4所示.

表4

Table 4

表4(Table 4)

表4 实验数据集 Table 4 Experimental datasets 名称 大小 稀疏度 ML-100k 943× 1682 0.0630 ML-1m 6040× 3952 0.0419 ML-10m 71567× 10681 0.2392 Filmtrust 1508× 2071 0.0114 Jester 24983× 101 0.2449

表4 实验数据集 Table 4 Experimental datasets

实验中使用的数据集均划分为两部分, 80%的数据作为训练集, 20%的数据作为测试集.文中数据集稀疏度定义为评分形式背景中有评分的数据占整个矩阵空间的比例.

对于推荐效果的评价主要采用推荐系统中常用的3个指标:精确度(Precision, P), 召回率(Recall, R)和F₁.用户进行推荐得到的推荐预测矩阵记为L(U), 用于验证结果的测试矩阵记为T(U).

精确度为被正确推荐的项目个数与总推荐项目个数的比例:

precision= |L(U)⋂T(U)||L(U)|.

召回率为被正确推荐的项目个数与测试集中项目个数的比例:

recall= |L(U)⋂T(U)||T(U)|.

F₁为综合考虑精确率和召回率, 对推荐结果进行全面评价:

F₁= 2×precision×recallprecision+recall.

为了验证CSPR的复杂度及推荐准确性, 在抽样数据集上与CNCF进行对比.CNCF为基于概念格的推荐算法, 概念格构造采用渐进式方法, 从空概念格开始, 将形式背景中的用户逐个加入到已构造好的格中, 再不断更新格, 最终完成格的构造.推荐时通过格间关系寻找包含目标用户概念的兄弟概念与子概念, 从而实现对目标用户的推荐.

实验所用的4个抽样数据集分别从ML-100k、ML-1m数据集上随机抽样得到, 大小均为200× 420.2种算法在不同数据集上的推荐效果和算法运行时间对比如表5所示, 表中黑体数字表示最优结果.

表5

Table 5

表5(Table 5)

表5 CSPR和CNCF的推荐效果及运行时间对比 Table 5 Comparison of recommendation result and running time of CSPR and CNCF 数据集 稀疏度 算法 P R F1 运行 时间 ML-100k -s1 0.0506 CSPR CNCF 0.1047 0.1035 0.2327 0.2300 0.1445 0.1427 250 ms 3 min ML-100k -s2 0.0595 CSPR CNCF 0.1200 0.1190 0.2402 0.2380 0.1601 0.1587 250 ms 8 min ML-1m -s1 0.0727 CSPR CNCF 0.1500 0.1505 0.2958 0.2866 0.1991 0.1973 330 ms 3.5 h ML-1m -s2 0.0724 CSPR CNCF 0.1465 0.1578 0.3048 0.2957 0.1979 0.2058 360 ms 4 h

表5 CSPR和CNCF的推荐效果及运行时间对比 Table 5 Comparison of recommendation result and running time of CSPR and CNCF

由表5可看出, 在4个抽样数据集上, CSPR和CNCF的推荐效果相当, 但运行时间有明显差异.在推荐效果方面, CSPR与CNCF在F₁值上保持基本一致, CSPR的召回率均略高于CNCF.在运行时间方面, CSPR的平均运行时间为几百毫秒, 而CNCF运行时间却是前者的几百倍, 甚至是几万倍.与CNCF对数据集稀疏度敏感不同的是, CSPR在不同稀疏度的数据集上保持运行时间的稳定.相比CNCF的运行时间从3 min增至4 h, CSPR的增幅较小.

为了验证CSPR推荐的有效性, 选择基于项目的协同过滤算法(Item-Based Collaborative Filte-ring, IBCF)、GRHC、KNN对比推荐效果.

IBCF通过计算项目间的相似度, 向目标用户推荐与其喜爱项目相似度较高的其它项目.文中项目之间的相似度通过杰卡德相似度计算.

GRHC是基于FCA理论的推荐算法.以面积作为启发式信息, 同时利用内涵约束, 构造面积最大的强概念, 用于包含更多的邻居用户, 再根据邻居用户的偏好对目标用户进行推荐.

KNN计算用户之间的相似度, 寻找与目标用户最相似的前K位邻居用户, 再根据它们的偏好对目标用户进行推荐.文中用户之间的相似度通过余弦相似度计算.

实验中ML-10m-s、Jester-s数据集为抽样数据集, 大小分别为3 600× 1 000和2 000× 100.不同算法的推荐效果对比如表6所示, 表中黑体数字表示最优结果.

表6

Table 6

表6(Table 6)

表6 各算法的推荐效果对比 Table 6 Recommendation result comparison of different algorithms 数据集 稀疏度 算法 P R F1 ML-100k 0.0630 CSPR IBCF GRHC KNN 0.1960 0.2369 0.2273 0.1929 0.3145 0.3613 0.2159 0.3518 0.2415 0.2862 0.2214 0.2491 ML-1m 0.0419 CSPR IBCF GRHC KNN 0.1549 0.1844 0.1270 0.1865 0.2653 0.2419 0.2203 0.2485 0.1956 0.2093 0.1611 0.2131 ML-10m-s 0.2498 CSPR IBCF GRHC KNN 0.3406 0.3047 0.2714 0.3571 0.3379 0.3450 0.3225 0.3072 0.3392 0.3236 0.2948 0.3303 Jester-s 0.2476 CSPR IBCF GRHC KNN 0.3150 0.2871 0.3294 0.2996 0.3875 0.3763 0.3256 0.3769 0.3475 0.3263 0.3279 0.3338 Filmtrust 0.0114 CSPR IBCF GRHC KNN 0.4549 0.4381 0.4503 0.4480 0.5236 0.4417 0.5043 0.4905 0.4868 0.4396 0.4757 0.4683

表6 各算法的推荐效果对比 Table 6 Recommendation result comparison of different algorithms

由表6可看出, 各算法在不同数据集上的推荐效果有明显区别.在精确度方面, CSPR在Filmtrust数据集上有最高的精确度, 而在ML-1m数据集上明显低于IBCF和KNN.在召回率方面, CSPR在3个数据集上有最高的召回率, 在ML-10m-s数据集上有次高的召回率, 并且在所有数据集上的召回率都高于GRHC.在F₁值方面, CSPR在3个数据集上有最高的F₁值, 在ML-100k、ML-1m数据集上, CSPR的F₁值均低于KNN和IBCF, 但在所有数据集上CSPR的F₁值都高于GRHC.

实验结果表明, CSPR在较稠密的数据集上有更好的推荐效果.ML-10m-s、Jester-s比ML-100k、ML-1m稠密, CSPR在前两个数据集上的F₁值更高.Filmtrust数据集虽然稀疏, 但数据在空间中分布较集中, CSPR在该数据集上的推荐效果也较优.