數(shù)據(jù)挖掘原理、-算法及應(yīng)用第6章-時(shí)間序列數(shù)據(jù)挖掘-PPT課件

1、第6章時(shí)間序列數(shù)據(jù)挖掘6.1概述6.2時(shí)間序列數(shù)據(jù)建模6.3時(shí)間序列預(yù)測6.4時(shí)間序列數(shù)據(jù)庫相似搜索6.5從時(shí)間序列數(shù)據(jù)中發(fā)現(xiàn)感興趣模式 6.1概述 時(shí)間序列是一種重要的高維數(shù)據(jù)類型， 它是由客觀對(duì)象的某個(gè)物理量在不同時(shí)間點(diǎn)的采樣值按照時(shí)間先后次序排列而組成的序列， 在經(jīng)濟(jì)管理以及工程鄰域具有廣泛應(yīng)用。 例如證券市場中股票的交易價(jià)格與交易量、 外匯市場上的匯率、 期貨和黃金的交易價(jià)格以及各種類型的指數(shù)，這些數(shù)據(jù)都形成一個(gè)持續(xù)不斷的時(shí)間序列。 利用時(shí)間序列數(shù)據(jù)挖掘， 可以獲得數(shù)據(jù)中蘊(yùn)含的與時(shí)間有關(guān)的有用信息， 實(shí)現(xiàn)知識(shí)的提取。時(shí)間序列數(shù)據(jù)本身具備有高維性、 復(fù)雜性、 動(dòng)態(tài)性、 高噪聲特性以及容易

2、達(dá)到大規(guī)模的特性，因此時(shí)間序列數(shù)據(jù)挖掘是數(shù)據(jù)挖挖中最具有挑戰(zhàn)性的十大研究方向之一。 目前的重點(diǎn)研究內(nèi)容包括時(shí)間序列的模式表示、 時(shí)間序列的相似性度量和查詢、 時(shí)間序列的聚類、 時(shí)間序列的異常檢測、 時(shí)間序列的分類、 時(shí)間序列的預(yù)測等。6.2時(shí)間序列數(shù)據(jù)建模 對(duì)于一個(gè)時(shí)間序列yt，t=1， 2， ，n，通常所建立的回歸模型都假定yt在整個(gè)時(shí)間范圍內(nèi)具有相同的變化模式， 這在許多情況下是適宜的。 但在實(shí)際中也確實(shí)存在著很多這樣的時(shí)間序列，它在整個(gè)時(shí)間序列里明顯地具有兩種或兩種以上的變化模式，對(duì)這樣的時(shí)間序列如果仍在整個(gè)時(shí)間序列里建立回歸模式(即假定它們?cè)谡麄€(gè)時(shí)間范圍里服從同一變化模式)，就明顯的不

3、太適合，效果也就不會(huì)太好。 對(duì)這樣的時(shí)間序列要采取非常規(guī)的建模方法，反映出它在不同時(shí)間范圍里的不同變化。 在實(shí)際中，具有不同變化規(guī)律的時(shí)間序列建立模型的方法有很多， 較常用的有虛擬變量法，段擬合法、 樣條函數(shù)法和門限模型法四種， 下面我們就來介紹和討論這四種方法。為簡單起見，我們假定時(shí)間序列yt(t=1， 2， ，n)在整個(gè)時(shí)間范圍里具有兩種不同的變化規(guī)律(具有多種變化規(guī)律時(shí)處理方法類似)，分界點(diǎn)或轉(zhuǎn)折點(diǎn)是k，即當(dāng)t=1， 2， ，k時(shí)，yt按某一模式變化，而當(dāng)t=k+1， k+2， ，n時(shí)，yt按另一模式變化。 這里，分界點(diǎn)或轉(zhuǎn)折點(diǎn)k?？赏ㄟ^觀察分析y的散點(diǎn)圖或曲線圖來確定。 1. 虛擬變量

4、法虛擬變量法就是設(shè)置一個(gè)在轉(zhuǎn)折點(diǎn)前后具有不同特征的虛擬變量Dt，在對(duì)yt建立回歸建模時(shí)引進(jìn)Dt, 從而通過Dt來反映yt的不同變化規(guī)律。 虛擬變量Dt最常用的形式是： (6.1) 這樣以t和Dt為自變量和解釋變量，yt為因變量和解釋變量，即可建立起回歸模型。通常是建立起如下最常用的線性回歸模型、 指數(shù)回歸模型或自回歸模型： (6.2) (6.3) (6.4) 2. 分段擬合法既然yt在前后兩個(gè)時(shí)間段里具有不同的變化規(guī)律， 那么一個(gè)很自然的做法就是在這兩個(gè)時(shí)間段里對(duì)yt分別建立回歸模型， 并且一般來說， 這兩個(gè)在不同時(shí)間段里具有不同變化規(guī)律的數(shù)據(jù)所建立的回歸模型是不同的， 因此可以反映出yt的轉(zhuǎn)

5、折性變化。 這種方法就是分段擬合法。分段擬合時(shí)， 兩個(gè)時(shí)間段的擬合模式或回歸函數(shù)類型可以是一樣的， 也可以是不一樣的， 因此分段擬合結(jié)果為(6.5) 這里, f1和f2一般可取為時(shí)間t的線性函數(shù)、多項(xiàng)式函數(shù)或指數(shù)函數(shù)，有時(shí)也可取為yt的滯后值yt-1、yt-2等的線性函數(shù)或這幾種函數(shù)的混合函數(shù)。 3. 樣條函數(shù)法上述兩種方法對(duì)yt建立的回歸模型在t=k處一般是不連續(xù)的，例如對(duì)模型(6.2)式， 在t=k處的左極限(即當(dāng)t從小于k處或k的左邊趨于k時(shí)的極限)為 (6.6) 而 在t=k處的右極限(即當(dāng)t從大于k處或k的右邊趨于k時(shí)的極限)為：(6.7) 由于b0， 因此(6.6)式和(6.7)式

