利用Simrank算法进行Query Rewriting

搜索引擎的检索结果页下方一般会提示多个相似的搜索关键词，这些词可以被看作查询关键词query的rewriting。在计算广告中，当某一个query没有对应的bid phase出价广告，或者该query对应的bid phase较少的时候，可以利用query rewriting获取相似query对应的广告进行显示，以期望获得更多的click。相似query的确定可以利用用户session中的搜索关键词上下文，但此方法需要确定query的边界，例如用户搜索过程中可能会突然跳到一个完全不相干的搜索，然后又跳回来。或者利用传统的文本相似度匹配，而由于query一般都很短，传统相似度匹配的语料也不足。

Simrank

Simrank算法是一种用于衡量结构上下文中个体相似度的方法，直观上的含义是利用已有个体的相似度来推算其他与有关联个体的相似度。形式化的定义如下：

有向图G={V,E}中，节点a的入边集合记为I(a)，而出边集合记为O(a)，则两个节点a,b(a != b时)相似度s(a,b)按照如下公式计算，其含义是个体a,b的相似度取决于所有与a,b相连节点的相似度，s(a,b)∈[0,1]；当a=b时，s(a,b)=1；如果a != b，且只有同一个入节点c，我们不希望从c计算得到的s(a,b)也为1，因此c做为衰减因子，取值是[0,1]，即s(a,b) = C。

对于二分图G’ = (V1,V2,E)，对于任意的(A,a)∈E，有A∈V1和a∈V2，则所有V1集合中的节点相似度按照出度O(A)计算。V2集合中的节点相似度则按照上述公式，利用入度I(a)计算。

在搜索广告中，把query和ad看作节点，当用户搜索某个查询关键词q时，点击了广告a，则建立q至a的一条边，这样构成一个由query和ad组成的二分图G=(V,E)，其中V=Vq∪Va，任何边e=(q,a,w)，q∈Vq并且a∈Va，可以利用simrank算法来求query之间的相似度。E(q)表示q的边，N(q)表示E(q)的个数：

按照上述算法，我们看以下的例子，假设C等于0.8，则利用上述公式计算出的sim(pc,camera)的相似度在前5次迭代中都大于sim(camera,digital camera)，但从直观上说，由于camera和digital camera的共同邻居较多，应该具备更高的相似度，而simrank的结果是反直观的。针对上述问题，Antonellis等人在VLDB 08上提出了Simrank在计算广告方面的改进——Simrank++。

Simrank++

Simrank++的改进主要包括两点，一是针对上面的问题对sim(q,q`)进行调整，如果两个节点共同节点{E(q)∩E(q`)}越多，则给予这两个节点相似度更高的权值。

按照上述调整后，上面示例的计算结果如下。同时Antonellis等人也证明了，如果迭代的次数足够多，对于未调整前的simrank，最终sim(pc,camera)会和sim(camera, digital camera)相等，但实际使用中肯定无法计算那么多次迭代。

另外一个改进就是对Simrank中的边进行加权，权值的常用设定方式包括query和ad的对应的显示次数、点击次数以及点击率CTR等。但具体也需要考量，采用显示次数作为权值会显得用户反馈不足，可信度不够；采用点击次数，即使query和ad的关联性不强，则显示次数多的被点击次数也多；而CTR则会受广告显示位置的影响，关联度不高但位置第一的ad获得的CTR也可能相对较高，并且对于相同的CTR，显示次数为10次和10000次时，CTR的可信度也不同。

例如，对于上图的两种情况，如果不考虑边的权值，即使加上evidence调整，sim(flower,orchids)的计算结果也是一样的。但直观上可以看出左边的相似度应该高于右边的相似度，Antonellis等人给出了以下方法，按照节点所有边的权值方差进行相似度调整，并对权值均一化。

定义W(a)为所有与a相邻边的权值组成的集合，即{w(i,a),w(j,a)….w(n,a)}，variance(a)则为W(a)的方差，计算如下

由Simrank计算的图中两个节点的相似度，也可以用Random Walk模型来解释，即两个节点a,b的相似度可以认为是同时从a,b节点出发，随机选择下一步的邻接点，直到相遇在某一点的期望距离(Expected Meeting Distance)，期望距离越短则相似度越高。

按照Simrank的原理，感觉Simrank有点类似PageRank的思想，都是利用邻居节点来进行估算。Simrank算法应该也可以用于在推荐系统中计算person,item的相似度从而进行推荐。

参考资料：

SimRank: A Measure of Structural-Context Similarity

Simrank++: Query rewriting through link analysis of the click graph