一文通俗理解大數據分析演算法的并行化

文 / 曾劍平

大數據分析所面對的數據量通常是巨大的，由此帶來了高計算複雜度的問題。以往主要針對單機系統而設計的分析演算法就難於在可接受的時間內完成任務，面向大數據分析處理的并行化分析演算法就很有必要了。本文以通俗的語言和例子解釋了大數據并行方法，描述了Kmeans并行化的原理。（關注微信公眾號 IntBigData "互聯網大數據處理技術與應用"獲得更多互聯網大數據技術介紹。）

一、數硬幣

在投幣乘車的年代里，公交公司每天會收到大量的硬幣，假如公司要數一下某一天收到的硬幣中一角、五角、一元三種硬幣的個數。

問題本身很簡單，三歲小孩都能區分這些硬幣，但問題是硬幣數量太大，一個工作人員來數要花多少時間? 假如每分鐘能區分60個硬幣，5萬個硬幣就需要數10幾個小時。

顯然，可以讓多個工作人員一起數，有兩種方法。一是，讓所有工作人員圍著這堆硬幣數；另一種方法是把這堆硬幣大概平均分一下，每個人自己去數。

前一種方法看起來很好，但是有的人在數數時，喜歡「1、2、3...」地發聲來數，從而嚴重干擾其他人。所以第二種是不錯的選擇。每個人數完之後，報告給公司老闆，老闆把每個人一角、五角、一元三種硬幣的個數分別加一下就可以得到結果。這樣，如果5個人來數，那麼兩個多小時就可以完成任務了。這種數法就是并行化方法。

同樣，大數據分析計算方法也採取類似的思路。在目前的計算平台中，并行化大都以Map Reduce為計算框架，每個人就相當於這個計算框架中的一台計算機，獨立完成任務。當然這種計算框架為了能更具有普遍適應性，就對參與計算的所有計算機進行了適當組織。

還是以數硬幣為例，儘管對硬幣進行了大概的平均分配，但總是有人快有人慢，老闆如果都要在現場等結果就不太合理了。因此，可以對這種人員結構做個調整，比如設置三個小組長A、B、C，分別負責匯總一角、五角、一元三種硬幣個數，等收齊后再報告老闆。

這樣，員工數完之後，需要把結果報告給不同的組長，即一角的個數報告給A，五角的個數報告給B，一元的個數報告給C。任務分工也很清晰。

上述過程其實就是Map Reduce的計算原理，員工是Map節點，組長是Reduce節點，老闆負責分配和記錄最終結果，是總控。

二、Kmeans的并行化

Kmeans是數據聚類中經典方法之一，在上述Map Reduce框架中，其并行化方法如圖所示。

步驟說明如下：

1. 對輸入的數據集進行分割，老闆按照一定原則分給各個計算節點（員工），並隨機選擇聚類的初始中心。

2. 每個計算節點負責分給自己的所有數據樣本，對每個樣本計算與每個聚類中心的距離，記錄每個樣本的最近中心，即（樣本、最近中心）。

3. 每個計算節點完成後，按照中心與樣本的對應關係，將樣本數據傳給相應的小組長。

4. 這樣每個小組長負責一個類，在收到所有樣本數據后，對這些數據計算新的中心。

5. 每個小組長將計算結果（類中心）報告給老闆，老闆根據Kmeans的收斂條件判斷是否要進行第2-4步驟迭代，直到完成任務。

下圖是傳統實現方法和并行化方法在性能上的對比關係，可以看出，隨著數據樣本數量的增加，傳統方法的時間消耗增加得很快。

當然由於Kmeans演算法的特點，可以簡單地將數據集進行分割，而在一些複雜的問題中，有時候要找到數據分割方法並不容易，需要先做一定的分解。在互聯網大數據分析應用中，頁面關係、用戶關係、位置聯繫等等許多問題都可以抽象為矩陣運算，對於矩陣相乘這個大數據基礎演算法的并行化就很關鍵，具體計算方法就難於在這裡展開了。在我編著的《互聯網大數據處理技術與應用》一書中，一章描述了數據挖掘的經典演算法及其并行化方法，分析了矩陣相乘并行化所需要考慮的關鍵因素，包括數據存儲、矩陣數據在網路上的傳輸量、稀疏矩陣，稠密矩陣等許多問題。點擊原文鏈接查看專著介紹。