Mobvista 海外移动变现核心技术

之前受邀在QCON进行了名为海外移动变现核心技术的演讲。正好近期也在总结过去一段时间的工作,所以就直接在这儿总结了。

流量分类

Mobvista的移动变现业务,从流量侧来看,主要分三类流量:

  1. 外部Affliliates的流量,这个就是传统的买量,很多时候我们也不知道流量的来源,仅根据数据表现,以及运营人工经验评判流量渠道的好坏
  2. Mobvista的自有流量,其实也是和开发者谈下来的流量:和开发者签订协议,将Mobvista的SDK达到开发者的app中,之后出Mobvista的广告。一般内部我们就叫该系统为M系统
  3. 程序化买量:Mobvista建立DSP,从各大ADExchange买量

Affiliates买量过程人工运营成分比较多,而DSP可以是一个专门的TOPIC,所以此处就主要介绍Mobvista的自有流量业务的挑战,以及解决方案。

挑战

移动变现,特别是国际化移动变现过程中,面临的挑战非常多,以下是主要的挑战:1,广告样式多样化:banner,appwall, offerwall, native, interstitial, native video, rewarded video。 样式丰富,效果表现不一,导致要进行算法抽象,数据共享的时候存在较大挑战

2,转化路径较长:impression -> click -> install(安装激活) -> 应用内付费。。 甚至impression之前的展示广告是否返回成功,SDK加载是否成功等都是问题

3,流量参差不齐,不同国家间网络基础设施也有较大差异

4,移动广告的归因方式, 决定了产业中出现了较多的黑科技。这个之后值得用大篇幅进行介绍

以上这些问题,都是对算法的较大挑战,也早就叫较多算法优化点以及衍生的创收的黑科技。

技术应对方案

为了应对上述挑战, 我们必须有较为完善的架构, 算法解决这些挑战。 以下为Mobvista变下架构, 主要包含如下及部分,从左至右分别为流量侧到广告主侧

1.SDK:我们会开发SDK对开发者变现流量进行托管, SDK不仅支持IOS系统, 也支持ANDROID系统, 同时支持多种广告形式, 包括native, appwall和video等广告样式, 从功能上SDK主要负责广告分发, 展现控制, 缓存机制及消费空。 其中自创的缓存机制配合算法, 不仅能大幅减少广告请求交互, 提升广告加载, 展现速度,同时还能保证开发这的ECPM

2.Mobvista会对对外的API进行封装, 所以提供直接的OPEN API供开发者调用。 当然, 一般需要配合SDK的控制机制, 才能达到较高的受益

3.Mobvista同时提供完善的广告设置管理portal对广告素材,预算, 展现机制等进行管理控制,方便对广告的金细化运营

4.同时系统中还有完善的实验机制及样式模板管理, 方便整个系统对效果的优化

5.画红线的部分主要包括我们使用大数据平台对ECPM的模型训练及预估机制

对于模型相关的组件, 在省略了工程细节后, 主要是以下算法策略在系统中的重要组件。

与传统变现系统的较大差别, 在于我们为了处理长转化路径问题,对模型进行了拆分, 拆分为CTR预估模型及CVR模型;

同时为了解决多样性问题, 我们设计了定制的优质campaign探索机制, 及Mobvista的Exploration&Exploitation机制;

同时我们使用模型assabling的方法, 对LR, GBDT, FM等模型进行组合,提升预估精度

Ecpm就是我们预估的目标, 以下是我们对ecpm的拆解方法: 其中 ctr及cvr是未知量, 需要模型进行预估。

预估的方法比较直接: 我们寻找优质高效特征对样本进行描述, 同时使用点击和安装作为labels, 之后训练模型对ctr, cvr进行预估, 最后 使用 ecpm = 1000 * ctr * cvr * price 的方式计算ecpm, 并按照计算ecpm进行广告排序推荐

每次模型升级后会使用a/b test机制进行效果测试, 选出效果最好的模型

下图为我们的模型算法框架图。

为了适应我们全球化的变现业务需求, 我们的大数据机器学习平台是给予亚马逊aws云计算搭建的。

平台分为在线预估部分和离线部分,离线部分又分为日志处理及模型训练与配置模块

我们的日志具有较强的多样性及复杂性, 主要体现在两方面:

1.Mobvsita流量覆盖230+个国家, 故我们再多国及地区均有服务器, 数据需要从多地多服务器进行快速收集汇总

2.Mobvista有多条产品线, 不同产品线为适应业需求特性, 会使用不同存储系统对数据进行存储, 故须要从不同系统中对数据进行收集汇总, 包括DynamoDB, MongoDB, 以及内部的多种API接口

数据均使用AWS EMR分布式系统进行汇总, 计算机清洗。 我们会使用azkaban任务调度系统周期性定时启动生成EMR平台, 对数据进行处理, 处理后的日志按照访问实时性要求高低分别存放在 AWS redshift和S3上。 同时我们会根据数据量大小及计算任务复杂度动态调整EMR集群资源, 在保证计算任务实时性要求的同时, 减少计算资源浪费。 并在AWS上搭建机器学习平台进行模型训练。

更多内容可以参见PPT:

更多内容可直接访问: semocean.com

 

 

如何使用机器学习解决实际问题-以关键词相关性模型为例

本文以百度关键词搜索推荐工具字面相关性模型为基础,介绍一个机器学习任务的具体设计实现。包括目标的设定,训练数据准备,特征选择及筛选, 以及模型的训练及优化。该模型可扩展到语意相关性模型,搜索引擎相关性及LTR学习任务的设计实现。该模型的设计调研实现,也可以很容易移植解决其他包括语义相关性的问题

目标设定:提升关键词搜索相关性

作为一个搜索+推荐产品,百度关键词搜索推荐系统的产品形态是向凤巢用户推荐适合他业务的关键词。例如一个卖鲜花的广告主,他想在百度上做关键词搜索推广时,需要提交和他业务相关的关键词,而且提交的关键词需要业务相关,例如他需要提交和卖鲜花业务相关的关键词。例如鲜花快递,鲜花速递等。此时他可以在百度关键词搜索推荐系统中进行搜索查询,选择适合他的关键词。

百度关键词搜索推荐系统query搜索

这是一个典型的搜索问题,具体的从输入query,到触发,到排序等会涉及到很多因素,例如如何查倒排,如果处理地域因素等;要提升搜索的质量,我们首先需要保证输入的query和推荐出来的推荐词的相关性,此处我们要解决的主要问题, 就是如何快速,准确地判断两个关键词(输入query和推荐词)的相关性,需要特别注明的是,我们主要的目标是让用户觉得该产品结果很靠谱, 所以该处我们仅考虑字面相关性,更多的语意扩展该模型并未考虑。

注:该模型的调研实验实现方式, 可以很容易平移到语义相关性。例如加入更多语意特征,例如plsa的bm25特征和word2vec的相似度特征(或者和扩展的相关性校验,例如将待推荐词扩展为baidu搜索结果的摘要扩展)提高语义特征的贡献。

相关性也是所有搜索问题的基石,只不过在不同的系统中使用方式不一样, 在一般的搜索中,相关性占有较大权重, 排序基本就以相关性为依据; 在商业系统中,相关性则经常作为搜索展现的门槛用于控制商业推广结果的质量(如果仅考虑CTR, 用户搜索鲜花快递时,给用户展现艳照门的结果,CTR会更高,但相关性较差)。  当然,判断相关性我们可以简单使用某一种方法进行直接判定,例如直接进行两个关键词的TF-IDF计算,或是进行两个关键词的BM25。但这样的方式效果都不太理想,想要达到更好的效果,就需要使用更多特征,而更多特征很自然地,需要使用模型组合这些特征,达到最终的预期效果。

图:相关性在关键词系统中的位置

此处将会使用机器学习的方法解决该问题。本文以下内容会从数据准备, 特征选择, 模型选择, 模

型调优等步骤介绍百度关键词搜索推荐系统如何解决该问题

数据,特征,模型

说到使用机器学习解决问题,我们经常提到的优化思路就是3方面的优化: 数据,特征,模型。首先找到充足的,准确的label数据(该出仅考虑有监督学习任务,例如相关性,或是LTR),之后提取贡献较大的特征作为input space,以label作为output /ground true label,之后优化模型(Hypothesis) )。下面会分别从这3方面对整个优化过程进行阐述

准备训练数据

训练数据的获取一般有几种方式:

  1. 人工标注: 优点是质量较高,噪音较少;缺点是标注结果和标注者本身的认识相关,例如在搜索引擎中,判定苹果和手机的相关性,对于年轻人,一般都认为相关;但对于比较多的老人,可能认为不相关;另外一个缺点就是人工获取标注的成本较高
  2. 从日志中进行挖掘:优点是数据量相对更大,获取成本较低(编写几个hadoop脚本对日志进行统计);缺点是噪音较多,例如搜索引擎中的恶意抓取访问导致的噪音数据

在相关性模型中,一开始我们使用百度关键词搜索推荐系统的人工反馈数据作为label对模型进行训练,分别提取1.5W query-推荐词pair作为正负例进行特征提取,模型训练。

 

如图所示,在交互上,当用户喜欢该关键词时,就会点击‘大拇指’表示该结果符合用户需求(正反馈,该query-推荐词 pair可作为正例);如用户认为该关键词不符合需求,就会点击‘垃圾桶’,将该关键词扔入回收站(负反馈,该query-推荐词 pair 可作为负例)

