基于時間滑動窗口的自適應(yīng)加權(quán)隨機抽樣算法

唐 達， 劉 暢， 岳 前 進， 張 建 英

（1.大連理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024；2.大連理工大學(xué) 工程力學(xué)系，遼寧 大連 116024）

0 引 言

深海平臺監(jiān)測系統(tǒng)通過分析傳感器網(wǎng)絡(luò)上采集到的數(shù)據(jù)，來確定不同的因素對該平臺的影響.從傳感器上采集到的數(shù)據(jù)是隨時間不斷變化的，具有連續(xù)、無界兩個特點，即為流數(shù)據(jù)[1].深海平臺監(jiān)測系統(tǒng)需要管理這類流數(shù)據(jù)，以便用戶查詢.對流數(shù)據(jù)的查詢通常是連續(xù)的，當新數(shù)據(jù)到達時增量式地返回結(jié)果.在深海平臺監(jiān)測系統(tǒng)中，用戶查詢僅僅需要一個近似結(jié)果，并不需要獲得精確的查詢值，由于存儲容量的有限性，將所有流數(shù)據(jù)都保存起來不現(xiàn)實，也沒有必要.為實現(xiàn)對流數(shù)據(jù)的存儲，需要設(shè)計一個保存原始流數(shù)據(jù)的特征，規(guī)模上遠小于原流數(shù)據(jù)的概要數(shù)據(jù)結(jié)構(gòu)（synopsis data structure）[2].本文對此進行研究.

1 概要數(shù)據(jù)構(gòu)建技術(shù)

概要數(shù)據(jù)構(gòu)建技術(shù)主要有直方圖（histogram）技術(shù)[3]、小波（wavelet）技術(shù)[4]和抽樣（sampling）技術(shù).直方圖技術(shù)只能反映數(shù)據(jù)的大致輪廓和分布特征，小波技術(shù)是從數(shù)據(jù)集中抽取小部分數(shù)據(jù)樣本，并根據(jù)樣本近似恢復(fù)數(shù)據(jù)集，相對復(fù)雜，兩種構(gòu)建技術(shù)構(gòu)建的概要數(shù)據(jù)均不能滿足流數(shù)據(jù)快速、連續(xù)查詢的要求.抽樣技術(shù)生成概要數(shù)據(jù)的效率高，能滿足流數(shù)據(jù)快速、連續(xù)查詢的要求，可以很好地應(yīng)用到深海平臺監(jiān)測系統(tǒng)上.現(xiàn)有抽樣算法主要有均勻抽樣（uniform sampling）、偏倚抽樣（biased sampling）和權(quán)值抽樣.

均勻抽樣：各元組被抽取到的概率是相等的.Vitter[5]提出水庫抽樣方法，假定數(shù)據(jù)集的總量為A，以S/A的概率抽取S個元組到樣本集合中，當抽取的元組數(shù)量超過S時，隨機刪除樣本集合里的一個元組，然后將抽取出來的新元組插入到樣本集合中.Gibbons等[6]優(yōu)化了水庫抽樣方法，給出了精確抽樣方法，將數(shù)據(jù)元組用（T，C）表示，其中T表示數(shù)據(jù)元組，C表示數(shù)據(jù)元組的個數(shù)，在相同數(shù)據(jù)元組多的數(shù)據(jù)集合中使用該方法，能有效地節(jié)省空間.

偏倚抽樣：各元組被抽取到的概率是不同的.Gibbons等[6]在精確抽樣方法的基礎(chǔ)上給出了計數(shù)抽樣方法，在抽取的元組數(shù)量超過S時，將出現(xiàn)次數(shù)少的元素從樣品集合中替換掉，可以很方便地獲得一個集合中的常用數(shù)據(jù)元組.

權(quán)值抽樣：各元組根據(jù)一定的權(quán)值進行抽樣.Efraimidis等[7]認為均勻抽樣沒有區(qū)分數(shù)據(jù)元組的重要性.其給出了加權(quán)抽樣算法，賦予數(shù)據(jù)元組相應(yīng)的權(quán)值，并根據(jù)權(quán)值進行抽樣.Zhang等[8]認為抽樣要考慮數(shù)據(jù)的時間因素，其在加權(quán)抽樣算法的基礎(chǔ)上，綜合計算數(shù)據(jù)元組的到達時間和權(quán)值，作為該數(shù)據(jù)元組的優(yōu)先數(shù)，再根據(jù)優(yōu)先數(shù)抽樣，形成優(yōu)先數(shù)隨機抽樣算法（PRS），解決了數(shù)據(jù)元組過期問題.Hou等[9]為解決多個流數(shù)據(jù)之間的多次連接操作效率低下的問題，提出一種針對多個相關(guān)流數(shù)據(jù)的概要數(shù)據(jù)生成算法.

