百度关键词搜索推荐系统交互流程

如果把百度凤巢系统比作商场,那这个商场的主要商品是什么?答案就是‘流量’,而关键词,就是流量对广告主最直观的表现载体。

客户想要在百度上做搜索广告,就需要找到能够准确描述自己推广意图的关键词集合;但另一方面,目前百度凤巢系统拍卖词接近10亿,百度每天有PV关键词约数十亿。从这些词海中淘出优质关键词,无论对于客户本身,还是为客户打理账户的客服而言都是一大挑战。
此时百度关键词搜索推荐工具(KR)就显现出它的重要作用。
那KR到底是什么呢?顾名思义,KR(Keyword Recommendation缩写)就是百度向客户推荐关键词的工具。当然,KR不仅提供诸如被动,主动,按URL,按行业等推荐形式为客户推荐个性化关键词,同时还提供像种子词,种子URL,Suggestion等引导提词技术;另外KR还提供客户账户诊断优化服务,一方面优化客户账户结构,提升客户提词,账户管理效率,同时也达到提升客户消费,提升百度凤巢系统整体消费的功能。

因为该工具是提供给百度广告主使用的,所以在网络上没有直接的入口,需要再www2.baidu.com上注册帐号后,找到‘关键词工具’后进行访问。

百度关键词搜索推荐交互

以下为关键词工具使用流程:

广告主进入KR入口(www2.baidu.com)中有多个入口,此时KR会根据广告主在凤巢中的历史操作行为,为其推荐种子关键词,广告主可以直接点击种子关键词进行搜索(种子关键词主要是面向对KR使用不熟练的客户,对他们的使用进行引导,百度搜索框也没有该功能,该功能为KR独有); 之后网民可输入搜索搜索query获取和该query字面,语义相似的关键词,同时系统会返回和这些关键词相关的属性。然后用户可以对关键词进行筛选及分组(系统会提供多种分组建议)

图: 百度关键词搜索推荐系统交互示意图

同时KR也提供传统推荐的方式为广告主推荐关键词。就是根据客户历史提词行为,使用SVD,图关系挖掘等协同过滤技术直接将结果推荐给广告主,广告主无需有任何交互输入,直接进入提词页面就能看到结果。

搜索系统策略架构

百度关键词搜索推荐系统(KR)不仅提供典型的推荐服务,即不搜既得,同时也提供搜索功能,即用户输入关键词进行搜索,KR推荐出与该关键词最相关的top n 关键词, 这些关键词不仅附带有容易理解的推荐理由(表明该关键词为何推荐出来),同时附带有关键词的各种属性(例如关键词在百度上的流量,竞争激烈程度等信息),同时对关键词按照字面,语义进行聚类;推荐出来的关键词默认已按照字面,语义相关性及marketing rule进行了排序。 以下为KR搜索过程online部分的策略架构(offline部分涉及较多数据挖掘逻辑,参见之前的文章介绍)

其中最底层为各种基础数据及这些基础数据经过预处理, 清洗后的存储, 以及基于这些过程的挖掘数据。当用户发起一次请求时,系统会经历以下主要步骤:

  1. 关键词触发: 根据经典的字面进行触发以及语义, 同购关系及复杂图关系的挖掘数据,触发出推荐关键词的候选。对应到百度搜索引擎上,该步骤就是query改写变换及文档的检索。
  2. 相关性准入:考虑到后续的过滤步骤, 触发的关键词量一般需要比最终需要的关键词数量多以保证召回。此时需要对这些候选关键词进行相关性过滤。例如使用GBDT模型进行二分类: 相关 or 不相关。
  3. audit:推荐出的关键词可能涉及黄赌毒, 为避免风险, 这些关键词需在推荐时尽早过滤。搜索引擎上,也需要对一些黄赌毒反内容进行过滤。
  4. ranking:为提升KR推荐的效率, 使用提词率模型,效用模型及价值模型对剩下的候选关键词进行排序,同时需要根据应用场景对关键词进行过滤(例如用户有pv过滤需求,则需要将pv值小于阈值的关键词过滤);对应到百度上, 最重要的技术就是ctr预估及质量度。
  5. marketing rule:此处集中了人工干预的逻辑,例如: 假设某个时间段需要KR推荐该消费的关键词,此时可以在此处增加逻辑对候选关键词队列进行重排序; 或者对于某些bad case进行过滤。搜索引擎上也需要有该逻辑层, 以便最快速度对结果进行人工干预。
  6. UI:关键词的展现, 以及保存等功能,同时包含传统推荐系统的正负反馈信息收集,反馈等机制; 以及KR独有的关键词分组功能,信息筛选功能等。对应到搜索引擎上就是前端的展示。

