劉永志

1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 210016； 2.宣城職業(yè)技術(shù)學(xué)院 信息工程系,安徽 宣城 242000

基于兩點(diǎn)的時(shí)間序列相似性研究

劉永志1,2

1.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 210016； 2.宣城職業(yè)技術(shù)學(xué)院 信息工程系,安徽 宣城 242000

目前，時(shí)間序列相似性判定大多采用歐式距離和動(dòng)態(tài)時(shí)間彎曲DTW(Dynamic Time Warping)方法，這兩種方法均存在一定缺陷。歐式距離要求序列長度一樣，垂直移動(dòng)序列將影響相似性判定和閾值設(shè)置的經(jīng)驗(yàn)性；動(dòng)態(tài)彎曲距離對歐式距離進(jìn)行了優(yōu)化，避免了歐式長度的一致性，但其他兩個(gè)缺點(diǎn)仍然存在且計(jì)算復(fù)雜度增加。提出了一種新的基于兩點(diǎn)時(shí)間序列相似性算法，可計(jì)算任意兩序列的相似度。首先分析了兩點(diǎn)組成的序列形態(tài)，提出了相似性判定方法TPSS(Two Points Segmentation Similarity)；其次為提高相似性判定的魯棒性，減少人為閾值設(shè)置的影響，對TPSS進(jìn)行了拓展；最后給出了算法及實(shí)驗(yàn)分析。實(shí)驗(yàn)結(jié)果表明，該算法能很好地判定任意序列的相似性，提高了魯棒性及減少人為干預(yù),對數(shù)據(jù)挖掘中的聚類與預(yù)測有很好的幫助作用。

時(shí)間序列；相似性；數(shù)據(jù)挖掘；比值序列

時(shí)間序列是按時(shí)間先后順序排列的數(shù)據(jù)，并保存在介質(zhì)上。它廣泛存在于工業(yè)、農(nóng)業(yè)及商業(yè)等領(lǐng)域，與人們生活息息相關(guān)[1-3]，已引起研究者的廣泛關(guān)注，起初在統(tǒng)計(jì)領(lǐng)域研究頗多，現(xiàn)在亦引起了數(shù)據(jù)挖掘領(lǐng)域的重視。

目前時(shí)間序列相似性研究方法主要有：基于形態(tài)的相似性、基于特征的相似性、基于模型的相似性、基于數(shù)據(jù)壓縮的相似性?；谛螒B(tài)的相似性具有普遍性和實(shí)用性，在滿足一定條件下可以取得與其他3類方法相近的度量結(jié)果。在研究形態(tài)的相似性方面，國內(nèi)外學(xué)者取得了部分成果，比較有代表性的有Keogh等提出的分段累積近似PAA、分段線性表示PLR和符號集合近似SAX等方法[4-5]。在國內(nèi)，梁建海等提出了斜率偏離的方法[6]；張雪麗等提出基于角點(diǎn)相似性的方法[7]；董曉莉等提出了七元模式組合法[8]。這些方法各有特點(diǎn)，為時(shí)間序列相似性研究提供了可以借鑒和參考的方向。

本研究在詳細(xì)分析了兩點(diǎn)組成的基本形態(tài)基礎(chǔ)上，提出一種新的基于兩點(diǎn)的時(shí)間序列相似性算法TPSS。依次連接相鄰兩點(diǎn)，組成最基本的平穩(wěn)序列、上升序列及下降序列，利用基本序列判定定理判別是否相似。TPSS算法僅需一次掃描序列數(shù)據(jù)庫，就可以比較等間隔時(shí)間序列的相似性，并根據(jù)TPSS算法對序列的相似性進(jìn)行計(jì)數(shù)，輸出相似度。此方法屏蔽掉了歐式距離的不能垂直移動(dòng)、序列長度相同及閾值的人為性等缺點(diǎn)，在運(yùn)算效率上優(yōu)于DTW，并克服了DTW閾值的人為性。

