? ? Hadoop平臺K-Means聚類算法分布式實現+MapReduce通俗講解

在Hadoop分布式環境下實現K-Means聚類算法的偽代碼如下：

輸入：參數0--存儲樣本數據的文本文件inputfile；

??????????? 參數1--存儲樣本數據的SequenceFile文件inputPath；

??????????? 參數2--存儲質心數據的SequenceFile文件centerPath；

??????????? 參數3--存儲聚類結果文件(SequenceFile文件)所處的路徑clusterPath；

??????????? 參數4--類的數量k；

輸出：k個類

Begin

?????????? 讀取inputPath，從中選取前k個點作為初始質心，將質心數據寫入centerPath；

?????????? While 聚類終止條件不滿足

??????????????????? 在Mapper階段，讀取inputPath，對于key所對應的點，遍歷所有的質心，選擇最近的質心，將該質心的編號作為鍵，

??????????????????? 該點的編號作為值傳遞給Reducer；

??????????????????? 在Reducer階段，將Mapper階段傳遞過來的值根據鍵歸并輸出，結果寫入clusterPath；

??????????????????? 讀取clusterPath，重新計算質心，將結果寫入centerPath；

?????????? EndWhile

End

判斷聚類效果好壞的常見指標是下述的準則函數值：

有理由認為上述值越小，聚類效果越好，隨著循環的不斷進行，上述準則函數值會收斂到一個很小的值，所以可以用這個值不再明顯變化作為聚類循環的終止條件。

在map 主要做的是計算各個數據點與聚類中心的距離并且找出與樣本對應的最近中心。 計算新的聚類中心<key,value> 輸入key MApreduce默認格式 ，即當前樣本相對于輸入數據文件其實點的偏移量， value 是當前樣本各維度的值組成的字符串。輸出：?<key‘,value’> key‘是距離最近簇下標，value’是 樣本點。

reduce 階段：根據map階段的<key,value>重新計算聚類中心,更新聚類中心。輸出：<key.id(下標),新的聚類中心>

? ? ? ? ? ?注：在map階段，減少數據通信，需要在本地map<key,value>做一次conbine(),減少數據大小，具體是根據key，相加value的每個維度，并記錄count。

MapReduce通俗講解

Hadoop就是一個實現了Google云計算系統的開源系統，包括并行計算模型Map/Reduce，分布式文件系統HDFS，以及分布式數據庫Hbase，同時Hadoop的相關項目也很豐富，包括ZooKeeper，Pig，Chukwa，Hive，Hbase，Mahout，flume等.

這里詳細分解這里面的概念讓大家通過這篇文章了解到底是什么hadoop：



1.什么是Map/Reduce，看下面的各種解釋：

(1)MapReduce是hadoop的核心組件之一，hadoop要分布式包括兩部分，一是分布式文件系統hdfs,一部是分布式計算框，就是mapreduce,缺一不可，也就是說，可以通過mapreduce很容易在hadoop平臺上進行分布式的計算編程。

(2)Mapreduce是一種編程模型，是一種編程方法，抽象理論。

(3)下面是一個關于一個程序員是如何個妻子講解什么是MapReduce？文章很長請耐心的看。

我問妻子：“你真的想要弄懂什么是MapReduce？” 她很堅定的回答說“是的”。 因此我問道：

我：?你是如何準備洋蔥辣椒醬的？（以下并非準確食譜，請勿在家嘗試）

妻子：?我會取一個洋蔥，把它切碎，然后拌入鹽和水，最后放進混合研磨機里研磨。這樣就能得到洋蔥辣椒醬了。


妻子：?但這和MapReduce有什么關系？

我：?你等一下。讓我來編一個完整的情節，這樣你肯定可以在15分鐘內弄懂MapReduce.

妻子：?好吧。

我：現在，假設你想用薄荷、洋蔥、番茄、辣椒、大蒜弄一瓶混合辣椒醬。你會怎么做呢？

妻子：?我會取薄荷葉一撮，洋蔥一個，番茄一個，辣椒一根，大蒜一根，切碎后加入適量的鹽和水，再放入混合研磨機里研磨，這樣你就可以得到一瓶混合辣椒醬了。

我：?沒錯，讓我們把MapReduce的概念應用到食譜上。Map和Reduce其實是兩種操作，我來給你詳細講解下。
Map（映射）: 把洋蔥、番茄、辣椒和大蒜切碎，是各自作用在這些物體上的一個Map操作。所以你給Map一個洋蔥，Map就會把洋蔥切碎。 同樣的，你把辣椒，大蒜和番茄一一地拿給Map，你也會得到各種碎塊。 所以，當你在切像洋蔥這樣的蔬菜時，你執行就是一個Map操作。 Map操作適用于每一種蔬菜，它會相應地生產出一種或多種碎塊，在我們的例子中生產的是蔬菜塊。在Map操作中可能會出現有個洋蔥壞掉了的情況，你只要把壞洋蔥丟了就行了。所以，如果出現壞洋蔥了，Map操作就會過濾掉壞洋蔥而不會生產出任何的壞洋蔥塊。


Reduce（化簡）:在這一階段，你將各種蔬菜碎都放入研磨機里進行研磨，你就可以得到一瓶辣椒醬了。這意味要制成一瓶辣椒醬，你得研磨所有的原料。因此，研磨機通常將map操作的蔬菜碎聚集在了一起。

妻子：?所以，這就是MapReduce?

我：?你可以說是，也可以說不是。 其實這只是MapReduce的一部分，MapReduce的強大在于分布式計算。

妻子：?分布式計算？ 那是什么？請給我解釋下吧。

我：?沒問題。

我：?假設你參加了一個辣椒醬比賽并且你的食譜贏得了最佳辣椒醬獎。得獎之后，辣椒醬食譜大受歡迎，于是你想要開始出售自制品牌的辣椒醬。假設你每天需要生產10000瓶辣椒醬，你會怎么辦呢？

妻子：?我會找一個能為我大量提供原料的供應商。

我：是的..就是那樣的。那你能否獨自完成制作呢？也就是說，獨自將原料都切碎？ 僅僅一部研磨機又是否能滿足需要？而且現在，我們還需要供應不同種類的辣椒醬，像洋蔥辣椒醬、青椒辣椒醬、番茄辣椒醬等等。

妻子：?當然不能了，我會雇傭更多的工人來切蔬菜。我還需要更多的研磨機，這樣我就可以更快地生產辣椒醬了。
我：沒錯，所以現在你就不得不分配工作了，你將需要幾個人一起切蔬菜。每個人都要處理滿滿一袋的蔬菜，而每一個人都相當于在執行一個簡單的Map操作。每一個人都將不斷的從袋子里拿出蔬菜來，并且每次只對一種蔬菜進行處理，也就是將它們切碎，直到袋子空了為止。
這樣，當所有的工人都切完以后，工作臺（每個人工作的地方）上就有了洋蔥塊、番茄塊、和蒜蓉等等。

妻子：但是我怎么會制造出不同種類的番茄醬呢？

我：現在你會看到MapReduce遺漏的階段—攪拌階段。MapReduce將所有輸出的蔬菜碎都攪拌在了一起，這些蔬菜碎都是在以key為基礎的 map操作下產生的。攪拌將自動完成，你可以假設key是一種原料的名字，就像洋蔥一樣。 所以全部的洋蔥keys都會攪拌在一起，并轉移到研磨洋蔥的研磨器里。這樣，你就能得到洋蔥辣椒醬了。同樣地，所有的番茄也會被轉移到標記著番茄的研磨器里，并制造出番茄辣椒醬。

（4）上面都是從理論上來說明什么是MapReduce，那么咱們在MapReduce產生的過程和代碼的角度來理解這個問題。
如果想統計下過去10年計算機論文出現最多的幾個單詞，看看大家都在研究些什么，那收集好論文后，該怎么辦呢？?

　　方法一：
? ?? ?我可以寫一個小程序，把所有論文按順序遍歷一遍，統計每一個遇到的單詞的出現次數，最后就可以知道哪幾個單詞最熱門了。 這種方法在數據集比較小時，是非常有效的，而且實現最簡單，用來解決這個問題很合適。?

　方法二：
? ?? ? 寫一個多線程程序，并發遍歷論文。?
　　這個問題理論上是可以高度并發的，因為統計一個文件時不會影響統計另一個文件。當我們的機器是多核或者多處理器，方法二肯定比方法一高效。但是寫一個多線程程序要比方法一困難多了，我們必須自己同步共享數據，比如要防止兩個線程重復統計文件。?

方法三：
? ?? ?把作業交給多個計算機去完成。?
　　我們可以使用方法一的程序，部署到N臺機器上去，然后把論文集分成N份，一臺機器跑一個作業。這個方法跑得足夠快，但是部署起來很麻煩，我們要人工把程序copy到別的機器，要人工把論文集分開，最痛苦的是還要把N個運行結果進行整合（當然我們也可以再寫一個程序）。?

　　方法四：
? ?? ?讓MapReduce來幫幫我們吧！?

　　MapReduce本質上就是方法三，但是如何拆分文件集，如何copy程序，如何整合結果這些都是框架定義好的。我們只要定義好這個任務（用戶程序），其它都交給MapReduce。