主动推荐策略架构

KR中的主动推荐,就是传统的推荐技术在百度关键词搜索推荐中的应用。所谓主动,是针对KR而言的:关键词,广告主无需发起交互操作,KR即使用传统推荐技术: content-based, collaborative filtering及多种技术混合的hybrid filtering方法向广告主推荐结果。

以下为KR主动推荐的策略架构, 一方面KR使用网民搜索日志,点击日志,广告库数据构建item候选集合,另一方面系统收集广告主的反馈(explicit or implicit)构建user profile,之后基于这些信息使用推荐算法向客户进行推荐。如果KR中的搜索功能是即搜即得, 那么主动推荐就是不搜即得

图:百度关键词搜索推荐系统主动推荐策略架构

按网页内容进行推荐

百度凤巢广告主都有自己的推广网站(或主页),而要达到较好的推广效果,广告主应该提交与网页相关性较高的关键词,否则即使广告主因为提交了一个高PV的关键词导致来到网站的流量较高, 也会因为内容与关键词不相关而导致转化较低而得不偿失。

KR为此提供了按URL进行推荐, 即广告主在KR搜索框中输入某一个网址(例如semocean.com),则KR会抓取该网站并分析其中的主题词进行推荐, 以下为主要的策略流程。

图:KR按URL推荐策略处理流程

 

每一种KR推荐算法, 或者做一个延伸:每一个商业搜索引擎中, 都会包含以下几个模块:触发,相关性过滤,rank,marketing rule。

