什么是推荐系统

推荐系统是信息过滤系统，手段是预测用户对物品的评分和偏好。

他能做什么。推荐系统可以把那些最终会在用户和物品之间的连接提前找出来。

他需要什么。推荐系统需要已经存在的连接，从已经有的连接预测未来的连接。

构建推荐系统必须要有的思维模式

对关键元素重要性的认识。四个关键元素，即UI和UE，数据，领域知识和算法。他们的重要性依次递减，权重大概是4 3 2 1。

目标思维和不确定性思维。推荐系统解决的不是传统软件信息生产信息消费的信息流通本身，而是如何让流通更有效率，即他是一个信息过滤工具。目标思维，即量化一切，不能停留在“感觉推荐很准”的玄学层面。不确定性思维是用概率的眼光看待结果，绝大多数推荐算法是概率算法。

用户画像

用户画像是推荐算法向量化后的结果，用户画像不是推荐系统的目的，而是构建推荐系统的过程中产生的一个关键环节的副产品。

用户画像要注意维度和量化这两个重要的东西。

用户画像构建的三个方法，方法一，直接用原始数据作为用户画像内容，如注册资料，购买历史，阅读历史。方法二，堆积历史数据，做统计工作。方法三，用机器学习，学习出人类无法直观理解的稠密向量，他在推荐系统中承担的作用最大。

文本结构化算法

tf idf。tf是词t在文档d中出现的频率。idf是词t在整个语料库D（包含所有文档d i）中的稀有程度。idf等于log N除以n加1，n是词出现的文档数，N是总文档数。

标签选择算法

方法一，卡方校验，他检验“词和某个类别相互独立”这个假设是否成立，和这个假设偏离越大，则说明这个词和类别有关系，他就是关键词。卡方校验统计四个值，类别为c j的文本出现词w i的文本数A，词w i在非c j的文本中出现的文本数B，等等，用A B C D计算卡方值。卡方值越大，则偏离“词和类别相互独立”的假设越远，离“词和类别相互不独立”备择假设越近。

方法二，信息增益。需要先了解信息熵。当各个类别文本数量差不多时，信息熵比较大。其中少数类别文本数量明显较多时，信息熵较小。信息增益计算分为三步，先统计全局文本信息熵。然后统计每个词的条件熵，两者相减就是每个词的信息增益。

内容推荐

内容推荐就是一个包装成推荐系统的信息检索系统。他是推荐系统的孩童时代。要把内容推荐做好，重点是抓、洗、挖、算四个步骤。抓就是抓取数据补充内容。洗就是把抓来的数据洗干净，注意卫生。挖就是对内容的挖掘。算就是匹配用户的兴趣和物品的属性。

协同过滤

协同过滤是根据历史消费为你找到一群和你口味相似的用户，根据这些用户消费了你没有见过的物品，推荐给你。具体步骤，先准备用户向量，再用每个用户向量，两两计算用户相似度。再为每个用户产生推荐结果。

问题。问题一，稀疏矩阵存储，用CSR和COO。CSR有三个组成，数值、列号和行偏移共同编码。COO每个元素用三元组表示，行号、列号和数值。问题二，用户向量很长，计算相似度时间复杂度高，用向量采样计算和向量化计算。采样就是随机从向量取部分维度计算，这个算法叫DIMSUM算法，已经在spark中实现。向量化计算是说直接用向量计算，而不是循环实现。问题三，用户太多，把相似度计算拆成map reduce任务。

相似度计算方法

首先把数据分为两类，实数值和布尔值。

方法一，欧氏距离。每个坐标上取值相减，求平方和，最后输出平方根。可以用转化公式，把他的值变成-1到1或者0到1，即1除以1加上欧式距离。

方法二，余弦相似度。他和向量长度无关。他的归一化可能有问题，比如用户a对两个电影评分为1和2，用户b对两个电影评分为4和5，他们的相似度为0.98，这不对，因为用户a不喜欢这两个电影。解决方法是，先计算向量每个维度均值，然后减去均值，再计算余弦相似度。

方法三，皮尔逊相似度。他也是一种余弦相似度，他先对向量做了去中心化。他的取值范围是-1到1。

方法四，杰卡德相似度。他计算两个集合交集的元素个数在并集中所占的比例。适合布尔值向量。

交替最小二乘优化算法

任务是找到P和Q，让他们相乘后约等于R。

