大數據分析：機器學習算法實現的演化

我將會對機器學習算法的不同的實現范式進行講解，既有來自文獻中的，也有來自開源社區里的。首先，這里列出了目前可用的三代機器學習工具。

1. 傳統的機器學習和數據分析的工具，包括SAS，IBM的SPSS，Weka以及R語言。它們可以在小數據集上進行深度分析——工具所運行的節點的內存可以容納得下的數據集。

2. 第二代機器學習工具，包括Mahout，Pentaho，以及RapidMiner。它們可以對大數據進行我稱之為粗淺的分析?；?a href='/map/hadoop/' style='color:#000;font-size:inherit;'>Hadoop之上進行 的傳統機器學習工具的規?；膰L試，包括Revolution Analytics的成果(RHadoop)以及Hadoop上的SAS，都可以歸到第二代工具里面。

3. 第三代工具，比如Spark, Twister，HaLoop，Hama以及GraphLab。它們可以對大數據進行深度的分析。傳統供應商最近的一些嘗試包括SAS的內存分析，也屬于這一類。

第一代機器學習工具/范式

由于第一代工具擁有大量的機器學習算法，因此它們適合進行深度的分析。然而，由于可擴展性的限制，它們并不都能在大數據集上進行工作——比如TB或者PB 級的數據（受限于這些工具本質上是非分布式的）。也就是說，它們可以進行垂直擴展（你可以提高工具運行的節點的處理能力），但無法進行水平擴展（它們并非 都能在集群上運行）。第一代工具的供應商通過建立Hadoop連接器以及提供集群選項來解決這些局限性——這意味著它們在努力對R或者SAS這樣的工具進 行重新設計以便可以進行水平擴展。這些都應該歸入第二代和第三代工具，下面我們將會介紹到。

第二代機器學習工具/范式

第二代工具（現在我們可以把傳統的機器學習工具比如SAS這些稱之為第一代工具了）比如 Mahout（http://mahout.apache.org），Rapidminer以及Pentaho，它們通過在開源的MapReduce產品 ——Hadoop之上實現相關算法，提供了擴展到大數據集上的能力。這些工具仍在快速完善并且是開源的（尤其是Mahout）。Mahout擁有一系列的 聚類及分類的算法，以及一個相當不錯的推薦算法（Konstan和Riedl，2012）。因此它可以進行大數據的處理，現在在生產環境上已經有大量的使 用案例，主要用于推薦系統。我在一個線上系統中也使用Mahout來實現了一個金融領域的推薦算法，發現它確是可擴展的，盡管并不是一點問題沒有（我還修 改了相當一部分代碼）。關于Mahou的一項評測發現它只實現了機器學習算法中的很小的一個子集——只有25個算法是達到了生產質量的，8到9個在 Hadoop之上可用，這意味著能在大數據集上進行擴展。這些算法包括線性回歸，線性支持向量機，K-means聚類算法，等等。它通過并行訓練，提供了 順序邏輯回歸的一個快速的實現。然而，正如別人指出的（比如Quora.com），它沒有實現非線性支持向量機以及多變項邏輯回歸（這也稱為離散選擇模 型）。

畢竟來說，本書并不是要為了抨擊Mahout的。不過我認為有些機器學習算法的確是很難在Hadoop上實現，比如支持向量機的核函數以及共軛梯度法 （CGD，值得注意的是Mahout實現了一個隨機梯度下降）。這一點別人也同樣指出了，比方說可以看一下Srirama教授的一篇論文（Srirama 等人，2012年）。這里詳細地比較了Hadoop和Twister MR（Ekanayake
等，2010年）在諸如共軛梯度法等迭代式算法上的不同，它指出，Hadoop上的開銷非常明顯。我所說的迭代式是指什么？一組執行特定計算的實體，在等待鄰居或者其它實體的返回結果，然后再進行下一輪迭代。CGD是迭代式算法的最佳范例——每個CGD都可以分解成daxpy,ddot，matmul等原語。我會分別解釋這三種原語都是什么：daxpy操作將向量x與常量k相乘，然后再和另一個向量y進行相加；ddot會計算兩個向量x,y的點積;matmul將矩陣與向量相乘，然后返回另一個向量。這意味著每個操作對應一個MapReduce操作，一次迭代會有6個MR操作，最終一次CG運算會有100個MR操作，以及數GB的數據交互，盡管這只是很小的矩陣。事實上，準備每次迭代的開銷（包括從HDFS加載數據到內存的開銷）比迭代運算本身的都大，這導致Hadoop上的MR會出現性能下降。相反，Twister會區分靜態數據和可變數據，使得數據可以在MR迭代過程中常駐內存，同時還有一個合并階段來收集reduce階段輸出的結果，因此性能有明顯的提升。

第二代工具還有一些是傳統工具基于Hadoop上進行的擴展。這類可供選擇的有Revolution Analytics的產品，它是在Hadoop上對R語言進行了擴展，以及在Hadoop上實現R語言程序的一個可擴展的運行時環境（Venkataraman等
，2012）。SAS的內存分析，作為SAS的高性能分析工具包中的一部分，是傳統工具在Hadoop集群上進行規?；牧硪粋€嘗試。然而，最近發布的版本不僅能在Hadoop上運行，同時也支持Greenplum/Teradata，這應該算作是第三代機器學習的方法。另一個有趣的產品是一家叫Concurrent Systems的初創公司實現的，它提供了一個預測模型標記語言（Predictive Modeling Markup Language，PMML）在Hadoop上的運行環境。PMML的模型有點類似XML，使得模型可以存儲在描述性語言的文件中。傳統工具比如 R以及SAS都可以將模型保存在PMML文件里。Hadoop上的運行環境使得它們可以將這些模型文件存儲到一個Hadoop集群上，因此它們也屬于第二代工具/范式。

第三代機器學習工具/范式

Hadoop自身的局限性以及它不太適合某類應用程序，這促進研究人員提出了新的替代方案。第三代工具主要是嘗試超越Hadoop來進行不同維度的分析。我將會根據三種維度來討論不同的實現方案，分別是機器學習算法，實時分析以及圖像處理。

迭代式機器學習算法

伯克利大學的研究人員提出了一種替代方案：Spark（Zaharia等，2010年）——也就是說，在大數據領域，Spark被視為是替換Hadoop的下一代數據處理的解決方案。Spark有別于Hadoop的關鍵思想在于它的內存計算，這使得數據可以在不同的迭代和交互間緩存在內存里。研發Spark的主要原因是，常用的MR方法，只適用于那些可以表示成無環數據流的應用程序，并不適用于其它程序，比如那些在迭代中需要重用工作集的應用。因此他們提出了這種新的集群計算的方法，它不僅能提供和MR類似的保證性和容錯性，并且能同時支持迭代式及非迭代式應用。伯克利的研究人員提出了一套技術方案叫作BDAS，它可以在集群的不同節點間運行數據分析的任務。BDAS中最底層的組件叫做Mesos，這是個集群管理器，它會進行任務分配以及集群任務的資源管理。第二個組件是基于Mesos構建的Tachyon文件系統 。Tachyon提供了一個分布式文件系統的抽象以及在集群間進行文件操作的接口。在實際的實施方案中，作為運算工具的Spark，是基于Tachyon和Mesos來實現的，盡管不用Tachyon，甚至是不用Mesos也可以實現。而在Spark基礎上實現的Shark，則提供了集群層面的結構化查詢 語言的抽象——這和Hive在Hadoop之上提供的抽象是一樣的。Zacharia等人在他們的文章中對Spark進行了探索，這是實現機器學習算法的重要組成部分。

HaLoop（Bu等人，2010）也擴展了Hadoop來實現機器學習算法——它不僅為迭代式應用的表示提供了一層編程抽象，同時還使用了緩存的概念來 進行迭代間的數據共享，以及對定點進行校驗，從而提高了效率。Twister( http://iterativemapreduce.org )是類似HaLoop的一個產品。

實時分析

實時分析是超越Hadoop考慮的第二個維度。來自Twitter的Storm（感覺原文說反了）是這一領域的最有力的競爭者。Storm是一個可擴展的復雜事件處理引擎，它使得基于事件流的實時復雜運算成為了可能。一個Storm集群的組件包括：  

Spout，用于從不同的數據源中讀取數據。有HDFS類型的spout，Kafka類型的spout，以及TCP流的spout。

Bolt，它用于數據處理。它們在流上進行運算?；诹鞯?a href='/map/jiqixuexi/' style='color:#000;font-size:inherit;'>機器學習算法通常都在這里運行。

拓撲。這是具體應用特定的spout和bolt的一個整合——拓撲運行于集群的節點上。

在實踐中，一個架構如果同時包含了Kafka（來自LinkedIn的一個分布式隊列系統）集群來作為高速的數據提取器，以及Storm集群來進行處理或 者分析，它的表現會非常不錯，Kafka spout用來快速地從Kafka集群中讀取數據。Kafka集群將事件存儲在隊列中。由于Storm集群正忙于進行機器學習，因此這么做是很有必要 的。本書的后續章節將會對這個架構進行詳細的介紹，以及在Storm集群中運行機器學習算法所需的步驟。Storm也被拿來跟實時計算領域的其它競爭者進 行比較，包括Yahoo的S4以及Typesafe的Akka。