朱淵萍

（南昌工程學院 計算機科學與技術(shù)系，江西 南昌 330099）

一種新的時間序列相似性模式發(fā)現(xiàn)算法

朱淵萍

（南昌工程學院 計算機科學與技術(shù)系，江西 南昌 330099）

為了提高效率，基于時間序列的數(shù)據(jù)挖掘，采用了近似的方法取代原有時間序列，這導(dǎo)致了數(shù)據(jù)挖掘準確性的降低，文章的主要目標在于有效率地搜尋時間序列中的相似子序列向量，且希望能夠兼顧準確性及效率，進而提供不同領(lǐng)域?qū)τ跁r間序列的不同需要.

時間序列；數(shù)據(jù)挖掘；相似子序列

時間序列相似性模式發(fā)現(xiàn)是時間序列數(shù)據(jù)挖掘中的一個重要方面.在生物信息這個領(lǐng)域中，利用像生物芯片這樣的技術(shù)，使得生物學家得以分析成千上萬基因與基因，甚至是蛋白質(zhì)與蛋白質(zhì)之間的相互關(guān)系.另外，時間序列分析包含了其它的研究，例如時間序列的索引或查詢、時間序列的叢集分析、時間序列的規(guī)則或模式的研究.但這些應(yīng)用都脫離不了最基本的問題，那就是如何正確地定義時間序列間的相似度.最早用于時間序列相似度計算的方法就是利用歐幾里德相似度量測法[1]，雖然這個方法解決了程度變形及偏移量，但對于時間序列長度長短不一、序列有噪聲存在及平移問題，此方法就變得不可行.動態(tài)時間變形[2]原本是用于語音識別的分析，其主要想法是允許序列中的任一點多次復(fù)制以將序列延伸，如此便可解決時間平移的問題，而序列間的相似度則是利用延伸后的序列，計算他們之間的歐幾里德距離當成其相似度，此方法首先找出兩時間序列之最佳的對齊方式，然后利用歐幾量德距離計算其相似度，但因為使用歐幾里德距離，所以依然無法解決程度變形及偏移量的問題.隨著數(shù)據(jù)量的增加，不少時間序列的分析方法都會變得難以運行.因為這些方法執(zhí)行所需的時間會隨著數(shù)據(jù)量及時間點的增加而變得更高.

目前不少人提出了將原有的時序數(shù)據(jù)維度轉(zhuǎn)換到另一維度來達成維度縮減的方法，比如Agraw?al提出使用離散付里葉變換，即F-index算法[3].在上述算法的基礎(chǔ)上Chan Franky提出用小波變換的方法進行時間序列相似性匹配[4]，用Haar小波對序列進行維數(shù)約簡，在R樹上進行相似匹配，進而降低所需運行的執(zhí)行時間.上述隔點采樣抽取算法有較大的局限性，在損失峰值信息的同時無法確保所提取曲線趨勢的有效性和效率.因此如何在時序數(shù)據(jù)的正確性及效率上取得一個平衡點，就成了許多人研究的問題.

本文對時間序列做了兩次變換，分別為角度變換及符號變換.角度變換后的數(shù)據(jù)能夠保有原有的特性，保證了數(shù)據(jù)正確性，符號變換比對數(shù)值數(shù)據(jù)直接分析運行時間少.變換后，采用有限狀態(tài)機檢索子模式，時間復(fù)雜度降低，進而更有效率地處理相似子序列.

1 相似子序列搜索算法

1.1 角度變換

為了解決時間序列分析所遇到的難題，我們首先為時間序列做角度變換.假設(shè)現(xiàn)有一時間序列向量S，為了找到相似的子序列，我們首先將原本的時間序列向量S變換成S′；T代表著時間序列記錄的時間點.

將原本的時間序列變換成S′，這樣的轉(zhuǎn)換是希望保留住原本序列上升及下降的變化，進而利用這些變化找到相似的子序列.如圖1所示，我們希望將所有的時間序列改以其變化的角度來做記錄.

new_min，new_max則分別為正規(guī)化后所有向量值域的最小及最大值.

因轉(zhuǎn)換后的時間序列S?被正規(guī)化到-1及1之間，這樣我們就能利用反三角函數(shù)sin-1求角度.經(jīng)由角度變換的方式，原有的時間序列改變?yōu)橹挥涗浧鋮^(qū)段的序列變化情況.

1.2 符號變換

為了達到維度縮減的目的，我們采取將數(shù)值型態(tài)的數(shù)據(jù)轉(zhuǎn)換成符號型態(tài)的數(shù)據(jù)，雖然這樣的方式可能會造成數(shù)據(jù)的完整性不足.但相對于直接對數(shù)值型態(tài)的數(shù)據(jù)做分析，這樣的方式時間運行的成本相當高.所以為了在數(shù)據(jù)完整性及效率上取得一個平衡點，我們提供使用者一個設(shè)定參數(shù)（SN），來決定應(yīng)該使用多少符號取代原有的數(shù)值型態(tài)的數(shù)據(jù)，這樣就能在許可范圍內(nèi)處理所需要的數(shù)據(jù).而這樣的方式使得我們能有效率地為時間序列做分析，而不失其準確性.

（1）首先利用Z-score正規(guī)化法

將所有的角度正規(guī)化成其平均值為0，且標準差為1，這是為了將序列數(shù)據(jù)正規(guī)化成正態(tài)分布，因此當使用者決定好要用多少符號來取代原有的時間序列時，我們便可利用表1來決定不同符號之間的切點，而這些切點大約等分了整個正態(tài)分布.

表1 正態(tài)分布切點Tab.1 Tangency point of normal distribution

