贝叶斯个性化推荐

一.介绍排序学习模型：
1.单点法：
单点法排序学习模型的每一个训练样本都仅仅是某一个查询关键字和某一个文档的配对。它们之间是否相关，与其他文档和其他查询关键字都没有关系单点法将文档转换为特征向量后，机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分，打分结果即是搜索结果。
2.配对法：
配对法的基本思路是对样本进行两两比较，构建偏序文档对，从比较中学习排序，因为对于一个查询关键字来说，最重要的其实不是针对某一个文档的相关性是否估计得准确，而是要能够正确估计一组文档之间的 “相对关系”。因此，配对法的训练集样本从每一个 “关键字文档对” 变成了 “关键字文档文档配对”。也就是说，每一个数据样本其实是一个比较关系，当前一个文档比后一个文档相关排序更靠前的话，就是正例，否则便是负例，如下图。试想，有三个文档：A、B 和 C。完美的排序是 “B>C>A”。我们希望通过学习两两关系 “B>C”、“B>A” 和 “C>A” 来重构 “B>C>A”。
3.列表法：
相对于尝试学习每一个样本是否相关或者两个文档的相对比较关系，列表法排序学习的基本思路是尝试直接优化像 NDCG（Normalized Discounted Cumulative Gain）这样的指标，从而能够学习到最佳排序结果。列表法的相关研究有很大一部分来自于微软研究院。列表法排序学习有两种基本思路。第一种称为 Measure-specific，就是直接针对 NDCG 这样的指标进行优化。目的简单明了，用什么做衡量标准，就优化什么目标。第二种称为 Non-measure specific，则是根据一个已经知道的最优排序，尝试重建这个顺序，然后来衡量这中间的差异。

二.BPR特点（对比传统方式）
传统的个性化推荐通常是计算出用户u对物品i的个性化分数,然后根据个性化分数进行排序。为了得到训练数据，通常是将所有观察到的隐式反馈作为正类，其余所有数据作为负类，如下图所示，左图为观察到的数据，右图为填充后的训练数据：

矩阵分解分析
矩阵分解是通过预测用户对候选物品的评分，然后根据这个预测评分去排序，最后再推荐给用户。这种方法是一种典型的单点法，无论是预测评分还是预测隐式反馈，本质上都是在预测用户对一个物品的偏好程度。但是这种方法有很大的问题，因为很多时候我们只能收集到少数正例样本，剩下的数据其实是真实负例和缺失值的混合构成（此处缺失值是指训练数据中除正例和负例外的未知数据，可以理解为未曝光或者曝光了的但是用户可能没有注意到缺失数据，所以缺失值中的样本即有可能是正例，也有可能是负例），而我们用这种方法构建训练数据的时候，往往无法确定负例是哪些，就只能把除正例以外的其他部分都当作是负例，这就会使得训练数据中负例的一部分其实是缺失值。把缺失值当作是负样本，再以预测误差为评判标准去使劲逼近这些样本。逼近正样本没问题，但是同时逼近的负样本只是缺失值而已，真正呈现在用户面前，并不能确定是不喜欢还是喜欢。而且，这样的模型仅能预测正例或负例，对于类别内的样本无法深入区别其重要性，不利于排序。

BPR 利用配对法的思想来构建偏序关系，它依然没有从无反馈数据中去区分负例样本和缺失值，不过和之前的方法不一样的是，BPR 不是单纯地将无反馈数据都看做是负例，而是与正例结合一起来构建偏序关系。这里的核心假设是，某用户对他有过反馈的物品的偏好程度一定比没有反馈过的物品高（这里的反馈一般指隐式反馈，如点击浏览等，不涉及负反馈），未反馈的物品包括真正的负例以及缺失值。BPR 试图通过用户的反馈矩阵 S 来为每一个用户构建出完整的偏序关系，也称全序关系，用>u>u表示。如下图：