其中触发是根据输入,找到一个相对较大的候选集合, 之后的所有排序过滤都是针对该集合的(在学术界使用的数据;例如搜索引擎中,根据网民输入的query,进行简单的字面语义匹配后,找到潜在的候选集合作为后续处理的对,又例如在学术界使用的LTR任务的开放数据LETOR中,直接使用BM25进行校验,筛选出相关性较高的top N进行后续的ranking实验; 之后对返回的结果进行相关性过滤及排序,最后根据一些业务规则进行强制过滤及重排序,包括黄赌毒反动内容的过滤,或是某些特定的人工干预。

图:KR搜索推词逻辑

 

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

协同过滤中item-based与user-based选择依据

协同过滤是大家熟知的推荐算法。 总的来说协同过滤又可以分为以下两大类:
  1. Neighborhood-based:计算相似item 或user后进行推荐
  2. Model-based: 直接训练模型预测Rating
在Neighborhoold-based算法中,又细分为user-based CF(Collaborative Filtering)和item-based CF。合适选择使用userd-based CF,什么时候item-based CF更适用就会是一个需要权衡的问题。一般而言,可以以下几个标准进行选择:
  1. Accuracy:一般而言,少数置信的邻居的推荐要比很多的没有太多区分性的邻居更加准确,所以一般我们会选择数量较少的因素(item or user)作为based的算法。 例如, amazon中的商品的种类很多,但远没有注册的用户多,所以该场景使用item-based CF比较合适; 反过来,在百度关键词推荐系统中,商业客户(user)量级是100W左右,而待推荐的关键词(item)是10亿量级,此时使用user-based会是更明智的选择。
  2. Efficiency
  3. Stability:一般情况下倾向于使用变动频率和变动量较少的因素作为based的因素, 例如item变动较少, 则选择item-based, 否则选择user-based
  4. Justifablity(说服力):推荐系统中,推荐理由越白盒,用户越容易理解就越有说服力。所以从这方面考虑,item-based CF会更有说服力,例如显示‘因为你浏览了三星 Galaxy,所以给你推荐了HTC One’的理由会比‘和你相似的用户也喜欢XXX’更有说服力,因为推荐系统是不披露哪些用户和我详细,怎么证明和我相似的,而且这种说法显得比较含糊。
  5. Serendipity:多样性就是user-based的一大优势,和自己相似的用户,总能发现一些自己还没发现的新东西。 如果追求多样性, userd-based会是不错的选择。
当然上述原则都不是绝对的,而且在真实工业界推荐系统中, 两种方法一般都是混合着使用。例如百度关键词推荐系统中,就会分别使用item-based和user-based方法找到待推荐关键词候选后,再统一使用model进行后续ranking。
参考文献:
  1. RSs Handbook
  2. Evaluating Collaborative Filtering Recommender Systems, Jonathan L.Herlocker
也可关注我的微博:  weibo.com/dustinsea
也可直接访问: http://semocean.com

经典聚类算法及在互联网的应用

此处并不会列举每一种聚类(Clustering)算法,因为学术界Clustering算法如果真要细分,还真有很多变种。此处只会介绍几种在我近几年互联网工作生涯中实际碰到的具体问题, 以及如何使用Clustering算法解决这些问题。

一般来说,我们可以将Clustering认为是将出现的数据进行Data Segmentation,也就是经常说的哲理: 物以类聚。 从机器学习的观点来看, Clustering算是Unsupervised Learning,或者叫做Learning by Observation,根据观察到的情况进行Clustering。 因为形成簇的数据都被聚到一起,所以Clustering 方法也可以用来发现噪音或是异常点。

Clustering 算法大致可以分为以下几类(参见Data Mining Concepts and Techniques):

  1. Partitioning Methods:这是一类经典的,最简单的聚类方式,就是直接按照类内的点距离最近,类间距离足够远的原则进行数据Clustering。该类方法比较经典的方法有K-Means 和K-Medoids。下文中会以广告分段问题来具体介绍K-Means的实现(K-Medoids类似)
  2. Hierachical Methods:层次Clustering算法,又大致分为bottom-up和top-down两种思路,bottom-up为自底向上,逐渐合并离得比较近的类以形成更大的类,top-down为一种divisive的思路,逐渐对离得比较远的类进行分裂。下文中会以如何合并搜索引擎中的同意,近义词词形成簇的的方式具体介绍bottom-up hierachical methods。
  3. Density-based Methods:以上两种方法基本上都是在高维空间中将数据聚成球形的多个类的方法,却不能处理非球形的聚类,Density-based Methods就是解决非球形数据的聚类方法。
  4. Model-based Methods:对数据进行建模,之后使用观察到的数据预估模型参数,比较经典的使用EM方法,先假设数据服从某种分布(例如k个高斯分布),并且这k个高斯分布由一系列隐随机变量决定。之后在E步预估这些隐随机变量,而在M步固定这些隐随机变量后,使用最大似然估计迭代得到最优参数。

文章以下内容将介绍3种聚类方法解决3个问题:

  1. 使用K-Means方法对广告受众网民进行Data Segmentation。
  2. 使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐。
  3. 使用EM方式寻找数据中的隐藏主体。

 使用K-Means方法对广告受众网民进行Data Segmentation

K-Means是一种球形的聚类,在二维空间中,类别会被聚成以圆心为中心的圆,三维空间中则会被聚成以球心为中心的球状簇(当然,这与选择的相似度度量有关,例如使用cosine计算归一化后的两个向量长度,就会变成计算二向量的夹角)

在K-Means算法运行前,有两个因素比较重要: 数据预处理和距离度量方法。具体距离度量参见博文相似度度量 ,数据预处理则包括数据归一化, 去除噪音等操作。

因为K-Means算法本身较为简单,此处直接给出Andrew Ng机器学习公开课教案中的伪代码:

k-means

其中uj为第j个簇的中心点,ci为第i条数据的簇类别。基本步骤就是遍历数据,每一轮迭代,先计算当前数据与哪个类中心最近,该条数据属于距离最近的簇,之后根据新计算出来的每条数据的类别,更新类中心。下图给出在指定数据上给出2个类的4轮迭代情况:

k-means-4-iteration

使用distortion function度量分类的好坏情况, distortion 越小越好,当然,一般distortion大小需要和类别 k 的数量间进行权衡。

distortion_function

应用: 虽然k-means堪称最简单的算法,但之前在实习时,在前东家还是用了一把,应用场景是使用MSN用户的注册信息(年龄,喜好,性别),以及MSN用户在 msn.com上经常访问的导航类别,搜索关键词等数据,使用决策树选出区分度较大的特征构成特征向量,使用L1-Norm进行归一化后,对特征向量进行Clustering。之后按Clustering向广告主售卖这些用户的pv。 该模式的优势是具有一定的兴趣定向作用。

 

右侧即为MSN展示广告。当然,该方法已经是2007年所使用的方法,现在相信MS已经使用更精准的方法了 。

该过程中尝试较多的是如何选择合适的类别数量k值,以及如何初始化初始类中心。当时迫于项目进度,k值最后根据经验并进行了粗略的搜索选择,初始类中心则使用在相同k值得情况下进行多次随机初始化Clustering

使用Bottom Up Hierachical Clustering方法对搜索引擎query进行聚类以进行流量推荐

例如在搜索引擎中, 很多网民的query意图的比较类似的,对这些query进行聚类,一方面可以使用类内部的词进行关键词推荐; 另一方面, 如果聚类过程实现自动化, 则也有助于新话题的发现;同时还有助于减少存储空间等。

例如:

训龙记国语  训龙记2 寻龙记  训龙记博克岛的骑手  驯龙记电影

骂人大全    骂人不带脏字的顺口溜    骂人带脏字越毒越好  骂人脏字的狠话

要设计层次聚类,就需要考虑一下几个因素及环节:

  1. 使用何种聚类算法: top-down 还是bottom-up 还是其他
  2. clusting的合并策略
  3. 使用哪些特征
  4. 如何度量距离
  5. 使用何种评估标准对效果进行评估

确定以上5个因素后,聚类算法也就确定了。

层次聚类

聚类算法:考虑到实现的复杂度, 一开始我们就确定使用bottom-up的方式作为聚类策略;后续也就没有尝试top-down的方式。

clusting的合并策略:

一般有两类合并策略: 选取最相近的两个clustering进行合并;求连通分量。 因为寻找相近cluster的方式, 时间复杂度会达到O(n^2), 所以最后决定使用连通分量。

特征: 我们使用字面特征及query在session中的共现特征; 例如, 对字面进行切词后的term(做适当过滤降维:idf太小则过滤)

距离函数, 尝试过cosine和jaccard后, 最终使用jaccard作为距离度量。

也可关注微博: weibo.com

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

推荐系统中的相似度度量

Cosine

最常使用的相似度计算方法,而且总体效果较好,可以说是简单实用。数学描述如下:

cosine_define

其中 是X的模。

例如,在推荐引擎中,使用 r_ui表示User u对Item i的打分,则可以使用u对各Item打的分数的向量作为User u的兴趣爱好,则User u和User v之间的cosine相似度计算方式为:

cosine_define1

其中 I_ui 表示User u,v均投票了的item。

Cosine的几何意义为向量空间中,将待计算相似度的向量均归一化为长度为1的向量, 所有被归一化后的向量  ov的v点坐标均落在以向量0为球心,半径为1的球面上,使用二向量的夹角度量二者相似度,夹角越小,相似程度越高。

在文本处理过程中,cosine度量方式表现效果都会比较好。

Mahout中参见CosineDistanceMeasure.java

Pearson Correlation

用于度量线性关系最常用的方法, 定义 为协方差,σ为标准差, 则Pearson相关系数为:

Pearson_num

例如,使用 表示User u对Item的打分,则User u,v之间的相似度计算方式为:

Pearson_num_2

其中 表示User u,v均投票了的item,与COS的区别是考虑了投票的均值, 且分母考虑的是User u,v共同投票的Item。

很多时候,针对User的PC要比针对Item的PC效果较好,因为针对User的PC相当于对各个用户的投票Scales做了一个中心化,避免各用户对相同Item投票时,因为投票习惯不一样而导致的差异。例如:投票分值分[1,5]档,有些人投4表示非常喜欢, 而有些人会投5表述相同的喜好程度。

PC的缺点如下:

  1. 如任意User仅投票了一个元素, 则无法使用该公式计算。
  2. 如任意User的每个投票分值均一样, 则无法使用该公式计算。
  3. 计算时没有考虑投票的总数量, 例如User u投票了200 Items,而v仅投票了2Items,则最后有可能还是v与待比较User近似。

另外PC也经常用作序列趋势的相近程度度量。在检索,推荐系统中经常需要考虑检索结果及推荐商品的季节因素,例如根据往年某一商品的季节特征,预测类似产品的接下来的流行程度。 下图分别为检索词‘吴莫愁’,‘梁博’,‘滑雪’在过去3个月的搜索PV,使用PC度量,很容易得到检索词‘吴莫愁’与‘梁博’的相似度远远大于‘梁博’与‘滑雪’的相似度。

tread_liangbo_wumochou

Mahout中参见PearsonCorrleationSimilarity.java

Spearman Rank Correlation(SRC)

Spearman Rank Correlation和Pearson Correlation非常类似, 只是SRC没有考虑对User对某具体Item的投票,而是考虑Item 在User所有投票中的相对Ranking。其数学表示为:

SRC

其中 k_ui表示User u对Item的投票值在User u所有投票中的Ranking。

SRC的优点是能够避免每个用户因投票习惯不一致带来的误差, 缺点是计算开销较大(每次计算都需要进行排序)

Mahout中参见SpearmanCorreleationSimilarity.java。计算复杂度较高。

Simple Matching Coefficient

imple Matching Coefficient

仅考虑数据为二值的情况(0,1)。 如果数据非二值, 则将数据转化为为二值。定义M01为u中属性为0,但v中属性为1的数量,M00表示u,v中属性均为0的数量,M10,M11同理。则SMC定义如下:

SMC

例如u=[1,1,0,0],v=[0,1,1,0],则SMC=2/4=0.5

Jaccard Coefficient

与SMC计算方式类似,但具体运算公式如下:

JC

即仅考虑两个向量中,同一维度上值均为1的数量。该相似度度量公式在文本匹配中也较为常用, 比如在计算两个短字串的相似度时,首先将字符串切词,找到更细粒度的切词结果term,之后以不同的term作为不同维度的属性,使用JC计算相似度。

Extented Jaccard(Tanimoto)

extend_JC

 

距离度量方式

该度量方式是最直观的度量方式,一般使用曼哈顿,欧几里得距离度量,而更为广义的是闵科夫斯基度量方式。以Euclidean Distance为例:

欧几里得距离计算公式

可简单转化为相似度则表示为:

欧氏距离转相似度

在Mahout中参见以下实现:

EuclideanDistanceMeasure.java

ManhattanDistanceMeasure.java

ManhalanobisDistanceMeasure.java

其他内容

为了提高运算速度, Mahout中实现了CachingUserSimilarity.java来缓存两User/Item的相似度计算结果。

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

或直接访问 semocean.com

PageRank的经济学效用解释

google大名鼎鼎的pagerank算法大家都耳熟能详,基本的思路就是: 网页的重要性由指向该网页的链接,及指向网页的重要性决定。
那从经济学的角度, 背后隐藏的深层含义是什么呢?  说简单点,就是‘具有流动性的市场对商品价值的客观定价’。
我们先举一个简单而又经典的例子: 假设在原始社会中, 没有货币的概念, 所有的交换均为物物交换。 且生产社会中只有三个生产者:  农夫(使用F表示), 生产衣服的人(使用C表示)和生产工具的人(使用M表示)。 三个生产者生产出来的物品, 除一部分留己自用外, 其余均用于与其余二人进行交换。 交换关系如下:
图1: 三生产者的交换比例关系
F M C
F 1/2 1/3 1/2
M 1/4 1/3 1/4
C 1/4 1/3 1/4
图2:三生产者的交换关系邻接关系
以农民为例,除1/2生产的农作为自行享用外,剩余1/4与工具制造人换取他制造的1/3的工具,用剩下的1/4与衣服制造人交换他生产的1/2的衣服。 则根据列昂惕夫生产投入产出理论, 在自由市场下,交换的比例也即反映出该产品的内在价值。 以上图为例,假设:
一份农产品的内在价值为x1,一份生产出的工具内在价值为x2,一份衣服的为x3,则获得方程如下:
1/2 * x1 + 1/3 * x2 +  1/2 * x3 = x1
1/4 * x1 + 1/3 * x2 + 1/4 * x3 = x2
1/4 * x1 + 1/3 * x2 + 1/4 * x3 = x3
即可用解线性方程组的方法解除各内在价值。 该方程组背后的思想是: 任一物品的价值由自由市场中其他商品对其的认可程度决定。  后续会讲到, PageRank中迭代求稳定特征向量的过程, 其实就相当于是在自由市场中, 货物经过长时间流通后所反映出来的市场价值认可程度。
上述例子是在知道了邻接矩阵(转移关系)的情况下直接求解内在价值的过程。 如果我们对每种物品进行初始定价, 则能够计算在该转移矩阵的作用下,物品的价格在市场的作用下逐渐趋向于内在价格。
又例如:
教科书中一个非常经典的例子,是小镇上已婚女性和单身女性每年的数量问题:某小镇上,每年30%的已婚女性离婚,20%的单身女性结婚,镇上有8000已婚女2000单身女,假设小镇上女性总量为常数,分别求一年,二年后的女性数量?
求解方式为构建已婚,单身女性的转移矩阵A=[[0.7, 0.2],[0.3, 0.8]]   (此处使用python第三方库 numpy方式表示matrix)   x=[8000, 2000]为当前已婚,单身女的数量向量。 则一年后小镇上已婚,单身女性的数量向量x1 = A*x  两年后为 x2 = A* x1 = A*A * x    ;  如将x 写为已婚,单身女性的比例, 则该过程为Markov Process(Markov Process为随机过程)
PageRank
PR其实就是随机过程在网页ranking过程中的应用,该算法假设网页都是有价值的, 且价值是可以传递的,同时价值传递时也会衰减。 价值大的节点传递给指向的网页的价值也比较大。该算法中的思想其实是个人类学的问题: 和权威的人关系紧密的人, 一般也较有权威; 也经常说: 你的收入和你关系最近的5个人类似  啥的说法都比较类似。
PR的计算方式如下:
其中PR(n)为节点n的PR值,它由指向n的节点q集合的PR值及系数w决定, 1/|V| 为随机跳转概率避免闭环
所有节点的PR值计算方式如上, 其中C即为转移矩阵。
实际应用中, 一般是制定PR的迭代次数作为停止条件。
而PR值其实就可以直接看作是一种价值转移直到稳定状态。
参考文献:
  1. 经济学原理
  2. The PageRank Citation Ranking: Bringing Order to the Web
也可关注微博: weibo.com/dustinsea
或是直接访问: http://semocean.com

特定场景的Cralwer

有时也叫Crawler。
今天整理电脑文档的时候发现很早09年初自己写的一个crawler的设计文档, 打开这个50多页的文档,里边N多的逻辑图及规范定义的数据结构, 才觉得真的好久没有见过写得那么规范的文档了(也许有点自夸, 或者码农都觉得自己的就是规范: )
将其中的总体设计图分享给大家参考,确切的说,并不是一个完整的crawler,而是一个连通性检查模块,所以当中更增加了很多定制化的逻辑。
该设计中严格地区分了数据流及过程,也算是设计图中的一种创新了。
设计时参考了Ming the Web: Discovering Knowledge from Hypertext Data》中的Crawler, 其中完整架构如下:
此处也向大家推荐这本书《Ming the Web: Discovering Knowledge from Hypertext Data》,里边对于从spider 索引建立,ranking,检索过程等搜索引擎相关的技术都有深入浅出的介绍, 特别适合从事互联网,特别是搜索的同学。
参考文档:
Ming the Web: Discovering Knowledge from Hypertext Data
也可关注微博: weibo.com/dustinsea
或者直接访问http://semocean.com

google youtube 电影推荐算法

在面试实习生的时候,我有个习惯,就是面试快结束的时候,会像聊天一样和面试的学生聊一下他们对某个技术方向的看法。很多时候不是期望他们能提供什么灵感,也不期望能聊出太多结果,更多的是想通过这些沟通,看一下现在学生对这些问题的看法达到什么程度,而且这些沟通很能反映一个面试者的个性。 比如有些人对问题比较坚持, 或者叫做偏执,或者叫做执着,都能够反映出来。
前几天面试的时候到了最后环节的时候,忘了是说什么问题了,面试的实习生提到一般工业界使用的推荐算法都是比较简单的,不会去尝试复杂的算法。 我问他为什么,他说觉得工业界不会投入太多人力; 后来我告诉他还需要考虑处理的数据量和可维护性等因素。 当然他说的这个现象的确比较普遍: 工业界一般都倾向于使简单粗暴有效的算法,只有这些方法都搞不定时,才会尝试更复杂的潜在算法。
两个例子: 一个是 youtube 使用的电影推荐算法(参见论文: The Youtube Video Recommendation System);另一个例子就是Baidu关键词推荐系统中使用的级联二步图;  应该说Baidu关键词推荐系统中的级联二步图的思路是借鉴于youtube电影推荐算法并应用在关键词推荐的场景中。 下边就简单介绍下youtube Video推荐算法。
算法的思想其实比较简单:使用关联规则找到有关联的电影,计算权值后进行ranking推荐。其中的新意在于,这种关联关系能够进行多次传递,逐渐扩大和种子电影相关的电影集合(当然关系传递得越远,一般关联程度也会相应减弱)
具体的推荐过程可以分为3步:
建立video间的关系
建立video间关系的方式比较简单,使用关联规则中的共现方式即可。此处youtube使用的是24小时内session的co-visitation。具体为:
使用 r(vi, vj) = cij/f(vi,vj) 表示video i和video的关联程度, 其中 r为两个video/item的相关系数, ci为i,j共同出现次数, f 为 vi, vj归一化后的分母总量(最简单的方式就是ci * cj),这样就能找到相关的两个vedio
产生特定用户的video候选
该过程在经典信息检索中可以被理解为触发逻辑,及找到待推荐video/item的候选(触发逻辑在推荐系统中所处的位置及重要性参见另外一篇blog: 传统推荐引擎系统架构)
定义S为特定用户的种子video集合, 例如在youtube推荐系统中可以选择用户最新观看(或者最新完整观看的video),之后的问题就是怎么找到和种子词相关的video进行推荐。我们将其分为以下3步:
  1. 定义Cn(S)为和种子集合S相关联的,通过n步扩展后的推荐候选集合。 例如 C1(S) = 所有Ri的并, 其中Ri是与S中的vi相关联的v(寻找相关联v的过程参见上述:产生特定用户的video候选)。 相当于找到所有与S中种子vi想关联的v的并集;该做法的缺点是可能范围比较小且太相似。
  2. 使用Cn(S)进行触发, 即得到C(n-1)(S)后,再找到与C(n-1)(S)中每一个vi相关联的v,之后去除种子词S,我们称Cn(S)为对S的n步扩展。
  3. 同时在C(n)(S)中保留着每一个v被找到的原因, 便于后续ranking及给出explanation。
经过上述3步,对于特定user的候选video就触发完毕了。 该触发步骤可以说是该论文中的值得借鉴的点。 组里之前一位工程架构策略都很牛的同学指导实习生实现了一个通用的级联二步图算法框架, 该算法框架能够将有关联的节点的关系进行传递:
例如对于关键词,我们可以使用topic 主题(由topic model产生)建立关键词之间的跳转关系, 或是关键词中的核心term(一般是归一化后的核心term)建立跳转关系。 而该框架更令人着迷的是, 二步图的左右两边可以不是同样的item, 例如左边节点是keyword而右边是user, 则可以使用topic 直接建立keyword与user的关系进行推荐。
 Ranking
youtube 的ranking策略主要考虑以下3个因素:
  1. video质量, 这个可以通过网名对video投票打分得到。这一项和用户及对应偏好, 仅和video自身质量有关,就类似于搜索中pagerank得到的page质量度一样
  2. user specificity: 在触发后,可以通过使用user profile和电影的一些质量, 或是内容属性进行排序。这一项反映的是用户对电影的偏好得分
  3. divercification:特别是类似video这种兴趣相关的内容, divercification的引入就显得非常重要了,否则推荐的video会逐渐收拢到可数的一两个品类,可以使用的方式是限制每一个category video的推荐数量,或者本文中限制每个seed video出的video的数量;相反, divercification在不同的场景下可能不同,百度关键词推荐中, 根据种子词直接检索得到的结果需要考虑与种子query的强相关性, 此时divercification的引入, 或者引入的程度需要比较慎重保守。
当然, ranking机制一般都会非常复杂, 论文中此处只是简单介绍; 例如在构造百度关键词推荐系统的过程中, 我们引入了提词率预估, 效用预估, 价值预估等模型对返回结果进行ranking。同时也需要结合user interaction的样式,算法出口(interface)等进行调整。 具体ranking机制会在后续blog中介绍。
效果上, 级联二步图的引入,能够找到非常多靠谱的结果(当然二步图边的建立是核心,选对了边的建立方式,才会有好效果),具体效果数据就不便透露了:)   反正是基本上能够覆盖全部凤巢用户,每个客户都能推出数量惊人的关键词(当然,需要使用字面, 语义等技术进行后续filtering and ranking)
更进一步, 级联二步图是图关系挖掘的一个简单有效的特例, 使用类似于pagerank等经典算法, 也能够很好地找出类似的关系进行推荐。
参考来源:
  1. 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.
  2. Google Adwords
  3. 百度关键词推荐工具 :http://support.baidu.com/product/fc/4.html?castk=e6f89hg77d37ada65d612
