歐陽(yáng)如琳,任立良,周成虎

(1.河海大學(xué)水文水資源與水利工程科學(xué)國(guó)家重點(diǎn)實(shí)驗(yàn)室,江蘇南京 210098;2.中國(guó)科學(xué)院地理科學(xué)與資源研究所資源與環(huán)境信息系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京 100101)

自20世紀(jì)90年代以來(lái),隨著數(shù)據(jù)庫(kù)技術(shù)的成熟和數(shù)據(jù)應(yīng)用的普及,人類積累的數(shù)據(jù)量正在以指數(shù)速度迅速增長(zhǎng).面對(duì)浩瀚無(wú)垠的數(shù)據(jù),人們迫切需要新的技術(shù)和自動(dòng)化工具將海量數(shù)據(jù)轉(zhuǎn)化為有用的信息和知識(shí).數(shù)據(jù)挖掘(data mining,DM)技術(shù)在這樣的背景下應(yīng)運(yùn)而生,并越來(lái)越顯示出其強(qiáng)大的生命力.所謂數(shù)據(jù)挖掘,就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中,提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和知識(shí)的過(guò)程[1].以時(shí)間序列為挖掘?qū)ο蟮臄?shù)據(jù)挖掘,稱之為時(shí)間序列數(shù)據(jù)挖掘(time series data mining,TSDM).由于時(shí)間序列數(shù)據(jù)的廣泛存在性,使得時(shí)間序列數(shù)據(jù)挖掘成為學(xué)術(shù)界的研究熱點(diǎn)之一,取得了顯著的研究成果[2-12],其中,時(shí)間序列相似性搜索是時(shí)間序列數(shù)據(jù)挖掘中研究最為廣泛也是發(fā)展最為成熟的.

水文過(guò)程受確定性因素和不確定性因素的共同作用,確定性因素的作用使得水文過(guò)程表現(xiàn)出年、季節(jié)甚至日等周期性變化.如日、旬、月流量過(guò)程明顯存在以年為周期的變化.這是由于影響水文過(guò)程的主要因素——?dú)夂蛞蛩卮嬖谝阅隇橹芷诘募竟?jié)性變化,這種水文過(guò)程中年際間的周期性可視為水文過(guò)程年際間的相似性.同樣,由于受一次降水量的過(guò)程影響,一場(chǎng)洪水過(guò)程都是由起漲到達(dá)頂峰最后消退的過(guò)程,年內(nèi)汛期洪水總趨勢(shì)與場(chǎng)次洪水過(guò)程間具有相似性.這是由于西風(fēng)帶、季風(fēng)活動(dòng)、副熱帶高壓等天氣系統(tǒng)的季節(jié)性活動(dòng)的相似性,形成的暴雨以及相應(yīng)的洪峰流量及其洪水過(guò)程在年內(nèi)季節(jié)間具有相似性[13-14].水文過(guò)程的形成和演變還受到許多隨機(jī)因素的影響,比如流域內(nèi)的地形、地勢(shì)、土壤、植被以及降水的時(shí)空分布等,使得水文過(guò)程年際間的相似性和場(chǎng)次洪水的相似性只能是某種程度上的相似,而并非完全相同.傳統(tǒng)水文過(guò)程的相似性研究強(qiáng)調(diào)精確匹配,實(shí)際的水文過(guò)程本身很難達(dá)到如此要求,而數(shù)據(jù)挖掘中,一般采用基于近似匹配的“近似”相似性搜索[15],符合水文數(shù)據(jù)的特點(diǎn).本文將數(shù)據(jù)挖掘中的相似性搜索方法和技術(shù)引入水文時(shí)間序列分析研究中,探索適合水文數(shù)據(jù)特點(diǎn)的相似性研究方法,挖掘相似的水文(流量)過(guò)程,發(fā)現(xiàn)隱藏在水文數(shù)據(jù)中有用的信息和知識(shí).

1 相似性搜索

1.1 原理

所謂相似性搜索,就是找出與給定查詢序列的變化行為最為接近的數(shù)據(jù)序列.給定一個(gè)目標(biāo)模式X=(x1,x2,…,xn)和一個(gè)序列Y=(y1,y2,…,ym),相似性問(wèn)題就是如何確定X和Y的相似度sim(X,Y).這里n和m的取值可以相同也可以不同,當(dāng)n=m時(shí)就是這兩個(gè)序列完全匹配(whole sequence matching)的問(wèn)題,即從具有相同長(zhǎng)度的序列中查找相似的序列;如果n≠m就是子序列匹配(subsequence matching)問(wèn)題,即從yi(i=1,2,…,m-n+1)開始,找出Y中與X最相似的子序列(假定n＜m).