6、不相等， 即在t=k處不連續(xù)。 這種不連續(xù)性一般是和實(shí)際相背的， 對(duì)于社會(huì)經(jīng)濟(jì)現(xiàn)象中的數(shù)據(jù)更是如此。因此上述兩種方法的擬合效果一般來說也不會(huì)很令人滿意。而樣條函數(shù)法正是對(duì)這一缺陷的一種補(bǔ)救方法，它是在多項(xiàng)式分段擬合(對(duì)其他函數(shù)形式也可如此處理，只是稍復(fù)雜而且也不常用)的基礎(chǔ)上加上分段多項(xiàng)式在轉(zhuǎn)折點(diǎn)t=k處的連續(xù)性和可微性的條件而形成的。下面我們給出實(shí)際中常用的幾種樣條函數(shù)擬合模型的形式，它們的具體推導(dǎo)就不在此詳述了。一次、 二次、 三次樣條函數(shù)擬合模型分別為(6.8) (6.9) (6.10) 如果引入(6.1)式中的虛擬變量Dt， 則上述三個(gè)模型可以簡寫為 (6.11) (6.12) (6.

7、13) 由此簡寫形式可以很容易地根據(jù)實(shí)際數(shù)據(jù)求出上述模型的系數(shù)， 因而也就能很容易地求出所需要的樣條函數(shù)擬合模型。 6.3時(shí)間序列預(yù)測 6.3.1局域線性化方法局部線性化方法是時(shí)間序列建模以及預(yù)測的有效方法， 其基本思想是采用相空間重構(gòu)的辦法，將時(shí)間序列當(dāng)前時(shí)刻點(diǎn)的領(lǐng)域線性化， 然后由所構(gòu)造的線性模型做出預(yù)測。局部線性化方法的原理如下所述。設(shè)觀測到時(shí)間序列xt, t=1, 2, , N，其中是采樣間隔數(shù)。根據(jù)下式從余震發(fā)生間隔時(shí)間序列重構(gòu)相空間：x (i) =(xi, xi+, , xi+(m-1) T, i=1, 2, , N (6.14) 其中，m為相空間維數(shù)， 為間隔時(shí)間。 (6.15)

8、 (6.16) (6.17) 其中，XRkm，yRk1，且應(yīng)使km。將按列零均值化，將也零均值化，那么在目標(biāo)點(diǎn)的鄰域內(nèi)建立如下線性模型：y=Xw+e (6.18)其中，e是零均值白噪聲，XRk1 ；w是參數(shù)向量， 。wRk1w的最小二乘估計(jì)為 (6.19) 根據(jù) 并由下式求出由在t時(shí)刻對(duì)t+T時(shí)刻的預(yù)測值(6.20) 當(dāng)X不是列滿秩或者X的條件數(shù)過大時(shí)，矩陣XTX接近奇異，將導(dǎo)致(6.19)式得出的參數(shù)估計(jì)不可信。另外如何選擇嵌入維數(shù)m也是令人困擾的問題。 1. SVD最小二乘法引理1矩陣 的SVD分解可描述為：存在n1階和n2階正交矩陣U和V，使 A=UDVT (6.21)式中, ；，12r

9、0是A的全部非零奇異值。 因此， 可以得到如下SVD最小二乘法： 考慮（5）式的線性回歸模型， 如果數(shù)據(jù)矩陣X是列滿秩的， 即r=n2， 設(shè)X的條件數(shù)c=1/r不大于一個(gè)給定的正數(shù)M， 且X的SVD分解為X=UDVT， 則w的SVD最小二乘估計(jì)為 (6.22)式中， g=(g1, g2, , gr) T， 且(6.23)其中，ui, 1ir是U的第i個(gè)列向量；i, 1ir是X的第i個(gè)奇異值。證明： 根據(jù)引理， 得X的SVD分解為X=UDVT， 因?yàn)槭钦痪仃嚕?得Dg=UTy， g=VTw注意到X列滿秩，且V是正交矩陣， D具有引理給出的形式， 可得結(jié)論。 2. 自適應(yīng)確定嵌入維數(shù)既然當(dāng)X不是

10、列滿秩或者X的條件數(shù)過大時(shí)， 導(dǎo)致線性最小二乘估計(jì)法的參數(shù)不可信， 因此需要改良X， 以使其列滿秩條件數(shù)不大于一個(gè)給定的正數(shù)M，從而保證參數(shù)估計(jì)的穩(wěn)健性。 設(shè)想在當(dāng)前時(shí)刻點(diǎn)，如果足夠大的嵌入維數(shù)是合理的， 那么數(shù)據(jù)矩陣X列滿秩且其條件數(shù)不大于M；反之， X很可能是病態(tài)的?；谶@個(gè)分析，我們可以在不損失估計(jì)精度的前提下達(dá)到此目的。做法是：先選一個(gè)初始嵌入維數(shù)m0， 然后在當(dāng)前時(shí)刻點(diǎn)，如果X是病態(tài)的，就做降維處理，從而找到一個(gè)最大的使X列滿秩且其條件數(shù)不大于M的嵌入維數(shù)m。 算法流程如下： (1) 初選嵌入維數(shù)m0，選定鄰近點(diǎn)數(shù)目k，并給定條件數(shù)閾值M0； (2) 在當(dāng)前時(shí)刻t，構(gòu)造X，并對(duì)X做S

11、VD分解； (3) while (1/rM)(4) r=r-1；r=r-1(5) end while(6) m=r 3. 自適應(yīng)局部線性化預(yù)測方法一般的局部線性化預(yù)測方法是取固定的嵌入維數(shù)， 按照相關(guān)的嵌入定理(Whitney定理和Taken定理)， 宜選擇較大的嵌入維數(shù)。 但是鑒于樣本數(shù)目有限， 在相空間上的某些數(shù)據(jù)點(diǎn)處，可能找不到k個(gè)彼此足夠接近的數(shù)據(jù)點(diǎn)， 這是導(dǎo)致預(yù)測誤差增加的主要原因。而如果是在較低維的相空間中， 就比較容易找到與當(dāng)前數(shù)據(jù)點(diǎn)足夠接近的k個(gè)數(shù)據(jù)點(diǎn)， 因此可以提高預(yù)測精度。故在當(dāng)前時(shí)刻，自適應(yīng)地選擇合適的嵌入維數(shù)，可望獲得比固定嵌入維數(shù)更好的預(yù)測結(jié)果。確定了合適的嵌入維數(shù)m

