《大資料算法》一1.2 大資料算法

本節書摘來華章計算機《大資料算法》一書中的第1章 ，第1.2節，王宏志　編著, 更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

這一節我們概述大資料算法。

首先我們看一看在大資料上問題求解的過程。我們面對的是一個計算問題，也就是說我們要用計算機來處理一個問題。

拿到一個計算問題之後，首先需要判定這個問題是否可以用計算機進行計算，如果學習過可計算性理論，就可以了解有許多問題計算機是無法計算的，比如判斷一個程式是否有死循環，或者是否存在能夠殺所有病毒的軟體，這些問題都是計算機解決不了的。從“可計算”的角度來看，大資料上的判定問題和普通的判定問題是一樣的，也就是說，如果還是用我們今天的電子計算機模型，即圖靈機模型，在小資料上不可計算的問題，在大資料上肯定也不可計算。計算模型的計算能力是一樣的，隻不過是算得快慢的問題。

那麼，大資料上的計算問題與傳統的計算問題有什麼本質差別呢？

第一個不同之處是資料量，就是說處理的資料量要比傳統的資料量大。第二個不同之處是有資源限制，就是說資料量可能很大，但是能真正用來處理資料的資源是有限的，這個資源包括cpu、記憶體、磁盤、計算所消耗的能量。第三個不同之處是對計算時間存在限制，大資料有很強的實時性，最簡單的一個例子是基于無線傳感網的森林防火，如果能在幾秒之内自動發現有火情發生，這個資訊是非常有價值的，如果三天之後才發現火情，樹都燒完了，這個資訊就沒有價值，是以說大資料上的計算問題需要有一個時間限制，即到底需要多長時間得到計算結果才是有價值的。判定能否在給定資料量的資料上，在計算資源存在限制的條件下，在時間限制内完成計算任務，是大資料上計算的可行性問題，需要計算複雜性理論來解決，然而，目前面向大資料上的計算複雜性理論研究還剛剛開始，有大量的問題需要解決。

注意：在本書中，有的算法可能很簡單，寥寥幾行就結束了，然而後面的分析卻長達幾頁。這本書花更大的精力講授算法分析，是因為在大資料上進行算法設計的時候，要先分析清楚這個算法是否适用于大資料的情況，然後才能使用。

本書讨論的主要内容是大資料上算法的設計與分析，即設計大資料上的算法并且加以分析。

特别值得說明的一點是，對于大資料上的算法，算法分析顯得尤為重要，這是為什麼呢？對于小資料上的算法可以通過實驗的方法來測試性能，實驗可以很快得到結果，但是在大資料上，實驗就不是那麼簡單了，經常需要成千上萬的機器才能夠得出結果。為了避免耗費如此高的計算成本，大資料上的算法分析就十分重要了。

經過算法設計與分析，得到了算法。接着需要用計算機語言來實作算法，得到的是一些程式子產品，下一步用這些程式子產品建構軟體系統。這些軟體系統需要相應的平台來實作，比如常說的hadoop、spark都是實作軟體系統的平台。

上面的叙述可以歸納為圖1-1，從中可以看到，大資料算法與分析在整個大資料問題求解過程中扮演着一個核心的角色，因而本書将對此重點介紹。

1.大資料算法是什麼

根據大資料上的計算過程可以定義大資料算法的概念，如定義1-1所示。

定義1-1(大資料算法)　在給定的資源限制下，以大資料為輸入，在給定時間限制内可以計算出給定問題結果的算法。

這個定義和傳統的算法有一樣的地方，首先大資料算法也是一個算法，有輸入有輸出；而且算法必須是可行的，也必須是機械執行的計算步驟。

補充知識：算法的定義

定義a-1(計算)　可由一個給定計算模型機械地執行的規則或計算步驟序列稱為該計算模型的一個計算。

定義a-2(算法)　算法是一個滿足下列條件的計算：

1) 有窮性/終止性：有限步内必須停止；

2) 确定性：每一步都是嚴格定義和确定的動作；

3) 可行性：每一個動作都能夠被精确地機械執行；

4) 輸入：有一個滿足給定限制條件的輸入；

5) 輸出：滿足給定限制條件的結果。

第一個不同之處是，大資料算法是有資源限制的，這意味着資源不是無限的，可能在100kb資料上可行的算法在100mb的資料上不可行，最常見的一個錯誤是記憶體溢出。這意味着進行大資料處理的記憶體資源不足，是以在大資料算法的設計過程中，資源是一個必須考慮的限制。第二個不同之處是，大資料算法以大資料為輸入，而不是以傳統資料的小規模為輸入。第三個不同之處是，大資料算法需要在時間限制之内産生結果，因為有些情況下過了時間限制大資料會失效，有些情況下超過時間限制的計算結果沒有價值。

2.大資料算法可以不是什麼

有了大資料作為輸入和運作時間作為限制，大資料算法和傳統算法就有了明确的差別。

