查看“协同过滤算法”的源代码


== 什么是协同过滤 ==

协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤 (Collaborative Filtering, 简称 CF)，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪部，你会怎么做？大部分的人会问问周围的朋友，看看最近有什么好看的电影推荐，而我们一般更倾向于从口味比较类似的朋友那里得到推荐。这就是协同过滤的核心思想。

== 协同过滤的原理 ==

要实现协同过滤的推荐算法，要进行以下三个步骤：

收集数据——找到相似用户和物品——进行推荐

===收集数据===

这里的数据指的都是用户的历史行为数据，比如用户的购买历史，关注，收藏行为，或者发表了某些评论，给某个物品打了多少分等等，这些都可以用来作为数据供推荐算法使用，服务于推荐算法。需要特别指出的在于，不同的数据准确性不同，粒度也不同，在使用时需要考虑到噪音所带来的影响。

===找到相似用户和物品===

这一步也很简单，其实就是计算用户间以及物品间的相似度。以下是几种计算相似度的方法：

欧几里德距离

[[文件:big1-11.png]]

皮尔逊相关系数

[[文件:big1-12.png]]

Cosine 相似度

[[文件:big1-13.png]]


=== 进行推荐 ===

在知道了如何计算相似度后，就可以进行推荐了。

在协同过滤中，有两种主流方法：基于用户的协同过滤，和基于物品的协同过滤。具体怎么来阐述他们的原理呢，看个图就明白了

基于用户的 CF 的基本思想相当简单，基于用户对物品的偏好找到相邻邻居用户，然后将邻居用户喜欢的推荐给当前用户。计算上，就是将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，找到 K 邻居后，根据邻居的相似度权重以及他们对物品的偏好，预测当前用户没有偏好的未涉及物品，计算得到一个排序的物品列表作为推荐。 下图给出了一个例子，对于用户 A，根据用户的历史偏好，这里只计算得到一个邻居 - 用户 C，然后将用户 C 喜欢的物品 D 推荐给用户 A 。

[[文件:big1-14.png]]

[[文件:big1-15.png]]

基于物品的 CF 的原理和基于用户的 CF 类似，只是在计算邻居时采用物品本身，而不是从用户的角度，即基于用户对物品的偏好找到相似的物品，然后根据用户的历史偏好，推荐相似的物品给他。从计算的角度看，就是将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度，得到物品的相似物品后，根据用户历史的偏好预测当前用户还没有表示偏好的物品，计算得到一个排序的物品列表作为推荐。下图给出了一个例子，对于物品 A，根据所有用户的历史偏好，喜欢物品 A 的用户都喜欢物品 C，得出物品 A 和物品 C 比较相似，而用户 C 喜欢物品 A，那么可以推断出用户 C 可能也喜欢物品 C。

[[文件:big1-16.png]]

[[文件:big1-17.png]]

==协同过滤的实现==

===数据的准备===
本程序通过交互式的Python命令来运行，在终端输入python即可进入Python交互式命令界面。完整的代码可以在附件中找到。

构造电影评分数据：

 <nowiki>movieRatingData = [[4, 4, 0, 2, 2], [4, 0, 0, 3, 3],
                 	                 [4, 0, 0, 1, 1], [1, 1, 1, 2, 0],
                                  [2, 2, 2, 0, 0], [5, 5, 5, 0, 0],
                                  [1, 1, 1, 0, 0]]</nowiki>

===相似度计算===
导入必要模块：

 <nowiki>from numpy import * #导入numpy
from numpy import linalg as la #numpy的线性代数模块作为la导入
from numpy.ma import logical_and #用于逻辑与操作</nowiki>

理论课中我们学习了三种方法来计算相似度，分别是欧氏距离、皮尔逊相关系数和余弦相似度。在python中利用numpy这个库很容易实现这三种方法，下列三个方法的输入inA，inB均为列向量。

欧式距离：

 <nowiki>def ecludSim(inA, inB):
    return 1.0 / (1.0 + la.norm(inA - inB))</nowiki> 

la.norm函数用于求范数，结果需要归一化，即相似度=1/(1+距离)，距离为0时相似度为1，距离很大时，相似度就趋近于0。

根据余弦相似度的定义:

[[文件:big1-18.png]]

 <nowiki>def cosSim(inA, inB):
    num = float(inA.T * inB) 
    denom = la.norm(inA) * la.norm(inB)
    return 0.5 + 0.5 * (num / denom)
</nowiki>
 
上面的代码很容易理解。余弦的范围是[-1,1]，同样需要归一化即0.5+0.5×余弦值。

===评分预估并进行推荐===
推荐方法代码：

 <nowiki>def recommend(dataMat, user, N=3, simMeas=ecludSim, estMethod=ratingEst):
    unratedItems = nonzero(dataMat[user, :].A == 0)[1]  # 获取用户没评分的电影
    print()
    print('-------- 对用户%d，未被评价的电影有: ' % (user + 1), end='')
    for i in unratedItems:
        print('%d ' % (i + 1), end='')
    print('--------')
    if len(unratedItems) == 0:
        return '无未评分的电影'
    itemScores = []
    for item in unratedItems:
        estimatedScore = estMethod(dataMat, user, simMeas, item)  # 调用方法预估评分
        itemScores.append((item, estimatedScore))
    return sorted(itemScores, key=lambda i: i[1], reverse=True)[:N]  # 返回降序结果</nowiki>

这个方法的输入参数有5个，dataMat为评分矩阵，user为给定的用户，N为需要推荐的电影数目，simMeas为计算相似度方法，estMethod为预估评分的方法。
接下来说说recommend方法做了什么。寻找用户没有评分的电影，这里用到了nonzero方法。nonzero方法，它会返回矩阵中不为0的元素的行下标和列下标。比如有矩阵  ，��就会返回行下标[0,2]，列下标[2,2]。上面代码中调用nonzero来判断用户哪些电影是没有评分的并赋值给unratedItems，如果用户对所以电影都评过分了就直接返回。接着遍历这些没有评分的电影，对它进行评分预估，即调用estMethod对应的ratingEst方法（接下来会讲到这个方法）。最后把这些电影按照评分从高到低排序返回N个。



评分预估代码：

 <nowiki>def ratingEst(dataMat, user, simMeas, item):
    '''
    :param dataMat: 评分数组
    :param user: 需要预测的用户
    :param simMeas: 相似度
    :param item: 未评价的电影
    :return:
    '''
    n = shape(dataMat)[1]  # 电影数量
    simTotal = 0.0  # 总的相似度
    ratingSimTotal = 0.0  # 总相似度x用户评分
    for j in range(n):  # 遍历每一部电影（列）
        userRating = dataMat[user, j]  # 用户对电影的评分
        if userRating == 0:
            continue
        print('比较电影%d与电影%d的相似度' % (item + 1, j + 1))
        overLap = nonzero(logical_and(dataMat[:, item].A > 0, dataMat[:, j].A > 0))[0]  # 寻找有用户评分的电影
        print('同时评价这两部电影的用户有: ', end='')
        for i in overLap:
            print('%d ' % (i + 1), end='')
        print()
        if len(overLap) == 0:
            similarity = 0
        else:
            similarity = simMeas(dataMat[overLap, item], dataMat[overLap, j])  # 计算相似度
        print('电影%d与电影%d的相似度为: %f' % (item + 1, j + 1, similarity))
        print()
        simTotal += similarity
        ratingSimTotal += similarity * userRating
    if simTotal == 0:
        return 0
    else:
        return ratingSimTotal / simTotal</nowiki>

这个方法有4个输入参数，dataMat为评分矩阵，user为给定的用户，simMeas为计算相似度的方法，item为需要预估评分的电影。预估评分的电影需要跟其他电影计算相似度。在计算相似度时需要输入两个列向量，把没有评分的数据输入是没有意义的，所以代码中overLap所做的就是去掉0评分的用户再计算相似度。举个例子，有评分矩阵：

==完整代码==
 <nowiki>from numpy import *  # 导入numpy
from numpy import linalg as la  # numpy的线性代数模块作为la导入
from numpy.ma import logical_and

movieRatingData = [[4, 4, 0, 2, 2],
                   [4, 0, 0, 3, 3],
                   [4, 0, 0, 1, 1],
                   [1, 1, 1, 2, 0],
                   [2, 2, 2, 0, 0],
                   [5, 5, 5, 0, 0],
                   [1, 1, 1, 0, 0]]

