基于改进型启发式相似度模型的协同过滤推荐方法

张南　林晓勇　史晟辉

摘要：为提高协同过滤推荐方法的准确性和有效性，提出一种基于改进型启发式相似度模型的协同过滤推荐方法PSJ。该方法考虑了用户评分差值、用户全局评分偏好和用户共同评分物品数三个因素。PSJ方法的Proximity因子使用指数函数反映用户评分差值对用户相似度的影响，这样也可避免零除问题；将NHSM（new heuristic similarity model）方法中的Significance因子和URP因子合并成PSJ方法的Significance因子，这使得PSJ方法的计算复杂度低于NHSM方法；而且为了提高在数据稀疏情况下的推荐效果，PSJ方法同时考虑了用户间的评分差值和用户全局评分两个因素。实验采用Top-k推荐中的查准率和查全率作为衡量标准。实验结果表明，当推荐物品数大于20时，与NHSM、杰卡尔德算法、自适应余弦相似度（ACOS）算法、杰卡尔德均方差（JMSD）算法和皮尔逊相关系数算法（SPCC）相比，PSJ方法的查准率与查全率均有提升。

关键词：协同过滤推荐方法；启发式相似度模型；用户相似度；推荐效果；数据稀疏

中图分类号：TP181

文献标志码：A

0引言

互联网的信息量正变得越来越大，然而大量的线上信息也带来一些不便。例如，某个消费者希望在网上买一部智能手机，在做出决定之前他将非常困惑，因为他将浏览和比较大量的互联网上提供的智能手机信息。推荐系统就是为了解决这种问题而被发明的，它会自动为用户提供购买物品的建议。准确的推荐可以帮助用户快速找到他感兴趣的物品并且避免用户浏览大量的相关商品。推荐系统同时对经销商来说也是一个很好的助手，它可以向访问经销商网站的浏览者推荐网站内的商品，通过这样的方式经销商有可能将这些浏览者变成长期客户。

协同过滤方法[1]首先被发明用于邮件过滤，现在它已经非常广泛地用于推荐系统。它依据激活用户的相似度或者被激活用户评过分的物品的相似度提供推荐结果。协同过滤技术可以被分成两类：基于内存的方法和基于模型的方法[2]。基于内存的方法首先利用用户评分数据计算用户之间的相似度，然后将相似度值超过某个阈值的用户作为目标用户的邻居，最后根据这些邻居产生推荐结果。基于模型的方法的工作方式完全不同。它首先建立一个模型用于描述用户的行为，并用这个模型来预测用户对物品的评分。协同过滤方法的关键是计算用户之间的相似度，因此相似度计算的准确性将影响推荐的准确性。现在有许多相似度算法，例如：杰卡尔德相似度（Jaccard similarity， Jaccard）算法[3]、余弦相似度（COSine similarity， COS）算法[4]、皮尔逊相关系数（Pearson Correlation Coefficient， PCC）算法[5]。除了协同过滤方法之外，还有许多方法被用于推荐系统，例如：语义推荐、社交推荐、基于内容的技术。

Jaccard方法[2]和均方差相似度算法（Mean Squared Difference， MSD）[9]也是很常用的计算相似度的方法，其中：Jaccard方法只考虑到了用户共同评分物品的数量，没有考虑用户评分的数值；而MSD方法只考虑到了用户评分的数值，但没有考虑到用户共同评分的物品数量。有研究人员认为可以将两种方法的优缺点相互弥补，为此提出了杰卡尔德均方差（Jaccard Mean Squared Difference， JMSD）相似度算法[10]。这三种相似度计算方法的计算公式分别如下：

