徐雪松

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法描述及實驗分析

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

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

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

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

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

3）DO

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

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

6）利用4）式計算聚類簇半徑

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

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

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

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

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

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

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

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

15）end if

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

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

19）else接收該微簇

20）end while

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

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

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

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

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

3 結(jié)束語

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

[1]周春光，邢輝，徐振龍，等.商業(yè)數(shù)據(jù)的預(yù)測模型及其算法研究[J].吉林大學(xué)學(xué)報，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]馮象初，甘小冰，宋國鄉(xiāng).數(shù)值泛函與小波理論[M].西安：西安電子科技大學(xué)出版社，2003.

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