挖掘數(shù)據(jù)流

??在許多數(shù)據(jù)挖掘場景中，我們預先知道整個數(shù)據(jù)集。但是有時數(shù)據(jù)輸入速率是由外部決定的，例如谷歌查詢和推特與臉書的狀態(tài)更新，這就涉及到了數(shù)據(jù)流的挖掘。

流數(shù)據(jù)模型

??輸入元組可以在一個或多個流中快速輸入。要求：流不需要具有相同的數(shù)據(jù)速率，一個流的元素之間不需要是時間均勻的。隨之而來的問題是系統(tǒng)不可能存儲所有的數(shù)據(jù)。那么如何利用有限的流量進行關鍵計算？從需要出發(fā)先分析兩個形式的查詢。Ad-hoc查詢：正常查詢一次詢問流例，如到目前為止在流中看到的最大值是多少。標準查詢：詢問所有時間的流的查詢，例如：報告在S流中看到的每個新的最大值

應用

挖掘查詢流

-谷歌想知道今天比昨天查詢更頻繁的是什么

挖掘點擊流

-雅虎想要知道在過去一小時里，它的哪一個頁面獲得了異常數(shù)量的點擊

IP數(shù)據(jù)包可以在交換機上被監(jiān)視

-收集信息以備不時之需
-檢測拒絕服務攻擊

挖掘監(jiān)測數(shù)據(jù)

-每臺監(jiān)控攝像機每隔一秒鐘就會產生一系列圖像
-發(fā)現(xiàn)安全威脅

在流中抽樣數(shù)據(jù)

??在流中抽樣數(shù)據(jù)的目標是從流中提取可靠的樣本。舉一個提示性的例子：一個搜索引擎接收到一系列查詢，它希望研究典型用戶的行為。這些流由元組（用戶、查詢、時間）組成。需要回答諸如：在過去一個月里，典型用戶的問題重復了多少次，假設我們只希望存儲1/10的流元素。一個很容易被想到但不對的方法：先產生一個0到9之間的隨機數(shù)，如果隨機數(shù)是0則存儲元組
??反例：假設一個用戶產生了一個s查詢，其中d被查詢了兩次，沒有一個查詢超過了兩次。正確答案是 d/(s+d)，用上面的解決方法我們得到的是d/(10s+19d)。

解決方法

??有鍵的元組流：鍵是每個元組主鍵的某個子集，例如元組（用戶,搜索，時間)，鍵是用戶；鍵的選擇依靠應用程序。得到一個大小為a/b的樣本：將每個元組的鍵統(tǒng)一哈希到b個桶；如果其哈希值a為最多，則選擇該元組。

保持一個固定大小的樣本

??假設我們需要保持樣本的大小正好是s例如：主內存大小約束。事先不知道流的長度：事實上，流可以是無限的。假設在t時刻我們看到了n項:確保每一項在樣本中都有等概率s/n。
解決方案
??存儲流的所有第一個s元素。假設我們看到n- 1個元素，現(xiàn)在第n個元素到達(n > s)：對于概率s/n，選擇第n個元素，否則就丟棄它；如果我們選擇第n個元素，它會替換樣本中的一個s元素，隨機選擇。聲明:該算法用于維護一個具有所需屬性的樣本也就是說，在長度為n的流中，所有位置被選中的概率都相等為s/n。
用歸納法證明:假設在n個元素之后，樣本包含到目前為止看到的概率為s/n的每個元素。當我們看到元素n+1時，它的概率是s/ (n+1)。對于樣本中已經存在的元素，留在樣本中的概率為s/(n+1)
??滑動窗口。流處理的一個有用的模型是查詢是關于長度為N的窗口，即接收到的N個最近的元素。備選項:在時間間隔T內接收的元素。有趣的情況:N太大了，不能存儲在主內存中?；蛘撸刑嗟牧?，所有的windows都不適合主內存。

過濾流

