大數據背景下的數據流挖掘技術

朱彥杰

許昌學院

數據流處理在某種程度上包含流的匯總過程，考慮如何從流中抽取有用樣本，以及如何從流中過濾大部分不想要的元素。估計流中的元素個數，其中估計方法所用的存儲開銷遠小于列舉所有所見元素的開銷。

Web 網站收到的流包括各種類型，如百度一天收到幾億個搜索查詢，新浪各個不同網站上收到數十億個“點擊”，基于這些流數據可以學習到很多有趣的結果，如某個鏈接的點擊率的突然上升可能意味著有些新聞連向此網頁，否則的話可能意味著該鏈接失效急需修復。

1 流數據

Web 網站收到的流包括各種類型，如百度一天收到幾億個搜索查詢，新浪各個不同網站上收到數十億個“點擊”，基于這些流數據可以學習到很多有趣的結果，如某個鏈接的點擊率的突然上升可能意味著有些新聞連向此網頁，否則的話可能意味著該鏈接失效急需修復。數據以一個或多個流的方式到來，如果不對數據進行及時的處理或存儲，數據將會永遠丟失，即是數據到來的速度太快，以致將全部數據存在傳統數據庫并在選定的時間進行交互是不可能的。流數據處理所受的一些限制，一方面，流元素的分發速度通常很快，必須對元素進行實時處理，否則就會永遠失去處理它們的機會，除非訪問歸檔存儲器。流處理算法通常在內存中執行，一般不會或者極少數訪問二級存儲器；此外，即使當數據流很慢時，也可能存在多個這樣的數據流，即每個流本身能夠基于很小的內存就能處理，但所有數據流的內存需求加在一起可能就很容易超過內存的可用容量。所以，當內存足夠大時，流數據的很多問題很容易解決，而實際情況，在一個真實規模的機器上獲得現實的處理速度，問題變得相當困難，需要采用新技術解決：1）通常情況下，獲得問題的近似解比精確解要高效得多；2）為了產生與精確解相當接近的近似解，需采用哈希相關技術。

2 流當中的數據抽樣

從流中選擇一個子集，以便能夠對它進行查詢并給出統計上對整個流具有代表性的結果；流由一系列n 字段元組構成，這些字段的一個子集稱為關鍵詞段，樣本的選擇基于它來進行，比如，一個流由三元組（user，query，time）組成，其中user 可以作為關鍵詞段。若關鍵詞段包含的字段不止一個，那么哈希函數就要將這些字段的值組合起來形成單一的哈希值。最后得到樣本由有某些特定鍵值的所有元組構成。為了保證樣本由鍵值子集所對應的所有元組組成，可以選擇一個哈希函數h，將鍵值映射到一個很大的取值范圍0，1，…，B-1。另外，維護一個閥值t，它的初始值可以設置成最大的桶編號B-1。任何時候，樣本都由鍵值K 滿足h（K）＜=t 的元組構成。當且僅當滿足同樣條件的情況下，流中的新元組才會加入到樣本中。如果樣本中存儲的元組數目超過分配的空間大小，那么就將閥值降低為t-1，并將那些鍵值K 滿足h（K）=t 的元組去掉。為提高效率，還可以將閥值降低更多。無論何時需要將某些鍵值從樣本中丟棄時，都可以將幾個具有最高哈希值的元組去掉。

3 流過濾

只想接受流中滿足某個準則的元組集合。如果選擇的準則基于元組的某個可計算屬性得到，那么選擇操作很容易完成，當選擇準則中包含集合元素的查找時，特別當集合大到無法在內存中存放時，問題就變得尤其困難；對此要去掉不滿足選擇準則的大部分元組，可以采用布隆過濾器：布隆過濾器的目的是讓所有鍵值在S 中的流元素通過，而阻擋大部分鍵值不在S 中的流元素。一個布隆過濾器由如下幾部分組成：

（1）n 個位組成的數組，每個位的初始值都為0；

（2）一系列哈希函數 h1,h2,…hk組成的集合。每個哈希函數將“鍵”值映射到上述的n 個桶（對應于位數組中n個位）中；

（3）m 個鍵值組成的集合S。

位數組的所有位的初始值為0。對S 中的每個鍵值K，利用每個哈希函數進行處理。對于一些哈希函數 ih 及S 中的鍵值K，將每個 hi(K)對應的位置為1。

當鍵值為K 的流元素到達時，檢查所有的h1(K ),h2(K),… hk(K)對應的位是否全部為1，如果是，則允許該流元素通過，若有一位或多位為0，則認為K 不可能在S 中，于是拒絕該流元素通過。另外可以將多個過濾器串聯起來使用來進一步過濾。

4 流中元素的數目統計

假定流元素選自某個全集，想知道流當中從開始或某個已知的過去時刻開始所出現的不同元素數目。如百度網站，它不需要登錄就可以提交搜索查詢，可能只能通過用戶提交查詢時的URL 來識別用戶。這里所有可能的URL全集可以想象成所有登錄主機名的全集。這需要在內存中保存當前已有的所有流元素，但是如果不同的元素數目太多，或需要即刻處理多個流，那么就無法在內存中存儲所需數據。處理策略是僅僅對獨立元素數目進行估計，具體思想是：通過將全集中的元素哈希到一個足夠長的位串，就可以對獨立元素個數進行估計。位串必須要足夠長，以致哈希函數的可能結果數目要大于全集中的元素個數。流中的不同元素越多，那么不同哈希值也越多，在眾多不同哈希值中，其中有一個值變得異常，該值后面會以多個0結束。任何時候在流元素a 上應用哈希函數h 時，位串h（a）的尾部將以一些0 結束，當然也可能沒有0，尾部0 的數目稱為a 和h 的尾長。假設流當中目前所有已有元素a 的最大尾長為R。那么將使用2R 來估計到目前為止流中所看到的獨立元素數目。

上述估計方法有直觀上意義：給定流元素a 的哈希值h（a）末尾至少有r 個0 的概率為2-r 。假定流中有m個獨立元素，那么任何元素的哈希值末尾都不滿足至少有r 個0 的概率為(1-2-r)m，該表達式可以改為((1-2-r)2r)m2-r。當r 相當大時，上式表達式就是(1-ε)1/ε，其大小約等于1/e。因此任何元素的哈希值末尾都不滿足至少有r 個0 的概率為 e-m2-r。于是可以得到如下結論：（1）如果m 遠大于2r，那么發現一個尾部長度至少為r 的概率接近1；（2）如果m 遠小于2r，那么發現一個尾部長度至少為r 的概率接近0；基于以上兩點結論，m 的估計值2R（R 是所有流元素中的最大尾長）不可能過高或過低。

5 總結

對任一到達流元素的鍵值進行哈希處理，使用哈希值來確定包含該鍵值的全部元素會是抽樣樣本的一部分。采用布隆過濾器允許屬于某個特定集合的流元素通過，而大部分其他元素被丟棄。為了估計流中出現的不同元素的數目，可以將元素哈希成整數，這些整數可以解釋為二進制整數，任意流元素的哈希值中最長的0 序列長度作為2 的冪得到的結果會作為獨立元素數目的估計值。