Archive

Archive for 2011年3月

简约风格的摄影照片范例

2011/03/31 留下评论
分类:五彩生活 标签:,

Google推“+1”社交搜索功能与Facebook竞争

2011/03/31 留下评论

北京时间3月31日凌晨消息,谷歌将于周三推出一个“+1”按钮,用户可以通过点击该按钮,向好友推荐特定搜索结果。

“+1”按钮会出现在谷歌搜索结果的旁边。目前,仅有部分用户能够使用这一功能。分析人士认为,这是谷歌为其产品增添社交网络特性,与Facebook竞争的重要举措。

Facebook一年前即已推出“赞”(Like)按钮,用户可通过点击该按钮,表达对某段内容的喜爱。这种个性化推荐系统被视为对传统搜索引擎的排名算法的挑战。

谷歌去年的营收高达290亿美元,其中很大一部分来自搜索广告。因此,对这家科技巨头而言,保持作为互联网信息主要来源的地位至关重要。

谷歌表示,“+1”按钮还会出现在谷歌显示广告旁边。谷歌高层周二表示,内部测试表示,加入推荐系统后,人们点击广告的几率更高。

 

此外,谷歌最终将允许第三方网站在自己的页面上使用“+1”按钮。

谷歌工程师马特·卡茨(Matt Cutts)表示,“+1”按钮是谷歌搜索技术演进的一部分,而不是对Facebook“赞”按钮的直接回应。

谷歌2009年推出了社交搜索。今年2月,该公司开始在一切曾被Twitter用户分享的搜索结果下方显示特殊片段。

目前,谷歌并未对排名算法做出调整,这意味着“+1”推荐尚未对搜索结果排名造成影响。某条被“+1”的搜索结果只有在本来就处于较靠前的位置时,用户才有可能看到它。

谷歌搜索“+1”按钮使用演示

谷歌搜索“+1”按钮使用演示

卡茨表示,谷歌正在进行评估,以决定是否将“+1”推荐作为排名要素之一。

如需使用这一新的推荐系统,用户必须创建一个谷歌个人主页(Google Profile)。用户的每一个“+1”推荐都会在他们的联系人网络中公开可见,而该网络是基于谷歌产品中现有的联系人系统,如谷歌电子邮件系统Gmail等。

卡茨表示,谷歌明确告知用户,一切“+1”推荐都是公开的,希望以此消除这一新功能可能带来的任何隐私疑虑。

新功能将于当地时间本周三向少量美国用户开放,其他美国用户可在当天晚些时候注册、体验“+1”按钮。(彦飞)

来自:http://www.alibuybuy.com/posts/57569.html

提问的智慧:利用决策树进行推荐系统新用户引导

2011/03/31 留下评论

图灵测试大家都很熟悉,通过问答形式来区分人和机器。小时候也做过假托《镜花缘》的逻辑题,需要你通过提问区分两个怪蜀黍谁来自“真话国”谁来自“假话国”。回到现实中,绝大多数推荐系统都无法回避冷启动问题——面对素不相识的用户,需要尽快把握其好恶给出尽量靠谱推荐。这时候通过问问题套瓷观察对方的反应,就是很常见和有效的做法(跟社交场合一样)。考虑到对象是形形色色千差万别的人,如何提出恰当给力的问题,就很值得研究和琢磨了。本文就来讲讲利用决策树的做法,源自论文《Adaptive Bootstrapping of Recommender Systems Using Decision Trees》。

背景
先说点题外话。几周前推荐系统论坛举办的相当成功。(这里感谢组织者的辛苦工作,以及淘宝同学的给力赞助。论坛官方已经放出材料和视频,几位同学的参会总结也相当给力,本文最后将一并给出链接。)

就我个人来讲,Koren博士的talk给我印象最为深刻。首先,极大的改造了我对netflix竞赛的看法。之前个人过于孤陋,觉得类似offline prediction竞赛,基于确定的数据集和目标函数,解决的不过是一个纯数学/算法问题:参赛者不用关心领域知识和用户需求(充其量看看数据的统计分布),不断的调整堆砌模型就ok了,离真正的推荐应用差之甚远。听了一圈发现,这些参赛者对于数据集其实有相当深刻的理解和思考,比如bias和temporal dynamics、用户不同反馈的理解,都很精彩且有启发性。这与实际构建推荐系统在很大程度上是契合的,首先要找到产品需求和数据中的规律,然后再加以利用。

其次,talk内容的针对性很强,不是一些形而上的抽象总结的或偏general的介绍,很多点跟实际应用的联系非常紧密。比如提到的bootstrapping a recommender,正是自己最近在琢磨的一个问题。最近构建的应用新用户比例过半,迫切需要解决对用户的judgement和profiling。由于工作没有深入到这里,之前只有一个大致的想法:人工或者机器找出一些区分度和接受度都较强的item,混合后提供给用户,通过用户的使用反馈逐渐确定其偏好;整个过程即可以是显式的用户引导(比如初始选择喜欢的item),也可以隐式的直接推荐。

结果Koren直接介绍了他们最近在这方面的工作,即《Adaptive Bootstrapping of Recommender System Using Decision Trees》这篇发表在WSDM2011的paper,提出用决策树的方法进行自适应的用户引导和判断。上周花时间找来读了一遍,写的相当清晰也很有意思。这里记下来备忘,如能帮同学们节约些时间更善。

设定
应用场景很明确,就是一个initial interview的过程,依次给出一些item要求用户进行显式的反馈,以此来构建对用户偏好的基本了解。
暂不考虑如何挑选,先来看看候选集合中的种子(即提出的问题)需要满足什么样的条件。作者认为,至少需要考虑以下几个因素:

  • 流行度(popularity)。需要尽量给出流行或用户熟悉的item,更容易让对方接受并做出选择;
  • 区分度(contenttion)。同样很好理解,好恶一边倒的item出现在候选序列中,不能提供多少信息量;
  • 覆盖度(coverage)。这里更多指item的泛化能力。如果这个item只能关联上非常少的其他item,后续真正可做的事情也会非常有限;