具体步骤。先随机初始化Q的元素值。再把Q当做已知，直接用线性代数方法求得矩阵P。得到P后，把P当做已知，故技重施，回去求解Q。不断交替，一直到误差可以接受为止。

预测行为和预测行为的推荐计算

One class就是把预测用户行为看成二分类，但实际数据只有用户干了什么，不干的数据没有表达。要对隐式反馈进行矩阵分解的话，交替最小二乘要做改进，即加权交替最小二乘，就是用户对没有反馈的物品认为他的评分是0，如果至少有一个隐式反馈则认为评分是1，次数作为评分置信度。

但是没有反馈的缺失值很多，他们都是0，这不合理，因为把他们当做负样本是我们的假设。解决方案是按照物品热门程度采样，即一个越热门的物品，用户越可能知道他的存在，在这种情况下，用户还没对他有反馈，则这就是真正的负样本。

预测行为的推荐计算。方法一，用专门设计的数据结构存储所有物品的隐因子向量，实现通过一个用户向量可以返回最相似的k个物品，可以参考脸书的开源实现Faiss。方法二，拿着物品的隐因子向量先做聚类，海量的物品会减少为少量的聚类，然后再逐一计算用户和每个聚类中心的推荐分数。

AUC用于相对排序，他计算模型关系的正样本排在其他样本前面的概率

AUC分母是M个正样本，和其他样本N两类样本相对排序的组合可能性，M乘以N。

AUC分子：第一名排序值r1，他排序不但比过了所有负样本，而且比过了自己以外的正样本。但后者是自己人，组合数要排除，总共有n减去M个组合，以此类推，排序值为rM的就贡献了rM减去1，把这些加起来就是分子。

BPR模型

构造样本，即：用户、物品1、物品2、两个物品相对顺序。两个物品相对顺序的取值为：如果物品1消费过，物品2没有，那么取值为1，正样本。如果相反，则为负样本。样本中不包括其他情况，即没有物品1和2都消费过，或都没有的情况。

目标函数，计算用户对每个物品的分数。如果物品1和2相对顺序为1，那么希望两个物品分数之差为正数，且越大越好。如果物品1和2相对顺序为0，那么希望两个物品分数之差为负数，且越小越好。目标函数就和物品1和2的矩阵分解预测分数之差有关，具体就是把这个分数之差用Sigmoid函数压缩到0到1之间。

融合之因子分解机模型FM

他是为了解决逻辑回归中特征组合的维度灾难问题，以及组合后特征样本稀疏，没办法在训练时更新参数。

因子分解机认为不用学习所有特征组合的权重，而是单独学习每个特征的隐因子向量，如果任何两个特征不小心实际使用时相遇了，需要组合，则各自掏出自己随身携带的隐因子变量做向量点积，就是两者组合特征的权重了。其实就是把原来的权重w i j，变成两个隐因子向量点积<vi,vj>。点积具有传递性，即特征a和b曾经在一些样本中一起出现过，特征b和c曾经在一些样本中出现过，那么特征a和c无论是否在样本中一起出现过，仍然是有联系的。

FM的改进FFM。之前的因子分解机认为每个特征有一个隐因子向量，FFM认为每个特征有f个隐因子向量。

wide and deep

融合排序用来做ctr预估，c可以是任何行为，如视频是否看完，看完后是否收藏，是否会分享到第三方平台，看完是否购买。

“宽模型”是线性模型，“深模型”是包含隐藏层的，给模型加了非线性变换。

常见的激活函数。Sigmoid，输入值是任意范围，输出是0到1之间。tanh，输入是任意范围，输出是-1到1之间。ReLU，当输入小于0时，输出为0，当输入大于0时，输出等于输入。softplus，是一条渐近线，输入趋于负无穷时，输出趋于0，输入趋于正无穷时，输出趋向于等于输入。

宽深模型是端到端的，不存在分阶段训练。

linUCB算法，改进UCB

简单版本ucb。假设D是候选臂在m次被选择中积累的特征，维度是m乘以d。这m次被选择，每次得到的用户点击或没点击，把这个反馈记录为m乘以1的向量，叫做C。这个候选臂的参数就是d乘以1的向量西塔。LinUCB认为，特征和参数相乘是收益，那么西塔就等于D的逆乘以C。但由于数据稀疏，求西塔时会用岭回归方法，在D中加上单位阵后再参与计算。linUCB每次选择臂时用各自的参数去计算期望收益和置信区间，然后按照置信区间上边界最大的输出结果。

