時隔一個多月，終于想起來寫大數(shù)據(jù)算法基礎(chǔ)的實(shí)驗(yàn)報(bào)告，主要是快截止了，hh

這兩天加急把這個報(bào)告寫完了~

接下來，寫一寫證明過程（參考書籍：高等教育出版社《數(shù)據(jù)科學(xué)與工程算法基礎(chǔ)》）主要代碼以及總結(jié)體會o(*￣▽￣*)ブ

---

本次實(shí)驗(yàn)主要設(shè)計(jì)三塊內(nèi)容，分別是水庫抽樣算法（當(dāng)水庫大小為1時），水庫抽樣算法（當(dāng)水庫大小為k>1時）以及分布式水庫抽樣算法

---

水庫抽樣算法

主要證明過程

主要Python代碼?

水庫抽樣算法（返回一個）

import randomdef sampling_single(stream):reservoir = stream[0]i = 1for i, item in enumerate(stream):j = random.randint(0, i)if j < 1:reservoir = itemreturn reservoir F = [i for i in range(100)]H = sampling_single(F)
print(f"Randomly sampled element: {H}")

水庫抽樣算法（返回多個）?

import randomdef reservoir_sampling(stream, k):reservoir = []for i, item in enumerate(stream):if i < k:reservoir.append(item)else:j = random.randint(0, i)if j < k:reservoir[j] = itemreturn reservoirdata_stream = [i for i in range(100)]sampled_data = reservoir_sampling(data_stream, 10)

分布式水庫抽樣算法?

?主要證明過程

? 一個Hadoop任務(wù)Sample由 n 個 Map 組成，其中每個 Map 都接受到一個數(shù)據(jù)流 Substream，當(dāng)這些數(shù)據(jù)無法完全保存在內(nèi)存時，如何隨機(jī)地抽取一個含有 k 條記錄的樣本（每條記錄被抽中的概率相同），于是，這就引出了分布式水庫抽樣算法（分層水庫抽樣 + 重抽樣 = 分布式水庫抽樣算法）

? 先在每個 Map 上獨(dú)立運(yùn)行水庫抽樣算法，之后對 n 個子樣本就行重抽樣，獲得滿足要求的最終結(jié)果。?

主要 Python 代碼?

import randomdef reservoir_sampling(stream, k):reservoir = []for i, item in enumerate(stream):if i < k:reservoir.append(item)else:j = random.randint(0, i)if j < k:reservoir[j] = itemreturn reservoirdef distributed_sampling(n, k, stream):N = []F = []H = []for i in range(n):F.append(reservoir_sampling(stream, k))N.append(len(F[i]))total_N = sum(N)for j in range(k):p = random.random()m = 0cumulative_N = 0while cumulative_N < p * total_N :cumulative_N += N[m]m += 1H.append(random.choice(F[m-1]))return Hn = 15
k = 10
data_stream = [i for i in range(100)]
H = distributed_sampling(n, k, data_stream)
print("Final Sample H:", H)   

---

總結(jié)?

? 水庫抽樣技術(shù)歸根到底就是在總體容量未知的情況下，僅通過單遍掃描數(shù)據(jù)集便能生成等概率抽樣集合的一種均勻抽樣技術(shù)。

? 代碼或許很簡單，但是其中的數(shù)學(xué)知識以及思想方法是很值得學(xué)習(xí)的！