徐雪松

（南京中醫(yī)藥大學(xué) 信息技術(shù)學(xué)院，江蘇 南京 210046）

隨著數(shù)據(jù)采集和處理技術(shù)的進(jìn)步，人們對(duì)數(shù)據(jù)的不確定性認(rèn)識(shí)也逐步深入，許多應(yīng)用領(lǐng)域產(chǎn)生的不確定數(shù)據(jù)屬于不確定數(shù)據(jù)流 （uncertain data stream）類型。傳統(tǒng)異常數(shù)據(jù)檢測(cè)算法[1-3]不適合不確定數(shù)據(jù)流中異常數(shù)據(jù)的檢測(cè)。這些算法只考慮和數(shù)據(jù)流中確定性成分相結(jié)合，并提高異常數(shù)據(jù)的檢測(cè)精度，但忽略了不確定數(shù)據(jù)流高速、無限和動(dòng)態(tài)不確定的特性，使得傳統(tǒng)方法無法檢測(cè)異常數(shù)據(jù)或需要改進(jìn)。文中提出一種基于時(shí)間序列不確定數(shù)據(jù)流的異常數(shù)據(jù)檢測(cè)方法，該方法充分考慮了數(shù)據(jù)流的不確定性，同時(shí)在計(jì)算資源受限情況下自適應(yīng)地平衡檢測(cè)計(jì)算代價(jià)與檢測(cè)精度。

1 不確定數(shù)據(jù)流的異常數(shù)據(jù)檢測(cè)模型

1.1 不確定數(shù)據(jù)流的小波分析

文中主要研究時(shí)間序列離散類型數(shù)據(jù)流，其包含的不確定離散元組以數(shù)據(jù)點(diǎn)概率模型描述。在該模型中，元組的屬性值確定，而存在性不確定，用一個(gè)[0，1]之間的概率值表示[4]。由于不確定數(shù)據(jù)流具有非線性及強(qiáng)繞動(dòng)性，文中采用小波變換來滿足自適應(yīng)時(shí)變信號(hào)分析的要求，從而可聚焦到信號(hào)的任意細(xì)節(jié)以識(shí)別不確定數(shù)據(jù)流中異常數(shù)據(jù)。

定義1.1時(shí)間序列不確定數(shù)據(jù)流是一個(gè)由相互獨(dú)立的k維不確定元組構(gòu)成的序列，S （t）={（w1（t），p1），（w2（t），p2），……，（wn（t），pn）}，其中 wi（t）為 t時(shí)刻第 i個(gè)元組的值，pi為該元組的存在概率且0≤pi≤1。

其中，a∈R且a≠0；a為尺度因子，表示與頻率相關(guān)的伸縮，b 為時(shí)間平移因子，當(dāng)時(shí) a=am0，b=nb0a0-m，式（1）為 S（t）的離散小波變換。

設(shè)SN（N為分解尺度）表示小波分解中低頻信息sN，EN表示小波分解中高頻信息 ej（j=1，2，…，N），由于 SN⊕EN=SN-1，即高頻信息是低頻信息中的正交補(bǔ)，顯然多分辨分析的子空間S0可表示為：

令 sN∈SN表示分辨率為 2N的時(shí)間函數(shù) S（t）∈L2（R）的無限逼近，ej∈Ej表示逼近的誤差，則式（2）可表示為：

由 s（t）=s0，式（3）表明任何時(shí)間序列 S（t）∈L2（R）都可根據(jù)相應(yīng)的低頻信息和高頻信息完全重構(gòu)。

1.2 異常數(shù)據(jù)檢測(cè)模型

小波變換后將包含異常數(shù)據(jù)的不確定數(shù)據(jù)流分別分解成包含異常數(shù)據(jù)的高頻信息和低頻信息，可采用如下方法識(shí)別異常數(shù)據(jù)。

目前對(duì)于確定數(shù)據(jù)流異常數(shù)據(jù)在定長(zhǎng)時(shí)間窗口中的判別可基于歐幾里得或者曼哈頓距離度量來決定聚類。基于這樣的距離度量的算法對(duì)于元組的不確定性十分敏感，這種不確定性通常由概率來表示，參數(shù)通常很難確定，特別是對(duì)于包含高維對(duì)象的數(shù)據(jù)流來說，這樣不僅加重了用戶的負(fù)擔(dān)，也使得聚類的質(zhì)量難以控制。因此，有必要重新定義簇的中心點(diǎn)與半徑，使之適應(yīng)不確定數(shù)據(jù)模型。

對(duì)于不確定數(shù)據(jù)流的元組，其在定長(zhǎng)時(shí)間窗口中簇的概率中心Cp定義為簇內(nèi)元組的概率加權(quán)線性均值，Cp=UP1/Ps。

針對(duì)定長(zhǎng)時(shí)間窗口內(nèi)時(shí)間序列不確定數(shù)據(jù)流，重新定義聚類算法，該定義不但考慮各元組到中心的距離，同時(shí)考慮定長(zhǎng)時(shí)間窗口內(nèi)元組的平均存在概率對(duì)半徑值的影響，半徑如（4）式所示：

2 算法描述及實(shí)驗(yàn)分析

時(shí)間序列不確定數(shù)據(jù)流中異常數(shù)據(jù)檢測(cè)算法簡(jiǎn)述如下：

輸入：由時(shí)間函數(shù)S（t）表示的不確定數(shù)據(jù)流。

輸出：剔除不確定異常數(shù)據(jù)。具體步驟如下：