上述抽樣算法均未能考慮到流數(shù)據(jù)變化的特點，但加權(quán)抽樣算法能根據(jù)用戶賦予數(shù)據(jù)的權(quán)值，來衡量數(shù)據(jù)的重要性，并根據(jù)重要性進行抽樣.在深海平臺監(jiān)測系統(tǒng)中，用戶事先并不知道何時到達的數(shù)據(jù)重要，只能根據(jù)經(jīng)驗，因此，抽取的概要數(shù)據(jù)的準確性依賴于用戶的經(jīng)驗.為此本文給出一種基于時間滑動窗口的自適應(yīng)加權(quán)隨機抽樣算法：AWRS/BTSW （adaptive weighted random sampling based on time sliding window）算法，該算法通過計算流數(shù)據(jù)的平均變化率，來確定一個數(shù)據(jù)元組的權(quán)值以及skipping因子的值，結(jié)合skipping因子、權(quán)值和數(shù)據(jù)元組的到達時間來對數(shù)據(jù)進行抽樣，解決了現(xiàn)有抽樣算法生成的概要數(shù)據(jù)與原始數(shù)據(jù)的誤差不確定以及數(shù)據(jù)過期問題.

2 AWRS/BTSW 算法

2.1 相關(guān)定義

定義1 數(shù)據(jù)平均變化率 假設(shè)在時刻i的數(shù)據(jù)為ti，則時刻i的數(shù)據(jù)變化率Δi為，則從時刻m到n之間的時間段Δt的數(shù)據(jù)平均變化率為

定義2 skipping因子 若時間段Δt內(nèi)的數(shù)據(jù)平均變化率小于閾值ξ，該時間段的所有數(shù)據(jù)元組的skipping因子的值為true，否則為false.skipping（Δt）函數(shù)定義如下：

定義3 數(shù)據(jù)集的穩(wěn)定度 將數(shù)據(jù)集分成若干個數(shù)據(jù)區(qū)間，ds表示數(shù)據(jù)平均變化率不超過閾值的數(shù)據(jù)區(qū)間的個數(shù)，da表示總數(shù)據(jù)區(qū)間的個數(shù)，則該數(shù)據(jù)集的穩(wěn)定度為s＝ds/da.

定義4 相對誤差 從原始數(shù)據(jù)里查詢的結(jié)果定義為Qr，從概要數(shù)據(jù)里查詢的結(jié)果定義為Qs，則相對誤差為e＝Qs/Qr.

2.2 數(shù)據(jù)項的鍵值

從流數(shù)據(jù)變化特點出發(fā)，根據(jù)流數(shù)據(jù)的平均變化率賦予數(shù)據(jù)項相應(yīng)的權(quán)值，令w（x）為單調(diào)遞增函數(shù)，w（x）函數(shù)取x1/λ（λ為正整數(shù)），數(shù)據(jù)變化越快，賦予的權(quán)值就越大.權(quán)值計算公式如下：

結(jié)合基本窗口技術(shù)，綜合考慮權(quán)值和時間因素并將其作為數(shù)據(jù)項的鍵值，解決時間滑動窗口的數(shù)據(jù)過期問題.鍵值計算公式如下：

其中α和β是權(quán)衡數(shù)據(jù)到達時間和權(quán)值的兩個參數(shù).用vi表示數(shù)據(jù)流中的第i個數(shù)據(jù)項，xi表示數(shù)據(jù)項vi的鍵值，ti表示數(shù)據(jù)項vi的到達時間，wi表示數(shù)據(jù)項vi的權(quán)值，μi表示數(shù)據(jù)項vi生成的一個隨機數(shù).g（x）為單調(diào)遞增函數(shù)，數(shù)據(jù)到達時間越早，它的值就越小.對于變量x，y，f（x，y）是一個單調(diào)遞增函數(shù)，例如xy.

