大資料分析：機器學習算法實作的演化

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

傳統的機器學習和資料分析的工具，包括sas，ibm的spss，weka以及r語言。它們可以在小資料集上進行深度分析——工具所運作的節點的記憶體可以容納得下的資料集。

第二代機器學習工具，包括mahout，pentaho，以及rapidminer。它們可以對大資料進行我稱之為粗淺的分析。基于hadoop之上進行的傳統機器學習工具的規模化的嘗試，包括revolution analytics的成果(rhadoop)以及hadoop上的sas，都可以歸到第二代工具裡面。

第三代工具，比如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，它用于資料處理。它們在流上進行運算。基于流的機器學習算法通常都在這裡運作。

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

在實踐中，一個架構如果同時包含了kafka（來自linkedin的一個分布式隊列系統）叢集來作為高速的資料提取器，以及storm叢集來進行處理或者分析，它的表現會非常不錯，kafka spout用來快速地從kafka叢集中讀取資料。kafka叢集将事件存儲在隊列中。由于storm叢集正忙于進行機器學習，是以這麼做是很有必要 的。本書的後續章節将會對這個架構進行詳細的介紹，以及在storm叢集中運作機器學習算法所需的步驟。storm也被拿來跟實時計算領域的其它競争者進行比較，包括yahoo的s4以及typesafe的akka。