大家好，又见面了，我是你们的朋友全栈君。

基于物品的协同过滤算法：理论说明，代码实现及应用

标签： 爬虫 Python

主要参考资料：
项亮. 推荐系统实践[M]. 北京:人民邮电出版社, 2012.

转载请注明出处：http://blog.csdn.net/xuelabizp/article/details/51823458

0.一些碎碎念

从4月中旬开始，被导师赶到北京的郊区搬砖去了，根本就没有时间学习看书，这个时候才知道之前的生活是多么的幸福：每天看自己想看的书，然后实践一下，最后写博文总结一下，偶尔还能去跑个步，游个泳。想找实习的计划也泡汤了，这个项目最早要到七月中下旬才能结束，只能自己挤时间学习了。

逝者如斯夫，不舍昼夜。

1.基于物品的协同过滤算法简介

如今网上信息泛滥，想要在里面找一条适合自己的信息的成本真的有点高，所以就有了推荐系统。于用户而言，推荐系统能够节省自己的时间；于商家而言，推荐系统能够更好的卖出自己的商品。

基于邻域的推荐算法是推荐系统中最基本的算法，该算法分为两大类：基于用户的协同过滤算法(UserCF)和基于物品的协同过滤算法(ItemCF)。

基于用户的协同过滤算法就是找到和“目标用户”相似的用户，然后把他喜欢的东西推荐给“目标用户”。例如小王和小赵一对好基友，他俩喜欢看的书风格基本相同。如果有一天，系统发现小赵给自己的书架添加了一本新书，并且评价很高，那么系统就把这本书自动推荐给了小王，因为小王喜欢这本书的概率很大。设$N(u)$表示用户$u$喜欢的物品，$N(v)$表示用户$v$喜欢的物品，则两个用户的相似度为：
$$w=\frac{\mid N(u)\bigcap N(v)\mid }{\mid N(u)\bigcup N(v)\mid }\text{\hspace{1em}(1)}$$

相比于基于用户的协同过滤算法，基于物品的协同过滤算法在工业界应用更多，因为基于用户的协同过滤算法主要有两个缺点：

• 随着网站的用户数目越来越大，计算用户数的相似度将会越来越困难，其运算的时间复杂度和空间复杂度基本和用户的增长数成平方关系
• 基于用户的协同过滤算法很难对推荐结果做出解释

基于物品的协同过滤算法就是找到和“目标用户”喜欢的物品相似的物品，然后把相似的物品推荐给“目标用户”。例如我很喜欢《黑客帝国》，而《盗梦空间》和《黑客帝国》相似度很高，推荐系统就可以给我推荐《盗梦空间》，实际上我也很喜欢《盗梦空间》。

2.基于物品的协同过滤算法实现

基于物品的协同过滤算法主要有两步：

• 计算物品之间的相似度
• 根据物品的相似度和用户的历史行为给用户生成推荐列表

2.1计算物品的相似度

设$|N(i)|$表示喜欢物品$i$的用户数，$|N(i)\bigcap N(j)|$表示同时喜欢物品$i$物品$j$的用户数，则物品$i$物品$j$的相似度为：
$$w_{ij}=\frac{|N(i)\bigcap N(j)|}{|N(i)|}\text{\hspace{1em}(2)}$$

(2)式有一个问题，当物品$j$是一个很热门的商品时，人人都喜欢，那么$w_{ij}$就会很接近于1，即(2)式会让很多物品都和热门商品有一个很大的相似度，所以可以改进一下公式：
$$w_{ij}=\frac{|N(i)\bigcap N(j)|}{\sqrt{|N(i)||N(j)|}}\text{\hspace{1em}(3)}$$

2.1.1建立用户物品倒排表

ItemCF首先需要建立用户物品倒排表。设用大写字母表示用户，小写字母表示物品，则建立的用户物品倒排表为：

一般情况下，数据都是用户物品倒排表，只需要从原始数据中提炼出来即可，此处就不做代码实现了，因为不同系统的数据不一样（不过可以参考后面应用部分建立用户物品倒排表的代码）。

2.1.2计算共现矩阵C

共现矩阵C表示同时喜欢两个物品的用户数，是根据用户物品倒排表计算出来的。如根据上面的用户物品倒排表可以计算出如下的共现矩阵C：

共现矩阵的对角线元素全为0，且是实对称稀疏矩阵。
实现代码如下：

from collections import defaultdict #可以直接使用下标访问二维字典不存在的元素
def cal_corated_users(train):
    C = defaultdict(defaultdict) #用户与用户共同喜欢物品的个数
    N = defaultdict(defaultdict) #用户个数
    for u, items in train.items():
        for i in items:
            if i not in self.N.keys(): #如果一维字典中没有该键，初始化值为0
                N[i] = 0
            N[i] += 1
            for j in items:
                if i == j:
                   continue
                if j not in self.C[i].keys(): #如果二维字典中没有该键，初始化值为0
                    C[i][j] = 0
                C[i][j] += 1

