數據工程師必知算法：蓄水池抽樣
英文原文：hadoop-stratified-randosampling-algorithm
譯者：bruce-accumulate 譯文鏈接
引言：眾所周知，想要面試一個統計學家和軟件工程師的合體——數據工程師——是件很難的事情。我在面試中常使用的方法是：提出即需要算法設計，又需要一些概率論知識的問題，來考察面試者的功底。下面就是在硅谷非常流行的例子：
“給出一個數據流，這個數據流的長度很大或者未知。并且對該數據流中數據只能訪問一次。請寫出一個隨機選擇算法，使得數據流中所有數據被選中的概率相等。”
當面對這樣一個問題的時候，我們首先應該做的是：鎮靜。你的面試官并沒有玩你，相反他可能特別想雇你。他可能正在為無盡的分析請求煩惱，他的 ETL 流水線已經不在工作，已有的機器學習模型也不再適合。他正想要你這樣一個聰明人進來幫忙，他希望你答出來。
第二件要做的事情是：不要在沒有深入思考的情況下盲目作答。假設你的面試官讀過 Daniel Tunkelang 的關于數據工程師的面試建議，那么這個面試題很可能就是他工作中實際遇到的問題。所以如果像下面一樣隨便回答，很可能會令你的面試官失望。
“我會首先將輸入存到一個列表中，統計出數據流中數據的個數，在讀取結束之后隨機選取一個”（大哥， 你沒看見題目已經說了，數據流長度很大或者未知么，不怕你的內存裝不下？）
第三件要做的事情是：從小例子開始分析。大部分的人都更容易解決具體問題（而不是抽象問題），最開始你設計的小例子可能和最后的問題之間相去甚遠，但是卻能啟發你對問題的理解，給你靈感。
蓄水池算法
如前面所說，對這個問題我們首先從最簡單的例子出發：數據流只有一個數據。我們接收數據，發現數據流結束了，直接返回該數據，該數據返回的概率為1。看來很簡單，那么我們試試難一點的情況：假設數據流里有兩個數據。
我們讀到了第一個數據，這次我們不能直接返回該數據，因為數據流沒有結束。我們繼續讀取第二個數據，發現數據流結束了。因此我們只要保證以相同 的概率返回第一個或者第二個數據就可以滿足題目要求。因此我們生成一個 0 到 1 的隨機數R,如果R小于 0.5 我們就返回第一個數據，如果R大于 0.5，返回第二個數據。
接著我們繼續分析有三個數據的數據流的情況。為了方便，我們按順序給流中的數據命名為1、2、3。我們陸續收到了數據1、2 和前面的例子一樣，我們只能保存一個數據，所以必須淘汰 1 和 2 中的一個。應該如何淘汰呢？不妨和上面例子一樣，我們按照二分之一的概率淘汰一個，例如我們淘汰了 1. 繼續讀取流中的數據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++算法進行初始化–在輸入數據上進行迭代操作，選擇樣本抽樣。每次選取過程，數據被選入樣本的概率和該數據與當前樣本中最短距離 節點的距離成比例。通過使用加權的蓄水池抽樣算法，只需掃描數據一遍就能決定樣本組成（一般方法需要首先遍歷一次以計算出聚類的總代價，之后第二次遍歷根 據第一次的計算結果進行樣本選擇）。
要讀的一些書目
很多有趣的算法都不止對寫分布式文件系統或者搜索引擎的工程師有用，它們有時對于大規模數據分析和一些統計問題也特別有幫助。接下來，我會再寫幾篇關于算法博客。但在這之前我的說，高德納老爺子的書常讀常新，大家先去看看《計算機程序設計藝術》上面的算法吧~