??過濾:接受流中滿足條件的元組。過濾的標準：可計算的元組屬性(容易)；查找集合中的成員，其中集合太大，無法存儲在主內存中(有趣)，在這種情況下可以使用布魯姆過濾器。其可以應用在Web爬蟲中過濾抓取的url；在黑名單中過濾電子郵件；在黑名單中過濾惡意軟件。

過濾流:布魯姆過濾器

??布魯姆過濾器組成：一個由n個位組成的大數(shù)組，幾乎都是0；一個散列函數(shù)h1, h2……h(huán)k的集合。每個哈希函數(shù)將鍵值映射到n個桶，對應于位數(shù)組的n位；m個鍵值的集合S。
查找：假設元素y出現(xiàn)在流中，我們想知道是否見過y，我們需要為每個散列函數(shù)計算hi(y) 1<=i<=k。如果所有生成的位位置都是1，就說我們以前見過y。錯誤的假設是可能的如果這些位置中至少有一個是0，就說我們以前沒見過y。這種方法當然是對的。

過濾流:Bloom Filter示例

??查找：假設我們有和之前一樣的布隆過濾器，我們將過濾器設置為10100101010；查詢:我們看到y(tǒng)=118了嗎？
解決方案
y = 118 = 1110110(二進制)
h1(y)=14模11 = 3
h2(y)= 5模11 = 5
第5位是1，第3位是0，所以我們確定y不在集合中。

布隆過濾分析

??誤報的概率取決于數(shù)組中1的密度和散列函數(shù)的數(shù)目，1的數(shù)量大約是插入元素的數(shù)量乘以哈希函數(shù)的數(shù)量，但是碰撞稍微降低了這個數(shù)字。

布隆濾波分析:投擲飛鏢

??將隨機位從0轉到1就像隨機地向t目標投擲d鏢一樣。一個鏢至少擊中了多少目標？給定的目標被給定的鏢命中的概率= 1/t。沒有被d飛鏢命中給定目標的概率是(1- 1/t)^d
重寫為(1- 1/t)^t(d/t) ~= e^- d/t，因為(1- 1/t)^t~=1/e對于 t很大。

布魯姆濾波分析:投擲飛鏢的例子

??假設我們使用一個10億比特的數(shù)組,5個哈希函數(shù),我們插入1億個元素。即t=10的9次冪，并且d=5*10的8次冪。剩下的0的分數(shù)是e^(- 1/2)=0.607密度1 = 0.393。

在窗口中計數(shù)

??你可以表明，如果堅持對窗口中的元素進行精確的求和或計數(shù)，那么就不能使用比窗口本身更少的空間。但是如果你愿意接受一個近似，你可以使用更少的空間。我們將把計算某種類型的元素的簡單情況視為特殊情況。和是相當直接的延伸。
??計算部分：問題:給定一個0 s和1 s的流，準備回答以下問題:在最近的k位中有多少個1 ?其中k <= N；簡單解決方案:存儲最近的N位；但是回答這個問題需要很O(K)時間，這個時間很可能要太長。例如:一些計算，像計算一個站點的url最近的點擊率。流是URL 的序列，窗口大小N= 10億。將數(shù)據(jù)看作多個流——每個URL對應一個流。URL x的流上的位是0，除非實際的流有x，那么則為1。

DGIM方法

??每個流只存儲O(2logN)位，其中N是窗口大小。給出大概的答案，不要超過50%。使用更復雜和按比例增加的存儲位，誤差因子可以減少到任何大于0的數(shù)。

時間戳

??流中的每個位都有一個時間戳，開始0,1，……。記錄時間戳的模N(窗口大小)，因此我們可以用O(log2N)位表示任何相關的時間戳。

存儲桶

??桶是窗口的一部分;它由一個記錄組成：它的時間戳的端點O(logN)位，在它的開始和結尾之間1的數(shù)目等于桶的大小。桶大小限制:1的數(shù)目必須是2的冪。因此，此計數(shù)只需要O(loglogN)位。

用桶表示流