2.1.3计算余弦相似度矩阵W

共现矩阵C其实就是式(3)的分子，矩阵N表示喜欢某物品的用户数，那么余弦相似度矩阵很容易就计算出来了，示例的矩阵N，以及余弦相似度矩阵如下所示：

a和d之间的相似度最高。
实现代码如下：

def cal_matrix_W():
        for i, related_items in C.items():
            for j, cij in related_items.items():
                W[i][j] = cij / math.sqrt(N[i] * N[j]) #余弦相似度

2.2根据物品的相似度和用户的历史行为给用户生成推荐列表

最终推荐的是什么物品，是由预测兴趣度决定的。物品$j$预测兴趣度=用户喜欢的物品$i$的兴趣度$\times$物品$i$和物品$j$的相似度。

例如某个用户喜欢物品a，b和c，对其兴趣度分别为1，2，2. 那么物品d和e的预测兴趣度分别为：

• d：$1\times 0.71+2\times 0.58+2\times 0.58=3.03$
• e：$2\times 0.58+2\times 0.58=2.32$

所以应当向该用户推荐物品d。
实现代码如下：

def recommend(train, user_id, W, K):
    rank = dict()
    ru = train[user_id] #用户数据，表示某物品及其兴趣度
    for i, pi in ru.items(): #i表示用户已拥有的物品id，pi表示其兴趣度
        #j表示相似度为前K个物品的id，wj表示物品i和物品j的相似度
        for j, wj in sorted(W[i].items(), key=itemgetter(1), reverse=True)[0:K]
        if j in ru: #如果用户已经有了物品j，则不再推荐
            continue
        rank[j] += pi * wj
    return rank

3.基于物品的协同过滤算法应用

之前写了两篇博文，实现了豆瓣书籍信息的爬取：

• 利用爬虫获取豆瓣上可能喜欢的书籍
• 爬取了豆瓣11W+网页，获取了5W+有效书籍信息

其中爬取的某项信息很关键，即某书籍的推荐书籍，如下图所示：

假设把《代码大全》看做一个用户，那么这些推荐书籍就可以看做该用户喜欢的物品，在数据库中的形式如下：

将爬取的数据稍微处理一下，一共得到40558本书籍的相关信息，即40558个用户的信息，那么就可以根据这40558个用户的信息计算余弦相似度矩阵，进行书籍推荐。

把整个计算过程封装到一个类里面，依次建立用户物品倒排表，计算共现矩阵C，计算余弦相似度矩阵W。由于计算余弦相似度矩阵W较为费时（本例大概需要20分钟），所以计算之后使用pickle.dump()把W矩阵保存在本地，下次程序重启的时候直接使用pickle.load()载入即可，大概需要7s。

编写itemCF(self, urls)函数生成推荐列表，urls表示用户所有添加到书架中的书籍的url，返回预测兴趣度TOP10书籍的url。

使用PyQt4编写用户界面，方便搜索，查看，添加，删除和推荐书籍，具体如下：

《统计学习方法》是一本好书，加入到书架中，看看会推荐什么书籍：

《机器学习实战》不错，是《统计学习方法》的黄金搭档，添加到书架里面，再看看推荐书籍：

试一试文学类的书籍，比如《夏洛的网》，看看推荐书籍：

4.一些讨论

Q：UserCF和ItemCF分别适用于什么情况？
A：UserCF根据相似用户推荐，更社会化；ItemCF根据用户本身的历史记录推荐，更加个性化。UserCF较适用于新闻，社区等网站，ItemCF较适用于购物等网站。

Q：UserCF和ItemCF的余弦相似度矩阵W有什么异同？
A：UserCF的相似度矩阵表示用户之间的相似度，适用于用户较少物品较多的场合；ItemCF的相似度矩阵表示物品之间的相似度，适用于用户较多物品较少的场合。目前的购物网站中，物品数量远远小于用户数量，所以购物网站大多采用ItemCF。

Q：如何评价一个推荐系统的优劣？
A：评价一个推荐系统有3种方法：离线实验，用户调查和在线实验。评测的指标有：用户满意度，预测准确度，覆盖率，多样性，新颖性，惊喜度，信任度，实时性，健壮性和商业目标。

5.小结

• 源码在这里，期待你的star
• 计算物品的相似度是ItemCF的关键
• 计算物品相似度矩阵W有3个步骤：建立用户物品倒排表，计算共现矩阵C，计算余弦相似度矩阵W
• 选取前K个相似度的物品进行推荐，其中参数K对推荐系统的准确率，召回率，覆盖率和流行度都有影响
• 协同过滤算法的推荐质量取决于用户的历史数据集，有可能有偏差
• ItemCF需要维护物品相似度矩阵W，一般一天更新一次
• 实际应用中的ItemCF往往会增加对流行物品的惩罚度，因为流行物品和任意物品的相似度都很高，而一个优秀的推荐系统应该能够进行长尾物品推荐