大數據背景下機器學習并行算法研究

馬巍巍 殷鳳梅 張江

摘要 面對海量、多樣變化的大數據，基于小數據的傳統機器學習算法計算負擔的困難日益顯現，并行計算是解決這一問題的主流方法。闡述了大數據環境下的機器學習研究現狀;在此基礎上，分析梳理了當前大數據下機器學習并行算法的關鍵技術;最后對其發展前景進行了展望。

[關鍵詞]機器學習算法 并行計算 大數據

1 引言

大數據時代已經來臨。最早提出這一概念的是全球知名咨詢公司麥肯錫，麥肯錫稱：“數據，已經滲透到當今每一個行業和業務職能領域，成為重要的生產因素。人們對于海量數據的挖掘和運用，預示著新一波生產率增長和消費者盈余浪潮的到來?！蔽覀兯信d趣的是大數據中所隱含的相較小型數據所不具備的大量未知的知識和價值，通過數據挖掘分析，它們能為社會帶來巨大的商業價值，實現多種高附加值的增值服務，讓人們的生活更加方便快捷。

機器學習和數據分析是將大數據轉換成有用知識的關鍵技術，并且有研究表明，在很多情況下，處理的數據規模越大，機器學習模型的效果會越好。因此，機器學習是大數據智能化分析處理應用中的重要手段。在大數據背景下，計算數據量級己升至TB級或PB級，這對傳統機器學習帶來了挑戰和機遇。機器學習算法本身含有大量的迭代計算，非常適用于并行化。目前，對大數據機器學習并行化研究己成為應對大數據應用需求的熱點研究方向。

本文首先介紹了大數據的內涵和機器學習算法的主要問題;然后重點分析總結了目前處理大數據機器學習的并行方法;最后闡述了大數據時代機器學習并行算法發展趨勢。

2 大數據與機器學習

2.1 大數據內涵

大數據的含義是由人類日益普及的網絡行為所伴生的，它被相關部門、企業按照某種意圖收集的多源異構、動態多變的數據。過去只有公司或科研機構才擁有數據;而現在，我們每個人都是數據的生產者，同時也是數據的消費者。根據美國互聯網數據中心的數據顯示互聯網上的數據每年將增長50%，每兩年便將翻一番，而目前世界上90%以上的數據是最近幾年才產生的。

目前在各行各業均存在大數據，然而大數據并不僅僅是指數量龐大的數據。它的真正含義是指數據一定有被學習算法利用的價值，也就是說除了數據量大外，還包含著挖掘這些數據價值的新的技術。由于大數據研究的重要性，在產業界和學術界受到了空前的關注，2012年，美國政府宣布將“大數據戰略”上升為國家戰略。我國也把大數據列為重大研究課題。

目前業界普遍認可大數據具有的5V特征是由IBM提出的，即：Volume（大量）、Velocity（高速）、Variety（多樣）、Value（價值密度）、Veracity（真實性）。具體見圖1。

2.2 大數據下的機器學習

機器學習即讓機器自己學習問題解決的算法，是目前信息技術領域中最受關注的方向之一。它涉及的內容非常廣泛，如機械應用中的無人駕駛汽車，瀏覽新聞時自動跳出你最近經?？吹南嚓P內容，生物學中的人類基因組分類等各個行業和基礎科學中都有著機器學習算法的身影。

傳統的機器學習主要包括四個方面：人類的學習過程的理解和模擬;研究計算機系統與人類用戶之間的自然語言接口;問題的推理能力，自動規劃設計能力;設計可發現新事物的程序。

針對大數據的5V特性，機器學習算法不僅僅解決數據庫方面的問題，它還必須智能化。在構建機器學習算法時，我們需要實現兩個任務：

（1）在訓練數據時，我們需要求解優化問題以及存儲和處理海量數據的高效算法。

（2）一旦習得了某種模型，它的表示和用于推理的算法解也必須是高效的。

在機器學習特定的應用中，算法的空間復雜度和時間復雜度，或者說算法的效率是和算法的準確率同樣重要的問題。傳統的機器學習算法大多是串行的，在數據量、數據維度不斷地增長的情況下，單機的存儲容量和運行時長都是無法忍受的。在這種情況下，考慮將算法并行化是一個非常自然的想法。研究人員開始尋求新的算法以及計算平臺加速大數據的運算。

3 大數據并行算法

為適應大數據處理的特征要求，學術界和產業界正在進行各種研究和探索，開發并行計算模型。目前，處理大數據機器學習的并行方法主要有分布式并行計算、多核異構計算平臺和以上兩種方式混合的并行計算。

3.1 分布式并行

早期的分布式并行計算需要大量復雜的通信、同步以及調度等并發控制操作，例如較流行的分布式存儲體系結構的MPI （MessagePassing Interface，消息傳遞接口），在提升計算性能方面也取得了很多成果，但也出現了很多問題。其中最主要的問題是隨著系統的復雜化和大數據的處理要求，管理和維護困難，并且硬件費用和運行成本高昂，因此一直局限于國家大型機構或實驗室應用，很難推廣。

以MapReduce /Hadoop為代表的大規模數據分布式并行計算模型能改善這一狀況。MapReduce是一個基于集群的高性能并行計算平臺，最早由谷歌公司研究提出，后基于Java設計開發的Hadoop開源實現后，已經成為事實上的大數據處理的工業標準。目前MapReduce己在數據挖掘、機器學習、圖形圖像處理等眾多領域實現應用。MapReduce提供了抽象的操作和并行編程接口，執行階段由Map和Reduce兩個函數編程實現，降低了并行編程難度，方便完成大規模數據的編程和計算處理。為提高并行效率，目前國內外的學者對MapReduce做了大量的優化研究工作。

Spark是繼Hadoop之后的新一代大數據分布式處理框架，由UC Berkeley的Mateaaharia主導開發。Spark架構較新，它啟用了內存分布數據集，對于需要多次迭代使用的數據保存在分布式內存中，省去大量的磁盤讀寫操作，縮短訪問延遲。同時，Spark提供了更為通用和靈活的操作接口，降低了編程難度。因此對于有較多迭代運算的機器學習算法，Spark平臺明顯比Hadoop有著顯而易見的優勢。國內外學者對此進行了相關研究并取得了相關的結論。文獻[6]實驗結果表明對于機器學習中的K-means聚類算法，改進后的基于Spark的并行加速比要優于Hadoop平臺，并且數據量增大時，并行計算效果更好。

另外，Spark和Hadoop都是面向批處理的并行計算模型，然而在大數據應用中，我們還需要處理基于數據流的數據挖掘。數據流應用要求低延遲，以保證數據價值的時效性。Spark提供了大量的庫，其中Spark Streaming可以實現高吞吐量的、具備容錯機制的實時流數據的處理。它的處理方式是首先接收實時流數據，按規定的時間間隔拆分數據，最后通過Spark Engine得到處理后的結果。文獻[7]實現了基于Spark Streaming的KMeans數據流聚類算法，其吞吐能力等運行性能表現優異，但還存在大量可以優化的方面。

3.2 多核異構計算平臺

近年來，多核異構的并行編程模型不斷涌現。由于其具有低成本高性能，且降低并行編程難度的優勢，目前在加速算法方面得到了廣泛的使用。目前較多的異構計算發生在CPU+GPU平臺上，早期的GPU （GraphicsProcessing Unit，圖形處理器）主要目標是處理圖運算工作，而現在GPU在通用計算方面的能力已經顯現，并行計算方面，GPU可以提供數十倍乃至于上百倍相較CPU的性能。GPU通用計算方面的標準目前有OPENCL、CUDA和ATI STREAM。文獻[8]基于GPU平臺提出一種并行冒泡的新型KNN并行算法，分別使用兩種異構編程模型實驗，結果表明改進后的使用OPENCL并行算法比未改進的使用CUDA并行算法快16倍。文獻[9]在深度神經網絡的計算中基于GPU并行計算，取得了較好的實驗效果。

