博客

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

下文就百度商业变现的指标体系进行概要描述,并针对一个类似于百度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

《小米是如何炼成的》-雷军百度讲互联网思维做手机

雷军前些天到百度给百度的员工进行了一次演讲, 演讲的题目是《我和小米这三年》, 主要介绍了小米的铁人三项:软件,硬件和互联网服务; 以及如何用互联网思维做手机。 尽管是非开放性报名, 仅有高T和M序列能报名。虽然讲座在百度大厦最大的五福降中天举行,但现场还是超级爆满,而且很多没报上名的同学很早就在现场门外守候, 期望最后能有机会进场。
黑百度的开场
雷军上台演讲后, 先没干别的, 立马黑了百度一把, 雷军说:‘大家知道, 百度还是一家挺好的公司, 在全国范围内就不说了。。。。’, 此时按照逻辑, 我会以为雷军会说百度在国际上也有一定知名度, 结果雷军顿了顿后,接着说‘在中关村, 百度还是一家不错的公司。。。。’当时立马笑喷了, 觉得雷军带着一种幽默来踢馆。 在后来的演讲中, 一直伴随着类似的幽默, 所以整个演讲下来, 一方面觉得说活颇多, 另一方面也不觉得累, 因为雷军非常风趣。
讲座部分流水账
接下来的演讲, 雷军先介绍了小米的8位co-founder, 听起来背景都挺牛的, 也介绍了小米成立那天几个同事一起喝小米粥的故事, 还有google 全球副总裁的hugo早就谈好来小米, 但重点提到: hugo是来小米, 但一直不来北京: 啧啧, 污染那么严重, 也可以理解。。。
之后就介绍了小米13年的业绩, 当时雷军给了一个截图, 图中列出的是全球最具创新企业50强中的部分企业, 当中惊奇地发现小米居然名列第3, 好像比苹果还要高。 当时觉得老牛了, 后来百度了一下, 360也是最具创新的企业之一, 后来才知道这个奖有两个版本。两个版本的结结论还差了好多。
后来就是介绍小米的一些产品, 功能设计理念的介绍。 雷军主要围绕着设计贴心产品
互联网思维做手机
在整个讲座中, 有两个内容让我印象深刻, 一个是雷军详细介绍如何使用互联网思维做手机的思想;另一个就是就是小米如何考核员工的KPI。
雷军使用了一个图完整地描述了他的思想:
  • 专注地快速做到极致打造口碑
整个过程的中心, 就是如何打造良好的口碑。 可以将图分为两部分: 打造口碑所要做的事, 在上图的左边, 包括专注, 极致, 快等几个因素, 都是小米自己需要做到的: 只有将事非常快地做到极致, 才有可能在用户心中建立良好的口碑, 而要将事做得非常快地做到极致, 就需要专注。
在Q&A环节, 有同学还专门问了雷军:极致和快, 很多时候是相互矛盾的: 做得快, 很可能就很难做到极致, 反之亦然。 我当时也好奇, 雷军如何回答这个问题。  雷军给出的答案是: 需要专注。 他提到小米就只做手机, 虽然很多人提议他做很多东西, 但很多都被他咔嚓了。。。 后来想了一下, 其实很多互联网大佬在实际执行的过程中, 都体现出专注, 例如百度的boss Robin,就一直在提专注, 专注地做搜索(当然, 后来发现, 也不能太专注, 或者说是要有远见地专注,例如作为搜索护城河的输入法, 浏览器, 在早期的百度, 就没有收到太多重视。 要眼观六路, 耳听八方地专注)。在一万小时天才理论中, 也提到专注于某一项即能, 1W小时成为天才的观点。 而在软件工程中, ‘好, 快, 省, 任选其二’ 也作为不变的定律, 这个地方的‘省’, 在这里也可以作为专注理解: 可以做的事太多, 之后专注, 才能快起来, 才能做好(极致)
  • 不将用户做上帝, 将用户当朋友