在实验中,我们发现正例没有问题, 不过负例中会存在较多这样的情形: query-推荐词是相关的, 但该用户不做该业务,所以被定义为负例,所以负例个性化较强。所以后来我们让产品经理同学又对负例子进行筛选,重新标注1.5W负例,进行后续特征提取, 模型训练。

之后我们将正负例打散后(直接使用python random.shuffle)分成10份,进行cross-validation

模型训练前,先定标准和样本

注: 训练样本的挑选完全决定了我们的问题目标,所以在一开始就需要准确选择,如果可能,所有的case都最好人工来搞,或者至少需要人工review。 确定没有问题后,再开展后续工作。特别是相关性类似的问题,比较主观,例如PM和RD在该问题的判断上就可能存在一定差异。

确定完训练样本, 评估标准,之后再小布快跑, 优化模型。

特征提取

一般特征的选择及处理会极大地影响学习任务的效果,而进行特征选择的时候,一般是先增加特征,并实验效果。 对于相关性模型, 我们可以先将传统的信息检索的特征加上,这些特征一般分为以下几类:

  1. query/候选词的一般结构特征: 例如query/候选词长度,term数等
  2. query-候选词的相关性度量:例如TF-IDF, bm25, LMIR及多重变种, plsa相似度度量,word2vec语意向量相似度等; 很多时候,关键词自身信息较少,还可以使用关键词在搜索引擎上的摘要扩展进行相似度度量
  3. 关键词自身在信息检索维度的重要性度量,例如关键词idf, 从语言模型方面的重要度等

在一开始的时候,我们可以先将能够想到,构造出来的特征均加入特征向量进行实验,而且每加一类特征,都可以看下该类特征对整体目标的提升程度。以便对该特征的贡献度有一个直观的感受。

以下数据可以简单看出随着特征的增加,效果的提升,其中的特征仅加不减(模型使用random forest   进行二分类):

等到特征加得差不多,模型准确性已经提升不多的时候, 可以考虑砍特征,有一种比较简单粗暴有效的砍特征的方法,就是使用树模型,就是直接砍掉特征贡献程度及特征重要性较低的特征,例如直砍掉特征贡献度为0的特征,对相关性模型的准确性几乎没有影响

特征贡献度

当增加特征已经很难提升效果, 考虑到为了防止过拟合,同时考虑到模型online预测,需要对特征进行挑选。在使用树模型时,可以直接使用数节点特征贡献度和节点使用次数,判断是否需要去除该特征,以下为使用树模型进行选择特征的例子:

对于特征贡献度和分裂特征使用次数为0的特征,在调研时,直接去除对模型效果几乎没有影响,而且能提升预测的效率。

在选择特征的时候, 有一些经验值得分享:

  1. bm25特征及term weight特征对分类任务有极大贡献
  2. 一些单独的比值类特征并没有太大贡献,例如query,推荐词共同term与query term数,推荐词term数的比值,这些特征并没有太大贡献,但是这些特征与query,推荐词的term数结合到一起,贡献就非常多;所以有些特征需要联合在一起,才有较大作用。
  3. 特征选择需要和目标一致:例如word2vec是非常高大上,且非常靠谱的技术,但用在字面相关性,对目标并没有太大贡献(如果目标是语意相关,那么类似于PLSA,word2vec将会有很大贡献)
  4. 有些特征就就是用来解决特殊case的,虽然贡献不大,但需要保留(当然也可以直接设置为强规则与模型配合),例如query与推荐词拼音一致

模型选择

经典模型

最开始我们尝试了最大熵,SVM和adaboost模型, 考虑到online使用的效率,最终我们选择了adaboost模型作为线上使用的模型,虽然效果不是最好的,但使用简单的weak learner构建的模型的确比较快(参见博文:《adaboost》),并且使用adaboost进行上线并取得较好效果:上线后不仅召回增加,准确性上90%的case相关性高于等于原有结果(采用非模型的版本)

评估结果分布图(2到-2分别代表扩召回结果相关性高于、略高于、等于、略低于、低于线上策略)

集成树模型

现在特别喜欢使用树模型,因为使用的时候,连特征归一化都省了: 如果使用SVM类似的模型,还需要对特征进行归一化等处理, 但使用树模型,直接将特征向量及label扔给模型, 模型自己会根据信息增益,或是基尼系数等标准选择最合适的拆分点进行树节点的拆分(具体的拆分标准可参见博文:《使用impurity选择树模型拆分节点》),开源的树模型,例如大名鼎鼎的Quinlan的C4.5或是C5.0都在调研时都可以拿来试试作为特征选择的依据。

特别是集成树模型的出现,更是极大地提升了树模型效果。所以现在的项目中,我比较喜欢在增加特征的时候就使用集成树模型进行效果实验。 具体树模型使用参见《集成树类模型及其在搜索推荐系统中的应用

集成树模型配置选择

此处的配置选择和传统的模型参数稍有区别,该出的树模型配置主要指集成树模型中树的数量,每棵树的特征选择因子和样本使用因子等。在项目中,考虑到准确率和速度,最终确定的参数是树的数量是20, 特征选择因子和样本选择因子均为0.65(每棵树随机选择0.65的样本和特征进行训练)

具体产品效果可参见www2.baidu.com中百度关键词搜索推荐系统的排序结果:

如何个性化

首要需要考虑的是我们的数据样本,是否本身就是包含个性化的case(此处的答案是否定的); 假设我们的标注case是个性化的,也就是case中本身就包含了个性化结果时,在模型训练流程上其实并没有太大区别, 主要的区别就在于我们选取哪些能够区分这些个性化的特征, 例如百度凤巢中账户(单元)的plsa模型产出的pzd向量与query的相似度等

登录www2.baidu.com->关键词工具->搜索query->查看结果 即可。

更多内容也可参见: http://semocean.com

百度搜索引擎变现策略指标体系

下文就百度商业变现的指标体系进行概要描述,并针对一个类似于百度LBS系统的变现思路,阐述一个商业系统变现策略指标体系的建立过程。

为什么需要商业变现策略指标体系

一般情况下,一个互联网产品,或是一个移动端产品在发展前期,主要会关注流量及用户量的增长。当流量,用户量做到一定程度时,就会考虑商业变现。例如今日头条,美丽说,高德地图这样的产品现在都开始商业化变现。而要从变现效果,效率衡量整个系统,以及监控技术策略对系统变现的贡献时,就需要建立一套完善的策略指标体系监控系统当前的状况, 发现系统策略效果瓶颈并有的放矢地去提升。
之前在百度,在和一位高级技术经理聊天时,他就说过, 之所以百度内部一位从Google过来的VP很受老板的重视,一个非常大的贡献,就是他推动百度凤巢指标体系建立,保证公司收入灵活可控,保证每次百度都能在华尔街交出漂亮的财报
指标体系包含的内容

广告主关心的指标

