【摘 要】時(shí)間序列的相似性度量是時(shí)間序列數(shù)據(jù)挖掘的基礎(chǔ)問題，針對(duì)時(shí)間序列相似性度量問題，綜述了現(xiàn)有的時(shí)間序列相似性度量方法，重點(diǎn)介紹了各種度量方法的基本原理、優(yōu)缺點(diǎn)，從而便于研究者對(duì)已有算法進(jìn)行改進(jìn)和研究新的時(shí)間序列相似性度量方法。

【關(guān)鍵詞】時(shí)間序列 數(shù)據(jù)挖掘 相似性 度量

時(shí)間序列的相似性度量是時(shí)間序列數(shù)據(jù)挖掘的基礎(chǔ)問題。兩條完全相同的時(shí)間序列幾乎不存在，因此采用相似性（距離）度量來衡量時(shí)間序列之間的相似性。由于時(shí)間序列數(shù)據(jù)的復(fù)雜性，經(jīng)常發(fā)生振幅平移和伸縮、線性漂移、不連續(xù)性、時(shí)間軸伸縮和彎曲等形變，為了最大程度地支持上述形變，并盡量提高相似性度量的時(shí)間效率，有一系列時(shí)間序列距離度量方法被提出和引入。

一、明科夫斯基距離

明科夫斯基（Minkowski）距離的優(yōu)點(diǎn)在于簡(jiǎn)單直觀，易于計(jì)算。設(shè)兩長(zhǎng)度相等的序列和，把它們看成n維空間中的兩個(gè)坐標(biāo)點(diǎn)，則兩者之間的明科夫斯基距離[2]定義為：

當(dāng)q=1時(shí)為曼哈頓（Manhattan）距離，

當(dāng)q=2時(shí)為歐幾里德（Euclidean）距離，

其中歐幾里德距離是最常用也是應(yīng)用最廣泛的一種距離，其計(jì)算復(fù)雜度不高，與序列長(zhǎng)度成線性關(guān)系，因而具有很好的伸縮性，序列長(zhǎng)度的增加不會(huì)造成計(jì)算復(fù)雜度的迅速提高。并且歐氏距離滿足距離三角不等式，在基于索引的查詢時(shí)，可以利用距離三角不等式快速過濾一些不符合條件的索引節(jié)點(diǎn)。

二、動(dòng)態(tài)時(shí)間彎曲距離

動(dòng)態(tài)時(shí)間彎曲（DTW）距離在語音處理領(lǐng)域得到廣泛的研究，Berndt和Clifford首次將DTW引入到數(shù)據(jù)挖掘領(lǐng)域[3]。與歐幾里德距離相比，動(dòng)態(tài)時(shí)間彎曲距離不要求兩條時(shí)間序列點(diǎn)與點(diǎn)之間一一對(duì)應(yīng)，允許序列點(diǎn)自我復(fù)制在進(jìn)行對(duì)齊匹配。

動(dòng)態(tài)時(shí)間彎曲（DTW）距離：設(shè)時(shí)間序列和，則X和Y的DTW距離定義為：

式中：表示序列點(diǎn)和之間的距離，可以根據(jù)情況選擇不同的距離度量，通常使用明科夫斯基距離。

動(dòng)態(tài)時(shí)間彎曲（DTW）距離的缺點(diǎn)是時(shí)間復(fù)雜度太高（），在子序列匹配時(shí)如不進(jìn)行優(yōu)化甚至為（，L為子序列的長(zhǎng)度），不適用于海量時(shí)間序列的數(shù)據(jù)挖掘，需要專門采用某種技巧來減少其計(jì)算復(fù)雜度。

三、最長(zhǎng)公共子串距離

當(dāng)兩條時(shí)間序列在大部分時(shí)間段具有相似的形態(tài)，而只在很短的時(shí)間范圍內(nèi)發(fā)生劇烈突變或間斷時(shí)（即時(shí)間序列形變中的不連續(xù)性），歐氏距離和動(dòng)態(tài)時(shí)間彎曲距離都忠實(shí)地記錄了該形變的影響，這對(duì)于那些忽略時(shí)間序列不連續(xù)性的相似性度量問題而言是不適用的。

設(shè)時(shí)間序列和，它們滿足以下條件的最長(zhǎng)公共子序列分別為和：1）對(duì)任意，都滿足；2）對(duì)任意，都有。那么時(shí)間序列和之間的相似度定義為：

最長(zhǎng)公共字串（LCS）距離能克服時(shí)間序列的短期突變或間斷帶來的相似性問題，但無法處理振幅平移、時(shí)間軸伸縮和彎曲等形變。

四、結(jié)束語

本文對(duì)現(xiàn)有常用的時(shí)間序列相似性度量方法進(jìn)行綜述，介紹了各種度量方法的基本原理、優(yōu)缺點(diǎn)，從而便于研究者對(duì)已有算法進(jìn)行改進(jìn)和研究新的時(shí)間序列相似性度量方法。

參考文獻(xiàn)：

[1].毛紅保等， 面向相似性查詢的時(shí)間序列距離度量方法述評(píng). 計(jì)算機(jī)工程與設(shè)計(jì)， 2010（19）： 第4221-4224頁.

[2].孫即祥， 現(xiàn)代模式識(shí)別. 2002： 國(guó)防科技大學(xué)出版社.

[3].Berndt， D.J. and J. Clifford， Using dynamic time warping to find patterns in time series. 1994.

[4].Keogh， E. Fast similarity search in the presence of longitudinal scaling in

time series databases. in Tools with Artificial Intelligence， 1997. Proceedings.， Ninth IEEE International Conference on. 1997.

[5].江詩鋒與何振峰， 一種基于權(quán)重的時(shí)間序列相似性度量. 計(jì)算機(jī)應(yīng)用與軟件， 2010（9）： 第116-118頁.

[6].邵校莎莎等， 不同粒度時(shí)間序列相似性度量. 計(jì)算機(jī)應(yīng)用， 2011（12）： 第3285-3287頁.

[7].孫達(dá)辰， 孫迎燕與周廣群， 不等長(zhǎng)子時(shí)間序列的相似性度量方法. 計(jì)算機(jī)時(shí)代， 2011（5）： 第17-20頁.

[8].丁永偉等， 基于弧度距離的時(shí)間序列相似度量. 電子與信息學(xué)報(bào)， 2011（1）： 第122-128頁.

[9].馮玉才等， 高效時(shí)序相似搜索技術(shù). 計(jì)算機(jī)學(xué)報(bào)， 2009（11）： 第2107-2122頁.

作者簡(jiǎn)介：孫建樂（1989-），男，河南，碩士研究生，主要研究方向：智能信息處理；廖清科（1990-），男，重慶，碩士研究生，主要研究方向：智能信息處理