[TOC]
协同过滤——基于用户与物品的推荐算法
本文是《写给程序员的数据挖掘实践指南》的一周性笔记总结。主要涵盖了以下内容：
- 不同距离函数的选择
- k-NN
- Slope One算法
- 简单分类算法
1. 协同过滤简介
所谓推荐系统就是系统根据你的行为操作为你推荐你可能想要的其他物品。这在电商平台、音乐平台、资讯推送平台等多有见到。而协同过滤简单来说是利用某兴趣相投、拥有共同经验之群体的喜好来推荐用户感兴趣的信息，个人通过合作的机制给予信息相当程度的回应（如评分）并记录下来以达到过滤的目的进而帮助别人筛选信息。其推荐基础是用户评分。这里可以分为两种用户评分，即显式评分与隐式评分。显式评分即日常见到的为物品打分，如对喜好音乐评级等；隐式评分是通过对用户行为的持续性观察，进而发现用户偏好的一种方法，如新闻网页中的推送你经常阅读过的相关内容等。两种评分方法都有自己的问题。
- 显示评级的问题：
- 用户多有惰性，不愿意对物品进行评级。
- 用户可能撒谎或者只给出部分信息。
- 用户不会更新其评级结果
- 隐式评级的问题：
- 不能确定账户的使用者是同一个人
- 同一个人的情况下不能确定其购买只是为了自身
总体来说，协同过滤其运作机制也可以分为两种：
- 基于用户的推荐
- 基于物品的推荐
1.1 基于用户的过滤
基于用户的推荐是指通过用户的行为偏好，划分相似用户。在相似用户群体之间互相推送一方喜欢而另一方未有过的物品。核心在于相似用户群体的划分。这种推荐方法有自己的局限：
- 复杂度随着用户数量的增长变得极高
- 大部分推荐系统中，用户和商品都很多，但是用户评级的平均商品数量较少。也就是说平均每个用户评级过的书的数量不足以使其找到最近邻居。
基于用户的过滤其核心是用户群体的划分，其实也就是分类。
1.1.1 基于距离函数的分类
这里的距离函数包括三种：曼哈顿距离和欧氏距离。这里以二维举例，更多维情况下类推即可。
- 曼哈顿距离
d(x, y) =
- 欧氏距离
d(x, y) =
两距离函数可以一般化为：
d(x, y)=
其中，当r=1时，函数为曼哈顿距离；当r=2时，函数为欧氏距离。
算法实现：
import numpy as np
import pandas as pd
def Mingdis(x, y, r):
'''
x, y是n维ndarray，其元素是评分的各feature。r是对距离函数的选择。
'''
return (np.sum((np.abs(x - y))^r))^(1 / r)
在算出距离函数后，通过比对目标用户与所有用户群体的偏好，找到最近邻的用户并给予推荐。
1.1.2 皮尔逊相关系数
基于用户距离的推荐有一个明显的问题，就是用户评分体系的差异。比如评分极端的用户给喜欢的评最高分，给不喜欢的评最低分；而有些用户倾向于不出现极端评分。即所谓“分数贬值”(Grade Inflation)问题。这种问题的存在可能让基于距离的评分产生偏差。皮尔逊相关系数可以缓解这种问题。
- 皮尔逊相关系数
原皮尔逊相关系数公式在实际运用的时候会出现多次迭代的问题，影响计算效率，这里给出了近似公式：
皮尔逊相关系数的用户判断依据不是单纯的用户距离，而是用户的评分一致性：取值在[-1, 1]之间，越接近1则表示两用户的评分一致性越好；反之则反。
python实现：
import numpy as np
import pandas as pd
def pearsonScore(x, y):
return (x.dot(y) - (np.sum(x) * np.sum(y)) / n) / ((np.sqrt(np.sum(x**2) - (1/n) * (np.sum(x))**2)) * ((np.sqrt(np.sum(y**2) - (1/n) * (np.sum(y))**2)))
1.1.3 余弦相似度
基于用户推荐的过程中，另一个存在的问题就是由于大部分人的喜爱物品集合的交集过少，存在大量计算值为0的feature的情况。即所谓 稀疏性 问题。一个较容易理解的例子是对书本内容的挖掘。余弦相似度会忽略这种0-0匹配。
余弦相似度：
cos(x, y) =
其中 ||x|| 表示向量的长度。在numpy中，可以使用np.linalg.norm(x)来求。
python实现：
import numpy as np
def cosRsys(x, y):
return x.dot(y) / (np.linalg.norm(x) * np.linalg.norm(y))
1.1.4 三种指标的选择问题与总结
如此多的评估系数，如何进行抉择呢？根据数据特征：
- 如果数据受分数贬值影响很大，即不同用户使用不同的评级范围，则使用皮尔逊。
- 如果数据稠密，几乎所有的属性都没有零，并且属性值大小十分重要，则使用距离。
- 如果数据稀疏，考虑余弦相似度。
另外值得考虑的一点是，目前为止的推荐都是基于单用户的。即对一个用户的推荐系统只是基于另一个用户。这会存在一些问题。比如虽然虽然两者相似度很高，但是另外一个人有一些怪癖，怪癖的推荐就是不合理的；又比如，在相似度极高的情况下，你不能确定统一账户下的操作是同一个人做出的或者说操作行为是为了用户自身。比如用户考虑购买某件商品作为礼物送给别人，这就是基于别人喜好的购买行为，这种推荐也是不合适的。
对这种问题的解决可以使用群体划分的方法。原理与单用户类似，但是用户的匹配是k个。在这k位最优匹配的用户之间，以相似度的大小为依据设定权重作为物品推荐的条件。此即协同过滤的k近邻。
1.2 基于物品的过滤
正如前面提到的基于用户的推荐有复杂度、稀疏性的问题，而基于物品的过滤则可以缓解这些问题。所谓基于物品的过滤是指，我们事先找到最相似的物品，并结合用户对物品的评级结果来生成推荐。前提是要对物品进行相似度匹配，找到一种算法。
1.2.1 调整后的余弦相似度
这里的调整是指为了减轻用户评分体系的不一致情况（抵消分数贬值），从每个评级结果中减去该用户所有物品的平均分的评级结果。
其中，U表示所有同时对i， j进行评级过的用户的集合。 表示用户ｕ给物品ｉ的评分减去用户ｕ对所有物品的评分的平均值。
在得到所有物品的余弦相似度后，我们就可以通过该指数预测用户对某件物品的偏好程度。方法就是所有相似物品的相似度乘以得分的总和。
其中p（u, i）指的是用户u对物品i评分的预测值。N是用户u的所有评级物品中每个和i得分相似的物品。这里的相似指的是矩阵中存在N和i的一个相似度得分。 是i和N之间的相似度得分。
是u给N的评级结果。公式较好运行的条件是
取值在（-1， 1）之间，这里就要使用归一化概念。
import numpy as np
import pandas as pd
from itertools import combinations
pd.set_option('display.width', None)
users3 = {"David": {"Imagine Dragons": 3, "Daft Punk": 5,
"Lorde": 4, "Fall Out Boy": 1},
"Matt": {"Imagine Dragons": 3, "Daft Punk": 4,
"Lorde": 4, "Fall Out Boy": 1},
"Ben": {"Kacey Musgraves": 4, "Imagine Dragons": 3,
"Lorde": 3, "Fall Out Boy": 1},
"Chris": {"Kacey Musgraves": 4, "Imagine Dragons": 4,
"Daft Punk": 4, "Lorde": 3, "Fall Out Boy": 1},
"Tori": {"Kacey Musgraves": 5, "Imagine Dragons": 4,
"Daft Punk": 5, "Fall Out Boy": 3}}
users2 = {"Amy": {"Taylor Swift": 4, "PSY": 3, "Whitney Houston": 4},
"Ben": {"Taylor Swift": 5, "PSY": 2},
"Clara": {"PSY": 3.5, "Whitney Houston": 4},
"Daisy": {"Taylor Swift": 5, "Whitney Houston": 3}}
users = pd.DataFrame(users3)
users4 = pd.DataFrame(users2)
# print(users)
# 用调整后的余弦相似度对物品相似度进行计算 对于缺失值用nanmena nanmax等函数
def cosRecSys(a, b):
sco = users.loc[['%s' % a, '%s' % b], ].dropna(axis=1, how='any') # 去掉缺失值的列
colname = sco.columns.values.tolist() # 获得用户名list
mean_socre = []
# print(sco)
for i in colname: # 得到相应用户的平均分
mean_socre.append(np.nanmean(np.array(users.loc[:, '%s' % i])))
mean_scoND = np.array(mean_socre)
# print(mean_socre)
upper = np.sum((sco - mean_scoND).iloc[0, :] * (sco - mean_scoND).iloc[1, :])
# print(upper)
down = np.sqrt(np.sum(((sco - mean_scoND).iloc[0, :])**2)) * np.sqrt(np.sum(((sco - mean_scoND).iloc[1, :])**2))
# print(down)
return upper / down
# 将关系制表
bandlist = users.index.tolist()
bandcom = list(combinations(bandlist, 2)) # 自动在list里找到排列组合
bandPD = pd.DataFrame()
for i in bandcom: # 比较好的建立表格的方法
i0 = list(i)[0]
i1 = list(i)[1]
bandPD.loc[i0, i1] = cosRecSys(i0, i1)
# 实现基于调整后的余弦相似度表对未评级物品进行评分预测。
# 1. 评分归一化
def n(a):
score = users.loc[:, a]
return (2 * (score - np.nanmin(score)) - (np.nanmax(score) - np.nanmin(score))) / np.abs(np.nanmax(score) - np.nanmin(score))
# 2. 评分预测函数实现
def predict_score(name, band):
nscore = n(name).dropna(axis=0, how='any')
bandcore = []
# 下列是把相关性表里的相关系数拿到bandcore里。
if len(list(bandPD.loc[:, band].dropna(axis=0, how='any'))) != bandPD.shape[0]:
print('进入')
sec = list(bandPD.loc[band, :].dropna(axis=0, how='any'))
# print('sec', sec)
bandcore.extend(list(bandPD.loc[:, band].dropna(axis=0, how='any')))
bandcore.extend(sec)
else:
bandcore.extend(list(bandPD.loc[:, band]))
bandcoreND = np.array(bandcore)
return np.sum(nscore * bandcoreND)/np.sum(np.abs(bandcoreND))
1.2.2 加权Slope one算法
另一种常用的基于物品过滤的算法就是 slope one算法。它的大概原理是预测用户u对产品j的评分时，预先计算包含所有物品的两物品偏差表；根据u的已评价的所有物品评分与该物品和产品j的偏差（）之和并乘以所有对此两类物品有过评分的用户个数，一一加总，除以所有同时对产品i与u评价过的所有物品有过评分的用户的人数，得到得分。公式如下：
- 计算所有物品的偏差（事先进行）
其中，card(S)是S集合中的元素个数，X是整个评分集合。因此是对i和j进行评分的用户集合。
- 利用偏差进行预测
_j%3D%5Cfrac%7B%5Csum_%7Bi%20%5Csubset%20S(u)%20-%7Bj%7D%7D%20%7B(dev_%7Bj%2C%20i%7D%20%2B%20u_i)*c_%7Bj%2C%20i%7D%7D%7D%7B%5Csum_%7Bi%20%5Csubset%20S(u)%20-%7Bj%7D%7D%7Bc_%7Bj%2C%20i%7D%7D%7D)
其中，；
是利用加权s1算法给出的用户u对物品j的预测值。
指的是对所有除j之外u打过分的物品。
python实现：
# Slope One算法
# 1. 偏差计算(任意产品i到j的偏差)
def dev(i, j):
conUser = users4.loc[[i, j], :].dropna(axis=1, how='any')
usercount = conUser.shape[1]
return np.sum((conUser.loc[i, :] - conUser.loc[j, :]) / usercount)
# 2. 利用加权S1算法进行预测
def preS1(user, item): # 根据user拿到其已经评价过的item，这些item里sum(和预测目标的偏差的和)/sum(usercount). item是目标
useritem = users4.loc[:, user].dropna(axis=0, how='any')._stat_axis.values.tolist() # 拿到已经评价过的item
upper = 0
usercountT = 0
for i in useritem:
usercount = users4.loc[[item, i], :].dropna(axis=1, how='any').shape[1]
usercountT += usercount
upper += (dev(item, i) + users4.loc[i, user]) * usercount
print(upper)
print(usercountT)
return upper / usercountT
1.3 基于物品属性的过滤
在前面两节中，基于物品和基于用户的过滤其前提都是用户需要对已有的item进行评分。而实际上，如果一个新的item出现，由于缺乏别人的偏好，他永远不会被推荐。这就是推荐系统中所谓的—— 冷启动 问题。基于用户评价的系统就会出现这种问题。
冷启动 问题的解决方案之一就是 基于物品属性的过滤 来进行推荐：对物品自身的属性进行归纳总结，并以此进行物品推荐。基于物品属性的过滤存在一个问题同样是量纲的不统一。如果量纲不统一极端值将会对推荐系统造成大麻烦。解决方法也很简单：归一化。此章使用的是z-评分。
使用z得分也存在问题，就是极易受到离群值的影响。这里可以使用 改进的标准分数 来缓解这个问题：
改进的标准分数=
其中为中位数，asd称为绝对标准差。Card（x）是指x集合中的个数。
什么时候可以进行归一化呢？
- 所用数据挖掘方法基于特征值来计算两个对象的距离；
- 不同特征的尺度不同。
这里用曼哈顿距离举例基于物品属性的过滤：
import pandas as pd
import numpy as np
# pd.set_option('display.width', None)
music = {"Dr Dog/Fate": {"piano": 2.5, "vocals": 4, "beat": 3.5, "blues": 3, "guitar": 5, "backup vocals": 4, "rap": 1},
"Phoenix/Lisztomania": {"piano": 2, "vocals": 5, "beat": 5, "blues": 3, "guitar": 2, "backup vocals": 1, "rap": 1},
"Heartless Bastards/Out at Sea": {"piano": 1, "vocals": 5, "beat": 4, "blues": 2, "guitar": 4, "backup vocals": 1, "rap": 1},
"Todd Snider/Don't Tempt Me": {"piano": 4, "vocals": 5, "beat": 4, "blues": 4, "guitar": 1, "backup vocals": 5, "rap": 1},
"The Black Keys/Magic Potion": {"piano": 1, "vocals": 4, "beat": 5, "blues": 3.5, "guitar": 5, "backup vocals": 1, "rap": 1},
"Glee Cast/Jessie's Girl": {"piano": 1, "vocals": 5, "beat": 3.5, "blues": 3, "guitar":4, "backup vocals": 5, "rap": 1},
"La Roux/Bulletproof": {"piano": 5, "vocals": 5, "beat": 4, "blues": 2, "guitar": 1, "backup vocals": 1, "rap": 1},
"Mike Posner": {"piano": 2.5, "vocals": 4, "beat": 4, "blues": 1, "guitar": 1, "backup vocals": 1, "rap": 1},
"Black Eyed Peas/Rock That Body": {"piano": 2, "vocals": 5, "beat": 5, "blues": 1, "guitar": 2, "backup vocals": 2, "rap": 4},
"Lady Gaga/Alejandro": {"piano": 1, "vocals": 5, "beat": 3, "blues": 2, "guitar": 1, "backup vocals": 2, "rap": 1}}
users = {'Angelica':{"Dr Dog/Fate":'L', "Phoenix/Lisztomania":'L', "Heartless Bastards/Out at Sea":'D', "Todd Snider/Don't Tempt Me":'D',
"The Black Keys/Magic Potion":'D', "Glee Cast/Jessie's Girl":'L', "La Roux/Bulletproof":'D', "Mike Posner":'D',
"Black Eyed Peas/Rock That Body":'D', "Lady Gaga/Alejandro":'L'},
'Bill': {"Dr Dog/Fate": 'L', "Phoenix/Lisztomania": 'L', "Heartless Bastards/Out at Sea": 'L',
"Todd Snider/Don't Tempt Me": 'D',
"The Black Keys/Magic Potion": 'L', "Glee Cast/Jessie's Girl": 'D', "La Roux/Bulletproof": 'D',
"Mike Posner": 'D',
"Black Eyed Peas/Rock That Body": 'D', "Lady Gaga/Alejandro": 'D'}}
musicPD = pd.DataFrame(music)
usersPD = pd.DataFrame(users)
usersPD[usersPD == 'D'] = 0
usersPD[usersPD == 'L'] = 1
print(musicPD)
print(usersPD)
def mingdis(n1, n2, r=1):
'''
使用明氏距离，r作为参数来选定距离测算方法
'''
s1 = np.array(n1)
s2 = musicPD['%s' % n2]
# content = np.intersect1d(s1, s2)
distance = (np.sum((np.abs(s1 - s2)) ** r) ** (1 / r))
return distance
def nearestClassify(user, itemname, score):
'''
思路很简单，用给的用户数据训练模型，模型用曼哈顿距离来做。根据模型用给的属性值推算是否喜欢。
具体来说，用给出的score去和每一个歌曲进行曼哈顿距离匹配，求出最近的歌。然后用这个歌的名字去看那位用户是否喜欢
'''
songname = musicPD.columns.values.tolist()
print(songname)
nearestsong = 'null'
nearestsongscore = 100
for i in songname:
if mingdis(score, i) < nearestsongscore:
nearestsong = i
nearestsongscore = mingdis(score, i)
print('最接近的是', nearestsong, nearestsongscore)
likeordislike = usersPD.loc[nearestsong, user] and 'yep' or 'nope'
print(likeordislike)
return likeordislike
nearestClassify('Angelica', 'Cagle', [5, 2.5, 1, 1, 1, 1, 5]) # 输入顺序要改一下，因为pd.Dataframe后列顺序会改变，如果按照原顺序distance不能正确识别
2. 分类器
在上一章最后一节对于用户是否喜欢某件item的判别中，实际上包含了分类器的思想：分类器就是利用对象属性判定对象属于哪个组或类别的程序。这里简单用另一个小项目来说明。
2.1 体育项目的识别
简单来说就是根据运动员的某些指标来判断这位运动员属于什么类别的运动员。
import pandas as pd
import numpy as np
# 读取数据集
# 1. 读取训练集. 注意，此时读取的内容，数字的格式为str。
def getdata(dataname):
with open('%s' % dataname[0], 'r') as data1:
trainingset = [i.rstrip().split('\t') for i in data1.readlines()]
colname = trainingset[0] # 把第一顺位的list元素提取出来作为columns names备用。
tradata = pd.DataFrame(trainingset[1:], columns=colname)
with open('%s' % dataname[1], 'r') as data2:
testset = [i.rstrip().split('\t') for i in data2.readlines()]
colname = testset[0] # 把第一顺位的list元素提取出来作为columns names备用。
testdata = pd.DataFrame(testset[1:], columns=colname)
return tradata, testdata
# 2. 用一位运动员的数据去预测其属于何类运动员
def whichSport(data, r1=1, r2=0):
'''
r1是距离计算方法，r2是归一化方法
大概思路是，用data去匹配tratest里与其相似度最高的一位运动员；
该位运动的项目即是我们预测的结果。
匹配中，有些问题需要注意：
1。 可以发现，运动员的属性值波动很大，这说明了归一化的必要。但由于本数据的特殊性（只含有两个feature， 所以不实用于归一化，不然返回结果只有0，1）
2。 匹配方法的选择上，这里选择曼哈顿距离与欧式距离。
'''
tradata0 = tradata.set_index('comment')
athname = tradata0.index.values.tolist()
minscore = 100000
ansclass = 'null'
for i in athname:
athclass = tradata0.loc[i, 'class']
data2 = np.array(tradata0.loc[str(i), 'num1':'num2'], dtype=float)
data2 = nor(data2, r2)
data = nor(data, r2)
# print('训练集遍历循环', data2)
tempscore = mingdist(data, data2, r1)
if tempscore < minscore:
minscore = tempscore
ansclass = athclass
return ansclass
# 2.1 距离函数
def mingdist(data1, data2, r=1): # r=1即曼哈顿距离；r=2即欧式距离。默认1
distance = (np.sum((np.abs(data1 - data2)) ** r) ** (1 / r))
return distance
# 2.2 归一化
def nor(data, way=0): # way=0, 不使用归一化；way=1， 使用（数据-最小）/（最大-最小）;way=2，使用改进的标准分数。默认0。
if way == 1:
return (data - np.min(data)) / (np.max(data) - np.min(data))
elif way == 2:
return (data - np.median(data)) / (np.sum(np.abs(data - np.median(data))) / data.shape)
elif way == 0:
return data
# 3. 测试单元。包括引入所有测试集数据，并计算准确度。
tradata, testdata = getdata(['athtra.txt', 'athtest.txt'])
testdata = testdata.set_index('comment')
testname = testdata.index.values.tolist() # 拿到测试集所有运动员名
counter = 0
total = testdata.shape[0] # 一共多少运动员
# print(testdata.loc['Maya Moore', 'class'])
for i in testname: # 开始遍历，并看是否预测准确
# print('测试集遍历循环')
ansclass = testdata.loc[str(i), 'class']
if ansclass == whichSport(np.array(testdata.loc[i, 'num1':'num2'], dtype=float), 1, 2):
counter += 1
print('准确率', counter/total)
准确率有0.8。
