204
《大數據算法》一3.3 尋找頻繁元素的非隨機算法
本節書摘來異步社區《大數據算法》一書中的第3章 ，第3.3節，王宏誌 編著, 更多章節內容可以訪問雲棲社區“異步社區”公眾號查看。
3.3 尋找頻繁元素的非隨機算法
上麵講的是一個簡單的例子，接下來講一個複雜的例子——頻繁元素。
頻繁元素指的是在數據流當中同一個元素出現多次，希望找到出現最頻繁的元素。我們看一個例子：在數據流狀態<32,12,14,32,7,12,32,7,6,12,4>中，當前最頻繁的元素是32和12。這兩個都是最頻繁元素。
頻繁元素問題
輸入：流
,隱式地定義了一個頻率向量f=(f1,…,fn)。注意f1+…+fn=m。
輸出：對於一個參數k，輸出集合
頻繁元素問題有廣泛的應用。在網絡當中找到“elephant flow”、ip地址等，在搜索引擎中找到頻繁查詢，可以給這些最頻繁的查詢做一些優化。在應用當中求頻繁元素時有一個假設，即Zipf原則:典型的頻率分布是高度偏斜的，隻有少數頻繁元素，大多數元素是非常不頻繁的。這個假設是合法的，根據統計一般最多10%的元素占元素總個數的90%。
3.3.1 頻繁元素的精確解
求精確解的方法很簡單，可以對每一個單獨元素設置一個計數器。當處理一個元素時，增加相應計數器。
例如求上述數據流中的頻繁元素。
1） 首先，32到來，給32設一個計數器，並加1，得到<32,1>。
2） 接著12到來，給12設一個計數器，並加1，得到<32,1>，<12,1>。
3） 接下來給14設一個計數器，得到<32,1>，<12,1>，<14，1>。
4） 32又來了，給32的計數器加1,得到<32,2>，<12,1>，<14，1>。
5） 依此類推，最終結果為<32,3>，<12,3>，<14，1>,<7,2>,<6,1>,<4,1>。
這樣做確實能得到精確解。但缺點是很明顯的，隻要數據流裏麵有一個新元素，在內存當中就要保存這個元素和它的計數器。如果在整個數據流中不同數據的數量非常大，則它所需要的內存量也是非常大的。這意味著沒有一個很具體的界限。最壞情況是需要維護n個計數器，數據的個數就是計數器的個數。但在現實當中可以提供的計數器個數k是遠小於n的，因此，可以退而求其次，求近似解。
3.3.2 頻繁元素的Misra-Gries算法
Misra-Gries算法是一個計算頻繁元素的非隨機化近似算法。求解思想為：對於接收到的元素x，如果已經為其分配計數器，則把相應計數器加1；如果沒有相應計數器，但計數器個數少於k,就為其分配計數器，並設為1，意味著內存中還有空間；如果當前計數器的個數為k，說明內存已經滿了，則把所有計數器減1，然後刪除取值為0的計數器，這樣內存就又有空間了，再依次處理下一個x。
考慮上麵的例子，其中n=6，k=3，m=11。
1) 接收32，內存有空間，為其分配計數器，內存狀態<32,1>。
2) 接收12，內存有空間，為其分配計數器，內存狀態<32,1>，<12,1>。
3) 接收14，內存有空間，為其分配計數器，內存狀態<32,1>，<12,1>,<14,1>。
4) 接收32，32對應計數器加1，內存狀態<32,2>，<12,1>,<14,1>。
5) 接收7，7不在內存當中，需要為其分配新的計數器，但是內存沒有空間了。這時將所有計數器減1，然後把值為0的計數器刪除，這時候，12和14的計數器就沒有了。注意此時不將7的計數器加1,內存狀態<32,1>。
6) 接收12，內存又有空間，為其重新分配計數器，內存狀態<32,1>，<12,1>。
7) 接收32，32對應計數器加1，內存狀態<32,2>，<12,1>。
8) 接收7，為其分配計數器，內存狀態<32,2>，<12,1>,<7,1>。
9) 接收6，這時候內存滿了，把所有計數器減1，然後把值為0的計數器刪除,內存狀態<32,1>。
10) 接收12，內存又有空間，為其再重新分配計數器，內存狀態<32,1>，<12,1>。
11) 接收4，為其分配計數器，內存狀態<32,1>，<12,1>,<4,1>。
這時候，如何根據計數器估計x出現的次數？最直接的辦法是將內存裏最後的數據定為x出現的次數，計數器在內存中將x返回，沒有則返回0。很顯然這種方法低估了計數問題，32出現了3次，但是最後隻返回1次。
該算法的偽代碼如算法3-2所示。算法3-2 求元素頻率
初始化:A←;
處理j:
if j ∈ keys(A) then
A\[j\]←A\[j\]+1
else if keys(A)<k-1 then
A\[j\]←1
else
foreach ∈keys(A) do
A\[\]←A\[\]-1
if A\[\]=0 then從A中移除;
輸出:對於查詢a, if a∈ keys(A),then輸出fa=Aa,else輸出fa=0。
算法精確性分析
定理3-2 算法3-2求得的元素a、頻率估計fa和真實值fa之間的關係滿足
，其中m是數據流中所有元素出現的次數，m′是當前所有計數器之和。
證明 由於在計算過程中每個元素對應的計數器都可能減掉一些值，故顯然
下麵通過分析刪除最多的元素數分析fa與fa之差的上界。這二者的差距是由a所對應計數器的減少所引起的，出現一個減少計數器的步驟，相應計數器就要減少一次。因而問題轉化為整個計算過程中a對應計數器減少的次數。
注意到在計算過程中，隻有內存已經滿了的時候，即已經有k個計數器的時候，才執行計數器減少步驟，而此時每個計數器減少了1，意味著共減少了k。而在出現減少的時候，應該往內存裏放的元素並沒有放到內存中，也就是說未計入輸入元素的此次出現，因此，每次計數器減少的步驟相當於減少了k+1。整個數據流的元素總數是m，內存中保存的計數總數是m′，每一輪計數器減少步驟減少了k+1，那麼應該有（m-m′）/（k+1）個計數器減少步驟，這也就意味著fa和fa最多相差（m-m′）/（k+1），即
。■
由上述分析可見，當數據流中元素的總數遠大於（m-m′）/（k+1）時，可得到頻繁項的一個好的估計。而且錯誤的界限和k成反比，因為k越大估計值和真實值相差越小，即內存越大誤差越小。
可以利用略圖計算錯誤的界限，在內存中記錄m、m′和k，然後，把內存裏最後一個頻繁元素再加上相差的值，就可以得到頻繁元素真實值的一個上界，而內存中保存的估計值是頻繁元素的一個下界。在頻繁元素的真實值範圍之內，估計就準確得多。該算法有效的原因源於Zipf原則，就是說極少數元素出現的次數非常多，而大多數元素出現的次數非常少。
最後更新：2017-06-21 13:31:55