用hadoop实现SimRank++算法(1)----权值转移矩阵的计算

本文主要针对广告检索领域的查询重写应用，根据查询-广告点击二部图，在mapreduce框架上实现simrank++算法，关于simrank++算法的背景和原理请参看前一篇文章《》。

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

算法主要步骤如下：

step1: 计算权值矩阵，并获取最大query编号和最大广告编号；

step2: 以step1的输出作为输入，迭代计算simrank相似度。

step3: 计算证据矩阵，并用计算结果修正step2的输出，计算出最终的经过归一化的相似度分数。

step4: 把step3的输出转化为固定的格式，得到最终的相似度分数结果。

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

为了简单起见，在我们的实现中，用点击次数作为边的权值。一个更好的选择是用广告点击率(click through rate, ctr)作为权值，理由如下：某个广告在q1下展示10000次，点击100次（ctr为0.01）；在q2下展示1000次，点击90次（ctr为0.09）；在q3下展示1000次，点击100次（ctr为0.1）；显然q3和q2的相似度要比q3和q1的相似度要高，然而如果只考虑点击次数，那么算法会认为q3和q1的相似度比q3和q2的高。

期待的输入数据的文件格式：

1. query和广告的点击关系数据文件（以下记为qas文件）的每一行的格式如下：

qas ^a queryid { ^a adid ^b clicknum}

其中，{ }表示内部的内容可以重复1次或多次，但至少一次；“qas”的标识字符串；‘^a’是ascii码为1的不可见字符；‘^b’是ascii码为2的不可见字符。

2. 广告和query的点击关系数据文件（以下记为aqs文件）的每一行的格式如下：

aqs ^a adid { ^a queryid ^b clicknum}

其中，{ }表示内部的内容可以重复1次或多次，但至少一次；“aqs”的标识字符串；‘^a’是ascii码为1的不可见字符；‘^b’是ascii码为2的不可见字符。

上图所示的查询和广告之间的点击关系对应的文件格式如下：

权值矩阵元素的计算公式为：

可以看出， variance(a)的计算需要用到aqs文件， normalize_weight(q,a)的计算需要用到qas文件； variance(q)的计算需要用到qas文件， normalize(q,a)的计算需要用到aqs文件。从而，在计算w(a,q) 和 w(q,a)时都要用到aqs文件和qas文件，这使得mapreduce算法的设计比较困难。

考虑前面所述的一个简单例子。”mapper”任务在处理qas文件时会计算出如下所示的内容。

”mapper”任务在处理aqs文件时会计算出如下所示的内容。

在计算w(q,a)时需要使用到variance(a)和normalizedweight(q, a)；在计算w(a,q)时需要使用到variance(q)和normalizedweight(a, q)。因此，根据以上分析，对于一个特定的q和a，需要把map任务的输出中的variance(a)和normalizedweight(q, a)”shuffle”到同一个”reduce”节点，由该”reduce”节点计算出w(q,a)；同理，需要把”map”任务的输出中的variance(q)和normalizedweight(a,

q) ”shuffle”到同一个”reduce”节点，由该”reduce”节点计算出w(a,q)。

另外，可以看出，在计算w(q1,a), w(q2,a),……. 时都需要用到variance(a)，因此我们希望计算 的“reduce”节点接受到的值列表中variance(a)项排在所有normalized_weight(q, a)项之前。mapreduce框架在记录到达”reducer”之前按键对记录排序，但键所对应的值并没有被排序。由于值来自不同的map任务，所以在多次运行程序时，值的出现顺序并不固定，导致每次运行作业的时间会各有不同。一般来说，大多数mapreduce程序无需考虑值在”reduce”函数中出现的顺序。但是，像我们这里碰到的情况一样，有时确实需要通过对键进行排序和分组等以实现对值的排序。通过mapreduce框架辅助对记录值排序的方法总结如下：

(1) 定义包括自然键和自然值的组合键。

(2) 键的comparator根据组合键对记录进行排序，即同时利用自然键和自然值进行排序。

(3) 针对组合键partitioner和分组comparator在进行分区和分组时均只考虑自然键。

基于以上分析，计算权值矩阵的mapreduce任务需要小心地设计”map”任务输出的key和value的数据结构以及”partitioner”函数。

(1) map任务输出的键(key)的数据结构

键(key)由一个三元组构成：< type, index1, index2 >

type用于标识index1是广告的编号(0)，还是query的编号(1)；当type = 0时，对应的值(value)表示normalizedweight(q,a)，其中q等于index1，a等于index2；当type = 1时，value表示normalizedweight(a,q)，其中a等于index1，q等于index2；

另外，当index2 = -1时，表示对应的值为方差（variance(index1)）。设为-1是为了保证同一组key对应的值列表中方差项排在第一个。

键(key)的三个元素都参与comparator的比较。

(2) map任务输出的值(value)的数据结构

值(value)有一个二元组构成：< index, value >，其中index总是等于对应的键的第三个元素index2。这里看似冗余，其实不然。因为我们在利用mapreduce框架辅助排序时，分组函数(groupcomparator)只比较key的前两个元素，忽略key的第三个元素，这样只有key的前两个元素的值相同，那么他们的值将合并到同一个列表中，有唯一的一个“reduce”函数处理。mapreduce框架在默认情况下只会把key完全相同值合并到同一个列表中。因此我们需要设置outputvaluegroupingcomparator为我们自定义的groupcomparator。可以利用如下的语句设置：

(3) 分区函数

分区函数控制”map”任务的每个输出记录由哪一个”reduce”节点处理。在权值矩阵的计算作业中该函数的地位特别重要。根据上一小节的分析和辅助排序的要求，分区函数只考虑键的前两个元素。我们把”reduce”节点分成两部分，一部分计算 ，另外一部分计算 。”partition”函数的代码如下。

(4) “map”函数和”reduce”函数

“map”函数和”reduce”函数并行地处理主要的工作。其中”map”函数读入qas文件，计算出variance(q)和normalizedweight(a, q)；读入aqs文件，输出variance(a)和normalizedweight(q, a)。同时为了以后的计算方便，”map”函数还记录下最大的query编号和最大的ad编号。由于多个”map”函数之间不能相互通信，为了得到全局的最大query编号和ad编号，每个map函数结束的时候在一个指定的hdfs目录下新建一个以本函数统计出的当前最大编号为文件名的空文件，前提条件是此时该指定目录下还没有更大编号的文件存在。

“reduce”函数比较简单，直接根据公式计算出最终的权值就可以了。”reduce”输出的key是一个二元组，表示权值矩阵的行号和列号。输出的值为相应的权值。由于我们在同一个作业中同时计算了query-ad的权值矩阵和ad-query的权值矩阵，这两个矩阵在后面的simrank实现过程中需要单独使用，因此必须要把两种的输出区分开来。我们使用multipleoutputs类定义了两个数据收集对象，这两个数据收集对象输出的文件名有不同的前缀。

“mapper”和”reducer”的伪代码如下。

计算权值矩阵的”map”函数

计算权值矩阵的”reduce”函数