机器学习 24 、MF ANN

你挡我一时,挡不了我一世

发布日期: 2019-06-24 11:08:26 浏览量: 79
评分:
star star star star star star star star star star
*转载请注明来自write-bug.com

前文链接:https://write-bug.com/article/2696.html

MF(Matrix Factorization)

基于矩阵分解的推荐算法-隐语义模型:ALS、LFM、SVD、SVD++

在15年左右流行

ALS:

-交替最小二乘

我们之前学习的协同过滤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即分解矩阵后再相乘的预估分数,两个相减就是误差

未知数:

  1. Xuuser vector
  2. yiitem vector

如何求解最优值:求导=0

公式1:

导数为0,可得到:

同理对yi求导(公式2):

为什么叫交替二乘法?

这里的做法是让x和y交替下降:

  • 随机生成X、Y向量(初始化)

  • 固定Y,更新X(公式1)

  • 固定X,更新Y(公式2)

  • 第2、3步循环,直到满足收敛条件(RMSE)

——均方根误差

那么我们得到这两个小矩阵,可以做什么?

  1. item-item IK*KI=II
  2. User-UserUK*KU=UU

user与item的向量

LFM

思路和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实践:

  1. class LFM(object):
  2. def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500):
  3. '''rating_data是list<(user,list<(position,rate)>)>类型
  4. '''
  5. self.F = F#维度K
  6. self.P = dict()
  7. self.Q = dict()
  8. self.alpha = alpha#学习率
  9. self.lmbd = lmbd
  10. self.max_iter = max_iter#迭代轮数
  11. self.rating_data = rating_data#矩阵
  12. '''随机初始化矩阵P和Q'''
  13. for user, rates in self.rating_data:
  14. self.P[user] = [random.random() / math.sqrt(self.F)
  15. for x in xrange(self.F)]
  16. for item, _ in rates:
  17. if item not in self.Q:
  18. self.Q[item] = [random.random() / math.sqrt(self.F)
  19. for x in xrange(self.F)]
  20. def train(self):
  21. '''随机梯度下降法训练参数P和Q
  22. '''
  23. for step in xrange(self.max_iter):
  24. for user, rates in self.rating_data:
  25. for item, rui in rates:
  26. hat_rui = self.predict(user, item)
  27. err_ui = rui - hat_rui
  28. for f in xrange(self.F):
  29. self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f])
  30. self.Q[item][f] += self.alpha * (err_ui * self.P[user][f] - self.lmbd * self.Q[item][f])
  31. self.alpha *= 0.9 # 每次迭代步长要逐步缩小
  32. def predict(self, user, item):
  33. '''预测用户user对物品item的评分
  34. '''
  35. return sum(self.P[user][f] * self.Q[item][f] for f in xrange(self.F))
  36. if __name__ == '__main__':
  37. '''用户有A B C,物品有a b c d,列表模拟矩阵:'''
  38. rating_data = list()
  39. rate_A = [('a', 1.0), ('b', 1.0)]
  40. rating_data.append(('A', rate_A))
  41. rate_B = [('b', 1.0), ('c', 1.0)]
  42. rating_data.append(('B', rate_B))
  43. rate_C = [('c', 1.0), ('d', 1.0)]
  44. rating_data.append(('C', rate_C))
  45. lfm = LFM(rating_data, 2)
  46. lfm.train()
  47. for item in ['a', 'b', 'c', 'd']:
  48. print(item, lfm.predict('A', item)) # 预测计算用户A对各个物品的喜好程度

SVD

LFM有什么缺点?没有考虑客观的偏置,所以带偏置的LFM称为SVD

什么是偏置,比如说有的人很极端给一些物品很高或者很低的分数,而有的人给每个物品都很平均的分数,还有包括地区等等都会影响对物品的看法,所以就有一个偏置存在。

偏置:事件固有的,不受外界影响的属性。

  • 𝜇:训练集中所有评分的平均值

  • 𝑏𝑢:用户偏置,代表一个用户评分的平均值

  • 𝑏𝑖:物品偏置,代表一个物品被评分的平均值

更新:

SVD实践:

  1. class BiasLFM(object):
  2. def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500):
  3. '''rating_data是list<(user,list<(position,rate)>)>类型
  4. '''
  5. self.F = F
  6. self.P = dict()
  7. self.Q = dict()
  8. self.bu = dict()
  9. self.bi = dict()
  10. self.alpha = alpha
  11. self.lmbd = lmbd
  12. self.max_iter = max_iter
  13. self.rating_data = rating_data
  14. self.mu = 0.0
  15. '''随机初始化矩阵P和Q'''
  16. cnt = 0
  17. for user, rates in self.rating_data:
  18. self.P[user] = [random.random() / math.sqrt(self.F)
  19. for x in xrange(self.F)]
  20. self.bu[user] = 0#初始化bu
  21. cnt += len(rates)
  22. for item, rate in rates:
  23. self.mu += rate
  24. if item not in self.Q:
  25. self.Q[item] = [random.random() / math.sqrt(self.F)
  26. for x in xrange(self.F)]
  27. self.bi[item] = 0#初始化bi
  28. self.mu /= cnt#计算μ
  29. def train(self):
  30. '''随机梯度下降法训练参数P和Q
  31. '''
  32. for step in xrange(self.max_iter):
  33. for user, rates in self.rating_data:
  34. for item, rui in rates:
  35. hat_rui = self.predict(user, item)
  36. err_ui = rui - hat_rui
  37. #更新两个b
  38. self.bu[user] += self.alpha * (err_ui - self.lmbd * self.bu[user])
  39. self.bi[item] += self.alpha * (err_ui - self.lmbd * self.bi[item])
  40. for f in xrange(self.F):
  41. self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f])
  42. self.Q[item][f] += self.alpha * (err_ui * self.P[user][f] - self.lmbd * self.Q[item][f])
  43. self.alpha *= 0.9 # 每次迭代步长要逐步缩小
  44. def predict(self, user, item):
  45. '''预测用户user对物品item的评分,加偏置
  46. '''
  47. return sum(self.P[user][f] * self.Q[item][f] for f in xrange(self.F)) + self.bu[user] + self.bi[item] + self.mu
  48. if __name__ == '__main__':
  49. '''用户有A B C,物品有a b c d'''
  50. rating_data = list()
  51. rate_A = [('a', 1.0), ('b', 1.0)]
  52. rating_data.append(('A', rate_A))
  53. rate_B = [('b', 1.0), ('c', 1.0)]
  54. rating_data.append(('B', rate_B))
  55. rate_C = [('c', 1.0), ('d', 1.0)]
  56. rating_data.append(('C', rate_C))
  57. lfm = BiasLFM(rating_data, 2)
  58. lfm.train()
  59. for item in ['a', 'b', 'c', 'd']:
  60. print(item, lfm.predict('A', item)) # 计算用户A对各个物品的喜好程度

SVD++

任何用户只要对物品i有过评分,无论评分多少,已经在一定程度上反映了用户对各个隐因子的喜好 程度𝑦𝑖 = (𝑦𝑖1,𝑦𝑖2,…,𝑦𝑖𝐹),y是物品携带的属性,什么意思?比如说A买了3个item,B买了3个item,每个item背后有一系列feature vector,那么我们用A买的3个item背后的fea向量相加(实际计算是学习更新出来的,不一定是相加)代表一个虚拟的物品A,间接表达了这个用户的偏好程度,同理得到向量B,那么对于这个每个人背后的虚拟物品向量,就是y

所以这个打分是在P上又增加了一个类似于偏置的东西,并做了归一化

  • 𝑁(𝑢):用户u评价过的物品集合

  • 𝑏𝑢:用户偏置,代表一个用户评分的平均值

  • 𝑏𝑖:物品偏置,代表一个物品被评分的平均值