或者直接访问 http://semocean.com

Collaborative Filtering根据近邻推荐时需要考虑的3要素

在使用类似于item-based 或user-based collaborative filtering构建推荐策略时,会涉及以下3个因素:
  1. 训练数据的归一化: 工业界推荐系统,包括商业系统中user的数量非常庞大(例如facebook是10亿级别),而user都会有自己对推荐内容打分的独特习惯,例如有些人对推荐内容,都会一股脑地接收,或是给出较高的评价,而有些人则会打较低的分数;有些人总给一样的分数,有些人的评价则分布较为广泛。这就需要对训练数据进行归一化,规避user个性化对模型的影响。
  2. 寻找一种适合数据的相似度度量方法:信息检索中的经典问题。在推荐系统中,第一步就是需要找到待推荐的候选, 以及之后的众多过滤,基本都是在使用合适的相似度度量过滤不相关的item,保留较为相关的item。例如在百度关键词推荐系统,以及触发系统中,大部分的工作,都是围绕相似度度量展开的(当然会比较复杂,包含各种特定场景,特定优化目标的相关性模型,以及使用topic model进行语义相关性计算)
  3. 高效的neigibors查找算法: 正如1中提到,工业界中待推荐处理的user/item较多,所以不可能为每个neighbor的pair都计算相似度,所以一般会对待计算的neighbors进行剪枝,仅计算‘靠谱’的neighbors进行计算。
