一個簡單直觀的基數估計方法
讓我們從一個簡單直觀的例子開始吧假設你通過如下步驟生成了一個數據集
隨機生成n個服從均勻分布的數字
隨便重復其中一些數字重復的數字和重復次數都不確定
打亂這些數字的順序得到一個數據集
我們要如何估計這個數據集中有多少不同的數字呢？因為知道這些數字是服從均勻分布的隨機數字一個比較簡單的可行方案是找出數據集中最小的數字 假如m是數值上限x是找到的最小的數則m/x是基數的一個估計例如我們掃描一個包含到之間數字組成的數據集其中最小的數是則一個 比較合理的推斷是數據集中大約有個不同的元素否則我們應該預期能找到一個更小的數注意這個估計值和重復次數無關就如最小值重復多少次都不改變 最小值的數值
這個估計方法的優點是十分直觀但是准確度一般例如一個只有很少不同數值的數據集卻擁有很小的最小值類似的一個有很多不同值的數據集可能最小 值並不小最後一點其實只有很少的數據集符合隨機均勻分布這一前提盡管如此這個原型算法仍然是了解基數估計思想的一個途徑後面我們會了解一些更加 精巧的算法
基數估計的概率算法
最早研究高精度基數估計的論文是Flajolet和Martin的Probabilistic Counting Algorithms for Data Base Applications後來Flajolet又發表了LogLog counting of large cardinalities和HyperLogLog: The analysis of a nearoptimal cardinality estimation algorithm兩篇論文對算法進行了進一步改進通過逐篇閱讀這些論文來了解算法的發展和細節固然有趣不過在這篇文章中我會忽略一些算法的理論細節把精力主要放在如何通過論文中的算法解決問題有興趣的讀者可以讀一下這三篇論文本文不會介紹其中的數學細節
Flajolet和Martin最早發現通過一個良好的哈希函數可以將任意數據集映射成服從均勻分布的（偽）隨機值根據這一事實可以將任意數據集變換為均勻分布的隨機數集合然後就可以使用上面的方法進行估計了不過只是這樣是遠遠不夠的
接下來他們陸續發現一些其它的基數估計方法而其中一些方法的效果優於之前提到的方法Flajolet和Martin計算了哈希值的二進制表示 的前綴結果發現在隨機數集合中通過計算每一個元素的二進制表示的前綴設k為最長的前綴的長度則平均來說集合中大約有k個不同的元素我們 可以用這個方法估計基數但是這仍然不是很理想的估計方法因為和基於最小值的估計一樣這個方法的方差很大不過另一方面這個估計方法比較節省資 源對於位的哈希值來說只需要比特去存儲前綴的長度
值得一提的是FlajoletMartin在最初的論文裡通過一種基於bitmap的過程去提高估計算法的准確度關於這點我就不再詳述了因為這種方法已經被後續論文中更好的方法所取代對這個細節有興趣的讀者可以去閱讀原始論文
到目前為止我們這種基於位模式的估計算法給出的結果仍然不夠理想如何進行改進呢？一個直觀的改進方法就是使用多個相互獨立的哈希函數通過計算每個哈希函數所產生的最長前綴然後取其平均值可以提高算法的精度
實踐表明從統計意義來說這種方法確實可以提高估計的准確度但是計算哈希值的消耗比較大另一個更高效的方法就是隨機平均（stochastic averaging）這種方法不是使用多個哈希函數而是使用一個哈希函數但是將哈希值的區間按位切分成多個桶（bucket）例如我們希望取 個數進行平均那麼我們可以取哈希值的前比特作為桶編號然後計算剩下部分的前綴長度這種方法的准確度和多哈希函數方法相當但是比計算 多個哈希效率高很多
根據上述分析我們可以給出一個簡單的算法實現這個實現等價於DurandFlajolet的論文中提出的LogLog算法不過為了方便這個實現中統計的是尾綴而不是前綴其效果是等價的
def trailing_zeroes(num):
Counts the number of trailing bits in num
if num == :
return # Assumes bit integer inputs!
p =
while (num >> p) & == :
p +=
return p
def estimate_cardinality(values k):
Estimates the number of unique elements in the input set values
Arguments:
values: An iterator of hashable elements to estimate the cardinality of
k: The number of bits of hash to use as a bucket number; there will be **k buckets
num_buckets = ** k
max_zeroes = [] * num_buckets
for value in values:
h = hash(value)
bucket = h & (num_buckets ) # Mask out the k least significant bits as bucket ID
bucket_hash = h >> k
max_zeroes[bucket] = max(max_zeroes[bucket] trailing_zeroes(bucket_hash))
return ** (float(sum(max_zeroes)) / num_buckets) * num_buckets *
這段代碼實現了我們上面討論的估計算法我們計算每個桶的前綴（或尾綴）的最長長度然後計算這些長度的平均數假設平均數是x桶數量是m則 最終的估計值是x×m其中一個沒提過的地方是魔法數字統計分析顯示這種預測方法存在一個可預測的偏差這個魔法數字是對這個偏差的修 正實際經驗表明計算值隨著桶數量的不同而變化不過當桶數量不太小時（大於）計算值會收斂於估計值原論文中描述了這個結論的推導過程
這個方法給出的估計值比較精確 —— 在分桶數為m的情況下平均誤差為/m√因此對於分桶數為的情況（所需內存* = 位或字節）大約會有%的平均誤差每桶比特的存儲已經足以估計的數據集而我們只用的不到k的內存！
讓我們看一下試驗結果
>>> [/estimate_cardinality([randomrandom() for i in range()] ) for j in range()] [ ] 不錯！雖然有些估計誤差大於%的平均誤差但總體來說效果良好如果你准備自己做一下這個試驗有一點需要注意Python內置的 hash() 方法將整數哈希為它自己因此諸如 estimate_cardinality(range() ) 這種方式得到的結果不會很理想因為內置 hash() 對於這種情況並不能生成很好的散列但是像上面例子中使用隨機數會好很多
提升准確度SuperLogLog和HyperLogLog
雖然我們已經有了一個不錯的估計算法但是我們還能進一步提升算法的准確度Durand和Flajolet發現離群點會大大降低估計准確度如果 在計算平均值前丟棄一些特別大的離群值則可以提高精確度特別的通過丟棄最大的%的桶的值只使用較小的%的桶的值來進行平均值計算則平均 誤差可以從/m降低到/m！這意味著在我們上面的例子中使用個字節可情況下可以將平均誤差從%降低到%而所 需內存並沒有增加
最後Flajolet等人在HyperLogLog論文中給出一種不同的平均值使用調和平均數取代幾何平均數（譯注原文有誤此處應該是算數 平均數）這一改進可以將平均誤差降到/m而且並沒不需要額外資源但是這個算法比前面的算法復雜很多因為對於不同基數的數據集要做不 同的修正有興趣的讀者可以閱讀原論文
並行化
這些基數估計算法的一個好處就是非常容易並行化對於相同分桶數和相同哈希函數的情況多台機器節點可以獨立並行的執行這個算法最後只要將各個節 點計算的同一個桶的最大值做一個簡單的合並就可以得到這個桶最終的值而且這種並行計算的結果和單機計算結果是完全一致的所需的額外消耗僅僅是小於k 的字節在不同節點間的傳輸
結論
基數估計算法使用很少的資源給出數據集基數的一個良好估計一般只要使用少於k的空間存儲狀態這個方法和數據本身的特征無關而且可以高效的進 行分布式並行計算估計結果可以用於很多方面例如流量監控（多少不同IP訪問過一個服務器）以及數據庫查詢優化（例如我們是否需要排序和合並或者是否 需要構建哈希表）
From:http://tw.wingwit.com/Article/program/Java/hx/201311/11149.html