SVD++实践:

  1. class SVDPP(object):
  2. def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500):
  3. '''rating_data是list<(user,list<(position,rate)>)>类型
  4. '''
  5. self.F = F
  6. self.P = dict()
  7. self.Q = dict()
  8. self.Y = dict()
  9. self.bu = dict()
  10. self.bi = dict()
  11. self.alpha = alpha
  12. self.lmbd = lmbd
  13. self.max_iter = max_iter
  14. self.rating_data = rating_data
  15. self.mu = 0.0
  16. '''随机初始化矩阵P、Q、Y'''
  17. cnt = 0
  18. for user, rates in self.rating_data:
  19. self.P[user] = [random.random() / math.sqrt(self.F)
  20. for x in xrange(self.F)]
  21. self.bu[user] = 0
  22. cnt += len(rates)
  23. for item, rate in rates:
  24. self.mu += rate
  25. if item not in self.Q:
  26. self.Q[item] = [random.random() / math.sqrt(self.F)
  27. for x in xrange(self.F)]
  28. if item not in self.Y:#比之前svd多加了一个y,初始化y
  29. self.Y[item] = [random.random() / math.sqrt(self.F)
  30. for x in xrange(self.F)]
  31. self.bi[item] = 0
  32. self.mu /= cnt
  33. def train(self):
  34. '''随机梯度下降法训练参数P和Q
  35. '''
  36. for step in xrange(self.max_iter):
  37. for user, rates in self.rating_data:
  38. z = [0.0 for f in xrange(self.F)]
  39. for item, _ in rates:
  40. for f in xrange(self.F):
  41. z[f] += self.Y[item][f]#用户观看过物品的评分集合加和,即虚拟物品向量,即∑Yjf
  42. ru = 1.0 / math.sqrt(1.0 * len(rates))
  43. s = [0.0 for f in xrange(self.F)]
  44. for item, rui in rates:
  45. hat_rui = self.predict(user, item, rates)
  46. err_ui = rui - hat_rui
  47. self.bu[user] += self.alpha * (err_ui - self.lmbd * self.bu[user])
  48. self.bi[item] += self.alpha * (err_ui - self.lmbd * self.bi[item])
  49. for f in xrange(self.F):
  50. s[f] += self.Q[item][f] * err_ui#每个物品的信息和误差相乘的累加
  51. self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f])
  52. self.Q[item][f] += self.alpha * (
  53. err_ui * (self.P[user][f] + z[f] * ru) - self.lmbd * self.Q[item][f])
  54. for item, _ in rates:
  55. for f in xrange(self.F):
  56. #Y的更新
  57. self.Y[item][f] += self.alpha * (s[f] * ru - self.lmbd * self.Y[item][f])
  58. self.alpha *= 0.9 # 每次迭代步长要逐步缩小
  59. def predict(self, user, item, ratedItems):
  60. '''预测用户user对物品item的评分
  61. '''
  62. z = [0.0 for f in xrange(self.F)]
  63. for ri, _ in ratedItems:
  64. for f in xrange(self.F):
  65. z[f] += self.Y[ri][f]
  66. return sum(
  67. (self.P[user][f] + z[f] / math.sqrt(1.0 * len(ratedItems))) * self.Q[item][f] for f in xrange(self.F)) + \
  68. self.bu[user] + self.bi[item] + self.mu
  69. if __name__ == '__main__':
  70. '''用户有A B C,物品有a b c d'''
  71. rating_data = list()
  72. rate_A = [('a', 1.0), ('b', 1.0)]
  73. rating_data.append(('A', rate_A))
  74. rate_B = [('b', 1.0), ('c', 1.0)]
  75. rating_data.append(('B', rate_B))
  76. rate_C = [('c', 1.0), ('d', 1.0)]
  77. rating_data.append(('C', rate_C))
  78. lfm = SVDPP(rating_data, 2)
  79. lfm.train()
  80. for item in ['a', 'b', 'c', 'd']:
  81. print(item, lfm.predict('A', item, rate_A)) # 计算用户A对各个物品的喜好程度

ANN

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

  1. import sys
  2. from annoy import AnnoyIndex
  3. a = AnnoyIndex(3)#建立3颗树
  4. a.add_item(0, [1, 0, 0])#添加用户和item
  5. a.add_item(1, [0, 1, 0])
  6. a.add_item(2, [0, 0, 1])
  7. a.build(-1)
  8. print(a.get_nns_by_item(0, 100))#与0这个用户最近的top100集合
  9. print(a.get_nns_by_vector([1.0, 0.5, 0.5], 100))#与这个item vector 最近的top100集合

下面这个代码是什么意思呢?随着我们候选集合圈的缩小,我们的计算量也在缩小,那么我们目标是让这个候选集合的top和全局的top尽量一致,也就是说要在计算量和召回率之间做一个权衡,那么全局的top我们就只能通过暴力遍历来知道答案了。

  1. from __future__ import print_function
  2. import random, time
  3. from annoy import AnnoyIndex
  4. try:
  5. xrange
  6. except NameError:
  7. # Python 3 compat
  8. xrange = range
  9. n, f = 100000, 40#初始化10w个点,40颗树
  10. t = AnnoyIndex(f)
  11. for i in xrange(n):
  12. v = []
  13. for z in xrange(f):
  14. v.append(random.gauss(0, 1))#高斯分布初始化点
  15. t.add_item(i, v)#添加在树里
  16. t.build(2 * f)
  17. t.save('test.tree')#保存树
  18. limits = [10, 100, 1000, 10000]#圈的大小
  19. k = 10#10个候选
  20. prec_sum = {}
  21. prec_n = 100
  22. time_sum = {}
  23. for i in xrange(prec_n):
  24. j = random.randrange(0, n)#随机选一个点作为用户
  25. #print(j)
  26. closest = set(t.get_nns_by_item(j, k, n))#求取与这个用户j最近的全局top10
  27. #print(closest)
  28. for limit in limits:
  29. t0 = time.time()
  30. toplist = t.get_nns_by_item(j, k, limit)#圈内的top10
  31. T = time.time() - t0
  32. found = len(closest.intersection(toplist))#用全局与圈内的top取交集
  33. hitrate = 1.0 * found / k#准确率
  34. #print(hitrate)
  35. prec_sum[limit] = prec_sum.get(limit, 0.0) + hitrate
  36. time_sum[limit] = time_sum.get(limit, 0.0) + T
  37. print(prec_sum[limit])
  38. for limit in limits:
  39. print('limit: %-9d precision: %6.2f%% avg time: %.6fs'
  40. % (limit, 100.0 * prec_sum[limit] / (i + 1),
  41. time_sum[limit] / (i + 1)))
上传的附件
最近文章
eject