基于对象阈值变精度概念的启发式推荐方法

张国锋，杨 凯

(辽宁科技大学 计算机与软件工程学院，辽宁 鞍山 114051)

0 引 言

形式概念分析(formal concept analysis，FCA)[1]是Wille基于序理论提出的理论体系，由于其核心数据结构概念格对于稀疏数据的处理能力较强，被应用于推荐系统[2-8]领域。Boucher Ryan首次将形式概念分析与推荐系统结合[9]。Zou、陈昊文、朵琳、张喜征等相继将形式概念分析的各种方法用于推荐算法研究[10-13]。

概念格的构造是FCA应用于推荐的瓶颈，数据量较大时，建造概念格会变得非常困难。曾利程等在Addintent算法的基础上，提出了一种快速构建概念格的算法[14]。JAM等构造依赖空间模型来生成概念格[15]。其后，郭泽蔚、钱婷、姜琴等相继在自己研究的领域对概念格构造进行改进[16-18]。这些构造算法虽然能一定程度上缩短建格时间，但未从根本上解决问题，在大数据下构造概念格依然难以完成。刘忠慧等提出了一种不建造格结构，而是利用强概念提取概念格规则的方法[19]，时间复杂度大幅降低，从根本上解决了效率问题，但应用于推荐时准确率和F1值过低，结构仍需完善。

本文将文献[19]中的启发式方法进行优化，将“形式背景”转化为“对象阈值变精度形式背景”，“强概念”转化为“对象阈值强概念”，提出了基于对象变精度概念的启发式推荐方法(variable precision heuristic concept，VPHC)。此方法对每个用户单独考虑阈值的取舍，在降低建格复杂度的同时又能充分考虑用户之间的差异，在推荐实验中取得了良好的效果。

1 相关定义

定义1 经典形式背景[1]

设形式背景K=(G，M，I)，G为对象集合，M为属性集合，I代表G和M之间的关系，I⊆G×M。 另设集合A、B，令A⊆G，B⊆M定义映射如式(1)、式(2)所示

f(A)={b∈M|a∈A，aIb}

(1)

g(B)={a∈G|b∈B，aIb}

(2)

设f(A) 是对象集A⊆G中所有对象所共同拥有的属性，g(B) 是属性集B⊆M中所有属性共有的对象。经典形式背景和经典概念格如表1和图1所示。

图1 经典概念格Hasse

表1 经典形式背景

定义2 模糊映射[20]

对于模糊形式背景中的每个属性，选取两个阈值k1和k2，满足0≤k1

F*(O)={d|o∈O，k1≤I(o，d)≤k2}

(3)

G*(D)={o|d∈D，k1≤I(o，d)≤k2}

(4)

定义3 变精度概念[21]

