Mapreduce实现矩阵乘法的算法思路

大数据计算中经常会遇到矩阵乘法计算问题,所以Mapreduce实现矩阵乘法是重要的基础知识,下文我尽量用通俗的语言描述该算法。

1.首先回顾矩阵乘法基础

矩阵A和B可以相乘的前提是,A的列数和B的行数相同,因为乘法结果的矩阵C中每一个元素Cij,是A的第i行和B的第j列做点积运算的结果,参见下图:

Mapreduce实现矩阵乘法的算法思路

2.进入正题

在了解了矩阵乘法规则后,我们打算采用分布式计算模型Mapreduce来完成这一过程。

MR过程是在Hadoop集群的多台机器上同时进行的,所以能MR化的计算必须是没有前后关系、相互独立的过程。通过分析上述矩阵乘法过程我们可以发现,其实C矩阵的每一个元素的计算过程都是相互独立的,比如C11和C21的计算不会相互影响,可以同时进行。

所以,我们的目标就转变为:通过MR计算每一个C矩阵元素Cij。

针对以上目标我们进一步分析,Cij其实就是A矩阵的第i行和B矩阵的第j列的点积,所以我们只要能最终将参与计算Cij的所有元素(A矩阵的第i行和B矩阵的第j列)都归到一组来参与计算就能算出Cij。这个所谓的“归到一组”,结合MR模型和矩阵乘法规则,其实就是Map将这些元素输出为相同的Key---C矩阵中元素的坐标,然后通过Shuffle就能把所有相同Key的元素输入到Reduce中,由Reduce来进行点积运算,得出该C元素最终的值。

OK,上面的思路都看明白后,我们回到输入数据,即A和B两个矩阵,我们只需要将矩阵中的每个元素处理一下(该过程需要在Map中进行),根据每一个元素即将参与哪些Cij的计算,为每一个元素打上(i,j)坐标即可,这样最终这些元素就会被shuffle到目标Cij的计算数据源分组中。

具体举例,A12,会参与到C11,C12的计算中;B22会参与到C12,C22的计算中。所以,我们从A和B的元素坐标,就完全可以得知它们即将参与计算的C元素的坐标。注意,这里是一对多的,每个A或者B的元素都会参与多个C元素的计算,如果不明白请再看第一遍矩阵乘法规则。

通过以上的分析,对于一个i行j列的A矩阵,和j行k列的B矩阵乘法:

我们将每个Aij元素处理为如下格式:

key=i,n(n=1,2,3...k)      value='a','j',aij

我们将每个Bjk处理为如下格式:

key= m,k(m=1,2,3...i)    value='b',

上面这个格式可能很多人看得痛苦,我就再唠叨两句,拿A12来举例,参见下图:

Mapreduce实现矩阵乘法的算法思路

A12最终会参与C11,C12的计算,所以我们处理A12时需将其处理为两个{key,value}对:

{(1,1),('a' , 2 , 2)}          /*  (1,1)是A12将参与计算的C11的坐标;'a'代表该数据来自A矩阵,因为A和B需要相乘,所以需要做一个标志位;头一个2代表这是计算C11时对应A向量的坐标,因为要知道A向量的第几个元素和B向量的第几个元素相乘;最后一个2就是当前元素的值  */

{(1,2),('a' , 2 , 2)}          /*  参考以上描述  */

这么解释都看不懂,就自己面壁去哈!

OK,Map过程结束,所有参与Cij的的A、B元素都shuffle到同一个Reduce了,Reduce的算法思路就简单了,通过标志位区分数据来源(A或B)创建数组,然后两个数组做点积即可。

Ubuntu 13.04上搭建Hadoop环境

Ubuntu 12.10 +Hadoop 1.2.1版本集群配置

Ubuntu上搭建Hadoop环境(单机模式+伪分布模式)

Ubuntu下Hadoop环境的配置

单机版搭建Hadoop环境图文教程详解

搭建Hadoop环境(在Winodws环境下用虚拟机虚拟两个Ubuntu系统进行搭建)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/b2cabcd3fbe853cfd769222dfede628a.html