结合对象属性与近似检索的协同过滤算法

陈 乐，余 粟

1(上海工程技术大学 电子电气工程学院,上海 201620)

2(上海工程技术大学 图文信息中心,上海 201620)

1 引 言

随着互联网与人们生活日趋密切，互联网产生的数据量和信息量呈爆发式增长，如何从海量数据中快速准确地找到用户所需信息成为一大难题[1，2].因此，个性化的推荐系统应运而生，它将根据用户的网络历史行为和自身属性预测人们可能需要的商品或信息[3].

协同过滤技术[4，5]因其模型通用性强和易于实现而成为推荐系统的主流技术之一.其又包含近邻模型[6]和隐变量模型[7]两种主要的实现方式.近邻模型通过挖掘由用户与商品的交互行为而产生的历史数据，例如评分数据、行为数据(点赞、评论、转发)等，将具有相似行为偏好的用户群作为目标用户的近邻用户集，再基于近邻用户集计算目标用户对未评分物品的预测得分[8，9].

为了解决原始评分数据高维稀疏，物品和用户自有属性缺失等问题，国内专家进行了相关研究.朱磊等[10]采用用户评分偏好模型改进用户间原始评分数据的偏好差异性，但是原始评分数据的稀疏性和近邻用户的检索性能有待改进.王永贵等[11]提出构建用户类别偏好矩阵，并利用花朵授粉优化模糊聚类算法，一定程度上改进了数据的稀疏性和近邻用户的检索性能，但是算法时间复杂度较大，且并未考虑用户评分偏好.李红梅等[12]利用基于精确欧式局部敏感哈希对评分数据降维并构建索引，能显著提高近邻用户检索性能，但并未挖掘评分数据中隐藏的用户和物品特性.

对已有的相关协同过滤技术综合分析可知，仅从用户或物品单一方面改进评分数据都存在一定的片面性，另外提高检索效率的同时还要保证稳定的时间复杂度，故本文提出一种结合对象属性和近似检索的推荐模型.该模型利用物品和用户的自有属性同时改进原始评分数据，并通过近似最近邻检索技术对评分数据降维索引，进而可以有效提高推荐质量和推荐效率.

2 相关工作

2.1 对象相似性度量

基于近邻模型的协同过滤算法中，推荐结果的精准与否主要取决于用户或物品的相似性计算[13].相似性度量方式主要采用Person相关系数、欧式距离和修正余弦相似系数等，且Pearson相关系数在度量精度上优于修正余弦相似系数[14].基于Pearson相关系数的用户间相似性sim(u,v)计算如下：

(1)

2.2 近似最近邻检索

在近邻模型中，如何在高维稀疏的评分数据空间快速准确地通过相似性检索以获取目标用户的近邻用户集合成为影响推荐性能的关键之一.为此，相比低效率的精确检索，近似最近邻检索技术在可接受的精度范围内具有更好的检索性能.δ-近似最近邻检索(Approximate Nearest Neighbor Search，ANNS)定义表述如下：

定义 1.(δ-近似最近邻搜索)在数据空间Rt中任取一个数据集合M，并给定近似系数δ>1.则空间Rt中任意一点q，若存在p∈M，使得对任意一点x∈M满足d(p,q)≤δ·d(x,q)，则称p是q的δ-近似最近邻.

局部敏感哈希(Locality-Sensitive Hashing,LSH)是目前实现ANNS最为广泛的索引技术之一，其具有高效的检索效率和良好的误差保证[14].LSH是一种特殊的哈希函数，将原始数据空间中的数据点哈希之后，相邻数据点哈希值相等的概率较大，将投影在同一区段，即落入同一哈希桶中，因此筛选出不相邻的数据点，降低计算复杂度的同时可以快速获取近邻用户集合.

3 原始评分数据修正与索引

3.1 物品类别偏好模型

在现实应用中，物品具有类别属性，用户间对于同一类别物品的评价数往往远大于同一物品的评价数.通过建立用户对物品类别的偏好模型可以实现对原始评分数据中相似用户群的细粒度划分.

设物品类别矩阵为Cngy，Cij=1表示物品i属于类别cj，Cij=0表示物品i不属于类别cj.同一物品也可能属于多个类别，如Ci(j+l)=1表示物品i也属于类别cj+l.故矩阵Cngy是一个0或1值填充的矩阵.设原始用户评分矩阵为Rmgn，m表示用户数，n表示物品数，Ru,i表示用户u对物品i的评分.物品类别偏好模型定义如下：

(2)

