分类： 数据挖掘

1. 候选词源触发(query retrival)：其主要功能是通过各种offline数据挖掘，得到query（或是成份）之间的关系， 获取到候选的待推荐query，供后续逻辑进行处理。
2. 相关性过滤（filtering）：根据应用场景，对不满足query之间相关性的候选词进行过滤，以减轻后续逻辑的性能负担。 相关性过滤的方法可参见《分类模型在关键词推荐系统中的应用》
3. 排序(ranking)：根据应用场景的优化目标，对候选词进行排序。 例如， 如果要提升用户体验，那就直接将高相关性的候选词排在前边（衡量标准可参见《使用NDCG评估关键词推荐系统的相关性》），如果同时需要考虑商业变现， 那么可以考虑将能够获取到较多广告点击量的query排到比较靠前的位置
4. 业务规则（marketing rule）： 例如， ‘黄赌毒’结果必须过滤，或者带有某些特定字眼的关键词必须提到比较靠前的位置。。。。 这些规则更多是人为确定的（例如PM确定）

1. 网民搜索session数据（后续简称session数据）： 就是网民在搜索引擎搜索框中连续输入的多个query。 这里有一个假定， 就是同一个session中的query都是有关系的（更进一步， 同一个session中离得近的query更相关； 在多个session中都出现的连续搜索更相关），该数据可以表示为多个query的序列
2. 搜索点击数据： 即网民输入某个query后，在搜索引擎上点击的url，该数据可以简单表示为的pair
3. 网页内容信息： url对应的网页内容

1. 查询前： 在用户进入关键词工具时， 还未有任何交互时，此时关键词推荐系统主动向用户push用户可能感兴趣的种子query； 具体实现时，可以根据客户历史上采纳的搜索引擎拍卖词（即客户采纳的符合客户客户推广意图的关键词）分析出客户的推广意图或业务点， 使用传统推荐算法（content-based 或 collaborative 推荐算法）找出客户可能感兴趣的种子query进行推荐。该场景更偏推荐问题
2. 查询中： 即用户已经开始在关键词工具搜索框中进行输入，但输入还未完成的阶段。此时最常采用的方式是使用suggesion的方式，结合客户当前输入，向用户推荐完整的高质量query；具体suggesion挖掘，可以找到一些高频的query，结合session数据，搜索点击数据进行挖掘（百度suggesion具体的算法此处涉及泄密不再介绍，后续会有文章介绍业界公开的suggesion方法）
3. 查询后： 当客户完成一次搜索后， 客户搜索的内容已经基本明确， 此时就可以根据这次用户的搜索意图，找到相关的更高质量的query，以类似于搜索引擎相关搜索的方式推荐给客户。

1. 推荐给客户能有多而好的检索结果的种子词，并逐步进行优化，提升用户体验，提高客户提词量；对于搜索引擎而言是优化输入query。
2. 降低未曾使用过KR的客户的使用门槛，让KR的使用更为简单便利，扩大关键词工具的市场占有率；对于搜索引擎而言， 也能够快速提升其他用户经常搜索的相同/类似意图的query给网民，提升搜索量。
3. 通过种子词引导客户对账户关键词的优化，提高客户的ROI，提升百度收益，达到双赢目的。对搜索引擎而言则是能将搜索引导至相同/类似意图的搜索上，提升搜索引擎的变现效率。

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

客户想要在百度上做搜索广告，就需要找到能够准确描述自己推广意图的关键词集合；但另一方面，目前百度凤巢系统拍卖词接近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机器学习公开课教案中的伪代码：

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

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

应用： 虽然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

1. 训练数据的归一化： 工业界推荐系统，包括商业系统中user的数量非常庞大（例如facebook是10亿级别），而user都会有自己对推荐内容打分的独特习惯，例如有些人对推荐内容，都会一股脑地接收，或是给出较高的评价，而有些人则会打较低的分数；有些人总给一样的分数，有些人的评价则分布较为广泛。这就需要对训练数据进行归一化，规避user个性化对模型的影响。
2. 寻找一种适合数据的相似度度量方法：信息检索中的经典问题。在推荐系统中，第一步就是需要找到待推荐的候选， 以及之后的众多过滤，基本都是在使用合适的相似度度量过滤不相关的item，保留较为相关的item。例如在百度关键词推荐系统，以及触发系统中，大部分的工作，都是围绕相似度度量展开的（当然会比较复杂，包含各种特定场景，特定优化目标的相关性模型，以及使用topic model进行语义相关性计算）
3. 高效的neigibors查找算法： 正如1中提到，工业界中待推荐处理的user/item较多，所以不可能为每个neighbor的pair都计算相似度，所以一般会对待计算的neighbors进行剪枝，仅计算‘靠谱’的neighbors进行计算。