基于MapReduce的SimRank++算法研究与实现[通俗易懂]

一、算法应用背景

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

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

理想情况下。赞助商搜索系统架构例如以下图所看到的。当一个新的查询q到达时，首先会利用查询中包括的关键词查询现有数据库中的各种数据，包括查询历史、广告数据和竞价数据。获得与查询q相关的广告，并依照竞拍价格排序规则将这些广告投放在查询结果的页面的相关位置。

实际应用中。一次竞价在概念上包含一个查询词或短语、一个广告和对应的竞标价格，表示当用户提交对应的查询词或短语时，广告主愿意付出不超过竞标价格的费用来使自己的广告得到展示和点击。在一个实际的赞助商搜索系统中。有很多查询没有足够数量的直接竞标广告，因而赞助商搜索系统应可以发现提交这些查询的用户可能感兴趣的非直接竞标广告。假设用户点击了系统推荐的这些广告。搜索引擎就行获得一定的收入，广告主也获得了一些顾客。

对于系统而言，挑战在于怎样匹配到与输入查询相关的而且用户可能会点击的广告。

有研究表明。互联网用户在使用网页搜索功能时，所提交的查询短语具有下面两个特点：(1) 查询短语较短。平均长度为2.2个单词，当中经常使用的查询短语的平均长度为1.7个单词；(2) 查询短语的使用频率呈幂率分布(Power Law)，近50%的查询短语每小时的使用频率在5次下面。

在进行广告检索时。往往因为查询短语较短，仅仅可以获得部分与查询相匹配的广告；同一时候，因为某些查询相应的直接竞标广告数据较少。数量不够在搜索结果页面中展示；另外，因为查询短语的使用频率呈幂率分布，往往会导致部分广告被频繁地检索到。

为了解决这些问题，赞助商搜索系统通常都会引入查询重写机制。相应的赞助商搜索系统架构通常分裂成两个部分，例如以下图所看到的。

前端接受输入查询q并产生一系列重写结果，这些重写结果与查询q之间具有一定的相关性。比方，对于查询“相机”。查询“数码相机”和“摄影”可能是实用的，由于用户可能会对与这些查询相关的广告感兴趣。同一时候，查询“电池”和原始查询也具有一定的相关性。虽然它们在文本上毫不相关，由于用户在购买相机的时候也会对相机的备用零件感兴趣。

原始查询和重写查询会被后端处理。与这些查询相关联的竞价广告会被检索出来。

把系统架构分裂成两个部分减少了系统的复杂性。

系统前端专注于查询重写。后端专注于处理高速变化的广告竞价数据、匹配相关内容和对检索结果排序。

眼下已有很多查询重写方法被提出和应用，如查询替代和查询扩展等。当中，优化后的SimRank算法以大量的历史PV数据为基础。利用加权的广告点击二部图(Bipartite Graph)结构信息，计算出的查询相关性具有较高的精度。可以有效地实现查询重写。

二、SimRank算法

很多应用领域都须要度量对象之间的相似性。

眼下主要有两大类相似性度量方法：(1) 基于内容(content-based)的特定领域(domain-specific)度量方法，如匹配文本相似度。计算项集合的重叠区域等；(2) 基于链接（对象间的关系）的方法，如PageRank、SimRank和PageSim等。

近期的研究表明。第二类方法度量出的对象间相似性更加符合人的直觉推断。

SimRank算法是一种用于衡量结构上下文中个体相似度的方法，其基本思想是：假设两个对象a和b分别与另外两个对象c和d关联，且已知c与d是相似的，则a与b也是相似的；而且随意节点与其自身拥有最大的相似度值为1。

SimRank算法的主要出发点是利用已有个体的相似度来推算其它与之有关联个体的相似度。

SimRank算法基于一个简单和直观的图论模型。它把对象和对象之间的关系建模为一个有向图G = (V, E)，当中V是有向图的节点集合，代表应用领域中的全部对象；E是有向图的边的集合，表示对象间的关系。对于图中的一个节点a，与其全部入边关联的邻节点集合(in-neighbors)记为I(a)，同一时候。其出边相应的邻节点集合(out-neighbors)集合记为O(a)。用s(a, b)表示对象a和对象b之间的相似性。其计算公式为：

从该计算公式能够看出，个体a, b的相似度取决于全部与a, b相连节点的相似度。式中c是一个常量衰减因子。

上述公式能够用矩阵的形式表示出来。如果S表示有向图G的SimRank分数矩阵。当中s(i,j)表示对象i和j之间的相似性分数。 P表示G的连接矩阵。当中P(i,j)表示从顶点i到顶点j的边数，则

用矩阵的符号表示，即为：

当中，矩阵W表示按列归一化的P矩阵。 I是n×n的单位矩阵。对于一个矩阵X，diag(X)表示获得由全部X的主对角线上的元素构成的向量。对于一个向量x，Diag(x)操作得到对应的对角矩阵，即x = diag(Diag(x))。

因为随意对象和自己的相似度值为1，所以加上项 ，其作用是把矩阵 的主对角线元素设为1。

