本節(jié)書摘來華章計(jì)算機(jī)《大數(shù)據(jù)算法》一書中的第1章 ，第1.2節(jié)，王宏志　編著, 更多章節(jié)內(nèi)容可以訪問云棲社區(qū)“華章計(jì)算機(jī)”公眾號(hào)查看。

1.2　大數(shù)據(jù)算法

這一節(jié)我們概述大數(shù)據(jù)算法。

1.2.1　大數(shù)據(jù)上求解問題的過程

首先我們看一看在大數(shù)據(jù)上問題求解的過程。我們面對的是一個(gè)計(jì)算問題，也就是說我們要用計(jì)算機(jī)來處理一個(gè)問題。
拿到一個(gè)計(jì)算問題之后，首先需要判定這個(gè)問題是否可以用計(jì)算機(jī)進(jìn)行計(jì)算，如果學(xué)習(xí)過可計(jì)算性理論，就可以了解有許多問題計(jì)算機(jī)是無法計(jì)算的，比如判斷一個(gè)程序是否有死循環(huán)，或者是否存在能夠殺所有病毒的軟件，這些問題都是計(jì)算機(jī)解決不了的。從“可計(jì)算”的角度來看，大數(shù)據(jù)上的判定問題和普通的判定問題是一樣的，也就是說，如果還是用我們今天的電子計(jì)算機(jī)模型，即圖靈機(jī)模型，在小數(shù)據(jù)上不可計(jì)算的問題，在大數(shù)據(jù)上肯定也不可計(jì)算。計(jì)算模型的計(jì)算能力是一樣的，只不過是算得快慢的問題。
那么，大數(shù)據(jù)上的計(jì)算問題與傳統(tǒng)的計(jì)算問題有什么本質(zhì)區(qū)別呢？
第一個(gè)不同之處是數(shù)據(jù)量，就是說處理的數(shù)據(jù)量要比傳統(tǒng)的數(shù)據(jù)量大。第二個(gè)不同之處是有資源約束，就是說數(shù)據(jù)量可能很大，但是能真正用來處理數(shù)據(jù)的資源是有限的，這個(gè)資源包括CPU、內(nèi)存、磁盤、計(jì)算所消耗的能量。第三個(gè)不同之處是對計(jì)算時(shí)間存在約束，大數(shù)據(jù)有很強(qiáng)的實(shí)時(shí)性，最簡單的一個(gè)例子是基于無線傳感網(wǎng)的森林防火，如果能在幾秒之內(nèi)自動(dòng)發(fā)現(xiàn)有火情發(fā)生，這個(gè)信息是非常有價(jià)值的，如果三天之后才發(fā)現(xiàn)火情，樹都燒完了，這個(gè)信息就沒有價(jià)值，所以說大數(shù)據(jù)上的計(jì)算問題需要有一個(gè)時(shí)間約束，即到底需要多長時(shí)間得到計(jì)算結(jié)果才是有價(jià)值的。判定能否在給定數(shù)據(jù)量的數(shù)據(jù)上，在計(jì)算資源存在約束的條件下，在時(shí)間約束內(nèi)完成計(jì)算任務(wù)，是大數(shù)據(jù)上計(jì)算的可行性問題，需要計(jì)算復(fù)雜性理論來解決，然而，當(dāng)前面向大數(shù)據(jù)上的計(jì)算復(fù)雜性理論研究還剛剛開始，有大量的問題需要解決。
注意：在本書中，有的算法可能很簡單，寥寥幾行就結(jié)束了，然而后面的分析卻長達(dá)幾頁。這本書花更大的精力講授算法分析，是因?yàn)樵诖髷?shù)據(jù)上進(jìn)行算法設(shè)計(jì)的時(shí)候，要先分析清楚這個(gè)算法是否適用于大數(shù)據(jù)的情況，然后才能使用。
本書討論的主要內(nèi)容是大數(shù)據(jù)上算法的設(shè)計(jì)與分析，即設(shè)計(jì)大數(shù)據(jù)上的算法并且加以分析。
特別值得說明的一點(diǎn)是，對于大數(shù)據(jù)上的算法，算法分析顯得尤為重要，這是為什么呢？對于小數(shù)據(jù)上的算法可以通過實(shí)驗(yàn)的方法來測試性能，實(shí)驗(yàn)可以很快得到結(jié)果，但是在大數(shù)據(jù)上，實(shí)驗(yàn)就不是那么簡單了，經(jīng)常需要成千上萬的機(jī)器才能夠得出結(jié)果。為了避免耗費(fèi)如此高的計(jì)算成本，大數(shù)據(jù)上的算法分析就十分重要了。
經(jīng)過算法設(shè)計(jì)與分析，得到了算法。接著需要用計(jì)算機(jī)語言來實(shí)現(xiàn)算法，得到的是一些程序模塊，下一步用這些程序模塊構(gòu)建軟件系統(tǒng)。這些軟件系統(tǒng)需要相應(yīng)的平臺(tái)來實(shí)現(xiàn)，比如常說的Hadoop、SparK都是實(shí)現(xiàn)軟件系統(tǒng)的平臺(tái)。
上面的敘述可以歸納為圖1-1，從中可以看到，大數(shù)據(jù)算法與分析在整個(gè)大數(shù)據(jù)問題求解過程中扮演著一個(gè)核心的角色，因而本書將對此重點(diǎn)介紹。

