基于KL散度与JS散度相似度融合推荐算法

胡 文，景玉海

(哈尔滨商业大学 计算机与信息工程学院，哈尔滨 150028)

现今信息爆炸式的增长，宣告着人们正处于一个无法从浩瀚信息海洋中高效筛选出自己所需信息的”信息超载”[1]时代.面临该亟需解决的问题，推荐系统[2]这一无需用户详细描述需求信息，而是依据其历史日常行为和数据，构建相应模型去挖掘用户需求和兴趣工具应运而生，大量推荐算法[3]被设计出来.

其中融合其他信息源，使得相似度计算准确率提高的变体协同过滤(CF)[4]算法思想更加普遍.Huang L等人[5]通过统一利用社会、顺序、时间和空间模式来表征用户的登记行为，将CPS系统中的异构流数据融入多模贝叶斯嵌入模型，来共同为用户决策推荐.Ren等人[6]将兴趣，地理，社会和分类相关性分数整合到推荐算法的概率矩阵分解模型PMF中，利用联合后的分数进行推荐.Ye等人[7]利用个人偏好、好友关系和兴趣点距离三方面因素，联合User-based CF(基于用户协同过滤)算法、建立在好友关系之上的协同过滤和应用地理位置信息的推荐方法提出混合CF(协同过滤)算法，让推荐精度有所提高.王啸岩等人[8]提出SoGeoCom融合推荐模型，该模型将用户社交关系数据、地理位置数据和兴趣点的评论信息这3个因素融合后进行兴趣点推荐.Hu等人[9]在进行推荐时应用了STT(Spatio-Temporal Topic)模型，将用户的概况与签到的时空主题相结合来提高推荐精度.

大体来讲，以上推荐算法在数据稀疏性缓解上取得了一定的成效，让推荐质量进一步提升，但也有一些不足：1)大多数算法都应用的是基于用户(User-Based CF)算法，时效性较强，但个性化不太明显，存在冷启动问题.2)在计算项目或用户相似度时仅使用用户签到的共同评分项，但由于用户-兴趣点签到矩阵具有高度稀疏性，则会使推荐结果不准确.3)训练模型花费较长的时间，模型计算复杂度较高.

为有效解决以上推荐时出现的问题及研究中包含的不完善之处，设计了一种基于KL散度和JS散度所求相似度融合的推荐算法，其基本内容为：首先将每个项目相关的评论文本信息进行主题建模计算项目间隐性相似度，再利用所有用户对每个项目的评分进行显性相似度度量，两者融合，最后在推荐生成阶段，将融合后的相似度加入到基于项目的协同过滤中，来生成得分最高的前N个项目进行推荐，让推荐系统中的冷启动问题得到缓解，在解决数据稀疏性问题方面也取得了较好的功效，降低了生成推荐时计算的复杂性，提高了推荐的质量.

1 相关工作

1.1 基于项目的协同过滤

基于协同过滤的推荐，即从用户历史签到记录角度进行推荐，可进一步分为基于内存的推荐和基于模型的推荐，基于内存的推荐就是传统的User-Based CF和Item-Based CF[10].User-Based CF时效性较强，Item-Based CF个性化较强.另外，User-Based CF存在冷启动问题，使推荐不易被用户阐释，Item-Based CF恰恰相反，不仅可以迅速推荐，而且可以令用户比较信服[11].本文在Item-Based CF算法基础上，提出基于KL散度与JS散度相似度融合的变体的Item-Based CF推荐算法.

1.2 隐含狄利克雷分布(LDA)

Blei等人在2003年提出LDA(Latent Dirichlet Allocation)主题模型[12].LDA又称三层(文档层(document)、主题层(topic)、词层(word))贝叶斯模型.通过无监督的学习方法来挖掘文档集中潜藏的主题信息，即通过LDA模型可以得到文档的各个主题的概率分布.在评论信息建模分析过程中，LDA模型不但兼顾了文本的多语义性，同时还起到降维的效果，即将document-word分布，映射为document-topic分布和topic-word分布.LDA模型如图1所示.