第一，大資料算法可以不是精确算法。因為有些情況下，能夠證明對于給定的資料輸入規模和資源限制，确實不可能得到精确解。

第二，大資料算法可以不是記憶體算法。由于資料量很大，在很多情況下，把所有資料都放在記憶體中幾乎不可能，因為對于現在的pc來說，記憶體的規模在gb級，對于高檔一些的并行機和伺服器來說記憶體也就是tb級，這個規模對于許多應用中的資料量是遠遠不夠的，必須使用外存甚至于網絡存儲。是以，大資料算法可以不僅僅在記憶體中運作。

第三，大資料算法可以不是串行算法。有的時候，單獨一台計算機難以處理大規模資料，需要多台機器協同并行計算，即并行算法。一個典型的例子是google公司中的計算，為了支援搜尋引擎，google公司需要處理大規模來自網際網路的資料，因而大資料裡面的很多重要概念是google提出的，例如并行平台mapreduce。google公司的資料規模太大，再好的機器也無法獨自處理，需要用成千上萬台機器構成一個機群來并行處理。

第四，大資料算法可以不是僅在電子計算機上運作的算法。有時對于某些任務而言，讓計算機處理很複雜，而讓人做很簡單。對于這些問題，可以讓人和計算機一起來做，是以就有了人和計算機協同的算法。

而傳統算法分析與設計課程中的算法，主要是記憶體算法、精确算法、串行算法且完全在電子計算機上執行，這和本書中的大資料算法不同。

3.大資料算法不僅僅是什麼

下面從大資料概念出發，澄清一些大資料算法的片面觀點。

第一，大資料算法不僅僅是基于mapreduce的算法。講到大資料算法，可能有很多人就會想到mapreduce，mapreduce上的算法确實在很多情況下适用于大資料，而且更确切說mapreduce上的算法是一類很重要的大資料算法，但是大資料算法不僅是mapreduce上的算法。

第二，大資料算法不僅僅是雲計算平台上的算法。說到大資料算法，很多人可能會想到雲計算，雲上的算法是不是大資料算法呢？雲上的算法不全是大資料算法，有的算法不是面向大資料的，例如安全性相關的算法和計算密集型算法，而且大資料算法也不都是雲上的算法，大資料算法有的可以是單機的，甚至可以是手機或者傳感器這種計算能力很差的裝置。

第三，大資料算法不僅僅是資料分析與挖掘中的算法。分析與挖掘是大資料中比較熱的概念，也确實是大資料的重要方面。之是以用得比較多，是因為其商業價值比較明顯。然而，大資料的應用除了需要分析與挖掘，還有擷取、清洗、查詢處理、可視化等方面，這些都需要大資料算法的支援。

第四，大資料算法不僅僅是資料庫中的算法。提到大資料，自然會聯想到這是和資料管理密切相關的。大資料算法是否等同于資料庫中的算法呢？不完全是這樣，雖然資料庫中的算法是大資料算法的一個重要組成部分，今天進行大資料算法研究的多是資料庫和資料管理研究領域的專家，但是不全是資料庫領域的。目前研究大資料算法的專家，有的研究背景是數學理論和算法理論，還有的來自機器學習和各種大資料應用的研究領域。是以大資料算法不僅僅是資料庫中的算法，還有專門為大資料設計的算法。

大資料的特點決定了大資料算法的設計方法。正如前面所介紹的，大資料的特點通常用四個v來描述。這四個v裡面和大資料算法密切相關的，有兩個v。一個是資料量(volume)大，也就是大資料算法必須處理足夠大的資料量。另一個是速度(velocity)，速度有兩方面:①大資料的更新速度很快，相應的大資料算法也必須考慮更新算法的速度；②要求算法具有實時性，是以大資料算法要考慮到運算時間。對于另外兩個v，我們假設大資料算法處理的資料已經是經過預處理的，其多樣性(variety)已經被屏蔽掉了。關于價值(value)本書也不考慮，而假設資料或算法的價值是預先知道的。

要設計一個大資料算法并不容易，因為大資料具有規模大、速度快的特點。大資料算法設計的難度主要展現在四個方面。

1.通路全部資料時間過長

有的時候算法通路全部資料時間太長，應用無法接受。特别是資料量達到pb級甚至更大的時候，即使有多台機器一起通路資料，也是很困難的。在這種情況下怎麼辦呢？隻能放棄使用全部資料這種想法，而通過部分資料得到一個還算滿意的結果，這個結果不一定是精确的，可能是不怎麼精确的而基本滿意，這就涉及一個“時間亞線性算法”的概念，即算法的時間複雜度低于資料量，算法運作過程中需要讀取的資料量小于全部資料。

2.資料難以放入記憶體計算

