809
《大數據算法》一1.2 大數據算法
本節書摘來異步社區《大數據算法》一書中的第1章 ，第1.2節，王宏誌 編著, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。
1.2 大數據算法
這一節我們概述大數據算法。
1.2.1 大數據上求解問題的過程
首先我們看一看在大數據上問題求解的過程。我們麵對的是一個計算問題，也就是說我們要用計算機來處理一個問題。
拿到一個計算問題之後，首先需要判定這個問題是否可以用計算機進行計算，如果學習過可計算性理論，就可以了解有許多問題計算機是無法計算的，比如判斷一個程序是否有死循環，或者是否存在能夠殺所有病毒的軟件，這些問題都是計算機解決不了的。從“可計算”的角度來看，大數據上的判定問題和普通的判定問題是一樣的，也就是說，如果還是用我們今天的電子計算機模型，即圖靈機模型，在小數據上不可計算的問題，在大數據上肯定也不可計算。計算模型的計算能力是一樣的，隻不過是算得快慢的問題。
那麼，大數據上的計算問題與傳統的計算問題有什麼本質區別呢？
第一個不同之處是數據量，就是說處理的數據量要比傳統的數據量大。第二個不同之處是有資源約束，就是說數據量可能很大，但是能真正用來處理數據的資源是有限的，這個資源包括CPU、內存、磁盤、計算所消耗的能量。第三個不同之處是對計算時間存在約束，大數據有很強的實時性，最簡單的一個例子是基於無線傳感網的森林防火，如果能在幾秒之內自動發現有火情發生，這個信息是非常有價值的，如果三天之後才發現火情，樹都燒完了，這個信息就沒有價值，所以說大數據上的計算問題需要有一個時間約束，即到底需要多長時間得到計算結果才是有價值的。判定能否在給定數據量的數據上，在計算資源存在約束的條件下，在時間約束內完成計算任務，是大數據上計算的可行性問題，需要計算複雜性理論來解決，然而，當前麵向大數據上的計算複雜性理論研究還剛剛開始，有大量的問題需要解決。
注意：在本書中，有的算法可能很簡單，寥寥幾行就結束了，然而後麵的分析卻長達幾頁。這本書花更大的精力講授算法分析，是因為在大數據上進行算法設計的時候，要先分析清楚這個算法是否適用於大數據的情況，然後才能使用。
本書討論的主要內容是大數據上算法的設計與分析，即設計大數據上的算法並且加以分析。
特別值得說明的一點是，對於大數據上的算法，算法分析顯得尤為重要，這是為什麼呢？對於小數據上的算法可以通過實驗的方法來測試性能，實驗可以很快得到結果，但是在大數據上，實驗就不是那麼簡單了，經常需要成千上萬的機器才能夠得出結果。為了避免耗費如此高的計算成本，大數據上的算法分析就十分重要了。
經過算法設計與分析，得到了算法。接著需要用計算機語言來實現算法，得到的是一些程序模塊，下一步用這些程序模塊構建軟件係統。這些軟件係統需要相應的平台來實現，比如常說的Hadoop、SparK都是實現軟件係統的平台。
上麵的敘述可以歸納為圖1-1，從中可以看到，大數據算法與分析在整個大數據問題求解過程中扮演著一個核心的角色，因而本書將對此重點介紹。
1.2.2 大數據算法的定義
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上的算法。
第二，大數據算法不僅僅是雲計算平台上的算法。說到大數據算法，很多人可能會想到雲計算，雲上的算法是不是大數據算法呢？雲上的算法不全是大數據算法，有的算法不是麵向大數據的，例如安全性相關的算法和計算密集型算法，而且大數據算法也不都是雲上的算法，大數據算法有的可以是單機的，甚至可以是手機或者傳感器這種計算能力很差的設備。
第三，大數據算法不僅僅是數據分析與挖掘中的算法。分析與挖掘是大數據中比較熱的概念，也確實是大數據的重要方麵。之所以用得比較多，是因為其商業價值比較明顯。然而，大數據的應用除了需要分析與挖掘，還有獲取、清洗、查詢處理、可視化等方麵，這些都需要大數據算法的支持。
第四，大數據算法不僅僅是數據庫中的算法。提到大數據，自然會聯想到這是和數據管理密切相關的。大數據算法是否等同於數據庫中的算法呢？不完全是這樣，雖然數據庫中的算法是大數據算法的一個重要組成部分，今天進行大數據算法研究的多是數據庫和數據管理研究領域的專家，但是不全是數據庫領域的。當前研究大數據算法的專家，有的研究背景是數學理論和算法理論，還有的來自機器學習和各種大數據應用的研究領域。因此大數據算法不僅僅是數據庫中的算法，還有專門為大數據設計的算法。
1.2.3 大數據的特點與大數據算法
大數據的特點決定了大數據算法的設計方法。正如前麵所介紹的，大數據的特點通常用四個V來描述。這四個V裏麵和大數據算法密切相關的，有兩個V。一個是數據量(Volume)大，也就是大數據算法必須處理足夠大的數據量。另一個是速度(Velocity)，速度有兩方麵:①大數據的更新速度很快，相應的大數據算法也必須考慮更新算法的速度；②要求算法具有實時性，因此大數據算法要考慮到運算時間。對於另外兩個V，我們假設大數據算法處理的數據已經是經過預處理的，其多樣性(Variety)已經被屏蔽掉了。關於價值(Value)本書也不考慮，而假設數據或算法的價值是預先知道的。
1.2.4 大數據算法的難度
要設計一個大數據算法並不容易，因為大數據具有規模大、速度快的特點。大數據算法設計的難度主要體現在四個方麵。
1.訪問全部數據時間過長
有的時候算法訪問全部數據時間太長，應用無法接受。特別是數據量達到PB級甚至更大的時候，即使有多台機器一起訪問數據，也是很困難的。在這種情況下怎麼辦呢？隻能放棄使用全部數據這種想法，而通過部分數據得到一個還算滿意的結果，這個結果不一定是精確的，可能是不怎麼精確的而基本滿意，這就涉及一個“時間亞線性算法”的概念，即算法的時間複雜度低於數據量，算法運行過程中需要讀取的數據量小於全部數據。
2.數據難以放入內存計算
第二個問題是數據量非常大，可能無法放進內存。一個策略是把數據放到磁盤上，基於磁盤上的數據來設計算法，這就是所謂的外存算法。學過數據結構與算法的學生對於外存算法可能不陌生，一些數據結構課程裏講過的外存排序，就是比較典型的外存算法，在數據庫實現課程中講過的一趟選擇算法、兩趟連接算法、嵌套循環連接算法也屬於外存算法。這些外存算法的特點是以磁盤塊為處理單位，其衡量標準不再是簡單的CPU時間，而是磁盤的I/O。另外一個處理方法是不對全部的數據進行計算，而隻向內存裏放入小部分數據，僅使用內存中的小部分數據，就可以得到一個有質量保證的結果，這樣的算法通常叫作“空間亞線性算法”，就是說執行這一類算法所需要的空間是小於數據本身的，即“空間亞線性”。
3.單個計算機難以保存全部數據，計算需要整體數據
在一些情況下，單個計算機難以保存或者在時間約束內處理全部數據，而計算需要整體數據，在這種情況下一個辦法就是采取並行處理技術，即使用多台計算機協同工作。並行處理對應的算法是並行算法，大數據處理中常見的MapReduce就是一種大數據的編程模型，Hadoop是基於MapReduce編程模型的計算平台。
4.計算機計算能力不足或知識不足
還有一種情況是計算機的計算能力不足或者說計算所需要的知識不足。例如，判斷一幅圖片裏是不是包含貓或者狗。這時候計算機並不知道什麼是貓什麼是狗，如果僅僅利用計算機而沒有人的知識參與計算的話，這個問題會變得非常困難，可能要從大量的標注圖像裏進行學習。但如果可以讓人來參與，這個問題就變得簡單了。更難一點的問題，比如說兩個相機哪個更好，這是一個比較主觀的問題，計算機是無法判斷的，怎麼辦呢？可以讓人來參與，因此，有一類算法叫作“眾包算法”，相當於把計算機難以計算但人計算相對容易的任務交給人來做，有的時候，眾包算法的成本更低，算得更快。
上述是大數據算法的一些難點，針對這些難點，有一係列算法提出，包括時間亞線性算法、空間亞線性算法、外存算法、並行算法、眾包算法，這些就是本書的主要內容。
1.2.5 大數據算法的應用
大數據算法在大數據的應用中將扮演什麼樣的角色呢？我們通過下麵一些例子來看看大數據算法的應用。
1.預測中的大數據算法
如何利用大數據進行預測？一種可能的方法是從多個數據源(比如社交網絡、互聯網等)提取和預測主題相關的數據，然後根據預測主題建立統計模型，通過訓練集學習得到模型中的參數，最後基於模型和參數進行預測。其中每一個步驟都涉及大數據算法問題。在數據獲取階段，因為從社交網絡或者互聯網上獲取的數據量很大，所以從非結構化數據(如文本)提取出關鍵詞或者結構化數據(例如元組、鍵值對)需要適用於大數據的信息提取算法；在特征選擇過程中，發現預測結果和哪些因素相關需要關聯規則挖掘或者主成分分析算法；在參數學習階段，需要機器學習算法，如梯度下降等，盡管傳統的機器學習有相應的算法，但是這些算法複雜度通常較高，不適合處理大數據，因此需要麵向大數據的新的機器學習算法來完成任務。
2.推薦中的大數據算法
當前推薦已經成為一個熱門的研究分支，有大量的推薦算法提出。由於當前商品信息和用戶信息數據量都很大，例如淘寶，用戶和商品的數量都達到了GB級以上，基於這樣大規模的數據進行推薦需要能夠處理大數據的推薦算法。例如為了減少處理數據量的SVD分解，基於以前有哪些用戶購買這個商品和這些用戶購買哪些商品的信息構成一個矩陣，這個矩陣規模非常大，以至於在進行推薦時無法使用，因而就需要SVD分解技術對這個矩陣分解，從而將矩陣變小。而基於這樣大規模的稀疏矩陣上的推薦也需要相應的大規模矩陣操作算法。
3.商業情報分析中的大數據算法
商業情報分析首先要從互聯網或者企業自身的數據倉庫(例如沃爾瑪PB級的數據倉庫)上發現與需要分析的內容密切相關的內容，繼而根據這些內容分析出有價值的商業情報，這一係列操作如果利用計算機自動完成，需要算法來解決。其中涉及的問題包括文本挖掘、機器學習，涉及的大數據算法包括分類算法、聚類分析、實體識別、時間序列分析、回歸分析等，這些問題在統計學和計算機科學方麵都有相關的方法提出，然而麵向大數據，這些方法的性能和可擴展性難以滿足要求，需要設計麵向大數據的分析算法。
4.科學研究中的大數據算法
科學研究中涉及大量的統計計算，如利用回複分析發現統計量之間的相關性，利用序列分析發現演化規律。例如，美國能源部支持的項目中專門有一部分給大數據算法，在其公布的指南裏包含相應的研究題目，包括如何從龐大的科學數據集合中提取有用的信息，如何發現相關數據間的關係（即相關規則發現），還包括大數據上的機器學習、數據流上的實時分析，以及數據縮減、高可控的拓展性的統計分析，這些都在科學研究中扮演重要的角色。
最後更新：2017-06-21 13:01:59