Weighted-Tau Rank: 一种采用加权Kendall Tau的面向排序的协同过滤算法

孙建凯，王帅强，马 军

(山东大学 计算机学院，山东 济南 250101)

1 引言

随着互联网的发展和普及,网络己成为人们获取各种信息和数字化资源的重要途径。然而,网络上日益增多的资源在给用户带来更多选择的同时,也使用户需要花费更多的时间和精力来查询自己想要的资源。于是,如何解决信息过载问题，帮助用户更快地找到所感兴趣的资源己成为当前研究的热点。个性化推荐技术的提出为信息过载问题提供了一个行之有效的解决方案。该技术旨在通过挖掘个体用户的兴趣喜好,把用户最感兴趣的资源从浩瀚如海的网络信息中抽取出来推荐给相应用户。个性化推荐也逐渐成为了电子商务领域不可缺少的工具之一,比如Amazon、Netflix和豆瓣等许多网站都广泛使用了个性化推荐技术。

协同过滤推荐系统是一种广泛应用的个性化推荐技术[1]。其最大的优点就是只需要评分信息，而对待推荐的对象没有特殊要求，因此能处理电影、音乐等难以进行文本结构化处理的对象[2]。它分为面向评分的和面向排序的两种[3]。面向评分的系统根据用户的历史评分信息来计算用户之间的相似度，利用相似度高的近邻的评分来预测目标用户对待推荐产品的评分。然而，当用户之间的评分差别较大时，基于评分的相似度度量方式便丧失了捕获用户之间偏好的相似性的能力。可由例1来说明：

例1.用户u和v对电影《画皮》和《盗梦空间》的实际评分分别是<1,2>和<4,5>。由基于评分的相似度度量方式，比如夹角余弦的方法来计算用户之间的相似性，两用户的相似度很小。但考虑到用户的偏好，两人却是一致的，都是相比于《画皮》更喜欢《盗梦空间》。

而且当前的面向评分的协同过滤系统只是对单独的产品(即例1中的电影)独立地预测评分，而没有考虑用户对产品的偏好关系。与之不同，面向排序的协同过滤系统则是根据用户对产品的排序来计算用户之间的相似度，进而产生满足目标用户偏好的推荐列表。

然而当前面向排序的协同过滤算法只是考虑用户对产品对的偏好是否一致，而忽略了偏好的程度。即使不同用户对同一产品对的偏好相同，但用户之间偏好的程度却有可能千差万别。可由例2说明。

例2. 用户u和v对电影《画皮》和《盗梦空间》的实际评分分别是<1,5>和<4,5>，由评分可知，两位用户的偏好都是相比《画皮》更喜欢《盗梦空间》。从偏好程度上来说则是用户u不喜欢《画皮》(评分不大于3分)却非常喜欢《盗梦空间》，而用户v虽对两部电影都喜欢，但相比还是更喜欢《盗梦空间》多一些。因此用户u与v相比，相对于《画皮》而言偏好《盗梦空间》的程度更深。过去的很多算法却只会将u和v的这一偏好一致对待，而忽略了两者的偏好程度不同这一重要信息。

当前面向排序的协同过滤算法不仅没有考虑用户对产品对的偏好程度，而且还忽略了偏好的流行度在区分用户时所发挥的作用。例3说明如下。

例3. 假设所有的用户相对于《画皮》都更喜欢《盗梦空间》，也就是说该偏好在用户间非常流行。这种流行的偏好就像一种常识性信息，即大家都知道任何人相对于《画皮》都会更喜欢《盗梦空间》，因此也就丧失了区分用户的能力。也就是说偏好在用户间越普遍，其区分用户的能力就会越弱。

为解决上述问题，本文提出了一种面向排序的协同过滤算法，能够结合用户对产品对的偏好程度以及偏好的流行程度，从而产生具有较好用户体验的推荐结果。算法主要流程如下： 首先提取出用户对每个产品对的偏好，利用类似TF-IDF的策略对用户的偏好程度以及偏好的流行度进行加权；然后利用加权的Kendall Tau相关系数计算用户间的相似度，这也是本文算法被称为Weighted-Tau Rank的原因；接着利用与目标用户相似度高的近邻预测目标用户对特定产品对的偏好；最后利用舒尔茨方法进行偏好融合和排序以产生最终的推荐列表。

本文结构组织如下： 第2节回顾相关研究工作；第3节详细论述本文采用的Degree-Popularity加权方式以及训练和预测模型；相关实验和分析在第4节给出；最后总结全文。

2 相关工作