以上九种算法可以分为三类：第一类只考虑了用户之间对同一个物品的评分而没有考虑共同评分物品的数量，包括COS、ACOS、PCC、CPCC和MSD方法。这类算法的缺点是会出现用户之间相似值偏高或偏低的现象。第二类只考虑了用户之间共同评分物品数而没有考虑用户之间对同一个物品的评分，Jaccard方法属于这一类算法；这类算法在数据不是很稀疏时会表现出大量用户之间相似度值相等的情况，这样就难以发现用户组之间的差异。第三类是混合型算法，这类算法至少考虑了两点与用户间相似度计算相关的因素，如SPCC、JMSD和NHSM方法。这些与相似度计算相关的因素都在前两类算法的设计思想中有体现，例如ACOS方法考虑了用户评分均值对相似度的影响，MSD方法考虑了用户评分差值对相似度的影响，Jaccard方法考虑了共同评分物品数目对相似度计算的影响。这类算法与前两类算法相比在计算用户之间的相似度值时更加准确。另外根据文献[11]中的实验结果显示，NHSM方法在数据稀疏的情况下能取得更好的推荐效果。

2本文算法

NHSM方法的五个因素中，有些因素还需要额外的计算，这使得NHSM方法十分复杂，而各个计算环节都会带来误差，多个计算误差相互叠加会增大偏离实际值的可能性，因此该方法的推荐效果在某些情况下不是很理想。本文将提出简化的NHSM方法。

2.1设计思想

首先介绍一下实际应用场景中的状况。在现实场景中，系统中用户只给系统中少部分物品评分，这样用户物品评分矩阵是非常稀疏的，所以应该将数据稀疏性问题引入到考虑范围中。下面是本文方法的考虑因素：

1）考虑用户评分的不同非常重要。在文献[12]的实验部分可以发现，大部分相似度计算方法考虑到了用户评分的不同。综合第1章介绍的九种方法可以发现，有三种方式可以引入用户评分的不同，一种是类似余弦相似度方法的那种乘积形式的计算公式，一种是MSD方法中的差值平方的方式，还有一种是NHSM方法中的指数函数的形式。在实际情况中，用户间评分差值和相似度是成反比的关系，即相似度越高评分差值越小。因此可以直接采用指数函数倒数的形式，这样处理没有NHSM方法那么复杂，同时还可以避免乘积形式中零除现象的出现。

2）用户共同评分物品所占的比例不能被忽略。一些研究者认为应该考虑共同评分物品所占的比例对相似度计算的影响，在前面的介绍中可以发现，SPCC[8]、JMSD[10]和NHSM方法[11]都引入了用户共同评分物品所占的比例，它们的实验结果显示这三种方法都提升了推荐效果。

3）应该考虑到用户评分的局部上下文和用户评分全局偏好。在 NHSM方法[11]的设计思想中提到了这一条设计思想，而且它的实验结果显示，当数据集稀疏度越高时，NHSM方法相比那些只考虑了用户评分的局部上下文的方法推荐效果要好。

4）应该使用用户全局评分均值区分用户对商品是喜欢还是讨厌。在 ACOS方法[6]的设计思想中提到了用户评分偏好对相似度计算的影响。通过观察不同网站的评分页面可以发现，大多数页面中没有明显地提醒用户评分域的中间值是一个区分喜欢和讨厌的中间值，因此用户会根据自己的偏好进行评分。根据上述情况可以将NHSM方法中的Significance因子和URP因子合并。

5）NHSM方法[11]中Singularity因子可能不如作者认为的那么有效。可以假设这样的情景，当评分域为1～5，只有5个评分域且只有5个不同的评分时，假设用户1给物品1评分1，用户2给物品1评分5，用户3给物品1评分3，用户4给物品1评分3，可以发现用户1与用户2的Singularity值和用户3与用户4的Singularity值相同。这显然给相似度计算带来了误导。因为大多数评分数据集的评分粒度不够大，使用该因子不一定能使用户组之间区分度增大，反而增加了计算复杂度和计算误差。

综合所述，本文将NHSM方法中的五个因子简化为三个因子，并用一个更简化的方程来重新定义Proximity因子，同时将Significance因子和URP因子结合在一起重新定义了新的Significance因子，而且在将Singularity因子移除的同时保留原来的Jaccard′因子。

由于在PSJ方法的Significance因子已经考虑了用户全局评分喜好，所以PSJ方法中的Significance因子是将NHSM方法中的Significance因子和URP因子合并。