在广告界的人士都知道广告主的这样一句名言:“我知道我投入的广告费用的一半是白费钱财,但问题是,我不知道是哪一半”。而搜索引擎的搜索一大优点,就是能够监控每一次搜索点击的效果。
对百度广告主来说,他们最关心的,和所有的商业投资一样,是:投资回报率 (ROI)。广告主们(商家)想知道在百度体系的广告的投入是否真的有回报,而这个回报是否能够超过投入的资金,超过的比例有多大,这一点上,搜索引擎商业变现系统是做了精心的设计的:
从商家的角度理解ROI,就要了解三个指标:
1.广告展现次数(简称show):当网民提供关键字,使用百度的搜索业务时候,相关的广告也会根据算法出现在页面相应的位置,用户投放的广告的展现次数,每天,每周,每月都会有统计。 当然,相对于传统的广告投放模式,只要展现了就要收费,百度对展现的广告是不收费的,哪怕用户看到了广告主企业的名字和推广口号,广告主已经获得了一定的广告收益,是要用户不点击广告链接,广告主不需要支付任何费用(针对竞价排名高,和右端广告而言)。这在传统的广告界是不可想象的,因为传统媒体,例如电视,包括门户网站上的banner广告,都是按照展现收费的:看到一次收一次的费用。
2.广告点击次数(简称clk) :用户看到广告后,点击了广告主提供的链接。 可以用每千次广告展现的点击率来计算。网民点了推广信息的链接。推广信息被点的次数被称为点击量,即Clicks,产生的费用叫做点击费用,平均到每次点击的费用被称为单次点击价格,即CPC,是Cost Per Click的缩写。推广信息点击量与展现次数之间的比值被称为点击率,即CTR,是Click-Through Rate的缩写,计算公式为:点击率=(点击量/展现量)×100%
3.点击率到商业收益的转换:用户点击了客户的广告,就会看到客户自己的网站页面,如果被客户提供的商业服务或者产品所吸引,而付费的话,那么客户就实现了一次成功的商业收益
因为商业系统必须要保证客户(广告主)的利益,这样才能长久合作,所以商业变现策略指标体系必须包含这些指标。
在类似于百度,360,或是Google这样的搜索引擎, 其能精准监控的,就是1,2, 对于最终的商业转化,因为是在商家的网站上完成的,所以除非网站上内嵌了搜索引擎单独提供的独立工具(例如百度的福尔摩斯),否则搜索引擎无法了解这些信息。
投资人关心的变现策略指标
以上是百度广告主需要关心的指标。对于百度这样的上市公司,每个季度的财报中都需要有公司详细的赚钱相关财报内容及各种指标分解,以便了解当前变现系统的健康程度及瓶颈及后续的突破点。
例如百度的投资人不仅关心这个季度百度多挣了多少钱,还会关心多挣的这些钱是来自于哪个环节的提升,是否可持续, 是否后续还有增长空间。 就和分析公司财务报表,或是分析股权收益率一致。
为了让大家对搜索引擎变现策略指标体系有一个对比了解,以下先用股权收益率说明问题。大家可以不用有较强的金融,财务知识也能看懂这个公式,而搜索引擎变现策略的指标体系,与此公式有异曲同工之处,都是将最终的收益(率),分解为各个相对独立的因素,以便发现系统挣钱效率的优势与瓶颈。
该公式主要的目的是让大家了解如何对最终目标指标进行拆解,如果大家不感兴趣可以跳过该节。
股权收益率
即在股市中,投资人购买的股票收益率, 设想一下,一个精明的投资人, 在购买了某个公司大宗股票后,一方面会关注每年的股票收益,另一方面也会分析股权收益是来自于哪些因素的上涨,这样才能分析公司增长是否健康,例如,股权收益率可以简单地使用以下公式计算ROE=净利润/权益。但如果要对这个公式进行细分,将其中对股权收益率相关的影响因素均拆分出来,那可以得到以下公式:
其中
  1. 税收负担比例:反映公司的税收负担情况,例如有一个季度百度的税率为腾讯的一半,因为百度和国家有什么高新技术的合作所以税收减免(记得百度可能是7%左右,腾讯13%左右,不是精确比例),类似的情况就可以在(1)中反映
  2. 为公司向债权人负担的利息比例, 借的钱越多,这个值越小
  3. 利润率:为每一块钱的销售额所带来的利润。
  4. 资产周转率:为公司资产的使用效率,例如家乐福,沃尔玛虽然利润率很低,但因为出货量大,所以照样赚钱
  5. 杠杆比例:公司资产与公司权益的比例,用于表示用于赚钱的钱中,有多少是自己的,有多少是别人的(例如银行)。例如:北京以前买房的人都发了,因为买的早,一方面房价便宜,一方面使用银行贷款,假设30%首付,那相当于剩下70%银行贷款在房产上的收益,也是自己的。
类似地,如果对百度商业变现体系的收入进行一个拆解,也能将其分解为类似的独立因子,对系统效率进行细化分析。
搜索引擎投资人关心的变现策略指标
从宏观上,我们假设投资人都是唯利是图的,收入是他们最关心的事。当然,很多投资人也会兼顾长远的收益,所以他们会关系收入是如何组成的。我们这里抛开运营,股权收益,利息支付,税收等各种公司的开销,我们仅考虑变现系统的名义收入,即搜索引擎中计费系统的计费和。此时可以将搜索引擎收入分解为以下独立因子:
Revenue =PV * PVR * ASN * CTR2 * ACP
以上公式就是百度,360,Google搜索广告变现收入的拆解。
要弄清楚以上公式的具体含义,需要了解下列指标的定义:
  1. CPM1:cost per thousand1 按每千次检索收费, 百度用户每使用百度一千次做搜索为百度带来的收益。 也就是用户使用了百度服务一千次所带来的百度的收入。这个是衡量百度赚钱能力的重要指标。是百度变现能力的基本衡量标准。是根据每个季度的总收入除以PV(Page View)算出来的。
  2. CPM2:cost per thousand2 按每千次展示收费,广告所在的网页被浏览了一千次,即认为该广告展示了一千次。 这个指标是衡量广告客户的广告展现了一千次的时候,客户交付的费用(注意客户是在用户点击广告后才付费的). 这个指标可以衡量用户对于广告的感兴趣程度。从广告客户的角度讲,也可以衡量在百度投放广告的费用多少,以及投放的有效性。
  3. CPM3:cost per thousand3 表示平均每千次有广告展现的检索请求对应的广告收入,衡量单次有广告展现检索的平均收入贡献。这个指标是衡量当搜索结果的页面有广告展现的时候,每展现一千次,百度能够拿到的收入。有的搜索结果是没有广告展示的(CPM1把这些PV也计算进去了)。
  4. CPC:cost per click 按每次点击收费,是目前最流行的搜索引擎营销的付费方式,即只有当用户点击观看了你的推广链接后,才发生费用。
  5. CPA:cost per action 按每次用户消费行动收费,被认为将是互联网广告未来必然的发展方向,但由于不同产品的广告对action的定义和回报率有太大差异,实现过于复杂,目前在全球范围尚无搜索引擎使用CPA收费的成功先例。
CTR——点击率,在这里特指广告或推广链接出现后被用户点击的机率。CTR还将可以进一步的细分。
  6. CTR1:表示平均每次检索请求对应的广告点击数,衡量单次广告检索的平均点击贡献。理论上 CTR1 可能大于 1。因为每次检索客户可以点击一个广告,看了后,在回去原来的检索页,点击下一个广告。
  7. CTR2:表示平均每次广告展现对应的广告点击数,衡量单次广告展现的平均点击贡献。
  8. CTR3:表示平均每次有广告展现的检索请求对应的广告点击数,衡量单次有广告展现检索的平均点击贡献。理论上 CTR3 可能大于 1。
  9. ARPU:户均消费,影响它的因素包括:点击流量大小、关键词的相关性、同一关键词的竞争度,以及客户在搜索引擎广告上的预算上限等。
  10. PV:检索量,百度搜索框的搜索次数
  11. ADPV:出广告的检索量,即PV中,有广告展现的搜索数量
  12. CLK:click number,广告的总点击次数
  13. CSM: 百度广告主的总广告费支出
  14. ASN:平均展现条数。即:如果展现了搜索推广广告,每次平均展现多少条
  15. ACP:Average Click Price 平均点击价格  总消费/总点击
  16. PVR:Page View Rates, PV比率,出广告的检索量 / 检索量
有了以上这些定义后,我们再来回顾变现系统的计算公式:
Revenue =PV * PVR * ASN * CTR2 * ACP
可以看出以上各因子表明了变现系统不同组成的效率
  1. PV:是百度能够用于变现的流量上限,由用户体验决定,百度越好用,口碑越好, PV越高。该指标在百度类似的搜索引擎公司,主要由搜索部门负责。
  2. PVR:就是PV中被用于变现的比例,PVR越高,说明在百度搜索中,出广告的概率越高,有可能导致用户体验的下降
  3. ASN:单次有广告展现的PV,展现的广告数量,表明单次有广告展现时的变现利用程度。ASN越高表明单次搜索出的广告越多,可能导致用户体验的下降
  4. CTR2:单条广告展现时, 广告北点击的概率。表明广告推的是否精准,是否满足用户需求(至少是感官上是否吸引用户)
  5. ACP:单次点击价格,相当于单价的高低
这样的指标分解非常有利于指导策略的优化,以下是几个case:
  • PV:搜索部门的重要指标,增加下降,都能立刻看出搜索部门的业绩,或是竞争对手带来的影响,例如,就百度而言,Google退出中国PV上升,360上了搜索, PV下降,都能直接看出来
  • 点击率预估:假设PV,PVR,ASN,ACP都固定,则要增加收入,需要提升用户对广告的点击率,此时可以用模型来对点击率预估,提升CTR2。各大搜索引擎公司,对CTR2的预估,基本上都是商业部门的重要机密,也是最重视的技术之一
  • 增加广告展现:在各上市公司(包括传统行业公司),都会有‘冲业绩’这么一说,就是极度末时,为了达到之前的营收计划,需要使用各种手段增加收入,例如我们经常听说的银行给高利息临时拉存款等,在百度则可以通过调参提升收入,比如增加ASN或是PVR,达到收入符合华尔街预期的效果
  • ASN的变化:如果收入的增长是来自于ASN的增长,则说明百度的点击卖得更贵了,广告主会不乐意。相反,ASN下降,说明点击卖便宜了,百度的收入有可能降低,所以类似于CTR2上升,ASN不变这样的策略,是最好的
有了以上定义即收入的拆解,则收入可以用其他集中形式表示:
Revenue = PV * CPM1
Revenue =PV * PVR * CPM3
Revenue =PV * PVR * ASN * CPM2
Revenue =PV * CTR1 * ACP
Revenue =PV * PVR * CTR3 * ACP
百度商业部门的工作,几乎每天都是在围绕着这些指标来进行的。每一次策略的调整,工作方式的改变,都希望在这些指标上做出正向的贡献,因为这些指标对百度的收入是直接造成影响的。从百度的收入(Revenue)的计算公式上就可以看出(每一种计算方法得到的结果都殊途同归)
如何建设LBS变现策略指标体系
拿百度地图类似的LBS产品为例,假设我们的转化漏斗路径是:推荐&搜索之后展示结果列表也,然后用户点击结果进入店家的表述页面(POI),之后如果用户感兴趣,则点击具体的团购,优惠券进行购买,搜索漏斗如下:
图:搜索漏斗
对应到线上系统,在评估衡量线上系统效果时,我们也需要分为这3阶段进行衡量,以及时发现线上策略效果的瓶颈所在, 快速找到提升重点。在以上3阶段中:
  1. 搜索or推荐:主要表明流量大小
  2. 点击详情页: 表现为用户带来的流量到详情页的浏览情况
  3. 转化:最终转化action