12、后，就可以重構(gòu)相空間，然后計(jì)算在當(dāng)前時(shí)刻點(diǎn)的預(yù)測值。自適應(yīng)局部線性化預(yù)測方法的步驟如下： (1) 根據(jù)Taken定理初選嵌入維數(shù)m0； 選定臨近點(diǎn)數(shù)目k， 并給定條件數(shù)閾值M0； (2) 在當(dāng)前時(shí)刻， 調(diào)用自適應(yīng)的算法確定合適的嵌入維數(shù)m； (3) 如果m=m0，則根據(jù)式(6.20)和式(6.22)計(jì)算出 ，做出預(yù)測;(4) 否則，根據(jù)m重構(gòu)相空間，并用式(6.18)和式(6.20)做出預(yù)測； (5) 重復(fù)步驟(2)和步驟(3)直到結(jié)束。 上述算法中的條件閾值M一般根據(jù)實(shí)驗(yàn)結(jié)果合理選擇， 根據(jù)經(jīng)驗(yàn)， 對(duì)許多實(shí)際問題， 一般取M=100較合適。 6.3.3神經(jīng)網(wǎng)絡(luò)方法神經(jīng)網(wǎng)絡(luò)是一組連接的輸入/輸

13、出單元， 其中每個(gè)連接都與一個(gè)權(quán)相關(guān)聯(lián)。 在學(xué)習(xí)階段，通過調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)，使其能夠預(yù)測輸入樣本的正確類標(biāo)標(biāo)號(hào)來學(xué)習(xí)。由于單元之間的連接，神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)又稱連接者學(xué)習(xí)。神經(jīng)網(wǎng)絡(luò)需要很長的訓(xùn)練時(shí)間， 因而對(duì)于有足夠長訓(xùn)練時(shí)間的應(yīng)用更合適。它需要大量的參數(shù)，這些參數(shù)通常主要靠經(jīng)驗(yàn)確定，如網(wǎng)絡(luò)拓?fù)浠颉敖Y(jié)構(gòu)”。神經(jīng)網(wǎng)絡(luò)的優(yōu)點(diǎn)包括其對(duì)噪聲數(shù)據(jù)的高承受能力，以及它對(duì)未經(jīng)訓(xùn)練的數(shù)據(jù)分類模式的能力。 對(duì)時(shí)間序列進(jìn)行預(yù)測時(shí)，給定的預(yù)測原點(diǎn)為k， 預(yù)測步長為t，即給定Y(k)的值和若干k時(shí)刻之前的時(shí)間點(diǎn)，要求預(yù)測y(k+t)的值。如果在k時(shí)刻預(yù)測y(k+t) ，需要先建立預(yù)測原點(diǎn)k和預(yù)測k+t之間的定量關(guān)系。由Ta

14、kens定理可知，在重構(gòu)的相空間中存在一個(gè)映射F: RmRm， 使得：Y(k+t)=F(Y(k)式中，y(k+t)為當(dāng)前狀態(tài)Y(k)的t步演化狀態(tài)。 因此只要能夠逼近真實(shí)函數(shù)F(g)，就能夠?qū)(k+t)的值作出預(yù)測。 BP網(wǎng)絡(luò)通過將網(wǎng)絡(luò)輸出誤差反饋回傳來對(duì)網(wǎng)絡(luò)參數(shù)進(jìn)行修正，從而實(shí)現(xiàn)網(wǎng)絡(luò)的映射能力。已經(jīng)證明，具有一個(gè)隱藏層的3層BP網(wǎng)絡(luò)可以有效地逼近任意連續(xù)函數(shù)，這個(gè)3層網(wǎng)絡(luò)包括輸入層、隱藏層和輸出層?？紤]到實(shí)際應(yīng)用當(dāng)中對(duì)于網(wǎng)絡(luò)預(yù)測泛化性能的要求，網(wǎng)絡(luò)設(shè)計(jì)應(yīng)堅(jiān)持盡可能減小網(wǎng)絡(luò)復(fù)雜性的原則。 對(duì)于一個(gè)給定的時(shí)間序列， 其具體的預(yù)測步驟如下： (1) 為了便于預(yù)測，首先對(duì)獲得的時(shí)間序列進(jìn)行歸一化處

15、理。歸一化方法為(6.24) (2) 選擇合適的m和重構(gòu)系統(tǒng)的狀態(tài)相空間， 依據(jù)預(yù)測步長要求構(gòu)造訓(xùn)練數(shù)據(jù)。輸入數(shù)據(jù)為： Y(k)=y(k), y(k-), , y(k-(m-1), k=1, 2, , N； 輸出數(shù)據(jù)為：y(k+t), k=1, 2, , N。 (3) 設(shè)計(jì)BP網(wǎng)絡(luò)結(jié)構(gòu)。網(wǎng)絡(luò)的輸入節(jié)點(diǎn)數(shù)目為重構(gòu)相空間的維數(shù)m，根據(jù)具體情況選擇合適的隱節(jié)點(diǎn)數(shù)目，因?yàn)槊看沃皇穷A(yù)測出一個(gè)數(shù)據(jù)點(diǎn)，輸出節(jié)點(diǎn)為單節(jié)點(diǎn)。用于實(shí)際預(yù)測的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖6-1所示。圖6-1神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖(4) 多次輸入訓(xùn)練數(shù)據(jù)Yk和對(duì)應(yīng)的理想輸出數(shù)據(jù)y(k+t)，對(duì)BP網(wǎng)絡(luò)進(jìn)行訓(xùn)練。訓(xùn)練結(jié)束以后就可以利用該網(wǎng)絡(luò)進(jìn)行預(yù)測了。 6

16、.4時(shí)間序列數(shù)據(jù)庫相似搜索 6.4.1問題描述對(duì)象之間相似性的定義和度量研究在統(tǒng)計(jì)理論、機(jī)器學(xué)習(xí)以及數(shù)據(jù)挖掘等方面都具有重大的意義。 基于大量甚至海量時(shí)間序列數(shù)據(jù)庫的數(shù)據(jù)挖掘技術(shù)，其研究目的是從大量時(shí)間序列數(shù)據(jù)中發(fā)現(xiàn)未知的模式和知識(shí)，因而主要研究時(shí)間序列數(shù)據(jù)之間的相互關(guān)系，即以某種度量來表征兩個(gè)時(shí)間序列之間的相似性，并以此為基礎(chǔ)實(shí)現(xiàn)多個(gè)時(shí)間序列數(shù)據(jù)中的相似性搜索、聚類、 分類和模式發(fā)現(xiàn)。因此，相似性問題成為時(shí)間序列數(shù)據(jù)挖掘中的基礎(chǔ)問題。時(shí)間序列數(shù)據(jù)的相似性搜索問題最早由IBM公司的Agrawal等人于1993年提出，該問題被描述為“給定某個(gè)時(shí)間序列，要求從一個(gè)大型的時(shí)間序列數(shù)據(jù)庫中找出與之最相

