面試高頻題：蓄水池演算法的證明

作者：由 SofaSofa.io 發表于攝影時間：2018-09-10

原連結：蓄水池取樣的證明

我們要從資料流中抽取

個數據點，那對於第

個樣本

，（

$n\geq k$

），它有$k/n$的機率被選進池子中；如果被選中了，我們隨機從池子中的$k$個樣本中挑選一個$X_i$被$X_n$取代。這個就是蓄水池演算法的基本思想。

——————————————-

下面開始證明

——————————————-

若數學公式無法顯示，點選這裡

用數學歸納法證明，每個樣本被選中的機率的都是相等的。

初始情況是，當前只有$k$個樣本，此時每個樣本都被選中進入池子，也就是$k /k=1$的機率。

如果我們一共有$n$個數據點，假設每個資料點被選進入池子的機率相等，都是$k / n$。

根據數學歸納法的思想，下面我們只要證明如果一共有$n+1$個數據點，每個資料進入池子中的機率都是$k/（n+1）$。

對於第$n+1$個樣本$X_{n+1}$，它進入池子的機率顯然是$k/（n+1）$。

對於第$j$個樣本$X_j$，$j\leq n$，它在前一輪中已經在池子裡的機率為$k/n$。

下面我們分兩種情況討論：第一種情況，$X_{n+1}$沒被選中，所以$X_j$依然留在池子中。這種情況的機率為

$P_1=1-\frac{k}{n+1}=\frac{n+1-k}{n+1}$

第二種情況，

$X_{n+1}$

被選中但是$X_j$沒有被替換。這種情況發生的機率為

$P_2=\frac{k}{n+1}\frac{k-1}{k}=\frac{k-1}{n+1}$

兩者相加

$P_1+P_2=\frac{n}{n+1}$

所以$X_j$此時在池子中的機率為

$\frac{k}{n}(P_1+P_2)=\frac{k}{n}\frac{n}{n+1}=\frac{k}{n+1}$

證畢。

其他閱讀：

資料科學、ML崗位的簡歷應該怎麼寫？

還在拿MNIST手寫數字練習？不如試試這個

SofaSofa。io：K-Means、非負矩陣分解（NMF）與影象壓縮

不用sklearn，自己動手寫梯度下降

SofaSofa。io：機器讀中文：根據名字判斷性別

標簽：池子機率樣本選中資料

猜你喜歡