在上图,口碑中心的右边, 雷军提到, 不要把顾客做上帝, 因为大家不信上帝, 要将顾客当朋友, 采纳顾客的意见, 这样顾客会帮忙推销, 同时使用互联网媒体将这种作用无限放大达到营销效果,这个过程中雷军一直说自己没有做太多营销; 需要虚心采纳用户的建议, 用户的建议采纳后, 一方面的确能够改进小米, 另一方面, 用户会非常高兴, 他们会积极地帮小米做宣传, 相当于小米发动了人民战争, 用户都在为小米积极宣传, 用户在帮小米营销。 他还举了一个例子, 说真由用户来北京, 在小米办公楼下苦等几个小时, 就是为了见雷军, 将自己制作的小米台历送给雷军。
雷军还提到, 在做功能的时候,不仅要做得好, 更要超过客户的预期。有时候, 一个东西做得好, 没有超出用户的预期, 用户也不会买账。他举了两个例子: 他去迪拜帆船酒店前, 大家都说这家酒店如何如何高大上, 但去了以后, 发现里边的装修,都是土豪金,导致他期望太高, 失望越大,所以感觉没有达到预期; 但在海里捞, 看到真诚的笑, 感觉非常好。 看来海底捞你还真是学不会。。。
通过自身品质的提升和发动人民战阵做宣传, 才能打造出现在小米的口碑。
小米的去KPI化管理
后来雷军还讲了其他很多内容, 但我都记不清了, 或者说, 内容以前都听过了, 没有超出预期。 不过Q&A环节比较有意思: 在Q&A开始前, 雷军说: 前4个提问的同学有奖品: 两个小米手机和两个小米移动电源, 所以大家提问异常火爆, 一开始我也积极举手, 可以坐在后排加上矮小的我, 虽然每次都举手, 但还是没有提问的机会。  我想问的问题和小米管理过程相关: 雷军讲座中提到小米提倡去KPI化的管理风格,具体衡量方式为:
  1. 做让用户尖叫的产品
  2. 让用户用户愿意分享给朋友
我一直还是觉得大家做事必须要有一个可以衡量的目标, 只是如何找到合适的目标是一个艺术问题。 所以当时我想问的问题就是: 以上两点, 在小米内部如何衡量。 不过幸好有个哥们问了这个问题, 雷军提到在小米内部, 有3个措施来保证以上目标的达成。
  1. 找到对的人, 自我驱动较强的人来做事; 将事做好做到极致;
  2. 充分,足够扁平化, 例如小米仅3层管理结构, 有否问题, 老板很容易知道。相当于去管理化(最大程度去行政化管理, 仅保留技术管理)。 我听360的同学说360也是极其扁平化, 看来异曲同工。相较下百度已经是个大公司了, 各种管理级别。。。
  3. 发动人民群众提问题, 收集反馈(雷军说道自己两周换一次手机, 自己亲自积极体验,回想百度最年轻的副总裁李明远上天天向上的时候, 也是腰间别了N多手机, 自己就天天作为PM琢磨里边的功能与体验; 同时也提到因为经常采纳用户体验, 有一些米粉甚至专程在小米办公楼下等候几小时给他送礼物)
一场风趣的讲座, 看来以后做啥事, 都可以想想如何用互联网思维来做: )

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

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

 

epoll机制在搜索引擎spider中的应用

