你挡我一时,挡不了我一世
前文链接:https://write-bug.com/article/2696.html
基于矩阵分解的推荐算法-隐语义模型:ALS、LFM、SVD、SVD++
在15年左右流行
-交替最小二乘
我们之前学习的协同过滤CF:单独考虑user、item
这里同时考虑User-item两方面:
原来我们的UI稀疏打分矩阵\<m,n>:
一般公司用户量可以随意达到上亿,物品量如音乐可以达到几十万,用户量之所以多,是因为可能一个用户有多个账户等等,共同组成一个很大很稀疏的矩阵
那么面对这样一个矩阵,我们可以通过矩阵分解来解决:
将User和Item分别映射到新的空间,分解成两个矩阵,U 和I两个维度都不变
K值远小于M和N,从而达到降维目的
无需关注新空间的各个维度,只需假定存在 ,即用向量表示user和item
新的维度称为Latent Factor(隐因子)
K的维度相比原来来说很小很小,并且可以人为设定,只需要两个矩阵相乘就能得到UI矩阵,即R’ ≈R
两个矩阵相似如何界定?误差
误差表示:RMSE :均方根误差
目标:真实矩阵,和结果矩阵之间的尽可能逼近
最小化平方误差作为损失函数:
考虑矩阵稳定性,引入L2正则项,得到损失函数:
这里的rui就是上面所说的R,即原矩阵user对item打的分数
xuyi即分解矩阵后再相乘的预估分数,两个相减就是误差
未知数:
Xu:user vector
yi:item vector
如何求解最优值:求导=0
公式1:
导数为0,可得到:
同理对yi求导(公式2):
为什么叫交替二乘法?
这里的做法是让x和y交替下降:
随机生成X、Y向量(初始化)
固定Y,更新X(公式1)
固定X,更新Y(公式2)
第2、3步循环,直到满足收敛条件(RMSE)
——均方根误差
那么我们得到这两个小矩阵,可以做什么?
item-item :IK*KI=II
User-User:UK*KU=UU
user与item的向量
思路和ALS算法类似,区别在于,ALS利用坐标下降法,LFM利用梯度下降法
假设:
评分矩阵𝑅𝑚,𝑛,m个用户对n个物品评分
𝑟𝑢,𝑖:用户u对物品i的评分
𝑅𝑚,𝑛 = 𝑃𝑚,𝐹 ∙ 𝑄𝐹,𝑛:R是两个矩阵的乘积
P:每一行代表一个用户对各隐因子的喜欢程度 ,即前面的user矩阵
Q:每一列代表一个物品在各个隐因子上的概率分布,即前面的item矩阵
在之前的随机梯度下降中,我们更新w(t+1)=w(t) - a*g(梯度)
那么根据这样的思路,这里把矩阵P与Q的分数当作权重w来更新:
矩阵展开后相当于对每个元素分数进行偏导:
随意抽取中间这个元素作为代表,求取偏导:
由于
所以后面两个等式相等,之后就有一件很有意思的事情发生了:P的分数是由上一时刻的Q更新的,Q的分数是由上一时刻的P更新的。也就是类似上面的坐标下降法:交替进行。
代入原式:
LFM实践:
class LFM(object):
def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500):
'''rating_data是list<(user,list<(position,rate)>)>类型
'''
self.F = F#维度K
self.P = dict()
self.Q = dict()
self.alpha = alpha#学习率
self.lmbd = lmbd
self.max_iter = max_iter#迭代轮数
self.rating_data = rating_data#矩阵
'''随机初始化矩阵P和Q'''
for user, rates in self.rating_data:
self.P[user] = [random.random() / math.sqrt(self.F)
for x in xrange(self.F)]
for item, _ in rates:
if item not in self.Q:
self.Q[item] = [random.random() / math.sqrt(self.F)
for x in xrange(self.F)]
def train(self):
'''随机梯度下降法训练参数P和Q
'''
for step in xrange(self.max_iter):
for user, rates in self.rating_data:
for item, rui in rates:
hat_rui = self.predict(user, item)
err_ui = rui - hat_rui
for f in xrange(self.F):
self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f])
self.Q[item][f] += self.alpha * (err_ui * self.P[user][f] - self.lmbd * self.Q[item][f])
self.alpha *= 0.9 # 每次迭代步长要逐步缩小
def predict(self, user, item):
'''预测用户user对物品item的评分
'''
return sum(self.P[user][f] * self.Q[item][f] for f in xrange(self.F))
if __name__ == '__main__':
'''用户有A B C,物品有a b c d,列表模拟矩阵:'''
rating_data = list()
rate_A = [('a', 1.0), ('b', 1.0)]
rating_data.append(('A', rate_A))
rate_B = [('b', 1.0), ('c', 1.0)]
rating_data.append(('B', rate_B))
rate_C = [('c', 1.0), ('d', 1.0)]
rating_data.append(('C', rate_C))
lfm = LFM(rating_data, 2)
lfm.train()
for item in ['a', 'b', 'c', 'd']:
print(item, lfm.predict('A', item)) # 预测计算用户A对各个物品的喜好程度
LFM有什么缺点?没有考虑客观的偏置,所以带偏置的LFM称为SVD
什么是偏置,比如说有的人很极端给一些物品很高或者很低的分数,而有的人给每个物品都很平均的分数,还有包括地区等等都会影响对物品的看法,所以就有一个偏置存在。
偏置:事件固有的,不受外界影响的属性。
𝜇:训练集中所有评分的平均值
𝑏𝑢:用户偏置,代表一个用户评分的平均值
𝑏𝑖:物品偏置,代表一个物品被评分的平均值
更新:
SVD实践:
class BiasLFM(object):
def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500):
'''rating_data是list<(user,list<(position,rate)>)>类型
'''
self.F = F
self.P = dict()
self.Q = dict()
self.bu = dict()
self.bi = dict()
self.alpha = alpha
self.lmbd = lmbd
self.max_iter = max_iter
self.rating_data = rating_data
self.mu = 0.0
'''随机初始化矩阵P和Q'''
cnt = 0
for user, rates in self.rating_data:
self.P[user] = [random.random() / math.sqrt(self.F)
for x in xrange(self.F)]
self.bu[user] = 0#初始化bu
cnt += len(rates)
for item, rate in rates:
self.mu += rate
if item not in self.Q:
self.Q[item] = [random.random() / math.sqrt(self.F)
for x in xrange(self.F)]
self.bi[item] = 0#初始化bi
self.mu /= cnt#计算μ
def train(self):
'''随机梯度下降法训练参数P和Q
'''
for step in xrange(self.max_iter):
for user, rates in self.rating_data:
for item, rui in rates:
hat_rui = self.predict(user, item)
err_ui = rui - hat_rui
#更新两个b
self.bu[user] += self.alpha * (err_ui - self.lmbd * self.bu[user])
self.bi[item] += self.alpha * (err_ui - self.lmbd * self.bi[item])
for f in xrange(self.F):
self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f])
self.Q[item][f] += self.alpha * (err_ui * self.P[user][f] - self.lmbd * self.Q[item][f])
self.alpha *= 0.9 # 每次迭代步长要逐步缩小
def predict(self, user, item):
'''预测用户user对物品item的评分,加偏置
'''
return sum(self.P[user][f] * self.Q[item][f] for f in xrange(self.F)) + self.bu[user] + self.bi[item] + self.mu
if __name__ == '__main__':
'''用户有A B C,物品有a b c d'''
rating_data = list()
rate_A = [('a', 1.0), ('b', 1.0)]
rating_data.append(('A', rate_A))
rate_B = [('b', 1.0), ('c', 1.0)]
rating_data.append(('B', rate_B))
rate_C = [('c', 1.0), ('d', 1.0)]
rating_data.append(('C', rate_C))
lfm = BiasLFM(rating_data, 2)
lfm.train()
for item in ['a', 'b', 'c', 'd']:
print(item, lfm.predict('A', item)) # 计算用户A对各个物品的喜好程度
任何用户只要对物品i有过评分,无论评分多少,已经在一定程度上反映了用户对各个隐因子的喜好 程度𝑦𝑖 = (𝑦𝑖1,𝑦𝑖2,…,𝑦𝑖𝐹),y是物品携带的属性,什么意思?比如说A买了3个item,B买了3个item,每个item背后有一系列feature vector,那么我们用A买的3个item背后的fea向量相加(实际计算是学习更新出来的,不一定是相加)代表一个虚拟的物品A,间接表达了这个用户的偏好程度,同理得到向量B,那么对于这个每个人背后的虚拟物品向量,就是y
所以这个打分是在P上又增加了一个类似于偏置的东西,并做了归一化
𝑁(𝑢):用户u评价过的物品集合
𝑏𝑢:用户偏置,代表一个用户评分的平均值
𝑏𝑖:物品偏置,代表一个物品被评分的平均值
SVD++实践:
class SVDPP(object):
def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500):
'''rating_data是list<(user,list<(position,rate)>)>类型
'''
self.F = F
self.P = dict()
self.Q = dict()
self.Y = dict()
self.bu = dict()
self.bi = dict()
self.alpha = alpha
self.lmbd = lmbd
self.max_iter = max_iter
self.rating_data = rating_data
self.mu = 0.0
'''随机初始化矩阵P、Q、Y'''
cnt = 0
for user, rates in self.rating_data:
self.P[user] = [random.random() / math.sqrt(self.F)
for x in xrange(self.F)]
self.bu[user] = 0
cnt += len(rates)
for item, rate in rates:
self.mu += rate
if item not in self.Q:
self.Q[item] = [random.random() / math.sqrt(self.F)
for x in xrange(self.F)]
if item not in self.Y:#比之前svd多加了一个y,初始化y
self.Y[item] = [random.random() / math.sqrt(self.F)
for x in xrange(self.F)]
self.bi[item] = 0
self.mu /= cnt
def train(self):
'''随机梯度下降法训练参数P和Q
'''
for step in xrange(self.max_iter):
for user, rates in self.rating_data:
z = [0.0 for f in xrange(self.F)]
for item, _ in rates:
for f in xrange(self.F):
z[f] += self.Y[item][f]#用户观看过物品的评分集合加和,即虚拟物品向量,即∑Yjf
ru = 1.0 / math.sqrt(1.0 * len(rates))
s = [0.0 for f in xrange(self.F)]
for item, rui in rates:
hat_rui = self.predict(user, item, rates)
err_ui = rui - hat_rui
self.bu[user] += self.alpha * (err_ui - self.lmbd * self.bu[user])
self.bi[item] += self.alpha * (err_ui - self.lmbd * self.bi[item])
for f in xrange(self.F):
s[f] += self.Q[item][f] * err_ui#每个物品的信息和误差相乘的累加
self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f])
self.Q[item][f] += self.alpha * (
err_ui * (self.P[user][f] + z[f] * ru) - self.lmbd * self.Q[item][f])
for item, _ in rates:
for f in xrange(self.F):
#Y的更新
self.Y[item][f] += self.alpha * (s[f] * ru - self.lmbd * self.Y[item][f])
self.alpha *= 0.9 # 每次迭代步长要逐步缩小
def predict(self, user, item, ratedItems):
'''预测用户user对物品item的评分
'''
z = [0.0 for f in xrange(self.F)]
for ri, _ in ratedItems:
for f in xrange(self.F):
z[f] += self.Y[ri][f]
return sum(
(self.P[user][f] + z[f] / math.sqrt(1.0 * len(ratedItems))) * self.Q[item][f] for f in xrange(self.F)) + \
self.bu[user] + self.bi[item] + self.mu
if __name__ == '__main__':
'''用户有A B C,物品有a b c d'''
rating_data = list()
rate_A = [('a', 1.0), ('b', 1.0)]
rating_data.append(('A', rate_A))
rate_B = [('b', 1.0), ('c', 1.0)]
rating_data.append(('B', rate_B))
rate_C = [('c', 1.0), ('d', 1.0)]
rating_data.append(('C', rate_C))
lfm = SVDPP(rating_data, 2)
lfm.train()
for item in ['a', 'b', 'c', 'd']:
print(item, lfm.predict('A', item, rate_A)) # 计算用户A对各个物品的喜好程度
ANN 多维空间检索算法,不完全是算法,是更偏工程的一种方法,时下正在流行的简单方式,从图像检索演化而来,复杂一点的方式一般使用DNN可以达到目的
每个用户、物品背后都有自己的向量映射在多为空间的点上,我们的目标就是把这些向量全部映射在一个空间内,求user最近的item点
稀疏场景适用物品召回:cb倒排(token)、cf倒排(user)
—召回能力有限
鲜花和巧克力在情人节的情况下可以关联起来,但是通过cb不能召回,通过cf需要很多很多用户共点击或者共现才会关联
那么这里如何计算和user距离近的点?之前我们使用cos或jaccard,但是我不能把所有的物品都遍历一遍,计算量过大,所以就引出了ANN的近邻检索annoy
Annoy目标:建立一个数据结构,在较短的时间内找到任何查询点的最近点,在精度允许的条件下通过牺牲准 确率来换取比暴力搜索要快的多的搜索速度
先圈出一部分集合,遍历集合取top
如果推荐的结果不理想,不喜欢,不是这个方法的问题,而是embedding方式的问题
那么这个集合如何圈呢?
方案:随机选择两个点,然后根据这两个点之间的连线确定一个可以垂直等分线段的超平面,灰色是两点的连 线,黑色是超平面
从而由里面的点集合就构成了叶子节点,最终形成整棵树
建立二叉树结构用于表示空间分布,每一个节点表示一个子空间
假设,如果两个点在空间彼此靠近,任何超平面不会将他们分开,如果我们搜索空间中的任意一点,和其距离 近的点为推荐候选,通过对二叉树的遍历,可以完成
重复上页步骤,继续分割 ,过程很像Kmeans要求:每个子节点包含数据不超过K个(10):
如果落在这个空间内的节点候选太少怎么办?或者本来两个点距离很近,但是被两个空间分割导致不能计算,那么我们就拓宽区域、多建几棵树,每次建立长得样子都不太一样。
annoy只是多维空间检索中的一种方法,其他还有:
KD-Tree (KNN-开始不随机,直接找到全局最优,速度慢,建树慢)
局部敏感哈希LSH
HNSW
OPQ等等
ANN实践:
annoy安装:pip
import sys
from annoy import AnnoyIndex
a = AnnoyIndex(3)#建立3颗树
a.add_item(0, [1, 0, 0])#添加用户和item点
a.add_item(1, [0, 1, 0])
a.add_item(2, [0, 0, 1])
a.build(-1)
print(a.get_nns_by_item(0, 100))#与0这个用户最近的top100集合
print(a.get_nns_by_vector([1.0, 0.5, 0.5], 100))#与这个item vector 最近的top100集合
下面这个代码是什么意思呢?随着我们候选集合圈的缩小,我们的计算量也在缩小,那么我们目标是让这个候选集合的top和全局的top尽量一致,也就是说要在计算量和召回率之间做一个权衡,那么全局的top我们就只能通过暴力遍历来知道答案了。
from __future__ import print_function
import random, time
from annoy import AnnoyIndex
try:
xrange
except NameError:
# Python 3 compat
xrange = range
n, f = 100000, 40#初始化10w个点,40颗树
t = AnnoyIndex(f)
for i in xrange(n):
v = []
for z in xrange(f):
v.append(random.gauss(0, 1))#高斯分布初始化点
t.add_item(i, v)#添加在树里
t.build(2 * f)
t.save('test.tree')#保存树
limits = [10, 100, 1000, 10000]#圈的大小
k = 10#10个候选
prec_sum = {}
prec_n = 100
time_sum = {}
for i in xrange(prec_n):
j = random.randrange(0, n)#随机选一个点作为用户
#print(j)
closest = set(t.get_nns_by_item(j, k, n))#求取与这个用户j最近的全局top10
#print(closest)
for limit in limits:
t0 = time.time()
toplist = t.get_nns_by_item(j, k, limit)#圈内的top10
T = time.time() - t0
found = len(closest.intersection(toplist))#用全局与圈内的top取交集
hitrate = 1.0 * found / k#准确率
#print(hitrate)
prec_sum[limit] = prec_sum.get(limit, 0.0) + hitrate
time_sum[limit] = time_sum.get(limit, 0.0) + T
print(prec_sum[limit])
for limit in limits:
print('limit: %-9d precision: %6.2f%% avg time: %.6fs'
% (limit, 100.0 * prec_sum[limit] / (i + 1),
time_sum[limit] / (i + 1)))
keyboard_arrow_left上一篇 : windows下静态使用QxOrm框架并使用泛型编程 (三) 基于ASP.NET的小清新风格的新闻发布系统 : 下一篇keyboard_arrow_right