無(wú)論哪一種相似性的搜索都依賴于時(shí)間序列的相似性度量方法,即如何定義sim(X,Y).目前時(shí)間序列相似性的度量主要是基于距離的度量.給定一個(gè)計(jì)算序列間的距離公式,并確定一個(gè)距離閾值,對(duì)任意給定的兩序列,當(dāng)距離小于或等于閾值時(shí),則認(rèn)為兩序列相似,否則,認(rèn)為二者不相似.因?yàn)殚L(zhǎng)度為n的時(shí)間序列可以看做是n維空間上的點(diǎn),所以空間距離函數(shù)可以用作序列距離公式.而最困難的是,如何定義序列間的距離.在時(shí)間序列相似性搜索中最常用的是歐幾里得距離(Eculidean distance),也稱歐氏距離.

假定兩個(gè)時(shí)間序列X=(x1,x2,…,xn)和Y=(y1,y2,…,ym),當(dāng)n=m時(shí),它們的歐氏距離定義為

歐氏距離雖然比較簡(jiǎn)單,但是在相似性的度量中卻很不可靠,這是因?yàn)闀r(shí)間軸的微小變形將會(huì)引起歐氏距離很大的變化,因此對(duì)時(shí)間軸有輕微變形的時(shí)間序列相似性的測(cè)量,歐氏距離將不再適用,如圖1所示.雖然兩個(gè)時(shí)間序列的形狀相似,但是它們?cè)跁r(shí)間軸上并不是完全對(duì)齊的,因此圖1(a)中用歐氏距離計(jì)算相似性結(jié)果的距離將會(huì)很大,可能會(huì)導(dǎo)致產(chǎn)生不相似的結(jié)果.若測(cè)量時(shí),時(shí)間軸可以根據(jù)具體情況進(jìn)行移動(dòng),在兩個(gè)序列之間尋找一條對(duì)齊路徑,使得兩個(gè)序列之間的歐氏距離最小,從而更直觀(更類似于人類思考方式)地測(cè)量時(shí)間序列的相似性,會(huì)更有效的找到兩個(gè)時(shí)間序列的相似形狀.對(duì)于這種情況人們提出了一種新的相似性測(cè)量方法——?jiǎng)討B(tài)時(shí)間扭曲(dynamic time warping,DTW)法[16],該方法允許在時(shí)間軸上有彈性地移動(dòng),以便能夠在兩個(gè)時(shí)間序列的不同時(shí)間階段發(fā)現(xiàn)相似的波形.動(dòng)態(tài)時(shí)間扭曲距離可以適時(shí)地轉(zhuǎn)換、擴(kuò)張或壓縮兩個(gè)序列的局部特征,實(shí)現(xiàn)兩個(gè)序列的同步化,因此動(dòng)態(tài)時(shí)間扭曲距離不要求比較序列長(zhǎng)度的一致性.最早動(dòng)態(tài)時(shí)間扭曲法是用于語(yǔ)音處理領(lǐng)域?qū)r(shí)間軸上的模式進(jìn)行對(duì)齊,后來(lái)Berndt等[17]將其引入到時(shí)間序列數(shù)據(jù)挖掘中.

圖1 不同的距離度量方法Fig.1 Different distance measuring methods

1.2 動(dòng)態(tài)時(shí)間扭曲算法

動(dòng)態(tài)時(shí)間扭曲法的計(jì)算過(guò)程是一個(gè)動(dòng)態(tài)最優(yōu)的計(jì)算過(guò)程,具體如下[18]:設(shè)兩個(gè)時(shí)間序列分別為X=(x1,x2,…,xn)和Y=(y1,y2,…,ym),構(gòu)建一個(gè)m×n階的矩陣,其中第(i,j)個(gè)元素就是兩個(gè)時(shí)間序列的點(diǎn)xi和點(diǎn)yj之間的距離d(xi,yj),通常采用d(xi,yj)=(xi-yj)2計(jì)算.如圖2所示,一個(gè)扭曲路徑W就是由上述矩陣元素構(gòu)成的連續(xù)路徑,這個(gè)路徑定義了時(shí)間序列X和Y之間的一個(gè)映射,W的第k個(gè)元素被定義為wk=(i,j)k,因此可以得到一個(gè)路徑集為

