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

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

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

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

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

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

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

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

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

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

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

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

13、出單元， 其中每個連接都與一個權相關聯。 在學習階段，通過調整神經網絡的權，使其能夠預測輸入樣本的正確類標標號來學習。由于單元之間的連接，神經網絡學習又稱連接者學習。神經網絡需要很長的訓練時間， 因而對于有足夠長訓練時間的應用更合適。它需要大量的參數，這些參數通常主要靠經驗確定，如網絡拓撲或“結構”。神經網絡的優點包括其對噪聲數據的高承受能力，以及它對未經訓練的數據分類模式的能力。 對時間序列進行預測時，給定的預測原點為k， 預測步長為t，即給定Y(k)的值和若干k時刻之前的時間點，要求預測y(k+t)的值。如果在k時刻預測y(k+t) ，需要先建立預測原點k和預測k+t之間的定量關系。由Ta

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

15、理。歸一化方法為(6.24) (2) 選擇合適的m和重構系統的狀態相空間， 依據預測步長要求構造訓練數據。輸入數據為： Y(k)=y(k), y(k-), , y(k-(m-1), k=1, 2, , N； 輸出數據為：y(k+t), k=1, 2, , N。 (3) 設計BP網絡結構。網絡的輸入節點數目為重構相空間的維數m，根據具體情況選擇合適的隱節點數目，因為每次只是預測出一個數據點，輸出節點為單節點。用于實際預測的神經網絡結構如圖6-1所示。圖6-1神經網絡結構圖(4) 多次輸入訓練數據Yk和對應的理想輸出數據y(k+t)，對BP網絡進行訓練。訓練結束以后就可以利用該網絡進行預測了。 6

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

17、似的序列”。6.4.2時間序列相似性定義時間序列相似搜索(又稱為相似查詢)的目的是在時間序列數據庫中發現與給定序列模式相似的序列或查找庫中相似的序列。時間序列相似查詢可分為完全匹配和子序列匹配兩種情況，前者對應查詢序列和被查詢序列長度相等的情況， 而后者是在長時間序列中查詢與查詢序列相似的子序列。完全匹配查詢和子序列匹配查詢進一步又分為三種情況：(1) 范圍查詢(Range Query)。給定查詢序列q和時間序列數據集X，在X中搜索全部滿足d(q，x)的序列x。這里d(q，x)是q與x之間的距離，閾值是大于0的常數。 (2) 全部配對查詢 (All 2 Pairs Query)，也稱為空間聯合

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

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

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

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

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

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

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

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

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

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

28、p-1tp-1 (6.32)即將x映射到多項式基1, t, t2, , tp-1張成的p維特征空間中的點w=(w0, w1, , wp-1)T，稱w是x的分段多項式表示(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實現RmRp的映射，一般mp， 因此RmRp的映射實現了時間序列數據的降維。 除上述的高級數據表示形式外，還有其他非系

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

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

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

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

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

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

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

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

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

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

39、或現象的行為發生了某種改變。因此， 挖掘例外模式的任務就是辨識出一個時間序列中的全部例外模式并提供給用戶。 可見，時間序列數據挖掘研究者們和時間序列分析研究者們對例外的價值認識是不同的。這種認識上的差異是由于雙方對例外的定義不同而造成的。時間序列數據挖掘中關心更多的是時間序列的形態特征，而不是其動力學特征。時間序列數據挖掘中定義的模式是一個相似的時間序列集合。時間序列的例外模式定義為一個與其他模式顯著不同且出現頻率相對較低的模式。因此例外模式中很可能蘊含著系統的某種行為或者性質的改變，如系統故障等。 2. 已有的例外模式挖掘算法近年來，傳統的數據挖掘研究領域對例外模式挖掘的研究已經較深入了。例

40、外模式發現方法可分為基于分布的方法、基于深度的方法、 基于距離的方法和其他方法。基于分布的方法采用標準分布(如正態分布、 泊松分布等)擬合數據集，根據數據分布情況定義偏差。其主要缺點是這些分布絕大多數適合于單變量情況，而且對于數據挖掘應用來說， 數據的分布情況事先并不知道， 需要通過很多次的測試才能找到合適的數據分布表示方式。用標準分布表示數據既費力， 又得不到滿意的結果。在基于深度的方法中，數據集D每一個數據對象表示為K維空間中的一個點，K即深度。人們提出了許多定義深度的方法。根據某種深度定義方法，在數據空間中以分層的方式表示數據對象。異常數據即那些具有較小深度的數據。這種方法避免了基于分布

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

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

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

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