基于双向主题模型的协同过滤算法*
2013-09-15李改,李磊
李 改,李 磊
(1.顺德职业技术学院电子与信息工程系,广东顺德 528333;2.中山大学信息科学与技术学院,广东广州 510006;3.中山大学软件研究所,广东广州 510275)
推荐系统通过收集和分析用户的各种信息来学习用户的兴趣和行为模式,根据分析得到的用户的兴趣和行为模式,来为用户推荐他所需要的服务。这些系统的例子包括:CiteULike论文推荐系统(www.citeulike.org)为用户推荐各种其可能感兴趣的论文;Netflix电影出租系统 (www.netflix.com)为用户推荐各种其可能喜欢的电影。Google、Baidu、Yahoo等为用户提供个性化的新闻推荐和搜索服务。推荐系统中运用最广泛的是基于协同过滤的推荐算法[1-4]。
协同过滤的算法核心是分析用户兴趣,在用户群中找到与指定用户的相似 (兴趣)用户,综合这些相似用户对某一信息的评价,形成系统对该指定用户对此信息的喜好程度预测。近年来协同过滤的算法在国内外得到了广泛研究。传统的协同过滤算法面临数据稀疏性问题和评分数据的不平衡问题。许多模型提出通过引入额外的信息来解决这些问题以增强推荐效果:如推荐项目的内容信息[4],用户的社交网络信息[5-6],用户本身的属性信息[7]等。协同主题模型 (CTR)就是这类模型中最新的一种模型[4-5]。CTR模型通过在传统的基于矩阵分解的协同过滤算法中引入潜在狄利克雷分布(LDA)来学习文本形式的推荐项目的潜在主题分布[8],从而增强推荐效果。文本形式的推荐项目在现实生活中广泛存在,如科学文献,网页,微博等。如何有效的推荐这类文本形式的对象给所需要的用户是当前协同过滤领域的一个重要研究课题。
本文的主要贡献是:
①在CTR模型的基础上,提出了一种新的基于双向主题模型的协同过滤算法 (DCTR);
②提出了两种学习用户的主题分布向量的方法,并实验验证了两种方法的优劣。
③实验验证了DCTR算法的有效性。
本文具体内容安排如下:第1节介绍基本定义、LDA模型和CTR模型简介;第2节详细介绍本文所提出的基于双向主题模型的协同过滤算法。第3节针对所提出的算法进行实验验证,并对实验结果进行分析;最后第4节是本文的总结。
1 基本定义、LDA模型和CTR模型简介
1.1 基本定义
在本文中矩阵用斜体大写字母表示 (如:R),标量用小写字母表示 (如:i,j)。给定一个矩阵R,Rij表示它的一个元素,Ri.表示矩阵R的第i行,R.j表示矩阵R的第j列,RT表示矩阵R的转置。R-1表示矩阵R的逆。在本文中给定的矩阵R表示具有I个用户、J个对象的评分矩阵,矩阵U、V分别表示用户和推荐对象的特征矩阵。
1.2 LDA模型简介
潜在狄利克雷分布 (LDA)是一种最简单的主题模型,图1是LDA模型的概率图。
图1 LDA模型Fig.1 LDA model
假定有K个主题,即β=β1:K,是一个向量,其中的每个元素值表示一个词表的分布。这里的参数α是一个超参数,用于控制主题分布θ。LDA模型的运行过程如以下算法1所示。
算法1 LDA模型的运行过程
输入:超参数α,向量β。
输出:每个文本形式的推荐项目的主题分布θj。对于每个文本形式的推荐项目j:
①得到主题分布θj,θj满足参数为α的狄利克雷分布,即 θj~Dirichlet(α)。
②对推荐项目中的每个单词wjn
(i)得到该单词的主题zjn,zjn服从参数为θj的多项式分布,即zjn~Mult(θj)。
(ii)得到单词wjn,wjn服从参数为βzjn的多项式分布,即wjn~Mult(βzjn)。
对于文本形式的推荐项目,我们可以运用LDA模型学习该推荐项目的主题分布向量θj。从而可以对推荐项目j的特征向量实施约束,使其满足均值为 θj的正态分布,即Vj~N(θj,λ-1vIK),其中IK表示秩为K的单位矩阵。在协同过滤算法中引入LDA模型模型可以有效提高推荐性能。LDA模型的具体详细算法描述可见参考文献 [8]。
1.3 CTR模型简介
CTR模型是一种基于主题模型的协同过滤算法,图2是CTR模型的概率图。
图2 CTR模型Fig.2 CTR model
CTR模型综合了传统的协同过滤算法和概率主题模型的优点。其中用户的特征向量符合均值为0的正态分布,用于表示用户的兴趣;推荐项目符合均值为θ的正态分布,其潜在方差为ε。CTR模型的运行过程如以下算法2所示。
算法2 CTR模型的运行过程
输入:用户的正则化系数λu,推荐项目的正则化系数λv。
输出:矩阵R的逼近矩阵X。
②对于每个文本形式的推荐项目j;
(i)运用算法1所描述的LDA模型得到其主题分布 θj。
(ii)得到推荐项目的潜在方差εj,εj满足分布N(0IK)。
③对于每个评分点(i,j),得到相应的预测评分
在这里参数Cij是对于评分点的值Xij的信任参数,参数Cij的值越大,表示评分值Xij越可信;当参数Cij的值为0时,可解释为用户i对推荐项目j不感兴趣或没有留意到项目j。这就是有名的单类协同过滤问题。我们与文献 [4-5,9-11]中的处理方式一样,来为参数Cij赋予一定的权值
这里的a,b是控制参数,满足1≥a>b>0。
在CTR模型中,我们只是考虑对推荐项目j的特征向量实施约束,使其满足均值为推荐项目j的主题分布向量的正态分布,即Vj~N(θj,IK);其实我们也可以对用户的特征向量实施约束,使其也符合以某种主题分布向量为均值的正态分布。基于这个思想,我们提出了一种新的基于双向主题模型的协同过滤算法DCTR。
2 基于双向主题模型的协同过滤算法(DCTR)介绍
DCTR模型是一种基于双向主题模型的协同过滤算法,图3是DCTR模型的概率图。
图3 DCTR模型Fig.3 DCTR model
DCTR从用户和推荐项目这两个方面,分别对用户的特征向量和推荐项目的特征向量进行约束,使他们都符合以某种主题分布向量为均值的正态分布,即Ui~N(θi,IK),Vj~N(θjIK)。其中θi为用户Ui的主题分布向量,θj为推荐项目Vj的主题分布向量。DCTR模型的运行过程如以下算法3所示。
算法3 DCTR模型的运行过程
输入:用户的正则化系数λu,推荐项目的正则化系数λv。
输出:矩阵R的逼近矩阵X。
①对于每个用户i;
(i)得到其主题分布θi。θi的值有两种获得方法:
a)取用户i所评过的项目的主题分布向量的均值作为用户i的主题分布向量。
b)把用户i所评过的项目的描述文本的集合作为用户i的描述文本内容,重新运用算法1所描述的LDA模型来学习用户i的主题分布向量。
(ii)得到用户的潜在方差 εi,εi满足分布N(0IK)。
(iii)得到用户的特征向量Ui=θi+εi。即:Ui~N(θiIK)。
②对于每个文本形式的推荐项目j;
(i)运用算法1所描述的LDA模型得到其主题分布 θj。
(ii)得到推荐项目的潜在方差εj,εj满足分布N(0IK)。
(iii)得到推荐项目的特征向量Vj=θj+εj。即:Vj~N(θjIK)。
③对于每个评分点(i,j),得到相应的预测评分:
为了学习模型的参数,我们在这里提出了一种与文献[4-5]中类似的EM算法。模型的参数我们可以通过最大化公式 (2)得到
同理,得到求解Vj.的公式。
在这里Ci表示一个以矩阵C的第i行为对角元素,其它元素值为0的对角矩阵。Cj的定义与Ci的定义一致。从公式 (3)、(4)不难看出用户i的主题分布向量θi影响用户i的特征向量Ui,推荐项目j的主题分布向量θj影响推荐项目的特征向量Vj。
反复迭代运用公式 (3)、(4)更新U、V,直到本算法计算出的recall@M值收敛或迭代次数足够多而结束迭代。X=UVT,矩阵X即为矩阵R的逼近矩阵。
3 实验结果及分析
本节首先介绍本文实验所采用的数据集及评价标准。接着给出了本文所提出的基于双向主题模型的协同过滤算法的参数对实验结果的影响,并把所提算法的试验结果与其他几个经典算法的实验结果进行比较。
3.1 实验数据集
在本实验中,我们使用了与文献 [4]相同的CiteULike数据集。
CiteULike数据集是一个有关科学研究者参考科学文献的数据集。在这个数据集中每个用户维护有一个他敢兴趣的文献列表。这个数据集包括了5 551个用户对16 980篇科学文献的204 986个引用记录。这是一个0/1数据集。矩阵的稀疏度是99.8%。平均来说,每个用户引用了37篇文献,引用的范围最少10篇,最多403篇。93%的用户引用的文献数少于100篇。对于每篇文献我们把它的题目和摘要合起来作为它的描述性文本,我们移除其中的标点符号,通过TF-IDF方法选择其中的8 000个单词构成词库。这些文献的发表时间是从2004年到2010年。平均来说,每篇文献出现在12个用户的引用列表中,最少出现在一个用户的引用列表,最多出现在321个用户的引用列表。97%的文献出现在用户列表的次数少于40次。
我们采用5折交叉确认的方式来进行试验。对于出现在用户的列表中超过5次的文献,我们把它的评分点 (0和1)平均的分为5份。我们迭代的选择其中的4份为训练集,剩下的一份为测试集。对于那些出现在用户的文献列表中少于5次的文献都放入训练集。这就保住了测试集中的每个文献都出现在训练集中。对所有的用户求5次5折交叉确认的试验结果,取平均值作为该用户的最终试验结果,所有用户的实验结果求平均作为整个系统的最终试验结果。
3.2 实验的评价标准
本文实验采用 recall@M 作为评价标准[4-5],recall@M通过对模型的预测值进行排序,计算排序后的前M个项目中占所有该用户的测试项的比例来作为试验结果。当M值取某个较小的固定值的情况下,recall@M越大系统性能越好,这个系统的recall@M值为每个用户的recall@M值的平均值。recall@M的定义如下:
3.3 实验结果
本实验中的所有实验结果recall@M的M值均取值为200。参数Cij的取值为a=1,b=0.01。3.3.1 DCTR模型的参数对模型性能的影响分析从图4和图5可以看出随着λu和λv的增大,DCTR模型的性能均先升高,后下降。说明用户和推荐项目的特征向量偏离他们的主题分布向量不能太远,也不能太近,有一个临界值。从本模型的实验可以看出,λu和λv的最优值均是100。
3.3.2 基于DCTR模型的算法和几个经典的CF算法的性能比较 在这里我们将把DCTR模型和几个经典的CF算法的性能比较。本实验中要比较的几个CF算法分别是:
CTR算法,是文献 [4]中所提出的一种基于主题模型的协同过滤算法,它只是对推荐项目的特征向量实施约束。通过实验交叉验证,在该算法中λu取值为0.01,λv取值为100时,算法性能最好。
CTRUI算法,是基于本文所提出的DCTR模型的协同过滤算法,在该算法中,用户的主题分布向量取值为他所评过的所有项目的主题分布向量的均值。在该算法中λu和λv均取最优值100。
WPMF算法,是加权的基于概率矩阵分解的协同过滤算法[9-11]。通过实验交叉验证,在该算法中λu和λv取值为0.01时,算法性能最好。
CTRUIReal算法,是基于本文所提出的DCTR模型的协同过滤算法,在该算法中,我们把某个用户评过的所有推荐项目的文本描述的集合作为该用户的文本描述。通过对每个用户运行LDA算法,来得到该用户的主题分布向量。在该算法中λu和λv均取最优值100。
图6中横轴表示各个算法的迭代次数,纵轴表示各个算法的recall值。
图6 基于DCTR模型的算法和几个经典的CF算法的性能比较Fig.6 The performance comparation of DCTR model and several classical CF methods
从图6可以看出基于DCTR模型的两个协同过滤算法CTRUIReal算法和CTRUI算法在recall性能上均优于CTR算法和WPMF算法,随着迭代次数的增加性能的差异越来越明显,这说明对用户和推荐项目的特征向量分别引入主题模型进行约束能够有效提高算法性能。并且CTRUIReal算法的性能优于CTRUI算法的性能,这说明相比于取评过的推荐项目的主题分布向量的均值作为该用户的主题分布向量,通过主题模型直接学习用户的主题分布向量更为可靠。还可看出基于DCTR模型的两个协同过滤算法CTRUIReal算法和CTRUI算法的收敛速度也明显快过CTR算法和WPMF算法,这也进一步说明了本文所提算法的有效性。
4 总结
本文在传统的矩阵分解模型和主题模型的基础上提出了一种新的基于双向主题模型的协同过滤算法,它运用LDA算法从用户和推荐项目两个方向对用户和推荐项目的特征向量进行约束,以便更有效的推荐文本形式的对象给所需要的用户。在真实的数据集上的实验结果表明:在recall@M性能指标下,基于本文所提出的DCTR模型的协同过滤算法的性能明显优于几个传统的协同过滤算法。在以后的工作中我们还将研究本文所提算法的并行化问题。
[1]WU J L.Collaborative filtering on the netflix prize dataset[D].Peking University,2010.
[2]RICCI F,ROKACH L,SHAPIRA B,et al.Recommender system handbook[J].Springer,2011,12 -120.
[3]罗辛,欧阳元新,熊璋,等.通过相似度支持度优化基于K近邻的协同过滤算法[J].计算机学报,2010,33(8):99-105.
[4]WANG C,BLEI D.Collaborative topic modeling for recommending scientific articles[C]∥In ACM KDD,2011,448-456.
[5]PURUSHOTHAM S,LIU Y,KUO C J.Collaborative topic regression with social matrix factorization for recommendation systems[C]∥In ACM ICML,2012,1255-1265.
[6]MA H,ZHOU D,LIU C,et al.Recommender system with social regularization[C]∥In ACM WSDM,2011,287–296.
[7]LI Y,HU J,ZHAI C,et al.Improving one-class collaborative filtering by incorporating rich user information[C]∥In ACM CIKM,2010,959–968.
[8]BLEI D,NG A,JORDAN M.Latent Dirichlet allocation[J].Journal of Machine Learning Research,2002,993-1022.
[9]PAN R,ZHOU Y,CAO B,et al.On e-class collaborative filtering[C]∥In IEEE ICDM,2008,502-511.
[10]PAN R,MARTIN S.Mind the gaps:weighting the unknown in large-scale one-class collaborative filtering[C]∥In ACM KDD,2009,667-675.
[11]YANG X,STECK H,GUO Y,et al.On top-k recommendation using social networks[C]∥In ACM RecSys,2012,67-74.