《大數據算法》一3.5　尋找頻繁元素的隨機算法

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

3.5　尋找頻繁元素的隨機算法

本節重新研究3.3節中討論的問題，提出尋找頻繁元素的隨機算法。Misra-Gries算法通過掃描數據一次提供足夠的信息，然後通過第二次掃描數據解決頻繁元素發現問題，即掃描數據第一次過程中Misra-Gries算法計算一個數據結構，對於j∈［n］該數據結構可以獲得其頻率fj的足夠準確估計fj。本小節提出另外兩個頻率估計的隨機算法。

3.5.1　略圖法

1.略圖和線性略圖
在處理數據流σ的過程中，令表示Misra-Gries算法中所需的數據結構。這種數據結構的一個缺點是缺少一種通用的方法從和中計算其中“”代表數據流的連接。很明顯，需要這種數據結構上的連接操作，如果一個數據結構支持這種連接操作，則該數據結構稱為略圖，具體定義如下。
　　定義3-3　D(σ)是一種以流的方式處理流σ的數據結構，這種數據結構稱為略圖，如果有一個空間有效組合算法COMB，對於任意兩個數據流σ1和σ2，計算

本節的每個算法都有很好的性質，就定義3-3的意義而言，這些算法能計算輸入流的略圖。因為這些算法要計算由σ決定的頻率向量f(σ)，它們的略圖會自然成為f(σ)的函數。事實上，它們應當是線性函數，這涉及另外一個定義。
　　定義3-4　略圖算法“sk”稱為線性略圖，如果對於每個域［n］上的數據流σ，sk(σ)的取值範圍在l=l(n)維的向量空間上，並且sk(σ)是f(σ)的線性函數。在這種情況下，l稱為線性略圖的緯度。
注意，對於線性略圖的結合算法隻是僅僅在相應向量空間上增加略圖。
除了不能產生略圖，Misra-Gries算法還有其他缺點，就是不能延伸到十字轉門（甚至嚴格的十字轉門）模型。但是本節的算法能夠實現，因為基於線性略圖的數據流算法從一般模型到十字轉門模型都是通用的。如果在一般模型中的j使我們向略圖增加一個向量vj，然後十字轉門模型中修正的（j,c）在略圖中增加cvj，這樣可以處理c≥0和c<0的不同情況。
2.計數略圖
現在我們描述第一個略圖算法，稱為“計數略圖”。我們從基本略圖開始討論，這個略圖已經包含了大部分所需思想。這個略圖有一個極小並且是正數的精度參數ε。算法3-5　元素頻率計數略圖算法

初始化:
1　C［1,…,k］←0，其中k=3/ε2;
2　從2通用函數族中隨機選擇哈希函數h:［n］→［k］;
3　從2通用函數族中隨機選擇哈希函數g:［n］→{-1,1};
處理(j,c):
4　C［h(j)］←C［h(j)］+cg(j);
輸出:
5　對於查詢a,輸出f→a=g(a)C［h(a)］。

通過這個算法計算的略圖是一個計數器數組C，這個數組可以看作zk上的一個向量。若要使兩個略圖是可結合的，則它們必須基於同樣的哈希函數h和g。
使用該算法，對數據流片段給出的示例如圖3-3所示。依據(j,c)值不斷計算h(j)、g(j)使用更新C［h(j)］的值。計算過程如下：

針對每個數據流計算其h(j)、g(j),更新C［h［j］］的值。對於查詢a使用最後更新數組C進行計算，輸出估計值。
3.計數略圖質量分析
定理3-6　對於任意查詢a，算法3-5生成的估計滿足
證明　固定查詢a，考慮基於查詢a的輸出X=fa。對於每個j∈［n］，當h(j)=h(a)時，讓Yj作為指示器，有
0，h(j)≠h(a)　　檢查算法的工作原理，我們發現當且僅當h(j)=h(a)時，j對計數器C［h(a)］有貢獻，並且貢獻的總和是隨機符號g(j)的fj倍。因此，因為g和h是獨立的，所以有因此，通過期望的線性度，有因此，輸出X=fa是一個對於所需頻率fa的無偏估計量。
我們仍然需要證明X不可能偏離其平均值太多。為此，我們分析其差異。根據2-通用哈希函數族的性質，對於每個
有　下一步，我們利用g所對應2-通用函數族的性質，以及g和h的獨立性，可總結出對於所有有　因此可計算得到(根據式（3-9）、式(3-11)和式(3-12))
(3-13)其中f=f(σ)是由σ決定的頻率分布。從式（3-10）到式（3-13），用切比雪夫不等式得到　　對於
，我們定義f-j為（n-1）維的向量，這個向量通過去掉輸入f的第j維元素得到，有因此，我們可以用下麵這個更加深刻的形式重寫上麵的公式。.改進略圖
略圖即通常所說的“計數略圖”，這實際上是通過對上述基本略圖應用中位數技巧（參見3.4節）獲得的略圖，對於給定的足夠小的δ>0，使其錯誤的概率降到δ。因此，計數略圖可看作二維計數器數組，其中每一個數據流中的元素導致流中若幹計數器的更新。為了完整起見，我們用下述算法討論之。