三.BPR（贝叶斯个性化推荐）简介
1.反馈：
(1)显示反馈：
用户对物品的直接评分（直接对影视作品评分）
(2)隐式反馈：
用户对物品的交互（浏览时间等个人信息）
贝叶斯个性化推荐便是基于隐式反馈位用户推荐物品，BPR采用配对法，借鉴矩阵分解的方式。
2.BPR 两个基本假设:
(1)每个用户之间的偏好行为相互独立，即用户 u 在商品 i 和 j 之间的偏好和其他用户无关。
(2)同一用户对不同物品的偏序相互独立，也就是用户 u 在商品 i 和 j 之间的偏好和其他的商品无关。
（）相互独立：相互独立是设A,B是两事件,如果满足等式P(AB)=P(A)P(B),则称事件A,B相互独立,简称A,B独立.
（）偏序：设R是集合A上的一个二元关系，若R满足：
Ⅰ 自反性：对任意x∈A，有xRx；

Ⅱ 反对称性（即反对称关系）：对任意x,y∈A，若xRy，且yRx，则x=y；

Ⅲ 传递性：对任意x, y,z∈A，若xRy，且yRz，则xRz。

则称R为A上的偏序关系。

四.定义
U代表所有的用户user集合；I代表所有的物品item集合；S代表所有用户的隐式反馈，S⊆U×I。如下图所示，只要用户对某个物品产生过行为，就标记为+, 所有+样本构成了S。那些未观察到的数据（即用户没有产生行为的数据）标记为?。

I﹢(u)={i∈I:(u,i)∈S}代表了用户u产生过行为的物品集合
U﹢(i)={u∈U:(u,i)∈S}代表了对物品i产生过行为的用户集合

BPR 用来解决隐式反馈的推荐排序问题，假设有用户集 U 和物品集 I，当用户 u（u∈U）在物品展示页面点击了物品 i（i∈I）却没有点击同样曝光在展示页面的物品 j（j∈I），则说明对于物品 i 和物品 j，用户 u 可能更加偏好物品 i，用配对法的思想则是物品 i 的排序要比物品 j 的排序更靠前，这个偏序关系可以写成一个三元组 <u,i,j>，为了简化表述，我们用 >u符号表示用户 u 的偏好，<u,i,j> 可以表示为：i>uj。单独用 >u代表用户 u 对应的所有商品中两两偏序关系，可知 >u⊂I²，且 >u 满足下面的特性：

完整性：∀i,j∈I:i≠j⇒i>uj∪j>ui
反对称性：∀i,j∈I:i>uj∩j>ui⇒i=j
传递性：∀i,j,k∈I:i>uj∩j>uk⇒i>uk

同时，BPR也用了和funkSVD类似的矩阵分解模型，这里BPR对于用户集U和物品集I的对应的U×I的预测排序矩阵X¯，满足：
（能力有限没法用简书打出这样，发图片吧）

那么对于任意一个用户u，对应的任意一个物品i，我们预测得出的用户对该物品的偏好计算如下：

五.算法运算思路

我手推一下，如图所示：

六.BPR算法流程

输入：训练集D三元组，梯度步长α，
正则化参数λ,分解矩阵维度k
　　　　　　　　　　
输出：模型参数，矩阵W,H

随机初始化矩阵W,H
迭代更新模型参数：

如果W,H收敛，则算法结束，输出W,H，否则回到步骤2.

当我们拿到W,H后，就可以计算出每一个用户u对应的任意一个电影的排序分：x¯ui=wu∙hi，最终选择排序分最高的若干电影输出。

七.python代码
（1）BPR代码

# Implement BPR.
# Steffen Rendle, et al. BPR: Bayesian personalized ranking from implicit feedback.
# Proceedings of the twenty-fifth conference on uncertainty in artificial intelligence. AUAI, 2009. 
# @author Runlong Yu, Mingyue Cheng, Weibo Gao
#感谢前辈大佬

import random
from collections import defaultdict
import numpy as np
from sklearn.metrics import roc_auc_score
import scores

