《Mining of Massive Datasets》 第四章（Mining Data Streams ）知識(shí)點(diǎn)提要
本章 pdf 下載鏈接：http://infolab.stanford.edu/~ullman/mmds/ch4.pdf
本書(shū)資料鏈接：http://mmds.org

前言

• 流數(shù)據(jù)處理的若干限制
  1. 數(shù)據(jù)以一個(gè)或多個(gè)流的方式到來(lái)谆扎，流元素分發(fā)速度快抒倚，必須對(duì)數(shù)據(jù)及時(shí)處理
  2. 通常來(lái)說(shuō)數(shù)據(jù)量十分大，無(wú)法存儲(chǔ)整個(gè)數(shù)據(jù)流
• 流處理算法通常在內(nèi)存中執(zhí)行，一般不會(huì)或者極少訪問(wèn)二級(jí)存儲(chǔ)器
• 數(shù)據(jù)流處理的每個(gè)算法都在某個(gè)程度上包含流的匯總過(guò)程
• 核心問(wèn)題：How to make critical calculations about the stream using a limited amount of memory?
• 流處理算法的原則：通常情況下衩匣，獲得問(wèn)題的近似解比精確解要高效得多。

1. 流處理模型

1.1 數(shù)據(jù)流管理系統(tǒng)

• 類比數(shù)據(jù)庫(kù)管理系統(tǒng)颤绕，流處理器實(shí)際上也可以看成是一個(gè)數(shù)據(jù)管理系統(tǒng)

  
  
  數(shù)據(jù)流管理系統(tǒng)
  
  

  若干個(gè)流進(jìn)入系統(tǒng)躏嚎，每個(gè)流的數(shù)據(jù)流、數(shù)據(jù)類型不必相同诫肠，流元素到達(dá)速率不受系統(tǒng)控制司澎，對(duì)流數(shù)據(jù)，不及時(shí)處理會(huì)永久丟失栋豫。

• 歸檔存儲(chǔ)器容量大挤安，速度慢，通常進(jìn)行歸檔處理丧鸯，無(wú)法滿足快速應(yīng)答查詢蛤铜，但是同樣不能存儲(chǔ)整個(gè)數(shù)據(jù)流
• 有限工作存儲(chǔ)器容量小，速度快，可存儲(chǔ)部分流數(shù)據(jù)围肥，用于快速應(yīng)答查詢
• ad-hoc 查詢：用戶根據(jù)自己的需求剿干，靈活的選擇查詢條件，系統(tǒng)能夠根據(jù)用戶的選擇生成相應(yīng)的統(tǒng)計(jì)報(bào)表穆刻，用戶無(wú)需對(duì) SQL 和數(shù)據(jù)庫(kù)架構(gòu)有了解

1.2 流查詢

流查詢主要有兩種方式：固定查詢（standing query）和 ad hoc 查詢置尔。

固定查詢

固定查詢永遠(yuǎn)不變地執(zhí)行并在適當(dāng)?shù)臅r(shí)候產(chǎn)生輸出結(jié)果，如查詢傳感器的最高溫氢伟。

ad hoc 查詢

• 通過(guò)存儲(chǔ)數(shù)據(jù)流的合適部分或者流概要信息來(lái)為查詢的應(yīng)答做準(zhǔn)備
• 可以在工作存儲(chǔ)器上保存每個(gè)流的滑動(dòng)窗口榜轿，將窗口看成是關(guān)系數(shù)據(jù)庫(kù)而在其上執(zhí)行任意的 SQL 查詢

2. 數(shù)據(jù)抽樣

2.1 固定比例抽樣

樣本的規(guī)模會(huì)隨著流的增長(zhǎng)而增長(zhǎng)

假定搜索引擎收到查詢流，流由三元組（user,query,time）組成
Question：在過(guò)去一個(gè)月用戶所提交的重復(fù)查詢的比率是多少腐芍？假設(shè)只能存儲(chǔ) 1/10 的流元素