式(2)中，preCu,cj表示用户u对物品类别cj的偏好值；Ccj表示用户u评分物品中属于类别cj的物品集合；Ru,i表示用户u对物品i的评分；Ncj表示所有物品中属于类别cj的数量，对应于矩阵Cngy中cj列等于1的行数；Ncjo表示所有物品中不仅属于类别cj的数量，对应矩阵Cngy中不止cj列唯一等于1的行数；Noo表示所有物品中仅属于一类的数量，对应矩阵Cngy中仅唯一列等于1的行数.式中不仅考虑了某一类别在所有类别中的评分比重，而且还在物品空间中考虑该类别的比重，所以可以较好地衡量用户对某一类别的偏好值.

则用户u对物品i的类别偏好得分计算如下：

(3)

式(3)中，Ru,i表式用户u对物品i的评分；Ci表示物品i所属类别集合；preCu,cj表示用户u对类别cj的偏好值.

3.2 用户评分偏好模型

因主观差异性，不同用户评分时具有不同的评分偏好.某些用户评分标准较高，评分习惯偏低，而某些用户评分标准较低，评分习惯偏高，当这两类用户对某一物品打出相同评分时，评分标准较高的用户可能更加偏好这个物品.假设有评分类别集合{η1,η2,…,ηn}，例如标准五分制可以表示为{1,2,…,5}，则用户u对于评分类别ηi的偏好得分preRRu,ηi可以通过如下公式计算[10]：

(4)

式(4)中，Nηj<ηi是用户u所有评分中小于类别ηi的数量；Nηi是用户u评分类别为ηi的数量；Nu是用户u的所有评分数量.通过评分偏好模型，用户u对于评分值属于评分类别ηi的物品i的评分偏好得分为preRRu,ηi.

最终，线性融合物品类别偏好模型与用户评分偏好模型，如式(5)所示，并用finalRu,i替换掉原始用户评分矩阵Rm·n中的对应值，得到修正用户评分矩阵comRm·n.

finalRu,i=λpreCRu,i+(1-λ)preRRu,ηi

(5)

式(5)中，λ表示调节参数，用于合理分配两种模型在原始评分数据中的占比，λ∈[0，1]，最优值由后面实验部分给出.

3.3 修正评分数据索引与查询

3.3.1 基于p-稳态分布的局部敏感哈希

基于p-稳态分布的局部敏感哈希具有更低的时空复杂性和更高的查询准确率，对于高维稀疏数据具有高效的查询效率和稳定的运行时间[15，16].基于p-稳态分布的哈希函数族如下：

(6)

式(6)中，a是Rt内某一随机直线的方向矢量，且各分量相互独立并服从p-稳态分布，t维空间向量s投影到a所在的直线上，b∈[0,w]是直线上的平移量，该直线按w划分，⎣·」为向下取整操作，哈希值h(s)便是投影点所在直线的区段号，由相关实验证明，w=4时检索效果最好.

3.3.2 建立索引与查询

在实际查询时，为了提高相似点碰撞概率和不相似点不碰撞概率，需要对哈希函数进行“与构造”和“或构造”.“或构造”即构建复合LSH函数，随机，均匀地选取l个哈希函数连接起来形成l维的哈希函数组H={g:Rt→Ul}，其中g(s)=(h1(s),h2(s),…,hl(s)).所以，原始数据空间Rt中的数据点经过函数g(s)处理后降至l维，在降维的同时也保证了数据间的相似性.“与构造”即从H中随机均匀选取L个函数g1(s),g2(s),…,gL(s),构造L个哈希表，将原始数据集存储在L个哈希表中的不同桶中.

4 改进的协同过滤算法

近似近邻集合中的所有用户与u的相似性度量依据公式(1)计算，返回前k个相似度较高的用户，得到目标用户u的最近邻用户集合.基于最近邻用户集，采用加权策略计算目标用户u对物品i的预测评分Pu,i.

(7)

算法1.改进的协同过滤算法

输入：Rm·n，Cn·y，l，L，近邻数k

输出：用户u对物品i的预测评分Pu·i

1.FOR(eachu∈Ru,g)DO

2.FOR(eachi∈Ci,g)DO

3. ComputepreCu,cj,preCRu,iBy Formula(2)，(3)

4. ComputepreRRu,ηiBy Formula(4)

5. ComputefinalRu,iBy Formula(5)

6.comRm·n←ReplaceRu·iWithfinalRu,i

7.g(u)=(h1(u),h2(u),…,hl(u))

8.YmgL=(g1(u),g2(u),…,hL(u))

9.ENDFOR

10.ENDFOR

11.FOR(eachu∈comRm·n)DO

12. Compute ANN FromYm·L

13. ComputekNN From ANN By Formula(1)

14. ComputePu·iFromkNN By Formula(7)

15.ENDFOR

算法1的3-8行表示对原始评分数据的修正、降维和索引.算法1的12-14行表示依次计算近似近邻集合、k近邻集合和最终的预测评分.

