本文關(guān)鍵詞：海量數(shù)據(jù)挖掘，由筆耕文化傳播整理發(fā)布。

本欄目（數(shù)據(jù)挖掘）下海量數(shù)據(jù)挖掘?qū)ｎ}是個(gè)人對(duì)Coursera公開課海量數(shù)據(jù)挖掘（2015）的學(xué)習(xí)心得與筆記。所有內(nèi)容均來自Coursera公開課Mining Massive Datasets中Jure Leskovec, Anand Rajaraman以及Jeff Ullman老師的講解。（https://class.coursera.org/mmds-002/lecture）

第1講-------MapReduce and PageRank

一、Distributed File System

隨著海量數(shù)據(jù)的I/O與計(jì)算需求越來越大，受到帶寬與單個(gè)CPU計(jì)算能力有限的限制，原來的Singles Node Architecture（單CPU，單Memory以及單Disk）已經(jīng)不能滿足需求。這時(shí)傳統(tǒng)的Cluster Architecture應(yīng)運(yùn)而生，如下圖所示，用以解決大數(shù)據(jù)的存儲(chǔ)與挖掘。

但是，傳統(tǒng)的Cluster Architecture并沒有完全解決問題，有如下的局限性：

MapReduce的出現(xiàn)就是為了解決傳統(tǒng)Cluster Architecture的局限性。將數(shù)據(jù)冗余地存儲(chǔ)在多個(gè)node上；Move computation close to data以減少數(shù)據(jù)的移動(dòng)；提供Simple Programming Model影藏了分布式架構(gòu)的復(fù)雜性。這三部分的內(nèi)容都將會(huì)在接下來的內(nèi)容中講到。

其中第一個(gè)挑戰(zhàn)的解決方案就是冗余存儲(chǔ)架構(gòu)，也就是經(jīng)常提到的Distributed File System，例如Google GFS，Hadoop HDFS。它提供了全局的文件命名空間、冗余性以及可用性。典型的特點(diǎn)是Huge files；數(shù)據(jù)很少有update in place；常見的是數(shù)據(jù)的讀取與文件末尾的添加。

Distributed File System的數(shù)據(jù)被切分成塊chunks，每一個(gè)數(shù)據(jù)塊都被復(fù)制多份保存在不同的machine上，這種情況下machine本身被稱為chunk server。如下圖所示，一個(gè)file被且分為C1-C6的數(shù)據(jù)塊。chunk servers同時(shí)也扮演著compute servers的角色，這樣就能實(shí)現(xiàn)Bring computation to data的目標(biāo)。

總的來說，Distributed File System由如下的三部分組成：

二、 The MapReduce Computational Model

從經(jīng)典的Word count的例子出發(fā)。假設(shè)有一個(gè)huge text document，需要統(tǒng)計(jì)其中distinct word出現(xiàn)的次數(shù)。對(duì)于Unix Shell來說，就是如下的一句命令：

這一條命令實(shí)際上已經(jīng)道出了MapReduce用于word count的精髓。這三個(gè)步驟實(shí)際上都是可以并行化的，實(shí)際上也可以對(duì)應(yīng)到MapReduce的如下三個(gè)過程。MapReduce的總體框架都是一樣的，不同的問題只是Map和Reduce function相應(yīng)的變化。具體的Map與Reduce的過程很簡單，這里就不畫圖進(jìn)行解釋了。

那么更正式一點(diǎn)的來說，MapReduce Computational Model如下圖所示。MapReduce的輸入就是一系列的key-value對(duì)；Map就是對(duì)鍵值對(duì)進(jìn)行映射；Reduce則針對(duì)相同的unique key進(jìn)行需要的操作，然后輸出結(jié)果。需要注意的是，當(dāng)有多個(gè)reduce node的時(shí)候，map是通過hash函數(shù)講相同的key放到同一個(gè)reduce函數(shù)上的。而且，使用的是sequence reading，節(jié)省時(shí)間。

三、 Scheduling and Data Flow

接下來，稍微深入一些MapReduce具體在分布式上的實(shí)現(xiàn)機(jī)制，如下圖所示。實(shí)際上有多個(gè)nodes，每個(gè)node都有多個(gè)Map或者Reduce在運(yùn)行。途中的Partitioning Function其實(shí)就是一個(gè)Hash Function，當(dāng)有多個(gè)reduce node的時(shí)候，map是通過hash函數(shù)講相同的key放到同一個(gè)reduce函數(shù)上的。這樣的話可能會(huì)有多個(gè)key放到同一個(gè)reduce上，Group by key的操作就是針對(duì)key進(jìn)行排序，分成多撥跑reduce函數(shù)。