扭曲路徑要求滿足以下條件限制:

a.邊界條件:w1=(1,1),wK=(m,n),即要求扭曲路徑必須從矩陣的起始位置處開始和結(jié)束位置處結(jié)束.

圖2 扭曲路徑示意圖Fig.2 Example of warping path

b.連續(xù)性:給定wk=(a,b),wk-1=(a′,b′),要求a-a′≤1和b-b′≤1,即要求扭曲路徑每一步的設(shè)定都是連續(xù)的.

c.單調(diào)性:給定wk=(a,b),wk-1=(a′,b′),要求a-a′≥0和b-b′≥0,即要求路徑必須在時(shí)間軸上是單調(diào)的.也就是說(shuō),路徑W通過(guò)點(diǎn)(i,j)同時(shí)必須至少通過(guò)點(diǎn)(i-1,j-1),(i-1,j)或(i,j-1)中的一個(gè).

很顯然滿足上述條件的路徑有很多,假設(shè)可計(jì)算每條路徑達(dá)到點(diǎn)(m,n)時(shí)總的累積距離,具有最小累積距離者為最佳路徑,即路徑滿足一個(gè)最小的扭曲代價(jià):

式中,分母K用來(lái)消除不同扭曲路徑長(zhǎng)度的影響.

基于動(dòng)態(tài)最優(yōu)原理可知,設(shè)有點(diǎn)(i,j)在最佳路徑上,那么從點(diǎn)(1,1)到點(diǎn)(i,j)的子路徑也是局部最優(yōu)解,也就是說(shuō)從點(diǎn)(1,1)到點(diǎn)(m,n)的最佳路徑可以由時(shí)間起始點(diǎn)(1,1)到終點(diǎn)(m,n)之間的局部最優(yōu)解通過(guò)遞歸搜索獲得.構(gòu)造累積距離矩陣r,點(diǎn)(i,j)計(jì)算公式如下:

其初始條件為r1,1=d(x1,y1).從兩個(gè)序列起始點(diǎn)(1,1)開始迭代計(jì)算點(diǎn)(i,j)的累積距離,最終時(shí)間序列彎曲路徑最小累加值為rm,n,即為時(shí)間序列X和Y的動(dòng)態(tài)時(shí)間扭曲距離.圖3顯示了兩個(gè)時(shí)間序列X=(3,4,5,6,3,3)和Y=(1,3,2,1)的累積距離矩陣計(jì)算過(guò)程,最終得到序列X和Y的動(dòng)態(tài)時(shí)間扭曲距離為11,灰色格子為最佳路徑.

圖3 時(shí)間序列 X=(3,4,5,6,3,3)和Y=(1,3,2,1)的累積距離矩陣計(jì)算過(guò)程Fig.3 Cumulative distance matrix for computing dynamic time warping distance between X=(3,4,5,6,3,3)and Y=(1,3,2,1)

2 水文時(shí)間序列的相似性搜索

2.1 計(jì)算步驟

在水文過(guò)程中,季節(jié)性的水文過(guò)程往往表現(xiàn)出一定的相似性,這是由于影響水文過(guò)程的氣候因素,在每年的同一個(gè)季節(jié)中變化較一致,但也不是完全一致.例如,在夏季,經(jīng)常出現(xiàn)由暴雨而產(chǎn)生的洪水過(guò)程,這樣的過(guò)程往往是具有相似性的,但具體出現(xiàn)的日期往往不是每年的同一天,有可能會(huì)錯(cuò)開幾天,在這樣的情形下,如果采用歐式距離來(lái)度量?jī)蓚€(gè)洪水過(guò)程,得到的結(jié)論往往是兩個(gè)過(guò)程不相似,而如果采用動(dòng)態(tài)時(shí)間扭曲算法,就有可能發(fā)現(xiàn)在不同時(shí)間出現(xiàn)的相似過(guò)程.

本文選取塔里木河流域源流區(qū)出山口水文站沙里桂蘭克站1961—2000年共220場(chǎng)洪水作為相似性搜索的挖掘?qū)ο?采用動(dòng)態(tài)時(shí)間扭曲距離度量,挖掘相似的水文時(shí)間序列過(guò)程.計(jì)算步驟如下:

a.對(duì)220場(chǎng)洪水,分別進(jìn)行標(biāo)準(zhǔn)化.假設(shè)某場(chǎng)洪水過(guò)程的流量時(shí)間序列為(q1,q2,…,qn),采用零-均值標(biāo)準(zhǔn)化方法對(duì)其進(jìn)行標(biāo)準(zhǔn)化,計(jì)算公式如下:

b.對(duì)標(biāo)準(zhǔn)化后的220場(chǎng)洪水過(guò)程,兩兩進(jìn)行動(dòng)態(tài)時(shí)間扭曲距離的計(jì)算.

c.用一個(gè)220行220列的矩陣來(lái)存放計(jì)算得到的各場(chǎng)次洪水之間的動(dòng)態(tài)時(shí)間扭曲距離,稱之為相似性距離度量矩陣:

式中f1,f2,…,f220為這220場(chǎng)洪水的代號(hào).Dmatrix是一個(gè)對(duì)稱矩陣,矩陣的第(u,v)元素代表第u場(chǎng)洪水和第v場(chǎng)洪水之間的動(dòng)態(tài)時(shí)間扭曲距離,即DDTW(fu,fv).矩陣對(duì)角線為0,表示同一場(chǎng)洪水自身的動(dòng)態(tài)時(shí)間扭曲距離為0.矩陣內(nèi)元素的值越小,相應(yīng)的兩場(chǎng)洪水的動(dòng)態(tài)時(shí)間扭曲距離越小,則這兩場(chǎng)洪水過(guò)程越相似;反之,元素值越大,即相應(yīng)的兩場(chǎng)洪水的動(dòng)態(tài)時(shí)間扭曲距離越大,則兩場(chǎng)洪水過(guò)程越不相似.

d.除去對(duì)角線的0元素,從矩陣中選取元素值較小時(shí)所對(duì)應(yīng)的洪水,即為挖掘得到的相似的洪水過(guò)程.

2.2 計(jì)算結(jié)果

塔里木河流域源流區(qū)地域廣闊,氣候和地形變化復(fù)雜,從而形成了類型多樣、特征各異的洪水,按其洪水成因,可分為暴雨型洪水、融雪型洪水、混合型洪水和冰川湖潰決洪水[19].不同類型的洪水表現(xiàn)出不同的洪水流量過(guò)程形態(tài),同種類型且相同條件下形成的洪水表現(xiàn)出相似的洪水流量過(guò)程形態(tài).圖4為部分從相似性距離度量矩陣中挖掘得到的相似洪水過(guò)程.從圖4中可以發(fā)現(xiàn),本研究流域的洪水過(guò)程形態(tài)多樣,有中等流量陡漲緩落型洪水(圖4(a))、大流量的陡漲陡落型洪水(圖4(b))、矮胖型洪水(圖4(c)和圖4(d))、雙峰型洪水(圖4(e))和無(wú)明顯洪峰的洪水(圖4(f)).從相似性搜索中挖掘出相似的洪水過(guò)程,說(shuō)明這些洪水過(guò)程具有一定出現(xiàn)的頻率,也往往隱藏著相似的洪水成因.

圖4 相似的洪水流量過(guò)程線Fig.4 Similar flood discharge hydrographs

3 結(jié) 語(yǔ)

本文將時(shí)間序列相似性搜索的數(shù)據(jù)挖掘方法應(yīng)用于水文過(guò)程的相似性研究中,在分析歐氏距離和動(dòng)態(tài)時(shí)間扭曲距離兩種相似性距離度量方法特點(diǎn)的基礎(chǔ)上,采用對(duì)時(shí)間軸的伸縮和彎曲具有較好適應(yīng)性的動(dòng)態(tài)時(shí)間扭曲距離法對(duì)洪水流量過(guò)程進(jìn)行相似性距離度量,搜索挖掘出相似的洪水流量過(guò)程.實(shí)例結(jié)果表明,動(dòng)態(tài)時(shí)間扭曲距離法適合水文數(shù)據(jù)的特點(diǎn),能有效挖掘出相似的水文過(guò)程.今后值得研究的問(wèn)題是,水文時(shí)間序列相似性搜索如何進(jìn)一步與數(shù)據(jù)挖掘中聚類和分類的算法相結(jié)合,進(jìn)一步對(duì)場(chǎng)次洪水過(guò)程進(jìn)行相似性類型的劃分,從相似的洪水類型中分析其相似的物理成因和機(jī)制,從而發(fā)現(xiàn)隱藏在相似過(guò)程中的確定性規(guī)律.

[1]FAYYAD U M,PIATETSKY-SHAPIRO G,SMYTH P,et al.Advances in knowledge discovery and data mining[M].Menlo Park,California,USA:AAAI Press,1996:307-328.

