在移动互联网时代，电商领域的O2O服务检索（检索目标为服务商家和优惠券等）和在线商品检索必然存在许多不同点。比如，O2O服务检索更强调“移动”的特点，有一定的地域和距离的限制。同时，检索需求也跟用户所处的“情境”有很大的关系，因而在不同“情境”下用户对检索结果的期望也有所不同。O2O场景下，一个好的检索系统必然要考虑到这些特点，检索结果要能够做到对用户所在地域和所处“情境”的自适应调整。相比传统的电商商品检索，O2O服务检索对检索系统的召回和排序算法都提出了更高的要求。

尽管如此，O2O服务检索和在线商品检索也存在很多共性，比如检索结果的相关性都是衡量用户满意度和检索系统是否成功的重要指标之一。就相关性度量算法而言，传统检索系统存在的问题在O2O服务检索系统中依然存在，比如文本的“mismatch”问题、检索结果的主题转义问题等。O2O服务检索相关性的另一个挑战是数据质量的问题。由于O2O行业还是一个比较年轻同时又竞争激烈的行业，检索系统对O2O服务的数据录入和校验相对来说比较宽松，加上在运营数据方面投入的资源相对较少，导致O2O垂直搜索引擎索引的文档数据质量严重不如传统电商的商品数据。与传统电商相比，O2O搜索服务要求对数据更多的结构化表示，比如每个O2O服务必然要关联一个POI，同时每个POI必然要关联地址、品牌、经纬度和所在城市等数据，因而O2O数据质量更难把控，数据的运维也需要很多的成本。在我们的系统中，发现的跟数据质量有关的问题包括：服务所在城市的信息错误、服务所关联的POI信息错误、服务挂载到不相关的类目等等。甚至O2O服务的类目体系都存在很多不合理的方面，比如存在很相似的类目，导致服务本身不知道到底应该挂载在哪个类目的情况，另外，不同类目下商品/服务数量不均衡也是一个问题。

所谓学习问题，是指观察由n个样本组成的集合，并根据这些数据来预测未知数据的性质。

学习任务（一个二分类问题）：

区分一个普通的互联网检索Query是否具有某个垂直领域的意图。假设现在有一个O2O领域的垂直搜索引擎，专门为用户提供团购、优惠券的检索；同时存在一个通用的搜索引擎，比如百度，通用搜索引擎希望能够识别出一个Query是否具有O2O检索意图，如果有则调用O2O垂直搜索引擎，获取结果作为通用搜索引擎的结果补充。

我们的目的是学习出一个分类器（classifier），分类器可以理解为一个函数，其输入为一个Query，输出为0（表示该Query不具有o2o意图）或1（表示该Query具有o2o意图）。

特征提取：

要完成这样一个学习任务，首先我们必须找出决定一个Query是否具有O2O意图的影响因素，这些影响因素称之为特征（feature）。特征的好坏很大程度上决定了分类器的效果。在机器学习领域我们都知道特征比模型（学习算法）更重要。（顺便说一下，工业界的人都是这么认为的，学术界的人可能不以为然，他们整天捣鼓算法，发出来的文章大部分都没法在实际中应用。）举个例子，如果我们的特征选得很好，可能我们用简单的规则就能判断出最终的结果，甚至不需要模型。比如，要判断一个人是男还是女（人类当然很好判断，一看就知道，这里我们假设由计算机来完成这个任务，计算机有很多传感器（摄像头、体重器等等）可以采集到各种数据），我们可以找到很多特征：身高、体重、皮肤颜色、头发长度等等。因为根据统计我们知道男人一般比女人重，比女人高，皮肤比女人黑，头发比女人短；所以这些特征都有一定的区分度，但是总有反例存在。我们用最好的算法可能准确率也达不到100%。假设计算机还能够读取人的身份证号码，那么我们可能获得一个更强的特征：身份证号码的倒数第二位是否是偶数。根据身份证编码规则，我们知道男性的身份证号码的倒数第二位是奇数，女生是偶数。因此，有了这个特征其他的特征都不需要了，而且我们的分类器也很简单，不需要复杂的算法。

言归正传，对于O2O Query意图识别这一学习任务，我们可以用的特征可能有：Query在垂直引擎里能够检索到的结果数量、Query在垂直引擎里能够检索到的结果的类目困惑度（perplexity）（检索结果的类目越集中说明其意图越强）、Query能否预测到特征的O2O商品类目、Query是否包含O2O产品词或品牌词、Query在垂直引擎的历史展现次数（PV)和点击率(ctr)、Query在垂直引擎的检索结果相关性等等。

字符编码简介

1. ASCII码

在计算机内部，所有的信息最终都表示为一个二进制的字符串。每一个二进制位（bit）有0和1两种状态，因此八个二进制位就可以组合出256种状态，这被称为一个字节（byte）。也就是说，一个字节一共可以用来表示256种不同的状态，每一个状态对应一个符号，就是256个符号，从0000000到11111111。