在模糊形式背景K=(U，A，I) 中，类比模糊映射定义，针对任意X⊆U，B⊆A，设阈值k(0

(5)

(6)

若二元组(X，B)满足X=B*k，B=X*k，则称(X，B)为阈值k下的变精度概念。变精度概念格共有3种，本文中变精度概念定义和结构指的都是Crisp-crisp变精度概念格。

定义4 概念领域[19]

在形式背景K=(U，A，I) 中，任意X⊆U，B⊆A，形式概念C=(X，B) 的领域由它的面积决定，面积越大表明该概念具有较高的相似性和较强的稳定性，具体如式(7)所示(|·|表示集合的基数)

Area(X，B)=|X|×|B|

(7)

定义5 强概念[19]

设C=(X，B) 为x∈X的强概念，当且仅当不存在x∈X′，Area(X，B)

2 基于对象阈值变精度概念的启发式推荐方法

2.1 对象阈值可变的变精度强概念

在进行电影推荐时，设电影评分为“1～5”，两人对一部电影评分，前者评分是“4”，后者评分为“3”，单纯来看前者的评价高于后者，但若前者评分从未低于过“3”，后者评分从未高于过“3”，这样看来二者对此电影的喜欢程度便会变得难以区分。

若对每个用户单独进行考虑，便不会再有这一麻烦。如，用户1喜欢对其看过的电影打高分，若其对一部电影的评分为“3”，那么这一中档评分便可归于低分类别。用户2喜欢对其看过的电影打低分，碰到用户2打分为“3”的电影数据时，这一评分则应归于高分类别。

基于以上思想，根据数学中的变精度概念格结构，提出对象阈值变精度概念格定义和结构(如定义6所示)。再将对象阈值变精度形式背景进行规则提取，生成强概念，便形成了对象阈值变精度启发式强概念。

定义6 对象阈值变精度概念格

设模糊形式背景为(U，A，I)，对应变精度阈值为k(0

(8)

(9)

此定义针对变精度概念做出改进，让其更适合于实际应用。如表2所示，阈值K={0.5，0.4，0.5，0.5，0.35}， 这种改动能将每个对象所需的隶属度函数全部提出，避免因阈值统一对隶属度函数均偏低或均偏高对象的影响。

表2 对象阈值变精度形式背景

通过μ和t的取值来控制对象的变精度阈值，如图2～图5所示。

图2 μ=0.6，t=0时对应的Hasse

图3 μ=1，t=0时对应的Hasse

图4 μ=1，t=0.2时对应的Hasse

图5 μ=1，t=-0.2时对应的Hasse

以下是4种取值所产生的强概念集合，由于形式背景极小，内涵阈值设为1，从左往右μ和t的取值依次为(μ=0.6，t=0)(μ=1，t=0)(μ=1，t=0.2)(μ=1，t=-0.2)。

由于模糊形式背景和变精度形式背景，利用了评分数据，所以对强概念定义加入评分信息，对概念领域进行修改，将面积转化为加权面积，提出了加权概念领域定义。

定义7 加权概念领域

(10)

例如：构建用户1的强概念，设有概念C1和概念C2备选。若由定义5概念领域定义计算，概念C1=(135，ad) 其面积为6，概念C2=(159，df) 其面积也为6，则两者概念面积相同，只能由先进入备选的概念作为强概念。对于加权概念领域定义来说，要在模糊形式背景中取两概念的评分集，设u1对“a”的评分为0.6，对“d”的评分为0.8；u3对“a”的评分为0.5，对“d”的评分为0.8；u5对“a”的评分为0.4，对“d”的评分也为0.4，可得概念C1外延集{1，3，5}对于内涵集{a，d}的评分集为 [{0.6，0.8}，{0.5，0.8}，{0.4，0.4}]， 概念C1的加权面积可由其概念面积乘以评分集之和得到，即Area(C1)=3×2×(0.6+0.8+0.5+0.8+0.4+0.4)=21； 同理，设概念C2的评分集为 [{0.8，0.8}，{0.4，0.6}，{0.6，0.8}]， 得到概念C2的加权面积：Area(C2)=3×2×(0.8+0.8+0.4 +0.6+0.6+0.8)=22.8； 由于Area(C1)=21

2.2 推荐置信度计算

通过计算基于强概念的推荐置信度，可以进行群组推荐，推荐置信度如式(11)所示。

定义8 推荐置信度[19]

给定形式背景K=(U，A，I)， 强概念C=(X，B)， 对象u∈X，属性i∈A-B，r(u，i)=0。 则基于强概念C向u推荐i的置信度为

(11)

置信度由群组中每个对象的推荐综合决定，r(u，i)=0表示规定对象u的属性i为0，即用户u没看过电影i。

2.3 推荐流程

2.3.1 数据处理

在推荐之前要对数据进行预处理，首先将电影数据转化为形式背景，并且将形式背景转化为对象阈值变精度形式背景(具体见算法1)，在数据处理的过程中，把每个用户所看过的全部电影作为一条数据输入算法。

算法1：数据预处理

输入：数据集(user Id，movie Id，rating，timestamp)

输出：对象阈值变精度形式背景K=(U，A，I)

(1) (U，A，I)← ∅； //构建三维数据并将其初始化作为形式背景

(2) len(U)=max(user Id)，len(A)=max(movie Id)； //对形式背景横纵长度进行约束

(3) a=max(user Id)； //取a作为id最大的用户

(4) for(each user Id)//对数据集中的每条数据进行遍历，将一个用户的全部数据作为每条数据

(5) if (user Id<=a) then

(6) n=len (movie(user Id))，rat=0；//n为用户i看过的电影个数之和

(7) for (each movie Id)；

(8) rat=rat+rating(user Id)；//对每个用户的所有评分求和

(9) (U，A，I)←(user id，movie Id(rating))； //求和时，需要遍历所有此用户看过的所有电影，这时便可写入到形式背景中去

(10) end for

(11) k=rat/n；//算出每个user所对应的基础阈值k

(12) (U，A，I)←k //将基础阈值k作为一个单独数据附到每个用户所有电影评分之后。

(13) end if

(14) end for

(15) return K=(U，A，I)

2.3.2 强概念集构造与置信度推荐

预处理数据生成形式背景之后便可以进行对象阈值强概念构造，这一部分的思想和文献[19，22]中的方法类似，但对概念领域的计算进行了修改，将原本的概念面积乘以了评分集之和，具体思想如算法2所示。还需要注意的是对象阈值强概念集合，并不是只有一个，根据μ和t值选取的不同可构造出不同粒度的强概念集合，在之后的推荐中根据离线测评数据来判定最优的强概念集合。

算法中伪代码为简洁明了省略了必要的循环步骤，如算法2第(16)行，需要对对象u的所有属性进行循环，然后返回形式背景中找出每个属性对应的对象个数，在算法中仅用一个公式来代替。

算法2：对象阈值强概念集构造

输入：μ，t，对象阈值变精度形式背景K=(U，A，I)

输出：强概念集合C

(1) C←∅；//初始化强概念集合C

(2) for(eachu∈U)

(3) if (A(u)>=μki+t) then//将对象u每个属性的隶属度函数与变精度阈值比对，大于等于变精度阈值的可以保留并在形式背景中为“1”，其它的为“0”

(4) ((U，A，I)→A(u))=1

(5) else ((U，A，I)→A(u))=0

(6) end for

(7)P=sort(U)； //建立全部对象的集合P，并将P进行排序。

(8) while (u∈P，P≠∅) do //对集合P中的每一个对象u进行强概念构造

(9) (X，B)←∅ //初始化强概念

(10)m←0；//设置m为加权概念领域面积

(11)b=arg max(len (a(u)))； //表示b为对象u的所有属性a中所包含对象数最多的属性。

(12)B=B∪{b}； //将此属性并入内涵集

(13) while(true)

(14) for (eachj∈a(u)-B) //表示对对象u中的不属于B的属性进行遍历，即刨去b之外的其它属性

(15)a=B∪j；

(16) uc=ac(u) //表示uc为属性集ac所对应的对象集

(17)i=jwhere len(uc) is the biggest；//i为使对象集uc达到最大长度所对应的属性j的取值

(18) end for

(19)mu=Area(uc，B∪i)； //mu便为计算出的加权概念面积

(20) if(mu>m∨(len(B)+1)<2) then //满足两个条件中的任一个就给B和m赋值继续循环

(21)B=B∪{i}；

(22)m=mu；

(23) else //针对(11)行中的两个条件皆不满足表示强概念已经满足要求，此时退出循环。

(24) break；

(25) end if

(26) end while

(27)X=uc；

(28) =C∪(X，B)； //将对象u的强概念并入概念集合C

(29)P=P-X(C)； //将强概念的外延中所有对象在对象集P里面剔除

(30) end while

(31) returnC

需要注意的是第(17)行i为单个属性值，第(19)行Area函数表示的是加权概念领域，第(29)行表示在对象u生成强概念的同时，其强概念外延中的对象便都以此为自身的强概念，避免了重复生成。

最后便是构造推荐预测矩阵进行置信度推荐，构造具体方式参见文献[19]，置信度公式为式(11)，推荐的具体流程如图6所示。

图6 推荐流程

首先，将评分数据集预处理生成模糊形式背景，对每一个用户计算出对象变精度阈值；然后，将阈值加入模糊背景生成对象阈值变精度形式背景；对此背景进行启发式构造生成对象阈值强概念集合；利用置信度公式对每个用户进行推荐度计算；最后构建推荐矩阵对用户进行推荐。

3 实验分析

3.1 评测指标

推荐系统的评测指标，通常有如下几种：

设R(u) 是算法针对用户u产生的推荐列表，T(u) 是用户在测试集上的行为列表。

(1)准确率(precision)

(12)

(2)召回率(recall)

(13)

(3)综合评价指标F1-measure

(14)

3.2 对比算法介绍

本文提出的VPHC算法将与User-KNN算法[2，5]、Item-KNN算法[2]、CNCF算法[11]、GRHC算法[22]进行比对。

User-KNN算法和Item-KNN算法是推荐系统经典算法，相似度采用Jaccard相似度，计算公式参见文献[2，5]。CNCF算法是基于概念格的协同过滤算法，其算法思想和公式表述参见文献[11]。GRHC算法是启发式概念的推荐方法，也是本文进行优化的方法，其推荐置信度如式(11)所示，推荐置信度阈值设置为0.5，内涵阈值设置为2。

3.3 生成概念数量及时间对比实验

实验数据集见表3，其中MoveLens1～MoveLens4为MovieLens 100K的抽样数据集，MovieLens 100K和Movie-Lens 1m数据集为经典的推荐系统数据集，FilmTrust数据集是2011年从整个FilmTrust网站上抓取的小型数据集，是高稀疏度下的推荐系统评测数据集。本文所用数据集中用户对于电影的评分区间均为[1，5]。

表3 数据集信息

本文VPHC算法和其它算法在多种数据集下生成概念数量与所需时间对比见表4，VPHC算法中对象变精度阈值的选取为(μki+t)，在表4中用(μ/t)表示。

表4 生成概念数量与所需时间对比

其中，CNCF算法构造概念格时按照渐进式Godin算法生成，所需时间较长，概念数量多。GRHC算法启发式生成强概念，时间上比之极大缩短。VPHC算法采用加权面积的方式生成强概念，计算稍微复杂，但因对象变精度阈值将一部分次等数据剔除，运行时间还要略低于GRHC算法。对比不同(μ/t)值下的VPHC算法，生成概念数量和所用时间都较为接近，在准确率等指标不同时，可仅依靠离线评测指标挑选出对特定数据集最优的(μ/t)取值。

3.4 三大离线评测指标对比实验

实验采用Movenlens4作为数据集，随机选取80%训练集，20%测试集，因数据选取的随机性，以5次测试的平均数为准。抽样数据集评测结果见表5。

表5 Movelens4数据集上的实验结果

由表5可以看出，GRHC算法和CNCF算法在此抽样数据集中评测指标相近，GRHC算法略低于CNCF算法，UserKNN算法准确率较高，但召回率较低，VPHC算法明显优于UserKNN和ItemKNN算法，略高于CNCF算法和GRHC算法。其中，随着(μ/t)值不同，导致所产生的强概念集合不同，VPHC算法准确率等指标有明显的波动。从表中可以看出在当前数据集下，当μ=1，t=-0.5时算法F1值最高。

VPHC算法μ、t两值单变量之间的比较如图7和图8所示(横坐标表示不同μ、t值下的VPHC算法，纵坐标表示准确率等3种指标的结果)。

图7 VPHC算法(μ/t)在μ值逐渐增大t值不变时各类指标比较

图8 VPHC算法(μ/t)在μ值不变t值逐渐增大时各类指标比较

通过图7可以看出，算法在μ值增加t值不变时，三大指标前段平稳并有缓慢上升的趋势，因为μ值较小时变精度阈值对每个对象来说也会相对较小，致使一部分低评分信息用于强概念构造，导致精度稍微下降；中段μ=1，t=0时达到最高；后段折线下降趋势明显，因为后段随着μ值的增加变精度阈值对每个对象来说越来越大，致使可用来构造强概念的评分信息越来越少，强概念信息不全，导致评测指标下降明显。

图8是算法在μ值不变t值增加时的指标比较折线图，总体趋势和图7相似，变化趋势较之图7来说略显平稳，表示t值(±0.5)对于总体阈值的变动略小于μ值(±0.2)，VPHC算法指标在μ=1，t=-0.5时达到最高。

两完整数据集上的对比实验结果见表6和表7。

表6 MovieLens数据集中各算法实验结果

表7 FilmTrust数据集中各算法实验结果

由表6可以看出在MovieLens 100k数据集中μ=1，t=-0.5时VPHC算法效果最好，准确率比GRHC算法高2.8%，召回率高0.82%，F1值高2.08%。

对于FilmTrust数据集来说，VPHC算法在μ=1，t=0时效果较好，准确率比GRHC算法高2.34%，召回率高2.29%，F1值高2.31%。并且这一数据集上基于概念结构的算法离线指标要远高于经典kNN算法。例如，VPHC(1/0)算法F1值比UserKNN算法高19.01%，比ItemKNN算法高15.81%。

综合来看，本文在GRHC算法的基础上提出的VPHC算法，在对其它算法的对比实验上表现出了较好的性能和精度。并且，根据表4可知，VPHC在各种(μ/t)值下的时间消耗均小于GRHC算法所需时间。

4 结束语

本文在启发式推荐方法中加入对象阈值变精度概念，提出了基于对象阈值变精度概念的启发式推荐方法。该方法既保留了启发式方法对概念构造的快速性，又提高了其精准度，并且该方法根据对象变精度阈值(μki+t)中(μ/t)变量的取值不同可得到不同的对象阈值强概念，进而产生不同的推荐。又因(μ/t)值变化时产生强概念的时间消耗接近，所以可找出最适合当前数据集(μ/t)取值方式，使VPHC算法达到最优。

未来的工作主要包括以下方面：

(1)本文推荐置信度公式过于简单，未来将考虑加入更多信息来完善置信度公式。

(2)启发式概念构造打破了传统概念格建格困难的屏障，将考虑将概念格中的其它优秀结构用启发式概念构造和提取规则。