1.2.2　大數(shù)據(jù)算法的定義

1.大數(shù)據(jù)算法是什么
根據(jù)大數(shù)據(jù)上的計(jì)算過程可以定義大數(shù)據(jù)算法的概念，如定義1-1所示。
定義1-1(大數(shù)據(jù)算法)　在給定的資源約束下，以大數(shù)據(jù)為輸入，在給定時(shí)間約束內(nèi)可以計(jì)算出給定問題結(jié)果的算法。
這個(gè)定義和傳統(tǒng)的算法有一樣的地方，首先大數(shù)據(jù)算法也是一個(gè)算法，有輸入有輸出；而且算法必須是可行的，也必須是機(jī)械執(zhí)行的計(jì)算步驟。
補(bǔ)充知識(shí)：算法的定義
定義A-1(計(jì)算)　可由一個(gè)給定計(jì)算模型機(jī)械地執(zhí)行的規(guī)則或計(jì)算步驟序列稱為該計(jì)算模型的一個(gè)計(jì)算。
定義A-2(算法)　算法是一個(gè)滿足下列條件的計(jì)算：
1) 有窮性/終止性：有限步內(nèi)必須停止；
2) 確定性：每一步都是嚴(yán)格定義和確定的動(dòng)作；
3) 可行性：每一個(gè)動(dòng)作都能夠被精確地機(jī)械執(zhí)行；
4) 輸入：有一個(gè)滿足給定約束條件的輸入；
5) 輸出：滿足給定約束條件的結(jié)果。