[2]ROSENSTEIN M T,COHEN P R.Conceptsfrom time series[C]//The American Association for Artificial Intelligence.Proceedingsof the Fifteenth National Conference on Artificial Intelligence(AAAI-98).Menlo Park,California,USA:AAAI Press,1998:739-745.

[3]MAMNILA H,TOIVONEN H,VERKAMO A I.Discovering frequent episodes in sequences[C]//FAYYAD U M,UTHURUSAMY R.Proceeding of the First International Conference onKnowledge Discovery and Data Mining(KDD-95).Menlo Park,California,USA:AAAI Press,1995:210-215.

[4]AGRAWAL R,IMIELINSKI T,SWAMI A N.Mining association rules sets of items in large databases[C]//BUNEMAN P,JAJODIA S.Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data.New York:ACM Press,1993:207-216.

[5]DAS G,LIN K I,MAMNILA H,et al.Rule discovery from time series[C]//AGRAWAL R,STOLOR Z P E,PIATETSKY-SHAPIRO G.Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining(KDD-98).Menlo Park,California,USA:AAAI Press,1998:16-22.

[6]HAN J W,YIN Y W,DONG G Z.Efficient mining of partial periodic patterns in time series database[C]//KITSUREGAWA M,MACIASZEK L,PAPAZOGLOU M,et al.Proceeding of the Fifteenth International Conference Data Engineering(ICDE 1999).Los Alamitos,California,USA:IEEE Computer Society Press,1999:106-115.

[7]BETTINI C,JAJODIA S,WANG S.Time granularities in databases,data mining and temporal reasoning[M].New York:Springer-Verlag,2000.

[8]POVINELLI R J.Time series data mining:identifying temporal patterns for characterization and prediction of time series events[D].Milwaukee,Wisconsin:Marquette University,1999.

[9]HAN J W,KAMBER M.Data mining:concepts and techniques[M].San Francisco,USA:Morgan Kaufmann,2001.

[10]曾海泉.時(shí)間序列挖掘與相似性查找技術(shù)研究[D].上海:復(fù)旦大學(xué),2003.

[11]張保穩(wěn),何華燦.時(shí)態(tài)數(shù)據(jù)挖掘研究進(jìn)展[J].計(jì)算機(jī)科學(xué),2002,29(2):124-126.(ZHANG Bao-wen,HE Hua-can.Progress of temporal data mining research[J].Computer Science,2002,29(2):124-126.(in Chinese))

[12]榮岡.時(shí)間序列數(shù)據(jù)挖掘研究與應(yīng)用[D].杭州:浙江大學(xué),2004.

[13]侯玉,吳伯賢,鄭國(guó)權(quán).分形理論用于洪水分期的初步探討[J].水科學(xué)進(jìn)展,1999,10(2):140-143.(HOU Yu,WU Bo-xian,ZHENG Guo-quan.Preliminary study on the seasonal periods classification of floods by using fractal theory[J].Advances in Water Science,1999,10(2):140-143.(in Chinese))

[14]方崇惠,雒文生.分形理論在洪水分期研究中的應(yīng)用[J].水利水電科技進(jìn)展,2005,25(6):9-13.(FANG Chong-hui,LUO Wensheng.Application of fractal theory to stage research of flood events[J].Advances in Science and Technology of Water Resources,2005,25(6):9-13.(in Chinese))

[15]吳德.水文時(shí)間序列相似模式挖掘的研究與應(yīng)用[D].南京:河海大學(xué),2007.

[16]SAKOE H,CHIBA S.Dynamic programming algorithm optimization for spoken word recognition[J].IEEE Transactions on Acoustics,Speech and Signal Processing,1978,26(1):43-49.

[17]BERNDT D,CLIFFORD J.Using dynamic time warping to find patterns in time series[C]//FAYYAD U M,UTHURUSAMY R.AAAI-94 Workshop on Knowledge Discovery in Databases(KDD-94).Menlo Park,California,USA:AAAI Press,1994:229-248.

[18]KEOGH E,PAZZANI M.Derivative dynamic time warping[C]//KUMAR V,GR OSSMAN R.Proceedings of the First SIAM International Conference on Data Mining(SDM'2001).Philadelphia,PA,USA:SIAM,2001:1-11.

[19]新疆維吾爾自治區(qū)水利廳,新疆水利學(xué)會(huì).新疆河流水文水資源[M].烏魯木齊:新疆科技衛(wèi)生出版社,1998:144.