所以Programmer只需要提供Map和Reduce兩個(gè)函數(shù)，然后MapReduce環(huán)境承擔(dān)了剩下所有的事情：將輸入數(shù)據(jù)劃分成塊；調(diào)度程序在一系列的機(jī)器中運(yùn)行；Map操作之后運(yùn)行Group by key步驟；處理node會(huì)fail的情況；負(fù)責(zé)機(jī)器之間的通信等。所以從Data Flow的角度來說，Input和final output都存儲(chǔ)在DFS上，Scheduler嘗試讓map task在輸入數(shù)據(jù)塊的chunk server上執(zhí)行，bring computation to data。Map或者Reduce產(chǎn)生的中間結(jié)果都只保存在worker的local FS上，一個(gè)Map/Reduce對(duì)的輸出往往是另一個(gè)Map/Reduce對(duì)的輸入。

Master node主要負(fù)責(zé)task的調(diào)度。task分為idle，in-progress以及completed。當(dāng)有空閑的worker時(shí)，idle task即準(zhǔn)備執(zhí)行。當(dāng)Map task完成的時(shí)候，會(huì)將產(chǎn)生的R個(gè)中間文件的位置info發(fā)送給master，Master則負(fù)責(zé)將這些信息發(fā)送給各個(gè)reducer。Master node會(huì)周期性地ping每一個(gè)work確保他們沒有fail。

當(dāng)Map worker fail的時(shí)候，所有completed以及in-progress task都會(huì)被reset為idle，會(huì)被重新調(diào)度在別的worker上執(zhí)行；當(dāng)Reduce worker fail的時(shí)候，只有in-progress task會(huì)被重新調(diào)度在別的worker執(zhí)行，因?yàn)镽educe的輸出就是final output，它已經(jīng)被寫入到DFS中而不是local DFS中，所以completed task沒必要重新調(diào)度執(zhí)行。那如果Master fail呢？MapReduce task終止并且發(fā)出警告，Master node沒有復(fù)制對(duì)于它fail的概率也很低。

那一般來說需要多少的Map和Reduce的job？M要比集群中的node數(shù)量大很多，每一個(gè)DFS chunk分配一個(gè)Map是很常見的，這樣提高了動(dòng)態(tài)負(fù)載平衡以及加速了worker failures的恢復(fù)。R一般比M要少，因?yàn)樽罱K的輸出是需要將R個(gè)輸出文件集中起來的，所以少的數(shù)量會(huì)比較好。

四、 Combiners and Partition Functions

接下來介紹幾個(gè)讓MapReduce得以更高效率運(yùn)行的改進(jìn)。一個(gè)是Combiners。一個(gè)Map會(huì)經(jīng)常產(chǎn)生大量的相同key的pair，例如在之前word count例子中的高頻詞匯。如果將這些Map產(chǎn)生的pair直接發(fā)送給Reduce，則需要大量的網(wǎng)絡(luò)帶寬損耗。Combiner的作用就是在每一個(gè)Mapper里將Map的輸出結(jié)果進(jìn)行一次結(jié)果的前期收集pre-aggregating，Combiner的操作usually和reduce function是一樣的，如下圖所示。

Combiner trick只有當(dāng)reduce的運(yùn)算滿足交換律和結(jié)合律的時(shí)候才能有效，例如word count 中Sum的操作。有一些操作不能直接使用Combiner，不過對(duì)reduce的運(yùn)算稍加調(diào)整之后可以使用，例如Average，如果reduce的操作是統(tǒng)計(jì)（sum，count）的二元組，最后進(jìn)行average的計(jì)算。還有一些操作不管怎樣都無法使用Combiner，例如Median求中位數(shù)。

另外一個(gè)是Partition Function。 Partition Function的存在就是為了讓用戶決定（key, value）的pair如何進(jìn)入reduce worker。默認(rèn)的partition function是hash(key) mod R，有時(shí)候想改變例如hash(hostname(URL)) mod R，希望來自同一個(gè)host的URL被分配到同一個(gè)reduce中去。

最早的MapReduce的實(shí)現(xiàn)是Google MapReduce，使用GFS作為stable storage，不開源；Hadoop是Google MapReduce的開源實(shí)現(xiàn)，使用HDFS作為文件系統(tǒng)；實(shí)踐證明在Hadoop上面的數(shù)據(jù)操作很多都需要類似與SQL操作的數(shù)據(jù)處理，Hive和Pig則提供了基于Hadoop的SQL-like事務(wù)處理的抽象。另外云上的MapReduce最有名的要數(shù)Amazon‘s "Elastic Compute Cloud"(EC2)，已S3作為文件系統(tǒng)。

五、 Link Analysis and PageRank

