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

SVD

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

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

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

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

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

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

更新：

SVD实践：

  1. class BiasLFM(object):
  3.     def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500):
  4.         '''rating_data是list<(user,list<(position,rate)>)>类型
  5.         '''
  6.         self.F = F
  7.         self.P = dict()
  8.         self.Q = 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
  17.         '''随机初始化矩阵P和Q'''
  18.         cnt = 0
  19.         for user, rates in self.rating_data:
  20.             self.P[user] = [random.random() / math.sqrt(self.F)
  21.                             for x in xrange(self.F)]
  22.             self.bu[user] = 0#初始化bu
  23.             cnt += len(rates)
  24.             for item, rate in rates:
  25.                 self.mu += rate
  26.                 if item not in self.Q:
  27.                     self.Q[item] = [random.random() / math.sqrt(self.F)
  28.                                     for x in xrange(self.F)]
  29.                 self.bi[item] = 0#初始化bi
  30.         self.mu /= cnt#计算μ
  32.     def train(self):
  33.         '''随机梯度下降法训练参数P和Q
  34.         '''
  35.         for step in xrange(self.max_iter):
  36.             for user, rates in self.rating_data:
  37.                 for item, rui in rates:
  38.                     hat_rui = self.predict(user, item)
  39.                     err_ui = rui - hat_rui
  40.                     #更新两个b
  41.                     self.bu[user] += self.alpha * (err_ui - self.lmbd * self.bu[user])
  42.                     self.bi[item] += self.alpha * (err_ui - self.lmbd * self.bi[item])
  43.                     for f in xrange(self.F):
  44.                         self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f])
  45.                         self.Q[item][f] += self.alpha * (err_ui * self.P[user][f] - self.lmbd * self.Q[item][f])
  46.             self.alpha *= 0.9  # 每次迭代步长要逐步缩小
  48.     def predict(self, user, item):
  49.         '''预测用户user对物品item的评分，加偏置
  50.         '''
  51.         return sum(self.P[user][f] * self.Q[item][f] for f in xrange(self.F)) + self.bu[user] + self.bi[item] + self.mu
  54. if __name__ == '__main__':
  55.     '''用户有A B C，物品有a b c d'''
  56.     rating_data = list()
  57.     rate_A = [('a', 1.0), ('b', 1.0)]
  58.     rating_data.append(('A', rate_A))
  59.     rate_B = [('b', 1.0), ('c', 1.0)]
  60.     rating_data.append(('B', rate_B))
  61.     rate_C = [('c', 1.0), ('d', 1.0)]
  62.     rating_data.append(('C', rate_C))
  64.     lfm = BiasLFM(rating_data, 2)
  65.     lfm.train()
  66.     for item in ['a', 'b', 'c', 'd']:
  67.         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):
  3.     def __init__(self, rating_data, F, alpha=0.1, lmbd=0.1, max_iter=500):
  4.         '''rating_data是list<(user,list<(position,rate)>)>类型
  5.         '''
  6.         self.F = F
  7.         self.P = dict()
  8.         self.Q = dict()
  9.         self.Y = dict()
  10.         self.bu = dict()
  11.         self.bi = dict()
  12.         self.alpha = alpha
  13.         self.lmbd = lmbd
  14.         self.max_iter = max_iter
  15.         self.rating_data = rating_data
  16.         self.mu = 0.0
  18.         '''随机初始化矩阵P、Q、Y'''
  19.         cnt = 0
  20.         for user, rates in self.rating_data:
  21.             self.P[user] = [random.random() / math.sqrt(self.F)
  22.                             for x in xrange(self.F)]
  23.             self.bu[user] = 0
  24.             cnt += len(rates)
  25.             for item, rate in rates:
  26.                 self.mu += rate
  27.                 if item not in self.Q:
  28.                     self.Q[item] = [random.random() / math.sqrt(self.F)
  29.                                     for x in xrange(self.F)]
  30.                 if item not in self.Y:#比之前svd多加了一个y，初始化y
  31.                     self.Y[item] = [random.random() / math.sqrt(self.F)
  32.                                     for x in xrange(self.F)]
  33.                 self.bi[item] = 0
  34.         self.mu /= cnt
  36.     def train(self):
  37.         '''随机梯度下降法训练参数P和Q
  38.         '''
  39.         for step in xrange(self.max_iter):
  40.             for user, rates in self.rating_data:
  41.                 z = [0.0 for f in xrange(self.F)]
  42.                 for item, _ in rates:
  43.                     for f in xrange(self.F):
  44.                         z[f] += self.Y[item][f]#用户观看过物品的评分集合加和，即虚拟物品向量，即∑Yjf
  45.                 ru = 1.0 / math.sqrt(1.0 * len(rates))
  46.                 s = [0.0 for f in xrange(self.F)]
  47.                 for item, rui in rates:
  48.                     hat_rui = self.predict(user, item, rates)
  49.                     err_ui = rui - hat_rui
  50.                     self.bu[user] += self.alpha * (err_ui - self.lmbd * self.bu[user])
  51.                     self.bi[item] += self.alpha * (err_ui - self.lmbd * self.bi[item])
  52.                     for f in xrange(self.F):
  53.                         s[f] += self.Q[item][f] * err_ui#每个物品的信息和误差相乘的累加
  54.                         self.P[user][f] += self.alpha * (err_ui * self.Q[item][f] - self.lmbd * self.P[user][f])
  55.                         self.Q[item][f] += self.alpha * (
  56.                                     err_ui * (self.P[user][f] + z[f] * ru) - self.lmbd * self.Q[item][f])
  57.                 for item, _ in rates:
  58.                     for f in xrange(self.F):
  59.                         #Y的更新
  60.                         self.Y[item][f] += self.alpha * (s[f] * ru - self.lmbd * self.Y[item][f])
  61.             self.alpha *= 0.9  # 每次迭代步长要逐步缩小
  63.     def predict(self, user, item, ratedItems):
  64.         '''预测用户user对物品item的评分
  65.         '''
  66.         z = [0.0 for f in xrange(self.F)]
  67.         for ri, _ in ratedItems:
  68.             for f in xrange(self.F):
  69.                 z[f] += self.Y[ri][f]
  70.         return sum(
  71.             (self.P[user][f] + z[f] / math.sqrt(1.0 * len(ratedItems))) * self.Q[item][f] for f in xrange(self.F)) + \
  72.                self.bu[user] + self.bi[item] + self.mu
  75. if __name__ == '__main__':
  76.     '''用户有A B C，物品有a b c d'''
  77.     rating_data = list()
  78.     rate_A = [('a', 1.0), ('b', 1.0)]
  79.     rating_data.append(('A', rate_A))
  80.     rate_B = [('b', 1.0), ('c', 1.0)]
  81.     rating_data.append(('B', rate_B))
  82.     rate_C = [('c', 1.0), ('d', 1.0)]
  83.     rating_data.append(('C', rate_C))
  85.     lfm = SVDPP(rating_data, 2)
  86.     lfm.train()
  87.     for item in ['a', 'b', 'c', 'd']:
  88.         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
  4. a = AnnoyIndex(3)#建立3颗树
  5. a.add_item(0, [1, 0, 0])#添加用户和item点
  6. a.add_item(1, [0, 1, 0])
  7. a.add_item(2, [0, 0, 1])
  8. a.build(-1)
  10. print(a.get_nns_by_item(0, 100))#与0这个用户最近的top100集合
  11. 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
  5. try:
  6.     xrange
  7. except NameError:
  8.     # Python 3 compat
  9.     xrange = range
  11. n, f = 100000, 40#初始化10w个点，40颗树
  13. t = AnnoyIndex(f)
  14. for i in xrange(n):
  15.     v = []
  16.     for z in xrange(f):
  17.         v.append(random.gauss(0, 1))#高斯分布初始化点
  18.     t.add_item(i, v)#添加在树里
  20. t.build(2 * f)
  21. t.save('test.tree')#保存树
  23. limits = [10, 100, 1000, 10000]#圈的大小
  24. k = 10#10个候选
  25. prec_sum = {}
  26. prec_n = 100
  27. time_sum = {}
  29. for i in xrange(prec_n):
  30.     j = random.randrange(0, n)#随机选一个点作为用户
  31.     #print(j)
  32.     closest = set(t.get_nns_by_item(j, k, n))#求取与这个用户j最近的全局top10
  33.     #print(closest)
  34.     for limit in limits:
  35.         t0 = time.time()
  36.         toplist = t.get_nns_by_item(j, k, limit)#圈内的top10
  37.         T = time.time() - t0
  39.         found = len(closest.intersection(toplist))#用全局与圈内的top取交集
  40.         hitrate = 1.0 * found / k#准确率
  41.         #print(hitrate)
  42.         prec_sum[limit] = prec_sum.get(limit, 0.0) + hitrate
  43.         time_sum[limit] = time_sum.get(limit, 0.0) + T
  44.         print(prec_sum[limit])
  46. for limit in limits:
  47.     print('limit: %-9d precision: %6.2f%% avg time: %.6fs'
  48.           % (limit, 100.0 * prec_sum[limit] / (i + 1),
  49.              time_sum[limit] / (i + 1)))
上传的附件

keyboard_arrow_left上一篇 : 真实感图形学研究 机器学习 23 、BM25 Word2Vec : 下一篇keyboard_arrow_right

comment 0

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

发送私信

67
文章数
3
评论数
最近文章
Copyright @2018-WRITE-BUG.COM 技术支持-YCY科技 京ICP备16025663号-5
highlight comment
eject