第一個(gè)不同之處是，大數(shù)據(jù)算法是有資源約束的，這意味著資源不是無限的，可能在100KB數(shù)據(jù)上可行的算法在100MB的數(shù)據(jù)上不可行，最常見的一個(gè)錯(cuò)誤是內(nèi)存溢出。這意味著進(jìn)行大數(shù)據(jù)處理的內(nèi)存資源不足，因此在大數(shù)據(jù)算法的設(shè)計(jì)過程中，資源是一個(gè)必須考慮的約束。第二個(gè)不同之處是，大數(shù)據(jù)算法以大數(shù)據(jù)為輸入，而不是以傳統(tǒng)數(shù)據(jù)的小規(guī)模為輸入。第三個(gè)不同之處是，大數(shù)據(jù)算法需要在時(shí)間約束之內(nèi)產(chǎn)生結(jié)果，因?yàn)橛行┣闆r下過了時(shí)間約束大數(shù)據(jù)會(huì)失效，有些情況下超過時(shí)間約束的計(jì)算結(jié)果沒有價(jià)值。
2.大數(shù)據(jù)算法可以不是什么
有了大數(shù)據(jù)作為輸入和運(yùn)行時(shí)間作為約束，大數(shù)據(jù)算法和傳統(tǒng)算法就有了明確的區(qū)別。
第一，大數(shù)據(jù)算法可以不是精確算法。因?yàn)橛行┣闆r下，能夠證明對于給定的數(shù)據(jù)輸入規(guī)模和資源約束，確實(shí)不可能得到精確解。
第二，大數(shù)據(jù)算法可以不是內(nèi)存算法。由于數(shù)據(jù)量很大，在很多情況下，把所有數(shù)據(jù)都放在內(nèi)存中幾乎不可能，因?yàn)閷τ诂F(xiàn)在的PC來說，內(nèi)存的規(guī)模在GB級(jí)，對于高檔一些的并行機(jī)和服務(wù)器來說內(nèi)存也就是TB級(jí)，這個(gè)規(guī)模對于許多應(yīng)用中的數(shù)據(jù)量是遠(yuǎn)遠(yuǎn)不夠的，必須使用外存甚至于網(wǎng)絡(luò)存儲(chǔ)。因此，大數(shù)據(jù)算法可以不僅僅在內(nèi)存中運(yùn)行。
第三，大數(shù)據(jù)算法可以不是串行算法。有的時(shí)候，單獨(dú)一臺(tái)計(jì)算機(jī)難以處理大規(guī)模數(shù)據(jù)，需要多臺(tái)機(jī)器協(xié)同并行計(jì)算，即并行算法。一個(gè)典型的例子是Google公司中的計(jì)算，為了支持搜索引擎，Google公司需要處理大規(guī)模來自互聯(lián)網(wǎng)的數(shù)據(jù)，因而大數(shù)據(jù)里面的很多重要概念是Google提出的，例如并行平臺(tái)MapReduce。Google公司的數(shù)據(jù)規(guī)模太大，再好的機(jī)器也無法獨(dú)自處理，需要用成千上萬臺(tái)機(jī)器構(gòu)成一個(gè)機(jī)群來并行處理。
第四，大數(shù)據(jù)算法可以不是僅在電子計(jì)算機(jī)上運(yùn)行的算法。有時(shí)對于某些任務(wù)而言，讓計(jì)算機(jī)處理很復(fù)雜，而讓人做很簡單。對于這些問題，可以讓人和計(jì)算機(jī)一起來做，因此就有了人和計(jì)算機(jī)協(xié)同的算法。
而傳統(tǒng)算法分析與設(shè)計(jì)課程中的算法，主要是內(nèi)存算法、精確算法、串行算法且完全在電子計(jì)算機(jī)上執(zhí)行，這和本書中的大數(shù)據(jù)算法不同。
3.大數(shù)據(jù)算法不僅僅是什么
下面從大數(shù)據(jù)概念出發(fā)，澄清一些大數(shù)據(jù)算法的片面觀點(diǎn)。
第一，大數(shù)據(jù)算法不僅僅是基于MapReduce的算法。講到大數(shù)據(jù)算法，可能有很多人就會(huì)想到MapReduce，MapReduce上的算法確實(shí)在很多情況下適用于大數(shù)據(jù)，而且更確切說MapReduce上的算法是一類很重要的大數(shù)據(jù)算法，但是大數(shù)據(jù)算法不僅是MapReduce上的算法。
第二，大數(shù)據(jù)算法不僅僅是云計(jì)算平臺(tái)上的算法。說到大數(shù)據(jù)算法，很多人可能會(huì)想到云計(jì)算，云上的算法是不是大數(shù)據(jù)算法呢？云上的算法不全是大數(shù)據(jù)算法，有的算法不是面向大數(shù)據(jù)的，例如安全性相關(guān)的算法和計(jì)算密集型算法，而且大數(shù)據(jù)算法也不都是云上的算法，大數(shù)據(jù)算法有的可以是單機(jī)的，甚至可以是手機(jī)或者傳感器這種計(jì)算能力很差的設(shè)備。
第三，大數(shù)據(jù)算法不僅僅是數(shù)據(jù)分析與挖掘中的算法。分析與挖掘是大數(shù)據(jù)中比較熱的概念，也確實(shí)是大數(shù)據(jù)的重要方面。之所以用得比較多，是因?yàn)槠渖虡I(yè)價(jià)值比較明顯。然而，大數(shù)據(jù)的應(yīng)用除了需要分析與挖掘，還有獲取、清洗、查詢處理、可視化等方面，這些都需要大數(shù)據(jù)算法的支持。
第四，大數(shù)據(jù)算法不僅僅是數(shù)據(jù)庫中的算法。提到大數(shù)據(jù)，自然會(huì)聯(lián)想到這是和數(shù)據(jù)管理密切相關(guān)的。大數(shù)據(jù)算法是否等同于數(shù)據(jù)庫中的算法呢？不完全是這樣，雖然數(shù)據(jù)庫中的算法是大數(shù)據(jù)算法的一個(gè)重要組成部分，今天進(jìn)行大數(shù)據(jù)算法研究的多是數(shù)據(jù)庫和數(shù)據(jù)管理研究領(lǐng)域的專家，但是不全是數(shù)據(jù)庫領(lǐng)域的。當(dāng)前研究大數(shù)據(jù)算法的專家，有的研究背景是數(shù)學(xué)理論和算法理論，還有的來自機(jī)器學(xué)習(xí)和各種大數(shù)據(jù)應(yīng)用的研究領(lǐng)域。因此大數(shù)據(jù)算法不僅僅是數(shù)據(jù)庫中的算法，還有專門為大數(shù)據(jù)設(shè)計(jì)的算法。