对于商业系统,我们最重要的目标就是保证在既定流量上,转化最高。
以下为我们需要关注的所有指标:
表:策略效果指标
如后续变现系统按转化收费,则整个LBS变现系统收入可定义为:
收入=  pv * pvr * easn * ctr2 * atr2 * aap
在产品的不同阶段,我们需要关注的重点不一样:
  • 在产品上线的阶段,我们需要关注用户体验,所以ctr2和atr2需要重点关注
  • 用户体验提升到一定程度,商户已经认可我们产品效果时,再考虑提升成单的单价(例如佣金等),同事可以考虑对商业POI进行放量,提升pvr和easn
物料召回及检索类指标
该类指标主要用于监控系统的检索量, 以及系统的召回能力。 检索量等指标是系统变现可以使用的所有资源,更多受用户产品影响;而召回能力相关指标则体现出CPR系统对商业物料的召回能力。
以下为重要指标说明:
  • 检索量: 发送到系统的所有请求量;通过统计检索日志条数得到;为能够变现的流量全集。
  • 查询用户数:所有发起请求的用户数;统计检索日志中去重后uid得到,体现参与检索的用户量。
  • 用户平均检索量:平均每个用户发起的请求数量;体现用户检索角度的活跃度。
  • 单次检索返回结果数:平均单次检索返回结果条数; 体现系统的召回能力(准确性参见相关性评估)
  • 商业结果检索量:出现商业结果的检索次数;
  • 商业结果检索用户数:出现商业结果的检索用户数;体现商业结果能够覆盖的客户群体
  • 商业检索占比:出现商业结果检索量占总体检索量占比;可根据改指标分析潜在变现流量。
  • 商业检索用户占比:看到商业结果的用户占所有检索用户占比;可根据该指标分析潜在变现用户。
  • 单次检索商业结果返回条数:一次出现商业结果的检索,返回的结果条数;
点击行为类指标
该类指标主要用于衡量用户浏览搜索/推荐结果后的点击行为。该过程为转化漏斗第二阶段。
以下为具体指标及含义:
  • 点击条数:被点击的POI数量(包括自然POI和商业POI)
  • 有点击检索次数:产生点击行为的检索次数(包括自然POI和商业POI)。
  • 有点击用户数:产生点击的用户数量。
  • 商业POI点击条数:商业POI被点击的数量。
  • 商业POI有点击检索次数:出现商业POI,且产生商业POI点击的次数。
  • 商业POI点击用户数:点击商业POI的去重用户数。
  • 单次检索点击率:平均每次检索点击POI的概率;该值理论上可能大于1
  • 单次检索商业POI点击率:平均每次检索,点击商业POI的概率;该值理论上可以大于1
  • 单条商业POI展现点击率:平均每条商业POI展现的点击概率;用于衡量每条商业POI曝光产生点击的效率。
  • 单次有商业结果展现点击率:平均每次有商业POI展现的检索的点击概率;用于衡量出商业POI的流量产生点击的效率。
效用类指标
该类指标主要用于衡量用户点击进入POI详情页后,根据详情页信息,做出最终决策的阶段(包括点击‘预订’,‘成单’,‘下载’等行为)。该过程处于转化漏斗的第三阶段,也是最终阶段。
以下为具体指标定义:
  • POI展现数:包括自然POI和商业POI的展现次数。
  • POI展现用户数:浏览POI的去重用户数。
  • POI详情页转化数:此处的转化根据每个入口可能有所不同。
  • POI详情页转化率:POI详情页转化数/POI详情页展现数。
  • 单次转化收费: 完成单次转化后,向商户收取的平均费用。
以上密密麻麻的指标,在不同的商业变现系统中会有所差别,但基本上都是按照用户产品形态及转换漏斗进行设定,而每个策略的上线,都会使用类似的指标体系来衡量策略对不同漏斗部分的效率影响。
更多内容也可参见: http://semocean.com

级联二步图关系挖掘关键词推荐系统及实现代码

youtube使用简单的共现思路, 实现视频的高效推荐。 受到该思路的启发, 我们基于百度凤巢广告主在广告库中提交的关键词, 更进一步设计出可级联的二部图关系挖掘算法框架, 实现亿量级关键词, 千万级别用户(单元结构)的高效推荐。 本文即对该算法的实现进行详细介绍,并在最后给出实验结果。
youtube 推荐算法
首先还是简单介绍下youtube使用的推荐算法。 符合google系一贯的风格, 算法很简单, 数据量很大, 效果很明显。
大家都知道youtube上有N多vedio,而且各种各样档次类型。而youtube将用户的需求分为3类:
  1. 查找具体video。直接通过搜索
  2. 查找某一topic的video。基本也可以通过搜索解决
  3. 没有明确目的, 随便看看打发时间娱乐
youtube算法,主要解决第三个需求, 使用top N方式推荐video供访问者浏览。而youtube的问题是视频数量太多,且视频的兴趣点较为分散(相对的amazon和netflix的需求则较为集中),所以google没有选择高大上的svd等复杂方法,而是简单的共现计算。论文中整个数据流的处理方式, 和传统的搜索引擎, 或是搜索推荐系统还是一致的, 基本分为: 候选的选择(检索系统中叫触发逻)找到可能推荐的候选, 排序(ranking过程)给出最终排序结果,并做top N截断
  • 候选vedio选择
youtube 使用关联规则的形式, 在24小时内所有用户session内找到共同访问(co-visitation)的video vi, vj
并计算,r(vi, vj) = cij/f(vi, vj)   vi, vj的关联程度可以使用该公式计算得出,  分母f最简单的方式就是ci*cj, cij为两个item共同出现的次数。之后根据阈值过滤r(vi, vj)即得到与vi关联的vj。 定义S为用户u看过的种子video集合, 则定义Ri为使用符合条件的r(vi, vj)得到的关联电影集合。
其中Ri为与vi关联的video,则C1(S)为使用种子电影S进行一次关联扩展后的电影集合,则可以定义:
则Cn(S)为种子video集合S进行n次扩展后的video集合。
以上思路虽然简单,但其中包含的一个特性是可以在相关性和种子集合数量间做一个权衡: 使用降低相关性的方法, 换取更多结果。
  • ranking
上述步骤为候选电影的挖掘方法, 之后需要对挖掘出来的种子video进行ranking,例如使用pv排序, 使用, 候选电影与user profile 的相关性等进行ranking。 当然此时还需要注意给出推荐理由(例如根据哪个种子电影进行推荐)以提升采纳率。
二部图实现思路简介
受到youtube二部图的启发, 我们设计开发了级联二部图, 基本思路是使用中间节点, 建立二步节点之间的路径(关系)计算左右两节点的相关性。
  • 二步跳转关系介绍
定义unit为一个凤巢中的单元(可理解为一组相关关键词), unit1与关键词‘礼品’相关, 而‘礼品’与‘礼品快递’关联, 此时通过两次二部图的链接, 即能找到unit1和‘礼品快递’的关联关系。
该级联二部图有两个特点:
  1. 二部图可以通过中间的节点建立关系: 只要能各自建立两边的节点(例如unit和关键词)与中间节点的关系,级联二部图两端,可以不是相同类别的item。例如unit1包含关键词‘礼品’, 而礼品与‘礼品快递’字面相关,则即使不包含‘礼品快递’, 算法仍然能够找到unit1与‘礼品快递’的关系。
  2. 可以进行多步扩展: 和youtube电影推荐算法类似, 该算法可以由级联二步扩展为级联多步, 当然, 实在牺牲准确性的前提下。
二步图的基本思想, 就是通过中间节点, 建立左右两特定节点之间的路径, 之后根据这些路径及权重, 算出左右两节点的相关性, 思路和random walk中价值传递的思路较为类似: 一个节点的价值, 最终流到那儿, 就说明这两个节点比较接近。
  • 具体挖掘步骤
步骤一:左右节点权重归一化, 可以使用L1-norm,或是L2-norm进行归一化, 之后得到每个左/右节点到中间节点的路径归一化权重。
步骤二:为了避免’哈利波特‘问题, 或我们经常说的’新华字典‘问题, 避免被多数人采用/提交的中间节点,需要对中间节点进行惩罚,降低部分中间节点的权重。
步骤三:计算左节点到右节点一条路径的权重, 路径的权重 = 左边权重 * 右边权重 * 通过惩罚值; 其中左右边权重通过步骤一计算得到, 通过惩罚值通过步骤二得到。
步骤四:根据连接某对左右节点的所有路径计算该对节点的相关性。
由上述4个步骤大家可以看出, 其实该框架和mahout中hadoop item-based 的计算item相似度的流程极为相似, 具体算法可参见mahout源码:mahout推荐算法;但该算法具有很好的扩展性, 就是前边介绍的: 灵活更换左右节点, 即可实现多步级联的推荐。
核心代码示意
具体实现即根据上文四个步骤进行划分, 四个步骤的实现代码可参见下属配置文件:
通过conf文件,大家即可了解上述4个步骤的实现, 具体该配置可以参见conf/twohop_bipartite.job.conf
实现效果
经过多次优化, 包含基础数据的清洗, 使用该方法, 客户的覆盖率提升至75.6%, 相关性85%。 且针对一些大客户的需求, 可以放松相关性来进行扩词。
工具使用方法
级联二部图工具使用方法如下:
python ${TWOHOP_MINING_HOME}/script/twohop_mining.py
-hadoop hadoop_client_path
-inputA input_A_path
-inputB input_B_path
-output output_path
注: 该框架依赖于我们自行开发的hadoop任务框架, 所以可能无法完整运行, 但使用者可以将上述4个步骤的hadoop脚本单独抽取出来进行单独运行。
工具代码地址
代码可从我的云盘下载:级联二部图框架
参考文献:
mahout推荐算法:http://mahout.apache.org/users/recommender/recommender-documentation.html
youtube video推荐算法:Davidson J, Liebald B, Liu J, et al. The YouTube video recommendation system[C]//Proceedings of the fourth ACM conference on Recommender systems. ACM, 2010: 293-296.
百度关键词工具介绍参见:http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596
也可关注我的微博: weibo.com/dustinsea
或是直接访问: http://semocean.com

