基于内存的协同过滤算法

基于内存的协同过滤算法类似于机器学习中的懒惰算法,该算法在处理个性化推荐问题时不建立模型。相反，它是利用整个用户-项目评分数据集来产生推荐结果,基于该算法的推荐系统利用统计技术搜索出一组用户或一组项目,我们称之为邻居,他们与待推荐用户或项目有一致的兴趣偏好或相似的项目属性。

因为使用的是整个用户-项目评分数据集,因此该类算法的可扩展性不高。根据选择放入的最近邻的方法的不同，又可以将基于内存的协同过滤算法分为基于用户的算法和基于项目的算法。

基于用户的算法

基于用户的协同过滤算法主要针对用户而言,也就是找到品味相似的用户。该协同过滤算法可以分为两步:最近邻选择和用户偏好预测。

最近邻选择阶段,根据其他用户对待推荐用户的历史项目偏好相似程度来选择。关于相似程度的计算已经有很多算法被提出,其中应用比较普遍的余弦近似度计算和pearson相关系数。

需要注意的是，余弦相似性度量方法中没有考虑不同用户的评分尺度问题,修正的余弦相似性度量方法通过给每个维度减去用户对项目的平均评分来改善上述缺陷。

此外，Herlocker等人提出了使用Sperman相关函数来选择最近邻,通过实验和Pearson相关系数进了对比,证明其计算结果和使用Pearson相关系数相似,并且在小规模数据集中使用Spearman的效果比其他相似度度量方法要好。

另外,信息理论中的熵理论也被应用到了协同过滤中。Breese提出了其他计算度量,一个称之为default voting,被用来对数据进行平滑,由于相当一部分项目很少有用户购买和评价,使用这些项目来选择最近邻就会产生很大的误差,因此需要对数据进行平滑处理。另外一个度量称为inverse user frequency,被用来对项目的流行度进行加权处理。Herlocker在实验过程屮还发现,使用Pearson相关系数进行相似度计算时,考虑inverse user frequency时的预测结果反而比不考虑的效果更差。一般情况下,多数相似度的计算结果都会有相对较好的预测结果。但由上述情况可以看出,度量函数的选择很大程度上取决于背后的测试数据集。

了解了如何计算相似度后，用户对指定项目的偏好采用如下方法计算：

function P(a,i) //预测用户a对未评分项目i的评分
{
    var avga=a.ScoreAverage(); //计算a用户评分均值
    var avgc=0; //计算用户邻居集的评分均值
    for(c in N) //用户邻居集为N
    {avgc+=c.ScoreAverage();}
    avgc/=N.length;

    var denominator=0;
    for(c in N)
    {denominator+=Math.abs(sim(a,c));}

    var numerator=0;
    for(c in N)
    {
        numerator+=sim(a,c)*(c.GetScore(i)-avgc);
    }

    return numerator/denominator;
}

基于项目的算法

由于用户-项目评分矩阵的极端稀疏性,传统的相似性度量方法不能有效的计算待推荐用户的最近邻用户,这样也会降低协同过滤推荐系统的推荐质量,通常的解决方法是计算项目间的相似性,使用用户对相似项目的评分来预测用户对未评分项目的评分,从而使得用户之间共同评分的项目比较多,可以有效地解决在用户评分数据极端稀疏的情况下,传统相似性度量方法存在的不足,得到比较准确的待推荐用户的最近邻用户。

基于项目的协同过滤算法基于这样的假设：待推荐用户经常购买的相似项目,那么给待推荐用户推荐的项目是应该与他经常购买的项目相似度较高的项目。

因此基于项目的算法主要利用待推荐用户对已有项目的喜好程度来预测他对推荐的未评分项目的喜好程度。项目的属性可以是对项目的语言描述,项目标签或者是分值等。

与先前类似，基于项目的算法通过计算项目间的相似性来选择最近邻项目,比较常用的相似度量算法在上一小节里已经介绍。当获取了项目的最近邻后,则指定用户对该项目的喜好程度将通过该用户对推荐项目的最近邻的喜好程度计算得到。计算方法有很多种,大致可以分为如下两类:

加权类

假如要估计用户对项目i的评分，那么加权的方法主要是通过计算用户u_a与项目i的相似的而且己经被用户u_a评过分的项目的分值之和。权重一般采用的是项目i和项目j之间的相似度。也就是说用户对项目j进行过评分,项目i与项目j的相似度比较高,则用户j的评分值将会更大的影响项目i的估计评分。计算方法如下：

function R(ua,i) //估计用户ua对项目i的评分
{
    var denominator=0;
    for(j in C) //项目邻居集为C
    {denominator+=sim(i,j);}

    var numerator=0;
    for(j in C)
    {
        numerator+=sim(i,j)*ua.GetScore(j);
    }

    return numerator/denominator;
}

回归类

回归方法与权相加方法相似,但是不是直接利用相似项的评分值,而是基于回归模型得到的近似评分值。在实际运用中,因为两个欧式距离比较大的评分矢量之间很可能会有比较大的相似度,所以通过余弦法或者相关系数法得到的相似度可能就会不太准确,也就是说,使用相似项的原始分数来计算预测值效果可能会比较差。所以回归方法采用的是用户基于回归模型得到的近似评分值而不是原始的评分值。回归模型可以用如下公式描述: