基于mapreduce的稀疏矩陣乘法算法

1、基于mapreduce的稀疏矩陣乘法算法組長：吳建些組員：白野朵寶寶目錄一、課題研究目的二、稀疏矩陣介紹（一）稀疏矩陣乘法介名S（三元組）2（二）Mapreduce介紹4（三）實驗環(huán)境配置7（四）創(chuàng)建代碼（來自網絡的代碼）10（五）組員總結16一、課題研究目的。矩陣乘法運算是一種基本運算。而擴大矩陣乘法的運算規(guī)模并降低其運算時間，將有利于滿足機器學習算法處理大規(guī)模數(shù)據(jù)的要求。將MapReduce并行框架用于分塊矩陣乘法，實現(xiàn)一種用于大規(guī)模矩陣乘法運算的方法。理論分析和實驗結果表明該方法在處理大規(guī)模矩陣乘法上具有極大的潛能，并且隨著計算節(jié)點的增加從而獲得較好的加速比。二、稀疏矩陣介紹。人們無法給

2、出稀疏矩陣的確切定義，一般都只是憑個人的直覺來理解這個概念，即矩陣中非零元素的個數(shù)遠遠小于矩陣元素的總數(shù)，并且非零元素沒有分布規(guī)律。對于那些零元素數(shù)目遠遠多于非零元素數(shù)目，并且非零元素的分布沒有規(guī)律的矩陣稱為稀疏矩陣（六）稀疏矩陣乘法介紹（三元組）當矩陣MN是稀疏矩陣時，我們可以采用三元組表的表示形式來實現(xiàn)矩陣的乘。采用三元組表的方法來實現(xiàn)時，因為三元組只對矩陣的非零元素做存儲所以可以采用固定三元組表a中的元素（i,k,Mik）（1wiwml,1wkwn1）,在三元組表b中找所有行號為k的的對應元素（k,j,Nkj）（iwkwm21wjWn2）進行相乘、累加，從而得到Qij,即以三元組表a中的

3、元素為基準，依次求出其與三元組表b的有效乘積。算法中附設兩個向量num、first,其中numrow表示三元組表b中第row行非零元素個數(shù)（1WrowWm2）,firstrow表示三元組表b中第row行第一個非零元素所在的位置。顯然，firstrow+1-1指向三元組表b中第row行最后一個非零元素的位置。first1=1;firstrow=firstrow-1+numrow-1,2wrowWm2+1。這里，firstm2+H-1表示最后一行最后一個非零元素的存儲位置。當三元組表a中第i行非零元素的列號等于三元組表b中非零元素的行號時，則元素相乘并將結果累加。（七）Mapreduce介紹1、M

4、apReduce是一種編程模型，用于大規(guī)模數(shù)據(jù)集（大于1TB）的并行運算。2、特點：具有接口簡單，健壯容錯的特點。3、關于map函數(shù)和reduce函數(shù)MapReduce的整體架構主要由map和reduce這兩個函數(shù)組。其含義是：Map（映射）和Reduce（化簡）。圖1Mapreduce模式工作過程用戶輸入一組鍵/值對，首先由map函數(shù)生成一批中間的鍵/值對，然后由reduce函數(shù)將具有相同鍵的中間值合并，產生最后的結果。在這一過程中，由于MapReduce的數(shù)據(jù)本地化特性，計算都是在本地節(jié)點完成。用戶在使MapReduce開發(fā)時，只需要關注于應用本身，而不必關心底層的任務分發(fā)、并發(fā)控制、資源

5、管理、容錯等復雜細節(jié)。極大地方便了編程人員在不會分布式并行編程的情況下，將自己的程序運行在分布式系統(tǒng)上。因此，可以有效地將大規(guī)模矩陣乘法運算引入到MapReduce并行框架中。4、MapReduce與傳統(tǒng)并行編程模型的比較：在傳統(tǒng)并行編程過程中，程序員必須花大量的精力去處理進程間通信。WordCount被用來統(tǒng)計輸入數(shù)據(jù)中各單詞出現(xiàn)的次數(shù)。以WordCount為例，MPI的一種實現(xiàn)方式為：在各個MPI進程完成各自的統(tǒng)計任務后，將結果匯總給某一個進程，然后由該進程進行最終統(tǒng)計。該實現(xiàn)方式很容易在完成最終統(tǒng)計任務的進程處形成通信瓶頸，而最終統(tǒng)計任務是以順序方式完成，會導致統(tǒng)計效率低下。采用并行分類

6、統(tǒng)計能提升效率，即收集各個進程獲得的關于某個相同單詞的局部統(tǒng)計信息，并將這些信息匯總給某個進程處進行分類統(tǒng)計。然而由于這種實現(xiàn)方式僅確定能產生某個單詞統(tǒng)計信息的進程范圍，因此會增加編程復雜度。圖2Mapreduce下WordCount運行過程在MapReduce模型下，完成單詞統(tǒng)at的具體步驟為：（1）用戶編寫Map程序對出現(xiàn)的單詞word產生中間結果key/value偶對，i0。（2）這些分布產生的中間結果將按key值的不同進行匯總處理，產生key（word）相同的value列表，如,并作為Reduce階段的輸入，這個階段的工作將MapReduce策略，把對全局（或階段性）計算結果有影響且有

7、關聯(lián)的value采用相同key標志。由于這種策略的簡單抽象，因此用戶可以較容易地把握局部和全局關系，從而確保問題求解并行實現(xiàn)的正確性，并進一步降低并行分布式編程的難度。（八）實驗環(huán)境配置。（10分）1 、作為一個成熟的MapReduce應用，Hadoop被選為我們的實驗平臺，算法在JavaJDK1.7.0_09上運行。2 、Hadoop和MapReduce的關系：?hadoop是一種分布式系統(tǒng)的平臺，通過它可以很輕松的搭建一個高效、高質量的分布系統(tǒng)，而且它還有許多其它的相關子項目，也就是對它的功能的極大擴充，包括Zookeeper,Hive,Hbase等。?MapReduce是hadoop的核

8、心組件之一，hadoop要分布式包括兩部分，一是分布式文件系統(tǒng)hdfs,一部是分布式計算框，就是mapreduce,缺一不可，也就是說，可以通過mapreduce很容易在hadoop平臺上進行分布式的計算編程。3、如下實現(xiàn)環(huán)境配置：?所用Linux版本：ubuntu-10.10?Unbuntu介紹：以桌面應用為主題的Linux操作系統(tǒng)。支持x86、x64和ppc架構。使用unbuntu的原因免費redhat主要還是服務器方面，而且收費。Ubuntu是完全免費的。-界面非常友好界面友好表現(xiàn)在更適合初學者使用，功能查找比較簡單。對硬件的支持非常全面最適合做桌面系統(tǒng)的Linux發(fā)行版本毋庸置疑，我們

9、最熟悉的操作系統(tǒng)是Windows。所以希望選擇一個跟Windows相似的操作系統(tǒng)。U圖形界面的思想已經根深蒂固。Unbuntu的桌面系統(tǒng)做的比Redhat更成熟，-容易上手，適合初學者作為一個初學者，之前沒有接觸過Windows以外的操作系統(tǒng)。所以我組選取的操作系統(tǒng)是unbuntu10-10.我組也安裝了Redhat,但是在安裝JDK的時候出現(xiàn)了無法獲取權限的問題。因此放棄Redhato從安裝JDK的過程中，按照下面的安裝步驟進行，沒有出現(xiàn)任何問題。?buntu下配置JDK:先去Oracle下載Linux下的JDK壓縮包，我下載的是jdk-7u9-linux-i586.tar.gz文件，下好后

10、直接解壓解壓命令：sudotarzxvf./jdk-7u9-linux-i586.tar.gz創(chuàng)建文件夾：sudomkdir/usr/lib/jvmStep1:#將解壓好的jdk1.7.0_09文件夾用最高權限復制到/usr/lib/jvm目錄里sudocp-r/jdk1.7.0_09/usr/lib/jvm/Step2:#配置環(huán)境變量sudogedit/.profile在末尾加上：exportJAVA_HOME=/usr/lib/jvm/jdk1.7.0_09exportCLASSPATH=.:$JAVA_HOME/lib:$JAVA_HOME/jre/libexportPATH=$JAVA

11、_HOME/bin:$PATH然后保存關閉，使用source更新下source/.profile使用env命令察看JAVA_HOM的值env如果JAVA_HOME=/usr/lib/jvm/jdk1.7.0_09,說明配置成功。-installStep3:#將系統(tǒng)默認的jdk修改過來$sudoupdate-alternatives/usr/bin/javajava/usr/lib/jvm/jdk1.7.0_09/bin/java300輸入sunjdk前的數(shù)字就好了$sudoupdate-alternatives-install/usr/bin/javacjavac/usr/lib/jvm/jd