context-aware recommendation

智能手机的普及让大家随时随地都可接入互联网,而这样的随时随地的应用场景,也让传统推荐技术需要充分考虑,利用这些信息提升推荐的准确性,同时从另外一方面考虑, 这种符合LBS的推荐, 因为有了这些信息后,也能够更加准确。
传统的推荐系统基本上就是根据用户对物品的打分进行推荐, 或者描述为 USER * ITEM -> RATING。 其工作就是去填充一个matrix,matrix的横坐标为item,纵坐标为user,推荐的任务就是根据当前已经获得的该matrix中非空的元素, 去填充该矩阵中没有值得元素,并保证用于填充matrix的模型, 在非空元素上的误差最小。
什么是Context-Aware Recommendation
但在很多场景下, user的rating会受到context的影响, 这里的context在不同的领域会有不同的定义。例如电影推荐,对是否为工作日这样的因素影响会比较大;在LBS应用中,推荐内容是否会被采纳, 会受到地理位置的影响(特别现在移动是个大趋势,后续更多的访问流量都会转向移动),例如手机美团,如果一个人在饭点上美团,则他购买餐馆团购券的概率应该要比夜晚大,而购买离他距离近的餐馆团购券的概率也要比购买距离比较远的团购券大。 这里的地理位置, 时间,就可以看成是context内容。
而在搜索引擎中,例如百度,要增强搜索的个性化(如果我们将搜索也看成推荐问题),那么网民的IP所在地,或者网民之前输入的几个query,都可以看成是context内容。
那context内容如何与传统Recommender技术融合? 这就是推荐技术中的contex-aware recommedation: 结合上下文的推荐。 例如,大家经常会进行团购,而团购中的项目,要数团购饭点的套餐最为划算了,这其中就会直接涉及到上文提到的时间,地点两个上下文因素。举个例子,如果我周末快到吃饭时间进行套餐的团购, 海底捞离我比较远但小肥羊离我比较近,那我还是有可能会考虑离得比较近的小肥羊, 或者离我比较近的海底捞的店。
在我看来,类似于美团, 大众点评这样的生活服务,是最需要Context-Aware Recommendation技术的了(特别是近些年来智能手机的普及,大家很多时间都是用智能手机上网),需要结合用户诸如位置,时间及之前积累的用户信息(user profile)进行推荐。
如何实现context-aware recommendation
一般来说,可以使用以下3类方法,在推荐技术中引入上下文信息:
  1. Contextual Pre-Filtering
  2. Contextual Post-Filtering
  3. Model-based
Contextual Pre-Filtering
该技术是在数据处理阶段,就使用contextual信息对数据进行处理过滤,之后就可以使用传统的推荐技术进行推荐。假设我们将信息的处理看成是一个漏斗: 在获得候选信息后,逐步根据当前能够获得的信息过滤掉不相关的内容,保留下最相关的内容,则contextual pre-filtering方法就相当于将最严格的信息放在漏斗的最开始,直接过滤掉与用户context不相关的内容。
在实现contextual pre-filtering技术时,需要考虑contextual的表示方式,很多时候可以将这些contextual使用层次信息进行表示,以下是几个例子:
Company: Girlfriend →Friends →NotAlone →AnyCompany;
Place: Theater → AnyPlace;
Time: Saturday →Weekend→ AnyTime.
上边的例子,从左到右越来越泛化。
例如百度关键词搜索推荐系统,推荐地域相关关键词时,如果用户提供了地域信息,例如‘北京’后,在后续的推荐中,就不会考虑‘北京’以外的地域,而北京下属的几个区,都可以作为推荐的候选,这就需要维护一个全国地域term的层次树。 而时间, 关系(上文中的Company)等维度也需要有类似的层次树进行维护。
Contextual Pre Filtering方法优点: 在一开始对contextual信息进行处理后,就可以使用传统方法进行推荐,例如将特定contextual相关的数据过滤出来后,就可以使用传统的按内容推荐,协同过滤等方法进行推荐。 如果是实时的搜索引擎,使用类似于Contextual Pre Filtering的方法, 能够有效地减少后续数据的处理量(相当于建立了一个数据过滤漏斗, 在一开始的阶段即将后续不会用到的数据过滤,减少后续策略的计算量);但推荐系统中如果将没中过contextual信息的数据过滤出来单独训练的话,速度并不会有所提升。
Contextual Post-Filtering
该方式对于数据的处理与传统的推荐方式一致, 区别在于当结果已经推荐出来时, 使用contextual信息对结果进行重新过滤或是重排序。
例如, 对于地域这一维contextual信息,百度关键词搜索推荐(Baidu Keyword Recommender,后续简称KR)中就是用Contextual Post-Filtering方法,例如KR首先使用传统的方法进行推荐,之后在结果返回前,会根据地域对关键词进行排序过滤;又例如,美团的app,在进行餐饮团购推荐是,一开始可以使用传统的推荐算法进行推荐(当然此时就应该根据上下文进行粗过滤,例如对于在北京找餐饮服务的网名, 给他推荐一个上海的海底捞可不是一个好的选择), 当传统推荐算法推荐出结果后, 就可以使用上下文来进行过滤排序了。 例如餐饮服务推荐中国,在其他因素固定时,可以优先推荐离用户地理位置近的item。 最终的结果也不是完全按照时间排序, 时间只是众多考虑因素中的一个因子,例如可以使用另一个CTR模型来预估用户的点击概率, 而网名地理位置离餐馆的远近可以作为一维重要特征(其他特征可
以包含推荐物品与网民兴趣的匹配程度, 该item是否与该网民历史购买能力匹配等)
Contextual Post-Filtering的优点: 该方法的优点和Contextual Pre-Filtering一样,可以使用传统的推荐技术。 但该方法与Contextual Pre-Filtering相比,有一个优点: 最终的过滤排序,都是在推荐算法完成后进行的, 当有新的数据,或是算法接入时,最终的排序过滤标准是可以不做调整,只要在最终排序过滤逻辑前引入新算法的推荐结果即可,另一个优点是,最终出的结果的数量,可以视最终可能被保留下来的结果的数量进行调整, 例如按照严格的contextural信息来过滤,可能最终剩下的结果只有两条,此时如果觉得结果太少,则可以适当放松过滤阈值,或者将接近阈值的结果打上特定标签推荐出来(例如,百度关键词搜索推荐中,如果推荐的结果太少,系统会将一些阈值相对偏低的结果也展现出来,只是结果后边会打上‘结果太少?网民也会这样搜索’);但任何事物都有两面性,Contextual Post-Filtering方法的缺点一开始推荐出来的结果,会在后续直接因为Context不match而直接被过滤掉,这样就白白浪费了在排序过滤前的计算。
在实际应用中,需要根据具体应用选择使用Contextual Pre-Filtering或是Contextual Post-Filtering方法,而更为常见的是,两种实现思路经常会同时在同一系统中出现,仍然以KR中地域属性为例,在进行关键词候选结果选择时(一般称为触发过程),就会使用地域信息对结果进行粗选;在得到候选结果后,会使用地域信息(包括层级地域信息)对关键词进行更精细化的排序过滤。
Contextual-Model
可以理解为传统的Model-based推荐方法, 区别在于在进行模型训练时, 就将Contextual作为特征加入模型进行训练, 该方法的优点是直接可以使用一个模型完成推荐, 缺点在于如果上下文信息维度较多, 会导致训练数据较为稀疏, 同时当结果较差时不容易进行优化,因为众多因素进行了融合,很难指出问题出在什么地方。而Contextual Pre-Filtering和Post-Filtering方法,可以理解为对问题进行了拆解。这样的策略架构,问题定位会相对容易一些。
后记:  前几天看到一个新闻,称美团2013年已经实现盈利。当时看到这个信息的时候还挺震惊的。2011年的时候百团大战时,团购网站都在各种烧钱推广。百度为了让团购网站能够更高效地在凤巢上进行推广(也可以理解为更高效地挣团购网站的钱),设计了无关键词拍卖系统: 团购网站只要提供团购页面(或是团购页面的结构化属性描述),即可在百度上进行推广。但悲剧的是该系统才刚要开发完毕,团购网站的前就已经烧得差不多了, 之后就出现一大批团购网站的倒闭。。。。现在美团居然活得好好的。
同时结合自己做推荐系统的几年,觉得美团和大众点评这样的网站,是最适合加大推荐系统研发投入的: 每个美团/大众点评用户都有自己的ID,也都有自己够买的商品(explicit rating)和自己浏览的网页(implicit rating),同时手机客户端的的位置,时间信息可以作为推荐的context信息增强推荐的准确性。所以如果后续仍想在推荐系统方面做一些工作的话, 美团和大众点评都会是不错的选择。
附上一个index.baidu.com上几个关键词的搜索量变化, 美团的曲线是相当的漂亮!
百度关键词工具介绍参见:http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596
也可关注我的微博: weibo.com/dustinsea
或是直接访问: http://semocean.com

