不使用隨機採樣（）？

Question

我最近被要求執行，將選擇具有相同的概率各元素的sampleStream（）方法，而不是使用隨機的（）。我認爲面試官正在尋找油藏採樣，但當我偶然發現它時，他補充說這是一種叫做「stratified sampling」的方法。無可否認，我可能已經被拋棄了，因爲有一種稱爲分層抽樣的統計方法，我試圖想到如何使用它來從流中對元素進行抽樣而沒有隨機抽樣。他指定的輸入是要抽樣的項目數量和我應該抽樣的比率（類似1000/100,000）。

無論如何，我仍然停留在這個問題上，即使我已經不得到未正確回答它的工作。谷歌搜索在這裏失敗了。任何人都可以幫助我理解它嗎？實行分層抽樣

Answer 1

一種方法是排序用於分層密鑰列表，然後在正取樣做1。

技術上，分類是不必要的，如果鍵是類別。在這種（典型的）情況下，可以使用哈希方法。這個想法仍然是一樣的：在一個「有序」列表中進行n次採樣。

或許，這就是面試官指的。

編輯：

您可以實現流上的分層抽樣，你就基本上可以讀取該流並做了「桶」計算每組相似的鍵值。當存儲桶有一些任意值時，您將輸出記錄。當桶達到某個值（基於整體頻率）時，您將重置計數器並重復（或使用模運算）。

但是，這並沒有獲得每條記錄的相同概率。爲此，我確實認爲你需要某種隨機化。接近的方法是將每個組的記錄存儲在一個存儲桶中，然後在存儲桶已滿時選擇一個隨機記錄。您可以通過在其他值（例如插入時間）上使用散列鍵來模擬隨機性，然後選擇最小或最大散列鍵值。 （而且，你可以讓這個更有效的通過只是存儲一個記錄。）