接下來，開始一個(gè)新的話題：Large Graph的分析。首先探討Link Analysis方法，例如PageRank或者SimRank；其次也會(huì)探討Community Detection，希望找出網(wǎng)絡(luò)中節(jié)點(diǎn)的集群；然后我們也會(huì)研究Spam Detection。

Web也可以表示為一個(gè)有向圖，每一個(gè)Webpage作為節(jié)點(diǎn)；超鏈接作為圖的邊。整個(gè)Web是一個(gè)巨大的有向圖，那應(yīng)該如何去Organize整個(gè)Web的內(nèi)容呢？一種早期的方式就是人工地分類目錄整理；另一種方式就是Web Search。但是，Web是龐大的，充滿著大量的不可信文檔，spam，不相關(guān)的信息等等。所以，Web search的兩大挑戰(zhàn)就是：一方面，Web上面的信息如何分辨哪些是可信的，一種trick就是可信的頁面可能會(huì)指向彼此；另一方面，對(duì)于一個(gè)query（例如“newspaper”）哪一個(gè)結(jié)果才會(huì)是最好的結(jié)果，不會(huì)有單一的正確答案，一種trick認(rèn)為知道newspaper的頁面可能會(huì)指向很多newspaper。

還有一點(diǎn)，Web頁面并不是同等重要的。我們希望計(jì)算出web graph中每個(gè)節(jié)點(diǎn)的重要性分?jǐn)?shù)，依據(jù)就是link structure。link越多的節(jié)點(diǎn)，分?jǐn)?shù)就越高。有很多方法來計(jì)算web graph中節(jié)點(diǎn)的重要性，它們統(tǒng)稱為Link analysis。例如，PageRank，Hubs and Authorities(HITS)。另外，也會(huì)來看一些它們的擴(kuò)展算法：Topic-Specific (Personalized) PageRank，Web Spam Detection Algorithms等。

六、 PageRank：The "Flow" Formulation

我們首先從直觀上來感受下PageRank，也就是被稱為The Flow Formulation，進(jìn)一步地給出數(shù)學(xué)上的推導(dǎo)，然后具體地探討它是如何計(jì)算重要性分?jǐn)?shù)的。

直觀上來說，它的核心思想就是Links as votes. 一個(gè)頁面如果擁有越多的links，它就顯得更重要。顯然這里的links指的是in-coming links。與此同時(shí)，并不是所有的in-link都是同等重要，來自于重要性分?jǐn)?shù)越高page的in-link更重要。對(duì)于一個(gè)page的所有out-link來說，它們平分這個(gè)page的importance score，如下圖所示。

如上圖所示的簡單例子，利用高斯消元法就能夠計(jì)算出每個(gè)page的重要性分?jǐn)?shù)。但是對(duì)于大量的Web Graph，我們需要一個(gè)更好的方法。

七、 PageRank：The Matrix Formulation

為了利用線性幾何來解決上節(jié)中提到的方程組解問題，我們需要重新從矩陣的角度重新來定義這個(gè)問題。引入鄰接矩陣M，如下圖所示，如果page i指向page j，那么M(j, i) = 1/d_i。這樣的話，矩陣M中的每一列和都為1。同時(shí)定義向量r為所有page的重要性分?jǐn)?shù)向量。

如何形象地理解這個(gè)Matrix Formulation？矩陣M中的第j行表示所有指向page j的in-link，矩陣M的第j行與向量r的內(nèi)積即得到r_j。也即如上圖的加和等式。然則，這個(gè)Matrix Formulation又解決了什么問題呢。

回憶一下線性代數(shù)中特征向量eigenvector與特征值eigenvalue的概念。對(duì)應(yīng)任意一個(gè)square matrix A

簡單對(duì)比即可發(fā)現(xiàn)，之前的Matrix Formulation的求解即是針對(duì)矩陣M在特征值為1時(shí)的特征矩陣r的求解。那么如果被給予一個(gè)矩陣M，要如何求解當(dāng)eigenvalue=1時(shí)他的eigenvector呢？The Method is called Power Iteration.

八、 PageRank：Power Iteration

接下來，我們來看一下Power Iteration這個(gè)算法。假設(shè)整個(gè)Web Graph擁有N個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)即網(wǎng)頁page，邊即為page之間的hyper link。如下圖所示，這就是PageRank算法最簡單的版本，我們從一個(gè)猜想的初始值開始，迭代大概50~100次，直到r收斂才認(rèn)為得到了PageRank的重要性分?jǐn)?shù)。

進(jìn)一步地，我們來看看page rank score究竟代表著什么意思？這被稱為Ramdom Walk Interpretation。我們將會(huì)看到page rank score將會(huì)等同于隨機(jī)游走者ramdom web surfer在整個(gè)graph中行走的概率分布。在時(shí)刻t，surfer在節(jié)點(diǎn)i上；那么在時(shí)刻t + 1，surfer則會(huì)隨機(jī)選擇節(jié)點(diǎn)i的out-link走出下一步到達(dá)節(jié)點(diǎn)j，如此循環(huán)。