5 实验设计与结果分析

5.1 实验数据集和算法评价指标

5.1.1 实验数据集

本文采用推荐算法经典测试数据集MovieLens 100k，该数据集包含943位用户对1682部电影的90570次评级.实验时，将原始数据集按照8：2比例随机划分为训练集和测试集.实验中，取5次实验的算术平均值作为最终结果.

5.1.2 评价指标

本文采用统计精度度量方法即平均绝对误差(Mean Absolute Error,MAE)来测试在不同参数条件下的推荐质量，MAE值越小，推荐质量越高.其定义如下：

(8)

式(8)中，Pi表示预测用户评分向量，Ri表示实际用户评分向量，m表示用户数.

另外，采用top-N推荐算法中最为常用的两个指标准确率(Precision)和召回率(Recall)来更加细致和精准地对比本文算法与其它相关算法的推荐质量.准确率和召回率定义如下：

(9)

(10)

式(9)和式(10)中，U是测试集所有用户集合；T(u)是训练集上对目标用户u的推荐列表；L(u)是目标用户u测试集上喜欢的物品集合.

5.2 结果分析

1)不同调节参数λ和组合哈希函数个数l下的MAE值.

本文推荐质量的高低主要依赖于调节参数λ，组合哈希函数个数l，哈希表个数L，其中L的取值又依赖于数据集大小和实际运行内存大小，所以根据实际实验情况取L=8.至于λ,l的取值则通过MAE的实验结果来确定.实验时，针对不同的l值，计算在取不同λ值的情况下MAE的变化趋势，λ∈[0,1]，步长为0.2.实验结果如图1所示.

图1 不同调节参数λ与组合哈希函数个数l下的MAE值

由图1数据可知，当调价参数λ=0.6时，对于所有不同组合哈希函数个数l的MAE值都取得最小，故本文取λ=0.6.这一结果直观反映了在用户评分中，物品类别偏好相比于用户评分偏好具有更大的比重，也符合客观事实.此外，当l=15时，在不同的调节参数λ下，MAE值均取得最低，故本文取组合哈希函数个数l=15.

2)相似协同过滤推荐算法与本文算法的推荐质量对比.

结合前文分析，本文算法将与朱磊等提出的PTP-Item-CF、王永贵等提出的优化算法和李红梅等提出的优化算法在准确率和召回率上做出对比.实验时，将针对不同近邻用户数k分别计算每个算法的准确率和召回率，k∈[20,120]，步长为15，本文算法中取λ=0.6，l=15，实验结果如图2，图3所示.

图2 不同k值下各算法准确率对比

图3 不同k值下各算法召回率对比

由图2，图3可知，随着近邻用户数k的不断增加，各算法的准确率和召回率均不断增加再趋于稳定，且对于不同算法，MAE值的稳定k值点均有所差异，但是本文所提算法的准确率和召回率无论在哪种k值条件下均高于其它算法.

3)相似协同过滤推荐算法与本文算法的运行效率对比.

为了验证本文采用的近似近邻检索技术能够显著提高近邻用户查询效率，本文算法将与其它3种算法在运行时间上做出对比.实验时，将针对不同近邻用户数k分别计算每个算法的运行时间，k∈[15,120]，步长为15，本文算法中取λ=0.6，l=15，实验结果如图4所示.

由图4可知，随着近邻用户数目的增加，基于传统检索方式的PTP-Item-CF的算法的运行时间急剧增加，而王永贵等提出的基于聚类优化的协同过滤算法的运行时间增加幅度相对较为缓慢.本文算法和李红梅所提优化算法由于采用相同检索方式，所以运行时间趋势较为一致，但是由于本文算法对原始评分数据有所修正，所以检索效率更高，运行时间更短.最终可知，本文算法相对其它算法具有更高的检索效率.

图4 不同k值下各算法的运行时间

6 结 语

本文针对传统协同过滤算法中存在的评分数据高维稀疏、用户评分偏好和物品类别偏好特征性较低等问题，提出一种基于对象属性和近似检索的协同过滤算法.通过线性融合两种偏好模型对原始评分数据进行修正，使得修正的评分值中可以合理地体现物品类别偏好和用户评分偏好，从而提高不同偏好的用户间的区分度.此外，针对评分数据的高维稀疏性，通过近似近邻搜索技术可以更加稳定和高效地获得近邻用户集合.由于本文算法的运行性能依赖与多个关键参数的设置，所以该模型对参数的敏感性较高.另外，文中偏好模型仅依赖于评分数据和物品类别信息，故对用户的偏好描述不够完善.下一步研究方向将在提高关键参数的自适应性的同时，利用文本挖掘技术从用户的文字评论信息中挖掘出更多偏好信息，完善偏好模型.