

首页  思维导图  详情



RankRecommender

2016-10-17 09:59:24   0  举报





仅支持查看

AI智能生成

Rank&Recommendation

R&R

模版推荐

作者其他创作

大纲/内容

Rank Based on User's Vote

delicious

按照单位时间内用户的投票排名

优点

算法简单

容易部署

内容更新相当快

缺点

排名变化不够平滑

缺乏自动淘汰旧内容的机制

容易引起马太效应

Hacker News排名算法

根据投票和时间因素进行排名

P:得票数，-1是为了减去发帖人

T：距离发帖的时间

G:T的权重

优点

同时考虑了得票数和时间因素

容易部署

内容变化比较平滑

新内容得到露出的机会

缺点

G的调整需要经验

不适合时效性不强的排序

只能投赞成票

Reddit社区排名算法

根据赞成票&反对票以及发帖时间进行排名

因素

帖子的新旧程度t

t=create_time-t0

create_time是发帖时间

t0是一个固定值

赞成票和反对票的差x

x=赞成票-反对票

投票方向y

帖子受肯定(或否定)的程度z

排名公式

赞成票与反对票的差额z越大，得分越高

前10个投票人与后90个投票人（乃至再后面900个投票人）的权重是一样的，即如果一个帖子特别受到欢迎，那么越到后面投赞成票，对得分越不会产生影响

<div style="widows: 1;">t越大，得分越高，即新帖子的得分会高于老帖子 </div>

y的作用是产生加分或减分

优点

同时考虑了赞成票&反对票已经发帖时间

可以展示少数派想法

缺点

对应有争议的帖子（赞成票和反对票相当）不能排到前面

假定同一时间有两个帖子发表，文章A有1张赞成票（发帖人投的）、0张反对票，文章B有1000张赞成票、1000张反对票，那么A的排名会高于B，这显然不合理

排名基本上由发帖时间决定

stackoverflow排名算法

考虑问题的得分，回答的数目以及问题的浏览次数

排名公式

Qviews（问题的浏览次数）

某个问题的浏览次数越多，就代表越受关注，得分也就越高

这里使用了以10为底的对数，用意是当访问量越来越大，它对得分的影响将不断变小

Qscore（问题得分）= 赞成票-反对票

Ascores（回答得分）

一般来说，"回答"比"问题"更有意义。这一项的得分越高，就代表回答的质量越高。

简单加总的设计还不够全面

Qage（距离问题发表的时间）和Qupdated（距离最后一个回答的时间）

如果一个问题的存在时间越久，或者距离上一次回答的时间越久，Qage和Qupdated的值就相应增大

随着时间流逝，这两个值都会越变越大，导致分母增大，因此总得分会越来越小

自然冷却模型

牛顿冷却定律

物体的冷却速度，与其当前温度与室温之间的温差成正比

T(t)是温度（T）的时间（t）函数

温度变化（冷却）的速率就是温度函数的导数T'(t)

H代表室温，T(t)-H就是当前温度与室温之间的温差

常数α（α>0）表示室温与降温速率之间的比例关系。前面的负号表示降温。不同的物质有不同的α值

由上式可得

假定室温H为0度，即所有物体最终都会"冷寂"

定在时刻t0，该物体的温度是T(t0)，简写为T0

"冷却系数"是一个你自己决定的值

由上式可得：本期温度 = 上一期温度 x exp(-(冷却系数) x 间隔的小时数)

即：本期得分 = 上一期得分 x exp(-(冷却系数) x 间隔的小时数)

威尔逊区间

步骤

第一步，计算每个项目的"好评率"（即赞成票的比例）

第二步，计算每个"好评率"的置信区间（以95%的概率）

第三步，根据置信区间的下限值，进行排名。这个值越大，排名就越高

排名公式：