1.2.3　大數(shù)據(jù)的特點(diǎn)與大數(shù)據(jù)算法

大數(shù)據(jù)的特點(diǎn)決定了大數(shù)據(jù)算法的設(shè)計(jì)方法。正如前面所介紹的，大數(shù)據(jù)的特點(diǎn)通常用四個(gè)V來描述。這四個(gè)V里面和大數(shù)據(jù)算法密切相關(guān)的，有兩個(gè)V。一個(gè)是數(shù)據(jù)量(Volume)大，也就是大數(shù)據(jù)算法必須處理足夠大的數(shù)據(jù)量。另一個(gè)是速度(Velocity)，速度有兩方面:①大數(shù)據(jù)的更新速度很快，相應(yīng)的大數(shù)據(jù)算法也必須考慮更新算法的速度；②要求算法具有實(shí)時(shí)性，因此大數(shù)據(jù)算法要考慮到運(yùn)算時(shí)間。對于另外兩個(gè)V，我們假設(shè)大數(shù)據(jù)算法處理的數(shù)據(jù)已經(jīng)是經(jīng)過預(yù)處理的，其多樣性(Variety)已經(jīng)被屏蔽掉了。關(guān)于價(jià)值(Value)本書也不考慮，而假設(shè)數(shù)據(jù)或算法的價(jià)值是預(yù)先知道的。

1.2.4　大數(shù)據(jù)算法的難度

要設(shè)計(jì)一個(gè)大數(shù)據(jù)算法并不容易，因?yàn)榇髷?shù)據(jù)具有規(guī)模大、速度快的特點(diǎn)。大數(shù)據(jù)算法設(shè)計(jì)的難度主要體現(xiàn)在四個(gè)方面。
1.訪問全部數(shù)據(jù)時(shí)間過長
有的時(shí)候算法訪問全部數(shù)據(jù)時(shí)間太長，應(yīng)用無法接受。特別是數(shù)據(jù)量達(dá)到PB級(jí)甚至更大的時(shí)候，即使有多臺(tái)機(jī)器一起訪問數(shù)據(jù)，也是很困難的。在這種情況下怎么辦呢？只能放棄使用全部數(shù)據(jù)這種想法，而通過部分?jǐn)?shù)據(jù)得到一個(gè)還算滿意的結(jié)果，這個(gè)結(jié)果不一定是精確的，可能是不怎么精確的而基本滿意，這就涉及一個(gè)“時(shí)間亞線性算法”的概念，即算法的時(shí)間復(fù)雜度低于數(shù)據(jù)量，算法運(yùn)行過程中需要讀取的數(shù)據(jù)量小于全部數(shù)據(jù)。
2.數(shù)據(jù)難以放入內(nèi)存計(jì)算
第二個(gè)問題是數(shù)據(jù)量非常大，可能無法放進(jìn)內(nèi)存。一個(gè)策略是把數(shù)據(jù)放到磁盤上，基于磁盤上的數(shù)據(jù)來設(shè)計(jì)算法，這就是所謂的外存算法。學(xué)過數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)生對于外存算法可能不陌生，一些數(shù)據(jù)結(jié)構(gòu)課程里講過的外存排序，就是比較典型的外存算法，在數(shù)據(jù)庫實(shí)現(xiàn)課程中講過的一趟選擇算法、兩趟連接算法、嵌套循環(huán)連接算法也屬于外存算法。這些外存算法的特點(diǎn)是以磁盤塊為處理單位，其衡量標(biāo)準(zhǔn)不再是簡單的CPU時(shí)間，而是磁盤的I/O。另外一個(gè)處理方法是不對全部的數(shù)據(jù)進(jìn)行計(jì)算，而只向內(nèi)存里放入小部分?jǐn)?shù)據(jù)，僅使用內(nèi)存中的小部分?jǐn)?shù)據(jù)，就可以得到一個(gè)有質(zhì)量保證的結(jié)果，這樣的算法通常叫作“空間亞線性算法”，就是說執(zhí)行這一類算法所需要的空間是小于數(shù)據(jù)本身的，即“空間亞線性”。
3.單個(gè)計(jì)算機(jī)難以保存全部數(shù)據(jù)，計(jì)算需要整體數(shù)據(jù)
在一些情況下，單個(gè)計(jì)算機(jī)難以保存或者在時(shí)間約束內(nèi)處理全部數(shù)據(jù)，而計(jì)算需要整體數(shù)據(jù)，在這種情況下一個(gè)辦法就是采取并行處理技術(shù)，即使用多臺(tái)計(jì)算機(jī)協(xié)同工作。并行處理對應(yīng)的算法是并行算法，大數(shù)據(jù)處理中常見的MapReduce就是一種大數(shù)據(jù)的編程模型，Hadoop是基于MapReduce編程模型的計(jì)算平臺(tái)。
4.計(jì)算機(jī)計(jì)算能力不足或知識(shí)不足
還有一種情況是計(jì)算機(jī)的計(jì)算能力不足或者說計(jì)算所需要的知識(shí)不足。例如，判斷一幅圖片里是不是包含貓或者狗。這時(shí)候計(jì)算機(jī)并不知道什么是貓什么是狗，如果僅僅利用計(jì)算機(jī)而沒有人的知識(shí)參與計(jì)算的話，這個(gè)問題會(huì)變得非常困難，可能要從大量的標(biāo)注圖像里進(jìn)行學(xué)習(xí)。但如果可以讓人來參與，這個(gè)問題就變得簡單了。更難一點(diǎn)的問題，比如說兩個(gè)相機(jī)哪個(gè)更好，這是一個(gè)比較主觀的問題，計(jì)算機(jī)是無法判斷的，怎么辦呢？可以讓人來參與，因此，有一類算法叫作“眾包算法”，相當(dāng)于把計(jì)算機(jī)難以計(jì)算但人計(jì)算相對容易的任務(wù)交給人來做，有的時(shí)候，眾包算法的成本更低，算得更快。
上述是大數(shù)據(jù)算法的一些難點(diǎn)，針對這些難點(diǎn)，有一系列算法提出，包括時(shí)間亞線性算法、空間亞線性算法、外存算法、并行算法、眾包算法，這些就是本書的主要內(nèi)容。

1.2.5　大數(shù)據(jù)算法的應(yīng)用

大數(shù)據(jù)算法在大數(shù)據(jù)的應(yīng)用中將扮演什么樣的角色呢？我們通過下面一些例子來看看大數(shù)據(jù)算法的應(yīng)用。
1.預(yù)測中的大數(shù)據(jù)算法
如何利用大數(shù)據(jù)進(jìn)行預(yù)測？一種可能的方法是從多個(gè)數(shù)據(jù)源(比如社交網(wǎng)絡(luò)、互聯(lián)網(wǎng)等)提取和預(yù)測主題相關(guān)的數(shù)據(jù)，然后根據(jù)預(yù)測主題建立統(tǒng)計(jì)模型，通過訓(xùn)練集學(xué)習(xí)得到模型中的參數(shù)，最后基于模型和參數(shù)進(jìn)行預(yù)測。其中每一個(gè)步驟都涉及大數(shù)據(jù)算法問題。在數(shù)據(jù)獲取階段，因?yàn)閺纳缃痪W(wǎng)絡(luò)或者互聯(lián)網(wǎng)上獲取的數(shù)據(jù)量很大，所以從非結(jié)構(gòu)化數(shù)據(jù)(如文本)提取出關(guān)鍵詞或者結(jié)構(gòu)化數(shù)據(jù)(例如元組、鍵值對)需要適用于大數(shù)據(jù)的信息提取算法；在特征選擇過程中，發(fā)現(xiàn)預(yù)測結(jié)果和哪些因素相關(guān)需要關(guān)聯(lián)規(guī)則挖掘或者主成分分析算法；在參數(shù)學(xué)習(xí)階段，需要機(jī)器學(xué)習(xí)算法，如梯度下降等，盡管傳統(tǒng)的機(jī)器學(xué)習(xí)有相應(yīng)的算法，但是這些算法復(fù)雜度通常較高，不適合處理大數(shù)據(jù)，因此需要面向大數(shù)據(jù)的新的機(jī)器學(xué)習(xí)算法來完成任務(wù)。
2.推薦中的大數(shù)據(jù)算法
當(dāng)前推薦已經(jīng)成為一個(gè)熱門的研究分支，有大量的推薦算法提出。由于當(dāng)前商品信息和用戶信息數(shù)據(jù)量都很大，例如淘寶，用戶和商品的數(shù)量都達(dá)到了GB級(jí)以上，基于這樣大規(guī)模的數(shù)據(jù)進(jìn)行推薦需要能夠處理大數(shù)據(jù)的推薦算法。例如為了減少處理數(shù)據(jù)量的SVD分解，基于以前有哪些用戶購買這個(gè)商品和這些用戶購買哪些商品的信息構(gòu)成一個(gè)矩陣，這個(gè)矩陣規(guī)模非常大，以至于在進(jìn)行推薦時(shí)無法使用，因而就需要SVD分解技術(shù)對這個(gè)矩陣分解，從而將矩陣變小。而基于這樣大規(guī)模的稀疏矩陣上的推薦也需要相應(yīng)的大規(guī)模矩陣操作算法。
3.商業(yè)情報(bào)分析中的大數(shù)據(jù)算法
商業(yè)情報(bào)分析首先要從互聯(lián)網(wǎng)或者企業(yè)自身的數(shù)據(jù)倉庫(例如沃爾瑪PB級(jí)的數(shù)據(jù)倉庫)上發(fā)現(xiàn)與需要分析的內(nèi)容密切相關(guān)的內(nèi)容，繼而根據(jù)這些內(nèi)容分析出有價(jià)值的商業(yè)情報(bào)，這一系列操作如果利用計(jì)算機(jī)自動(dòng)完成，需要算法來解決。其中涉及的問題包括文本挖掘、機(jī)器學(xué)習(xí)，涉及的大數(shù)據(jù)算法包括分類算法、聚類分析、實(shí)體識(shí)別、時(shí)間序列分析、回歸分析等，這些問題在統(tǒng)計(jì)學(xué)和計(jì)算機(jī)科學(xué)方面都有相關(guān)的方法提出，然而面向大數(shù)據(jù)，這些方法的性能和可擴(kuò)展性難以滿足要求，需要設(shè)計(jì)面向大數(shù)據(jù)的分析算法。
4.科學(xué)研究中的大數(shù)據(jù)算法
科學(xué)研究中涉及大量的統(tǒng)計(jì)計(jì)算，如利用回復(fù)分析發(fā)現(xiàn)統(tǒng)計(jì)量之間的相關(guān)性，利用序列分析發(fā)現(xiàn)演化規(guī)律。例如，美國能源部支持的項(xiàng)目中專門有一部分給大數(shù)據(jù)算法，在其公布的指南里包含相應(yīng)的研究題目，包括如何從龐大的科學(xué)數(shù)據(jù)集合中提取有用的信息，如何發(fā)現(xiàn)相關(guān)數(shù)據(jù)間的關(guān)系（即相關(guān)規(guī)則發(fā)現(xiàn)），還包括大數(shù)據(jù)上的機(jī)器學(xué)習(xí)、數(shù)據(jù)流上的實(shí)時(shí)分析，以及數(shù)據(jù)縮減、高可控的拓展性的統(tǒng)計(jì)分析，這些都在科學(xué)研究中扮演重要的角色。

總結(jié)

以上是生活随笔為你收集整理的《大数据算法》一1.2　大数据算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。