movieRatingData2 = [[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5],
                    [0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3],
                    [0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0],
                    [3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0],
                    [5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0],
                    [0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0],
                    [4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1],
                    [0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4],
                    [0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2],
                    [0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0],
                    [1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]]


def ecludSim(inA, inB):
    return 1.0 / (1.0 + la.norm(inA - inB))  # la.norm用于求范数


def pearsSim(inA, inB):
    if len(inA) < 3: return 1.0
    return 0.5 + 0.5 * corrcoef(inA, inB, rowvar=0)[0][1]


def cosSim(inA, inB):
    num = float(inA.T * inB)
    denom = la.norm(inA) * la.norm(inB)
    return 0.5 + 0.5 * (num / denom)


def svdRatingEst(dataMat, user, simMeas, item):
    n = shape(dataMat)[1]  # 电影数量
    simTotal = 0.0  # 总的相似度
    ratSimTotal = 0.0  # 总相似度x用户评分
    U, Sigma, VT = la.svd(dataMat)  # 原始数据进行svd分解
    Sig4 = mat(eye(4) * Sigma[:4])  # 转化为对角矩阵，取前3个奇异值。注分片操作是前开后闭的
    xformedItems = dataMat.T * U[:, :4] * Sig4.I  # 利用U矩阵降维，即降维了的矩阵。T操作为转置，I操作为求逆
    for j in range(n):
        userRating = dataMat[user, j]
        if userRating == 0 or j == item: continue
        similarity = simMeas(xformedItems[item, :].T,
                             xformedItems[j, :].T)  # 计算相似度，注意进行了转置
        print('the %d and %d similarity is: %f' % (item, j, similarity))
        simTotal += similarity
        ratSimTotal += similarity * userRating
    if simTotal == 0:
        return 0
    else:
        return ratSimTotal / simTotal


def ratingEst(dataMat, user, simMeas, item):
    '''
    :param dataMat: 评分数组
    :param user: 需要预测的用户
    :param simMeas: 相似度
    :param item: 未评价的电影
    :return:
    '''
    n = shape(dataMat)[1]  # 电影数量
    simTotal = 0.0  # 总的相似度
    ratingSimTotal = 0.0  # 总相似度x用户评分
    for j in range(n):  # 遍历每一部电影（列）
        userRating = dataMat[user, j]  # 用户对电影的评分
        if userRating == 0:
            continue
        print('比较电影%d与电影%d的相似度' % (item + 1, j + 1))
        overLap = nonzero(logical_and(dataMat[:, item].A > 0, dataMat[:, j].A > 0))[0]  # 寻找有用户评分的电影
        print('同时评价这两部电影的用户有: ', end='')
        for i in overLap:
            print('%d ' % (i + 1), end='')
        print()
        if len(overLap) == 0:
            similarity = 0
        else:
            similarity = simMeas(dataMat[overLap, item], dataMat[overLap, j])  # 计算相似度
        print('电影%d与电影%d的相似度为: %f' % (item + 1, j + 1, similarity))
        print()
        simTotal += similarity
        ratingSimTotal += similarity * userRating
    if simTotal == 0:
        return 0
    else:
        return ratingSimTotal / simTotal


def recommend(dataMat, user, N=3, simMeas=ecludSim, estMethod=ratingEst):
    unratedItems = nonzero(dataMat[user, :].A == 0)[1]  # 获取用户没评分的电影
    print()
    print('-------- 对用户%d，未被评价的电影有: ' % (user + 1), end='')
    for i in unratedItems:
        print('%d ' % (i + 1), end='')
    print('--------')
    if len(unratedItems) == 0:
        return '无未评分的电影'
    itemScores = []
    for item in unratedItems:
        estimatedScore = estMethod(dataMat, user, simMeas, item)  # 调用方法预估评分
        itemScores.append((item, estimatedScore))
    return sorted(itemScores, key=lambda i: i[1], reverse=True)[:N]  # 返回降序结果


myMat = mat(movieRatingData)
# myMat[0, 1] = myMat[0, 0] = myMat[1, 0] = myMat[2, 0] = 4
# myMat[3, 3] = 2
print(myMat)
print(recommend(myMat, 0))
</nowiki>