为了考虑共同评分物品的所占比例，PSJ方法仍然使用NHSM算法中的Jaccard′方法，通过实际的实验对比可知，它融合到PSJ方法中产生的推荐效果比原始的Jaccard方法融入到PSJ方法产生的推荐效果更好，它的计算方式定义如下：

图1表示各个相似度算法的相似度计算结果。由于这些矩阵是对称的，这里只列举出了矩阵的上半部分，行从左到右表示用户1～6，列从上到下表示用户1～6。

1）可以在图1（a）中发现用户1与用户2的相似度高于用户1与用户3之间的相似度。用户2的评分向量为（4，1，—，5，—，4，1），并且用户3的评分向量为（5，—，1，—， 5，5，1）。通过观察可以发现用户3有两个评分分值和用户1相同，而用户2只有一个评分和用户1相同，这两个用户的其他的评分大致与用户1相同。因此用户1与用户3的相似度应该高于用户1与用户2。这个错误也发生在ACOS方法中，PSJ方法纠正了这个相似度计算错误。

2）仔细观察用户1与用户3的评分向量，在图1（c）中可以发现，用户1与用户3的相似度达到了0.997，用户1与用户3之间只有两个相同评分物品，这个值跟实际情况相比偏高，这个问题也发生在CPCC、SPCC和MSD方法中。在PSJ方法中的计算结果是0.646，该结果足够用于描述用户1与用户3的相似度。

3）在图1（f）中可以发现，用户2和用户5的相似度与用户2和用户6的相似度相等。实际上，在表1中用户2与用户5对共同评分物品的评分差值还是比较大的，用户2与用户6的相似度应该高于用户2与用户5之间的相似度。在PSJ方法中用户2与用户5中的相似度是0.037，并且用户2与用户6的相似度为0.117，与实际情况相符。

4）在图1（c）中有许多相似度值为NaN，其产生是因为零除问题。这样的问题也发生在CPCC、SPCC、MSD和JMSD方法中。将JMSD和MSD方法比较可以发现，JMSD方法中NaN值的数量相对少一些。PSJ方法的计算结果中没有NaN值，这体现了PSJ方法使用指数函数的倒数的优势。

5）在图1（f）中许多的相似度值为0.4和0.5。当仔细观察表1中各个用户的评分向量后可以发现，这些用户之间是彼此不同的，这些用户之间的相似度值也应该是不同的，这样才能更好地区分他们。在PSJ方法的计算结果中这个问题得到了解决。

6）在图1（g）中许多用户的相似度值偏低，有些相似度值过于接近0。同时NHSM方法中用户和用户自己的相似度还是不同，即不等于1，这个问题也发生在SPCC方法中。在PSJ方法中这个问题得到了解决。

3实验与分析

3.1数据集

在实验中使用了最新的MovieLens数据集，该数据集被叫作ml-latest-small。它包括706个用户，8570部电影和100023个评分，每个用户至少给20部电影评过分。它与其他MovieLens数据集的不同之处是：它的评分粒度更细一些，其评分域是0.5～5.0，有10个不同的评分值。它的用户物品评分矩阵的密度是1.7%。

本文选取了该数据集中的所有用户和前5000部电影，每个用户至少给15部电影评过分，用于实验的用户物品评分矩阵密度仍然是1.7%。在实验过程中，数据集被分成两部分，80%的数据用于训练，剩下20%的数据用于测试。按照这样的数据处理方式在实验过程中一共进行了五次交叉验证，每次交叉验证的训练集和测试集都不相同。

3.2相似度计算对推荐的影响

实验设计：首先使用数据集里的数据建立一个用户物品矩阵；然后，用相似度计算方法计算用户之间的相似度，并建立用户相似度矩阵；接着，建立推荐列表。建立推荐列表的操作又分成两步：1）通过用户相似度矩阵找出与用户最相似度值排在前k的用户，用链表将他们从高到低记录下来；2）根据相似度值最高的用户给出的评分排列这前k位用户关注过的而目标用户从未关注过的物品，最终选取排在前n的物品推荐给目标用户。

对比方法分别是ACOS方法、SPCC方法、Jaccard方法、JMSD方法和NHSM方法。因为推荐的物品数量和最近邻居的数量将影响到推荐效果，所以本文将实验情景分成两种状况：第一种状况是当邻近用户数是定值而推荐物品数是变量，第二种情况是推荐物品数是定值而邻近用户数是变量。最终的每条实验数据都由五次交叉实验的结果求平均值得出。

在上述实验中每个算法都要进行35次用户用户相似度矩阵计算，在本章的3.2.4节中将通过用户用户相似度矩阵计算的平均时间说明PSJ方法的优越性。

3.2.1衡量尺度

在商业化推荐系统中，总是推荐给用户一个他或她可能喜欢的k件物品的列表，这种方式被称为Top-k推荐。本文对比实验也使用Top-k推荐，因此使用查全率和查准率[14-16]来衡量实验结果。

3.2.2推荐物品数

本节实验将邻近用户数设为定值20，推荐物品数从10到70变化。

图2展现的是当Top-k中k变化时不同方法查准率的变化。与NHSM、ACOS和SPCC方法相比，PSJ方法的查准率提升比较明显；当k=10时，Jaccard和JMSD方法的查准率与PSJ方法很接近；当k>20时，NHSM方法获得了比SPCC、JMSD和ACOS方法更好的查准率，而PSJ方法能获得最好的查准率。

图3展现的是当Top-k中k变化时不同方法查全率的变化。与ACOS和SPCC方法相比，PSJ方法的查全率提升明显；当k=10时，Jaccard、JMSD和NHSM方法的查全率与PSJ方法很接近；当k>20时，NHSM方法获得了比SPCC、JMSD和ACOS方法更好的查全率，而PSJ方法获得了最好的查全率。

图2和图3的实验结果表明，PSJ方法考虑的各种因素对提升推荐效果是有效的。

3.2.3最近邻居数量

本节实验将推荐物品数量设为定值50，最近邻居数从10到70变化。

图4展现的是当最近邻居数变化时不同方法查准率的变化。在整个实验过程中，PSJ方法能获得最高的查准率，与其他五种协同过滤方法相比，PSJ方法的查准率提升较为明显。当最近邻居数大于20时，除了ACOS方法外，其他方法的查准率都比较稳定；当最近邻居数在10～20时，ACOS方法的查准率下降很快，这是用户相似度计算偏差太大造成的。

图5展现的是当最近邻居数变化时不同方法查全率的变化。与查准率实验结果一样，PSJ方法能获得最高的查全率，与其他五种协同过滤方法相比，PSJ方法的查全率提升较为明显。

图4和图5的实验结果表明，PSJ方法在实验情景下与其他方法相比，其推荐效果也有明显提升。

3.2.4不同算法的计算时间

本节通过用户用户相似度矩阵的计算时间来对比PSJ算法与其他五种相似度算法。表2展示的是各个算法计算了35次用户用户相似度矩阵的平均计算时间。从表2的数据中可以发现，PSJ方法与NHSM方法相比计算时间缩短了9.85%，但与其他四种相似度算法的计算时间仍有差距，继续降低PSJ算法的复杂度仍然很有必要。

综合以上两组实验的实验结果，从两个不同情景说明了PSJ方法的有效性，其查准率与查全率与对比的五种协同过滤方法相比有不同幅度的提升；同时在实验中还对比了PSJ方法与其他五种方法计算用户用户相似度矩阵的平均计算时间，这些实验结果说明了PSJ仍然需要降低复杂度。

4结语