p<img src="file:///C:/Users/stephenzeng/AppData/Local/YNote/data/qq6B63765DDD9F4C3CE79ED79CF110D1BB/bfdd8e4a3f7e483aa1a87d2d1a4205f0/chart.png" data-attr-org-src-id="0DECA43F3EB2479FBA3A5DE49F2A6E97" data-attr-org-img-file="file:///C:/Users/stephenzeng/AppData/Local/YNote/data/qq6B63765DDD9F4C3CE79ED79CF110D1BB/bfdd8e4a3f7e483aa1a87d2d1a4205f0/chart.png" data-media-type="image" style="cursor: default; display: inline-block; margin-top: 8px; max-width: 800px; color: rgb(17, 17, 17); font-family: Georgia, serif; font-size: 16px; line-height: 24px; widows: 1; height: auto !important;">表示样本的"赞成票比例"，n表示样本的大小

表示对应某个置信水平的z统计量，这是一个常数，可以通过查表或统计软件包得到。一般情况下，在95%的置信水平下，z统计量的值为1.96

下限：

当n的值足够大时，这个下限值会趋向p<img src="file:///C:/Users/stephenzeng/AppData/Local/YNote/data/qq6B63765DDD9F4C3CE79ED79CF110D1BB/a8d17883886c4df8adf493aec4b9e216/chart.png" data-attr-org-src-id="E4467D2542D44E5FAB0913B1DDB3AC29" data-attr-org-img-file="file:///C:/Users/stephenzeng/AppData/Local/YNote/data/qq6B63765DDD9F4C3CE79ED79CF110D1BB/a8d17883886c4df8adf493aec4b9e216/chart.png" data-media-type="image" style="cursor: default; display: inline-block; margin-top: 8px; max-width: 800px; color: rgb(17, 17, 17); font-family: Georgia, serif; font-size: 16px; line-height: 24px; widows: 1; height: auto !important;">。如果n非常小（投票人很少），这个下限值会大大小于p<img src="file:///C:/Users/stephenzeng/AppData/Local/YNote/data/qq6B63765DDD9F4C3CE79ED79CF110D1BB/1ac07952b073470ebde8fc54a09dd4a5/chart.png" data-attr-org-src-id="17613ABBCDF643C494396D15C408120C" data-attr-org-img-file="file:///C:/Users/stephenzeng/AppData/Local/YNote/data/qq6B63765DDD9F4C3CE79ED79CF110D1BB/1ac07952b073470ebde8fc54a09dd4a5/chart.png" data-media-type="image" style="cursor: default; display: inline-block; margin-top: 8px; max-width: 800px; color: rgb(17, 17, 17); font-family: Georgia, serif; font-size: 16px; line-height: 24px; widows: 1; height: auto !important;">。实际上，起到了降低"赞成票比例"的作用，使得该项目的得分变小、排名下降。

优点

投票总数增加时，得分趋向于正向反馈占总反馈的比例，对于内容质量有较强的解释性

在总票数较少（个位数投票）和极端参数（真实比例接近 0 或 100%）的情形下，结果也能具有较高的准确性

置信区间大小可以通过参数控制

虽然二项分布是离散模型，但是由于得分表达式关于正负反馈次数的函数是连续的，因此可以引入非整数的投票（加权投票），同时不改变算法性质

<ul style="margin: 0.8em 0px; padding: 0px; color: rgb(34, 34, 34); font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 13px; line-height: 22.1px;"><li style="margin-bottom: 5px; list-style-position: inside;">得分的取值范围是 (0,1)，与投票总数无关。因此可以间接地用来对不同问题下的回答做归一化的质量比较。</li></ul>

缺点

对高票回答的惩罚可能会过于严重

Recommendation

基于流行度的算法

基于流行度的算法非常简单粗暴，类似于各大新闻、微博热榜等，根据PV、UV、日均PV或分享率等数据来按某种热度排序来推荐给用户

优点

适用于刚注册的新用户

缺点

无法针对用户提供个性化的推荐

优化方向

加入用户分群的流行度排序

协同过滤算法

基于用户的CF(User-based CF)

