矩陣乘法
我們先來(lái)補(bǔ)充一下矩陣乘法的數(shù)學(xué)知識(shí)：
- 矩陣乘法的意義: 對(duì)一個(gè)矩陣進(jìn)行左乘一個(gè)矩陣的運(yùn)算豆励，相當(dāng)于對(duì)該矩陣的每一列元素做線性變換洼滚；對(duì)一個(gè)矩陣進(jìn)行右乘矩陣運(yùn)算相當(dāng)于對(duì)該矩陣的行進(jìn)行線性變換。
- 矩陣乘法的計(jì)算公式： 若矩陣A為m * n的矩陣皮璧，矩陣B為n * p的矩陣舟扎，那么兩矩陣相乘的公式如下：
用向量來(lái)解釋為下圖：
分布式計(jì)算
- 概念：把需要進(jìn)行大量計(jì)算的工程數(shù)據(jù)分區(qū)成小塊，由多臺(tái)計(jì)算機(jī)分別計(jì)算悴务，再上傳運(yùn)算結(jié)果后睹限，將結(jié)果統(tǒng)一合并得出數(shù)據(jù)結(jié)論的科學(xué)
- 實(shí)現(xiàn)工具：目前最流行的分布式處理平臺(tái)是Hadoop，其流程大致如下圖：
數(shù)據(jù)存儲(chǔ)在HDFS上通過(guò)指令分發(fā)到多個(gè)Mapper（多個(gè)計(jì)算機(jī)）上進(jìn)行處理讯檐，隨后Mapper輸出的結(jié)果（key - value）按照key進(jìn)行shuffle最后傳遞到不同的reduce（統(tǒng)一合并）統(tǒng)計(jì)處理結(jié)果輸出羡疗。
關(guān)鍵點(diǎn)：首先我們要將龐大的問(wèn)題拆分成運(yùn)算規(guī)則相同的子問(wèn)題；隨后通過(guò)設(shè)定Mapper輸出的key將該合并的問(wèn)題分類(lèi)到同一個(gè)reduce下實(shí)現(xiàn)分布式計(jì)算别洪。
稀疏矩陣的存儲(chǔ)方式
- Coordinate(COO)
![COO存儲(chǔ)方式.png]
如上圖所示叨恨。我們對(duì)于矩陣的存儲(chǔ)我們需要直到三個(gè)值即可：columnid, rowid, value.于是對(duì)于一個(gè)稀疏矩陣我們可以存儲(chǔ)為三行，三個(gè)值對(duì)應(yīng)一個(gè)三元組存儲(chǔ)為一列挖垛。如右圖所示痒钝。對(duì)于等于0的元素我們可以選擇不存儲(chǔ)。因?yàn)樵谧鼍仃囘\(yùn)算時(shí)痢毒，如上面運(yùn)算公式可以看出送矩，這些元素對(duì)結(jié)果并沒(méi)有什么貢獻(xiàn)。這樣我們對(duì)于矩陣的存儲(chǔ)可以變?yōu)镺(3K)的空間復(fù)雜度哪替。（K為非零元素的個(gè)數(shù)）,對(duì)于上面的存儲(chǔ)方式栋荸，我們可以進(jìn)一步對(duì)行索引進(jìn)行壓縮。就是下面所說(shuō)的行壓縮稀疏存儲(chǔ)。
- Compressed Sparse Row (CSR)
![CSR存儲(chǔ).png]
如上圖所示蒸其，這時(shí)對(duì)行壓縮優(yōu)化的一個(gè)存儲(chǔ)方式敏释。其中三元組變?yōu)椋盒衅屏俊⒘兴饕alue钥顽。
行向量偏移量：每一行第一個(gè)非零元素在所有非零元素中的索引。也就是將所有的非零元素按矩陣的順序排列在數(shù)組中后的索引靠汁。如左圖：所有非零元素組成數(shù)組:[1,7,2,8,5,3,9,6,4],所以每行的偏移量就是該行第一個(gè)元素在該數(shù)組中的索引蜂大。(1,2,5,6) --(0,2,4,7),最后加上所有非零元素個(gè)數(shù)。
可行性分析： 我們所要做的無(wú)非是用上述三個(gè)數(shù)組的信息是否可以恢復(fù)出原有的矩陣蝶怔。我們發(fā)現(xiàn)有幾個(gè)偏移量就有幾行奶浦。并且每個(gè)元素的列是記錄了的，所以可以恢復(fù)出原有的矩陣踢星。
空間復(fù)雜度: O(2K + m), m為矩陣行數(shù)
進(jìn)一步優(yōu)化：用兩個(gè)數(shù)組來(lái)表示一個(gè)矩陣澳叉，如下面的方法
- ELLPACK (ELL)
![ELL存儲(chǔ).png]
該方法只是在CSR上做了進(jìn)一步改進(jìn)，因?yàn)槲覀儼l(fā)現(xiàn)只要記錄了非零元素的列沐悦，我們只需直到非零元素在第幾行就可以成洗。于是我們將每一行的非零元素末尾加上 #來(lái)表示該位置為這一行的結(jié)尾。于是我們可以在上面的CSR中拿出列和值的數(shù)組藏否，在其中插入#來(lái)區(qū)分每一行即可瓶殃，上圖矩陣記錄如下：
column id [0,1,#,1,2,#,0,2,3,#,1,3]
value [1,7,#,2,8,#,5,3,9,#,6,4]
通過(guò)#的個(gè)數(shù)，我們可以直到該#為第幾行的結(jié)尾副签，從而直到上一個(gè)#之前的元素是第幾行元素遥椿。
空間復(fù)雜度：降到了二維的存儲(chǔ)，并且可以格式很整齊淆储，對(duì)后面分布式計(jì)算有很大的幫助冠场。
矩陣乘法的分布式計(jì)算
-
可行性：我們從矩陣乘法的公式來(lái)看：
A * B.png
我們發(fā)現(xiàn)最終乘機(jī)得到的矩陣是一個(gè)m x p的矩陣，相當(dāng)于每個(gè)元素都要進(jìn)行上述公式的運(yùn)算 O(n); 求出整個(gè)矩陣復(fù)雜度就為O( n m p) = n O(m p); 我們思考可以把這個(gè)問(wèn)題拆分成n個(gè)子問(wèn)題遏考，每個(gè)子問(wèn)題需要求出m * p 個(gè)值慈鸠，而這里的每一個(gè)值都是對(duì)最終結(jié)果對(duì)應(yīng)位置的貢獻(xiàn)蓝谨，也就是我們把上面加法的每一個(gè)元素放在一個(gè)map里去處理灌具，以i#j作為key， 以![ ]為value輸出作為索引為(i, j)的元素貢獻(xiàn)值譬巫。隨后在reduce中進(jìn)對(duì)相同key的value加和作為最終結(jié)果中（i, j）的結(jié)果咖楣。這樣我們就實(shí)現(xiàn)了矩陣在k個(gè)機(jī)器上的分布式計(jì)算。這也是最小粒度相乘的一個(gè)思路芦昔，將矩陣的乘積轉(zhuǎn)化為數(shù)的乘積诱贿，隨后疊加。如下圖：
-
實(shí)現(xiàn)詳解：
(1) 數(shù)據(jù)切分：
首先在hdfs上的文件存儲(chǔ)我們采用ELL的存儲(chǔ)方式，并將這個(gè)二維數(shù)組按照#切分成不同的split-part珠十，例如上面的例子我們切分成了：
[0,1] [1,2] [0,2,3] [1,3]
[1,7] [2,8] [5,3,9] [6,4]
上下組成columnid 與 value的對(duì)應(yīng)關(guān)系,一共4組料扰，我們對(duì)于A矩陣按照列壓縮存儲(chǔ)(存行號(hào))如下，B矩陣按照行壓縮存儲(chǔ)(存列號(hào))也就是上面所示焙蹭。
[0,2] [0,1,3] [1,2] [2,3]
[1,5] [7,2,6] [8,3] [9,4]
隨后map中的工作就是將A與B中對(duì)應(yīng)位置的分片值逐一相乘以(i,j)作為key輸出晒杈；例如A的第一個(gè)分片與B的第一個(gè)分片相乘放在第一個(gè)mapper里去做結(jié)果如下：
(0,0) 1 ; (0, 2) 5; (1,0) 7; (1,2) 35這些都是對(duì)最終結(jié)果(i, j)位置上的值的一個(gè)分量。對(duì)于A的第二個(gè)分片和B的第二個(gè)分片我們繼續(xù)做上述工作得到：(1,0) 14; (1,1) 4;(1,3) 12; (2, 0) 56; (2, 1) 16; (2, 3) 48孔厉。A的第三個(gè)分片與B的第三個(gè)分片：(0,1) 40; (0,2) 15;(2,1) 24; (2, 2) 9; (3拯钻，1) 72; (3, 2) 27。A的第四個(gè)分片與B的第四個(gè)分片：(1, 2) 54; (1, 3) 24; (3, 2) 36; (3, 3) 16;
隨后每個(gè)mapper將key 設(shè)定為 (i # j); value 為計(jì)算所得到的數(shù)值撰豺；將所有的mapper值shuffle后進(jìn)入reducer粪般。這樣，相同的i, j會(huì)在一起污桦。相加后得到(1,j) 元素的值亩歹。完成計(jì)算。
轉(zhuǎn)載請(qǐng)著名出處：http://www.reibang.com/p/b335ad456990
[ ]: http://latex.codecogs.com/png.latex?a_i_k*b_k_j
[ELL存儲(chǔ).png]:http://upload-images.jianshu.io/upload_images/5666544-f794e5f9814a9612.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240
[CSR存儲(chǔ).png]:http://upload-images.jianshu.io/upload_images/5666544-414e9610a52e3a5e.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240
[COO存儲(chǔ)方式.png]:http://upload-images.jianshu.io/upload_images/5666544-1ccdc71896ffb315.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240
