RankRecommender
2016-10-17 09:59:24 0 举报AI智能生成
Rank&Recommendation
作者其他创作
大纲/内容
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个投票人）的权重是一样的，即如果一个帖子特别受到欢迎，那么越到后面投赞成票，对得分越不会产生影响
t越大，得分越高，即新帖子的得分会高于老帖子
y的作用是产生加分或减分
优点
同时考虑了赞成票&反对票已经发帖时间
可以展示少数派想法
缺点
对应有争议的帖子（赞成票和反对票相当）不能排到前面
假定同一时间有两个帖子发表，文章A有1张赞成票（发帖人投的）、0张反对票，文章B有1000张赞成票、1000张反对票，那么A的排名会高于B，这显然不合理
排名基本上由发帖时间决定
stackoverflow排名算法
考虑问题的得分，回答的数目以及问题的浏览次数
排名公式
Qviews（问题的浏览次数）
某个问题的浏览次数越多，就代表越受关注，得分也就越高
这里使用了以10为底的对数，用意是当访问量越来越大，它对得分的影响将不断变小
Qscore（问题得分）和Qanswers（回答的数量）
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
表示样本的"赞成票比例"，n表示样本的大小
表示样本的"赞成票比例"，n表示样本的大小 表示对应某个置信水平的z统计量，这是一个常数，可以通过查表或统计软件包得到。一般情况下，在95%的置信水平下，z统计量的值为1.96
下限：
当n的值足够大时，这个下限值会趋向p
。如果n非常小（投票人很少），这个下限值会大大小于p
。实际上，起到了降低"赞成票比例"的作用，使得该项目的得分变小、排名下降。
。如果n非常小（投票人很少），这个下限值会大大小于p。实际上，起到了降低"赞成票比例"的作用，使得该项目的得分变小、排名下降。 优点
投票总数增加时，得分趋向于正向反馈占总反馈的比例，对于内容质量有较强的解释性
在总票数较少（个位数投票）和极端参数（真实比例接近 0 或 100%）的情形下，结果也能具有较高的准确性
置信区间大小可以通过参数控制
虽然二项分布是离散模型，但是由于得分表达式关于正负反馈次数的函数是连续的，因此可以引入非整数的投票（加权投票），同时不改变算法性质
- 得分的取值范围是 (0,1)，与投票总数无关。因此可以间接地用来对不同问题下的回答做归一化的质量比较。
缺点
对高票回答的惩罚可能会过于严重
Recommendation
基于流行度的算法
基于流行度的算法非常简单粗暴，类似于各大新闻、微博热榜等，根据PV、UV、日均PV或分享率等数据来按某种热度排序来推荐给用户
优点
适用于刚注册的新用户
缺点
无法针对用户提供个性化的推荐
优化方向
加入用户分群的流行度排序
协同过滤算法
基于用户的CF(User-based CF)
步骤
- 分析各个用户对item的评价（通过浏览记录、购买记录等）；
- 依据用户对item的评价计算得出所有用户之间的相似度；
- 选出与当前用户最相似的N个用户；
- 将这N个用户评价最高并且当前用户又没有浏览过的item推荐给当前用户。
示例图
首先我们根据网站的记录计算出一个用户与item的关联矩阵
然后计算每两个用户之间的向量距离（余弦距离）
最后，我们要为用户1推荐物品，则找出与用户1相似度最高的N名用户（设N=2）评价的物品，去掉用户1评价过的物品，则是推荐结果
基于物品的CF(Item-based CF)
步骤
- 分析各个用户对item的浏览记录；
- 依据浏览记录分析得出所有item之间的相似度；
- 对于当前用户评价高的item，找出与之相似度最高的N个item；
- 将这N个item推荐给用户。
基于物品的CF计算方式大致相同，只是关联矩阵变为了item和item之间的关系，若用户同时浏览过item1和item2，则(1,1)的值为1
优点
CF算法确实简单，而且很多时候推荐也是很准确的
能够过滤难以进行机器自动内容分析的信息
共享其他人的经验，避免了内容分析的不完全和不精确
有推荐新信息的能力
可以发现内容上完全不相似的信息，用户对推荐信息的内容事先是预料不到的
能够有效的使用其他相似用户的反馈信息，较少用户的反馈量，加快个性化学习的速度
缺点
依赖于准确的用户评分
在计算的过程中，那些大热的物品会有更大的几率被推荐给用户
冷启动问题。当有一名新用户或者新物品进入系统时，推荐将无从依据
在一些item生存周期短（如新闻、广告）的系统中，由于更新速度快，大量item不会有用户评分，造成评分矩阵稀疏，不利于这些内容的推荐
优化方向
对于矩阵稀疏的问题，有很多方法来改进CF算法。比如通过矩阵因子分解（如LFM），我们可以把一个nm的矩阵分解为一个nk的矩阵乘以一个k*m的矩阵 
基于内容的算法
项目或对象是通过相关的特征的属性来定义，系统基于用户评价对象 的特征，学习用户的兴趣，考察用户资料与待预测项目的相匹配程度
优点
基于内容的推荐算法能够很好地解决冷启动问题
不会囿于热度的限制，因为它是直接基于内容匹配的，而与浏览记录无关
能为具有特殊兴趣爱好的用户进行推荐
通过列出推荐项目的内容特征，可以解释为什么推荐那些项目
已有比较好的技术，如关于分类学习方面的技术已相当成熟
缺点
过度专业化(over-specialisation)
用户的口味必须能够用内容特征形式来表达，不能显式地得到其它用户的判断情况
基于模型的算法
LR回归预测
GBDT回归预测
SVD矩阵因子分解
混合算法
通 过组合后要能避免或弥补各自推荐技术的弱点
基于内容的推荐&&协同过滤
加权（Weight）：加权多种推荐技术结果
变换（Switch）：根据问题背景和实际情况或要求决定变换采用不同的推荐技术
混合（Mixed）：同时采用多种推荐技术给出多种推荐结果为用户提供参考
特征组合（Feature combination）：组合来自不同推荐数据源的特征被另一种推荐算法所采用
层叠（Cascade）：先用一种推荐技术产生一种粗糙的推荐结果，第二种推荐技术在此推荐结果的基础上进一步作出更精确的推荐
特征扩充（Feature augmentation）：一种技术产生附加的特征信息嵌入到另一种推荐技术的特征输入中
元级别（Meta-level）：用一种推荐方法产生的模型作为另一种推荐方法的输入
非传统推荐算法
深度学习
学习等级
Multi-armed bandits（E&E）
bandit算法
Thompson采样(以广告点击率预测为例)
np.argmax( np.random.beta(observed_data[:,0], observed_data[:,1]) )
一个广告的ctr是最大似然估计，是一个点估计，有偏
Thompson采样利用ctr的共轭先验(beta分布)来平滑点估计（Beta分布是一个连续分布，由于它描述ctr的分布，因此其取值范围为0到1），因此ctr较低的广告也有可能通过随机产生较大的预估值，达到探索（exploration）的目的
参数分布随着曝光试验次数增加，会收敛峰度变高形态很尖的分布，而没法很快捕捉点击率随着时间变化的情况
UCB算法（可以对比威尔逊区间） 
其中加号前面是这个臂到目前的收益均值（ctr），后面的叫做bonus，本质上是均值的标准差，t是目前的试验次数（点击次数），Tjt是这个臂被试次数（曝光次数）
estimated_variances = estimated_means - estimated_means**2
多种计算形式（其中两种）
estimated_means + np.sqrt( np.minimum( estimated_variances + np.sqrt(2*np.log(t)/totals), 0.25 ) * np.log(t)/totals )
UCB = estimated_means + np.sqrt( 2 * np.log(t)/totals ) UCB算法（置信度95%）
UCB = estimated_means + 1.96*np.sqrt(estimated_variances/totals)
Epsilon-Greedy算法
选一个(0,1)之间较小的数epsilon
每次以概率epsilon（产生一个[0,1]之间的随机数，比epsilon小）做一件事：所有臂中随机选一个。否则，选择截止当前，平均收益最大的那个臂
简单粗暴
威尔逊区间
native
先试几次，每个臂都有了均值之后，一直选均值最大那个臂
更加简单粗暴
random算法
比native还差。。。
累计遗憾(regret)衡量 
这个公式可以用来对比不同bandit算法的效果：对同样的多臂问题，用不同的bandit算法试验相同次数，看看谁的regret增长得慢
上下文感知推荐
LTR算法
pointwise
主要思想是将排序问题转化为多类分类问题或者回归问题
Pointwise完全从单文档的分类角度计算，没有考虑文档之间的相对顺序
McRank
pairwise
主要将排序问题归结为二元分类问题(Boost、SVM、神经网络)
张量分解
分解机
社会推荐
改进策略
用户画像
- 打通公司各大业务平台，通过获取其他平台的用户数据，彻底解决冷启动问题；
- 在不同设备上同步用户数据，包括QQID、设备号、手机号等；
- 丰富用户的人口属性，包括年龄、职业、地域等；
- 更完善的用户兴趣状态，方便生成用户标签和匹配内容。
社交平台
通过用户的好友、兴趣群的成员等更快捷地找到相似用户以及用户可能感兴趣的内容，提高推荐的准确度
基于关联规则的推荐
优点
关联规则挖掘可以发现不同商品在销售过程中的相关性，在零 售业中已经得到了成功的应用
不需要领域知识，能够发现新的兴趣点
缺点
关联规则的发现最为关键且最耗时，是算法的瓶颈，但可以离线进行
商品名称的同义性问题也是关联规则的一个难点
个性化程度低
评价指标
准确率
准确率就是最终的推荐列表中有多少是推荐对的
召回率
召回率就是推荐对了的占全集的多少
覆盖率
子主题
新颖度
新颖度是为了推荐长尾区间的物品
AUC
LR回归预测的评价标准
收藏
职业：数据挖掘
0 条评论
下一页