步骤

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">分析各个用户对item的评价（通过浏览记录、购买记录等）；</li></ul>

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">依据用户对item的评价计算得出所有用户之间的相似度；</li></ul>

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">选出与当前用户最相似的N个用户；</li></ul>

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">将这N个用户评价最高并且当前用户又没有浏览过的item推荐给当前用户。</li></ul>

示例图

首先我们根据网站的记录计算出一个用户与item的关联矩阵

然后计算每两个用户之间的向量距离（余弦距离）

最后，我们要为用户1推荐物品，则找出与用户1相似度最高的N名用户（设N=2）评价的物品，去掉用户1评价过的物品，则是推荐结果

基于物品的CF(Item-based CF)

步骤

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">依据浏览记录分析得出所有item之间的相似度；</li></ul>

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">对于当前用户评价高的item，找出与之相似度最高的N个item；</li></ul>

基于物品的CF计算方式大致相同，只是关联矩阵变为了item和item之间的关系，若用户同时浏览过item1和item2，则(1,1)的值为1

优点

CF算法确实简单，而且很多时候推荐也是很准确的

可以发现内容上完全不相似的信息，用户对推荐信息的内容事先是预料不到的

能够有效的使用其他相似用户的反馈信息，较少用户的反馈量，加快个性化学习的速度

缺点

依赖于准确的用户评分

在计算的过程中，那些大热的物品会有更大的几率被推荐给用户

冷启动问题。当有一名新用户或者新物品进入系统时，推荐将无从依据

在一些item生存周期短（如新闻、广告）的系统中，由于更新速度快，大量item不会有用户评分，造成评分矩阵稀疏，不利于这些内容的推荐

优化方向

对于矩阵稀疏的问题，有很多方法来改进CF算法。比如通过矩阵因子分解（如LFM），我们可以把一个nm的矩阵分解为一个nk的矩阵乘以一个k*m的矩阵

基于内容的算法

项目或对象是通过相关的特征的属性来定义，系统基于用户评价对象的特征，学习用户的兴趣，考察用户资料与待预测项目的相匹配程度

优点

基于内容的推荐算法能够很好地解决冷启动问题

不会囿于热度的限制，因为它是直接基于内容匹配的，而与浏览记录无关

通过列出推荐项目的内容特征，可以解释为什么推荐那些项目

已有比较好的技术，如关于分类学习方面的技术已相当成熟

缺点

过度专业化(over-specialisation)

用户的口味必须能够用内容特征形式来表达，不能显式地得到其它用户的判断情况

基于模型的算法

LR回归预测

GBDT回归预测

SVD矩阵因子分解

混合算法

基于内容的推荐&&协同过滤

变换（Switch）：根据问题背景和实际情况或要求决定变换采用不同的推荐技术

混合（Mixed）：同时采用多种推荐技术给出多种推荐结果为用户提供参考

特征组合（Feature combination）：组合来自不同推荐数据源的特征被另一种推荐算法所采用

层叠（Cascade）：先用一种推荐技术产生一种粗糙的推荐结果，第二种推荐技术在此推荐结果的基础上进一步作出更精确的推荐

特征扩充（Feature augmentation）：一种技术产生附加的特征信息嵌入到另一种推荐技术的特征输入中

元级别（Meta-level）：用一种推荐方法产生的模型作为另一种推荐方法的输入

非传统推荐算法

深度学习

学习等级

<span style="color: rgb(0, 0, 0); font-family: "Lantinghei SC", "Open Sans", Arial, "Hiragino Sans GB", "Microsoft YaHei", 微软雅黑, STHeiti, "WenQuanYi Micro Hei", SimSun, Helvetica, sans-serif; font-size: 14px; line-height: 21px; widows: 1;">Multi-armed bandits（E&E）

bandit算法

Thompson采样(以广告点击率预测为例)

<pre style="color: rgb(0, 0, 0); font-family: 宋体; font-size: 9pt;">np.argmax( np.random.beta(observed_data[:,0], observed_data[:,1]) )</pre>