协同过滤是现在电子商务推荐系统中很常用的技术。它能够充分利用用户的历史评分信息。这些评分信息可以是显式(explicit)值也可以是隐式(implicit)值。比如说在豆瓣网上用户可以用1～10的数值来表示对某电影的喜好程度，这些评分信息就是显式值。而在淘宝上用户的浏览、点击、评论、收藏和购买的行为则是隐式值。相比显式值，隐式值因包含较多的噪音而难以收集和处理。

在讨论与协同过滤算法的具体细节之前，我们先引进一些与之相关的概念以及符号表示。设U={u1,u2,...,um}为有m个用户的集合，I={i1,i2,...,in}为有n个产品的集合。用户对产品的评分信息可以用一个m×n的矩阵R来表示，R中的元素ru,i表示用户u对产品的评分。ru,i=0表示u未对i评分。另外Ui表示所有对产品i评过分的用户的集合，Iu则表示用户u所有评过分的产品的集合。

面向评分的协同过滤系统的算法可以分为两类： 基于记忆(memory-based)的和基于模型(model-based)的算法[4]。基于记忆的算法是根据历史评分信息进行预测。其中一个最常用的技术就是基于近邻(neighbor-based)的方法[5]，其工作流程主要分为邻居发现和评分预测两步[6]。基于模型的算法收集评分数据进行学习并推断用户行为模型，进而对某个产品预测评分。

面向排序的协同过滤算法不再关注预测评分的精度，而是根据用户的偏好向目标用户产生一个推荐列表。面向排序的协同过滤系统一般分为两个步骤： 邻居发现和预测排序。邻居发现即系统要找出与目标用户相似度高的用户作为其近邻。预测排序在此基础上系统根据近邻对特定产品对的偏好来预测目标用户的偏好，然后对预测的偏好进行融合和排序以产生一个尽可能满足目标用户偏好的推荐列表。具体细节将在第3节详细讨论。

一系列面向排序的协同过滤算法的提出丰富了该领域的研究。比如，CoFiRank[7]采用最大化边界的矩阵分解技术直接优化推荐列表，以产生一个结构化的预测输出。而ListRank-MF[8]则将矩阵分解产生的潜在特征用于学习排序算法的训练，从而产生推荐列表。文献[3]提出的EigenRank算法则根据用户对产品对的偏好利用标准的Kendall Tau Rank相关系数计算用户之间偏好的相似性，然后再根据邻居对特定产品对的偏好预测目标用户的偏好。通过标准的Kendall Tau Rank相关系数[9]来计算用户之间排序的相似度T的公式见式(1)。

其中，Nc是用户u和v中排序相同的产品对数，Nd则是排序不同的产品对数，N=|Iu∩Iv|。

为判断用户之间对同一个产品对的偏好是否相同，我们需要引入一个指示函数sgn，对每一个产品对，sgnu,v(k,l)满足如下定义：

用户u和v对产品ik、il排序一致时，sgnu,v(k,l)=1；不一致时sgnu,v(k,l)=-1。根据式(2)我们得到式(3)。

因此式(1)中Tu,v的计算也可以用式(4)表示：

Tu,v的取值范围为[-1,1]，值越大表示用户之间的相似度越高。具体的计算可由例4来说明。

例4. 假设我们有产品集合{i1,i2,i3},从产品集合中抽取产品对的集合为{,,}。用户u对这三个产品的评分为3、4和2，用户的评分则是2、4和3。则用户u从产品对的偏好集合为{i1i2,i1≻i3,i2≻i3}，用户v对产品对的偏好集合则为{i1i2,i1≻i3,i2≻i3}。可知Nc=2，Nd=1。两用户u、v之间的相似度

然而，EigenRank只是考虑了用户间产品偏好的一致性，而没有考虑用户对不同产品对的偏好程度以及偏好在用户间的流行度。我们在之前的工作[10]中对表示为词项的用户偏好进行了类似TF-IDF的加权，然后采用向量空间模型进行用户间相似度的计算,但偏好融合与预测部分采用的算法和EigenRank一样均为贪婪算法，效率不高。

3 Weighted-Tau Rank算法

本节将详细介绍本文提出的Weighted-Tau Rank算法，算法流程如下：

1) 从历史信息中抽取用户对产品对的偏好，即3.1节的偏好表示部分；

2) 然后利用3.2节的偏好权重度量偏好的程度以及流行度以便对该偏好加权；

3) 3.3节利用加权的Kendall Tau Rank相关系数计算用户间的相似度；

4) 3.4.1节选出与目标用户相似度高的用户作为近邻来预测目标用户对特定产品对的偏好；

5) 最后3.4.2节利用基于投票的舒尔茨方法进行偏好融合和排序以产生最终的推荐列表。