（2）接下來利用表1的切點，將原本的角度取代為符號.如圖，假設(shè)SN=5且得到符號切點分別為：A（54°至 90°）、B（18°至 54°）、C（-18°至 18°）、D（-54°至-18°）、E（-90°至-54°），則原本的角度將會依序轉(zhuǎn)換成符號.

如圖1，第一個時間序列的夾角為45°，介于18°至54°之間，所以于轉(zhuǎn)換時以符號B表示，以此類推將整個序列轉(zhuǎn)換成字串，上圖的序列夾角就轉(zhuǎn)變成字串BDEAEB.

利用這樣的符號變換，我們可將所有的時間序列數(shù)據(jù)轉(zhuǎn)換成以符號代表，接著利用現(xiàn)有的有效率的字串算法，便可找出兩時間序列中相似的部份.

1.3 檢索子模式算法

從上面的變換我們可以看到，所有的時間序列都會由一定個數(shù)的字符所代表，這樣將時間復(fù)雜度降低至與字符個數(shù)成比例就成了我們的目標.雖然現(xiàn)有的Suffix Tree[5]已相當有效率的字串算法，但是它的時間復(fù)雜度會隨著字串的長度而增加，在此我們利用類似有限狀態(tài)自動機的概念來重新定義一時間序列，且這個時間序列能夠保存原有Suffix Tree的信息.其步驟如下：

（1）首先分別建立字符串"BANANAS"及"BAS?CANA"，比如字符串"BANANAS"只有四種字符，故一開始只擁有四個結(jié)點如圖2（a），接下來由字符"B"開始，依據(jù)其下一個字符在結(jié)構(gòu)上增加邊如（b），且在邊上會給予編號，這個編號記錄的是"B"在字串中的位置，而"B"也同樣記錄這樣的數(shù)據(jù)，這代表著通過此邊的條件為此字符的發(fā)現(xiàn)位置必須與邊上的編號相同，以此類推，將整個結(jié)構(gòu)建立完成如（g），而我們利用陣列來記錄這樣的結(jié)構(gòu)如表2（a）.

（2）接下來利用記錄字符串"BANANAS"的表2（a）及"BASCANA"的表2（b），取此兩表的交集得到表2（c）.

（3）最后利用表2（c），由不同的字符出發(fā)便可得到如表3中所有的相同子字串，最后依照其在原字串中的順序一一排列.

表2 字符串記錄表Tab.2 String recording

表3 子串位置Tab.3Substring position

而這當中的"C"可以直接忽略，因在字串"BA?NANAS"并沒有相對應(yīng)的位置，而"AS"及"C"則因在"BANANAS"中出現(xiàn)的位置皆在"ANA"之后，所以比較其子字串的長度后會保留"ANA"，而"NA"出現(xiàn)的位置皆被"ANA"所包含，故也可省略.

（4）最后我們得到的子序列分別為"BA"及"ANA"，因"ANA"共出現(xiàn)在字串"BANANAS"的第2及第5個位置，但第2個位置會與"BA"有重復(fù)，因此正確的對應(yīng)的方式應(yīng)為：

假設(shè)n代表時間序列庫中被搜索字符串的長度，m代表要搜索字符串的長度，而k代表字串中符號的個數(shù)，采用Suffix tree方法的時間復(fù)雜度是O（n+m），而該方法是O（k2）可以看出當時間序列的長度很長時，使用有限狀態(tài)自動機的概念能夠大幅地減少時間復(fù)雜度.此外用來記錄的結(jié)構(gòu)也能用來同時處理多個時間序列相似的部份，且這樣的結(jié)構(gòu)在k值不變時，并不需要重新建立，因此用來為相似子序列做索引或重復(fù)搜索時能提供信息的再利用.

2 結(jié)論

維度變換的缺點就是原始數(shù)據(jù)正確性的降低，但在數(shù)據(jù)量不斷增加情況下，現(xiàn)有的方法已不再能夠承受如此龐大的計算量，如何快速地尋找有效的信息，便成了數(shù)據(jù)挖掘領(lǐng)域的一大挑戰(zhàn).在本文中，利用符號變換取代原有的數(shù)據(jù)，接著再利用有限狀態(tài)機的字符串算法來改進搜索的效率，這不僅僅提供了更有效率的方式給使用者，更大大地提升原本耗時耗力的運算.

[1]李斌,譚立湘.面向數(shù)據(jù)挖掘的時間序列符號化方法研究[J].電路與系統(tǒng)學報,2000,4(5):9-14．

[2]鄭詮,朱明,王俊普.相似時間序列的快速檢索算法[J].小型微型計算機系統(tǒng),2004,25(5):785-789．

[3]Agrawal,Faloutsos C,Swami A.Efficient similarity search in sequence databases[A].Proceedings of the 4th Int'l Con?ference on Foundations of Data Organization and Algo?rithms[M].New York：Springer,1993:69-84.

[4]Franky C,Fu Waichee.Efficient Time Series M atching by Wavelets[J].15th IEEE International Conference on Da?ta Engineering,Sydney，Australia,1999,23/26:126-133．

[5]Pampapathi R,Mirkin B,Levene M.A suffix tree ap?proach to anti-spam email filtering[J].Machine Learning,2006,65(1):309-338．

An New Algorithm of Finding Simliar Subpattern Based on Times Series

ZHU Yuanping
（School of Information Engineering，Nanchang Institute of Technology，Nanchang330099，China）

Based on the data mining of times series,the approximation-like methods for performance improvement,lead to decrease of accuracy.In this paper,we focus on the efficient method of searching similar subpattern,which considers balance between performance and accuracy.

times series；data mining；similar subpattern

TP 301.6

A

1674-4942（2011）02-0151-04

2011-01-23

江西省科技廳科技支撐項目（2009ZDG08400）

黃 瀾