17、似的序列”。6.4.2時(shí)間序列相似性定義時(shí)間序列相似搜索(又稱為相似查詢)的目的是在時(shí)間序列數(shù)據(jù)庫中發(fā)現(xiàn)與給定序列模式相似的序列或查找?guī)熘邢嗨频男蛄小r(shí)間序列相似查詢可分為完全匹配和子序列匹配兩種情況，前者對(duì)應(yīng)查詢序列和被查詢序列長度相等的情況， 而后者是在長時(shí)間序列中查詢與查詢序列相似的子序列。完全匹配查詢和子序列匹配查詢進(jìn)一步又分為三種情況：(1) 范圍查詢(Range Query)。給定查詢序列q和時(shí)間序列數(shù)據(jù)集X，在X中搜索全部滿足d(q，x)的序列x。這里d(q，x)是q與x之間的距離，閾值是大于0的常數(shù)。 (2) 全部配對(duì)查詢 (All 2 Pairs Query)，也稱為空間聯(lián)合

18、(Spatial Joint) 。在時(shí)間序列集合X中找出所有相互之間距離小于閾值的所有序列對(duì)。將范圍查詢的條件略加修改，可以得到k最近鄰查詢。 (3) k最近鄰查詢(kNearest Neighbor Query)。給定查詢序列q和時(shí)間序列數(shù)據(jù)集X，在X中搜索k個(gè)與q距離最近的序列。 6.4.3高級(jí)數(shù)據(jù)表示與索引1. 高級(jí)數(shù)據(jù)表示TSDM面對(duì)的時(shí)間序列數(shù)據(jù)通常是海量數(shù)據(jù)，直接用原始數(shù)據(jù)進(jìn)行基于內(nèi)容的查詢以及時(shí)間序列聚類與分類分析等操作效率低下，甚至是不可行的。因此就需要研究合適的時(shí)間序列高級(jí)數(shù)據(jù)表示形式，在更高級(jí)的數(shù)據(jù)表示層次上進(jìn)行數(shù)據(jù)挖掘處理。從數(shù)學(xué)的觀點(diǎn)看，所謂時(shí)間序列高級(jí)數(shù)據(jù)表示，就是將

19、原始時(shí)間序列映射到某個(gè)特征空間中，并用它在這個(gè)特征空間中的映像來描述原始的時(shí)間序列。 這樣處理有兩個(gè)好處：實(shí)現(xiàn)了數(shù)據(jù)壓縮，從而將顯著減少后續(xù)處理的計(jì)算代價(jià)；在更抽象的層次上描述時(shí)間序列，有利于從中發(fā)現(xiàn)規(guī)律。 目前已有的時(shí)間序列高級(jí)數(shù)據(jù)表示形式大致可以分為如下幾類。1) 離散傅立葉變換(Discrete Fourier Transform， DFT) 離散傅立葉變換是最早被運(yùn)用于時(shí)間序列的相似性降維方法。 在對(duì)時(shí)間序列數(shù)據(jù)的相似分析中， 大多數(shù)人采用歐氏幾何距離作為相似性計(jì)算的依據(jù)，因此所選用的方法多采用保持歐氏距離的正交變換法。 離散傅立葉變換是一種十分常用的獨(dú)立于數(shù)據(jù)的變換。 一方面由于在時(shí)

20、間域中兩個(gè)信號(hào)的距離與頻率域中的歐氏距離相等； 另一方面因?yàn)镈FT開頭的幾個(gè)系數(shù)表現(xiàn)十分突出，可以集中信號(hào)的極大部分的能量，因此可以通過保留DFT前幾個(gè)系數(shù)來實(shí)現(xiàn)數(shù)據(jù)降維，成功地計(jì)算出實(shí)際距離的下界。自從DFT被Agrawal最早應(yīng)用于時(shí)間序列數(shù)據(jù)相似性搜索后， 又有其他一些論文相繼提出了DFT的許多擴(kuò)展和改進(jìn)方法，但核心思想并沒有什么變化。DFT算法的時(shí)間復(fù)雜度(n lgn)，相比于點(diǎn)對(duì)點(diǎn)的比較的時(shí)間復(fù)雜度O(mn)，甚至是O(nm2)，已經(jīng)有了很大的提高。離散傅立葉變換的基本算法如下。 對(duì)于連續(xù)信號(hào)x(t)，它的Fourier變換定義為式中， 虛數(shù)， f為頻率，X(f)為頻域函數(shù)。 設(shè)時(shí)間

21、序列x(k)(k=0，1，L，N-1)是由連續(xù)信號(hào)x(t)采樣得到的，采樣間隔為t，則有 (6.25) 同時(shí)信號(hào)可以通過逆變換恢復(fù)為 (6.26) (6.27) DFT所保留的系數(shù)越多， 恢復(fù)特征也就越多；DFT在數(shù)據(jù)截取的過程中，舍棄了信號(hào)的高頻成分，平滑了信號(hào)的局部極大值和極小值，因而造成了信息的遺漏。歐氏幾何距離在經(jīng)過DFT變換之后依然得到保持，所以可以用歐氏距離作為時(shí)間序列的相似性度量，即通過計(jì)算兩序列差的平方和的平方根作為這兩個(gè)時(shí)間序列的距離函數(shù)。如果計(jì)算的結(jié)果小于一個(gè)由用戶所定義的閾值，則可以認(rèn)為這兩個(gè)時(shí)間序列是相似的。 歐氏距離是一種較優(yōu)越的估計(jì)距離的方法，尤其是在信號(hào)受到高斯噪