集成树类模型及其在百度搜索推荐系统中的应用

决策树是经典高效的机器学习分类算法, 非常适用于线性模型效果不能满足需求, 规则描述分布比较合适的场景。而决策树与传统bagging, boosting思想结合在一起, 就形成集成树模型方法, 包括Random Forest,GBDT等方法。 在百度搜索关键词搜索推荐系统策略中,实验证明集成树模型具有非常高的预估分类准确性。

决策树模型

举一个简单例子(引自公司pengzhiming同学的PPT): 老妈让自己相过多次亲的女儿再次去相亲, 女儿简单问了下对方的条件, 以判断是否去; 根据男方条件(特征)对去与不去进行分类的过程, 就是一个CART决策树。

例如:

母女对话如下:

 

如果将女儿的历史相亲经历看成是训练样本(男方条件为特征,女儿到对方后觉得是否靠谱作为label),将女儿积累到现在的相亲经验则是一个CART模型: 根据老妈的描述,就可以判断出是否有必要去见男方。

当然, 决策树模型也可以再细分, 包括经典的ID3,C4.5, CART。 不同的决策树具有不同的树结构,以及不同的节点拆分算法及拆分标准。

树模型的优缺点

总体来说,树类算法都是使用贪心算法, 选择当前最合适属性进行拆分建立整棵决策树,该类模型比较适用于能够用复杂规则描述的应用场景

以下为树模型的优点:

  • 实现较为简单, 且容易实现并行化
  • 训练速度较快, 且一般效果也比较好
  • 能够处理离散连续值特征(和LR类似的模型相比), 不用对特征做归一化即能取得较好效果
  • 能够处理缺失值
  • 能够处理高维特征
  • 训练完毕后, 能够给出哪些特征比较重要;而且很多情况下,即使最终使用其他模型 也可以使用树模型选择特征

当然, 所有的模型都有其弊端:

  • 树模型容易过拟合, 所以需要进行剪枝(以及使用后续将描述的集成学习方法解决)
  • 不能表示复杂结构和运算: 树模型原则上天然表示‘与’操作, 所以不能表示类似于‘异或’的操作

因为树模型的以上优点, 树模型在很多场景均会被选用

树模型训练框架

以下为使用数据集D,属性(特征)集合attribute_list产生决策树的算法框架。该算法未包含任何剪枝。

以上伪代码中(2)~(5)行用来处理数据中都是相同label及无属性拆分的情况,剩余代码使用贪心算法选择最合适的属性后,进行拆分,并递归建立子节点。

在上述伪代码中涉及到attribute_selection_method逻辑, 也就是决策树节点拆分标准的问题。

树模型节点分裂标准

如上所述,决策树使用贪心算法进行拆分, 选择当前认为最优的拆分特征进行树节点的分裂。 这就涉及到选择何种属性作为拆分的标准。一般说来, 经常使用的树节点拆分标准主要有以下几类:

  • information gain

一般情况下, 在决策树中, 使用信息增益(information gain)作为节点分裂的选择标准。

要定义信息增益, 我们需要定义‘信息’,我们将信息定义为: 对于数据集合D,我们需要对D中的各种类别进行编码的字节编码数,即:

 

 

信息量, 也被称为熵(entropy),用于描述不稳定性或多样性。 对样本集合D中, 假设对于某一维度的特征, 该特征A有v种取值, 而每种取值对应的数据样本数为Dj, 则在知道了某属性A的各种取值,并将符合各v值得样本进行分类后, 需要将样本集合D完全分开所需要的信息量为:

其中Dj为符合每个A的取值(假设A为离散可数种取值)的子样本集合。infor(Dj)为完全划分子样本集合所需要的信息量。 此时可定义信息增益:

在ID3算法中, 使用信息增益进行分裂特征的选择, 算法会使用贪心算法选择信息增益最大的特征进行树节点的分裂。 但信息增益有一个缺点: 会选择有众多值的特征进行节点分裂, 极端情况, 对于ID类特征(利用用户ID, 或是item ID), ID的个数与待分类的样本数一样, 这样的分裂是没有意义的, 此时, 使用gain ratio作为节点拆分标准, 能避免该问题。

  • gain ratio

为了解决信息增益偏向于选择属性值较多的特征问题, 在c4.5中引入了gain ratio。 首先定义:

注意splitinfo_A 与info_A的不同: splitinfo的第二项受到的是符合特征A下每种取值的样本数量影响; info_A则受到特征A下每种取值的样本包含的信息的影响。注意参考entropy的定义, 当分布越是不均匀时, 描述这种状态所需要的信息量约小, 分布越是散时, 需要的信息量越大(info值越大), 所以当拆分特征的值越多时, splitinfo会越大。

此时我们定义gainratio, 分母为splitinfo 起到抑制拆分多值特征的倾向。

  • gini index

在CART中, 使用gini index作为节点拆分的标准, gini系数的定义如下:

其中pi为样本集合D中各类的占比(总共有m类, pi=Di/D, 其中Di为D中属于类别i的的样本数量)

定义:

即使用属性A来对样本进行节点拆分后时的gini index, 此时可使用gini_A来对A进行拆分判定, 选择gini系数值下降最快的属性进行拆分。

一般说来information gain,gain ratio, gini index就是最常使用的三种拆分指标。结合前述树模型构建方法, 再加上构建树的过程中/后的限定条件及剪枝, 即可构建出实际中高效的决策树。

 

集成学习方法

集成学习方法是将bagging,boosting思路与树模型结合的高效学习方法。

bagging的思路比较简单, 就是汇集多个模型进行投票, 每个模型的票的权重一样, 获得票数最多的预估类胜出, 该类获得的票数与总票数的比值可以作为置信度。 如果是回归问题, 则多模型预估值得平均值作为bagging结果。

boosting方法在bagging的思想上前进了一步: boosting在训练时会更在乎分类错误的样本, 给予分类错误的样本更高的权重训练模型, 并将这些权重不一的模型根据权重进行bagging。boosting更像是是医疗专家诊断病情一样: 诊断容易出错的病情正确率更高的专家的话语权更高。 具体adaboost的介绍可参见《adaboost

bagging方法, 特别是adaboost方法一般都会使用非常简单的弱分类器进行bagging和boosting, 随着计算机处理能力的增强, 可以使用更加复杂的模型进行bagging&boosting, 而过将弱分类器使用更加复杂的树模型, 就形成‘集成树模型’。比较常用的‘集成树模型’包括Random Forest和GBDT。

虽然单个树模型学习能力有限(拟合复杂的数据分布能力有限), 但多个树模型放到一起, 就能够高精度拟合出复杂的分布(如上图所示), 这就是集成学习的强大之处。

  • Random Forest

Random Forest(RF)是典型的bagging树模型的方法。 其思路就是使用随机的部分样本/特征构建树模型, 之后使用bagging思想进行分类。

RF不仅对特征集合进行采样, 同样也可以对样本进行采样, 例如在进行单个cart训练时, 对每个模型,随机使用这种方式一方面充分利用了所有样本, 特征的贡献, 另一方面, 又能避免部分噪音带来的过拟合。设置合适的样本随机采样率(例如0.6表示每个模型选择60%的样本进行训练)以及何时的特征随机采样率(例如0.6表示每个模型选择特征集合60%的特征进行训练)进行RF训练。

在进行分类时, 根据样本和特征抽样训练出来的模型使用bagging方法进行投票。

相对于boosting会依赖于前一模型分类正确or错误调整样本权值的思路, RF更容易实现并行化, 因为RF中各子树的训练过程是完全独立的不会相互影响

  • GBDT

Grandent Boosting(GB)是将梯度下降思路融入boosting方法中, 不同于传统boosting每一步对分错样本进行加权(或对分对样本进行加权),GB定义整个模型的损失函数。

算法的每一步沿着损失函数下降最快的方向建立新的模型,这样使得算法在每一步均沿着下降最快的方向收敛。 直到满足要求, 建立满足要求的若干组合加权子模型。

Gradient Boosting将问题进行建模,定义loss function为

则对于训练样本集合{y, x}, 我们的任务是寻找最小化loss的函数F*(x):

而gradient boosting的思路是将映射模型函数表示为以下形式:

其中h(x;am)为简单函数/模型, am 为h的参数, 此时, belta, a, 就为我们要预估的最小化loss下的参数:

同时Fm与F_m-1的关系为

 

之后可以求belta和a序列参数, 求解过程如下:

在第i个样本点, 第m个模型里边的伪残差求解方法为:

要构建模型h(x,am), 最快的方法, 就是让所有的样本点处, 损失函数都沿着最快的方向下降。

