特定场景的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上进行广告投放时, 需要选择关键词, 以向搜索引擎表述自己想要覆盖的有商业价值的网民搜索流量。 在选择关键词后, 还需要设定具体的关键词匹配模式, 以告诉搜索引擎选择的关键词以何种方式去匹配网民的搜索。 举个例子: 网民在百度上搜索 ‘鲜花快送’, 假设商家A是卖花的, 搞鲜花速递业务的, 则A可以在百度凤巢系统中选择‘鲜花快送’这个关键词,同时设定匹配模式为精确匹配(即网民搜索和A在凤巢系统中选择的关键词完全一致时才出A的广告, 更多细节参见:http://yingxiao.baidu.com/), 假设B在凤巢中未选择‘鲜花快递’, 但选择了‘鲜花速递’, 假设B选择了广泛匹配(语义近似即匹配,具体参见http://yingxiao.baidu.com/), 则B的广告也会被触发(具体是否会展现, 还和出价, 质量度等诸多因素有关)
此时会面临一个问题: 广告主在凤巢系统中选择关键词时, 仅凭自己去想, 很难完全想到所有符合自己需求的关键词(网民的搜索query千奇百怪), 故需要提供工具, 帮助凤巢客户快速找到和自己推广意图一致或相近的关键词,即: 关键词推荐工具。
从交互上来看,可以将关键词工具看成一个搜索引擎,凤巢客户输入一个种子词(种子query),返回一个和种子query意图相近的推荐词list。
当然作为推荐系统, 其中还会包括属性披露, 推荐理由, 关键词行业分类, 关键词自动分组等支持, 这些内容会在接下来的其他博文进行介绍。
整个推荐流程大致如下
整个推荐流程, 大致分为5步:
  1. 基础日志,数据清洗即预处理
  2. 候选词触发: 根据输入种子query触发得到系统性能支持的最大关键词候选(供后续流程进行筛选过滤及排序),当然为保证性能, 该过程中会保留触发关键词的各种基础属性,例如PV, 行业, 主题等; 一般业界的检索,推荐系统会有较多触发逻辑逻辑,故触发出的关键词会比较多
  3. 相关性过滤:因为触发出的推荐关键词较多,故需要判断推荐关键词与种子query的相关性;既要保证召回,又需要保证准确性。
  4. ranking
  5. 使用业务,商业规则对最终结果进行排序调整及过滤(最经典的, 黄赌毒必须过滤删除)
对于相关性过滤,很早以前我们也是使用规则进行过滤,但随着规则数量的急剧增加,一方面导致系统架构性能下降,另外一方面也使系统策略越难约维护,故最终决定使用机器学习方法进行相关性过滤。
涉及到机器学习方法解决问题, 就会涉及到3方面的问题: 用哪些数据,准备哪些数据,如何处理数据? 使用哪些特征? 选用何种model ?
数据
一般来说,如果数据选择有问题, 那基本可以说后边无论再做多少努力, 这些努力都会付诸东流, 公司里这样的机器学习相关的项目也不少见: 几个人全情投入几个月或是1年多,效果总提不上去,回过头来发现数据就有问题,哭都没有眼泪。
所以一开始我们选择数据就比较慎重,还好关键词推荐工具隐性和显性反馈数据都还算比较丰富(推荐系统中都需要有这些信息, 将整个数据流形成完整的迭代闭环): 我们可以认为用户输入一个query并选择了这个query返回的某个候选推荐词的pair,就是一个正例(即模型是判断是否相关,相关为正例,不相关为),而输入一个query后,用户将返回的某个词放入垃圾箱(关键词工具交互上支持该操作),则query及被放入垃圾箱的关键词组成的pair,即为负例。
获得数据后, 很快就发现一个问题: 客户操作得到的正例, 就是毫无疑问的正例;但用户的负反馈(用户使用种子query搜索得到返回结果后,被扔入垃圾箱的的case)很多时候并不一定和query不相关, 甚至是很相关,只是因为用户个性化的原因导致客户认为这个case 不适合自己。
比如: 一个客户主要卖各种花茶, 像菊花茶, 桂花茶等,但他不卖茉莉花茶,此时如果用户输入花茶, 从相关性来说, 推荐‘菊花茶’,‘茉莉花茶’, ‘桂花茶’其实都是OK的,但用户将‘茉莉花茶’放入垃圾箱,因为他不卖该产品。其实并不能说明花茶和茉莉花茶不相关。
为了消除因个性化带来的负例不准的情况,我们人工标注了1.5W非个性化的负例。 并进行随机sampling, 使正负例数量基本相当。
最终使用1/10数据作为测试样本,9/10作为训练样本。
特征
数据准备就绪后,下一步就是如何选择合适的特征了。 因为整个关键词推荐系统所能触发的关键词各式各样, 各种类型千奇百怪, 所以如果直接使用各种地位特征(例如字面,或是ID类)的话,会导致特征空间较大而数据比较稀疏,导致完成分类基本上变成不可能完成的任务; 所以我们不能直接使用字面, ID作为特征进行分类,而是要使用更加泛化,高维的特征。
在特征选择过程中,我们也充分贯彻了站在巨人的肩膀上远眺的方式,充分利用手头的资源,例如短串核心判断,同意变化扩展等基础工具进行特征设计。更详细的特征此处不便于列出,仅列出两个有代表性的特征供大家参考。
  1. 推荐词与种子query经过切词后的相同term的长度之和与种子query经过切词后的term的长度之和的比值;类型为double类型。
  2. 推荐词基本切词后切词顺序包含 query, 特征值为1,默认值为0;类型为double类型。
  3. 推荐词,种子query的topic向量相似度。
  4. 。。。。更多高维特征。。。。。
利用多个类似的高维特征,就能很好地覆盖推荐词与种子query; 当然特征的设计会直接影响关键词推荐中相关性的定义,例如如果字面(重合)相关特征较多, 则推荐主要表现为字面相关,如特征主要为语义特征, 则推荐结果反映为语义相关。如果特征中有用户的历史行为信息特征(例如用户已经选择的关键词),则可以认为相关性模型就已经实现了个性化处理。
 模型
很多项目因为周期比较赶, 所以小步快跑的起步阶段并没有太多时间去做模型和参数的双向搜索,所以综合效率和时间的代价,选择了部分模型及在经验参数下的效果,进行模型的初选。
最终综合考虑性能,准确性和召回诸多因素下,选择了adaboost,在adaboost ratio 和 弱分类器数量上进行了参数实验。 准确性/召回 效果如下:
具体adaboost算法参见: adaboost介绍
WLRatio 300 500 1000 1500
0 0.87/0.89 0.87/0.91 0.87/0.9 0.86/0.91
-0.1 0.81/0.95 0.79/0.96 0.8/0.96 0.8/0.97
-0.2 0.74/0.98 0.73/0.98 0.73/0.98 0.73/0.98
-0.3 0.66/0.99 0.64/1 0.65/1 0.64/1
评估
以上内容均属于线下模型优化部分,所有的指标均可以线下获得, 但最终需要用线上的效果说话, 最后说服力的, 还是线上A/B Test, 因为是后台策略的升级, 故这样的实验在成熟的A/B test框架下比较容易做; 线上实验的最终效果也比较符合预期, 保证准确性的情况下召回大为提升(此处就不贴具体数值)
后文:后来将adaboost直接替换为Random Forest,在未改变模型的基础上效果立刻提升非常多,可见模型选择也较为重要。
参考文献:
百度凤巢关键词工具: www2.baidu.com
Data.Mining.Concepts.and.Techniques.2nd.Ed
也可关注微博: weibo.com
或是直接访问: http://semocean.com

使用impurity选择树模型拆分节点

在近期的项目中经常会使用到连续值模型以提升模型效果。 例如在项目初期, 训练数据准备OK后,就会使用原有的LR模型初步训练model看实际的效果, 同时因为连续值模型, 特别是树类模型已经在其他项目中应用并取得较好的效果, 所以我们也会将离散特征进行变换处理后, 使用GBDT, RF看下实际效果。
虽然GBDT, RF都有现成的model训练环境,直接用就可以,在项目过程中还是顺便复习了一下与树类模型相关的impurity度量标准;就像侯捷在《STL源码剖析》中说的,开飞机的人不一定需要了解飞机的原理,但参观飞机制造厂也是一种乐趣。
常用的使用impurity选择树模型拆分节点的度量有以下几类,他们都来自于信息论:
  1. Information Gain
  2. Gain Ratio
  3. Gini Index
以上三种根据impurity进行拆分的度量方式各有优缺点, 一下具体介绍
Information Gain
首先要定义概念熵(entropy)可以理解为定义一个分布的信息量, 具体定义如下:
其中D为数据集合, pi为第i类在数据中出现的概率。之所以使用以2为底的对数, 是因为我们默认使用bit进行编码。而该处的info/entropy即描述分布不纯的程度。 而我们可以将树模型看成是对接点进行分裂, 之后根据拆分条件节点的建立使整棵树的叶子节点尽快达到较纯的状态。
假设现在有A,B,C作为拆分feature的候选,且假设我们选择使用featureA进行拆分, 则拆分后的信息为:
其中A为选择的feature,Dj为feature A的值为j的集合,而Information Gain,即表示在原分布上,确定待拆分的feature A 后, 所带来的信息增益(减少的信息量), 拆分时使用贪心算法, 信息减少量越多越好。故:
每次拆分时,贪心地选择Gain最大的feature A进行拆分即可。
最经典的Decision Tree算法ID3中即使用Information Gain作为节点拆分的标准。ID3算法具体描述参见:http://link.springer.com/article/10.1023/A:1022643204877
Gain Ratio
Information Gain在节点拆分时是有倾向的, 倾向于拆分属性值较多的feature,一个极端的例子,假设feature是具体的ID值,即每条instance的ID值都唯一,则对该feature进行一次拆分后,则每个节点都达到纯的状态,Information Gain值最大。为了解决该问题,在ID3的升级版Decision Tree中引入另外的拆分标准,Gain Ratio。
定义:
因为某feature的属性值越多, SplitInfo就会越大,故可以使用SplitInfo在一定程度上消除Information Gain倾向于多属性feature的偏好。 具体Gain Ratio如下:
在此:属性值越多Gain越大,但SplitInfo也会越大,这样就中合了Information Gain带来的偏向。
P.S. 做策略算法中,类似的操作都是互通的,例如在推荐引擎中,用户打分可能偏好不一样,有些习惯打高分,有些习惯打低分,则我们可以使用打分的均值去中和这种偏差;而有些人打分分值比较集中,有些人则分布比较广泛,则我们可以使用z-score,即处于标准差去一定程度上消除这种分布。
Gini Index
Gini Index在CART(Classify and Regression Tree)中使用,定义:
其中D为数据集, pi为类Ci在D中出现的概率, 可以直接使用|Dci|/|D|预估。
假设我们在feature A上进行拆分, 并且是进行二分类拆分,拆分得到D1,D2数据集
则拆分后的Gini Index如上。
同样, 我们使用Gini稀疏的减少量选择拆分的feature。
这里需要注意,CART中仅进行二分拆分,如果A为多属性, 则需要转化为二分类拆分。
细心的同学可能会发现,除了gini和entropy的定义不一样外,其余的计算Gain的方式都是相似的
reference:
induction to decision tree,  J,R,Quinlan
Data Ming: Concepts and Techniques
 也可关注微博: weibo.com/dustinsea
或是直接访问: http://semocean.com

使用NDCG评估关键词推荐系统的相关性

对于传统推荐策略, 我们在验证其效果的时候, 一般会采用以下流程验证其实验效果:
  1. offline 的评测: 思路基本和传统机器学习的思路类似, 例如在推荐算法中我们直接使用AUC,F2等评估模型效果一样, 线下使用测试数据就能知道算法的初步效果。
  2. 用户调研实验: 该方式需要人的参与, 例如招一批人, 不告诉他们新老算法的界面或是使用的算法, 然后看用户的行为, 之后使用他们的最终交互, 或是选择判定算法/交互方案的优略。
  3. 线上实验: 最真实的尝尽, 例如小流量进行A/B test
具体关于评测后续会用专门的文章介绍,此处略去。 此处仅考虑一种特定的评估:关键词推荐系统的相关性评估。
因为baidu 关键词推荐系统是关键词的推荐,所以在很大程度上, 该推荐系统和传统的IR系统有着非常紧密的联系, 评估标准也较为相像。
对于一次推荐,用户进入百度关键词推荐系统交互界面: 关键词推荐系统会主动向用户push推荐的关键词,同时用户可以输入种子query进行查询:
如果将种子query看成是搜索引擎上的query,返回的关键词看成doc, 则问题就转换为搜索引擎的结果评估问题, 一种常用的方式为:NDCG(Normalized Discount Cummulative Gain)
CG
要介绍NDCG,我们首先介绍CG(Cummulative Gain), 其思想比较简单, 就是将相关性的分值累加后, 作为某个query/ 请求结果的分值。
reli 为处于位置i的推荐结果与query的相关性, p代表我们要考察前p个结果。
DCG
CG的一个缺点是CG没有考虑结果处于不同位置对结果的影响,例如我们总是希望相关性高的结果应排在前面,相关性低的结果排在靠前的位置会严重影响用户体验, 所以需要在CG的基础上引入位置影响因素,即DCG(Discounted Cummulative Gain)
即相同的相关性rel,排在对整次检索结果的正向影响,相较于放在后边更大。
NDCG
DCG仍然有其局限之处,即不同的query之间,很难进行横向的评估。例如, 我们评估百度关键词推荐系统, 或是搜索引擎的时候,都不可能仅使用一个query及相应结果进行评估, 一般都是是使用一批query及结果进行评估。 不同的query的评估分数就需要进行归一化。 也即NDCG。
例如我们定义:
其中DCG的定义如上, IDCG为特定query返回的最好结果, 即假设返回结果按照相关性排序, 最相关的结果放在最前面, 此序列的DCG为IDCG。因DCG的值介于 (0,IDCG],故NDCG的值介于(0,1]
具体操作方式
在具体操作中, 可以事先确定query和结果的相关系分级, 例如可以使用 0,1分别表示相关或不相关, 或是这是0~5分别表示严重不相关到非常相关。 相当于确定了rel值的范围。
之后对于每一个query的返回结果给定rel值,然后使用DCG的计算公式计计算出返回结果的DCG值。
使用根据sort后的rel值得序列计算IDCG值, 即可计算NDCG
参考文献:
百度关键词系统评估
 可关注微博: weibo.com/dustinsea
也可直接访问: http://semocean.com