class BPR:
    user_count = 943
    item_count = 1682
    latent_factors = 20
    lr = 0.01
    reg = 0.01
    train_count = 1000
    train_data_path = 'train.txt'
    test_data_path = 'test.txt'
    size_u_i = user_count * item_count
    #U和V的潜在元素
    #随机初始化矩阵
    U = np.random.rand(user_count, latent_factors) * 0.01
    V = np.random.rand(item_count, latent_factors) * 0.01
    test_data = np.zeros((user_count, item_count))
    test = np.zeros(size_u_i)
    predict_ = np.zeros(size_u_i)

#输入所需数据
    def load_data(self, path):
        user_ratings = defaultdict(set)
        max_u_id = -1
        max_i_id = -1
        with open(path, 'r') as f:
            for line in f.readlines():
                u, i = line.split(" ")
                u = int(u)
                i = int(i)
                user_ratings[u].add(i)
                max_u_id = max(u, max_u_id)
                max_i_id = max(i, max_i_id)
        return user_ratings

#输入测试数据
    def load_test_data(self, path):
        file = open(path, 'r')
        for line in file:
            line = line.split(' ')
            user = int(line[0])
            item = int(line[1])
            self.test_data[user - 1][item - 1] = 1

#训练
    def train(self, user_ratings_train):
        for user in range(self.user_count):
            # s抽样检验一个用户
            u = random.randint(1, self.user_count)
            if u not in user_ratings_train.keys():
                continue
            # 从观察到的样本中抽取一个正样本
            i = random.sample(user_ratings_train[u], 1)[0]
            #从未被观测到的样本中抽取一个负样本
            j = random.randint(1, self.item_count)
            while j in user_ratings_train[u]:
                j = random.randint(1, self.item_count)
            u -= 1
            i -= 1
            j -= 1
            r_ui = np.dot(self.U[u], self.V[i].T)
            r_uj = np.dot(self.U[u], self.V[j].T)
            r_uij = r_ui - r_uj
            mid = 1.0 / (1 + np.exp(r_uij))
            temp = self.U[u]
            self.U[u] += -self.lr * (-mid * (self.V[i] - self.V[j]) + self.reg * self.U[u])
            self.V[i] += -self.lr * (-mid * temp + self.reg * self.V[i])
            self.V[j] += -self.lr * (-mid * (-temp) + self.reg * self.V[j])

#预测
    def predict(self, user, item):
        predict = np.mat(user) * np.mat(item.T)
        return predict

    def main(self):
        user_ratings_train = self.load_data(self.train_data_path)
        self.load_test_data(self.test_data_path)
        for u in range(self.user_count):
            for item in range(self.item_count):
                if int(self.test_data[u][item]) == 1:
                    self.test[u * self.item_count + item] = 1
                else:
                    self.test[u * self.item_count + item] = 0
        for i in range(self.user_count * self.item_count):
            self.test[i] = int(self.test[i])
        # 训练
        for i in range(self.train_count):
            self.train(user_ratings_train)
        predict_matrix = self.predict(self.U, self.V)
        #预测
        self.predict_ = predict_matrix.getA().reshape(-1)
        self.predict_ = pre_handel(user_ratings_train, self.predict_, self.item_count)
        auc_score = roc_auc_score(self.test, self.predict_)
        print('AUC:', auc_score)
        # Top-K评价
        str(scores.topK_scores(self.test, self.predict_, 20, self.user_count, self.item_count))

def pre_handel(set, predict, item_count):
    # 确保推荐在训练集中不是正项
    for u in set.keys():
        for j in set[u]:
            predict[(u-1) * item_count + j - 1]= 0
    return predict

if __name__ == '__main__':
    bpr = BPR()
    bpr.main()

（2）scores代码

# @author Runlong Yu, Mingyue Cheng, Weibo Gao

import heapq
import numpy as np
import math