也就是:

利用最小二乘法求解am后, 即可求解belta_m

依次求解所有am, belta_m后, 即得到最终模型F*(x)

树模型在百度关键词搜索推荐中的应用及实验结果

当然, 很多时候我们不会直接去修改模型, 在应用中, 更多地是使用模型作为工具解决具体问题。 例如在百度关键词搜索推荐中, 我们更多是构建相关性判断的特征样本, 之后对模型参数进行搜索: 例如样本采样率, 特征采样率等参数。 具体效果参见实验部分。百度关键词搜索推荐介绍及交互流程参见《百度关键词搜索推荐系统交互流程

一下为具体应用标注负样本示例,例如‘水仙花’, 从搜索引擎商业价值角度考虑, 是具体描述水仙花这个商品, 而不一样是信息型舞蹈名字query’紫蝶广场舞水仙花开’:

具体GBDT在百度关键词搜索推荐中, 相关性判断的应用方法(包括特征选取和实验结果), 参见《分类模型在关键词搜索推荐中的应用》, 使用树模型, 在没有任何样本,特征调整的情况下, 准确性直接提升了5个点 ,效果惊人。

同时, 正如前述: 树模型还有一个显著优点, 就是在模型建立时, 能够清晰分析出哪些特征对分类贡献大, 哪些对分类影响小(常用的指标包括特征的贡献度, 特征在分裂时的使用频率), 一般情况下特征贡献度和特征使用频率均是越大越好。 例如百度关键词搜索中, 对关键词相关性模型(使用分类模型判断两个关键词是否相关)使用17维特征。 使用Random Forest保留贡献最高的5维特征时, 在交叉验证情况下, 准确性基本保持不变, 召回也就下降1个百分点。

而在排序任务重, 使用衍生GBrank对百度关键词搜索推荐结果进行排序, 一般情况下,效果随着树的深度增长而提升, 但树深度达到8后, 就不再提升。

随着叶子节点书的增长, 效果仍然在提升, 所以在应用中,如果效率允许, 可以让最大叶子节点数多一些。

在实际应用中, 理论上可以对众多参数进行全参数搜索, 找到最优参数。 实际应用中会快速找到比较好的参数后, 策略即上线进行实验。

参考文献:

  1. Friedman J H. Stochastic gradient boosting[J]. Computational Statistics & Data Analysis, 2002, 38(4): 367-378.
  2. Quinlan J R. Induction of decision trees[J]. Machine learning, 1986, 1(1): 81-106.
  3. Breiman L, Friedman J, Stone C J, et al. Classification and regression trees[M]. CRC press, 1984.
  4. 分类模型在关键词搜索推荐中的应用

百度关键词工具介绍参见:http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596

也可关注我的微博: weibo.com/dustinsea

或是直接访问: http://semocean.com

 

推荐系统经典论文文献及业界应用

列了一些之前设计开发百度关键词搜索推荐引擎时, 参考过的论文, 书籍, 以及调研过的推荐系统相关的工具;同时给出参加过及未参加过的业界推荐引擎应用交流资料(有我网盘的链接), 材料组织方式参考了厂里部分同学的整理。
因为推荐引擎不能算是一个独立学科,它与机器学习,数据挖掘有天然不可分的关系,所以同时列了一些这方面有用的工具及书籍,希望能对大家有所帮助。
Survey方面的文章及资料
  1. Adomavicius G, Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions[J]. Knowledge and Data Engineering, IEEE Transactions on, 2005, 17(6): 734-749. 2005年的state-of-the-art的推荐综述,按照content-based, CF, Hybrid的分类方法进行组织,并介绍了推荐引擎设计时需要关注的特性指标,内容非常全。
  2. Marlin B. Collaborative filtering: A machine learning perspective[D]. University of Toronto, 2004. 从传统机器学习的分类角度来介绍推荐算法,有一定机器学习背景的人来看该文章的话, 会觉得写得通俗易懂
  3. Koren Y, Bell R. Advances in collaborative filtering[M]//Recommender Systems Handbook. Springer US, 2011: 145-186.  RSs Handbook中专门讲述协同过滤的一章,其中对近年协同过滤的一些重要突破进行了介绍,包括因式分解,时间相关推荐,基于近邻的推荐以及多种方法的融合,内部不多,但其中引用的论文值得细看
  4. Su X, Khoshgoftaar T M. A survey of collaborative filtering techniques[J]. Advances in artificial intelligence, 2009, 2009: 4. 协同过滤的篇survey, 按照memory-base, model-based, hybrid分类方法介绍各种协同过滤方法及评价标准,并在其中给出基于netflix数据进行评估的效果对比
  5. Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30-37.  主要集中在因式分解实现协同过滤方法,如果看完Advances in collaborative filtering[M]//Recommender Systems Handbook的话,这篇文章就没有必要再看了
  6. Pazzani M J, Billsus D. Content-based recommendation systems[M]//The adaptive web. Springer Berlin Heidelberg, 2007: 325-341.从宏观上介绍content-based的策略架构
Content-based方法
content-based方法非常依赖于特定领域item的特征提取及处理,例如音乐推荐或是关键词推荐中很多细节内容信息处理过程都是不一样的,故这里仅列了content-based综述类的几篇文章。
  1. Pazzani M J, Billsus D. Content-based recommendation systems[M]//The adaptive web. Springer Berlin Heidelberg, 2007: 325-341.从宏观上介绍content-based的策略架构
  2. Lops P, de Gemmis M, Semeraro G. Content-based recommender systems: State of the art and trends[M]//Recommender Systems Handbook. Springer US, 2011: 73-105. RS Handbook中专门介绍content-based 算法的章节
  3. Jannach D, Zanker M, Felfernig A, et al. Content-based recommendation   [M] Charpter 3 Recommender systems: an introduction[M]. Cambridge University Press, 2010.
Collaborative Filtering方法
Neighbourhood Based Methods
  1. Sarwar B, Karypis G, Konstan J, et al. Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th international conference on World Wide Web. ACM, 2001: 285-295. KNN进行item-based推荐的经典文章,其中也介绍了多种相似度度量标准
  2. Linden G, Smith B, York J. Amazon. com recommendations: Item-to-item collaborative filtering[J]. Internet Computing, IEEE, 2003, 7(1): 76-80. 经典的亚马逊item-based算法的文章
  3. Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing[C]//VLDB. 1999, 99: 518-529.  LSH
  4. Bell R M, Koren Y. Scalable collaborative filtering with jointly derived neighborhood interpolation weights[C]//Data Mining, 2007. ICDM 2007. Seventh IEEE International Conference on. IEEE, 2007: 43-52.
  5. Indyk P, Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality[C]//Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 1998: 604-613. LSH
  6. Buhler J. Efficient large-scale sequence comparison by locality-sensitive hashing[J]. Bioinformatics, 2001, 17(5): 419-428. LSH应用
Model Based Methods
  1.  Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30-37.主要集中在因式分解实现协同过滤方法,如果看完Advances in collaborative filtering[M]//Recommender Systems Handbook的话,这篇文章就没有必要再看了
  2. Singh A P, Gordon G J. A unified view of matrix factorization models[M]//Machine Learning and Knowledge Discovery in Databases. Springer Berlin Heidelberg, 2008: 358-373.
Hybrid Methods
  1. Koren Y. Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2008: 426-434. 因式分解与Neighbour-based方法融合
  2. Burke R. Hybrid recommender systems: Survey and experiments[J]. User modeling and user-adapted interaction, 2002, 12(4): 331-370.
  3. Burke R. Hybrid recommender systems: Survey and experiments[J]. User modeling and user-adapted interaction, 2002, 12(4): 331-370. 介绍了多种推荐算法进行融合的框架
推荐系统工业界应用
  1. Netflix:Netflix视频推荐的背后:算法知道你想看什么
  2. Netflix:Netflix Recommendations Beyond the 5 Stars
  3. Hulu:Recommender System Algorithm and Architecture-项亮
  4. Youtube:Davidson J, Liebald B, Liu J, et al. The YouTube video recommendation system[C]//Proceedings of the fourth ACM conference on Recommender systems. ACM, 2010: 293-296.  Youtube推荐系统中的主要算法。 百度关键词搜索推荐系统对其进行了优化, 实现了任意类型的级联二部图推荐。 具体内容可参见博文: google youtube 电影推荐算法, 以及百度关键词搜索推荐级联二部图实现
  5. 豆瓣: 个性化推荐系统的几个问题_豆瓣网王守崑
  6. 豆瓣:阿稳_寻路推荐_豆瓣
  7. 豆瓣:豆瓣在推荐领域的实践与思考
  8. 百分点:量化美-时尚服饰搭配引擎
  9. weibo及考拉FM:停不下来的推荐实践_陈开江
  10. 阿里:天猫双11推荐技术应用
  11. 阿里:淘宝推荐系统
  12. 当当:当当网搜索和推荐_庄洪波
  13. 土豆:个性化视频推荐系统土豆_明洪涛
  14. 360:360推荐系统实践-杨浩
  15. 盛大:推荐系统实战与效果提升之道-陈运文
  16. 盛大:智能推荐系统的开发与应用-陈运文