图1 LDA模型

其生产过程如下：对于一篇文档中的每个单词，LDA依据Dirichlet分布参数α得到某个document-topic分布θ并在topic多项式分布θ中抽取一个topic(用z来表示)，再则依据狄利克雷分布参数β得到当前topic-word分布Φ，然后从主题z所对应的word多项分布Φ中抽取一个word(用w来表示).将这个步骤重复N次，就生成了文档d.Φ即为word分布，θ即为topic分布，N表示document的word总数，M表示document的总数.

所有项目间评论的隐含相似性的挖掘过程即为以上生成过程的逆向推导过程.基于KL散度与JS散度相似度融合的推荐算法主要运用LDA主题模型根据项目的评论信息来判断每个项目所属主题的概率分布θ.

1.3 KL散度和JS散度

Kullback-Leibler Divergence(KL散度)又可以被叫做KL距离，作为信息论中统计变量间独立性的重要指标而存在.即从概率分布的角度去衡量2个变量间的距离[13].在连续区间D中如若P1和P2分别为两个不同的概率密度函数，那么离散变量KL散度见式(1)：

(1)

由于KL散度不具有对称性，即D(P1‖P2)≠D(P2‖P1)，为解决此问题，有人提出了JS散度来作为相似度衡量的指标.现有两个概率分布P1和P2.其JS散度公式见式(2).

(2)

本文经过LDA主题分配模型处理每个项目评论数据得到每个项目属于T个主题的概率分布后，利用JS散度去衡量任意两个项目基于主题概率分布的JS散度相似度，即为隐性反馈相似度.

2 KL和JS相似度融合的推荐算法

2.1 项目间KL散度相似度的定义及计算

在计算项目间KL散度相似度时主要使用了王永等[14]人在电影推荐上相似度计算方法.

定义1：在用户签到的实验数据集中,定义所有项目的集合为I={I1,I2,…,Ii}，每个项目的评分列表集合为List={List1,List2,…,Listi}，每个项目评分列表中有$a个范围在(1-5)之间的数字，即任意一个项目s评分列表List={r1,r2,…r$a}(其中s>=1且s<=i，$a为所有用户对项目s的评分总数量).

根据以上定义，假如存在任意两个项目I1和I2,将所有用户对它们的评分视作两个评分序列,记为List1和List2,根据公式(3)[14]可得任意两个项目I1与I2的KL距离D(I1,I2)为：

(3)

其中：PI1为项目I1的概率密度函数，max为评分的最大值(数据集的评分为1～5分),PI1r=$r/$a为项目I1的评分列表中分数为r的比率，$a为所有用户对项目I1评分的数量，$r为分值为r的数量，同理得到PI2r.

由于KL散度不具有对称性，即D(I1,I2)≠D(I2,I1)，最终采用的KL距离为式(4)所示[14]：

(4)

定义2：在得到任意两个项目之间的KL距离距离Dd(I1,I2)后，则可以计算任意两个项目之间的基于评分概率分布的KL相似度如式(5)所示[14]：

KL(I1,I2)=sim(I1,I2)=1/1+Dd(I1,I2)

(5)

于此同时初始化一个矩阵KL_Sim，用来存储任意两个项目间的相似性.

2.2 项目间JS散度相似性的定义及计算

为了让相似度的计算更加准确，本文在KL散度相似度的基础上基于评论文本信息在主题上的概率分布，引入JS散度再次进行项目间相似性度量.即应用LDA主题模型挖掘兴趣点相关的评论信息，学习项目的topic分布特征，并用topic向量表示出来，其中定义主题topic的数量为T，引入JS散度进行相似性度量.实现步骤如下：

1) 首先汇集任意项目所有评论的描述信息到一个document，再将所有document汇集成一个大文档，从而获得了一个包括超大量document的集合，其中的每一个document对应着一个项目.

