基于单步的Map-Reduce的矩阵乘法

基于单步的Map-Reduce的矩阵乘法

矩阵的乘法只有在第一个矩阵的列数(column)和第二个矩阵的行数(row)相同时才有定义。一般单指矩阵乘积时，指的便是一般矩阵乘积。若A为i×r矩阵，B为r×j矩阵，则他们的乘积AB(有时记做A · B)会是一个i×j矩阵。其乘积矩阵的元素如下面式子得出:

书中提到的对矩阵乘法的MapReduce实现方法是：

Map函数：对于矩阵M的每个元素M[i,j]，产生一系列的键值对(i,k)->(M,j, M[i,j]),其中k=1,2…，直到矩阵N的列数。同样，对于矩阵N的每个元素N[j,k]，产生一系列的键值对(i,k)->(N,j,N[j,k]),其中i=1,2…，直到矩阵M的行数。

Reduce函数：根据MR的原理，相同键i,k的数据会发送个同一个 reduce。如果M为2*2矩阵，N为2×3矩阵，reduce函数需要处理的数据为：

（1,1）->[(M,1, M[1,1])、(M,2, M[1,2])、(N,1, N[1,1])、(N,2, N[2,1])]，

（1,2）->[(M,1, M[1,1])、(M,2, M[1,2])、(N,1, N[1,2])、(N,2, N[2,2])]，

（1,3）->[(M,1, M[1,1])、(M,2, M[1,2])、(N,1, N[1,3])、(N,2, N[2,3])],

（2,1）->[(M,1, M[2,1])、(M,2, M[2,2])、(N,1, N[1,1])、(N,2, N[2,1])]，

（2,2）->[(M,1, M[2,1])、(M,2, M[2,2])、(N,1, N[1,2])、(N,2, N[2,2])]，

（2,3）->[(M,1, M[2,1])、(M,2, M[2,2])、(N,1, N[1,3])、(N,2, N[2,3])]。

这样只要将所有(M,j, M[i,j])和(N,j, N[j,k])分别按照j值排序并放在不同的两个列表里面。将这个列表的第j个元素M[i,j]个N[j,k]相乘，然后将这些积相加，最后积的和与键(i,k)组对作为reduce函数的输出。对于上面的例子reduce的输出就是：

（1,1）->（M[1,1]* N[1,1]+ M[1,2]* N[2,1]）

（1,2）->（M[1,1]* N[1,2]+ M[1,2]* N[2,2]）

（1,3）->（M[1,1]* N[1,3]+ M[1,2]* N[2,3]）

（2,1）->（M[2,1]* N[2,1]+ M[2,2]* N[2,1]）

（2,2）->（M[2,1]* N[1,2]+ M[2,2]* N[2,2]）

（2,3）->（M[2,1]* N[1,3]+ M[2,2]* N[2,3]）

下面是MapReduce的实现步骤：

(1).构造矩阵M：300*150；矩阵N：150*500。两矩阵的值放在一个M.data文件中，每行的格式为：文件标识#行坐标#列坐标#坐标值。

(2).基于上面的方法编写Map函数和Reduce函数。代码详见：

(3).将运行的结果文件copy到本地,并使用check.py对结果中元素[10,95]的正确性进行验证。

参考文献：

1.《大数据—互联网大规模数据挖掘与分布式处理》

2.http://blog.sina.com.cn/s/blog_62186b460101ai1x.html

秒客网