當新數(shù)據(jù)到達時，時間窗口向后移，周期性地計算當前滑動窗口的數(shù)據(jù)項的鍵值，可以將滑動窗口平均分為k個子窗口（s[0]，s[1]，…，s[k－1]）.假設(shè)vi在子窗口s[m]，則當前滑動窗口的各個數(shù)據(jù)項Δt的鍵值xi計算如下：

假定l是一個正整數(shù)，g（x）取x－1/l，f（x，y）取y1/x，代入式（3）可得

由式（1）可得

新到來的Δt時間段的數(shù)據(jù)，將其放入s[k]中，將m＝k代入式（5）計算可得

2.3 AWRS/BTSW 算法步驟

當Δt時間段的數(shù)據(jù)到達時，首先計算該時間段的數(shù)據(jù)平均變化率Δi，然后根據(jù)數(shù)據(jù)平均變化率計算其skipping因子.如果skipping因子的值為真，則滑過這些元組；否則，根據(jù)數(shù)據(jù)平均變化率給這段數(shù)據(jù)項賦予一定的權(quán)值，并結(jié)合到達時間計算這段數(shù)據(jù)項的鍵值；最后再根據(jù)鍵值進行抽樣.具體算法如下：

輸入：包含n個數(shù)據(jù)項的流數(shù)據(jù)S

輸出：基于時間的滑動窗口T的概要數(shù)據(jù)集R

（1）將新到達的時間跨度為T的h個數(shù)據(jù)項加入到當前時間滑動窗口；

2.3 AWRS/BTSW 算法步驟

當Δt時間段的數(shù)據(jù)到達時，首先計算該時間

（2）將當前時間滑動窗口T按照Δt的時間間隔，平均切分為k個子窗口（s[0]，s[1]，…，s[k－1]），k＝T/Δt；

（4）計算各個數(shù)據(jù)項的鍵值xi；

（5）for（i＝h＋1；i＜＝n；＋＋i），重復(fù)步驟（5）～ （13）；

（6）計算下一個Δt時間間隔的數(shù)據(jù)平均變化率

（7）if skipping（Δt）＝＝true，跳躍Δt個時間跨度段，轉(zhuǎn)步驟（5）；

（8）將Δt時間跨度的數(shù)據(jù)項讀取到s[k]；

（9）計算Δt時間跨度里的各個數(shù)據(jù)項的鍵值xi；

（10）for（j＝1；j＜＝ Δt；＋＋j），重復(fù)步驟（10）～ （12）；

（11）查找當前滑動窗口中鍵值最小的數(shù)據(jù)項，假設(shè)最小鍵值為MIN，并且有R[m]＝MIN；

（12）ifxi＞MIN－ε

用鍵值為xi的數(shù)據(jù)項替換R[m]；

（13）窗口向前滑動，s[i]→s[i－1]（i＝1，2，…，k）.

3 算法分析與比較

AWRS/BTSW算法首先計算平均數(shù)據(jù)變化率，時間復(fù)雜度為o（n），將流數(shù)據(jù)中的數(shù)據(jù)元組抽取到樣本集，時間復(fù)雜度為o（hlogn/h＋Δt（h－1）），算法在數(shù)據(jù)穩(wěn)定的情況下滑過Δt個時間跨度，假設(shè)流數(shù)據(jù)中的數(shù)據(jù)項的穩(wěn)定度為s，則該算法總時間復(fù)雜度為o（n＋（n－h(huán)）（1－s）（（hlogn/h）/Δt＋（h－1））），其中s∈ [0，1]，Δt∈ [2，h].

從算法的時間復(fù)雜度計算公式可以得出，該算法依賴數(shù)據(jù)集的穩(wěn)定度s和時間跨度Δt.從深海平臺監(jiān)測系統(tǒng)取出3萬個數(shù)據(jù)，用該算法生成5 000個概要數(shù)據(jù).其中測試環(huán)境為操作系統(tǒng)Windows XP、CPU 2.6GHz Pentium 4、1GB內(nèi)存.

對穩(wěn)定度相同（假設(shè)數(shù)據(jù)集的穩(wěn)定度為25%），時間跨度 Δt不同（分別為5 000、3 000、1 000、900、800、100、2s）的數(shù)據(jù)集進行實驗，生成概要數(shù)據(jù)所用時間如圖1所示.

在時間跨度Δt相同（時間跨度Δt設(shè)置為5 s），穩(wěn)定度不同（分別為0、10%、25%、50%、75%）的數(shù)據(jù)集中，將AWRS/BTSW算法和優(yōu)先數(shù)隨機抽樣（PRS）算法生成概要數(shù)據(jù)所用的時間和準確性進行對比，其中PRS算法中的數(shù)據(jù)項的權(quán)值用隨機函數(shù)生成，分別運行兩種算法并求其算術(shù)平均值.兩種算法生成概要數(shù)據(jù)所用時間和相對誤差如圖2、3所示.

圖1 AWRS/BTSW算法所用時間Fig.1 AWRS/BTSW algorithm efficiency

圖2 算法所用時間的比較Fig.2 Comparison of algorithm efficiencies

圖3 算法相對誤差的比較Fig.3 Comparison of accuracy of algorithm

從圖1、2可以看出，穩(wěn)定度相同，AWRS/BTSW算法所用時間在2～100s時隨時間跨度Δt的增大而減小，在800～5 000s時隨時間跨度Δt的增大而增大.當時間跨度Δt相同時，數(shù)據(jù)集的穩(wěn)定度越高，該算法生成概要數(shù)據(jù)的效率越高.

從圖2、3可以看出，數(shù)據(jù)集的穩(wěn)定度越高，AWRS/BTSW算法生成概要數(shù)據(jù)的效率越高；數(shù)據(jù)集的穩(wěn)定度越低，與PRS算法相比該算法的準確性越高.當數(shù)據(jù)集的穩(wěn)定度在10%以上時，該算法的效率和準確性都比PRS算法高；當數(shù)據(jù)集的穩(wěn)定度在10%以下時，該算法的準確性比PRS算法高，效率略低.

4 結(jié) 論

本文總結(jié)和分析了概要數(shù)據(jù)構(gòu)建的幾種抽樣方法，給出了一種基于時間滑動窗口的自適應(yīng)加權(quán)隨機抽樣算法：AWRS/BTSW算法，解決了目前抽樣算法在深海平臺檢測系統(tǒng)等數(shù)據(jù)變化不確定的應(yīng)用中，抽取出的概要數(shù)據(jù)的準確性與原始數(shù)據(jù)之間的誤差不確定的問題.與其他的抽樣算法相比，該算法能根據(jù)數(shù)據(jù)變化的情況，動態(tài)生成概要數(shù)據(jù)，在數(shù)據(jù)變化穩(wěn)定的情況下生成概要數(shù)據(jù)的效率高，在數(shù)據(jù)變化劇烈的情況下生成概要數(shù)據(jù)的準確性高，相對誤差較小.

[1] Babcock B，Babu S，Datar M，etal.Models and issues in data streams [C]//Proceedings of the Twenty－First ACM SIGACT－SIGMOD－SIGART Symposium on Principles of Database Systems.New York：ACM，2002：1－16.

[2] Gibbons P B，Matias Y.Synopsis data structures for massive data sets[C]//Proceedings of the Annual ACM－SIAM Symposium on Discrete Algorithms.Philadelphia：SIAM，1999.

[3] Gibbons P B，Matias Y，Poosala V.Fast incremental maintenance of approximate histograms [J].ACM Transactions on Database Systems，2002，27（3）：261－298.

[4] Matias Y，Vitter J S， Wang M. Wavelet－based histograms for selectivity estimation [J].ACM SIGMOD Record，1998，27（2）：448－459.

[5] Vitter J S.Random sampling with a reservoir[J].ACM Transactions on Mathematical Software，1985，11（1）：37－57.

[6] Gibbons P B， Matias Y. New sampling－based summary statistics for improving approximate query answers [C]// Proceedings of the 1998ACM SIGMOD International Conference on Management of Data.New York：ACM，1998：331－342.

[7] Efraimidis P S，Spirakis P G.Weighted random sampling with a reservoir[J].Information Processing Letters，2006，97（5）：181－185.

[8] ZHANG Long－bo，LI Zhang－h(huán)uai，ZHAO Yi－qiang，etal.A priority random sampling algorithm for timebased sliding windows over weighted streaming data[C]//Proceedings of the 2007ACM Symposium on Applied Computing.New York：ACM，2007：453－456.

[9] HOU Wei，YANG Bing－ru，WU Chen－shen，etal.RedTrees：A relational decision tree algorithm in streams[J].Expert Systems with Applications，2010，37（9）：6265－6269.