2) 假定被推荐者偏好的topic数量为T(即topic维度为T)，任意两个项目为I1和I2.采用吉布斯采样法以及似然函数估计法，能够得出topic-word分布Φ和项目的主题分布θ，其中θ为T维向量，向量中的每个数字(即每一维)代表该项目相应topic下的分布的概率,则PI1=θI1,PI2=θI2.

3) 引入JS散度指标来衡量任意两个项目之间的相似程度.输入任意两个项目I1和I2主题分布PI1和PI2，利用JS散度计算任意两个项目的主题分布的概率之间的JS距离如式(6)所示:

(6)

定义3：在得到任意两个项目之间基于JS的相似度距离后，给出如下定义来计算任意两个项目之间的JS相似度如式(7)所示：

JS(I1,I2)=sim2(I1,I2)=1/1+JS(PI1‖PI2)

(7)

在得到任意两个项目间的相似度后，初始化一个矩阵JS_Sim，用来存储任意两个项目间的相似性.

2.3 将任意两个项目之间的相似度进行融合

定义4：将得出的基于KL散度的相似度和基于JS散度的相似度融合，即最终的相似度如式(8)所示:

S(I1,I2)=KL(I1,I2)*JS(I1,I2)

(8)

根据定义2和定义3所得的两个相似度矩阵KL_Sim和JS_Sim可得到相似性矩阵S=KL_Sim*JS_Sim=[S(I1,.I2)]n*n，如下所示：

根据项目相似矩阵S，可得到项目I1的K个最近邻居集合S(I1,K)，即为和项目I1最相似的K个项目的集合.

2.4 生成项目推荐列表

定义5：计算被推荐者u对项目I1的最终评分Pu,I1如式(9)所示：

(9)

其中：ruI2为用户u给项目I2的评分，S(I1,I2)为项目I1和项目I2的相似性.根据预测值Pu,I1，最终排序可以做前Top-N个项目推荐，即取预测值最高的前N个项目作为用户的项目推荐集.

2.5 本文算法实现

基于上述分析，本文提出基于KL和JS相似度融合的推荐算法如算法1所示：

算法1：基于KL和JS相似度融合的推荐算法

输入：item_list,P, T, N,KL_Sim,JS_Sim.

输出：为目标用户u推荐其可能感兴趣点列表

for m,n in enumerate(item_list):

KL_Sim.append(KL(m,n))

JS_Sim.append(JS(m,n))

return KL_Sim,JS_Sim

end for

S=KL_Sim*JS_Sim

S(m,K)=get_SK(S)

Top_N_List=Top_N(S(m,K),run)

return Top_N_List

输入包括目标用户在内的带有评分和评论信息的所有项目列表item_list，与目标用户u最相似的项目数量P，主题数量T，推荐项目数量N.

首先:利用式(5) 计算任意两个项目之间KL相似度KL(m,n)，得到基于KL(m,n)的相似度矩阵KL_Sim；

其次:利用式(7) 计算任意两个项目之间JS相似度JS(m,n)，得到基于JS(m,n)的相似度矩阵JS_Sim;

然后:利用式(8)，得到任意两个项目之间的相似度矩阵S，通过get_SK函数得到最近邻居项目集合S(m,K)；

最后:利用式(9)，将得分最高的前K个项目形成Top_N_List列表推荐给目标用户u.

3 实验结果分析

为验证本文推荐算法相对于传统算法的优越之处，将本文推荐算法与传统的推荐算法应用于兴趣点(POI)推荐当中，得出实验结果，通过对比与分析，进而得出结论.

3.1 实验数据集

本节使用从美国最大点评网站Yelp数据集收集的数据进行数据分析.Yelp数据集包括1 326 101个用户和174 567个兴趣点.此外Yelp还包括了5 261 669条评论和49 626 957个朋友友谊对，统计结果及数据格式见表1～3所示.

表1 Yelp数据集统计

表2 社交关系数据格式

表3 评分与评论文本格式

3.2 评价指标

