推荐系统算法

1.ItemCF：

原文链接

  协同过滤是什么？
    协同过滤 (Collaborative filtering)，指的是，通过收集群体用户的偏好信息，自动化预测（过滤）个体用户可能感兴趣的内容。协（collaborating）是群体行为，过滤（filtering）则是针对个人的行为。

    ItemCF：Item Collaboration Filter，基于物品的协同过滤。
    核心思想：给用户推荐那些和他们之前喜欢的物品相似的物品。
    基本假设：物品A和物品B具有很大的相似度是因为喜欢物品A的用户大都也喜欢B。
    算法步骤：
        1.计算物品之间的相似度；
        2.根据物品的相似度和用户的历史行为给用户生成推荐列表；
    计算物品之间的相似度：

    |N(i)|是喜欢物品i的用户数，|N(j)|是喜欢物品j的用户数。
    对用户热度做惩罚：

        3.给用户推荐物品。
        用户u对物品j的兴趣程度：

        基本思想：如果要计算用户u与物品j的兴趣度， 先找到与j最相似的k个物品，再看用户u与这些物品的感兴趣程度，加权得到用户u对物品j的兴趣程度。

举个例子：

    ItemCF流程：
    1、根据用户下单数据计算poi相似度

       CalSim为计算poi相似度的模块，基于论文Scalable Similarity-Based Neighborhood Methods with MapReduce实现。

        CalSim模块：
        Preprocess: 将（user, poi, score）输入转换成 poi,(user, score);(user, score); ...形式，
针对不同相似度度量方法对score进行转换；
        Norm:针对不同相似度度量方法计算poi vector的norm；
        Reverse:将Preprocess中生成的poi,(user, score);(user, score); ...数据，转化成
user,(poi, score);(poi, score); ...的倒排形式，以便Similarity按照user进行数据分块；
        Similarity：组织mapper，combiner & reducer实施相似度计算。

理论部分已经介绍完毕，下面是代码部分：

#-*-coding:utf-8-*-'''Created on 2016-5-30@author: thinkgamer'''import mathclass ItemBasedCF:def __init__(self,train_file):self.train_file = train_fileself.readData()def readData(self):#读取文件，并生成用户-物品的评分表和测试集self.train = dict()     #用户-物品的评分表for line in open(self.train_file):# user,item,score = line.strip().split(",")user,score,item = line.strip().split(",")self.train.setdefault(user,{})self.train[user][item] = int(float(score))def ItemSimilarity(self):#建立物品-物品的共现矩阵C = dict()  #物品-物品的共现矩阵N = dict()  #物品被多少个不同用户购买for user,items in self.train.items():for i in items.keys():N.setdefault(i,0)N[i] += 1C.setdefault(i,{})for j in items.keys():if i == j : continueC[i].setdefault(j,0)C[i][j] += 1#计算相似度矩阵self.W = dict()for i,related_items in C.items():self.W.setdefault(i,{})for j,cij in related_items.items():self.W[i][j] = cij / (math.sqrt(N[i] * N[j]))return self.W#给用户user推荐，前K个相关用户def Recommend(self,user,K=3,N=10):rank = dict()action_item = self.train[user]     #用户user产生过行为的item和评分for item,score in action_item.items():for j,wj in sorted(self.W[item].items(),key=lambda x:x[1],reverse=True)[0:K]:if j in action_item.keys():continuerank.setdefault(j,0)rank[j] += score * wjreturn dict(sorted(rank.items(),key=lambda x:x[1],reverse=True)[0:N])#声明一个ItemBased推荐的对象Item = ItemBasedCF("uid_score_bid")Item.ItemSimilarity()recommedDic = Item.Recommend("xiyuweilan")for k,v in recommedDic.iteritems():print k,"\t",v

2.MF(ALS)矩阵分解

原理和代码可以参考https://blog.csdn.net/pearl8899/article/details/80336938，这是18年夏天使用该算法的时候，做的笔记，写的略微繁琐，这里精简一下。论文名字：matrix factorization techniques for recommender systems

先放一张图留着：

MF(matrix factorization)：矩阵分解，分解的是什么矩阵，元素如何获取？

       这个矩阵是上图的“Rating”，是user对deal，也就是item的行为，在论文中，Rating是电影评分的意思，在工业界中，这个Rating，可以是user对deal的点击、下单、浏览的汇总，至于汇总的方式是什么，根据你对业务的理解，自己定义。比如user对deal1点击1次算1分，下单算5分，也即是给不同行为加权累积。这里要注意，在使用spark ML中ALS的时候，要注意迭代分解的时候是显示还是隐式，像上述给出的Rating，那便是显示行为，人为的给这个user-deal之间强加了一个rating.

基于矩阵分解的推荐算法的核心假设是用隐语义（隐变量）来表达用户和物品，他们的乘积关系就成为了原始的元素。这种假设之所以成立，是因为我们认为实际的交互数据是由一系列的隐变量的影响下产生的（通常隐变量带有统计分布的假设，就是隐变量之间，或者隐变量和显式变量之间的关系，我们往往认为是由某种分布产生的。），这些隐变量代表了用户和物品一部分共有的特征，在物品身上表现为属性特征，在用户身上表现为偏好特征，只不过这些因子并不具有实际意义，也不一定具有非常好的可解释性，每一个维度也没有确定的标签名字，所以才会叫做 “隐变量”。而矩阵分解后得到的两个包含隐变量的小矩阵，一个代表用户的隐含特征，一个代表物品的隐含特征，矩阵的元素值代表着相应用户或物品对各项隐因子的符合程度，有正面的也有负面的。