1 時(shí)間序列

按照時(shí)間先后順序排列的數(shù)據(jù)稱為時(shí)間序列。時(shí)間序列分為動(dòng)態(tài)時(shí)間序列和靜態(tài)時(shí)間序列，時(shí)間序列有嚴(yán)格的時(shí)間先后順序。時(shí)間序列可以抽象為由一系列二元組組成，記為S={， ，…，，…}, 滿足Ti

由兩點(diǎn)組成的序列稱為基本的時(shí)間序列,如圖1所示。

圖1 基本序列Fig.1 The basic sequence

a:平穩(wěn)序列，序列值波動(dòng)很小的序列。

b:上升序列，序列值處于上升趨勢的序列。

c:下降序列，序列值處于下降趨勢的序列。

時(shí)間序列不管怎樣復(fù)雜多變，都是由這3種基本序列組合而成。

2 時(shí)間序列的相似性

設(shè)有兩個(gè)時(shí)間序列S1和S2，度量時(shí)間序列的函數(shù)sim(S1,S2),當(dāng)sim(S1,S2)≤ε(ε為指定的閾值，下同)，認(rèn)為時(shí)間序列S1和S2滿足以ε為界的相似性。

相似函數(shù)，sim(S1,S2)同時(shí)滿足：

正定性：即sim(S1,S2)≥0，當(dāng)且僅當(dāng)S1=S2時(shí)，sim(S1,S2)=0；

對稱性：sim(S1,S2)=sim(S2,S1)；

三角不等式：有3個(gè)序列S1、S2、S3，有sim(S1,S2)≤sim(S1,S3)+sim(S2,S3)。

時(shí)間序列都是由基本序列組合而成，研究時(shí)間序列的相似性就自然轉(zhuǎn)化為研究基本序列的相似性。

2.1 平穩(wěn)序列

平穩(wěn)序列分為嚴(yán)格的平穩(wěn)序列和非嚴(yán)格的平穩(wěn)序列。嚴(yán)格的平穩(wěn)序列要求序列的值相等，這樣的序列在實(shí)際應(yīng)用中并不常見。

定義1:如果序列的方差σ2小于指定的閾值ε，即滿足σ2<ε，則稱序列為非嚴(yán)格的平穩(wěn)序列。非嚴(yán)格平穩(wěn)序列亦稱為平穩(wěn)序列，平穩(wěn)序列都是相似的。

2.2 上升序列

定義2:序列中的值滿足Di-Di-1>ε,稱序列為上升序列。

定義3:序列中相鄰的值所對應(yīng)的點(diǎn)相連成為折線，如果折線對應(yīng)平行，稱兩序列相似。

如圖2所示，A、B兩折線互相平行，則稱A中的點(diǎn)組成的序列與B中的點(diǎn)組成的序列相似。折線去掉連線僅留節(jié)點(diǎn)成為序列，序列相連成為折線，以后序列與折線不加區(qū)分。

圖2 相似序列Fig.2 Similar sequence

圖3 三平行線間線段Fig.3 The line between three parallel lines

證明:由定義和推論易得出結(jié)論，略。

2.3 下降序列

定義4:序列中的值滿足Di-1-Di>ε，稱序列為下降序列。

證明:由定義和推論易得出結(jié)論，略。

2.4 序列相似性的局限性

滿足定義1、定理1及定理2的時(shí)間序列并不多。它要求序列的長度相同，序列的對應(yīng)比值要小于一個(gè)指定的閾值，這樣人為因素較多，不利于計(jì)算機(jī)的自動(dòng)操作。對于以上的定義及定理必須進(jìn)行相應(yīng)的調(diào)整，以滿足不同序列的相似性比較。

3 時(shí)間序列相似性拓展

對于任意的兩個(gè)時(shí)間序列A和B，其長度分別為m和n，且m≥n，時(shí)間間隔可同或不同。如何判斷A和B的相似性，定義如下方法。