3.1 偏好表示

我们从用户u以及其评过分的产品集合Iu中抽取该用户的偏好集合为{ikil|ik,il∈I∧k

ikil表示用户对产品对ik和ik的偏好。ik≻il则表示相比产品il，用户u更喜欢ik；ikil则相反。

3.2 偏好权重

偏好权重的定义由两部分组成： 用户对产品对的偏好程度Degree和偏好在用户间的流行度Popularity。正如Term Frequency(TF)可用来描述文档的内容，Degree可以用来描述用户的爱好；正如Inverse Document Frequency (IDF)可用来区分该词项所在文档与其他文档，Popularity可以用来区分不同的用户。

3.2.1 Degree

偏好ikil的Degree值表示用户对产品对的偏好程度。根据用户对产品对的评分，我们可以得到该用户的偏好程度的信息。在本文中，我们采用类似TF的定义，如式(6)所示。

3.2.2 Popularity

Popularity可衡量偏好在用户集合中的流行程度。对偏好ikil，我们有两个实体：ikil和ik≻il，因此我们并不能直接使用类似IDF的公式log来计算Popularity值，其中|U|为用户的数量，Nikil为偏好ikil出现的次数。

对于用户的一个特定偏好ik≻il，该偏好的流行度，是相对于偏好ikil出现的次数而言的。因此我们应该把|U|修改为Nik≻il+Nikil。得到Popularity的一种可能的计算公式如式(7)。

但是式(7)的定义会出现例 5中描述的问题。

例5.有产品{i1,i2,i3,i4}，用户总数为10 000。有1 000名用户给i1,i2打过分，其中800名用户相对于i2更喜欢i1，其他200名用户偏好则相反，即Ni1≻i2=800，Ni1i2=200。对i3、i4，则有100名用户对它们评过分，其中Ni3≻i4=80，Ni3i4=20。

根据公式(7)有：λi1≻i2=λi3≻i4，λi1i2=λi3i4。虽然i1和i2、i3和i4的评分用户数有显著差异，但最后的比值却是相同的，公式(7)存在小样本问题。样本数越小，Nik≻il+Nikil越小，公式(7)得到的结果可信度就不高，不确定性就越大，因而结果需要较大地调整。相反，Nik≻il+Nikil越大，公式(7)得到的结果可信度就越高，就需要较小甚至不需要调整。为此，我们引入可信因子α，定义见式(8)。

最后综合考虑λikil和αik,il，偏好ikil的Popularity值的定义如式(9)。

其中，αu,ik,il值越小，可信度越低，λu,ikil调整的幅度就越大；相反αu,ik,il越大，与λu,ikil的差别就越小。

3.2.3 Degree-Popularity

和TF-IDF的加权方式类似，Degree-Popularity的值为Degree和Popularity两者的乘积。对用户u，偏好ikil的Degree-Popularity权重定义如式(10)。

3.3 相似度计算

在面向排序的协同过滤算法中，可以通过式(4)中的标准Kendall Tau Rank相关系数[3]来计算用户之间排序的相似度T。但从式(4)可以看出，Tu,v用户相似度的计算过程中，只是考虑了用户之间的偏好是否一致，而没有考虑偏好的程度以及偏好的流行度。为了能够综合考量用户偏好的一致性、用户偏好程度以及偏好的流行度，本文对式(4)进行改进采用加权的Kendall Tau Rank相关系数来计算两用户偏好之间的相似性，如式(11)所示。

其中,wk,l为用户u和v对偏好ikil权重的乘积，即式(12)。

3.4 排序预测

在3.2和3.3节中我们利用Degree-Popularity加权用户偏好，通过加权Kendall Tau Rank相关系数来计算用户之间的相似度。在这节我们讨论如何进行排序预测。排序预测主要分为两步： 偏好预测与偏好融合。

3.4.1 偏好预测

首先我们定义一个偏好函数Ψ。Ψ(i,j)>0表示相对于产品j用户更喜欢i。|Ψ(i,j)|大小表示用户对这两个产品的偏好程度。Ψ(i,j)=0表示用户对i和j没有偏好。Ψ有反对称的性质，即Ψ(i,j)=-Ψ(j,i)，但不保证具有传递性，即由Ψ(i,j)>0和Ψ(j,k)>0，并不能得到Ψ(i,k)>0。

接下来我们要借助近邻预测用户对未知产品对的偏好关系。我们将与目标用户u有相似偏好的用户记为u的邻居Nu。Nu中越多的用户对《盗梦空间》的评分高于《画皮》，我们就越有理由相信u相对于画皮更喜欢《盗梦空间》。具体定义见式(13)。

得到目标用户对未知产品对的偏好关系的预测结果后，我们要生成一个排序列表使其尽可能地满足Ψ的结果。然而由于Ψ不具有传递性，排序预测为NP完全问题[9]。文献[3]和文献[10]通过构建价值函数，利用贪婪算法最大化价值函数，得到近似最优解的排序列表。但这种方法需要构建价值函数的中间步骤，算法效率低。本文则不用构建价值函数，直接利用基于投票的舒尔茨方法来解决偏好融合与排序问题，能够大大提高效率。

3.4.2 偏好融合

偏好融合是指根据Ψ对目标用户产生的偏好关系进行排序产生推荐列表的过程。本文利用舒尔茨方法来实现偏好融合以产生推荐列表。舒尔茨方法是Markus Schulze提出的投票算法。该方法能够利用用户有偏好的投票产生胜者列表。本文将Ψu(i,j)表示为用户u对产品对的投票，Ψu(i,j)>0表示用户将票投给i≻j，相反Ψu(i,j)<0则表示用户将票投给ij。|Ψu(i,j)|则为投票的权重。

算法1： 舒尔茨算法

# Input: d[i,j]，d[i,j]=Ψu(i,j).

# Output: p[i,j], the strength of the strongest path from item i to item j.

for i from 1 to C

for j from 1 to C

if (i ≠ j) then

if (d[i,j] > d[j,i]) then

p[i,j] := d[i,j]

else

p[i,j] := 0

for i from 1 to C

for j from 1 to C

if (i ≠ j) then

for k from 1 to C

if (i ≠ k and j ≠ k) then

p[j,k] := max (p[j,k],

min (p[j,i], p[i,k]))

end

4 实验结果与分析

4.1 实验设置

为验证本文所提算法的有效性，我们采用了两个具有真实评分的电影数据集： EachMovie和MovieLens。EachMovie中有74 418名用户，1 648部电影，约有281万条评分；MovieLens则有6 040名用户，3 883部电影，100万条左右的评分。

在实验过程中，为了保证目标用户和其邻居的共同评分的电影具有一定的数量，我们首先对数据集做了过滤操作： EachMovie中剔除了评分数小于100的用户，MovieLens中剔除了评分数小于50的用户。然后随机选取用户评分的80%用做训练，10%用于校验，其余的10%用于测试。

4.2 评价指标

对于面向评分的协同过滤系统，评价指标主要用于衡量系统预测评分的精度。比如精确度衡量的两个典型的指标平均绝对误差(Mean Absolute Error, MAE)和平均平方误差(Mean Squared Error, MSE)就用来衡量用户实际评分和预测评分之间的差异[11]。然而本文的算法是面向提高推荐列表排序的精度而不是预测评分的精度。因此本文采用的评价指标为Normalized Discounted Cumulative Gain(NDCG)[12]。对于给定的用户u，NDCG在第n位的值的定义如式(14)所示。

其中,Zu为归一化因子,ru,i为用户u对处于推荐列表第i位的电影的评分。最后对所有用户的NDCG值求平均：

NDCG值的取值范围为[0,1]，值越大，推荐效果就越好。对推荐的结果，大部分用户只会查看排在推荐列表前面的产品，因此排名相对靠前的产品对用户的价值相对较大，这就要求评价指标能够给予排名靠前的产品更多的关注。NDCG的分母log(1+i)随着排序位置的增加而增大，使得NDCG对排名靠前的产品比较敏感。

4.3 实验结果分析

我们使用现在两种比较流行的面向排序协同过滤算法: EigenRank[3]和CoFiRank[7]作为本文的主要对比方法。EigenRank使用标准Kendall相关系数来度量用户之间的相似性，通过邻居来预测用户对特定产品对的偏好，然后利用贪婪算法解决偏好融合问题，最后向用户产生一个有序的推荐列表。CoFiRank则利用最大化边界的矩阵分解技术，直接优化推荐列表，产生一个结构化的输出。同时，我们还使用了一种传统的面向用户的协同过滤算法，称之为UVS。UVS采用夹角余弦作为相似度的度量方式，采用利用近邻预测评分,最后根据产品的预测评分对用户的推荐列表排序。

图1和图2展示了在NDCG评测指标下，本文提出的算法Weighted-Tau Rank以及其他对比方法在MovieLens和EachMovie数据集上的表现。从中我们可以看出：

图1 MovieLens结果对比

图2 EachMovie结果对比

(1) Weighted-Tau Rank在两个数据集上结果的精确度要高于其他所有的对比方法。比如说，在MovieLens上，Weighted-Tau Rank的NDCG@1-2的结果为0.733和0.743，和EigenRank的0.690 8和0.713 8相比提高了6.1%和4.1%。在EachMovie上，Weighted-Tau Rank的NDCG@1-2的结果为0.733 9和0.744 7，和CoFiRank的0.681 3和0.699 6相比提高了7.7%和6.55%。这是因为EigenRank、CoFirank只是考虑用户对项目对偏好的存在情况，而没有考虑偏好的程度以及流行度，Weighted-Tau Rank则由于综合考虑了用户偏好的各方面信息，使得推荐效果更加精确。

(2) 在NDCG评测指标下，面向排序的协同过滤算法的效果要优于面向评分的协同过滤算法。这是因为UVS算法只关注预测评分的精度，但预测评分的精度和排序的效果两者之间并没有必然的联系，这从本文的实验结果中就可以看出。比如，在MovieLens上，本文提出的算法Weighted-Tau Rank的NDCG@1-2的结果相比UVS分别提高了9%和8%，而在EachMovie上，则分别提高了13.4%和12.7%。

(3) 在MovieLens上，EigenRank除NDCG@1之外，其他结果均优于CoFiRank。在EachMovie上，EigenRank的NDCG@1-2的值优于CoFiRank。Weighted-Tau Rank在所有数据集上表现是最好的，而UVS则是最差的。因此这四个推荐算法在MovieLens和EachMovie上的优劣关系为： Weighted-Tau Rank>EigenRank>CoFiRank>UVS。

5 结语

在本文中，我们提出了一种使用加权Kendall Tau Rank相关系数的面向排序的协同过滤算法Weighted-Tau Rank。本文的主要贡献有： 与其他的面向排序的协同过滤算法一致对待用户对不同产品对的偏好不同，Weighted-Tau Rank使用类似TF-IDF的Degree-Popularity加权策略对用户的偏好加权；与其他的面向排序的协同过滤算法需要构建价值函数利用贪婪算法进行偏好融合和排序不同，Weighted-Tau Rank直接利用基于投票的舒尔茨方法直接进行偏好融合和排序。在两个数据集上的实验结果也证明了Weighted-Tau Rank的有效性。我们未来拟开展的研究包括： (1)研究不同的加权方式对推荐效果的影响；(2)研究不同的相似度度量方式对推荐效果的影响；(3)优化算法，提高算法效率；(4)将推荐结果的多样性等因素考虑到算法当中去。

[1] Su X, Khoshgoftaar TM. A survey of collaborative filtering techniques[J]. Adv. in Artif. Intell. 2009,2009:2-2.

[2] Hu Y, Koren Y, Volinsky C. Collaborative Filtering for Implicit Feedback Datasets[C]//Proceedings of the 2008 Eighth IEEE International Conference on Data Mining: IEEE Computer Society; 2008: 263-272.

[3] Liu NN, Yang Q. EigenRank: a ranking-oriented approach to collaborative filtering[C]//Proceedings of the 31st annual international ACM SIGIR conference on research and development in information retrieval. Singapore, Singapore: ACM; 2008: 83-90.

[4] Sarwar B, Karypis G, Konstan J, Riedl J. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web. Hong Kong, Hong Kong: ACM; 2001: 285-295.

[5] 刘建国, 周涛, 汪秉宏. 个性化推荐系统的研究进展[J]. 自然科学进展,2008,19:15.

[6] Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions[J]. Knowledge and Data Engineering, IEEE Transactions, 2005,17:734-749.

[7] Weimer, Markus, Karatzoglou, et al. COFIRANK—Maximum Margin Matrix Factorization for Collaborative Ranking[C]//Proceedings of NIPS; 2007.

[8] Shi Y, Larson M, Hanjalic A. List-wise learning to rank with matrix factorization for collaborative filtering[C]//Proceedings of the fourth ACM conference on recommender systems. Barcelona, Spain: ACM; 2010: 269-272.

[9] Cohen W W, Schapire R E, Singer Y. Learning to order things[J]. Artif. Int. Res. 1999,10:243-270.

[10] Wang S, Sun J, Gao B J, et al. Adapting Vector Space Model to Ranking-based Collaborative Filtering[C]//Proceedings of CIKM; 2012.

[11] Gunawardana A, Shani G. A Survey of Accuracy Evaluation Metrics of Recommendation Tasks[J]. Mach. Learn. Res. 2009,10:2935-2962.

[12] Valizadegan H J R, Zhang R, Mao J. Learning to Rank by Optimizing NDCG Measure[C]//Proceedings of the Conference on Neural Information Processing Systems (NIPS); 2009.