大數(shù)據(jù)背景下的數(shù)據(jù)流挖掘技術(shù)

朱彥杰

許昌學(xué)院

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

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

1 流數(shù)據(jù)

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

2 流當(dāng)中的數(shù)據(jù)抽樣

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

3 流過濾

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

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

（2）一系列哈希函數(shù) h1,h2,…h(huán)k組成的集合。每個哈希函數(shù)將“鍵”值映射到上述的n 個桶（對應(yīng)于位數(shù)組中n個位）中；

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

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

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

4 流中元素的數(shù)目統(tǒng)計

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

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

5 總結(jié)

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