推荐系统书籍
  1. Segaran T. Programming collective intelligence: building smart web 2.0 applications[M]. O’Reilly Media, 2007.寓教于乐的一本入门教材,附有可以直接动手实践的toy级别代码
  2. Shapira B. Recommender systems handbook[M]. Springer, 2011.  推荐系统可做枕头,也应该放在枕边的书籍,看了半本多。如果将该书及其中的参考文献都看完并理解,那恭喜你,你已经对这个领域有深入理解了
  3. Jannach D, Zanker M, Felfernig A, et al. Recommender systems: an introduction[M]. Cambridge University Press, 2010.  可以认为是2010年前推荐系统论文的综述集合
  4. Celma O. Music recommendation and discovery[M]. Springer, 2010. 主要内容集中在音乐推荐,领域非常专注于音乐推荐,包括选取的特征,评测时如何考虑音乐因素
  5. Word sense disambiguation: Algorithms and applications[M]. Springer Science+ Business Media, 2006. 如果涉及到关键词推荐,或是文本推荐, 则可以查阅该书
P.S. 想对某个领域或是工具有深入了解,可以找一本该行业的XX HandBook满怀勇气与无畏细心看完,然后就会对这个领域有一定(较深)了解,当然如果手头有相关项目同步进行,治疗效果更好^_^
推荐系统工具
  1. Mahout:基于hadoop的机器学习,数据挖掘,推荐系统开源工具。我厂的超低版本haodop集群居然不支持Mahout,想跑个Mahout还要进行移植,郁闷。。。该死!!
  2. scikit-learn:基于python的机器学习,数据挖掘库, 方便好用,适合数据量较小的调研任务,不过,一切不支持大数据的机器学习算法,(一定程度上)都是耍流氓。。。。
  3. weka:经典的数据挖掘工具, java版本
  4. R:R语言
  5. Cluto:聚类工具,集成了较多聚类算法及相似度度量方法
  6. RapidMiner:没用过,但据说使用量非常大
国内推荐系统站点
  1. http://www.resyschina.com/
因为我一直认为推荐系统不是一个独立的学科,它很多技术都是直接来自于机器学习,数据挖掘和信息检索(特别是文本相关的搜索推荐),所以以下也整理了一些之前工作及工作之余看过,了解过,或者准备看的这方面的资料
数据挖掘资料
  1. Han J, Kamber M, Pei J. Data mining: concepts and techniques[M]. Morgan kaufmann, 2006. 数据挖掘方面的handbook,教科书类型,虽然厚,却通俗易懂(再次提醒,要了解某一领域,找本该领域的啥啥handbook耐心认真读完,那你基本对该领域有一定认识了)
  2. Chakrabarti S. Mining the Web: Discovering knowledge from hypertext data[M]. Morgan Kaufmann, 2003.介绍了一个搜索引擎中的大部分技术,包括spider,索引建立,内部的机器学习算法,信息检索,而且非常具有实用性,我在百度商务搜索部开发的spider,就是按照其中的架构设计开发的
  3. Liu B. Web data mining: exploring hyperlinks, contents, and usage data[M]. Springer, 2007. 如果说 Mining the Web: Discovering knowledge from hypertext data更偏web mining更偏整体,工程的话,这本书就更偏策略,两本都读过的话,你对搜索引擎中的数据挖掘算法的了解,就比较全面了
  4. Wu X, Kumar V, Quinlan J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1): 1-37. 专门将2006年评选出来的10大数据挖掘算法拎了出来讲讲
  5. Rajaraman A, Ullman J D. Mining of massive datasets[M]. Cambridge University Press, 2012.介绍如何使用hadoop进行数据挖掘,如果有hadoop环境则非常实用
  6. Feldman R, Sanger J. The text mining handbook: advanced approaches in analyzing unstructured data[M]. Cambridge University Press, 2007.文本挖掘的handbook
机器学习资料
  1. Tom M Mitchell,Machine Learning, McGraw-Hill Science/Engineering/Mat, 1997,非常早起的机器学习书籍,非常适合入门, 浅显易懂, 但对于工业界应用, 只能说是Toy级别的算法。
  2. Bishop C M, Nasrabadi N M. Pattern recognition and machine learning[M]. New York: springer, 2006. 进阶型的书籍,对每种算法都有较为具体的理论介绍
  3. 课程: 机器学习(Stanford->Andrew Ng)http://v.163.com/special/opencourse/machinelearning.html,大名鼎鼎的Andrew Ng的机器学习公开课,网易上字幕版本;配合课程stanford cs229对应的handout及习题一起学习效果更好
信息检索
  1. Agirre, Eneko, and Philip Glenny Edmonds, eds. Word sense disambiguation: Algorithms and applications. Vol. 33. Springer Science+ Business Media, 2006.
  2. Manning C D, Raghavan P, Schütze H. Introduction to information retrieval[M]. Cambridge: Cambridge University Press, 2008.
  3. MOFFAT A A, Bell T C. Managing gigabytes: compressing and indexing documents and images[M]. Morgan Kaufmann, 1999.一本很老的介绍搜索引擎的书了,不过09年的时候看还是被震撼到了,书中各种变着戏法使用几十M内存处理上G数据,感觉非常牛叉。
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com

关键词推荐工具中的用户引导机制之四:种子query推荐

上一篇《关键词推荐工具中的用户引导机制之三:相关搜索query技术》中, 我们提到可使用用户query-点击日志,session数据,及网页内容,挖掘与query意图相关(同时具有变现价值)的相query推荐给客户引导用户优化搜索。 如用户还未输入,此时搜索引擎默认直接展示搜索框。但在关键词推荐系统中,更好的选择是push与用户相关高质量query,帮助用户高效发现兴趣点,本文将介绍在关键词推荐系统中,实现种子词推荐产品及策略
什么是种子query推荐功能
什么是种子词query推荐,先向大家展示两个直观的例子: 百度锁屏,以及百度关键词推荐种子词推荐功能。
 
图: 百度锁屏种子词query推荐
图:红框部分为关键词推荐工具中种子query功能
种子query推荐功能作用
种子query,就是在用户在搜索框中,还没有任何搜索时,通过线下挖掘计算,主动push推荐用户潜在感兴趣的query的功能。 例如百度锁屏功能的种子query,当用户锁屏准备解锁时,app推荐用户可能感兴趣的搜索引擎候选query(种子query)后,用户可以直接点击进行搜索,以提升搜索引擎访问量; 在百度关键词推荐系统中,用户还没有输入适合自己的query时,可以根据用户的历史搜索,以及百度推广业务等信息,推荐高质量的种子query给客户。
大家可能会有疑惑,既然关键词推荐就是一个推荐系统,那为什么还要有种子词推荐? 而Baidu,或是Google首页上,也没有种子词推荐?  从我的角度来看,Baidu,Google首页之所以没有种子词推荐功能,一方面是这两个搜索引擎简单的首页的访问量实在太大,首页上任何的信息,可点击的内容均会对网民带来影响巨大的引导作用, 举个例子: 之前就曾经发生过类似的时间,就是在百度首页上放了一个大型网站(具体网站名不便透露)的文字链,结果在很短时间内,该网站就被来自百度该文字链的流量压垮;反过来说, 在搜索引擎首页上增加种子词推荐,也会分散用户的注意力。 另一方面网民的搜索内容太泛,要做到准确推荐的确有难度。
在关键词推荐系统中,特定用户搜索的(商业)query对应的意图,产品范围均相对集中,或者说使用关键词推荐系统的用户,兴趣点相对集中,难点是用户很难想出来搜索引擎上可能接受的描述该兴趣点的千奇百怪的表述。 所以就需要使用种子词推荐功能进行搜索引导。
如何设计种子词推荐策略
可以很简单, 也可以很难。。。
为什么说很简单, 例如,在搜索引擎上, 最简单的方式, 就是直接使用一定时间内网民的搜索, 过滤掉黄赌毒反结果,作为推荐结果。 但这样做有一个问题, 就是有些搜索query,基本上可以说任何时候,搜索量都比较高, 例如搜索query “淘宝”。 为了避免该类问题, 可以使用在某一段时间内搜索量变化比较大的query作为种子query。
为什么说可以很难?  因为这本来就是一个关键词推荐问题: 根据用户历史行为,数据,推荐用户可能感兴趣的query。 当然, 种子词推荐有它的特殊性, 因为推荐的优化目标是不一样的,它是一个多目标的优化问题:
  1. 符合用户的搜索意图(搜索引擎中为搜索意图,百度推广中为推广意图)
  2. 用户使用该种子词搜索后,为搜索引擎/商业系统带来的效用
假设搜索意图质量为Q(Quality),带来的效用为U(Utility),则这个多目标优化问题可以描述为:
S = Q^(t) * U^(1-t)
其中S为最终的Score,使用t控制Q与U在最终结果中的权重。
我们可以使用经典的colleborative filtering, 或是content-based recommendation方法, 获取到推荐词源, 之后使用以上双目标优化方式计算S来进行结果的filtering和ranking,给出Score权值最高的top n 结果。
例如, 在关键词推荐系统中,我们希望用户使用种子query进行搜索后, 一方面结果要相关, 另一方面,返回的结果数要超过阈值(或者尽可能多), 此时, 搜索结果相关可以被定义为Q(可以离线挖掘时使用PLSA等技术进行判断相关性), 同时使用返回结果数作为U, 最终对挖掘的种子词进行filtering和ranking。
更多内容请参考:
《recommender systems handbook》
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com