??桶的要求： 桶的右端總是1和1的正數(shù)；每個帶1的正數(shù)都在某個桶里；一個或兩個桶任意大小，直到某個最大大?。凰谐叽缍急仨毷?的冪；桶不重疊；桶是按大小排序的:舊桶并不比新桶??；更新桶：當一個新比特進來時，如果最后一個(最老的)桶的結束時間在當前時間之前的N個時間單位之前，則將其丟棄。如果當前位為0，則不需要進行其他更改;如果當前位是1,為這個位創(chuàng)建一個大小為1的新桶 結束時間戳=當前時間。如果現(xiàn)在有3個桶大小為1，那么將生成時間最久的2個桶合并為2個桶，如果現(xiàn)在有3個2碼的桶,將生成時間最久的2碼的桶合并成4碼的桶，依次類推。

查詢

??估計最近k<=N位中1的個數(shù)，找到具有最早的時間戳的桶b，該時間戳至少包含k個最近的位。估計1 s的個數(shù)是所有桶的大小之和比桶b最近，加上桶b本身的一半大小。誤差范圍：假設范圍內最老的桶的大小是2^i。然后通過假設2 ^(i- 1)的1仍在窗口中,我們使錯誤最多2 ^ (i- 1)。因為每個大小小于2ⁱ的桶至少有一個，而且最老的桶至少有一個，所以真正的和不小于2^i。因此，錯誤最多為50%?？臻g要求:我們可以用O(logN)位表示一個桶;任何桶的大小都不能大于N;最多有兩個桶大小相同(范圍1到logN);最多有2logN桶;因此，所需空間為O(log2N)。

流的聚類

集群的流

??某些空間中的數(shù)據(jù)點流(歐幾里得或非歐幾里得)問題：對于任何m<=N，從該點的最后m個點組成的最佳簇的中心或簇(簇的代表點)。我們將考慮一些可能的解決方案，這取決于我們對集群如何在流中演化的假設。

BDMO算法

??BDMO算法是在DGIM算法的基礎上構建的。關鍵的相似點和不同點是：和DGIM一樣，流的點也被分成若干塊，用桶來概括。在這里，桶的大小是它表示的點的數(shù)量，而不是流元素的數(shù)量是1。和以前一樣，桶的大小遵守每個大小都有一個或兩個的限制，直到某個限制。我們不假設允許桶大小的順序從1開始。相反，它們只需要形成一個序列，其中每個大小是以前大小的兩倍。例如:3,6,12,24。桶的大小不會隨著時間的推移而減小。
??桶的內容包括桶的大小，桶的時間戳，一組記錄，它們表示已將桶的點分區(qū)到的集群：群集中的點數(shù)；星團的質心或團簇；合并集群和保持與合并集群的完整參數(shù)集近似所需的任何其他參數(shù)。
??初始化桶：最小的桶大小是p乘以(2的冪)。因此，每一個p流元素，我們用最近的p點創(chuàng)建一個桶。每個桶的時間戳是桶中最近一點的時間戳。存儲桶中的集群點(或者將它們作為一個集群保留)，計算集群的中心或clustroid并計算每個集群中的點。
??合并桶:類似于在流的計數(shù)為1的問題中合并桶。如果某個bucket的時間戳在當前時間之前超過N個時間單位，則刪除它。如果有3個p大小的桶，合并3個中最老的兩個。如果現(xiàn)在有3個大小為2p的桶，合并3個桶中最大的2個。如果現(xiàn)在有3個桶大小是4p，……
??合并桶(合并兩個連續(xù)的桶):新桶的大小是正在合并的兩個桶的兩倍。新桶的大小是正在合并的兩個桶的兩倍。合并桶的時間戳是兩個連續(xù)桶中最近的時間戳?？紤]在兩個桶中合并集群(取決于聚類算法)。

回答查詢

??查詢:請求流中最近m個點的集群(m<=N)。解決方案：選擇覆蓋m個點的最小的桶集。這些桶可能不超過2百萬個點。假設:2m和m+1之間的點與最近的m點沒有根本不同(為了更好的近似)。從選定的桶中收集所有集群，例如:如果您要求K- cluster，我們將繼續(xù)合并，直到使用上面內容中合并桶的方法得到K- cluster。