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

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

客户想要在百度上做搜索广告,就需要找到能够准确描述自己推广意图的关键词集合;但另一方面,目前百度凤巢系统拍卖词接近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

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

此处并不会列举每一种聚类(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