知識星球（點選上方公眾號，可快速關註）
翻譯：伯樂線上 – bruce-accumulate ，英文：Josh Wills
http://blog.jobbole.com/42550/
引言：眾所周知，想要面試一個統計學家和軟體工程師的合體——資料工程師——是件很難的事情。我在面試中常使用的方法是：提出即需要演演算法設計，又需要一些機率論知識的問題，來考察面試者的功底。下麵就是在矽谷非常流行的例子：
“給出一個資料流，這個資料流的長度很大或者未知。並且對該資料流中資料只能訪問一次。請寫出一個隨機選擇演演算法，使得資料流中所有資料被選中的機率相等。”
當面對這樣一個問題的時候，我們首先應該做的是：鎮靜。你的面試官並沒有玩你，相反他可能特別想僱你。他可能正在為無盡的分析請求煩惱，他的ETL流水線已經不在工作，已有的機器學習模型也不再適合。他正想要你這樣一個聰明人進來幫忙，他希望你答出來。
第二件要做的事情是：不要在沒有深入思考的情況下盲目作答。假設你的面試官讀過Daniel Tunkelang的關於資料工程師的面試建議，那麼這個面試題很可能就是他工作中實際遇到的問題。所以如果像下麵一樣隨便回答，很可能會令你的面試官失望。
“我會首先將輸入存到一個串列中，統計出資料流中資料的個數，在讀取結束之後隨機選取一個”（大哥， 你沒看見題目已經說了，資料流長度很大或者未知麼，不怕你的記憶體裝不下？）
第三件要做的事情是：從小例子開始分析。大部分的人都更容易解決具體問題（而不是抽象問題），最開始你設計的小例子可能和最後的問題之間相去甚遠，但是卻能啟發你對問題的理解，給你靈感。
蓄水池演演算法
如前面所說，對這個問題我們首先從最簡單的例子出發：資料流只有一個資料。我們接收資料，發現資料流結束了，直接傳回該資料，該資料傳回的機率為1。看來很簡單，那麼我們試試難一點的情況：假設資料流裡有兩個資料。
我們讀到了第一個資料，這次我們不能直接傳回該資料，因為資料流沒有結束。我們繼續讀取第二個資料，發現資料流結束了。因此我們只要保證以相同的機率傳回第一個或者第二個資料就可以滿足題目要求。因此我們生成一個0到1的隨機數R,如果R小於0.5我們就傳回第一個資料，如果R大於0.5，傳回第二個資料。
接著我們繼續分析有三個資料的資料流的情況。為了方便，我們按順序給流中的資料命名為1、2、3。我們陸續收到了資料1、2和前面的例子一樣，我們只能儲存一個資料，所以必須淘汰1和2中的一個。應該如何淘汰呢？不妨和上面例子一樣，我們按照二分之一的機率淘汰一個，例如我們淘汰了2。繼續讀取流中的資料3，發現資料流結束了，我們知道在長度為3的資料流中，如果傳回資料3的機率為1/3,那麼才有可能保證選擇的正確性。也就是說，目前我們手裡有1,3兩個資料，我們透過一次隨機選擇，以1/3的機率留下資料3，以2/3的機率留下資料1.那麼資料1被最終留下的機率是多少呢？
-
資料1被留下：（1/2）*(2/3) = 1/3
-
資料2被留下機率：（1/2）*(2/3) = 1/3
-
資料3被留下機率：1/3
這個方法可以滿足題目要求，所有資料被留下傳回的機率一樣！
因此，我們做一下推論：假設當前正要讀取第n個資料，則我們以1/n的機率留下該資料，否則留下前n-1個資料中的一個。以這種方法選擇，所有資料流中資料被選擇的機率一樣。簡短的證明：假設n-1時候成立，即前n-1個資料被傳回的機率都是1/n-1,當前正在讀取第n個資料，以1/n的機率傳回它。那麼前n-1個資料中資料被傳回的機率為：(1/(n-1))*((n-1)/n)= 1/n，假設成立。
這就是所謂的蓄水池抽樣演演算法。它在分析一些大資料集的時候非常有用。你可以在這裡找到Greg寫的關於蓄水池抽樣的演演算法介紹。本文後面會介紹一下在Cloudera ML中使用的兩種：分散式蓄水池抽樣和加權分散式蓄水池抽樣。
（註：Cloudera ML是基於hadoop的資料分析和挖掘開源專案）
蓄水池抽樣在Cloudera ML上的應用
分散式蓄水池抽樣是Greg討論的第一種演演算法。可以從前面的討論中發現，基本的蓄水池抽樣要求對資料流進行順序讀取。要進行容量為k的分散式蓄水池抽樣（前面討論的容量都為1）我們使用mapreduce 模擬sql中的ORDER BY RAND (隨機抽取)。對於集合中的每一個元素，都產生一個0-1的隨機數，之後選取隨機值最大的前k個元素。這種方法在對大資料集進行分層抽樣的時候非常管用。這裡每一個分層都都是一些分類變數如性別，年齡，地理資訊等的組合。註意如果輸入的資料集分佈極端的不均勻，那麼抽樣可能不能改寫到所有的層級。為了對每種分類的組合進行抽樣，cloudera ML 提供了sample命令，它可以操作純文字或者hive中的表。
第二個演演算法更加好玩：加權分散式蓄水池抽樣。這裡集合中的資料是有權重的，演演算法希望資料被抽樣選中的機率和該資料的權重成比例。實際上這個問題之前並不一定有解，直到2005年pavlos efraimidis和paul spirakis的論文《weighted random sampling with a reservoir》。他們的解法既簡單又優雅，基本思想和上面的分散式蓄水池抽樣一致：對於每個資料計算一個0-1的值R，並求r的n次方根作為該資料的新的R值。這裡的n就是該資料的權重。最終演演算法傳回前k個R值最高的資料然後傳回。根據計算規則，權重越大的資料計算所得的R值越接近1，所以越有可能被傳回。
在cloudera ML專案中，為了更好地使用k-means++演演算法（K-均值++演演算法），我們會首先使用加權的蓄水池抽樣演演算法對輸入資料進行抽樣。ksketch命令會為k-means++演演算法進行初始化–在輸入資料上進行迭代操作，選擇樣本抽樣。每次選取過程，資料被選入樣本的機率和該資料與當前樣本中最短距離節點的距離成比例。透過使用加權的蓄水池抽樣演演算法，只需掃描資料一遍就能決定樣本組成（一般方法需要首先遍歷一次以計算出聚類的總代價，之後第二次遍歷根據第一次的計算結果進行樣本選擇）。
要讀的一些書目
很多有趣的演演算法都不止對寫分散式檔案系統或者搜尋引擎的工程師有用，它們有時對於大規模資料分析和一些統計問題也特別有幫助。接下來，我會再寫幾篇關於演演算法部落格。但在這之前我的說，高德納老爺子的書常讀常新，大家先去看看《計算機程式設計藝術》上面的演演算法吧~
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