本文将介绍epoll的概念,原理, 优点,及使用接口,同时结合作者在搜索引擎spider开发中epoll使用方式的代码向大家具体介绍epoll的使用方式。
P.S. 笔者08年曾有使用epoll编写未考虑压力控制的crawler,将国内著名票务网站(艺龙)压垮并在boss的带领下登门道歉的经历:) 足见epoll的强悍!
epoll是什么
按照man帮助中的说明,epoll是为了高性能处理处理文件句柄而改进的poll机制, 和其类似的功能是select调用。epoll提供相对简单的接口, 即能实现高效的数量巨大的文件句柄的操作和控制。 是select和poll的升级替代品。
select也可以管理调度数量众多的文件句柄,但一般select能够管理的文件句柄数为2048(受FD_SETSIZE定义大小的限制), 虽然可以通过修改linux内核代码调整,但因为其实现为轮询机制,所以在当文件句柄较多,而有事件的句柄较少的情况下select的性能会较低(当然,我个人觉得最大的问题,还是文件句柄数的限制), 当然,很多早期的搜索引擎spider,很多都是直接使用select,调度网络句柄,性能也还不错,比如larbin
而在操作系统实现中,epoll是通过callback回调函数来操作active的文件句柄,所以该调用不用像select或是poll一样需要线性扫描,所以epoll效率较高(当然,如果操作的文件句柄都是活跃的,那select/poll的性能类似),而且epoll能够管理的文件句柄数非常多,一般是系统能够管理的文件句柄的上限,况且epoll通过epoll_create,epoll_ctl,epoll_wait即能完成文件句柄的管理, 所以很多时候epoll系列的接口会成为管理大量文件句柄的机制的首选。
epoll的优点
其实上文已经提到了很多,综合起来,主要是以下两方面有点:
  1. 高效: 在大量文件句柄管理中,如果active的文件句柄较少,则效率较select/poll高
  2. 量大: 理论上能够管理操作系统最大文件句柄数的句柄
当然,在实际中,在一些benchmark中,如果绝大部分文件句柄/socket都active,则epoll的效率相较select/poll并没有什么优势,相反, 如果过多使用epoll_ctl,效率相比还有稍微的下降。但是一旦使用idle connections模拟WAN环境,epoll的效率就远在select/poll之上
另外,能够管理的文件句柄数也不可能达到最大句柄上限,在1GB内存的机器上大约是10万左右,具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。
epoll的使用
首先要介绍epoll相关的数据结构。
epoll用到的有函数都是在头文件sys/epoll.h中声明:
typedef union epoll_data { void *ptr; int fd; __uint32_t u32; __uint64_t u64; } epoll_data_t; struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */ };
结构体epoll_event 被用于注册所感兴趣的事件和回传所发生待处理的事件,其中epoll_data 联合体用来保存触发事件的某个文件描述符相关的数据,例如一个client连接到服务器,服务器通过调用accept函数可以得到于这个client对应的socket文件描述符,可以把这文件描述符赋给epoll_data的fd字段以便后面的读写操作在这个文件描述符上进行。epoll_event 结构体的events字段是表示感兴趣的事件和被触发的事件可能的取值为:
EPOLLIN :表示对应的文件描述符可以读; EPOLLOUT:表示对应的文件描述符可以写; EPOLLPRI:表示对应的文件描述符有紧急的数据可读; EPOLLERR:表示对应的文件描述符发生错误; EPOLLHUP:表示对应的文件描述符被挂断; EPOLLET:表示对应的文件描述符有事件发生;
函数接口如下:
函数声明:int epoll_create(int size)
该函数生成一个epoll专用的文件描述符,其中的参数是指定生成描述符的最大范围 2、epoll_ctl函数
函数声明:int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)
该函数用于控制某个文件描述符上的事件,可以注册事件,修改事件,删除事件。
参数: epfd:由 epoll_create 生成的epoll专用的文件描述符;
op:要进行的操作例如注册事件,可能的取值:
                EPOLL_CTL_ADD 注册、EPOLL_CTL_MOD 修改、EPOLL_CTL_DEL 删除