22、聲干擾的時(shí)候，由于DFT變換具有保持歐氏幾何距離、計(jì)算簡便且能夠把信號(hào)大部分能量集中到很少的幾個(gè)系數(shù)當(dāng)中等優(yōu)點(diǎn)，所以用它來表示時(shí)間序列數(shù)據(jù)可以達(dá)到一定的要求。前幾個(gè)系數(shù)集中的能量越多，方法也就越有效。但是DFT卻平滑了原序列中局部極大值和局部極小值， 導(dǎo)致了許多重要信息的丟失。 此外，DFT還對(duì)序列的平穩(wěn)性有較高要求，對(duì)非平穩(wěn)序列并不適用。分段DFT可以用來緩和這一矛盾，但是分段的方法同樣也引入了一些新的問題。例如，分段過大會(huì)導(dǎo)致判斷力度的下降，分段過小又有低頻建模的缺陷。因此在實(shí)際應(yīng)用中，DFT的方法尚存在較大的局限性。 2) 離散小波變換 (Discrete Wavelet Transfo

23、rm， DWT) 離散小波變換和離散傅立葉變換一樣是一種線性信號(hào)處理技術(shù)。 當(dāng)用于數(shù)據(jù)向量D時(shí)，將它轉(zhuǎn)換成數(shù)值上不同但長度相同的小波系數(shù)的向量D。小波變換數(shù)據(jù)降維的實(shí)現(xiàn)同樣是由數(shù)據(jù)裁減實(shí)現(xiàn)的，即通過僅存放一小部分最強(qiáng)的小波系數(shù)來保留近似的壓縮數(shù)據(jù)。DWT是一種較好的有損壓縮，對(duì)于給定的數(shù)據(jù)向量，如果DWT和DFT保留相同數(shù)目的系數(shù)，則DWT能提供比原數(shù)據(jù)更精確的近似，更重要的是小波空間的局部性相當(dāng)好，有助于保留局部細(xì)節(jié)。DWT在很多場合的應(yīng)用中要比DFT更加有效。例如， DWT擁有時(shí)頻局部特性， 可以同時(shí)考慮時(shí)域和頻域的局部特性，而不像DFT那樣只考慮頻域特性。DWT在很大程度上和DFT處理方

24、法很類似， 其基本函數(shù)由遞歸函數(shù)定義。 信號(hào)的連續(xù)小波變換定義如下：(6.28) 其中，是尺度因子；反映了位移。 由多尺度分析可知， 任意函數(shù)都可以分解為細(xì)節(jié)部分W1和大尺度逼近部分V1； 然后，V1又可進(jìn)一步分解。如此重復(fù)進(jìn)行，我們可以將其分解為任意尺度(分辨率)的逼近部分和細(xì)節(jié)部分。小波分解與重構(gòu)的Mallat算法：設(shè)f(k)是一離散信號(hào)，f(k)=ck，則信號(hào)f(t)的正交小波變換分解公式為 (6.29) 其中，cj, k為尺度系數(shù)；dj, k為小波系數(shù)；j為分解的層數(shù)；N為離散采樣點(diǎn)數(shù)。其重構(gòu)過程為分解過程的逆運(yùn)算，相應(yīng)的重構(gòu)公式為(6.30) 在實(shí)際應(yīng)用中，總是希望能夠用盡量小的存儲(chǔ)

25、空間實(shí)現(xiàn)更快的計(jì)算速度，于是Harr小波變換最早被引入到時(shí)間序列的相似性研究中來。該方法得到了系數(shù)子集的良好近似，可以在保持歐氏幾何距離的同時(shí)更加簡便快捷地計(jì)算結(jié)果。小波變換在針對(duì)時(shí)間序列相似性研究中相比DFT并沒有太大的優(yōu)勢。DWT并沒有減少相對(duì)鏡像誤差，也沒有在相似性查詢中提高查詢的準(zhǔn)確性。在時(shí)間序列數(shù)據(jù)庫的相似性搜索中，基于DFT和基于DWT的不同技術(shù)相比并沒有太大的差異，而且DWT無法處理任意長度的序列。而在實(shí)際應(yīng)用中，始終分析一種長度的序列或是在索引中建立各種長度序列的架構(gòu)顯然也是不現(xiàn)實(shí)的，因此DWT在使用中還存在很大的缺陷。 3) 動(dòng)態(tài)時(shí)間彎曲(Dynamic Time Warpi

26、ng，DTW) 動(dòng)態(tài)時(shí)間彎曲廣泛用于語音識(shí)別領(lǐng)域，允許信號(hào)沿著時(shí)間軸對(duì)模式進(jìn)行伸縮變換，以使查詢模式Q和給定模式R相似。其基本思想是： 考慮時(shí)間序列X=x0, x2, , xn-1和Y=y0, y2, , yn-1， 允許通過重復(fù)元素?cái)U(kuò)展每個(gè)序列，歐氏距離在擴(kuò)展的序列X和Y之間計(jì)算。 設(shè)D(i, j)表示子序列x0, x2, , xn-1和y0, y2, , yn-1之間的動(dòng)態(tài)彎曲距離，用公式表示為D(i, j)=|xi-yi|+min D(i-1, j-1), D(i-1, j-1), D(i, j-1) (6.31)對(duì)彎曲路徑作如下限制： (1) 單調(diào)性： 路徑應(yīng)該不能向下或向左； (2)

27、 連續(xù)性： 在序列中沒有間斷點(diǎn)； (3) 邊界條件： 彎曲路徑要在矩陣的單元開始和結(jié)束位置。這種方法支持時(shí)間軸上的伸縮， 但需計(jì)算每個(gè)(i, j)的組合， 計(jì)算代價(jià)高。 4) 分段多項(xiàng)式表示(Piecewise PolynomialRepresentation，PPR)PPR有時(shí)也被稱為正交多項(xiàng)式變換(Orthogonal Polynomial Transform，OPT)。PLR實(shí)際上是PPR的特例，不過PLR出現(xiàn)得更早，應(yīng)用得也更普遍。 PPR是一類基于線性多項(xiàng)式回歸的正交變換。xX, 其長度|x|=m，在最小均方誤差意義下用如下多項(xiàng)式函數(shù)近似： f(t, w)=w0+w1t+w2t2+w

28、p-1tp-1 (6.32)即將x映射到多項(xiàng)式基1, t, t2, , tp-1張成的p維特征空間中的點(diǎn)w=(w0, w1, , wp-1)T，稱w是x的分段多項(xiàng)式表示(PPR)。 w=F(x)=(QTQ)-1QTx (6.33)式中，Q=(1T, , iT, , mT)T，i=(i0, i1, ip-1) T, i=1, 2, , m，x的逆變換為 x=F-1(w)=Qw (6.34)x與x之間滿足下式： x=x+e (6.35)其中，eN(0, 2)，e是殘差序列。 PPR實(shí)現(xiàn)RmRp的映射，一般mp， 因此RmRp的映射實(shí)現(xiàn)了時(shí)間序列數(shù)據(jù)的降維。 除上述的高級(jí)數(shù)據(jù)表示形式外，還有其他非系