为验证推荐算法的性能，特使用准确率(Precision)和召回率(Recall)这两个衡量指标对Top-N兴趣点推荐进行评测.Precision和Recall是实验数据集上多组用户的平均值.

其中：Ivisited表示测试数据集中被推荐者已经留下签到数据的POI集合.Ire表示前N个被推荐的POI集合.

3.3 实验结果及分析

本文主要使用的是基于用户友谊对之间的兴趣点访问数据，为测试算法，按照7∶3的比例将每个数据集随机分成70%的训练集和30%的测试集并且考虑到算法的准确性，将签到次数少于3的朋友用户和POI除去.同时本文主要和基于用户共同评分项的利用余弦相似度计算兴趣点间相似性后，再融入到传统的Item-Based CF算法做POI推荐形成对比，得出实验结论.本文算法与对比算法描述如下：

1)传统方法(Cos-ItemCf)，基于余弦相似度的协同过滤(CF)推荐算法，该方法只利用用户的共同评分兴趣点计算相似性，在没有加入POI相关的上下文信息的情况下，在传统的Item-Based CF算法中应用做前Top-N个POI推荐.

2)本文算法(LDA-ItemCf)，基于所有用户对每个兴趣点的评分列表，使用KL散度计算任意两个兴趣点之间的显性相似度，基于每个兴趣点的评论信息，结合LDA模型使用JS散度挖掘兴趣点之间的隐性相似度.将显性相似度和隐性相似度融合后，融入到Item-Based CF算法做前Top-N个POI推荐.

3.3.1 影响参数对比分析

从图2、3中可以看出相似度融合后的方法准确率和召回率都高于传统的Cosine计算的相似度的方法.即表明使用本文方法在推荐中出现在用户喜欢列表中的兴趣点数增加，提高了推荐的准确性.

图2 #P-nearest neighbors

图3 #P-nearest neighbors

从图4、5中发现，实验中LDA的Topic数量影响最终的推荐结果.Topic数量增多，准确率和召回率也在上升，在Topic数量为60的时候达到最优推荐效果.

图4 不同Topic数量下的两个方法的准确率对比图

图5 不同Topic数量下的两个方法的召回率对比图

3.3.2 最终推荐对比分析

经过使用多组数据进行参数调整的分析验证后，将最相似的兴趣点数量设置为80，LDA主题数量设置为60，将产生前Top-N个兴趣点推荐给用户，如图6、7得到了本文算法与传统的基于项目的POI推荐算法的推荐比较结果.

从图中可以明显看出：因为其签到数据存在数据稀疏性问题，所以从实验所得的准确率和召回率来看兴趣点推荐算法的精度不是很高.由于Precision和Recall的计算公式的性质.当推荐列表中被推荐的POI数量增加时，Precision降低、Recall上升.其中本文的基于KL和JS相似度融合后的推荐方法在准确率和召回率方面都高于传统的基于Cosine计算相似度的方法，在一定程度上缓解了传统方法依赖于用户共同评分项计算POI相似度的问题，提高了推荐的质量.

图6 不同被推荐POI数量下的两个方法准确率对比图

图7 不同被推荐POI数量下的两个方法召回率对比图

4 结 语

传统方法在计算项目间相似性时，通常只考虑了用户共同评分项，在实际应用中，由于数据集的稀疏性会导致共同评分项十分稀少，造成在计算项目间相似性时存在一定的误差，影响推荐效果.本文引入信息论中的KL散度和JS散度，分别计算项目之间基于评分值概率密度分布的相似性和基于评论信息的主题概率密度分布的相似性，将两个相似性融合后应用到传统的基于项目的协同过滤算法中进行兴趣点推荐.在一定程度上缓解了数据稀疏性的问题，使得计算项目间相似性时不仅局限在共同评分项，与此同时，充分利用了兴趣点评分和评论的信息，增强了推荐的可靠性和准确性.在真实的数据集上进行对比实验分析表明，该方法具有良好的性能且优于传统的基于项目进行兴趣点推荐的协同过算法，具有良好的应用价值.