阿里云-云小站(无限量代金券发放中)
【腾讯云】云服务器、云数据库、COS、CDN、短信等热卖云产品特惠抢购

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

139次阅读
没有评论

共计 1865 个字符,预计需要花费 5 分钟才能阅读完成。

大数据计算中经常会遇到矩阵乘法计算问题,所以 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 环境 http://www.linuxidc.com/Linux/2013-06/86106.htm

Ubuntu 12.10 +Hadoop 1.2.1 版本集群配置 http://www.linuxidc.com/Linux/2013-09/90600.htm

Ubuntu 上搭建 Hadoop 环境(单机模式 + 伪分布模式)http://www.linuxidc.com/Linux/2013-01/77681.htm

Ubuntu 下 Hadoop 环境的配置 http://www.linuxidc.com/Linux/2012-11/74539.htm

单机版搭建 Hadoop 环境图文教程详解 http://www.linuxidc.com/Linux/2012-02/53927.htm

搭建 Hadoop 环境(在 Winodws 环境下用虚拟机虚拟两个 Ubuntu 系统进行搭建)http://www.linuxidc.com/Linux/2011-12/48894.htm

更多 Hadoop 相关信息见Hadoop 专题页面 http://www.linuxidc.com/topicnews.aspx?tid=13

正文完
星哥说事-微信公众号
post-qrcode
 0
星锅
版权声明:本站原创文章,由 星锅 于2022-01-20发表,共计1865字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
【腾讯云】推广者专属福利,新客户无门槛领取总价值高达2860元代金券,每种代金券限量500张,先到先得。
阿里云-最新活动爆款每日限量供应
评论(没有评论)
验证码
【腾讯云】云服务器、云数据库、COS、CDN、短信等云产品特惠热卖中