顯然的做法是對(duì)每個(gè)查詢產(chǎn)生一個(gè) 0~9 的隨機(jī)數(shù)差导，當(dāng)且僅當(dāng)隨機(jī)數(shù)為0時(shí)才存儲(chǔ)該元組。大數(shù)定律會(huì)保證大部分用戶所存儲(chǔ)的查詢比例接近 1/10猪勇。

但是设褐，如果問(wèn)題變成求用戶提交的平均重復(fù)查詢數(shù)目，上述抽樣機(jī)制會(huì)帶來(lái)錯(cuò)誤泣刹。

• 假設(shè)某用戶有 x 個(gè)搜索查詢提交了一次助析， d 個(gè)搜索查詢提交了兩次，不存在超過(guò) 2 次的其他查詢椅您。
• 顯然該問(wèn)題的正確答案時(shí)：d/(x+d)

但是外冀，如果采用上述 1/10 的抽樣機(jī)制，得到的結(jié)果會(huì)是 d/( 10x+19d )

• 對(duì)于原本 d 個(gè)提交 2 次的搜索查詢掀泳，只有 d/100 會(huì)在樣本中再重復(fù) 2 次（1/10 * 1/10 * d）

• 而原本 d 個(gè)提交 2 次的搜索查詢樣本中只出現(xiàn)一次的概率是：1/10 * 9/10 + 9/10 * 1/10 = 18/100
  

  因此雪隧，平均重復(fù)查詢數(shù)目:

代表性樣本采樣

• 挑選1/10 的用戶并將他們所有的搜索查詢放入樣本中，不考慮其他用戶的搜索查詢
• 使用哈希函數(shù)將用戶名或用戶 ID 哈希到桶中员舵，提取一個(gè)桶的用戶脑沿。
• 更一般的，若想得到 a/b 比例的用戶马僻，可以哈希到 b 個(gè)桶中庄拇，提取前 a 個(gè)桶。

選擇哪些用戶作為代表性用戶至關(guān)重要

樣本規(guī)模的變化

• 哈希函數(shù) h韭邓，元組鍵值 K措近，閾值 t
• 樣本由滿足 h(K) <= t 的元組組成
• 調(diào)整樣本空間大小：降低閾值 t 為 t-1女淑，刪除樣本空間中 h(K) = t 的元組

2.2 固定窗口大小抽樣

樣本空間大小固定瞭郑，不會(huì)隨著流規(guī)模的擴(kuò)大而增長(zhǎng)

• 樣本空間 S，能容納 s 個(gè)樣本
• 任何時(shí)候都盡可能保持足夠多的元組鸭你，并且樣本空間已滿時(shí)凰浮，隨著流增長(zhǎng)會(huì)丟棄某些元組我抠，丟棄元組會(huì)被新元組取代。
• 保證任何時(shí)候選擇選擇某一任意位置的概率和選擇其他位置的概率相等袜茧〔送兀可用歸納法證明，n 個(gè)元素時(shí)概率是 s/n笛厦，第 n+1 個(gè)元素到達(dá)時(shí)是 s/n+1纳鼎。

3. 流過(guò)濾

即只接受流中滿足某個(gè)準(zhǔn)則的元組集合。

布隆過(guò)濾器

一個(gè)布隆過(guò)濾器由以下幾部分組成

1. n 個(gè)位組成的數(shù)組（視為 n 個(gè)桶）裳凸，每個(gè)位的初始值為0贱鄙。
2. 一系列哈希函數(shù) h1,h2 ... hk。每個(gè)哈希函數(shù)將流元組鍵值映射到上述 n 個(gè)桶中姨谷。
3. m 個(gè)鍵值組成的集合 S（樣本準(zhǔn)則）逗宁。

• 對(duì)于流中的元組，若鍵值在集合 S 中梦湘，則通過(guò)過(guò)濾器瞎颗。
• 對(duì)于集合 S 中所有鍵值，利用每個(gè)哈希函數(shù)進(jìn)行處理捌议，將在數(shù)組的對(duì)應(yīng)位置為1哼拔。
• 當(dāng)鍵值K的流元素到達(dá)時(shí)，檢查所有的哈希函數(shù)h對(duì)應(yīng)為是否為1瓣颅，如果是則允許通過(guò)倦逐。

