《大數據算法》一3.2　水庫抽樣

本節書摘來異步社區《大數據算法》一書中的第3章，第3.2節，王宏誌　編著, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。

3.2　水庫抽樣

本節介紹一個簡單的空間亞線性算法，即水庫抽樣。問題定義如下。
抽樣問題
輸入：一組數據，但大小未知。
輸出：這組數據的k個均勻抽樣。
對於這個問題有三點要求：
1) 僅允許掃描數據一次。
2) 空間複雜度為O(k)。注意，空間複雜度和抽樣大小有關，而與整個數據的數據量無關，這意味著不能把所有數據都放在內存當中進行抽樣。
3) 掃描數據的前n個數據時(n>k)，要求保存當前已掃描數據的k個均勻抽樣。這意味著在任何（n>k）時刻，在內存的k個數據裏要放k個均勻的抽樣。針對這個需求提出了水庫抽樣算法。算法3-1　水庫抽樣算法

1　申請一個長度為k的數組A保存抽樣。
2　保存首先接收到的k個元素。
3　當接收到第i個新元素t時，以k/i的概率隨機替換A中的元素。

隨機替換可以生成［1,i］間的隨機數j,若j≤k,就意味著j是存在的，則以t替換A［j］。
算法3-1的空間複雜度是，這是因為在整個算法中，隻需要一個長度為k的數組保存抽樣。額外的空間（如計算概率）都是常數，與n和k沒有關係，因此空間複雜度是O（k）。
算法3-1的抽樣性質如定理3-1所示。
定理3-1　算法3-1得到的采樣是均勻的，在任何時候接收到大於k的n個數時，選出的這k個數一定都是它的一個均勻采樣。
證明　在接收第i+1個數時，第i個數還能保存在數組當中的概率是，因為在接收到第i+1個數時要以的概率隨機替換，而第i個數被選中的概率是1k，它們相乘為就是第i個數被換出數組的概率，所以就是在接收第i+1個元素時第i個數在數組當中的概率。同理，在接收第i+2個數時，第i個數仍然保留在數組當中的概率是。依此類推，當接收第n個數時，第i個元素保存在數組當中的概率是。如果這些事件都發生了，那麼在接收第n個數時，第i個數字才能保留在數組當中。因此它保留在抽樣當中的概率是發生這些事件的概率的積，就是。■