第二個問題是資料量非常大，可能無法放進記憶體。一個政策是把資料放到磁盤上，基于磁盤上的資料來設計算法，這就是所謂的外存算法。學過資料結構與算法的學生對于外存算法可能不陌生，一些資料結構課程裡講過的外存排序，就是比較典型的外存算法，在資料庫實作課程中講過的一趟選擇算法、兩趟連接配接算法、嵌套循環連接配接算法也屬于外存算法。這些外存算法的特點是以磁盤塊為處理機關，其衡量标準不再是簡單的cpu時間，而是磁盤的i/o。另外一個處理方法是不對全部的資料進行計算，而隻向記憶體裡放入小部分資料，僅使用記憶體中的小部分資料，就可以得到一個有品質保證的結果，這樣的算法通常叫作“空間亞線性算法”，就是說執行這一類算法所需要的空間是小于資料本身的，即“空間亞線性”。

3.單個計算機難以儲存全部資料，計算需要整體資料

在一些情況下，單個計算機難以儲存或者在時間限制内處理全部資料，而計算需要整體資料，在這種情況下一個辦法就是采取并行處理技術，即使用多台計算機協同工作。并行處理對應的算法是并行算法，大資料進行中常見的mapreduce就是一種大資料的程式設計模型，hadoop是基于mapreduce程式設計模型的計算平台。

4.計算機計算能力不足或知識不足

還有一種情況是計算機的計算能力不足或者說計算所需要的知識不足。例如，判斷一幅圖檔裡是不是包含貓或者狗。這時候計算機并不知道什麼是貓什麼是狗，如果僅僅利用計算機而沒有人的知識參與計算的話，這個問題會變得非常困難，可能要從大量的标注圖像裡進行學習。但如果可以讓人來參與，這個問題就變得簡單了。更難一點的問題，比如說兩個相機哪個更好，這是一個比較主觀的問題，計算機是無法判斷的，怎麼辦呢？可以讓人來參與，是以，有一類算法叫作“衆包算法”，相當于把計算機難以計算但人計算相對容易的任務交給人來做，有的時候，衆包算法的成本更低，算得更快。

上述是大資料算法的一些難點，針對這些難點，有一系列算法提出，包括時間亞線性算法、空間亞線性算法、外存算法、并行算法、衆包算法，這些就是本書的主要内容。

大資料算法在大資料的應用中将扮演什麼樣的角色呢？我們通過下面一些例子來看看大資料算法的應用。

1.預測中的大資料算法

如何利用大資料進行預測？一種可能的方法是從多個資料源(比如社交網絡、網際網路等)提取和預測主題相關的資料，然後根據預測主題建立統計模型，通過訓練集學習得到模型中的參數，最後基于模型和參數進行預測。其中每一個步驟都涉及大資料算法問題。在資料擷取階段，因為從社交網絡或者網際網路上擷取的資料量很大，是以從非結構化資料(如文本)提取出關鍵詞或者結構化資料(例如元組、鍵值對)需要适用于大資料的資訊提取算法；在特征選擇過程中，發現預測結果和哪些因素相關需要關聯規則挖掘或者主成分分析算法；在參數學習階段，需要機器學習算法，如梯度下降等，盡管傳統的機器學習有相應的算法，但是這些算法複雜度通常較高，不适合處理大資料，是以需要面向大資料的新的機器學習算法來完成任務。

2.推薦中的大資料算法

目前推薦已經成為一個熱門的研究分支，有大量的推薦算法提出。由于目前商品資訊和使用者資訊資料量都很大，例如淘寶，使用者和商品的數量都達到了gb級以上，基于這樣大規模的資料進行推薦需要能夠處理大資料的推薦算法。例如為了減少處理資料量的svd分解，基于以前有哪些使用者購買這個商品和這些使用者購買哪些商品的資訊構成一個矩陣，這個矩陣規模非常大，以至于在進行推薦時無法使用，因而就需要svd分解技術對這個矩陣分解，進而将矩陣變小。而基于這樣大規模的稀疏矩陣上的推薦也需要相應的大規模矩陣操作算法。

3.商業情報分析中的大資料算法

商業情報分析首先要從網際網路或者企業自身的資料倉庫(例如沃爾瑪pb級的資料倉庫)上發現與需要分析的内容密切相關的内容，繼而根據這些内容分析出有價值的商業情報，這一系列操作如果利用計算機自動完成，需要算法來解決。其中涉及的問題包括文本挖掘、機器學習，涉及的大資料算法包括分類算法、聚類分析、實體識别、時間序列分析、回歸分析等，這些問題在統計學和計算機科學方面都有相關的方法提出，然而面向大資料，這些方法的性能和可擴充性難以滿足要求，需要設計面向大資料的分析算法。

4.科學研究中的大資料算法

科學研究中涉及大量的統計計算，如利用回複分析發現統計量之間的相關性，利用序列分析發現演化規律。例如，美國能源部支援的項目中專門有一部分給大資料算法，在其公布的指南裡包含相應的研究題目，包括如何從龐大的科學資料集合中提取有用的資訊，如何發現相關資料間的關系（即相關規則發現），還包括大資料上的機器學習、資料流上的實時分析，以及資料縮減、高可控的拓展性的統計分析，這些都在科學研究中扮演重要的角色。