29、統(tǒng)化方法，如界標(biāo)法以及微分法，等等。 2. 索引時(shí)間序列索引是海量時(shí)間序列數(shù)據(jù)庫相似查詢(有些文獻(xiàn)也稱之為相似搜索、基于內(nèi)容的查詢、 特定模式搜索等)的關(guān)鍵技術(shù)之一。 在時(shí)間序列數(shù)據(jù)庫相似查詢處理中， 一般首先用某種高級(jí)數(shù)據(jù)表示將原始時(shí)間序列映射為特征空間中的點(diǎn)， 然后再用某種空間索引結(jié)構(gòu)對(duì)這些點(diǎn)進(jìn)行索引。有關(guān)空間數(shù)據(jù)索引的問題一直是數(shù)據(jù)庫領(lǐng)域的研究熱點(diǎn)之一，研究成果也較多。從大的方面， 空間數(shù)據(jù)索引技術(shù)可分為兩類： 樹結(jié)構(gòu)和網(wǎng)格文件。6.4.4相似搜索算法的性能評(píng)價(jià)相似搜索算法的性能評(píng)價(jià)基本可分為三種。 1. 信息損失量 S=(x-x)(x-x) T (6.36) 其中，x為原始序列；x為高

30、維表示后的近似序列。 2. 相似查詢效率定義6.1給定查詢序列q，時(shí)間序列相似查詢算法的查詢效率為(6.37)因?yàn)閨CI|CO|，Dim1， 故Ef(q)0, 1)。對(duì)于順序掃描算法，上式中Dim=1；|CI|=|DB|。 3. 計(jì)算復(fù)雜度例如，任給一實(shí)值時(shí)間序列X，其長度|x|=n，X的PPR變換W=F(X)由(6.33)式計(jì)算。 因?yàn)?，其中的矩陣Q僅與n和p有關(guān)，故可以事先計(jì)算好Q以及(QTQ)-1QT。因?yàn)?QTQ)-1QT是pn維矩陣，故PPR變換需要進(jìn)行pn次乘法運(yùn)算和p(n-1)次加法運(yùn)算。 一般p遠(yuǎn)遠(yuǎn)小于n，故PPR變換的時(shí)間復(fù)雜度為O(n)。6.5從時(shí)間序列數(shù)據(jù)中發(fā)現(xiàn)感興趣模式

31、 6.5.1發(fā)現(xiàn)周期模式周期搜索問題可以描述為： 在一個(gè)規(guī)則時(shí)間間隔內(nèi)找出發(fā)生模式的問題。這個(gè)概念強(qiáng)調(diào)了問題的兩個(gè)方面， 即模式和間隔。因而，給出一個(gè)事件序列，我們可以找出隨時(shí)間重復(fù)的模式及它們重復(fù)發(fā)生的時(shí)間間隔。例如，給出在一個(gè)十年階段中某個(gè)公司的銷售記錄信息，要求我們找出在這十年中的一個(gè)基于每月的匯總數(shù)據(jù)的年度銷售模式。通過一些分析，我們也許發(fā)現(xiàn)某種產(chǎn)品在每年的七月達(dá)到它們的最大值，這是一個(gè)周期模式。然而，有時(shí)模式在一個(gè)自然時(shí)間間隔，如每小時(shí)、每天、每月內(nèi)等并不重復(fù)，電報(bào)碼就是這種例子。又如一個(gè)人的心臟跳動(dòng)通常在每分鐘、 每小時(shí)間隔內(nèi)并不規(guī)則跳動(dòng)。因而，人們會(huì)被問到對(duì)于被給定的銷售數(shù)據(jù)庫的

32、另外一種類型的問題是找出一個(gè)序列的重復(fù)模式以及同此模式階段相對(duì)應(yīng)的間隔。 1. 周期模式發(fā)現(xiàn)在與時(shí)間序列中模式發(fā)現(xiàn)有關(guān)的人工智能領(lǐng)域已經(jīng)做了很多的工作，所要考慮的問題是發(fā)現(xiàn)由事件(或?qū)ο?所標(biāo)識(shí)的規(guī)律，每一個(gè)事件(或?qū)ο?由一個(gè)屬性集標(biāo)識(shí)， 以便預(yù)告一個(gè)連續(xù)序列。 另外一個(gè)熱門的研究領(lǐng)域是尋找一個(gè)與給定規(guī)則表達(dá)式相匹配的文本子序列，或是尋找一個(gè)與給定字符串近似匹配的文本子序列。然而，這種問題并不考慮一個(gè)序列的周期行為，而且，用在這個(gè)問題中的技術(shù)是面向一個(gè)模式的匹配。另一方面，在我們的問題中，沒有給定的模式， 我們可以找到一種體現(xiàn)在一個(gè)序列中的周期模式來取代搜尋模式匹配問題的另外一種類型相似搜索

33、。我們比較兩個(gè)序列以便看它們是否全體或局部相似，這個(gè)問題處理比較兩個(gè)并行的序列以發(fā)現(xiàn)其中的共同之處，而在周期搜索的問題中，我們處理發(fā)現(xiàn)在所有相同階段、連續(xù)的同一個(gè)序列內(nèi)的共同之處。關(guān)于相似搜系的更詳細(xì)的資料可在參考書中找到。我們的問題是同查找序列模式問題相聯(lián)系的。 給定一個(gè)客戶交互的數(shù)據(jù)庫，序列模式挖掘的問題是查找在有一個(gè)用戶指定最小支持度的所有序列中找出最大序列。我們可以針對(duì)更普通的情況來考慮這個(gè)問題。 例如， 一個(gè)如表6-1所示的序列關(guān)系，如果最小支持度設(shè)為20%， 則這個(gè)事件中兩個(gè)序列1234和15符合這個(gè)支持度， 因?yàn)樗鼈兪窃诒?-1中客戶序列的兩個(gè)最少順序發(fā)生， 因而這兩個(gè)是所求的序

34、列模式，我們稱序列滿足這個(gè)最小支持度。所以除這兩個(gè)序列模式之外，1，2，3，4等都是大序列，即使它們不是最大的，而且，當(dāng)這個(gè)問題既不考慮一個(gè)序列的周期行為也不考慮在一個(gè)單個(gè)序列中的模式時(shí)， 一個(gè)序列如果它的長度是n稱為n序列。這個(gè)算法被稱為AprioriAll，它由查找所有的大1序列開始，在我們的例子中，這個(gè)大1序列是1， 2， 3，4和5， 然后這個(gè)算法通過迭代，首先從大n序列集中生成一個(gè)大(n+1)序列的候選集，這個(gè)(n+1)序列將要在原始序列中被重新檢測以看它們是否是更大的，這個(gè)候選生成過程包括一個(gè)加入(join)過程和一個(gè)刪整(prune)過程。 表6-1序列關(guān)系 2. 周期模式分析同