fd:关联的文件描述符;
event:指向epoll_event的指针;
如果调用成功返回0,不成功返回-1
函数声明:epoll_wait
epoll的工作模式
epoll有两种工作模式,ET模式与LT模式。
LT是缺省的工作方式,并且同时支持block和no-block socket;在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的,所以,这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表。 ET是高速工作方式,只支持no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了。但是请注意,如果一直不对这个fd作IO操作(从而导致它再次变成未就绪),内核不会发送更多的通知。 ET(Edge Triggered)与LT(Level Triggered)的主要区别可以从下面的例子看出:
例子:1. 标示管道读者的文件句柄注册到epoll中;2. 管道写者向管道中写入2KB的数据;3. 调用epoll_wait可以获得管道读者为已就绪的文件句柄;4. 管道读者读取1KB的数据5. 一次epoll_wait调用完成
如果是ET模式,管道中剩余的1KB被挂起,再次调用epoll_wait,得不到管道读者的文件句柄,除非有新的数据写入管道。如果是LT模式,只要管道中有数据可读,每次调用epoll_wait都会触发。 另一点区别就是设为ET模式的文件句柄必须是非阻塞的。
搜索引擎spider中的使用示例
功能描述
此处的spider,是一个具体而微的应用,或者更应该定义为crawler,即定向快速抓取指定网站,例如我们已经获取到1KW个URL,需要再1天内江1KW的URL对应的网站,使用单机抓取下来。
更具体地,笔者当时的应用场景,是快速地检查指定URL list对应的网站是否能连通, 所以具体操作的时候,仅抓取网页的头部信息, 并返回其中的return status即可, 因为一开始没有spider设计的经验, 所以该crawler一开始没有考虑同一网站的压力控制, 而epoll过去强悍,导致QA线下测试该crawler时,就将国内著名票务网站压垮(据票务网站的同事说, 他们的服务器CPU过热自动重启,而刚完成重启,就。。。又挂了: ),也算是工作后的一个奇遇了。  当然, 这样的CASE在如今,能够很容易被检查出来是一场攻击而被直接封IP。
架构
因为是一个简化的spider,所以架构图和下图类似(精确的架构图涉及泄密不再贴出来):
性能考虑
假设20个线程,每个线程最多管理50个socket, 假设抓取超时时间为10秒(一般会比这个时间长),假设不考虑压力控制,则该crawler每天能够抓取 20 * 50 * 86400 / 10 = 8640,000个网页,单机。如需要更强悍的抓取能力, 考虑使用多机。
代码示例
因为代码较多,此处仅贴出涉及到epoll工作原理的代码部分。
 图: epoll_create,创建epoll的fd,其中_max_sock_num指定最大管理的socket数量
图: 将socket加入epoll机制: 创建非阻塞fd,并将非阻塞fd加入epoll管理(初始的fd不响应读消息)
图: 使用epoll_ctl设置fd的状态,请参见上图设置读消息机制理解
图: epoll_wait调用方式: 如果active的socket数量不为0,则分出错,断开,读,写状态进行对应处理。
更多实现参见该文附件代码: contm_connector.cpp, 该代码在实际项目中应用,因用到了自行开发的日志库等外部lib,故不能直接编译,但逻辑经过测试,所以参考性较强。
具体代码参见: http://pan.baidu.com/share/link?shareid=2373459832&uk=1493671608
更多内容参见:
epoll 使用说明: http://www.xmailserver.org/linux-patches/nio-improve.html
也可关注我的微博:  weibo.com/dustinsea
或是直接访问: http://semocean.com

管理者如何做好团队规划

之前看过一篇文章,讲述的是孙正义如何设定目标及如何达成目标, 具体的原话忘了, 大概的思路是: 先设想自己10年后想达成的状态和目标,之后再分析要达到这个目标, 在第8年的时候需要哪些资源, 需要达成怎样的状态, 之后不断倒推, 直到当前;当然, 这么牛叉的目标设定方法, 不是每个人都能掌控的。。。

以前也曾经听一个Google资深产品经理的讲座,介绍Google的产品设计理念时,也提到Google一开始会将产品设想得比较宏大, 之后从某一个小点入手推进该产品,直到将该产品越做越大, 直到影响几乎全人类。。。