定義6:設(shè)時(shí)間序列A={a1,a2…am}和B={b1,b2,…bn}，長度為|A|=m和|B|=n，且m≥n，其比值序列θ={θ1，θ2，…θn-1}，θ的均值為μ，均方差為σ。如果θi落在95%的置信區(qū)間，即θi∈[μ-1.96σ,μ+1.96σ]，由于比值序列均為正值，也可定義為θi∈[0,μ+1.96σ]，就稱序列B中的bibi+1與序列A相似。

4 算法

輸入:時(shí)間序列A={a1,a2…am}和B={b1,b2,…bn}

輸出:A和B的相似度sim(A,B)。

步驟

(1)求A和B的長度;

(2)計(jì)算A和B的比值序列θ;

(3)按θ的置信區(qū)間計(jì)算A與B的相似點(diǎn)集O;

5 性能分析

為了檢驗(yàn)本文提出的TPSS算法的科學(xué)性與合理性，提出了3套方案來對比相似性度量方法的優(yōu)劣：方案1，用歐式距離計(jì)算時(shí)間序列的相似性；方案2，利用動(dòng)態(tài)彎曲距離DTW計(jì)算時(shí)間序列的相似性；方案3，利用TPSS計(jì)算時(shí)間序列相似性。

實(shí)驗(yàn)環(huán)境為PentiumIV雙核CPU，2GB內(nèi)存和160GB硬盤，MicrosoftWindowsXP操作系統(tǒng)，開發(fā)工具為Java。所用測試數(shù)據(jù)為2012年某城市兩個(gè)生活小區(qū)每天的用水量，每個(gè)小區(qū)的記錄為366個(gè)，共732個(gè)數(shù)據(jù)，如圖4所示，上面的是一個(gè)小區(qū)，下面的是另一個(gè)小區(qū)。

圖4 用水量序列Fig.4 Water consumption series

實(shí)驗(yàn)結(jié)果表明，與歐式距離相比，TPSS算法剔除了歐式距離的不能垂直移動(dòng)，兩個(gè)序列數(shù)據(jù)要相同及閾值的人為性；與DTW相比，TPSS算法降低了運(yùn)算量及閾值的人為性。表明TPSS算法能夠準(zhǔn)確的比較時(shí)間序列的相似性。

6 結(jié) 語

提出了一種基于兩點(diǎn)的時(shí)間序列相似性算法TPSS，即利用兩個(gè)相鄰數(shù)據(jù)組成的基本序列相似性，判斷序列的相似性。TPSS算法如下：掃描一次序列數(shù)據(jù)庫，計(jì)算比值序列θ及置信區(qū)間，進(jìn)而計(jì)算相似度，并確定基本序列是否相似。該算法時(shí)間復(fù)雜度為O(n)(n為兩系列長度較大者)，與歐式距離相同，優(yōu)于DTW。實(shí)驗(yàn)結(jié)果與理論分析表明，TPSS算法能夠?qū)崟r(shí)有效地判斷序列的相似性，并給出相似度。

[1] 賈澎濤,何華燦,劉麗,等.時(shí)間序列數(shù)據(jù)挖掘綜述[J].計(jì)算機(jī)應(yīng)用研究,2007,24(11):15-18.

[2] 萬定生,張奕韜,余宇峰.基于統(tǒng)計(jì)分析的水文時(shí)間序列關(guān)聯(lián)規(guī)則優(yōu)化算法[J].微電子學(xué)與計(jì)算機(jī)，2007,24(10)：126-129.

[3] 郭秀珍,陸建峰,湯九斌.周期性時(shí)間序列數(shù)據(jù)聚類算法的改進(jìn)研究[J].微電子學(xué)與計(jì)算機(jī)，2011,28(10)：118-121.