本文介绍了协同过滤推荐方法中使用的相似度计算方法，并在综合了这些相似度计算方法的优点之后，提出了PSJ方法的设计思路，并给出了PSJ方法的计算公式。PSJ方法是基于NHSM方法的改进方法，并且在设计时考虑到了数据稀疏状况对产生推荐结果的影响。它简化了NHSM方法的Proximity因子的计算，将NHSM方法的Significance因子和URP因子合并组成了自己的Significance因子。通过这两步简化，使得PSJ方法的计算复杂度相较于NHSM方法明显降低。在PSJ方法的讨论中，通过一个用户物品评分矩阵的例子验证了PSJ方法在相似度计算方面的准确性。在MovieLens的ml-latest-small数据集上对比实验结果验证了PSJ方法的有效性，结果表明，与对比的协同过滤方法相比，PSJ方法可以有效提升推荐效果，同时在一定程度上克服了数据稀疏情况对推荐效果的影响。然而，在更为稀疏的数据集上推荐效果如何，以及如何改进是下一步需要深入研究的内容。

参考文献：

[1]YANG X， GUO Y， LIU Y， et al. A survey of collaborative filtering based social recommender systems [J]. Computer Communications， 2014， 41： 1-10.

[2]CACHEDA F， CARNEIRO V， FERNNDEZ D， et al. Comparison of collaborative filtering algorithms： limitations of current techniques and proposals for scalable， high-performance recommender systems [J]. ACM Transactions on the Web， 2011， 5（1）： Article No. 2.

[3]KOUTRIKA G， BERCOVITZ B， GARCIA-MOLINA H. FlexRecs： expressing and combining flexible recommendations [C]// SIGMOD 09： Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2009： 745-758.

[4]ADOMAVICIUS G， TUZHILIN A. Toward the next generation of recommender systems： a survey of the state-of-the-art and possible extensions [J]. IEEE Transactions on Knowledge and Data Engineering， 2005， 17（6）： 734-749.

[5]RESNICK P， IACOVOU N， SUCHAK M， et al. GroupLens： an open architecture for collaborative filtering of netnews [C]// CSCW 94： Proceedings of the ACM Conference on Computer Supported Cooperative Work. New York： ACM， 1994： 175-186.

[6]AHN H J. A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem [J]. Information Sciences， 2008， 178（1）： 37-51.

[7]PATRA B K， LAUNONEN R， OLLIKAINEN V， et al. A new similarity measure using Bhattacharyya coefficient for collaborative filtering in sparse data [J]. Knowledge-Based Systems， 2015， 82： 163-177.

[8]JAMALI M， ESTER M. TrustWalker： a random walk model for combining trust-based and item-based recommendation [C]// KDD 09： Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 397-406.

[9]BOBADILLA J， HERNANDO A， ORTEGA F， et al. Collaborative filtering based on significances [J]. Information Sciences， 2012， 185（1）： 1-17.

[10]BOBADILLA J， SERRADILLA F， BERNAL J. A new collaborative filtering metric that improves the behavior of recommender systems [J]. Knowledge-Based Systems， 2010， 23（6）： 520-528.

[11]LIU H， HU Z， MIAN A， et al. A new user similarity model to improve the accuracy of collaborative filtering [J]. Knowledge-Based Systems， 2014， 56： 156-166.

[12]BOBADILLA J， ORTEGA F， HERNANDO A， et al. A collaborative filtering approach to mitigate the new user cold start problem [J]. Knowledge-Based Systems， 2011， 26： 225-238.

[13]ANAND D， BHARADWAJ K K. Utilizing various sparsity measures for enhancing accuracy of collaborative recommender systems based on local and global similarities [J]. Expert Systems with Applications， 2011， 38（5）： 5101-5109.

[14]CREMONESI P， KOREN Y， TURRIN R. Performance of recommender algorithms on top-n recommendation tasks [C]// RecSys 10： Proceedings of the fourth ACM conference on Recommender Systems. New York： ACM， 2010： 39-46.

[15]FOUSS F， PIROTTE A， RENDERS J-M， et al. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation [J]. IEEE Transactions on Knowledge and Data Engineering， 2007， 19（3）： 355-369.

[16]YU S J. The dynamic competitive recommendation algorithm in social network services [J]. Information Sciences： an International Journal， 2012， 187： 1-14.