A. MapRece是什麼有什麼作用
MapRece是一種編程模型，用於大規模數據集（大於1TB）的並行運算。概念"Map（映射）"和"Rece（歸約）"，和它們的主要思想，都是從函數式編程語言里借來的，還有從矢量編程語言里借來的特性。它極大地方便了編程人員在不會分布式並行編程的情況下，將自己的程序運行在分布式系統上。 當前的軟體實現是指定一個Map（映射）函數，用來把一組鍵值對映射成一組新的鍵值對，指定並發的Rece（歸約）函數，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。
瑭錦TANJURD總結在Google，MapRece用在非常廣泛的應用程序中，包括「分布grep，分布排序，web連接圖反轉，每台機器的詞矢量，web訪問日誌分析，反向索引構建，文檔聚類，機器學習，基於統計的機器翻譯...」值得注意的是，MapRece實現以後，它被用來重新生成Google的整個索引，並取代老的ad hoc程序去更新索引。
B. 請問你有用maprece實現Apriori演算法的代碼嗎
matlab實現apriori演算法源代碼 一、實驗目的 通過實驗，加深數據挖掘中一個重要方法——關聯分析的認識，其經典演算法為apriori演算法，了解影響apriori演算法性能的因素，掌握基於apriori演算法理論的關聯分析的原理和方法。 二、實驗內容 對一數據集用apriori演算法做關聯分析，用matlab實現。 三、方法手段 關聯規則挖掘的一個典型例子是購物籃分析。市場分析員要從大量的數據中發現顧客放入其購物籃中的不同商品之間的關系。如果顧客買牛奶，他也購買麵包的可能性有多大？ 什麼商品組或集合顧客多半會在一次購物時同時購買？例如，買牛奶的顧客有80%也同時買麵包，或買鐵錘的顧客中有70%的人同時也買鐵釘，這就是從購物籃數據中提取的關聯規則。分析結果可以幫助經理設計不同的商店布局。一種策略是：經常一塊購買的商品可以放近一些，以便進一步刺激這些商品一起銷售，例如，如果顧客購買計算機又傾向於同時購買財務軟體，那麼將硬體擺放離軟體陳列近一點，可能有助於增加兩者的銷售。另一種策略是：將硬體和軟體放在商店的兩端，可能誘發購買這些商品的顧客一路挑選其他商品。 關聯規則是描述資料庫中數據項之間存在的潛在關系的規則,形式為 1212 ......mnAAABBB,其中(1,2...,)iAim,(1,2...,)jAjn是資料庫中的數據項.數據項之間的關聯規則即根據一個事務中某些項的出現,可推導出另一些項在同一事務中也出現。 四、Apriori演算法 1.演算法描述 Apriori演算法的第一步是簡單統計所有含一個元素的項集出現的頻率,來決定最大的一維項目集。在第k步,分兩個階段,首先用一函數sc_candidate(候選),通過第(k-1)步中生成的最大項目集Lk-1來生成侯選項目集Ck。然後搜索資料庫計算侯選項目集Ck的支持度. 為了更快速地計算Ck中項目的支持度, 文中使用函數count_support計算支持度。 Apriori演算法描述如下： (1) C1={candidate1-itemsets}; (2) L1={c∈C1|c.count≥minsupport}; (3) for(k=2,Lk-1≠Φ,k++) //直到不能再生成最大項目集為止 (4) Ck=sc_candidate(Lk-1); //生成含k個元素的侯選項目集 (5) for all transactions t∈D //辦理處理 (6) Ct=count_support(Ck,t); //包含在事務t中的侯選項目集 (7) for all candidates c∈Ct (8) c.count=c.count+1; (9) next (10) Lk={c∈Ck|c.count≥minsupport}; (11) next (12) resultset=resultset∪Lk 其中, D表示資料庫；minsupport表示給定的最小支持度；resultset表示所有最大項目集。 全國注冊建築師、建造師考試備考資料 歷年真題 考試心得 模擬試題 Sc_candidate函數 該函數的參數為Lk-1,即: 所有最大k-1維項目集,結果返回含有k個項目的侯選項目集Ck。事實上,Ck是k維最大項目集的超集,通過函數count_support計算項目的支持度,然後生成Lk。 該函數是如何完成這些功能的, 詳細說明如下: 首先, 通過對Lk-1自連接操作生成Ck,稱join(連接)步,該步可表述為: insert into Ck select P.item1,P.item2,...,P.itemk-1,Q.itemk-1 from Lk-1P,Lk-1Q where P.item1=Q.item1,...,P.itemk-2=Q.itemk-2,P.itemk-1<Q.itemk-1 若用集合表示:Ck={X∪X'|X,X'∈Lk-1,|X∩X'|=k-2} 然後,是prune(修剪)步,即對任意的c,c∈Ck, 刪除Ck中所有那些(k-1)維子集不在Lk-1 中的項目集,得到侯選項目集Ck。表述為： for all itemset c∈Ck for all (k-1)維子集s of c if(s不屬於Lk-1) then delete c from Ck; 用集合表示:Ck={X∈Ck|X的所有k-1維子集在Lk-1中} 2.Apriori演算法的舉例 示例說明Apriori演算法運作過程，有一資料庫D, 其中有四個事務記錄, 分別表示為 TID Items T1 I1,I3,I4 T2 I2,I3,I5 T3 I1,I2,I3,I5 T4 I2,I5 在Apriori演算法中每一步創建該步的侯選集。統計每個侯選項目集的支持度,並和預定 義的最小支持度比較,來確定該步的最大項目集。 首先統計出一維項目集,即C1.這里預定義最小支持度minsupport=2,侯選項目集中滿足最小支持度要求的項目集組合成最大的1-itemsets。為生成最大的2-itemsets,使用了sc_candidate函數中join步,即：L1joinL1，並通過prune步刪除那些C2的那些子集不在L1中的項目集。生成了侯選項目集C2。搜索D中4個事務,統計C2中每個侯選項目集的支持度。然後和最小支持度比較,生成L2。侯選項目集C3是由L2生成.要求自連接的兩個最大2-itemsets中,第一個項目相同,在L2中滿足該條件的有{I2,I3},{I2,I5}.這兩個集合經過join步後, 產生集合{I2，I3，I5}.在prune步中,測試{I2，I3，I5}的子集{I3，I5},{I2，I3},{I2，I5}是否在L2中,由L2可以知道{I3,I5},{I2,I3},{I2,I5}本身就是最大2-itemsets.即{I2,I3,I5}的子集都是最大項目集.那麼{I2,I3,I5}為侯選3-itemset.然後搜索資料庫中所有事務記錄,生成最大的3-tiemsets L3。此時, 從L3中不能再生成侯選4-itemset 。Apriori演算法結束. 演算法的圖例說明 五、實驗結果 test.txt格式及內容如下： 實驗結果如下： 六、實驗總結 Apriori演算法可以很有效地找出數據集中存在的關聯規則且能找出最大項的關聯規則，但從以上的演算法執行過程可以看到Apriori演算法的缺點: 第一,在每一步產生侯選項目集時循環產生的組合過多，沒有排除不應該參與組合的元素；第二,每次計算項集的支持度時，都對資料庫D中的全部記錄進行了一遍掃描比較，如果是一個大型的資料庫的話，這種掃描比較會大大增加計算機系統的I/O開銷。而這種代價是隨著資料庫的記錄的增加呈現出幾何級數的增加。因此人們開始尋求一種能減少這種系統1/O開銷的更為快捷的演算法。 七、實驗程序 function my_apriori(X,minsup) clc; %%%%主函數，輸入X數據集，判斷產生大於minsup最小支持度的關聯規則 %%%%%%%%%%%%%%%%%%%%%%%%%%打開test.txt文件 file = textread('test.txt','%s','delimiter','\n','whitespace',''); [m,n]=size(file); for i=1:m words=strread(file{i},'%s','delimiter',' '); words=words'; X{i}=words; end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% minsup=0.3; %預先定義支持度 [m,N]=size(X); %求X的維數 temp=X{1}; %用已暫存變數存儲所有不同項集 for i=2:N temp=union(temp,X{i}); %找出所有不同項（種類） end %%%%%%%%%%%%%%%%%%%%找出k-頻繁項 L=Sc_candidate(temp); %找出2-項候選項集 sum=1; %統計滿足條件的最多項集 while(~isempty(L{1})) %循環終止條件為第k次頻繁項集為空 sum=sum+1; C=count_support(L,X,minsup); %挑選出滿足最小支持度的k-頻繁項 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% sprintf('%s%d%s','滿足要求的',sum,'次頻繁項集依次為') %顯 for i=1:size(C,1) %示 disp(C{i,1}); %部 end %分 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% L=gen_rule(C); %依次產生k-頻繁項(依據apriori演算法規則） End %%%%%%%%%%%%%%%%%%%%%%%%各個子程序如下 function y=cell_union(X,Y) %實現兩cell元組合並功能,由k-1項集增加到k項集函數 [m,n]=size(X); if(~iscellstr(X)) %判斷X是否元組 L{1}=X; L{1,2}=Y; else L=X; L{1,n+1}=Y; end y=L; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function y=count_support(L,X,minsup) %找出符合大於支持度sup的候選集,L為候選集，X為總數據集 X=X';%轉置 %%%%%%%%%%%%%%%%%統計頻繁項 [m,n]=size(L); [M,N]=size(X); count=zeros(m,1); for i=1:m for j=1:M if(ismember(L{i},X{j})) count(i)=count(i)+1; end end end %%%%%%%%%%%刪除數據表中不頻繁的項 p=1; C=cell(1); for i=1:m if(count(i)>minsup*M) %小於支持度的項為不頻繁數，將刪除,大於的保留 C{p}=L{i}; p=p+1; end end y=C'; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function y=gen_rule(C) %apriori演算法規則判斷是否產生k-候選項集 if(~isempty(C{1})) %判斷C是否為空 [M,N]=size(C); [m,n]=size(C{1}); temp1=C; L=cell(1); for i=1:M temp2{i}=temp1{i}{n}; temp1{i}{n}=[]; end p=1; for i=1:M for j=i+1:M if(isequal(temp1{i},temp1{j})) %判斷前k-1項候選集是否相等 L{p}=cell_union(C{i},temp2{j}); %若相等，則增加至k-項集 p=p+1; end end end y=L'; else y=cell(1);%否則y返回空 end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function y=Sc_candidate(C) %產生2-項候選集函數 C=C'; %轉置 [m,n]=size(C); bcount=zeros(m*(m-1)/2,1); L=cell(m*(m-1)/2,1); p=1; for i=1:m-1 %注意 for j=i+1:m L{p}=cell_union(C{i},C{j}); %產生2-項候選集 p=p+1; end end y=L; function y=count_support(L,X,minsup) %找出符合大於支持度sup的候選集,L為候選集，X為總數據集
C. 什麼是MapRece
概念"Map（映射）"和"Rece（化簡）"，和他們的主要思想，都是從函數式編程語言里借來的，還有從矢量編程語言里借來的特性。他極大地方便了編程人員在不會分布式並行編程的情況下，將自己的程序運行在分布式系統上。 當前的軟體實現是指定一個Map（映射）函數，用來把一組鍵值對映射成一組新的鍵值對，指定並發的Rece（化簡）函數，用來保證所有映射的鍵值對中的每一個共享相同的鍵組。 映射和化簡 簡單說來，一個映射函數就是對一些獨立元素組成的概念上的列表（例如，一個測試成績的列表）的每一個元素進行指定的操作（比如前面的例子里，有人發現所有學生的成績都被高估了一分，他可以定義一個「減一」的映射函數，用來修正這個錯誤。）。 事實上，每個元素都是被獨立操作的，而原始列表沒有被更改，因為這里創建了一個新的列表來保存新的答案。這就是說，Map操作是可以高度並行的，這對高性能要求的應用以及並行計算領域的需求非常有用。 而化簡操作指的是對一個列表的元素進行適當的合並（繼續看前面的例子，如果有人想知道班級的平均分該怎麼做？他可以定義一個化簡函數，通過讓列表中的元素跟自己的相鄰的元素相加的方式把列表減半，如此遞歸運算直到列表只剩下一個元素，然後用這個元素除以人數，就得到了平均分。）。雖然他不如映射函數那麼並行，但是因為化簡總是有一個簡單的答案，大規模的運算相對獨立，所以化簡函數在高度並行環境下也很有用。編輯本段分布和可靠性 MapRece通過把對數據集的大規模操作分發給網路上的每個節點實現可靠性；每個節點會周期性的把完成的工作和狀態的更新報告回來。如果一個節點保持沉默超過一個預設的時間間隔，主節點（類同Google File System中的主伺服器）記錄下這個節點狀態為死亡，並把分配給這個節點的數據發到別的節點。每個操作使用命名文件的原子操作以確保不會發生並行線程間的沖突；當文件被改名的時候，系統可能會把他們復制到任務名以外的另一個名字上去。（避免副作用）。 化簡操作工作方式很類似，但是由於化簡操作在並行能力較差，主節點會盡量把化簡操作調度在一個節點上，或者離需要操作的數據盡可能近的節點上了；這個特性可以滿足Google的需求，因為他們有足夠的帶寬，他們的內部網路沒有那麼多的機器。 用途在Google，MapRece用在非常廣泛的應用程序中，包括「分布grep，分布排序，web連接圖反轉，每台機器的詞矢量，web訪問日誌分析，反向索引構建，文檔聚類，機器學習，基於統計的機器翻譯...」值得注意的是，MapRece實現以後，它被用來重新生成Google的整個索引，並取代老的ad hoc程序去更新索引。 MapRece會生成大量的臨時文件，為了提高效率，它利用Google文件系統來管理和訪問這些文件。
D. maprece怎麼對特定欄位進行分析
理文本是 MapRece 流程的一種常見用法，因為文本處理相對復雜且是處理器資源密集的處理。基本的字數統計常常用於演示 Haddoop 處理大量文本和基本匯總大體內容的能力。
要獲得字數，將文本從一個輸入文件中拆分（使用一個基本的 string tokenizer）為各個包含計數的單詞，並使用一個 Rece 來計算每個單詞的數量。例如，從短語 the quick brown fox jumps over the lazy dog 中，Map 階段生成清單 1 中的輸出。
E. Hadoop MapRece中把分析數據寫入mysql中
你的job類並沒有設置outputformat，如需要輸出到資料庫，需要特定的輸出如下：
job.setJarByClass(TextCheckerJob.class);
job.setMapperClass(TextMapper.class);
job.setRecerClass(TextRece.class);
job.setInputFormatClass(TextInputFormat.class);
job.setOutputFormatClass(MysqlDBOutputFormat.class);
job.setMapOutputKeyClass(Text.class);
job.setMapOutputValueClass(Text.class);
job.setOutputKeyClass(Text.class);
job.setOutputValueClass(Text.class);
job.setNumReceTasks(1);
MysqlDBOutputFormat.setOutput(job,"data_chck_result",newString[]{"tblName","colName","wrongValue","count"});
同時，job初始化之前，你需要把連接資料庫的信息寫入conf中，如下
conf.set("maprece.jdbc.driver.class",clazz);
conf.set("maprece.jdbc.username",username);
conf.set("maprece.jdbc.password",password);
conf.set("maprece.jdbc.url",url);上面的MysqlDBOutputFormat類是我自己重寫了，你可以直接使用DBOutputFormat這個類
F. MapRece和Hadoop有什麼區別分別有哪些優缺點
(1)Hadoop
是一個開源的框架，可編寫和運行分布式應用處理大規模數據，是專為離線和大規模數據分析而設計的，並不適合那種對幾個記錄隨機讀寫的在線事務處理模式。
Hadoop=HDFS（文件系統，數據存儲技術相關）+
Maprece（數據處理），Hadoop的數據來源可以是任何形式，在處理半結構化和非結構化數據上與關系型資料庫相比有更好的性能，具有更靈活的
處理能力，不管任何數據形式最終會轉化為key/value，key/value是基本數據單元。用函數式變成Maprece代替SQL，SQL是查
詢語句，而Maprece則是使用腳本和代碼，而對於適用於關系型資料庫，習慣SQL的Hadoop有開源工具hive代替。
(2)Hadoop就是一個分布式計算的解決方案.
G. 大數據培訓哪家靠譜
要找，可靠的大數據培訓確高端前沿的IT人才聚集的地方找
H. maprece有哪些局限性
從MapRece 的特點可以看出MapRece的優點非常明顯，但是MapRece也有其局限性，並不是處理海量數據的普適方法。它的局限性主要體現在以下幾點。
MapRece的執行速度慢。一個普通的MapRece作業一般在分鍾級別完成，復雜的作業或者數據量更大的情況下，也可能花費一小時或者更多，好在離線計算對於時間遠沒有OLTP那麼敏感。所以MapRece現在不是，以後也不會是關系型資料庫的終結者。MapRece的慢主要是由於磁碟I/O, MapRece作業通常都是數據密集型作業，大量的中間結果需要寫到磁碟上並通過網路進行傳輸，這耗去了大量的時間。
MapRece過於底層。與SQL相比，MapRece顯得過於底層。對於普通的查詢，一般人是不會希望寫一個map函數和rece函數的。對於習慣於關系型資料庫的用戶，或者數據分析師來說，編寫map函數和rece函數無疑是一件頭疼的事情。好在Hive的出現，大大改善了這種狀況。
不是所有演算法都能用MapRece實現。這意味著，不是所有演算法都能實現並行。例如機器學習的模型訓練，這些演算法需要狀態共享或者參數間有依賴，且需要集中維護和更新。
I. hadoop的maprece常見演算法案例有幾種
基本MapRece模式
計數與求和
問題陳述:
有許多文檔，每個文檔都有一些欄位組成。需要計算出每個欄位在所有文檔中的出現次數或者這些欄位的其他什麼統計值。例如，給定一個log文件，其中的每條記錄都包含一個響應時間，需要計算出平均響應時間。
解決方案:
讓我們先從簡單的例子入手。在下面的代碼片段里，Mapper每遇到指定詞就把頻次記1，Recer一個個遍歷這些詞的集合然後把他們的頻次加和。
1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Recer
7 method Rece(term t, counts [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)
這種方法的缺點顯而易見，Mapper提交了太多無意義的計數。它完全可以通過先對每個文檔中的詞進行計數從而減少傳遞給Recer的數據量:
1 class Mapper
2 method Map(docid id, doc d)
3 H = new AssociativeArray
4 for all term t in doc d do
5 H{t} = H{t} + 1
6 for all term t in H do
7 Emit(term t, count H{t})
如果要累計計數的的不只是單個文檔中的內容，還包括了一個Mapper節點處理的所有文檔，那就要用到Combiner了:
1 class Mapper
2 method Map(docid id, doc d)
3 for all term t in doc d do
4 Emit(term t, count 1)
5
6 class Combiner
7 method Combine(term t, [c1, c2,...])
8 sum = 0
9 for all count c in [c1, c2,...] do
10 sum = sum + c
11 Emit(term t, count sum)
12
13 class Recer
14 method Rece(term t, counts [c1, c2,...])
15 sum = 0
16 for all count c in [c1, c2,...] do
17 sum = sum + c
18 Emit(term t, count sum)
應用：Log 分析, 數據查詢
整理歸類
問題陳述:
有一系列條目，每個條目都有幾個屬性，要把具有同一屬性值的條目都保存在一個文件里，或者把條目按照屬性值分組。 最典型的應用是倒排索引。
解決方案：
解決方案很簡單。 在 Mapper 中以每個條目的所需屬性值作為 key，其本身作為值傳遞給 Recer。 Recer 取得按照屬性值分組的條目，然後可以處理或者保存。如果是在構建倒排索引，那麼 每個條目相當於一個詞而屬性值就是詞所在的文檔ID。
應用：倒排索引， ETL
過濾 (文本查找)，解析和校驗
問題陳述:
假設有很多條記錄，需要從其中找出滿足某個條件的所有記錄，或者將每條記錄傳換成另外一種形式（轉換操作相對於各條記錄獨立，即對一條記錄的操作與其他記錄無關）。像文本解析、特定值抽取、格式轉換等都屬於後一種用例。
解決方案:
非常簡單，在Mapper 里逐條進行操作，輸出需要的值或轉換後的形式。
應用：日誌分析，數據查詢，ETL，數據校驗
分布式任務執行
問題陳述:
大型計算可以分解為多個部分分別進行然後合並各個計算的結果以獲得最終結果。
解決方案: 將數據切分成多份作為每個 Mapper 的輸入，每個Mapper處理一份數據，執行同樣的運算，產生結果，Recer把多個Mapper的結果組合成一個。
案例研究： 數字通信系統模擬
像 WiMAX 這樣的數字通信模擬軟體通過系統模型來傳輸大量的隨機數據，然後計算傳輸中的錯誤幾率。 每個 Mapper 處理樣本 1/N 的數據，計算出這部分數據的錯誤率，然後在 Recer 里計算平均錯誤率。
應用：工程模擬，數字分析，性能測試
排序
問題陳述:
有許多條記錄，需要按照某種規則將所有記錄排序或是按照順序來處理記錄。
解決方案: 簡單排序很好辦 – Mappers 將待排序的屬性值為鍵，整條記錄為值輸出。 不過實際應用中的排序要更加巧妙一點， 這就是它之所以被稱為MapRece 核心的原因（「核心」是說排序？因為證明Hadoop計算能力的實驗是大數據排序？還是說Hadoop的處理過程中對key排序的環節？）。在實踐中，常用組合鍵來實現二次排序和分組。
MapRece 最初只能夠對鍵排序， 但是也有技術利用可以利用Hadoop 的特性來實現按值排序。想了解的話可以看這篇博客。
按照BigTable的概念，使用 MapRece來對最初數據而非中間數據排序，也即保持數據的有序狀態更有好處，必須注意這一點。換句話說，在數據插入時排序一次要比在每次查詢數據的時候排序更高效。
應用：ETL，數據分析
非基本 MapRece 模式
迭代消息傳遞 (圖處理)
問題陳述：
假設一個實體網路，實體之間存在著關系。 需要按照與它比鄰的其他實體的屬性計算出一個狀態。這個狀態可以表現為它和其它節點之間的距離， 存在特定屬性的鄰接點的跡象， 鄰域密度特徵等等。
解決方案：
網路存儲為系列節點的結合，每個節點包含有其所有鄰接點ID的列表。按照這個概念，MapRece 迭代進行，每次迭代中每個節點都發消息給它的鄰接點。鄰接點根據接收到的信息更新自己的狀態。當滿足了某些條件的時候迭代停止，如達到了最大迭代次數（網路半徑）或兩次連續的迭代幾乎沒有狀態改變。從技術上來看，Mapper 以每個鄰接點的ID為鍵發出信息，所有的信息都會按照接受節點分組，recer 就能夠重算各節點的狀態然後更新那些狀態改變了的節點。下面展示了這個演算法：
1 class Mapper
2 method Map(id n, object N)
3 Emit(id n, object N)
4 for all id m in N.OutgoingRelations do
5 Emit(id m, message getMessage(N))
6
7 class Recer
8 method Rece(id m, [s1, s2,...])
9 M = null
10 messages = []
11 for all s in [s1, s2,...] do
12 if IsObject(s) then
13 M = s
14 else // s is a message
15 messages.add(s)
16 M.State = calculateState(messages)
17 Emit(id m, item M)
一個節點的狀態可以迅速的沿著網路傳全網，那些被感染了的節點又去感染它們的鄰居，整個過程就像下面的圖示一樣：
案例研究： 沿分類樹的有效性傳遞
問題陳述：
這個問題來自於真實的電子商務應用。將各種貨物分類，這些類別可以組成一個樹形結構，比較大的分類（像男人、女人、兒童）可以再分出小分類（像男褲或女裝），直到不能再分為止（像男式藍色牛仔褲）。這些不能再分的基層類別可以是有效（這個類別包含有貨品）或者已無效的（沒有屬於這個分類的貨品）。如果一個分類至少含有一個有效的子分類那麼認為這個分類也是有效的。我們需要在已知一些基層分類有效的情況下找出分類樹上所有有效的分類。
解決方案：
這個問題可以用上一節提到的框架來解決。我們咋下面定義了名為 getMessage和 calculateState 的方法：
1 class N
2 State in {True = 2, False = 1, null = 0},
3 initialized 1 or 2 for end-of-line categories, 0 otherwise
4 method getMessage(object N)
5 return N.State
6 method calculateState(state s, data [d1, d2,...])
7 return max( [d1, d2,...] )
案例研究：廣度優先搜索
問題陳述：需要計算出一個圖結構中某一個節點到其它所有節點的距離。
解決方案： Source源節點給所有鄰接點發出值為0的信號，鄰接點把收到的信號再轉發給自己的鄰接點，每轉發一次就對信號值加1：
1 class N
2 State is distance,
3 initialized 0 for source node, INFINITY for all other nodes
4 method getMessage(N)
5 return N.State + 1
6 method calculateState(state s, data [d1, d2,...])
7 min( [d1, d2,...] )
案例研究：網頁排名和 Mapper 端數據聚合
這個演算法由Google提出，使用權威的PageRank演算法，通過連接到一個網頁的其他網頁來計算網頁的相關性。真實演算法是相當復雜的，但是核心思想是權重可以傳播，也即通過一個節點的各聯接節點的權重的均值來計算節點自身的權重。
1 class N
2 State is PageRank
3 method getMessage(object N)
4 return N.State / N.OutgoingRelations.size()
5 method calculateState(state s, data [d1, d2,...])
6 return ( sum([d1, d2,...]) )
要指出的是上面用一個數值來作為評分實際上是一種簡化，在實際情況下，我們需要在Mapper端來進行聚合計算得出這個值。下面的代碼片段展示了這個改變後的邏輯 （針對於 PageRank 演算法）：
1 class Mapper
2 method Initialize
3 H = new AssociativeArray
4 method Map(id n, object N)
5 p = N.PageRank / N.OutgoingRelations.size()
6 Emit(id n, object N)
7 for all id m in N.OutgoingRelations do
8 H{m} = H{m} + p
9 method Close
10 for all id n in H do
11 Emit(id n, value H{n})
12
13 class Recer
14 method Rece(id m, [s1, s2,...])
15 M = null
16 p = 0
17 for all s in [s1, s2,...] do
18 if IsObject(s) then
19 M = s
20 else
21 p = p + s
22 M.PageRank = p
23 Emit(id m, item M)
應用：圖分析，網頁索引
值去重 （對唯一項計數）
問題陳述: 記錄包含值域F和值域 G，要分別統計相同G值的記錄中不同的F值的數目 (相當於按照 G分組).
這個問題可以推而廣之應用於分面搜索（某些電子商務網站稱之為Narrow Search）
Record 1: F=1, G={a, b}
Record 2: F=2, G={a, d, e}
Record 3: F=1, G={b}
Record 4: F=3, G={a, b}
Result:
a -> 3 // F=1, F=2, F=3
b -> 2 // F=1, F=3
d -> 1 // F=2
e -> 1 // F=2
解決方案 I:
第一種方法是分兩個階段來解決這個問題。第一階段在Mapper中使用F和G組成一個復合值對，然後在Recer中輸出每個值對，目的是為了保證F值的唯一性。在第二階段，再將值對按照G值來分組計算每組中的條目數。
第一階段：
1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...]])
3 for all category g in [g1, g2,...]
4 Emit(record [g, f], count 1)
5
6 class Recer
7 method Rece(record [g, f], counts [n1, n2, ...])
8 Emit(record [g, f], null )
第二階段：
1 class Mapper
2 method Map(record [f, g], null)
3 Emit(value g, count 1)
4
5 class Recer
6 method Rece(value g, counts [n1, n2,...])
7 Emit(value g, sum( [n1, n2,...] ) )
解決方案 II:
第二種方法只需要一次MapRece 即可實現，但擴展性不強。演算法很簡單-Mapper 輸出值和分類，在Recer里為每個值對應的分類去重然後給每個所屬的分類計數加1，最後再在Recer結束後將所有計數加和。這種方法適用於只有有限個分類，而且擁有相同F值的記錄不是很多的情況。例如網路日誌處理和用戶分類，用戶的總數很多，但是每個用戶的事件是有限的，以此分類得到的類別也是有限的。值得一提的是在這種模式下可以在數據傳輸到Recer之前使用Combiner來去除分類的重復值。
1 class Mapper
2 method Map(null, record [value f, categories [g1, g2,...] )
3 for all category g in [g1, g2,...]
4 Emit(value f, category g)
5
6 class Recer
7 method Initialize
8 H = new AssociativeArray : category -> count
9 method Rece(value f, categories [g1, g2,...])
10 [g1', g2',..] = ExcludeDuplicates( [g1, g2,..] )
11 for all category g in [g1', g2',...]
12 H{g} = H{g} + 1
13 method Close
14 for all category g in H do
15 Emit(category g, count H{g})
應用：日誌分析，用戶計數
互相關
問題陳述：有多個各由若干項構成的組，計算項兩兩共同出現於一個組中的次數。假如項數是N，那麼應該計算N*N。
這種情況常見於文本分析（條目是單詞而元組是句子），市場分析（購買了此物的客戶還可能購買什麼）。如果N*N小到可以容納於一台機器的內存，實現起來就比較簡單了。
配對法
第一種方法是在Mapper中給所有條目配對，然後在Recer中將同一條目對的計數加和。但這種做法也有缺點：
使用 combiners 帶來的的好處有限，因為很可能所有項對都是唯一的
不能有效利用內存
1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 for all item j in [i1, i2,...]
5 Emit(pair [i j], count 1)
6
7 class Recer
8 method Rece(pair [i j], counts [c1, c2,...])
9 s = sum([c1, c2,...])
10 Emit(pair[i j], count s)
Stripes Approach（條方法？不知道這個名字怎麼理解）
第二種方法是將數據按照pair中的第一項來分組，並維護一個關聯數組，數組中存儲的是所有關聯項的計數。The second approach is to group data by the first item in pair and maintain an associative array (「stripe」) where counters for all adjacent items are accumulated. Recer receives all stripes for leading item i, merges them, and emits the same result as in the Pairs approach.
中間結果的鍵數量相對較少，因此減少了排序消耗。
可以有效利用 combiners。
可在內存中執行，不過如果沒有正確執行的話也會帶來問題。
實現起來比較復雜。
一般來說， 「stripes」 比 「pairs」 更快
1 class Mapper
2 method Map(null, items [i1, i2,...] )
3 for all item i in [i1, i2,...]
4 H = new AssociativeArray : item -> counter
5 for all item j in [i1, i2,...]
6 H{j} = H{j} + 1
7 Emit(item i, stripe H)
8
9 class Recer
10 method Rece(item i, stripes [H1, H2,...])
11 H = new AssociativeArray : item -> counter
12 H = merge-sum( [H1, H2,...] )
13 for all item j in H.keys()
14 Emit(pair [i j], H{j})
應用：文本分析，市場分析
參考資料：Lin J. Dyer C. Hirst G. Data Intensive Processing MapRece
用MapRece 表達關系模式
在這部分我們會討論一下怎麼使用MapRece來進行主要的關系操作。
篩選（Selection）
1 class Mapper
2 method Map(rowkey key, tuple t)
3 if t satisfies the predicate
4 Emit(tuple t, null)
投影（Projection）
投影只比篩選稍微復雜一點，在這種情況下我們可以用Recer來消除可能的重復值。
1 class Mapper
2 method Map(rowkey key, tuple t)
3 tuple g = project(t) // extract required fields to tuple g
4 Emit(tuple g, null)
5
6 class Recer
J. 如何用亞馬遜彈性MapRece分析大數據
首先，打開Amazon Elastic MapRece控制台。然後點擊 Create Cluster ，在五個步驟中完成配置設置。
第一步，配置一個集群
在 Cluster name 欄位中，輸入一個描述性的名稱。它可以是非唯一的。
在Termination protection 欄位中，其默認值為Yes。這一設置可確保集群不會因為意外或錯誤而關閉。
在Logging 欄位中，其默認值為Enabled。日誌數據將被發送至亞馬遜S3。
在Log folder S3 location 欄位中，請以如下格式輸入存儲桶名稱和文件夾信息：s3://<bucket name>/<folder>/。
在Debugging 欄位中，其默認值為Enabled。
Tag 部分是可選的。你可以為你的EMR集群添加最多10個標簽。在一個標簽中，包括了一個區分大小寫的鍵值對。
第二步，設置軟體配置
在Hadoop distribution 多選框中，選擇Amazon 為默認值。
在 AMI version 多選框中，選擇 2.4.2 （Hadoop 1.0.3）
在Application to be installed 多選框中，保留選中Hive 和 deletePig。
第三步，設置硬體配置
在 Network 欄位中，選擇Launch into EC-2 Classic。
在EC2 Subnet 欄位中，選擇 No preference。
在Master、Core 以及 Task 欄位中，默認EC2實例類型為m1.small。對於低工作負載的應用，你可以為所有節點選擇使用小實例（可確保降低你的使用成本）。相應地，Count
的默認值分別為1、 2、 0。同時，對於所有三個欄位，確保不選中 Request Spot Instances 。
注意：20是每個AWS帳戶的最大節點數。如果你運行了2個集群，那麼2個集群運行的節點總數必須為20或以下。如果你確實需要節點數超過20，那麼你必須提交一個請求以便於提高你的亞馬遜EC2實例上限。
第四步，設置安全和訪問配置
在EC2 key pair 欄位中，從列表中選擇一個亞馬遜EC2密鑰對。這一設置可以讓你使用Secure Shell（SSH）來連接主節點。
在IAM user access 欄位中，其默認值為 No other IAM users。
在EC2 role 多選框中，其默認值為 no roles found。
在Bootstrap Actions 部分，你可以不做任何操作。
第五步，指定集群參數
在Steps 部分，從列表中選擇Hive Program，並點擊 Configure and add。
在Name 欄位中，其默認值為Hive Program。
在 Script s3 Location 欄位中（必選項），以BucketName/path/ScriptName的格式輸入相關信息，例如
s3n://elasticmaprece/samples/hive-ads/libs/model-build。
在 Input s3 Location 欄位中（可選項），以BucketName/path的格式輸入相關信息，例如
s3n://elasticmaprece/samples/hive-ads/tables。該輸入值會作為名為INPUT的參數發送給Hive腳
本程序。
Output S3 Location 欄位（可選項），以BucketName/path的格式輸入相關信息，例如
s3n://myawsbucket/hive-ads/output/2014-4-14。該輸入值會作為名為OUTPUT的參數發送給Hive腳本程
序。
在 Arguments 欄位，輸入相關信息，如 - d LIBS=s3n://elasticrecemap/samples/hive-ads/libs。HIVE腳本程序需要額外的庫。
在 Action on Failure 欄位中，選擇 Continue。如果當前步驟失敗，它將繼續至下一個步驟。
當你完成後，點擊Add，然後點擊Create Cluster。你將會看到Summary 信息。
如上例，在你繼續查詢操作和分析大數據前，你需要在主節點上准備一個HIVE會話。
你將需要每隔五分鍾向亞馬遜S3推送 Impression 和 Click Log Files。每次添加一個條目，就會向客戶顯示一條廣告。每次添加一個Click
Log Files的條目，客戶一條廣告。類似於SQL的查詢操作簡化了關聯客戶點擊數據和特定廣告的過程。
總之，分析大數據的最佳方法就是在Hadoop上運行Hive，並使用SQL查詢以簡化日誌數據分析。