上个世纪60年代，美国制定了一套字符编码，对英语字符与二进制位之间的关系，做了统一规定。这被称为ASCII码，一直沿用至今。
ASCII码一共规定了128个字符的编码，比如空格“SPACE”是32（二进制00100000），大写的字母A是65（二进制01000001）。这128个符号（包括32个不能打印出来的控制符号），只占用了一个字节的后面7位，最前面的1位统一规定为0。

2. Unicode

英语用128个符号编码就够了，但是用来表示其他语言，128个符号是不够的。因此，很多欧洲国家发明了很多非ASCII码，同样用一个字节，用最高位为1的区间（既128~255）来扩展原来的ASCII码，其中一种比较有名的就是IBM字符编码。这样一来，这些欧洲国家使用的编码体系，可以表示最多256个符号。但是，这里又出现了新的问题。不同的国家有不同的字母，因此，哪怕它们都使用256个符号的编码方式，代表的字母却不一样。比如，130在法语编码中代表了é，在希伯来语编码中却代表了字母Gimel (ג)，在俄语编码中又会代表另一个符号。但是不管怎样，所有这些编码方式中，0—127表示的符号是一样的，不一样的只是128—255的这一段。

背景

本文主要针对广告检索领域的查询重写应用，根据查询-广告点击二部图，在MapReduce框架上实现SimRank++算法，关于SimRank++算法的背景和原理请参看前一篇文章《SimRank++算法原理深入解析》。关于权值转移概率矩阵的实现请参看另一位文章《用hadoop实现SimRank++算法(1)----权值转移矩阵的计算》。关于算法的迭代计算过程请参考《用hadoop实现SimRank++算法(2)---- 算法迭代过程》。

背景

本文主要针对广告检索领域的查询重写应用，根据查询-广告点击二部图，在MapReduce框架上实现SimRank++算法，关于SimRank++算法的背景和原理请参看前一篇文章《SimRank++算法原理解析》。关于权值转移概率矩阵的实现请参看另一位文章《用hadoop实现SimRank++算法(1)----权值转移矩阵的计算》。

准备工作

在广告检索系统的查询重写应用中，对象分为两种类型：查询和广告。对象间的关系为点击关系。关系图为二部图，图中的每一条边表示在相应的查询下点击了对应的广告，边的权值为点击次数。下图表示由3个查询和2个广告构成的完全二部图，图中略去了边的权值。

本文主要针对广告检索领域的查询重写应用，根据查询-广告点击二部图，在MapReduce框架上实现SimRank++算法，关于SimRank++算法的背景和原理请参看前一篇文章《SimRank++算法原理解析》。关于算法迭代过程的实现请参看另一位文章《用hadoop实现SimRank++算法(1)----权值转移矩阵的计算》。

SimRank++的矩阵形式的计算公式为：

算法主要步骤如下：

• Step1: 计算权值矩阵，并获取最大Query编号和最大广告编号；
• Step2: 以Step1的输出作为输入，迭代计算SimRank相似度。
• Step3: 计算证据矩阵，并用计算结果修正Step2的输出，计算出最终的经过归一化的相似度分数。
• Step4: 把Step3的输出转化为固定的格式，得到最终的相似度分数结果。

其中Step2迭代计算SimRank相似度分数比较复杂，由一系列的MapReduce作业组成。本文主要关注Step1，即计算权值矩阵的计算。Step2~4将在后续的文章中给出。

一、算法应用背景

计算广告学(Computational Advertising)是一门广告营销科学，以追求广告投放的收益最大化为目标，重点解决用户与广告匹配的相关性和广告的竞价模型问题，涉及到自然语言处理、数据挖掘以及竞价营销、创意设计等诸多学科的融合。计算广告是根据给定的用户和网页内容，通过计算得到与之最匹配的广告并进行精准定向投放的一种广告投放机制，其目的是为用户提供最易于接受的优质广告；对于广告主的广告投放效果负责；综合用户和广告主之间的关系，进行广告竞价产生最大收益。

对于用户而言，计算广告存在赞助商搜索广告、浏览页面投放广告、社区人群广告等多种形式。其中，赞助商搜索(Sponsored Search)是一种特定的广告投放形式，其广告投放的目标位置是搜索引擎所返回的搜索结果页面。与其他广告投放形式不同，在赞助商搜索的场景中，搜索引擎既充当了网络媒体也充当了广告网络，因此赞助商搜索便成为广告主、用户和搜索引擎三方的一个博弈过程，博弈的目标是要使三方的总收益(Payoff)最大。

首先推荐李航的《统计机器学习》这本书，这个实现就是按照书上的算法来的。Python 用的是最新的3.3版的，和2.x不兼容，运行的时候需要注意。