《大數據算法》一3.4　估算不同元素的數量

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

3.4　估算不同元素的數量

顧名思義，估算不同元素的數量就是看數據流中出現了多少不同的元素。
數據流中不同元素數量統計問題
輸入：數據流,隱式地定義了一個頻率向量f=(f1,…,fn)，中j出現的次數輸出：,即出現在σ中不同元素的數量。
估算數據流中不同元素的個數可以用於統計訪問某個網站的所有用戶個數或者統計某個頁麵的訪問ip數等。由於這些訪問量十分巨大，不可能在內存中完全保存所有訪問信息，因而需要合理的亞線性算法。
如果這個問題被限定為確定性算法(比如δ=0)或精確算法(比如ε=0)，那麼可以證明，這個問題是不可能在亞線性空間內求解的。因此，我們要尋找一個隨機化的近似算法，即輸出d的(ε,δ)近似。
3.4.1　基本算法
1.算法描述
對於一個整數p>0,令
表示p的二進製表示中末尾0的個數，即該算法的核心思想是，數據流當前不同的元素個數越多，對應不同哈希值的個數就越多，從而其中出現某一個元素對應哈希值末尾0的個數多的概率就越大。具體地，對於d個不同的數來說，我們可以期望其中某一個數j滿足。於是，我們在數據流中維護的的最大值(也就是z)給出了一個logd的估計。
我們設計了如下非常簡單的算法。算法3-3　數據流中元素數量估計基本算法

初始化:
1　從2-通用哈希函數族中隨機選擇哈希函數h:［n］→［n］;
2　z←0;
處理j:
3　if zeros(h(j))>z then z←zeros(h(j));
輸出:2z+1/2。

針對該算法，對數據流<1,3,3,5,2,2,1,4,4,6,6>的數據流片段給出具體計算示例，如圖3-1所示。使用哈希函數h(x)=x mod 23，計算過程如下：
1) 對數據流中第一個數據1，計算h(1)=1,其二進製數為001,zeros(h(x))=0；
2) 對數據流中第二個數據3,計算h(3)=3,其二進製數為011，zeros(h(x))=0；
3) 對數據流中第三個數據3,計算h(3)=3,其二進製數為011，zeros(h(x))=0；
4) 對數據流中第四個數據5,計算h(5)=5,其二進製數為101，zeros(h(x))=0，同時更新z的最大值為2;
5) 對數據流中第五個數據2,計算h(2)=2,其二進製數為010，zeros(h(x))=1。
直到數據流處理完當前數據得到最大的z=2，作為統計不同元素估計的參數，即最終估計值為2z+1/2≈6。

補充知識:通用哈希函數族
對於任意哈希函數，都可以人為構造一些特殊的輸入，使得哈希衝突非常高，從而讓哈希表的性能大大降低。為了抵禦這種攻擊，我們可以實現大量哈希函數，然後

在構造哈希表的時候從中任選一個。由於數據輸入者並不知道挑選的是哪一個哈希函數(算法設計者其實也不知道)，這樣做就達到了避免刻意攻擊的目的。這是一種舍伍德算法，即用隨機化方法提高算法在最壞情況下的性能，類似用隨機化方法來優化快速排序(參見參考文獻［12］的7.3節)。下麵簡單介紹通用哈希函數族，對其細節感興趣的讀者可以閱讀參考文獻［12］的11.5節和參考文獻［13］的第13章。
設集合U是一個全域，U≥n，令集合V={0,1,2,3,…,n-1}，H是一個從U到V的哈希函數集合。如果H滿足對於任意的元素x1,x2,x3,…,xk以及從H中均勻隨機選取的一個哈希函數h，的概率小於1/nk-1，那麼將H稱為k-通用哈希函數族。
所以，如果哈希函數h是從2-通用哈希函數族中選取的，那麼對於任何兩個元素x、y，它們的哈希值滿足h(x)=h(y)的概率最多為1/n。
下麵給出一個2-通用函數族的例子：

其中p是質數，

2.算法質量分析
定理3-3　算法3-3輸出數據流中不同元素數目的估計為d，數據流中真實不同元素數目為d,則
證明　形式上，對於j∈［n］和整數r≥0，令Xr,j作為事件zeros(h(j))≥r的指示隨機變量，並令當算法處理完該流時將z的值記作t。如果Yr>0，則表明(3-1)我們可以將上麵的公式重新表示為下麵的形式：(3-2)由於h(j)為(log n)比特字符串上的均勻分布，所以可以得到現在我們對Yr的期望和方差做如下估算。式(3-3)的第一步使用隨機變量Yr的兩兩獨立性，因為h是由2-通用哈希函數族產生的。E［Y(3-3)這樣，分別使用馬爾可夫不等式和切比雪夫不等式，得到
 於是，d=2t+12，令a是滿足2a+12≥3d的最小整數，利用式(3-1)和式(3-4)得到同樣，令b取得最大的整數，這樣有2b+12≤d/3，利用式(3-2)和式(3-5)得到以上證明在以下兩方麵稍顯薄弱。首先，評估d隻能和d在同一數量級，並且不是任意好的近似值。其次，算法失效的概率的上界相當大(2/3≈47%)。當然，我們可以通過用更大的常量替代常量“3”來減小這個概率。但更好的方法是用一個不斷生成的標準——“中位數技巧”，這個方法不會進一步降低評估d的質量。
補充知識:馬爾科夫不等式和切比雪夫不等式
馬爾科夫不等式和切比雪夫不等式是概率分析中常用的概率不等式。
馬爾科夫不等式：設X為隻取非負值的隨機變量，則對任意實數t>0有

切比雪夫不等式：設X為隨機變量，具有有限均值μ和方差σ2，則對任意實數t>0有

3.中位數技巧
想象一下，如果並行運行k個該算法的副本，在這些副本中使用互不依賴的隨機哈希函數，並且輸出k個答案的中位數作為最終結果。如果這個中位數超過3d，那麼至少有k/2個答案超過3d，反之，我們僅僅希望k2/3個答案超過3d。通過標準的切爾諾夫界，這個事件的概率是2-Ω(k)。同樣，中位數小於d/3的概率也是2-Ω(k)。
選擇k=θ(log(1/δ)),我們可以使這兩個概率的和最多為δ。這就得到一個(O(1),δ)近似算法。下一節給出一個不同的算法，可得到一個(ε,δ)近似算法。
原來的算法需要O(logn)位空間存儲一個哈希函數，並需要多於O(log logn)位的空間以存儲z。因此，最終的算法需要的空間為O(log(1/δ)×logn)。當用一個新的算法解決這個問題時，將改善這個空間的界限。
3.4.2　改進算法
針對上述問題，本節給出一個更好的算法。這個算法稱為BJKST算法，BJKST是以Bar-Yossef、Jayram、Kumar、Sivakumar和Trevisan五個作者的名字命名的。介紹這個算法的原論文給出了三個算法，我們將要介紹第三個算法（在某種意義上是“最好的”）。下麵的函數zeros與3.4.1節中的含義相同。常量的值稍後基於算法分析中的需要確定。算法3-4　數據流中元素數量估計改進算法

初始化:
1　從2-通用函數族中隨機選擇哈希函數h:\[n\]→\[n\];
2　從2-通用函數族中隨機選擇哈希函數g:\[n\]→\[bε-4log2n\];
3　z←0;
4　B←;
處理j:
5if zeros(h(j))>z then
6　B←B ∪{ g(j), zeros(h(j))};
7　while B>=c/ε2 do
8　　　z←z+1
9　　　從B中移除所有滿足β<z的(α,β);
輸出：B2z。