以上只是针对单个item,更理想的情况是考虑item间的关联和序列关系,充分利用之前答案的信息来调整后续的对话,打出一套组合拳。

应用于推荐引导的决策树
将决策树应用于推荐引导,是一个很好理解且自然的过程。从根节点开始,向用户提问,每个节点对应一个特定问题(item/电影);依据用户的不同反馈,进入相应的子节点;不断迭代上述过程,直到到达叶子节点或满足其他退出条件。用户的profilling过程,就是一条从根节点到叶子节点的访问路径。
先看看论文中给出的一棵生成树。

论文的工作都是基于Netflix数据集。如图可见,用户有三种回答,喜欢(like)、不喜欢(dislike)和不知道(unknown);rmse值是对落到该节点所有用户预测评分的均方误差,马上会讲到。

基本的构树过程比较简单:

  • 将所有的用户评分数据映射到<like, dislike, unknown>三维空间上。Netflix评分为1-5星,这里将1-3星映射为dislike ,4-5映射为like,未评分则对应unknown;
  • 从根结点开始,选择最佳的分割item,自顶向下建树;
  • 终止条件,同时考虑以下三种:
    • 设定树的最大深度;
    • 设定最佳分割item的误差阈值;
    • 设定当前节点的最少评分数量;

来看看对分割item的评价。整个决策树的优化目标是使得RMSE最小,这里为使树均衡和方便计算,在每个结点使用了和方差。

  • 对于给定用户集合t,我们都可以计算评分的和方差
    • 任选一个item i,可以计算针对该item的平方误差,R(i)是所有对item i评分的用户集合,是集合用户对item i的平均打分;
    • 和方差,即将该用户集合t所有评分item的平方误差相加;
  • 对于给定用户集合t,任选一个item i作为分割,都会将用户分成三组:评分喜欢、评分不喜欢、未评分,分别记为tL(i)、tH(i)、tU(i)。这样可以计算出三个集合的和方差之和。
  • 决策树的每个结点对应一个用户集合,即其父结点的一个特定划分。对于根结点,这个集合就是全体用户;
  • 为每个结点寻找最佳的分割item,就是找到一个item i使得三个集合和方差之和最小:

具体实现中,还有如下的一些考虑:

  • 在计算评分误差时,考虑user bias;
  • 通过将item的损失误差转化为其被选择的概率,支持一定程度上的随机树的生成;
  • 针对性的性能优化
    • tU(i)集合的用户数目是占大多数,通过公式变化转化为对结点全体用户t和tL(i)、tL(i)的运算;
    • 通过数据结构设计,将集合划分实现为对某item对应user数组的排序操作,由于是评分只有三个值,计算复杂度为O(n);

文中给出了构树的伪代码:

建树完成。当用户通过一系列选择到达某结点时,就可以使用该结点用户集合的平均评分来进行预测对各item的喜好,甚至可以基于预测评分得到一个ranked-list提供最简陋的推荐。文中作者也做了相关的讨论:

  • 首先需要考虑对于某个item该结点下用户评分数目过少的情况,这样很容易出现过拟和。因此引入层次平滑(hierarchical smoothing),将父结点对于该item的评分也纳入来考虑,实现的相当精巧;
  • 直接基于预测值排序的推荐可能过于保守,作者建议比较该结点的预测值跟全体用户的平均值,倾向取差值较大的item;

评估
最终的评估还是RMSE,计算测试集上,决策树判定节点的预测得分与用户实际打分的差异。作者对比了HELF和Entropy0(综合popularity和熵)、Var(利用item方差)等方法,如图所见,决策树的方法使用少数几个item的效果要优于其他方法使用20、30个item的结果。


同时还比较了训练集中用户评分数据的多少对效果的影响,基本上符合常识数据越多越靠谱。

评估部分相对讲的较少,有点意犹未尽。

多棵决策树
作者认为可以考虑使用多棵决策树:

  • 互为补充,防止用户对给出的item无感。通过数据分析可知,对于unknown分支上的用户,预测准确率低;
  • 用户界面考虑,更喜欢同一页面下评分多个item(这个地方存疑,不过一次多评几个也没啥坏处);
  • 决策树属于“weak learners”,使用多棵提升准确率;

多棵树的生成参见前述的随机生成,如何合并多棵树的结果,也是很有意思。一般使用均值、线性加权的做法,不是很适用——尤其是考虑对于不同用户不同树的贡献很可能是不同的。作者着重考虑了两类因素:

  • 命中的结点深度。假设反馈越多,判定应该越准;
  • 反馈类型,like、dislike、unknown分别考虑。假设置信度like > dislike >> unknown;

最后作者进行了验证,证明混合多棵树还是能有一定的效果提升。

一些感想

  • 整个思路和实现都并不复杂,简单是种大美。不需要额外的标注、不需要进行用户/item聚类,对于数据充足、缺乏较强领域知识和强悍pm的应用完全可以快速尝试;
  • 对于数据不充足的应用,类似的做法局限性较大。之前也跟几位同学讨论过,或许可以考虑把挖掘目标从领域内的兴趣描述(喜欢什么类型的音乐、电影),转移到对用户通用属性(如性别、年龄段)的挖掘上,带入先验知识再来做处理;

附:推荐系统高峰论坛的其他链接

 

分类:推荐系统 标签:,

偏好分析强悍图

2011/03/29 留下评论

分类:数据分析 标签:, ,

An Introduction to Data Mining

2011/03/29 1条评论