map函數和reduce函數　　


map函數和reduce函數是交給用戶實現的，這兩個函數定義了任務本身。?

　　map函數：接受一個鍵值對（key-value pair），產生一組中間鍵值對。MapReduce框架會將map函數產生的中間鍵值對里鍵相同的值傳遞給一個reduce函數。?

　　reduce函數：接受一個鍵，以及相關的一組值，將這組值進行合并產生一組規模更小的值（通常只有一個或零個值）。?

　　統計詞頻的MapReduce函數的核心代碼非常簡短，主要就是實現這兩個函數。?

　　map(String key, String value):?

　　// key: document name?

　　// value: document contents?

　　for each word w in value:?

　　EmitIntermediate(w, "1");?

　　reduce(String key, Iterator values):?

　　// key: a word?

　　// values: a list of counts?

　　int result = 0;?

　　for each v in values:?

　　result += ParseInt(v);?

　　Emit(AsString(result));?

　　在統計詞頻的例子里，map函數接受的鍵是文件名，值是文件的內容，map逐個遍歷單詞，每遇到一個單詞w，就產生一個中間鍵值對<w, "1">，這表示單詞w咱又找到了一個；MapReduce將鍵相同（都是單詞w）的鍵值對傳給reduce函數，這樣reduce函數接受的鍵就是單詞w，值是一串"1"（最基本的實現是這樣，但可以優化），個數等于鍵為w的鍵值對的個數，然后將這些“1”累加就得到單詞w的出現次數。最后這些單詞的出現次數會被寫到用戶定義的位置，存儲在底層的分布式存儲系統（GFS或HDFS）。?



工作原理

?

　　上圖是論文里給出的流程圖。一切都是從最上方的user program開始的，user program鏈接了MapReduce庫，實現了最基本的Map函數和Reduce函數。圖中執行的順序都用數字標記了。

　　1.MapReduce庫先把user program的輸入文件劃分為M份（M為用戶定義），每一份通常有16MB到64MB，如圖左方所示分成了split0~4；然后使用fork將用戶進程拷貝到集群內其它機器上。?

　　2.user program的副本中有一個稱為master，其余稱為worker，master是負責調度的，為空閑worker分配作業（Map作業或者Reduce作業），worker的數量也是可以由用戶指定的。?

　　3.被分配了Map作業的worker，開始讀取對應分片的輸入數據，Map作業數量是由M決定的，和split一一對應；Map作業從輸入數據中抽取出鍵值對，每一個鍵值對都作為參數傳遞給map函數，map函數產生的中間鍵值對被緩存在內存中。?

　　4.緩存的中間鍵值對會被定期寫入本地磁盤，而且被分為R個區，R的大小是由用戶定義的，將來每個區會對應一個Reduce作業；這些中間鍵值對的位置會被通報給master，master負責將信息轉發給Reduce worker。?

　　5.master通知分配了Reduce作業的worker它負責的分區在什么位置（肯定不止一個地方，每個Map作業產生的中間鍵值對都可能映射到所有R個不同分區），當Reduce worker把所有它負責的中間鍵值對都讀過來后，先對它們進行排序，使得相同鍵的鍵值對聚集在一起。因為不同的鍵可能會映射到同一個分區也就是同一個Reduce作業（誰讓分區少呢），所以排序是必須的。?

　　6.reduce worker遍歷排序后的中間鍵值對，對于每個唯一的鍵，都將鍵與關聯的值傳遞給reduce函數，reduce函數產生的輸出會添加到這個分區的輸出文件中。?

　　6.當所有的Map和Reduce作業都完成了，master喚醒正版的user program，MapReduce函數調用返回user program的代碼。?

　　所有執行完畢后，MapReduce輸出放在了R個分區的輸出文件中（分別對應一個Reduce作業）。用戶通常并不需要合并這R個文件，而是將其作為輸入交給另一個MapReduce程序處理。整個過程中，輸入數據是來自底層分布式文件系統（GFS）的，中間數據是放在本地文件系統的，最終輸出數據是寫入底層分布式文件系統（GFS）的。而且我們要注意Map/Reduce作業和map/reduce函數的區別：Map作業處理一個輸入數據的分片，可能需要調用多次map函數來處理每個輸入鍵值對；Reduce作業處理一個分區的中間鍵值對，期間要對每個不同的鍵調用一次reduce函數，Reduce作業最終也對應一個輸出文件。

轉載于:https://www.cnblogs.com/AcceptedLin/p/9525729.html

總結

以上是生活随笔為你收集整理的Hadoop平台K-Means聚类算法分布式实现+MapReduce通俗讲解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。