mapreduce常見演算法

『壹』 請問你有用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為總數據集

『貳』 大數據如何入門

首先我們要了解java語言和Linux操作系統，這兩個是學習大數據的基礎，學習的順序不分前後。

大數據

Java ：只要了解一些基礎即可，做大數據不需要很深的Java 技術，學java SE 就相當於有學習大數據基礎。

Linux：因為大數據相關軟體都是在Linux上運行的，所以Linux要學習的扎實一些，學好Linux對你快速掌握大數據相關技術會有很大的幫助，能讓你更好的理解hadoop、hive、hbase、spark等大數據軟體的運行環境和網路環境配置，能少踩很多坑，學會shell就能看懂腳本這樣能更容易理解和配置大數據集群。還能讓你對以後新出的大數據技術學習起來更快。

Hadoop：這是現在流行的大數據處理平台幾乎已經成為大數據的代名詞，所以這個是必學的。Hadoop裡麵包括幾個組件HDFS、MapRece和YARN，HDFS是存儲數據的地方就像我們電腦的硬碟一樣文件都存儲在這個上面，MapRece是對數據進行處理計算的，它有個特點就是不管多大的數據只要給它時間它就能把數據跑完，但是時間可能不是很快所以它叫數據的批處理。

Zookeeper：這是個萬金油，安裝Hadoop的HA的時候就會用到它，以後的Hbase也會用到它。它一般用來存放一些相互協作的信息，這些信息比較小一般不會超過1M，都是使用它的軟體對它有依賴，對於我們個人來講只需要把它安裝正確，讓它正常的run起來就可以了。

Mysql：我們學習完大數據的處理了，接下來學習學習小數據的處理工具mysql資料庫，因為一會裝hive的時候要用到，mysql需要掌握到什麼層度那?你能在Linux上把它安裝好，運行起來，會配置簡單的許可權，修改root的密碼，創建資料庫。這里主要的是學習SQL的語法，因為hive的語法和這個非常相似。

Sqoop：這個是用於把Mysql里的數據導入到Hadoop里的。當然你也可以不用這個，直接把Mysql數據表導出成文件再放到HDFS上也是一樣的，當然生產環境中使用要注意Mysql的壓力。

Hive：這個東西對於會SQL語法的來說就是神器，它能讓你處理大數據變的很簡單，不會再費勁的編寫MapRece程序。有的人說Pig那?它和Pig差不多掌握一個就可以了。

Oozie：既然學會Hive了，我相信你一定需要這個東西，它可以幫你管理你的Hive或者MapRece、Spark腳本，還能檢查你的程序是否執行正確，出錯了給你發報警並能幫你重試程序，最重要的是還能幫你配置任務的依賴關系。我相信你一定會喜歡上它的，不然你看著那一大堆腳本，和密密麻麻的crond是不是有種想屎的感覺。

Hbase：這是Hadoop生態體系中的NOSQL資料庫，他的數據是按照key和value的形式存儲的並且key是唯一的，所以它能用來做數據的排重，它與MYSQL相比能存儲的數據量大很多。所以他常被用於大數據處理完成之後的存儲目的地。

Kafka：這是個比較好用的隊列工具，隊列是干嗎的?排隊買票你知道不?數據多了同樣也需要排隊處理，這樣與你協作的其它同學不會叫起來，你干嗎給我這么多的數據(比如好幾百G的文件)我怎麼處理得過來，你別怪他因為他不是搞大數據的，你可以跟他講我把數據放在隊列里你使用的時候一個個拿，這樣他就不在抱怨了馬上灰流流的去優化他的程序去了，因為處理不過來就是他的事情。而不是你給的問題。當然我們也可以利用這個工具來做線上實時數據的入庫或入HDFS，這時你可以與一個叫Flume的工具配合使用，它是專門用來提供對數據進行簡單處理，並寫到各種數據接受方(比如Kafka)的。

Spark：它是用來彌補基於MapRece處理數據速度上的缺點，它的特點是把數據裝載到內存中計算而不是去讀慢的要死進化還特別慢的硬碟。特別適合做迭代運算，所以演算法流們特別稀飯它。它是用scala編寫的。Java語言或者Scala都可以操作它，因為它們都是用JVM的。

『叄』 maprece是什麼意思

MapRece是一種編程模型，用於大規模數據集（大春碧缺於1TB）的並行運算。概念"Map（映射）"和"Rece（歸約）"，是它們的主要思想，都是從函數式編程語言里借來的，還有從矢量編程語言里借來的特性。

它極大地方便了編程人員在不扒辯會分布式並行編程的情況下，將自己的程序運行在分布式系統上。 當前的軟體實現是指定一個Map（映射）函數，用來把一組鍵值對映射成一組新的鍵值對，指定並發的Rece（歸約）函數。

用來保證所有映射的鍵值對中的每一個共享相同的鍵組。MapRece最早是由Google公司研究提出的一種面向大規模數據處理的並行計算模型和方法。Google公司設計MapRece的初衷主要是為了解決其搜索引擎中大規模網頁數據的並行化處理。

Google公司發明了MapRece之後首先用其重新改寫了其搜索引擎中的Web文檔索引處理系統。

但由於MapRece可以普遍應用於很多大規模數據的計算問題，因此自發明MapRece以後，Google公司內部進一步將其廣泛應用於很多大規模數據處理問題。Google公司內有上萬個各種不同的演算法問題和程序都使慧缺用MapRece進行處理。