[4] Keogh E,Lin J,Fu A．HOT SAX：Efficiently Finding the Most Unusual Time Series Subsequence[C]//Proc．of the 5th IEEE Int’l Conf．on Data Mining．Newport Beach，USA：IEEE Press，2005:226-233.

[5] Keogh E, Chakrabarti K, Pazzani M, et al. Dimensionality reduction for fast similarity search in large time series databases[J].Knowledge and information Systems, 2001,3(3):263-286.

[6] 梁建海,張建業(yè).基于斜率偏離的時(shí)間序列相似性搜索方法研究[J].計(jì)算機(jī)應(yīng)用研究,2010,27(1):54-55.

[7] 張雪麗,牛強(qiáng).基于角點(diǎn)彎曲度的時(shí)間序列相似性搜索算法[J].計(jì)算機(jī)工程,2011,37(15):37-40.

[8] 董曉莉,顧成奎,王正歐.基于形態(tài)的時(shí)間序列相似性度量研究[J].電子與信息學(xué)報(bào),2007,29(5):1 228-1 231.

[9] 李正欣,張鳳鳴,李克武.多元時(shí)間序列模式匹配方法研究[J].控制與決策,2011,26(4):565-570.

[10] 李海林,郭崇慧.基于多維形態(tài)特征表示的時(shí)間序列相似性度量[J].系統(tǒng)工程理論與實(shí)踐,2013,33(4):1 024- 1 034.

[11] 朱天,白似雪,王柏,等.基于時(shí)間段的時(shí)序規(guī)則發(fā)現(xiàn)[J].通信學(xué)報(bào),2009,30(8):112-115.

[12] Park S，Kim S W，Chu W W．Segment-based approach for subsequence searches in sequence databases[C]Proceedings of the 16th ACM Symposium on Applied Computing．New York:ACM Press,2001:248-252.

[13] 肖輝，胡運(yùn)發(fā).基于分段時(shí)間彎曲距離的時(shí)間序列挖掘[J].計(jì)算機(jī)研究與發(fā)展，2005,42(1):72-78.

[14] 喻高瞻,彭宏,胡勁松,等.時(shí)間序列數(shù)據(jù)的分段線性表示[J].計(jì)算機(jī)應(yīng)用與軟件,2008,24(12):17-18.

(責(zé)任編輯：李華云)

Research on the Similarity in Time Series Data with Two Points

LIU Yongzhi1,2

1.College of Computer Science and Technology ,Nanjing University of Aeronautics and Astronautics, Nanjing Jiangsu 210016, China; 2.Department of Information Engineering,Xuancheng Vocational & Technical College, Xuancheng Anhui 242000, China

At present, the judgement of the similarity of time series is based on Euclidean distance and DTW(Dynamic Time Warping). These two kinds of methods have some defects. Euclidean distance request the same length of sequence, vertical movement will affect similarity judgment of sequence. Anyone set the threshold of the empirical is difference; DTW is optimized of the Euclidean distance to avoid the consistency of European length. But the other two disadvantages still exist and the computational complexity is increased. This paper proposes a novel similarity algorithm of time series based on the two points, it can calculate any of the two sequence similarity. First, it analyzes the time series form of two points, put forward TPSS method. Secondly, in order to improve the robustness of the similar judgment, reduce the influence of artificial threshold setting, TPSS is developed. Finally, it gives the algorithm and experiment analysis. The experimental results show that tThis algorithm can effectively determine the similarity of arbitrary sequences, improves the robustness and reduces human intervention and can help clustering, prediction in data mining.

Time series; Similarity; Data mining; Two points Ratio series

2014-08-27

安徽省質(zhì)量工程項(xiàng)目(20101452);安徽高?；鹬攸c(diǎn)課題(KJ2014A285)

劉永志(1973-)，女，河南杞縣人，副教授、高工，博士生，主要研究方向?yàn)閿?shù)據(jù)挖掘。

TP391

A

1671-5322(2014)04-0001-04