35、我們的研究最接近的是周期規(guī)律發(fā)現(xiàn)的問題。 規(guī)律的發(fā)現(xiàn)是周期關(guān)聯(lián)規(guī)則， 每個(gè)序列的形成與一個(gè)關(guān)聯(lián)規(guī)則相對(duì)應(yīng)。例如，一個(gè)序列0011同一個(gè)關(guān)聯(lián)規(guī)則A相關(guān)，表示A包含在t2和t3中。這里t1指時(shí)間間隔it， (i+1)t。如果每個(gè)關(guān)聯(lián)規(guī)則包含每個(gè)t時(shí)間單元(從tj開始)， 我們說這個(gè)關(guān)聯(lián)規(guī)則有一些周期行為，這個(gè)關(guān)聯(lián)規(guī)則的周期表示為(1，i)。在Ozden et.al. 的研究中，揭示了周期序列的一些特性，并且用這些特性發(fā)現(xiàn)與一個(gè)給定序列中有關(guān)的經(jīng)過時(shí)間顯示規(guī)則周期變化的規(guī)則，一些非常有用的屬性如下： 屬性1如果一個(gè)項(xiàng)目集X有一個(gè)周期(1，i)，則X的任何子集有周期(1，i)在這個(gè)屬性中，一個(gè)項(xiàng)目集指

36、包含在一個(gè)給定序列中的項(xiàng)目集，假設(shè)在x中有兩個(gè)項(xiàng)目x1，x2，如果X有一個(gè)周期(4，0)， 如果每4個(gè)時(shí)間單元重復(fù)從時(shí)間t0。開始，它暗示x1和x2將也有這個(gè)周期。 屬性2對(duì)于任何周期(1，i)來說，它的倍數(shù)(1，i)，這里1/l(l被1除)而且i=iT mod 1也是一個(gè)周期，因而，僅僅只有那些不是其他周期的倍數(shù)的周期才是我們關(guān)注的。 這些屬性被用做周期關(guān)聯(lián)規(guī)則挖掘技術(shù)的基礎(chǔ)， 這些技術(shù)包含周期刪節(jié)、周期跳過和周期消除。這些操作技術(shù)的總的思想是不必檢查每個(gè)項(xiàng)目集的周期，而是用周期序列的一些規(guī)則(或?qū)傩?來產(chǎn)生這個(gè)搜索空間，周期搜索問題因而被看做周期規(guī)則發(fā)現(xiàn)問題的一個(gè)超集。 6.5.2發(fā)現(xiàn)例外

37、模式數(shù)據(jù)挖掘的重要的任務(wù)之一是發(fā)現(xiàn)偏離分布主體的少數(shù)對(duì)象所呈現(xiàn)的弱模式，即例外模式。 挖掘例外模式有助于人們發(fā)現(xiàn)電子商務(wù)和移動(dòng)通信等領(lǐng)域中存在的欺詐模式，或者用于發(fā)現(xiàn)機(jī)電系統(tǒng)的故障與異常。 本節(jié)主要介紹時(shí)間序列數(shù)據(jù)的例外模式挖掘問題。 給出了時(shí)間序列例外模式的形式化定義，并提出一種基于這個(gè)定義的例外模式的挖掘算法。 1. TSDM中的例外模式數(shù)據(jù)挖掘中的“例外(Outlier)”這個(gè)詞是從時(shí)間序列分析理論中借用過來的, 因此時(shí)間序列數(shù)據(jù)挖掘中的例外模式的概念與時(shí)間序列分析理論中的例外的概念的區(qū)別必須搞清楚。傳統(tǒng)的時(shí)間序列分析理論中所講的“例外(Outlier)”是指一個(gè)孤立的異常觀測值。 Ha

38、wkins給例外下的經(jīng)典定義是： “例外是一個(gè)觀測， 它與其他的觀測偏離很大，以至于人們懷疑它是由一個(gè)不同的機(jī)制產(chǎn)生的?！?按照這個(gè)定義，1個(gè)時(shí)間序列中的例外會(huì)對(duì)模型辨識(shí)和參數(shù)估計(jì)帶來不利的影響，因此是有害的。A.Justel等人還提出了“例外片”的概念， 即若干個(gè)連續(xù)的例外。在時(shí)間序列分析中，無論是例外還是例外片都是相對(duì)某一具體的數(shù)學(xué)模型而言的, 檢測例外或例外片的任務(wù)就是發(fā)現(xiàn)一個(gè)時(shí)間序列中的例外或例外片，并盡可能準(zhǔn)確地估計(jì)其真值。就這個(gè)意義上說，例外(片)等同于噪聲，是需要消除的。 時(shí)間序列數(shù)據(jù)挖掘研究者認(rèn)為例外模式中蘊(yùn)含著有用的知識(shí)。 一個(gè)時(shí)間序列中的例外模式反映了產(chǎn)生這個(gè)時(shí)間序列的系統(tǒng)

39、或現(xiàn)象的行為發(fā)生了某種改變。因此， 挖掘例外模式的任務(wù)就是辨識(shí)出一個(gè)時(shí)間序列中的全部例外模式并提供給用戶。 可見，時(shí)間序列數(shù)據(jù)挖掘研究者們和時(shí)間序列分析研究者們對(duì)例外的價(jià)值認(rèn)識(shí)是不同的。這種認(rèn)識(shí)上的差異是由于雙方對(duì)例外的定義不同而造成的。時(shí)間序列數(shù)據(jù)挖掘中關(guān)心更多的是時(shí)間序列的形態(tài)特征，而不是其動(dòng)力學(xué)特征。時(shí)間序列數(shù)據(jù)挖掘中定義的模式是一個(gè)相似的時(shí)間序列集合。時(shí)間序列的例外模式定義為一個(gè)與其他模式顯著不同且出現(xiàn)頻率相對(duì)較低的模式。因此例外模式中很可能蘊(yùn)含著系統(tǒng)的某種行為或者性質(zhì)的改變，如系統(tǒng)故障等。 2. 已有的例外模式挖掘算法近年來，傳統(tǒng)的數(shù)據(jù)挖掘研究領(lǐng)域?qū)饽Ｊ酵诰虻难芯恳呀?jīng)較深入了。例