进行团队规划时,也是如此。下边就来介绍下在团队中, 一般我们是怎么做团队规划的吧。

简单来说,团队规划,是不断回答完善以下一系列问题的过程,这些问题需要在工作推进的过程中定期review和调整:

  1. 希望你的团队成为怎样的团队
  2. 现在离理想状态还有多远
  3. 分几个阶段每个阶段如何做才可以做到
  4. 需要哪些资源才能做到这样的团队

希望你的团队成为怎样的团队

这个问题,解决的是目标问题, 我们经常说‘指哪打哪’, 这个问题就是回答‘指哪? 以及是否指对’  的问题。 这个过程相当于为团队明确定位, 例如需要明确团队的职责, 理想的团队梯队和组织架构, 团队的意识和价值体系, 理想的团队氛围, 团队能够对更大范围产生的影响和输出价值。

明确团队的职责和定位: 这个相当于是限定了团队所要做的工作的范围以及价值, 例如之前我们对位团队负责百度搜索变现流量的挖掘,以便提升公司搜索变现效率。 这就是团队的职责,符合该职责的工作, 都需要考虑是否去做。 在这样的目标设定下,首先可以选择一些当前认为重要的, 且可以做到的事去做,量力而行,逐步推进。 之后可以设定设定一些未来看起来有希望的能够做到的重点工作作为中期目标进行推进。在设定中期目标的时候,一定要抓住重点,例如以前我的老大就跟我说过: 抓住最重要的3件事,避免大而全。

团队一般还会有其他的一些目标,但这些目标一定是围绕着团队的职责来设定的,例如组织架构是为了更高效地完成团队的职责,而且好的组织架构可以用一张清晰的图就能表述清楚;团队的价值体系也是使用简单明了的话就能进行介绍; 最好还能够形成几句比较好记,琅琅上口的团队口号, 这样能够让团队,员工更有凝聚力, 这个很重要。 例如经常说百度的使命是:‘让人们更便捷地获取信息,找到所求’, 我们团队会经常类比, 说我们的职责是:‘让广告主更高效准确地覆盖适合他的流量’, 简单地一句话就能概括团队的职责。

如何确定团队职责和定位是正确的:这个可以从多个角度来验证,例如和自己的上级, 下级, 平级的同事讨论。这个非常重要,团队的职责很多时候只有得到老大的认可这是必须的,如果老大都不认可这样的定位, 那后续的工作几乎能难开展(或者从某种程度上也没必要开展: 毕竟谁出钱谁拍板!),也很协调到资源来做。 与下级讨论的主要目的有两方面, 一方面下级对团队也会有自己的看法, 可以让管理者从另外一个角度来看团队定位职责是否正确, 因为有些资深员工还是会有自己非常独到的看法,从技术的角度来对这个问题进行审视; 另外一个主要的作用,就是可以看下下级对团队职责定位的认可程度, 毕竟他们是这些职责定位的落实者, 他们具体做事,只有他们认可,后续的工作才能顺畅开展(当然即使某人不认可, 也可以通过多次沟通进行说服)

另外需要注意,这个阶段更主要的是确定近期目标, 例如半年或一年目标, 所以需要确定的事既要比较实际,又要有所拔高; 同时也需要往前看一两年, 心里边要有一个大致的谱: 一两年后,自己的团队会走到哪里。

现在离理想状态有多远

分析团队现状:在指定这些目标的时候, 非常重要的一点,就是需要分析团队的现状: 例如团队现在的梯队,组织架构, 氛围, 相当于我们设定目标的时候是从当前的实际情况去做拔高,这个非常重要,如果起点很低,而将目标设定的非常高,也不是说不能实现,但有可能会出现目标过高导致不可能实现(具体设多少,是个技术问题,有时像又是个艺术问题)