def topK_scores(test, predict, topk, user_count, item_count):
    PrecisionSum = np.zeros(topk+1)
    RecallSum = np.zeros(topk+1)
    F1Sum = np.zeros(topk+1)
    NDCGSum = np.zeros(topk+1)
    OneCallSum = np.zeros(topk+1)
    DCGbest = np.zeros(topk+1)
    MRRSum = 0
    MAPSum = 0
    total_test_data_count = 0
    for k in range(1, topk+1):
        DCGbest[k] = DCGbest[k - 1]
        DCGbest[k] += 1.0 / math.log(k + 1)
    for i in range(user_count):
        user_test = []
        user_predict = []
        test_data_size = 0
        for j in range(item_count):
            if test[i * item_count + j] == 1.0:
                test_data_size += 1
            user_test.append(test[i * item_count + j])
            user_predict.append(predict[i * item_count + j])
        if test_data_size == 0:
            continue
        else:
            total_test_data_count += 1
        predict_max_num_index_list = map(user_predict.index, heapq.nlargest(topk, user_predict))
        predict_max_num_index_list = list(predict_max_num_index_list)
        hit_sum = 0
        DCG = np.zeros(topk + 1)
        DCGbest2 = np.zeros(topk + 1)
        for k in range(1, topk + 1):
            DCG[k] = DCG[k - 1]
            item_id = predict_max_num_index_list[k - 1] #
            if user_test[item_id] == 1:
                hit_sum += 1
                DCG[k] += 1 / math.log(k + 1)
            # precision, recall, F1, 1-call
            prec = float(hit_sum / k)
            rec = float(hit_sum / test_data_size)
            f1 = 0.0
            if prec + rec > 0:
                f1 = 2 * prec * rec / (prec + rec)
            PrecisionSum[k] += float(prec)
            RecallSum[k] += float(rec)
            F1Sum[k] += float(f1)
            if test_data_size >= k:
                DCGbest2[k] = DCGbest[k]
            else:
                DCGbest2[k] = DCGbest2[k-1]
            NDCGSum[k] += DCG[k] / DCGbest2[k]
            if hit_sum > 0:
                OneCallSum[k] += 1
            else:
                OneCallSum[k] += 0
        # MRR
        p = 1
        for mrr_iter in predict_max_num_index_list:
            if user_test[mrr_iter] == 1:
                break
            p += 1
        MRRSum += 1 / float(p)
        # MAP
        p = 1
        AP = 0.0
        hit_before = 0
        for mrr_iter in predict_max_num_index_list:
            if user_test[mrr_iter] == 1:
                AP += 1 / float(p) * (hit_before + 1)
                hit_before += 1
            p += 1
        MAPSum += AP / test_data_size
    print('MAP:', MAPSum / total_test_data_count)
    print('MRR:', MRRSum / total_test_data_count)
    print('Prec@5:', PrecisionSum[4] / total_test_data_count)
    print('Rec@5:', RecallSum[4] / total_test_data_count)
    print('F1@5:', F1Sum[4] / total_test_data_count)
    print('NDCG@5:', NDCGSum[4] / total_test_data_count)
    print('1-call@5:', OneCallSum[4] / total_test_data_count)
    return

结果：