把SimRank计算公式用矩阵乘法的形式表示。便于利用MapReduce分布式并行编程模型实现。从而可以大幅度提升算法的扩展能力，使之可以处理千万级甚至上亿级的数据规模。

三、SimRank++算法

在广告检索领域，用户在给定查询下点击广告链接的活动也能够抽象成一个典型的二部图，当中顶点分为两类：查询和广告；每条边表示在给定的查询下点击了相应的广告。

SimRank算法正是基于对广告点击二部图的分析处理来进行查询重写。依据SimRank算法的基本思想能够得出两个结论：(1) 关联到相似广告的查询是相似的。(2) 关联到相似查询的广告也是相似的。

原始的SimRank算法在该应用领域存在的一个问题就是在全然二部图中，算法计算出来的分数和人的直观是不一致的，一个详细的样例例如以下图所看到的，图中两个全然二部图的相似性分数依据原始SimRank算法计算的结果例如以下表所看到的，计算时採用的衰减因子为0.8。

从图中我们能够看出“平板电脑-智能手机”有很多其它的证据（很多其它的共同连接对象）表明它们之间的相似性更高，然而，虽然“平板电脑-智能手机”的相似性分数随着迭代的进行不停地添加，原始的SimRank算法在初始的7轮迭代中计算出来的“平板电脑-智能手机”相似性分数总是低于“数码相机-智能手机”的相似性分数。

一个可行的校正方法是对原始的SimRank算法的迭代公式进行改动。加入一个证据(evidence)因子。定义为：

当中，E(q)表示和对象q相关联的全部对象， |E(q)∩E(q’)|表示节点q和节点q’共同拥有邻居的数目。可见|E(q)∩E(q’)|和evidence(q, q’)呈正比关系， |E(q)∩E(q’)|值越大。evidence(q, q’) 越接近于1。对应地，新的计算公式变为：

利用新公式又一次计算上述问题的相似性分数，结果例如以下表。能够看到新的方法在第二轮迭代时，“平板电脑-智能手机”的相似性分数就高于“数码相机-智能手机”的相似性分数。

还有一方面。原始的SimRank算法没有考虑边的权值。

在下图(a)所看到的的情况下，“计算机-电视机”的相似度显然比“收音机-电视机”的相似度高，由于前两个查询点击同一个广告的次数同样，而后两个查询点击同一个广告的次数相差非常大。

然而，由于原始的SimRank算法不考虑广告的点击次数，仅仅考虑是不是点击了同样的广告，因而其计算出来的“计算机-电视机”的相似度和“收音机-电视机”的相似度同样。同样。在下图(b)所看到的的情况下，“计算机-电视机”的相似度依旧应该比“收音机-电视机”的相似度高，因而虽然每一个查询对都以同样的次数点击了同一个广告。可是前一个查询对点击的次数在数量上要比第二个查询对要多，很多其它的点击次数代表了两个查询之间更高的相似度。

原始的SimRank算法再一次不能非常好地处理这样的情况，它仅仅是简单地忽略了不同查询下的广告点击次数，因而计算出的相似性分数值不够精确。

考虑二部图边的权值，能够改进SimRank算法的计算结果。

考虑权值时的两个基本出发点是：假设两个节点相应的权值的方差相等，那么权值较大的节点对之间的相似性较高；假设两个节点相应的权值的方差不相等，那么方差较小而且权值较大的节点对之间的相似性较高。

引入一个新的函数p(·,·)表示二部图中节点间的转移概率：

从而，新的算法迭代公式例如以下：

当中，q和q’表示随意两个查询，a和a’表示随意两个广告，因子W(q,i)和W(a,i)的定义例如以下：

对SimRank算法进行上述两个方面的扩展，即通过“权值”和“证据值”对原始计算结果进行校正，所得的新算法就是SimRank++算法。SimRank++算法由Antonellis等人于2008年专门针对赞助商广告检索领域的查询重写应用提出的。

类似于SimRank算法。SimRank++算法也能够写成矩阵运算的形式，例如以下式所看到的。

当中，矩阵P是二部图中节点间的转移概率矩阵。

SimRank++算法针对查询重写的详细应用。能够非常好地衡量不同查询关键词之间的相似性，通过使用雅虎搜索的数据进行实验。证实了SimRank++算法能够为用户提供很多其它感兴趣的查询结果，添加广告的点击率，加强系统的互动体验，提升搜索服务的质量。

用矩阵运算表示的SimRank++算法例如以下：

‘’‘
输入: 转移概率矩阵P。证据值矩阵V，衰减因子c，迭代步数k
输出: 相似性分数矩阵S
For i = 1:k, do
temp = c PT S P
S = temp + I – Diag(diag(temp))
End
S = V .* S
’‘’

因为实际的互联网广告检索系统包括了数以亿计查询和广告，数据规模很庞大。导致对应的广告点击二部图也很巨大且难以切割。

因此，若要在实际应用中利用SimRank++算法重写查询，须要一种提升算法可扩展性的方法。通过MapReduce并行计算模型框架能够有效地提高算法的扩展能力。为避免文章过于冗长。详细的实现细节在下一篇文章中给出，敬请期待。