例如11年团队调整的时候, 当时关键词搜索推荐团队分为工程, 策略团队(当时的现状), 后来考虑到这种组织架构会导致策略调研和策略上线之间存在断层(分析‘现状’), 出于提高团队策略迭代速度的考虑, 后来就将工程团队和策略团队进行合并, 且重新制定开发流程, 即后续很多项目, 都是从策略调研, 开发, 到最终推上线小流量乃至全流量都是由唯一负责人负责, 这样就避免了原来策略团队策略调研完毕后, 工程开发同学还要向策略同学了解具体策略考虑的代价, 同时工程同学也不会再觉得自己就是个外包, 避免了那种帮别人实现算法的失落感。 当架构有非常大的调整时, 才会引入外部纯工程团队, 一起合作推进架构的重构。

规划时,排除干扰因素:在很多公司我们都会说: 拥抱变化, 或是说: 世界上唯一没变的, 就是变化。 的确很多时候我们在做规划的时候, 都是在一个动态发展的节点对未来进行预见,会有很多变数。 例如13年就碰到两次大的团队调整, 而且第二次调整时, 团队调整方案已经定下来了, 而且已经和团队成员沟通了团队调整方案后, 突然接到老大通知, 调整方案有变, 整个团队会很快被划到另外一个部门, 后来不得不重新进行规划。 在这样变化的环境中, 会有很多的干扰因素, 但规划的时候, 其实可以在一定程度上先排除这些干扰, 否则考虑太多这种干扰因素, 会导致规划无法进行。

分几个阶段达到理想状态每个阶段如何做才能做到

分几个阶段做: 每次做年度规划的时候, 都觉得第一季度的事是相对比较明确的,第二季度的也还基本可以预知,但第三,第四季度的就很难把握了, 而前面也提到, 指定规划后, 需要定期review和调整, 所以每个阶段,最好不要超过一个季度,否则可能出现有些方向走偏但没有意识到的情况。每个阶段进行review,之后根据当前的进度进行目标的调整。 如果有些目标的达成需要太长时间, 则可以将这个目标达成再进行分解,避免某个节点持续时间过长。

需要哪些资源才能达到这样的团队水平

设定了上述预见的远景外, 就可以分析, 要达到该远景,需要哪些资源了。

资源可以从几个维度去区分:自己团队需要那些人, 需要上级的哪些支持, 需要兄弟团队的哪些支持,需要更大环境的哪些支持。

例如, 我们在进行百度关键词搜索推荐引擎团队规划时,认为后续需要在机器学习上进行加强, 于是开始联系HR,让其帮忙招聘更多机器学习方面的同事,同时开始联系擅长机器学习的团队, 一方面希望从兄弟团队引入对我们的项目感兴趣的同学,另一方面也了解他们团队中的机器学习工具和技术。

再比如之前团队调整过程中, 觉得关键词搜索推荐应该加强与百度检索投放系统的联动,所以后来与老大讨论后, 将底层涉及基础技术的topic model 方向划到了关键词搜索推荐小组。 这就是需要上级支持的典型。

还有一个大原则, 就是上述的规划,并不是一经制定后就是一成不变的,我们经常说计划赶不上变化,那为什么还要做规划?   规划的更大的作用是能让我们能将这些事在现阶段想清楚, 就类似于说拿破仑虽然每次战争都不是按照作战计划进行, 但每次战前他都会制定周密的作战计划。 所以, 我们要对规划怀着开放的心态,做好调整的准备。

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

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

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

百度在 2013 年是衰落的吗?是有怎样的依据?

知乎上受邀回答问题:“百度在 2013 年是衰落的吗?是有怎样的依据?”
正好在做自己个人的年度总结及明年的规划, 那也顺便分析下公司今年的情况。
我的观点: 2013年百度各业务发展势头都还算不错,中规中矩, 没看出特别出彩, 但完全谈不上差,而且一些行动,给别人看到老大的决心
下边的一些数据都是想到的时候从网上搜(不同的评估维度, 甚至同一维度不同的咨询公司给出的数据均会有差别)的, 谨慎参考。
可以从以下几方面看出来: 战略的推进, 内部机制
战略的推进
百度一直的思路都是去做入口, 都想直接占有用户上网需求的入口,从第一时间控制用户的上网时间。 这点从百度一贯的战略重心就能够看出来: 搜索, app下载(app下载的入口), 微购, 去哪儿, 爱奇艺等都是这样, 而今年公司在这些方面投入都很多, 也有不错的成绩: 可能变现上没有直接对百度有多大贡献,但是从市场占有方面, 提升还是非常明显的。现有搜索业务,中间页, LBS, 无线等战略方向均顺畅地推进中, 国际化没啥动静
现有搜索业务
虽然现在搜索需求增长已经放缓, 但毕竟这个业务还是最大的变现业务。 就好比股市里边说的现金牛, 虽然后续增长速度可能已经没有那么快, 但最赚钱的还是这个业务; 而且现在百度也在从生产力上提升变现效率, 例如商业知心细分各个行业提升变现能力及用户体验。教育, 金融等细分行业也已经上线。而且从财报中可以看到, 活跃用户仍然是增长的, 具体可参见13年Q3财报:Baidu | Press Releases
中间页
中间页相当于是将用户的垂直需求细化与具体, 是某个方向或点的需求满足。 例如去哪儿是出行的需求满足, 爱奇艺, 百度视频是视频的需求满足,微购是购物(虽然现在推广一般,但好歹做了个东西正在推), 而这些垂直需求与大搜索的需求整合起来, 威力的确惊人。
出行需求:这个今年百度也有比较大的动作, 去哪网上市(具体市场占有率没太关注, 但今年过年回家,在三线城市定酒店用的就是去哪儿, 而且第二天续住时,前台告诉我在去哪儿上定比较便宜, 而且网上仅支持去哪儿网, 当时感觉到去哪儿的覆盖率的确挺高) 我现在过年回家, 或是出去旅游, 基本上都是从去哪儿订票(以前都是用酷讯;不排除个人对公司的支持, 不过在上边下订单的确让人很放心, 而且价格也比携程低), 从各个维度看, 在旅游方面, 去哪儿市场占有均领先(数据均是来自网络, 谨慎参考):10月去哪儿无线端市占率38.86% 携程27.75%
视频需求: 爱奇艺与PPS合并, 外加一个百度视频, 基本上也占据了视频需求的一大块,艾瑞:10月份爱奇艺移动视频三大数据稳居第一 虽然现在还在厮杀, 但依托百度搜索这个老爸(技术+砸钱的支持, 比如百度Q3财报中显示内容的投入增加主要是在爱奇艺上: 可以参见ir.baidu.com), 市场占有率应该只会扩大, 而且现在也在推软硬件结合, 在卖各种爱奇艺电视, 小度影棒。 个人感觉这个比较有钱途, 一年多前一个创维的同学告诉我他在做互联网智能电视, 就觉得这块后续会取代传统电视:后续随着互联网电视普及, 谁还会去7点钟看脑残新闻联播? (至少我不会), 先看啥直接电视上点播, 随心所欲而且高清!
这块虽然现在不赚钱, 但赚钱迟早的事, 而且赚的是现在投钱在电视广告上的那些预算。当然, 有两个前提: 1是在现在视频市场的厮杀中不出什么大错,最后还是行业老大剩下来(当然这一块竞争还是比较激烈的, 说个狗血的小细节,说是爱奇艺买断爸爸去哪儿二期的独家网上播放权, 但内容中却可能会播放乐视的广告, 足见各种狗血各种竞争激烈); 2是政府不出强硬政策干扰这块的自由竞争发展。
91的并购
号称中国互联网最大的并购, 也体现出来百度一贯的做入口的思路与决心, 而且也让投资人看到了百度利用现有资源(现金, 技术)去为未来铺路的决心。在这方面的市场占有率也一下子就飞跃上升:百度91称日均分发8000万 市场份额超40%_科技频道
知心, 或者说其他垂直行业需求
教育, 金融, 网上购物等垂直行业都在试水, 例如教育, 金融等知心; 微购则是想整合网上的电商, 作为购物的入口。 这些垂直行业今年没那么出彩, 但至少在尝试中。
之前我就用google地图, 觉得还挺好用, 后来试了百度地图不就, 就将google地图卸载了, 这个真不是托: 百度地图真的比google做的好。 而地图虽然是个小工具(咋一看), 但背后代表的确实巨大的LBS需求, 包括各种衣食住行。 感受最深的就是11年去同学家, 当时用的还是Google地图,坐公交中转等车时,看到远处的楼盘上溪林, 然后google地图了一下, 结果当时google上就显示了上溪林售楼处的电话, 我还真就打了个电话咨询, 虽然最后没买这个盘。 但当时就意识到LBS变现潜力的巨大。
各种移动产品及APP
百度连七八糟的应用一大堆, 很多都很烂, 记得有一次出了个百度云笔记, 我用的时候真心失望无力吐槽, 烂到极点, 完全没有自己特色, 抄一个还抄的那么烂, 用它是伤我自尊。 但也有一些还算比较成功(当然和腾讯比还是差一大截,但还是在各种尝试,建立搜索的护城河) 百度移动这一年:13款过亿产品的全面布局, 有些真心好用, 例如云盘(之前一直用酷盘, 现在转到了百度云, 而且老婆的事业单位, 都实用百度云管理他们的资料), 相册, 输入法等都还不错。 这些虽然和搜索无关, 但可以说是搜索主业务的外延, 或是护城河, 占据了这些需求满足, 用户对百度的需求依赖就会更重。
无线变现(看份额的增长就比较明显)
这块在上个季度的财报中就已经体现出来, 无线搜索份额已经超过10%(参见http://ir.baidu.com), 所以这块会增长比较迅速, 也是公司的重点。
国际化: 说了好几年了, 也不知道之前说的覆盖全球一般的地区人口的目标何时能实现, 感觉没啥动静(或者有动静自己没太关注), 希望别到‘家祭无忘告乃翁’的地步
当然, 也有一个现象让人觉得挺有危机感的, 就是微信, 每次同学聚会, 一堆人都在玩手机, 而且基本都是微信。 没到这个时候就会觉得腾讯的牛叉。 这个如何破?
当然上边很多领域, 与腾讯还是有很多差集的; 而且百度非常看中技术积累, PM再给力点的话, 仍然会前途无量。
人才的引进
个人感觉百度和上面同学提到的MSRA的性质还不太一样, 百度会成立研究院, 但这些研究院都会有直接在项目中的需求, 例如deep learning会直接在百度的产品中有应用
一方面百度会在这方面有较大的持续投入, 邀请业界的专家加入百度, 也会提供较为丰厚的待遇,具体是多少我不知道, 但从公司财报可以看出(在研发上77.5%的同比投入增长: a 77.5% increase from the corresponding period in 2012, primarily due to an increase in the number of research and development personnel 参见百度2013Q3财报);另一方面百度会保证这些研究是与产品紧密结合的, 例如2013百度最高奖是语音识别引擎和通宝项目, 另外入选的团队还有基础机器学习的研究小组和deep learning在投放变现系统中的应用, 里边3个项目和基础研究有关, 都有业界大牛的带领, 而且都在具体场景中有应用:百度最高奖_百度百科
当然有一个让我一直比较困惑的, 就是百度的狼性, 这个仁者见仁, 愚者见愚(我是愚者)的东东, 我就不发表意见了。
更多内容可参见: 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