【Python算法】协同过滤算法——基于物品的协同过滤算法
推荐算法背景:
互联网的迅猛发展将人类带入了信息社会和网络经济时代,信息化影响到了生活的方方面面。但是随着互联网产业的扩大,为用户提供更多选的同时也带来了筛选与推荐的难题。于是便提出了推荐算法帮助用户快速找到自己喜爱的东西。例如京东、淘宝、美团等,在用户购买物品后,均会给用户推荐他们可能喜欢的物品,不仅免去了用户不断查找类似物品的烦恼,而且也使得用户可以货比多家,最终找到自己物美价廉的商品,而相关的网站平台也可以提升自己的销量。电影推荐也是比较常见的,例如用户观看了阿甘正传,可能推荐给用户肖申克的救赎、当幸福来敲门等,推荐相关的应用数不胜数,但其核心就是相关的推荐算法的组合。

目前有关个性化推荐算法主要分为三大类:
1.基于协同过滤的推荐;
2.基于内容过滤的推荐;
3.社会化推荐。
本文主要讨论基于协同过滤的推荐,而该算法也可以划分为两类:
这里主要介绍基于物品的协同过滤算法(ItemCF):
内容过滤根据信息资源与用户兴趣的相似性来推荐商品,通过计算用户兴趣模型和商品特征向量之间的向量相似性,主动将相似度高的商品发送给该模型的客户。由于每个客户都独立操作,拥有独立的特征向量,不需要考虑别的用户的兴趣,不存在评价级别多少的问题,能推荐新的项目或者是冷门的项目。这些优点使得基于内容过滤的推荐系统不受冷启动和稀疏问题的影响
实验工具
1.python

Python是一种计算机程序设计语言。是一种动态的、面向对象的脚本语言,最初被设计用于编写自动化脚本(shell),随着版本的不断更新和语言新功能的添加,越来越多被用于独立的、大型项目的开发。Python已经成为最受欢迎的程序设计语言之一。自从2004年以后,python的使用率呈线性增长。2011年1月,它被TIOBE编程语言排行榜评为2010年度语言。
由于Python语言的简洁性、易读性以及可扩展性,在国外用Python做科学计算的研究机构日益增多,一些知名大学已经采用Python来教授程序设计课程。例如卡耐基梅隆大学的编程基础、麻省理工学院的计算机科学及编程导论就使用Python语言讲授。 众多开源的科学计算软件包都提供了Python的调用接口,例如著名的计算机视觉库OpenCV、三维可视化库VTK、医学图像处理库ITK。而Python专用的科学计算扩展库就更多了,例如如下3个十分经典的科学计算扩展库:NumPy、SciPy和matplotlib,它们分别为Python提供了快速数组处理、数值运算以及绘图功能。因此Python语言及其众多的扩展库所构成的开发环境十分适合工程技术、科研人员处理实验数据、制作图表,甚至开发科学计算应用程序。
jupyter

Jupyter Notebook(此前被称为 IPython notebook)是一个交互式笔记本,支持运行 40 多种编程语言。
Jupyter Notebook 的本质是一个 Web 应用程序,便于创建和共享文学化程序文档,支持实时代码,数学方程,可视化和 markdown。 用途包括:数据清理和转换,数值模拟,统计建模,机器学习等等
基于物品的推荐算法以及流程
例如前面背景中介绍的,用户喜欢看阿甘正传,且给了高评分后,那么系统将会寻找与阿甘正传类似的电影推荐给用户。
算法流程
构建用户–>物品的倒排;
构建物品与物品的同现矩阵;
计算物品之间的相似度,即计算相似矩阵;
根据用户的历史记录,给用户推荐物品;
算法流程1
构建用户–>物品的倒排
如下表,行表示用户,列表示物品,1表示用户喜欢该物品
| 用户\物品 | a | b | c | d | e |
|---|---|---|---|---|---|
| A | 1 | 1 | |||
| B | 1 | 1 | 1 | 1 | |
| C | 1 | ||||
| D | 1 | 1 | 1 | ||
| E | 1 | 1 |
例如python构建的数据格式如下
{
'A': {'a': '1', 'b': '1', 'd': '1'},
'B': {'c': '1', 'b': '1', 'e': '1'},
'C': {'c': '1', 'd': '1'},
'D': {'c': '1', 'b': '1', 'd': '1'},
'E': {'a': '1', 'd': '1'}
}
算法流程2
构建物品与物品的同现矩阵
共现矩阵C表示同时喜欢两个物品的用户数,是根据用户物品倒排表计算出来的。如根据上面的用户物品倒排表可以计算出如下的共现矩阵C:
| 物品\物品 | a | b | c | d | e |
|---|---|---|---|---|---|
| A | 1 | 2 | |||
| B | 1 | 2 | 2 | 1 | |
| C | 2 | 2 | 1 | ||
| D | 2 | 2 | 2 | ||
| E | 1 | 1 |
算法流程3
计算物品之间的相似度,即计算相似矩阵
其中两个物品之间的相似度如何计算?
设|N(i)|表示喜欢物品i的用户数,|N(i)⋂N(j)|表示同时喜欢物品i,j的用户数,则物品i与物品j的相似度为:
(1)式有一个问题,当物品j是一个很热门的商品时,人人都喜欢,那么wij就会很接近于1,即(1)式会让很多物品都和热门商品有一个很大的相似度,所以可以改进一下公式:

算法流程2中的共现矩阵C其实就是式(2)的分子,矩阵N(用于计算分母)表示喜欢某物品的用户数(是总的用户数),则(2)式中的分母便很容易求解出来了。
矩阵N如下所示:
| 物品 | a | b | c | d | e |
|---|---|---|---|---|---|
| 用户数 | 2 | 3 | 3 | 4 | 1 |
利用式(2)便能计算物品之间的余弦相似矩阵如下:
| 物品\物品 | a | b | c | d | e |
|---|---|---|---|---|---|
| a | 0.41 | 0.71 | |||
| b | 0.41 | 0.67 | 0.58 | 0.58 | |
| c | 0.67 | 0.58 | 0.58 | ||
| d | 0.71 | 0.58 | 0.58 | ||
| e | 0.58 | 0.58 |
算法流程4
根据用户的历史记录,给用户推荐物品;
最终推荐的是什么物品,是由预测兴趣度决定的。
物品j预测兴趣度=用户喜欢的物品i的兴趣度×物品i和物品j的相似度
例如:A用户喜欢a,b,d ,兴趣度分别为1,1,1
推荐c的预测兴趣度=1X0.67+1X0.58=1.25
推荐e的预测兴趣度=1X0.58=0.58
python实现算法
数据描述
该数据为用户,兴趣度,物品
#用户,兴趣度,物品 uid_score_bid = ['A,1,a', 'A,1,b', 'A,1,d', 'B,1,b', 'B,1,c', 'B,1,e', 'C,1,c', 'C,1,d', 'D,1,b', 'D,1,c', 'D,1,d', 'E,1,a', 'E,1,d']
2.python实现物品推荐
# -*- coding: UTF-8 -*-
from math import sqrt
import operator
# 用户,兴趣度,物品
uid_score_bid = ['A,1,a', 'A,1,b', 'A,1,d', 'B,1,b', 'B,1,c', 'B,1,e', 'C,1,c', 'C,1,d', 'D,1,b', 'D,1,c', 'D,1,d',
'E,1,a', 'E,1,d']
# 1.构建用户-->物品的倒排
def loadData(files):
data = {}
for line in files:
user,score,item = line.split(",")
data.setdefault(user,{})
data[user][item] = score
print("----1.用户:物品的倒排----")
print(data)
return data
# 2.1 构造物品-->物品的共现矩阵
# 2.2 计算物品与物品的相似矩阵
def similarity(data):
# 2.1 构造物品:物品的共现矩阵
N = {} # 喜欢物品i的总人数
C = {} # 喜欢物品i也喜欢物品j的人数
for user,item in data.items():
for i,score in item.items():
N.setdefault(i,0)
N += 1
C.setdefault(i,{})
for j,scores in item.items():
if j not in i:
C.setdefault(j,0)
C[j] += 1
print("---2.构造的共现矩阵---")
print ('N:',N)
print ('C',C)
# 2.2 计算物品与物品的相似矩阵
W = {}
for i,item in C.items():
W.setdefault(i,{})
for j,item2 in item.items():
W.setdefault(j,0)
W[j] = C[j]/sqrt(N*N[j])
print("---3.构造的相似矩阵---")
print(W)
return W
# 3.根据用户的历史记录,给用户推荐物品
def recommandList(data,W,user,k=3,N=10):
rank = {}
for i,score in data[user].items(): # 获得用户user历史记录,如A用户的历史记录为{'a': '1', 'b': '1', 'd': '1'}
for j,w in sorted(W.items(),key=operator.itemgetter(1),reverse=True)[0:k]: # 获得与物品i相似的k个物品
if j not in data[user].keys(): # 该相似的物品不在用户user的记录里
rank.setdefault(j,0)
rank[j] += float(score) * w
print("---4.推荐----")
print(sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N])
return sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N]
if __name__ == '__main__':
# 用户,兴趣度,物品
uid_score_bid = ['A,1,a', 'A,1,b', 'A,1,d', 'B,1,b', 'B,1,c', 'B,1,e', 'C,1,c', 'C,1,d', 'D,1,b', 'D,1,c', 'D,1,d',
'E,1,a', 'E,1,d']
data = loadData(uid_score_bid) # 获得数据
W = similarity(data) # 计算物品相似矩阵
recommandList(data, W, 'A', 3, 10) #推荐
运行结果如下图:

电影推荐应用案例
1.电影数据描述
data = {'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5,
'Just My Luck': 3.0, 'Superman Returns': 3.5, 'You, Me and Dupree': 2.5,
'The Night Listener': 3.0},
'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5,
'Just My Luck': 1.5, 'Superman Returns': 5.0, 'The Night Listener': 3.0,
'You, Me and Dupree': 3.5},
'Michael Phillips': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.0,
'Superman Returns': 3.5, 'The Night Listener': 4.0},
'Claudia Puig': {'Snakes on a Plane': 3.5, 'Just My Luck': 3.0,
'The Night Listener': 4.5, 'Superman Returns': 4.0,
'You, Me and Dupree': 2.5},
'Mick LaSalle': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
'Just My Luck': 2.0, 'Superman Returns': 3.0, 'The Night Listener': 3.0,
'You, Me and Dupree': 2.0},
'Jack Matthews': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
'The Night Listener': 3.0, 'Superman Returns': 5.0, 'You, Me and Dupree': 3.5},
'Toby': {'Snakes on a Plane': 4.5, 'You, Me and Dupree': 1.0, 'Superman Returns': 4.0}
}
2.推荐
推荐过程和上面的代码过程一样,仅不用构造倒排数据
demo.py:
# -*- coding: UTF-8 -*-
from math import sqrt
import operator
data = {'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5,
'Just My Luck': 3.0, 'Superman Returns': 3.5, 'You, Me and Dupree': 2.5,
'The Night Listener': 3.0},
'Gene Seymour': {'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5,
'Just My Luck': 1.5, 'Superman Returns': 5.0, 'The Night Listener': 3.0,
'You, Me and Dupree': 3.5},
'Michael Phillips': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.0,
'Superman Returns': 3.5, 'The Night Listener': 4.0},
'Claudia Puig': {'Snakes on a Plane': 3.5, 'Just My Luck': 3.0,
'The Night Listener': 4.5, 'Superman Returns': 4.0,
'You, Me and Dupree': 2.5},
'Mick LaSalle': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
'Just My Luck': 2.0, 'Superman Returns': 3.0, 'The Night Listener': 3.0,
'You, Me and Dupree': 2.0},
'Jack Matthews': {'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0,
'The Night Listener': 3.0, 'Superman Returns': 5.0, 'You, Me and Dupree': 3.5},
'Toby': {'Snakes on a Plane': 4.5, 'You, Me and Dupree': 1.0, 'Superman Returns': 4.0}
}
# 1.构建用户-->物品的倒排(此推荐无需使用)
def loadData(files):
data = {}
for line in files:
user,score,item = line.split(",")
data.setdefault(user,{})
data[user][item] = score
print("----1.用户:物品的倒排----")
print(data)
return data
# 2.1 构造物品-->物品的共现矩阵
# 2.2 计算物品与物品的相似矩阵
def similarity(data):
# 2.1 构造物品:物品的共现矩阵
N = {} # 喜欢物品i的总人数
C = {} # 喜欢物品i也喜欢物品j的人数
for user,item in data.items():
for i,score in item.items():
N.setdefault(i,0)
N += 1
C.setdefault(i,{})
for j,scores in item.items():
if j not in i:
C.setdefault(j,0)
C[j] += 1
print("---2.构造的共现矩阵---")
print ('N:',N)
print ('C',C)
# 2.2 计算物品与物品的相似矩阵
W = {}
for i,item in C.items():
W.setdefault(i,{})
for j,item2 in item.items():
W.setdefault(j,0)
W[j] = C[j]/sqrt(N*N[j])
print("---3.计算的相似矩阵---")
print(W)
return W
# 3.根据用户的历史记录,给用户推荐物品
def recommandList(data,W,user,k=3,N=10):
rank = {}
for i,score in data[user].items(): # 获得用户user历史记录,如A用户的历史记录为{'a': '1', 'b': '1', 'd': '1'}
for j,w in sorted(W.items(),key=operator.itemgetter(1),reverse=True)[0:k]: # 获得与物品i相似的k个物品
if j not in data[user].keys(): # 该相似的物品不在用户user的记录里
rank.setdefault(j,0)
rank[j] += float(score) * w
print("---3.推荐----")
print(sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N])
return sorted(rank.items(),key=operator.itemgetter(1),reverse=True)[0:N]
if __name__ == '__main__':
print("---1.构造数据---")
W = similarity(data) # 计算物品相似矩阵
recommandList(data, W, 'Toby', 10, 10) #推荐
推荐结果如下图所示:

