唐 達(dá)， 劉 暢， 岳 前 進(jìn)， 張 建 英

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

0 引 言

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

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ù)集中抽取小部分?jǐn)?shù)據(jù)樣本，并根據(jù)樣本近似恢復(fù)數(shù)據(jù)集，相對(duì)復(fù)雜，兩種構(gòu)建技術(shù)構(gòu)建的概要數(shù)據(jù)均不能滿(mǎn)足流數(shù)據(jù)快速、連續(xù)查詢(xún)的要求.抽樣技術(shù)生成概要數(shù)據(jù)的效率高，能滿(mǎn)足流數(shù)據(jù)快速、連續(xù)查詢(xún)的要求，可以很好地應(yīng)用到深海平臺(tái)監(jiān)測(cè)系統(tǒng)上.現(xiàn)有抽樣算法主要有均勻抽樣（uniform sampling）、偏倚抽樣（biased sampling）和權(quán)值抽樣.

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

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

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

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

2 AWRS/BTSW 算法

2.1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

由式（1）可得

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

2.3 AWRS/BTSW 算法步驟

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

輸入：包含n個(gè)數(shù)據(jù)項(xiàng)的流數(shù)據(jù)S

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

（1）將新到達(dá)的時(shí)間跨度為T(mén)的h個(gè)數(shù)據(jù)項(xiàng)加入到當(dāng)前時(shí)間滑動(dòng)窗口；

2.3 AWRS/BTSW 算法步驟

當(dāng)Δt時(shí)間段的數(shù)據(jù)到達(dá)時(shí)，首先計(jì)算該時(shí)間

（2）將當(dāng)前時(shí)間滑動(dòng)窗口T按照Δt的時(shí)間間隔，平均切分為k個(gè)子窗口（s[0]，s[1]，…，s[k－1]），k＝T/Δt；

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

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

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

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

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

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

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

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

（12）ifxi＞MIN－ε

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

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

3 算法分析與比較

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

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

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

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

圖1 AWRS/BTSW算法所用時(shí)間Fig.1 AWRS/BTSW algorithm efficiency

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

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

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

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

4 結(jié) 論

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

[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.