此外CPU+FPGA異構平臺也引起了研究人員的關注，FPGA （Field Programmable GateArray，FPGA現場可編程門陣列）具有低功耗，高吞吐量等優點，利用芯片中的眾多邏輯門同時進行邏輯運算實現高度并行計算。文獻[10]基于FPGA對機器學習K-means算法優化，實驗顯示與基于Spark框架的8核心CPU平臺相比，FPGA異構平臺的計算性能最高提升4.4倍。文獻[11]對以上兩種并行平臺均進行了實驗，并與串行方式進行比較，結果都有較大提升。

3.3 混合方式

上述兩種并行方式對計算性能的提升都有很大幫助，但也存在著各自的問題。例如GPU的運算能力遠超CPU，但是GPU集群對大數據的存儲能力不足;而分布式MapReduce架構在大量不斷的優化下，易于擴展、性價比高，但對于復雜大數據的處理性能不佳。鑒于此，國內外學者開始嘗試以混合兩種方式來提升機器學習并行算法。

文獻[12]采用MapReduce與GPU集群混合的方法，并細致的描述了這種方法的計算有效性。當然，除此之外，還存在很多有效的混合方式，如文獻[13]實現了基于MPI的GPU并行通信系統，文獻[14]則討論了三級并行編程環境CUDA+MPI+OpenMP的快速搭建以及多粒度混合并行編程方法，這些方法的實現為并行平臺的多樣化發展提供了有益的借鑒。

4 結論

并行平臺能有效改善高性能計算系統的性能瓶頸和海量數據存儲問題，同時也帶來了大量的研究挑戰。隨著基礎硬件資源的不斷更新發展，以及物聯網、云計算等的興起，決定了并行計算模型的多樣化和應用性。目前并行計算模型的的研究已經展開，但仍在摸索階段，有很多大量關鍵的問題等待解決完善。在大數據背景下，針對具體的應用場景，設計出更加高效地并行算法完成數據挖掘任務，滿足實際應用的需求，是未來所要努力的方向。

參考文獻

[1]黃宜華.大數據機器學習系統研究進展[J]，大數據，2015，TOPIC專題，

[2]何清，李寧等，大數據下機器學習算法綜述[J].模式識別與人工智能，2014， 27 （04）： 327-337.

[3]（土）阿培?。ˋlpaydin，E.）著，范明譯，機器學習導論（原書第3版）[M].北京：機械工業出版牡，2015：2.

[4] CHEN L， AGRAWAL G. Optimizing MapReducefor GPUs with effective shared memoryusage[C]. proceeding of the 21stinternational symposium on High-Performace Parallel and DistributedComputing （HDPC2012）.

[5] Apache Spark Project [EB/OL].[2016-03-20]. http：，/spark. apache. org/mllib/.

[6]孟建良，劉德超，一種基于Spark和聚類分析的辨識電力系統不良數據新方法…，電力系統保護與控制，2016，44 （03）：85-91.

[7]唐振坤，基于Spark的機器學習平臺設計與實現[D].廈門大學，2014.

[8]賀江，蒲宇亮，李海波等.一種基于OpenCL的高能效并行KNN算法及其GPU驗證[J]，電子技術應用，2016，42 （02）：14-16.

[9] Seide F，Fu H，Droppoj， et al. l-bittochastic gradient descent andits application to data-paralleldistributed training of speechDNNs [C]. Interspeech.2 014： 1058-1062.

[10]胡雷鈞，龐松，朱炯等，基于FPGA的大數據K-means算法優化[J].電力信息與通信技術，2016，14 （08）：1—6.

[11]黃海洋，面向大數據的CPU_GPU_FPGA計算平臺研究[D].成都：電子科技大學，2017.

[12]徐順茍.GPU計算在大數據處理中的應用[D].蘭州大學，201 5.

[13]侯景德，陳慶奎等，基于MPI的GPU集群并行通信系統實現[J].計算機應用與軟件，2016，33 （04）116-121.

[14]滕人達，劉青昆.CUDA、MPI和OpenMP三級混合并行模型的研究[J].微計算機應用，2010，31（09）：63-69.