把bandit算法和协同过滤结合起来，cofiba算法

cofiba算法的思路。1.在时刻t，有个用户访问推荐系统，推荐系统从已有的候选池子挑选一个最佳物品推荐给他，然后观察他的反馈，更新挑选策略。2.每个物品都有一个特征向量，且虽然给每个用户维护参数，但实际是用户所在的聚类类簇一起决定结果。3.用岭回归拟合用户权重向量，预测用户对每个物品的反馈。

cofiba具体步骤。1.计算用户i的bandit参数w。2.遍历候选物品。3.每个物品对应一个物品聚类类簇，每一个物品类簇对应一个全量用户聚类结果，遍历到每个物品时，可以判断当前用户属于哪个用户聚类，针对类簇求解岭回归参数。4.每个物品得到预测值和置信区间上界，挑出上界最大的物品作为推荐结果。

cofiba更新聚类的过程。用户聚类的更新，只针对被推荐物品k，对其用户子聚类中与用户i差异大的成员剔除边，产生新的用户连通分量。物品聚类的更新，对物品间的边，检查用户集合是否一致，不一致则删除边。

加权采样算法

加权采样、利用指数分布的加权采样、加权蓄水池采样。

信息流架构

主要模块。1.日志收集，他是排序训练的数据来源，记录用户在信息流上产生的行为。2.内容发布，用推或拉模式把信息流内容从源头发到受众端。3.机器学习，从日志训练模型，为每个用户即将收到的信息流提供打分服务。4.信息流服务，为信息流前端提供rest api。

数据模型。信息流基本数据包括用户内容和关系。内容就是activity，包含time，actor，verb，object，target，title，summary。关系就是连接，包含from，to，type（连接类型，如关注，加好友），affinity（连接强弱）。

内容发布。拉模式，信息流是用户刷新后实时产生的，优点是简单，缺点是随着连接数增加，操作复杂度增加，且服务很难高可用。推模式，当一个actor产生一条activity后，不管受众是否在线，是否刷新，都会立即将这条内容推送给用户，系统为每个用户单独开辟信息流存储。推模式优点是用户访问信息流时，操作简单，服务可用性高，缺点是大量写。解决方案是活跃度高的用户用推模式，低的用拉模式。

Netflix推荐系统架构

分为在线层、近线层、离线层。在线层实时响应用户请求，常放的计算逻辑有：模型预测阶段、商业目标的过滤或者调权逻辑。离线层数据源是Hadoop，实际是hdfs，用pig或hive取数据，用kafka管理，常放的逻辑有：模型训练和推荐结果计算。近线层，用storm，spark streaming，flink进行流计算。

实时推荐

给的实时，服务需要实时响应，最基本。

用的实时，特征实时更新，用户刚购买一个新物品，记录这个行为事件，参与到下一次协同过滤结果召回。这一层的操作只影响当前用户。

改的实时，模型实时更新。用户购买一个新物品，实时更新这个商品和所有该用户购买的其他商品的相似度，这一层影响的是全局推荐。

Storm实时流计算。他包含几个元素，spout，bolt，tuple，topology。spout是喷嘴，接入一个数据流，以喷嘴的形式把数据喷洒出去。bolt是螺栓，是两段水管的连接处，两端可以接入喷嘴，也可以接入另一个螺栓。tuple是元组，是流在水管中的水。topology，是拓扑结构，螺栓，和喷嘴，以及水管，构成有向无环图。注意，水管由storm提供。

怎么更新物品的相似度。可以用hoeffding不等式确定什么时候可以不再更新这个物品对的相似度。他告诉我们如果发现一个物品对的更新次数已经达到最少更新次数，可以不再更新，

数据驱动和实验平台abtest

流量分配如何避免流量偏置。流量偏置是同时做多个实验，如何避免前面的实验给后面的实验带来影响。谷歌的实验平台，用域，层，桶定义。他能做到避免流量偏置的原因：每一层每个桶受到上一层带来的影响被均匀分散在这一层的每一个桶中。在进行分桶时，不只是对cookie或uuid散列取模，还要加上层id，来让层和层之间相互独立。

每个实验需要累积多少流量才能得到实验结论？谷歌给出的公式可以回答，N大于等于10.5乘以（s除以西塔）的平方。s是实验指标的标准差，西塔是希望的检测敏感度，如检测到2%的ctr变化。上面的公式有90%概率相信结果显著。

推荐系统三十六式笔记