12、k1.7.0_09/bin/javac300$sudoupdate-alternatives-configjava$sudoupdate-alternatives-configjavacStep4:然后再輸入java-version,看到如下信息，就說明改成sun的jdk了：配置hadoop:沒有配置成功，所以沒有自己編寫代碼。(九)創(chuàng)建代碼(來自網絡的代碼)。稀疏矩陣的乘法只有在第一個矩陣的列數(shù)(column)和第二個矩陣的行數(shù)(row)相同時才有定義。一般單指矩陣乘積時，指的便是一般矩陣乘積。若A為ixr矩陣，B為rxj矩陣,則他們的乘積AB(有時記做AB)會是一個iXj矩陣。其乘積矩陣的

13、元素如下面式子得出：對矩陣乘法的MapReduce實現(xiàn)方法是：Map函數(shù)：對于矢I陣M的每個元素Mi,j,產生一系列的鍵值對(i,k)-(M,j,Mi,j),其中k=1,2.,直到矩陣N的列數(shù)。同樣，對于矢I陣N的每個元素Nj,k,產生一系列的鍵值對(i,k)-(N,j,Nj,k),其中i=1,2.,直到矩陣M的行數(shù)。Reduce函數(shù)：根據(jù)MR勺原理，相同鍵i,k的數(shù)據(jù)會發(fā)送個同一個reduce。如果M為2*2矩陣，N為2X3矩陣,reduce函數(shù)需要處理的數(shù)據(jù)為:(1,1)-(M,1,M1,1)(1,(2) -(M,1,M1,1)(1,(3) -(M,1,M1,1)(2,1)-(M,1,M2

14、,1)(2,2)-(M,1,M2,1)(2,3)-(M,1,M2,1)(M,2,M1,2)(M,2,M1,2)(M,2,M1,2)(M,2,M2,2)(M,2,M2,2)(M,2,M2,2)、(N,1,N1,1)、(N,1,N1,2)、(N,1,N1,3)、(N,1,N1,1)、(N,1,N1,2)、(N,1,N1,3)、(N,2,N2,1)、(N,2,N2,2)、(N,2,N2,3),、(N,2,N2,1)、(N,2,N2,2)、(N,2,N2,3)這樣只要將所有(M,j,Mi,j)和(N,j,Nj,k)分別按照j值排序并放在不同的兩個列表里面。將這個列表的第j個元素Mi,j個Nj,k相乘，

15、然后將這些積相加，最后積的和與鍵(i,k)組對作為reduce函數(shù)的輸出。對于上面的例子reduce的輸出就是：(1,(1) -(M1,1*N1,1+M1,2*N2,1)(1,(2) -(M1,1*N1,2+M1,2*N2,2)(1,(3) -(M1,1*N1,3+M1,2*N2,3)(2,(1) -(M2,1*N2,1+M2,2*N2,1)(2,(2) -(M2,1*N1,2+M2,2*N2,2)(2,(3) -(M2,1*N1,3+M2,2*N2,3)下面是MapReduce的實現(xiàn)步驟：(1) .構造矩陣M300*150;矩陣N:150*500。兩矩陣的值放在一個M.data文件中，每行的

16、格式為：文件標識樹亍坐標#J坐標#坐標值。(2) .基于上面的方法編寫Map函數(shù)和Reduce函數(shù)。代碼詳見:importjava.io.IOException;importorg.apache.hadoop.conf.Configuration;importorg.apache.hadoop.fs.Path;importorg.apache.hadoop.io.Text;importorg.apache.hadoop.mapreduce.Job;importorg.apache.hadoop.mapreduce.Mapper;importorg.apache.hadoop.mapreduce

17、.Reducer;importorg.apache.hadoop.mapreduce.lib.input.FileInputFormat;importorg.apache.hadoop.mapreduce.lib.output.FileOutputFormat;importorg.apache.hadoop.util.GenericOptionsParser;PublicclassMartrixMultiplicationpublicstaticclassMartrixMapperextendsMapperprivateTextmap_key=newText();privateTextmap_

18、value=newText();intrNumber=300;intcNumber=500;StringfileTarget;Stringi,j,k,ij,jk;publicvoidmap(Objectkey,Textvalue,Contextcontext)throwsIOException,InterruptedExceptionStringeachterm=value.toString().split(#);fileTarget=eachterm0;if(fileTarget.equals(M)i=eachterm1;j=eachterm2;ij=eachterm3;for(intc=1

19、;c=cNumber;c+)map_key.set(i+#+String.valueOf(c);map_value.set(M+#+j+#+ij);context.write(map_key,map_value);elseif(fileTarget.equals(N)j=eachterm1;k=eachterm2;jk=eachterm3;for(intr=1;r=rNumber;r+)map_key.set(String.valueOf(r)+#+k);map_value.set(N+#+j+#+jk);context.write(map_key,map_value);publicstati

20、cclassMartrixReducerextendsReducerprivateTextreduce_value=newText();intjNumber=150;intM_ij=newintjNumber+1;intN_jk=newintjNumber+1;intj,ij,jk;StringfileTarget;intjsum=0;publicvoidreduce(Textkey,Iterablevalues,Contextcontext)throwsIOException,InterruptedExceptionjsum=0;for(Textval:values)Stringeachte

21、rm=val.toString().split(#);fileTarget=eachterm0;j=Integer.parseInt(eachterm1);if(fileTarget.equals(M)ij=Integer.parseInt(eachterm2);M_ijj=ij;elseif(fileTarget.equals(N)jk=Integer.parseInt(eachterm2);N_jkj=jk;for(intd=1;d=jNumber;d+)jsum+=M_ijd*N_jkd;reduce_value.set(String.valueOf(jsum);context.writ

22、e(key,reduce_value);publicstaticvoidmain(Stringargs)throwsExceptionConfigurationconf=newConfiguration。；StringotherArgs=newGenericOptionsParser(conf,args).getRemainingArgs();if(otherArgs.length!=2)System.err.println(Usage:MartrixMultiplication);System.exit(2);Jobjob=newJob(conf,martrixmultiplication)

23、;job.setJarByClass(MartrixMultiplication.class);job.setMapperClass(MartrixMapper.class);job.setReducerClass(MartrixReducer.class);job.setOutputKeyClass(Text.class);job.setOutputValueClass(Text.class);FileInputFormat.addInputPath(job,newPath(otherArgs0);FileOutputFormat.setOutputPath(job,newPath(othe

24、rArgs1);System.exit(job.waitForCompletion(true)?0:1);）（3）,將運行的結果文件copy到本地，并使用check.py對結果中元素10,95的正確性進行驗證。運行結果：沒有運行。組員總結姓名：吳建喧我是本組組長，我給每個人的分工是，白野負責稀疏矩陣三元組實現(xiàn)矩陣乘法。朵寶寶負責的是Mapreduce思想的理解上，比如運行程序的工作原理。我主要負責使用虛擬機方面。在安裝虛擬機，安裝Linux和配置JDK上，花費的時間比較大。也不是很成功。但是我覺得我的收獲是我了解了unbuntu。它擁有比較友好的界面，方便查找功能。而且安裝也是比較簡單。用Vi

25、rtualBox虛擬機安裝，只要按部就班就可以成功。在安裝redhat上，我覺得步驟比復雜。首先是第一次運行需要安裝。安裝過程比較簡單，但是在也出現(xiàn)了空間不足的情況，然后就修改內存大小。而且過程中有些選項理解比較模糊，就是一般按默認進行。然后配置JDK上出現(xiàn)了權限無法獲取的問題。具體原因可能是開始沒有卸載成功。包括改成可執(zhí)行權限也沒有成功。因為進度的關系，所以放棄redhat。然后使用ubuntu10-10.我認為這個系統(tǒng)更適合初學者，因為操作起來比較簡單。包括可以再終端下解壓縮，在終端下為profile文件增加代碼。然后根據(jù)上面的步驟配置很成功。但是利用網絡上的教程配置hadoop的過程中。

26、前面都很順利，該顯示的都已經顯示。但是卻沒有運行成功。沒有出現(xiàn)：具體原因應該是的hdfs文件系統(tǒng)沒有格式化成功。但是在進度上沒有時間再往下做。所以本實驗終結在了這里。姓名：朵寶寶我們的網絡工程項目是基于mapreduce的稀疏矩陣乘法算法。我們從最開始的不了解，我們的網絡工程項目是基于mapreduce的稀疏矩陣乘法算法。通過圖書館和網上查到資料弄清了一些關于mapreduce的稀疏矩陣乘法算法，值到最后把這個項目課題基本做完。我們先對mapreduce進行了了解。之后安裝了虛擬機Linux,并分析了源代碼。我們一個組共同努力，不同分工，在網上查閱了資料，整理資料。在這其中，我負責查閱了mapreduce思想的部分。其中遇到了很多困難，通過組長和其他同學的幫助，解決了不少的問題。MapRedue是一個為并行處理大量數(shù)據(jù)而設計的編程模型，它將工作劃分為一個獨立任務組成的集合。它是一種并