初始化:
1　C［1,…,t］［1,…,k］←0,其中k=3/ε2且t=O(log(1/δ));
2　從2通用哈希函數族中隨機選擇哈希函數h1，…，ht:［n］→［k］,
3　從2通用哈希函數族中隨機選擇哈希函數g1，…，gt:［n］→［lk］;
處理(j,c):
4　for i=1 to t do C［i］［hi(j)］←C［i］［hi(j)］+cgi(j);
輸出:
5　對於查詢a,輸出fa=median1≤i≤tgi(a)C［i］［hi(a)］。

像3.4節一樣，可以使用一個標準的切爾諾夫界參數證明估計量fa滿足Pr［fa-fa≥εf-a2］≤δ通過適當選擇哈希函數族，我們能將哈希方程存儲在O(tlog n)的空間。在略圖中的每個tk計數器占據O(log m)的空間。這就給我們一個整體的限製空間，即　計數最小略圖
另一種頻率評估的解決方案就是所謂的“計數最小略圖”。與計數略圖相同，這個略圖也采用一個精度參數ε和一個誤差概率參數δ，並包含一個t×k的二維計數數組，用基於哈希函數的方法來更新。t和k的值基於ε和δ來設置，偽代碼如下所示。算法3-6　計數最小略圖算法

初始化:
1　C［1，…，t］［1，…，k］←0→,其中k=2/ε,t=log(1/δ);
2　從2通用哈希函數族中選取t個哈希函數h1，…，ht:［n］→［k］；
處理(j,c)：
3　for i=1 to t do C［i］［hi(j)］←C［i］［hi(j)］+c;
輸出：
4　在查詢a中，令fa=min1≤i≤tC［i］［hi(a)］。

注意這個算法相比計數略圖簡單了很多，另外，還要注意其占用空間為這要比計數略圖好1/ε倍。計數最小略圖的缺點在於它的近似比保證，這也是我們接下來將要分析的。
計數最小略圖質量分析
我們關注當每個流中的元素（j,c）滿足c>0的情況,也就是現金注冊模型，顯然，在這種情況下，每個對應元素a的計數器是對fa的過高估計,這樣總有其中fa是算法輸出的fa的評估。
定理3-7　
證明　對於固定的a，現在我們分析在計數器中超出真實值的部分。令隨機變量Xi表示超出真實值的部分。對於,令Yi,j作為事件hi(j)=hi(a)的指示。注意當且僅當Yi,j=1且被觸發時，j作用於計數器C［i］［hi(a)］，它使得fj被加入這個計數器。這樣有由於hi是2通用哈希函數族，因此得到這樣，通過數學期望的線性可加性可得對於每個fj≥0,有Xi≥0，我們可以通過選擇的k值應用馬爾可夫不等式得到　上述概率是對於一個計數器進行分析的結果。我們有t個這樣的計數器，且它們相互獨立。輸出中的fa-fa是Xi中的最小值，其中i∈［t］。這樣有
≤12t通過對t的選擇，可以讓這個概率最大為δ。■
至此，我們證明了，最高概率時，有其中左不等式總是成立，右不等式在概率為最大δ時失效。
這個評估弱於計數略圖,其原因是它的偏差以εf-a1為界，而不是εf-a2。對於所有矢量z∈Rn，有這個不等式在z有一個非零項時是緊的。且當z中所有值的絕對值都相等時最弱，此時兩個範數相差因子n。這樣，當流的頻率向量更加分散時，與計數最小略圖相比,計數略圖的評估質量將會提升。