1）對(duì)S（t）進(jìn)行小波分解，選定尺度函數(shù)、小波函數(shù)及其對(duì)應(yīng)的分解系數(shù)序列{an}、{bn}和重構(gòu)系數(shù)序列{pn}、{qn}，確定分解尺度N和給出作為判斷分解重構(gòu)達(dá)到要求的常數(shù)δ。

2）利用小波分解得到N+1組低頻、高頻信息，分別單獨(dú)用Mallat塔式算法重構(gòu)到原尺度上，得到N+1組重構(gòu)后的時(shí)間序列信號(hào)。

3）DO

4）從權(quán)值給定的時(shí)間序列不確定數(shù)據(jù)流中采樣wi（t）//生成樣本

5）Cp=UP1/ps//生成簇的概率中心

6）利用4）式計(jì)算聚類簇半徑

7）if（元組的概率值高于簇的平均概率值，且該元組至中心點(diǎn)距離近）

8）接收該元組為不確定元組

9）else if（元組概率高于簇的平均概率值，且該元組至中心點(diǎn)遠(yuǎn)）

10）接收該元組為不確定元組

11）else if（元組概率低于簇的平均概率值，且該元組至中心點(diǎn)近）

12）接收該元組為不確定元組

13）else if（元組概率低于簇的平均概率值，且該元組至中心點(diǎn)遠(yuǎn)）

14）確認(rèn)該元組為不確定異常數(shù)據(jù)，應(yīng)剔除

15）end if

17）if（q（u）/ps≤λ0）

18）該微簇的不確定元組已經(jīng)陳舊，從內(nèi)存剔除

19）else接收該微簇

20）end while

以某市中心某路口一個(gè)方向的交通流量為例，每個(gè)信號(hào)周期記錄一次（流量單位：輛/周期），2010年8月20日，該路口方向的交通流量曲線如圖1所示，該時(shí)間序列共測(cè)得726個(gè)實(shí)測(cè)數(shù)據(jù)，文中根據(jù)該流量序列，分別運(yùn)用文中算法和傳統(tǒng)的聚類算法對(duì)該實(shí)測(cè)數(shù)據(jù)集進(jìn)行異常數(shù)據(jù)的識(shí)別。

文中利用MATLAB小波工具箱的DB4小波函數(shù)依據(jù)小波分辨分析的原則選定尺度和小波函數(shù)，分別得到分解系數(shù)序列{an}、{bn}和重構(gòu)系數(shù)序列{pn}、{qn}，為了保證檢測(cè)精度，確定分解尺度為2。

在該交通流量數(shù)據(jù)集中共有45個(gè)異常數(shù)據(jù)，直接采用傳統(tǒng)聚類算法檢測(cè)，共檢測(cè)出了98個(gè)異常數(shù)據(jù)，其中誤檢了86個(gè)，漏檢了33個(gè)；采用小波分析的不確定聚類算法進(jìn)行異常檢測(cè)，共檢測(cè)到了47個(gè)異常數(shù)據(jù)，其中誤檢了3個(gè)，漏檢了1個(gè)。表1為這兩種算法的檢測(cè)結(jié)果對(duì)比。

圖1 交通流量數(shù)據(jù)Fig.1 Traffic flow data

表1 兩種算法對(duì)異常數(shù)據(jù)檢測(cè)結(jié)果對(duì)比Tab.1 Comparison of the detected results of abnormal data between two algorithms

3 結(jié)束語

筆者深入分析時(shí)間序列不確定數(shù)據(jù)流的特點(diǎn)，針對(duì)傳統(tǒng)數(shù)據(jù)流異常數(shù)據(jù)檢測(cè)方法存在的問題，提出一種時(shí)間序列不確定數(shù)據(jù)流異常數(shù)據(jù)檢測(cè)方法。該方法針對(duì)不確定數(shù)據(jù)流的高速、無限和動(dòng)態(tài)不確定特性，結(jié)合小波分析和改進(jìn)的聚類方法來識(shí)別異常數(shù)據(jù)。同時(shí)在計(jì)算資源受限情況下，能有效平衡計(jì)算代價(jià)與檢測(cè)精度問題。實(shí)驗(yàn)表明該方法能夠較好地滿足高速交通流量的不確定數(shù)據(jù)流異常數(shù)據(jù)檢測(cè)的需求。

[1]周春光，邢輝，徐振龍，等.商業(yè)數(shù)據(jù)的預(yù)測(cè)模型及其算法研究[J].吉林大學(xué)學(xué)報(bào)，2002 ，20（3）:53-60.

ZHOU Chun-guang， XING Hui， XU Zhen-long， et al.Research of prediction models and arithmetic in commerce[J].Journal of Jilin University， 2002， 20（3）:53-60.

[2]JAIN A， CHANG E Y，WANG Yuan-Fang.Adaptive stream resource management using Kalman filters[C]//Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data.Paris， France， USA:ACM Press，2004：11-22.

[3]FALOUTSOS C.Stream and sensor data mining.[C]//Proceedings of the 9th International Conference on Extending Database Technology.Heraklion， Greece， Berlin:Springer-Verlag， LNCS， 2004：25-27.

[4]CORMODE G，McGregor A.Approximation algorithms for clustering uncertain data[J].In ACM Principles of Database Systems （PODS）， 2008：191-200.

[5]彭玉華.小波變換與工程應(yīng)用 [M].北京：科學(xué)出版社，2005.

[6]馮象初，甘小冰，宋國(guó)鄉(xiāng).數(shù)值泛函與小波理論[M].西安：西安電子科技大學(xué)出版社，2003.

[7]王勝坤.JPEG 2000中小波變換的FPGA實(shí)現(xiàn)[D].山西：太原理工大學(xué)，2007.