训练数据归一化
最常用的训练数据归一化方法,非Mean-centering莫属,该方法的核心思想就是对于每一个user,找出其投票分值得中心,该用户其他的分值均会与该中心对比正负,即不关心投票分数的绝对值,而是看与均值的偏差: 如果投票分数为负数,说明是一个负向的打分,如果为正值,则说明正向。例如小明和小张都是用户,小明平均情况下对电影的打分是3分(例如满分是5,最低分是1),小张的打分均值是4,说明相比于小明,小张喜欢打高分,对于小张,一个电影如果打分为3就算是负向评价了,而同样的分值对于小明这样的分数是个中性的分数。
item-base CF中mean-centering计算方法如下:
user-based CF中mean-centering计算方法同理
设想这样一个场景: 小明和小张投票的均值均为3,小明投票时都投3分,而小张则各个分数的分布都有。如果小明和小张对于同一个电影都投了5分,此时小明和小张的投票体现出的信息是不同的: 小明平常都投3分而此时投了5分,这一票体现出的信息,比经常投5分的小张的一票体现出的信息要多(类似于TF-IDF中的IDF原理),而Mean-Centering则不能体现该特性。故我们引出另一种Normalization方法: Z-Score
Z-Score
核心思路是:如果一个用户投票的波动较大,则其投票的话语权要降低。具体计算公式与Mean-Centering相比,除以标准差即可。
极端的解释,就是经常投各种票的人, 其投票的权重会被降低;而投票分值一般不变,但突然改变以往习惯投票值得一票,体现出的信息较多。