40、外模式發(fā)現(xiàn)方法可分為基于分布的方法、基于深度的方法、 基于距離的方法和其他方法?；诜植嫉姆椒ú捎脴?biāo)準(zhǔn)分布(如正態(tài)分布、 泊松分布等)擬合數(shù)據(jù)集，根據(jù)數(shù)據(jù)分布情況定義偏差。其主要缺點(diǎn)是這些分布絕大多數(shù)適合于單變量情況，而且對(duì)于數(shù)據(jù)挖掘應(yīng)用來說， 數(shù)據(jù)的分布情況事先并不知道， 需要通過很多次的測試才能找到合適的數(shù)據(jù)分布表示方式。用標(biāo)準(zhǔn)分布表示數(shù)據(jù)既費(fèi)力， 又得不到滿意的結(jié)果。在基于深度的方法中，數(shù)據(jù)集D每一個(gè)數(shù)據(jù)對(duì)象表示為K維空間中的一個(gè)點(diǎn)，K即深度。人們提出了許多定義深度的方法。根據(jù)某種深度定義方法，在數(shù)據(jù)空間中以分層的方式表示數(shù)據(jù)對(duì)象。異常數(shù)據(jù)即那些具有較小深度的數(shù)據(jù)。這種方法避免了基于分布

41、的方法中的數(shù)據(jù)分布擬合問題， 理論上也適合處理多維數(shù)據(jù)。 Knorr等人首次對(duì)例外模式進(jìn)行了形式化定義， 提出了基于距離的例外模式定義, 即DB(p, d)-Outlier的概念，并給出了相應(yīng)的例外模式挖掘算法。Knorr和Ng將例外模式定義為：如果數(shù)據(jù)集D中至少有p%的對(duì)象到對(duì)象O(OD)的距離大于d，那么，對(duì)象O是一個(gè)DB(p, d) -Outlier。該定義的特點(diǎn)是對(duì)例外模式的定義具有一定的靈活性，通過調(diào)節(jié)參數(shù)p和d可以獲得不同強(qiáng)度的例外模式。后來的許多例外模式挖掘算法都或多或少受到了Knorr和Ng的這一工作的啟發(fā)。 有些研究者認(rèn)為應(yīng)當(dāng)強(qiáng)調(diào)例外模式的局部性， 他們對(duì)例外模式的定義為：如

42、果數(shù)據(jù)集D的對(duì)象O距離與它最近鄰的對(duì)象較遠(yuǎn)，且O中包含的元素?cái)?shù)目較少，則O是一個(gè)例外模式。然而，上述定義的著眼點(diǎn)主要是如何對(duì)數(shù)據(jù)進(jìn)行分類，從而發(fā)現(xiàn)例外模式。這些成果并不能直接用于辨識(shí)時(shí)間序列數(shù)據(jù)中的例外模式，因?yàn)閷?duì)時(shí)間序列如何分類本身就是一個(gè)復(fù)雜的問題。特別是面對(duì)海量時(shí)間序列數(shù)據(jù)，要求例外模式發(fā)現(xiàn)算法必須要能實(shí)現(xiàn)時(shí)間序列數(shù)據(jù)的降維(即壓縮)，否則，直接對(duì)原始時(shí)間序列數(shù)據(jù)進(jìn)行操作將是沒有效率的， 甚至是不可行的。本章采用的思路是用某種合適的高級(jí)數(shù)據(jù)表示將原始時(shí)間序列數(shù)據(jù)映射到正交多項(xiàng)式基張成的特征空間中， 不但實(shí)現(xiàn)了時(shí)間序列數(shù)據(jù)的降維， 而且可以在特征空間中方便地進(jìn)行聚類操作。 3. 時(shí)間序列的

43、例外模式定義考慮一個(gè)可數(shù)模式集合P=P1, P2, , PK， 這些模式的中心分別記為cen=cen1, cen2, , cenK。 假設(shè)： (1) ； (2)。 其中， 表示空集。定義6.2模式PiP(i=1, 2, , K）的頻率為(6.38) 這里， 記號(hào)| |表示模式中的元素?cái)?shù)目。 定義6.3模式PiP(i=1, 2, , K)的例外支持度為 其中，D(ceni, cenj)是模式Pi的中心ceni到模式Pj的中心cenj的距離；DMi和DMj分別是模式Pi和模式Pj中的元素到其中心的最大距離。 定義6.4給定模式集合P，閾值01；對(duì) ，如果os(Q)0，有QP，如果Q是模式集合P中的

44、一個(gè)廣義例外模式，且滿足f(Q)(6.41) 則稱模式Q是模式集合P中的一個(gè)狹義例外模式。 狹義例外模式定義是符合數(shù)據(jù)挖掘中經(jīng)典的例外模式定義的。 狹義例外模式的定義強(qiáng)調(diào)例外模式與其他模式顯著不同且出現(xiàn)頻率相對(duì)較低。 【例6.1】如圖6-2所示，假設(shè)將全部數(shù)據(jù)集分為A、B、 C和D等4個(gè)模式。那么按照廣義例外模式的定義，A、B、C和D這4個(gè)模式互為廣義例外模式；而按照狹義例外模式的定義，只有C和D這兩個(gè)模式是潛在的狹義例外模式。 圖6-2例外模式圖示4. 辨識(shí)時(shí)間序列中例外模式的算法本節(jié)提出一種系統(tǒng)化的辨識(shí)時(shí)間序列中例外模式的算法。 該算法的一般框架如圖6-3所示。該算法分為4步： (1) 將原始時(shí)間序列數(shù)據(jù)分割成子序列集合。 (2) 將這些子序列用某種高級(jí)數(shù)據(jù)表示映射成特征空間的點(diǎn)。 可選的高級(jí)數(shù)據(jù)表示包括FFT、DWT、 PPR、 DTW等。 (3) 用聚類算法對(duì)特征空間中的點(diǎn)進(jìn)行聚類， 得到一個(gè)模式集合P以及每一個(gè)模式的中心。(4) 用時(shí)間序列的例外模式的定義辨識(shí)P中的例外模式?？梢愿鶕?jù)不同應(yīng)用的需要， 辨識(shí)廣義例外模式， 或者狹義例外模式。 圖6-3 辨識(shí)時(shí)間序列中例外模式的步驟考慮一個(gè)單變量實(shí)值時(shí)間序列xt(t=1，2，N)，具體的算法流程如下： (1) 給定一個(gè)