一个广告的ctr是最大似然估计，是一个点估计，有偏

Thompson采样利用ctr的共轭先验(beta分布)来平滑点估计（Beta分布是一个连续分布，由于它描述ctr的分布，因此其取值范围为0到1），因此ctr较低的广告也有可能通过随机产生较大的预估值，达到探索（exploration）的目的

<div>参数分布随着曝光试验次数增加，会收敛峰度变高形态很尖的分布，而没法很快捕捉点击率随着时间变化的情况</div>

UCB算法（可以对比威尔逊区间）

其中加号前面是这个臂到目前的收益均值（ctr），后面的叫做bonus，本质上是均值的标准差，t是目前的试验次数（点击次数），Tjt是这个臂被试次数（曝光次数）

<pre style="color: rgb(0, 0, 0); font-family: 宋体; font-size: 9pt;">estimated_variances = estimated_means - estimated_means**2 </pre>

多种计算形式（其中两种）

<pre style="color: rgb(0, 0, 0); font-family: 宋体; font-size: 9pt;">estimated_means + np.sqrt( np.minimum( estimated_variances + np.sqrt(2*np.log(t)/totals), 0.25 ) * np.log(t)/totals )</pre>

<pre style="color: rgb(0, 0, 0); font-family: 宋体; font-size: 9pt;"><pre style="font-family: 宋体; font-size: 9pt;">UCB = estimated_means + np.sqrt( 2 * np.log(t)/totals )</pre></pre>

UCB算法（置信度95%）

<pre style="color: rgb(0, 0, 0); font-family: 宋体; font-size: 9pt;">UCB = estimated_means + 1.96*np.sqrt(estimated_variances/totals) </pre>

Epsilon-Greedy算法

选一个(0,1)之间较小的数epsilon

每次以概率epsilon（产生一个[0,1]之间的随机数，比epsilon小）做一件事：所有臂中随机选一个。否则，选择截止当前，平均收益最大的那个臂

简单粗暴

威尔逊区间

native

先试几次，每个臂都有了均值之后，一直选均值最大那个臂

更加简单粗暴

random算法

比native还差。。。

累计遗憾(regret)衡量

这个公式可以用来对比不同bandit算法的效果：对同样的多臂问题，用不同的bandit算法试验相同次数，看看谁的regret增长得慢

上下文感知推荐

LTR算法

pointwise

主要思想是将排序问题转化为多类分类问题或者回归问题

Pointwise完全从单文档的分类角度计算，没有考虑文档之间的相对顺序

McRank

pairwise

主要将排序问题归结为二元分类问题(Boost、SVM、神经网络)

张量分解

分解机

社会推荐

改进策略

用户画像

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">打通公司各大业务平台，通过获取其他平台的用户数据，彻底解决冷启动问题；</li></ul>

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">在不同设备上同步用户数据，包括QQID、设备号、手机号等；</li></ul>

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">丰富用户的人口属性，包括年龄、职业、地域等；</li></ul>

<ul style="margin-bottom: 0px; color: rgb(51, 51, 51); font-family: 微软雅黑; font-size: 16px; line-height: 24px; widows: 1; list-style-position: outside; list-style-image: none;"><li style="list-style: disc outside none; background-color: inherit;">更完善的用户兴趣状态，方便生成用户标签和匹配内容。</li></ul>

社交平台

通过用户的好友、兴趣群的成员等更快捷地找到相似用户以及用户可能感兴趣的内容，提高推荐的准确度

基于关联规则的推荐

优点

关联规则挖掘可以发现不同商品在销售过程中的相关性，在零售业中已经得到了成功的应用

不需要领域知识，能够发现新的兴趣点

缺点

关联规则的发现最为关键且最耗时，是算法的瓶颈，但可以离线进行

个性化程度低

评价指标

准确率

准确率就是最终的推荐列表中有多少是推荐对的