ALS 是什么？----同SGD一样，求解参数的一种方法

      ALS 是交替最小二乘 （alternating least squares）的简称。在机器学习的上下文中，ALS 特指使用交替最小二乘求解的一个协同推荐算法。

ALS 的核心就是下面这个假设：打分矩阵是近似低秩的。换句话说，一个m*n的大矩阵 A 可以用两个小矩阵U(m*k)和V(n*k)的乘积来近似：

ALS 的名字里给出——交替最小二乘。ALS 的目标函数不是凸的，而且变量互相耦合在一起，所以它并不算好解。但如果我们把用户特征矩阵U和产品特征矩阵V固定其一，这个问题立刻变成了一个凸的而且可拆分的问题。比如我们固定U，那么目标函数就可以写成。其中关于每个产品特征vj的部分是独立的，也就是说固定U求vj我们只需要最小化就好了，这个问题就是经典的最小二乘问题。所谓“交替”，就是指我们先随机生成U0然后固定它求解V0,在固定V0求解U1，这样交替进行下去。因为每步迭代都会降低重构误差，并且误差是有下界的，所以 ALS 一定会收敛。但由于问题是非凸的，ALS 并不保证会收敛到全局最优解。但在实际应用中，ALS 对初始点不是很敏感，是不是全局最优解造成的影响并不大。

汇总：

        对于一个users-products-rating的评分数据集，ALS会建立一个user*product的m*n的矩阵。其中，m为users的数量，n为products的数量。但是在这个数据集中，并不是每个用户都对每个产品进行过评分，所以这个矩阵往往是稀疏的，用户i对产品j的评分往往是空的。

        ALS所做的事情就是将这个稀疏矩阵通过一定的规律填满，这样就可以从矩阵中得到任意一个user对任意一个product的评分，ALS填充的评分项也称为用户i对产品j的预测得分。所以说，ALS算法的核心就是通过什么样子的规律来填满（预测）这个稀疏矩阵

它是这么做的：假设m*n的评分矩阵R，可以被近似分解成U*(V)T，U为m*d的用户特征向量矩阵，V为n*d的产品特征向量矩阵（(V)T代表V的转置），d为user/product的特征值的数量。ALS算法的核心就是将稀疏评分矩阵分解为用户特征向量矩阵和产品特征向量矩阵的乘积交替使用最小二乘法逐步计算用户/产品特征向量，使得差平方和最小通过用户/产品特征向量的矩阵来预测某个用户对某个产品的评分。

spark ALS代码解释

常被应用于推荐系统。这些技术旨在补充用户-商品关联矩阵中所缺失的部分。MLlib当前支持基于模型的协同过滤，其中用户和商品通过一小组隐语义因子进行表达，并且这些因子也用于预测缺失的元素。为此，我们实现了ALS来学习这些隐性语义因子。在 MLlib 中的实现有如下的参数:

numBlocks 是用于并行化计算的分块个数 (设置为-1为自动配置)。

rank 是模型中隐语义因子的个数。就是平时的特征向量的长度。

maxIter：iterations 是迭代的次数。

lambda 是ALS的正则化参数。

implicitPrefs 决定了是用显性反馈ALS的版本还是用适用隐性反馈数据集的版本，如果是隐性反馈则需要将其参数设置为true。

alpha 是一个针对于隐性反馈 ALS 版本的参数，这个参数决定了偏好行为强度的基准。

itemCol:deal的字段名字，需要跟表中的字段名字是一样的。

nonnegative:是否使用非负约束，默认不使用 false。

predictionCol:预测列的名字

ratingCol：评论字段的列名字，要跟表中的数据字段一致。

userCol：用户字段的名字，同样要保持一致。

实践小技巧：
1.调参，推荐使用网格搜索进行调参。

包括三步： 

println("end als and begin paramGrid ----------")val paramGrid = new ParamGridBuilder().addGrid(als.maxIter,Array(50,100,150)).addGrid(als.rank,Array(32,64,128,256)).build()val evaluator = new RegressionEvaluator().setMetricName("rmse").setLabelCol("rating").setPredictionCol("prediction")println("end evaluator and begin TV ")val trainValidationSplit = new TrainValidationSplit().setEstimator(als).setEvaluator(evaluator).setTrainRatio(0.8).setEstimatorParamMaps(paramGrid).setSeed(567812)println("begin tv model__________")val tvModel: TrainValidationSplitModel = trainValidationSplit.fit(training)

第一步：确定paramGrid。这里加入对迭代次数和分裂维度进行网格搜索。其实就是贪婪搜索，遍历每一种可能。

第二步：确定评估方法evaluator。这里用rmse进行评估。

第三步：TV方法进行训练。

第四步：可能需要模型之间的转换。

2. ALS中还有一个加速分解的参数：

.setNumBlocks(200)

这个参数官网文档说这个参数可以设置为-1，加速分解，但是我将其设置为-1的时候，出bug，说是该参数设置无效。因此只能尽量的将这些参数设置的大一些，加速矩阵分解。我采用了rating矩阵中有5亿数据进行分解，分200块，速度确实提高了不少，具体没有衡量。

3.

写在最后，感谢孟祥瑞大佬、铭霏大佬以及各位大佬在als在sparkML中的实现。

参考博客：

1.https://blog.csdn.net/u012102306/article/details/51097502
2.关于矩阵分解用于推荐系统的博客：https:///recommendation-algorithm-based-on-matrix-decomposition.html

    补充知识：
        准确率：最终的推荐列表中推荐对了的比率。
        召回率：推荐对了的占全集的比率。