在这插入另一篇文章中的思想: 就是经常投票给较多item的user的票的权值需要进行惩罚。例如在youtube推荐视频时,如果某个视频经常和很多视频一起被观看,则有可能不是因为他们相关,而是某个视频就是比较热,需要增加惩罚降低‘哈利波特’效应(具体思想可参见论文: the youtube video recommendation system),例如百度关键词推荐系统中就在级联二步图算法中对类似边的权值进行了惩罚(具体技术实现后续会有专门章节介绍)
Neighborhood 中的相似度度量方法参见前文,此处就不再复述。
至于高效的Neighbors计算方法,则可以在离线计算时设定固定Neighbors的具体N值(KNN中的N),之后在性能和效果之间权衡, 就像你知道的,很多时候,系统设计,就是在不停地在性能和效果之间做取舍达到平衡。
参考文献:
the youtube video recommendation system,James Davidson 等
RSs Handbooks
可关注微博:  weibo.com/dustinsea
也可直接访问:  http://semocean.com

关键词推荐系统架构

在百度做关键词推荐系统3年多, 以前更多是从工程, 以及解决用户需求的角度去考虑系统的实现。 大概一年前开始系统地学习业界推荐系统相关的内容并对照自己手头的工作。 当时就画了以下系统结构图, 算是对百度关键词系统(KR: Keyword Recommendation)中主动推荐(主动push结果给客户)的一个总结。
系统逻辑图如下:
当中包含以下几个重要步骤:
  1. 离线的数据挖掘: 根据广告库,客户landingpage内容, 网名检索query等数据,建立关键词之间的关系。 这块能做的工作非常多,包括建立关键词之间的商业价值关系,等同相关性等。很多任务都是offline的, 在hadoop/spark上进行挖掘。
  2. 关键词候选集索引建立:当这些关系建立后,就将这些关系数据建立索引加入线上系统,而且经常会提前做结构化的预处理以提升线上处理效率。
  3. user profile建立:根据用户提词反馈, 包括显式的反馈,包括对关键词的正/负向评估以及隐式反馈(通过KR,或者通过其他途径提交了关键词),以及用户的注册信息,Landingpage等构建用户user profile
  4. 结果触发:当用户访问KR时,首先根据离线挖掘的各种关系数据进行触发, 得到关系数据的大量候选。之后结合user profile进行过滤
  5. ranking: 该处的ranking较为负责, 可以分别对采用率, 的pair的效用,使用模型进行预估, 之后综合加权。 此处的效用, 可以根据具体场景的不同而做定制。
  6. 业务逻辑的ranking(Marketing Rule):相较于上边提到的纯算法策略的ranking,有时也需要根据具体产品的出口, 场景等因素, 使用规则对结果进行reranking, 以满足业务需求(此处未在上图中体现)
当然真实系统并不是上述内容就能说清的, 例如线下数据挖掘,就会用到二步图, 全关系PageRank, 关联规则等多种方式进行挖掘。 触发时也需要考虑各种同意,核心等的变换, ranking时使用机器学习方法结合业务规则综合排序。 更多细节可以参考后续推荐系统相关文章。
更多内容可关注微博:weibo.com
或是直接访问: http://semocean.com