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

image

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。

image

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

image

在搜索广告中,把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)的个数:

image

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

image

阅读全文…

, ,