定義向量p(t)，第i個(gè)元素代表surfer在時(shí)刻t時(shí)處于節(jié)點(diǎn)i的概率。也就是說，p(t)是一個(gè)各個(gè)頁面節(jié)點(diǎn)之間的概率分布。那么，在時(shí)刻t+1時(shí)，the surfer又在哪里？

如上圖所示，當(dāng)the random walk達(dá)到平穩(wěn)分布時(shí)p(t)是等同于p(t+1)的，也就是說我們之前要求解的特征向量r即為the random walk的平穩(wěn)分布。所以，page rank score代表著random surfer隨機(jī)游走中在給定的時(shí)刻t時(shí)位于特定節(jié)點(diǎn)的概率分布。隨機(jī)游走在隨機(jī)過程中也被稱為馬爾科夫過程。對(duì)于滿足特定條件的graph來說，平穩(wěn)分布是唯一的。也就說不管初始概率分布如何，最終都會(huì)到達(dá)同一個(gè)平穩(wěn)分布的狀態(tài)。

九、 The Google Formulation

上節(jié)我們講到：對(duì)于滿足特定條件的graph來說，平穩(wěn)分布是唯一的。那么，究竟需要滿足什么特定的條件？接下來我們講探討PageRank算法真正的Google Formulation版本。對(duì)于之前的Matrix Formulation等式，有幾個(gè)遺留問題：

(1) 是否能收斂�？紤]如下的“Spider trap”問題——所有的out-links都在一個(gè)group的內(nèi)部，就會(huì)發(fā)現(xiàn)永遠(yuǎn)不會(huì)收斂。

Solution：Random Teleports。

(2)是否能收斂到我們想要的程度�？紤]如下的“Dead end”問題——某些page節(jié)點(diǎn)沒有out-links，，就會(huì)發(fā)現(xiàn)雖然收斂了但是不是我們想要的結(jié)果，Dead end節(jié)點(diǎn)會(huì)導(dǎo)致importance score“泄露”。

Solution：Always Teleports。

(3)結(jié)果是否是合理的。我們會(huì)發(fā)現(xiàn)以上的兩大類問題得到的結(jié)果都是不合理的。

十、 Why Teleports Solve the Problem

這一節(jié)我們探討一下為什么Teleports就能夠解決之前PageRank算法的問題�；氐街榜R爾科夫鏈的理論，P(i, j)代表從節(jié)點(diǎn)j到節(jié)點(diǎn)i的概率。馬爾科夫鏈的理論是說，對(duì)于任意的開始向量，Power Method使用馬爾科夫變換P將會(huì)收斂到一個(gè)唯一的正穩(wěn)態(tài)向量的充要條件是矩陣P是stochastic，irreducible以及aperiodic的。

接下來我們將會(huì)看到，加入Random Teleports的方案實(shí)際上某種程度上確保了變換矩陣P的這三種屬性。

首先是Stochastic。矩陣是Stochastic的也就是說矩陣每列和加起來是1。對(duì)于“Dead Ends”的情況因?yàn)闆]有out-links，所以這一列的和加起來不是1而是0。但是當(dāng)我們加入random teleportation的時(shí)候，我們就會(huì)發(fā)現(xiàn)加入了如下圖所示的綠色箭頭，這樣的話就確保了矩陣M是Stochastic的。

其次是Aperiodic。非周期性，如下圖所示的循環(huán)鏈，random teleportation的加入相當(dāng)于綠色links，保證了每兩次訪問某個(gè)節(jié)點(diǎn)的時(shí)間間隔是非周期性的。

最后是Irreducible。對(duì)于任意的狀態(tài)，從任一狀態(tài)轉(zhuǎn)換到另外任一狀態(tài)的概率不能為0。

Google‘s 的解決方案解決了所有的這三個(gè)問題。也就是說，PageRank算法的Google Formulation如下圖所示。

舉個(gè)例子，這個(gè)時(shí)候的PageRank算法如何計(jì)算importance score的。

十一、 How we Really Compute PageRank

對(duì)于大規(guī)模的Web Graph，我們?nèi)绾蝸碛?jì)算PageRank score？當(dāng)Web Graph大到內(nèi)存不足以存下整個(gè)矩陣A的時(shí)候，該怎么辦？

最后的最后，完整的PageRank算法實(shí)現(xiàn)步驟如下圖所示：

  本文關(guān)鍵詞：海量數(shù)據(jù)挖掘，由筆耕文化傳播整理發(fā)布。