直觀地說，這個算法是3.4.1節的算法3-3的改良版。這次，我們不是簡單地計算在數據流中zeros(h(j))的最大值，而是要嚐試確定由所有滿足zeros(h(j))≥z的元素j組成的存儲桶B的大小。如果在數據流中包含d個不同元素，我們可以期望d/2z落入桶中。因此B2z應該是對d的很好的估計。
我們的目的是節省空間，因而希望B小一些，這樣就能存儲足夠的信息來精確地追蹤B值。同時，我們又希望B足夠大，這樣我們生成的估計值就足夠精確。我們可以證明讓B增大到大約O(1/ε2)是個不錯的選擇。最後，為了節約空間，這個算法沒有存儲B中實際的數字，而是存儲基於g的哈希值和zeros(h(j))的值，當B必須縮小時，這兩個值用來刪除B中相應的元素。
使用改進算法對數據流<1,3,3,5,2,2,1,4,4,6,6>的數據流片段給出具體示例，如圖3-2所示。使用與上文相同的哈希函數h(x)=x mod 23進行完全哈希，結果如圖中的統計表所示。
1) 如果不壓縮，即保留所有B，B=6,得到完全精確的值6。
2) 如果設定相關的參數ε，使得z=1，即需要刪除所有哈希值為1的桶，保留下的B=3，使用公式B2z計算得到的不相同元素數為6。
3) 如果設定參數使得z=2，則得到B=1，使用公式B2z得到最終估計值為4。
所以我們需要平衡B的空間和估計的準確度。
下麵我們詳細地分析算法，在這裏，我們假設1/ε2=O(m)，否則這個算法就沒有任何意義。

定理3-4　算法3-4的空間複雜度是
證明　這個算法必須存儲h、g、z和B，其中h和B是主要空間需求，根據有限域哈希函數族中哈希函數的性質，h需要位的存儲空間。存儲桶B的規模限製在每個數據桶中的元組（α，β）需要位來存儲哈希值α，這個哈希值大於存儲數量β所需的存儲空間log logn位。綜上所述，算法3-4的空間複雜度是
算法質量分析
整個分析假設在B中存儲的是(在g下的)哈希值，而不是元素本身，更沒有改變B。不論g在其應用到元素集合時是否發生衝突都是如此。通過選擇足夠大的常量B，並針對每一個選擇的哈希函數h，我們保證估計誤差過大的可能性最多為1/6。因此，使用這個假設增加了最多1/6的錯誤可能性。我們現在在不發生衝突的情況下分析餘下的誤差。
定理3-5　令d表示算法3-4輸出的估計值，d表示數據流中實際的不同元素數量，則
證明　該證明的基本條件與3.4.1節一致。對於每個和整數r≥0，對於，令作為一個指示隨機變量，並且令當算法完成數據流的處理後用t表示z的值，然後得到Yt=B當算法結束時d=Yt2t與3.4.1節中的證明過程一致，得到注意到如果t=0，那麼算法沒有增加z，這就意味著d<c/ε2並且d=B=d。簡單來說，這個實例中算法精確地算出了d的值。
另外一種情況下，t≥1，如果不等於d，那麼我們認為這是個失敗的結果。通過對所有可能的t的r值求和我們能估出這個事件的概率。對於小的r，當t=r時錯誤不會出現，因為錯誤需要Yt很大的偏差。對於大數值的r，僅僅有t=r是不可能的。下麵是將總和分成兩部分的一個直觀體現，我們需要選擇閾值，便於將r的“小”值和“大”值區分開，做法如下。
令s等於一個固定的整數，得到
現在我們用切比雪夫不等式和馬爾可夫不等式來約束式(3-8)中的第一項，然後我們用式(3-6)計算得到
(根據式(3-7))其中最後一步的界限通過選擇一個足夠大的常數c(≥2×24×12)來實現。█
記得我們的初始條件中有一個針對g的沒有衝突的假設，則最後錯誤的可能性最大為1/6+1/6=1/3。因此，上麵的算法(ε，1/3)近似為d。與3.4.1節一樣，通過使用中位數技巧，我們將算法改為對於任意0<δ≤1/3，有算法(ε，δ)近似為d，其空間複雜度增加了O（log(1/δ）)。