八.python知识补充：
1.np.random.rand(d0,d1,d2……dn)
*注：使用方法与np.random.randn()函数相同
作用：
通过本函数可以返回一个或一组服从“0~1”均匀分布的随机样本值。随机样本取值范围是[0,1)，不包括1。
应用：在深度学习的Dropout正则化方法中，可以用于生成dropout随机向量（dl），例如（keep_prob表示保留神经元的比例）：
dl = np.random.rand(al.shape[0],al.shape[1]) < keep_prob
np.random.randn(d0,d1,d2……dn)
(1)当函数括号内没有参数时，则返回一个浮点数；
(2）当函数括号内有一个参数时，则返回秩为1的数组，不能表示向量和矩阵；
*(3）当函数括号内有两个及以上参数时，则返回对应维度的数组，能表示向量或矩阵；
(4）np.random.standard_normal（）函数与np.random.randn()类似，但是np.random.standard_normal（）的输入参数为元组（tuple）.
(5)np.random.randn()的输入通常为整数，但是如果为浮点数，则会自动直接截断转换为整数。
秩是线性代数术语，在线性代数中，一个矩阵A的列秩是 A的线性无关的纵列的极大数目。行秩是 A的线性无关的横行的极大数目。方阵的列秩和行秩总是相等的，因此它们可以简单地称作矩阵 A的秩。

2.np.zeros函数的作用
返回来一个给定形状和类型的用0填充的数组；
zeros(shape, dtype=float, order=‘C’)
shape:形状
dtype:数据类型，可选参数，默认numpy.float64
order:可选参数，c代表与c语言类似，行优先；F代表列优先

3.defaultdict
的作用是在于，当字典里的key不存在但被查找时，返回的不是keyError而是一个默认值，返回的是工厂函数的默认值，比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应0

4.readlines()
方法用于读取所有行(直到结束符 EOF)并返回列表，该列表可以由 Python 的 for... in ... 结构进行处理。
如果碰到结束符 EOF 则返回空字符串。

5.line.split(" ")
对于每一行，按照制表符切割字符串，得到的结果构成一个数组，数组的每个元素代表一行中的一列。

6.add() 方法用于给集合添加元素，如果添加的元素在集合中已存在，则不执行任何操作。

7.with as
获取一个文件句柄，从文件中读取数据，然后关闭文件句柄。

8.dot()返回的是两个数组的点积(dot product)
(1)如果处理的是一维数组，则得到的是两数组的內积（顺便去补一下数学知识）
*(2)如果是二维数组（矩阵）之间的运算，则得到的是矩阵积
(3)dot()函数可以通过numpy库调用，也可以由数组实例对象进行调用。a.dot(b) 与 np.dot(a,b)效果相同。
矩阵积计算不遵循交换律,np.dot(a,b) 和 np.dot(b,a) 得到的结果是不一样的。

9.random.randint(参数1，参数2)
参数1、参数2必须是整数
函数返回参数1和参数2之间的任意整数

10.np.exp(B) : 求e的幂次方,np.sqrt(B):求B的开方

11.np.mat():从分析它和array的区别来看吧
（1）格式不同：
mat可以从字符串或列表中生成；array只能从列表中生成
（2）计算方式不同：
array生成数组，用np.dot()表示矩阵乘积，（）号或np.multiply()表示点乘
mat生成数组，（）和np.dot()相同，点乘只能用np.multiply()
九.知识补充：
1.AUC:
AUC的全名是Area Under Curve，就是ROC曲线下的面积,往往使用AUC值作为模型的评价标准是因为很多时候ROC曲线并不能清晰的说明哪个分类器的效果更好，而作为一个数值，对应AUC更大的分类器效果更好。
总之：AUC是衡量二分类模型优劣的一种评价指标，表示预测的正例排在负例前面的概率。

2.MRR：
这是一个常用来衡量搜索算法效果的指标
是把标准答案在被评价系统给出结果中的排序取倒数作为它的准确度，再对所有的问题取平均。

3.MAP：
MAP 是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前(rank 越高)，MAP就可能越高。如果系统没有返回相关文档，则准确率默认为0。
单个主题的平均准确率是每篇相关文档检索出后的准确率的平均值

1.参考：https://www.biaodianfu.com/bpr.html
2.参考：https://www.cnblogs.com/pinard/p/9128682.html
3.参考：https://blog.csdn.net/qq_31747765/article/details/108462075
4.参考：百度百科
5.参考：https://www.jianshu.com/p/bbd258f99fd3
6.参考：http://blog.sina.com.cn/s/blog_662234020100pozd.html
7.参考：http://www.voidcn.com/article/p-hgmpcymt-sr.html
8.参考：https://www.runoob.com/python3/ref-set-add.html
9.参考：https://www.runoob.com/python/file-readlines.html
10.参考：https://ask.csdn.net/questions/235007
11.参考：https://www.cnblogs.com/luhuan/p/7925790.html
12.参考：https://www.jianshu.com/p/1a02a5b63c88
13参考：https://blog.csdn.net/weixin_44177568/article/details/106427896
14.参考：http://www.mamicode.com/info-detail-2664838.html