假陽(yáng)率

所有真正的負(fù)例當(dāng)中被判為正例的比例，即本來(lái)不能通過(guò)的流元素卻通過(guò)過(guò)濾的比例

使用飛鏢投擲模型來(lái)模擬布隆過(guò)濾宫补。假設(shè) y 支飛鏢和 x 個(gè)靶位檬姥，預(yù)計(jì)給定靶位至少被投中一次的概率。

• 給定飛鏢不能投中給定靶位概率 (x-1)/x

• y 支飛鏢全部沒(méi)有命中給定靶位的概率 [(x-1)/x]^y粉怕，即

• 根據(jù)重要極限公式
  
  

  y 支飛鏢全部沒(méi)有命中給定靶位的概率為 e^(-y/x)健民，故假陽(yáng)率位 1- e^(-y/x)
  

  故對(duì)于有 k 個(gè)哈希函數(shù)的布隆過(guò)濾器，假陽(yáng)率為

4. 流中獨(dú)立元素的數(shù)目統(tǒng)計(jì)

使用若干不同的哈希算法和隨機(jī)算法斋荞，在每個(gè)流空間開(kāi)銷較小的情況下得到近似結(jié)果

FM（Flajolet-Martin）算法

• 基本思想：如果流中看到的不同元素越多荞雏，那么不同的哈希值也會(huì)越多虐秦，同時(shí)平酿，也越可能看到其中一個(gè)值變得“異常”悦陋。具體的異常性質(zhì)是該值后多個(gè)0結(jié)束蜈彼。
• 任何流元素 a 應(yīng)用哈希函數(shù) h 時(shí)，位串 h(a) 的尾部將以 0 結(jié)束（可能沒(méi)有）俺驶，尾部 0 的數(shù)目稱為尾長(zhǎng)幸逆，流中所有元素的最大尾長(zhǎng)為 R棍辕。
• 用 2^R 來(lái)估計(jì)目前為止流中獨(dú)立元素?cái)?shù)目。

流元素 a 的哈希值 h(a) 末尾至少有 r 個(gè) 0 的概率為 2^(-r)还绘。

假定流中有 m 個(gè)獨(dú)立元素楚昭，那么任何元素的哈希值末尾不滿足至少有 r 個(gè) 0 的概率為

即

可改寫(xiě)為

• 結(jié)論
  1. 如果 m 遠(yuǎn)大于 2^r，那么發(fā)現(xiàn)一個(gè)尾長(zhǎng)長(zhǎng)度至少為 r 的概率接近1拍顷；
  2. 如果 m 遠(yuǎn)小于 2^r抚太，那么發(fā)現(xiàn)一個(gè)尾長(zhǎng)長(zhǎng)度至少為 r 的概率接近0。

組合估計(jì)

1. 平均值

假定在每個(gè)哈希函數(shù)上得到不同的 2^R昔案，然后求平均值

• 會(huì)受到偶然極大值得影響尿贫，即某個(gè)哈希函數(shù)得到的 2^R 過(guò)大。（ 2^R 是以指數(shù)成倍增長(zhǎng)的）

2. 中位數(shù)

取每個(gè)哈希函數(shù)得到不同的 2^R 的中位數(shù)踏揣。

• 得到的值永遠(yuǎn)都是 2 的冪庆亡，不可能得到非常近似的估值

3. 平均值和中位數(shù)組合

先將哈希函數(shù)分成若干組，組內(nèi)取平均值捞稿，組外取中位數(shù)

或

將哈希函數(shù)分成若干組又谋，組內(nèi)取中位數(shù)，組外取平均值

5. 矩估計(jì)

流的 k 階矩：流中至少出現(xiàn)一次的元素出現(xiàn)次數(shù)的 k 次方之和

• 0 階矩表示流中獨(dú)立元素個(gè)數(shù)
• 1 階矩表示整個(gè)流的長(zhǎng)度括享，也就是元素個(gè)數(shù)
• 2 階矩度量流中元素分布的非均勻性搂根。越小越均勻。

二階矩估計(jì)的 AMS 算法