# Generalized Framework for Similarity Measure of Time Series

Authors: Hongsheng Yin; Honggang Qi; Jingwen Xu; William N. N. Hung; Xiaoyu Song
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Currently, there is no definitive and uniform description for the similarity of time series, which results in difficulties for relevant research on this topic. In this paper, we propose a generalized framework to measure the similarity of time series. In this generalized framework, whether the time series is univariable or multivariable, and linear transformed or nonlinear transformed, the similarity of time series is uniformly defined using norms of vectors or matrices. The definitions of the similarity of time series in the original space and the transformed space are proved to be equivalent. Furthermore, we also extend the theory on similarity of univariable time series to multivariable time series. We present some experimental results on published time series datasets tested with the proposed similarity measure function of time series. Through the proofs and experiments, it can be claimed that the similarity measure functions of linear multivariable time series based on the norm distance of covariance matrix and nonlinear multivariable time series based on kernel function are reasonable and practical.


---

## Body

## 1. Introduction

A complex system typically needs to be described with multiple state variables. These state variables can be obtained by experimental observations and instrumental measures. With these state variables, a set of discrete multivariate time series (MTS) can be constructed. Mathematically, MTS is expressed in matrix formX=(X1,X2,…,Xm). Its samples are xi(t), xi(i=1,2,…,m; t=1,2,…,n), where m and n denote the number of observation variables and the number of observation samples of each observation variable, respectively. Obviously, X is a n×m matrix. If m≥2, the matrix X represents MTS. Otherwise, if m=1, X is simplified to a univariate time series (UTS), which is a special case of MTS and can be denoted as a n-dimensional vector x(n). Time series theory is widely applied in various fields such as electricity, finance, medical, multimedia, meteorology and hydrology, scientific research, and industrial control. Discovery of the hidden information and operating regularity in a time series is a research hotpot in data mining and knowledge discovery. The research on time series includes clustering, classification, similarity search, feature extraction, trend forecasting, and decision support. Similarity measures a fundamental research topic on time series theory.Most of the existing research on the similarity measure of time series is focused on UTS. The common measure functions areLp-norms (p=1,2,∞) [1, 2], DTW [3–5], longest common subsequence (LCSS) [6], edit distance on real sequence (EDR) [7], edit distance with real penalty (ERP) [8], spatial assemble distance (SpADe) [9], DISSIM [10], swale [11], and TQuEST [12]. With further research on UTS, we can expect more new methods will be proposed in the future. However, few researches focus on the similarity measure of MTS. Yang and Shahabi [13, 14] calculated the similarity of MTS with the extended Frobenius norm. Xu et al. [15, 16] measured the MTS similarity based on information theoretic learning framework.The contributions in the research on framework for similarity measure of time series are also less. Liu and Jiang [17] proposed a concept of similarity of time series through analyzing the geometric relation of Euclidean distance of time series in high-dimensional space, which describes the similarity relation between two UTS using both similarity function and transform constraint function to establish an exact concept for similarity of time series.From existing UTS and MTS literatures, the similarity measure methods of time series are undefined and nonstandardized which makes the research very difficult. Thus, it is very necessary to establish a general concept for uniform similarity of time series. In this paper, we give the definition of similarity measure function of UTS with vector norm and proved that the similarity functions defined in the form of norms are equivalent in original UTS space and linear transformed space. Moreover, we also extend the definitions of similarity of time series and present a uniform theory of similarity measure based on set theory, metric space theory, operator theory, matrix theory, and kernel method. The uniform theory based on distance of vector/matrix norm can be used for measuring the similarity of time series in both original and transformed spaces, whether the time series are univariable or multivariable and the linear transform or the nonlinear transform. The theory analysis and experimental results show that the definition of distance of vector/matrix norm is equivalent in original and transformed spaces.The rest of this paper is organized as follows. In Section2, it is proved that the vector norm based definitions of similarity functions are equivalent in UTS original and linear transformed spaces. In Section 3, the theory that matrix norm is used for defining the similarity function of linear MTS is discussed. Then, the theory that kernel function is used for defining the similarity function of nonlinear MTS is discussed in Section 4. In Section 5, all similarity functions proposed in this paper are discussed and analyzed. It is proved that the norm based definition of similarity functions for measuring the similarity of UTS is equivalent in time domain and Fourier transform or wavelet transform domain. Also, the similarity function of linear MTS defined based on covariance matrix norm distance and the similarity function of nonlinear MTS defined based on kernel function are analyzed in this section. The experimental results are shown in Section 6. Finally, we conclude this paper in Section 7.


## 2. Similarity Measure of Linear Univariable Time Series

For the original data of linear univariable time series, whether they are recoded manually or sampled automatically, it is assumed that they all satisfy Shannon theorem of information theory without any distortion and without considering the data dimension. The linear univariable time series is denoted as setA. Considering two UTS samples x,y∈A, wherein x is the time series to be observed (observed time series) and y is the time series to be referenced (referenced time series). They are represented in vector form X=(X1,X2,…,Xm), Y=(Y1,Y2,…,Ym), m≥n. To measure the similarity of x and y, the subseries with the same dimension as y needs to be extracted from x. All n-dimension successive subseries of x compose a set B, B=(Xi,Xi+1,…,Xi+n-1∣i=1,2,…,m-n+1), in which each element represents a n-dimension successive time series. The ith element in set B is denoted as xi(b), xi(b)=(Xi,Xi+1,…,Xi+n-1), which is a n-dimension vector.The similarity measure between observed time seriesx and referenced time series y is that the subseries of x,xi(b),∀xi(b)∈B, and the given referenced series y are measured in the similarity measure function Sim=f(xi(b),y) with the threshold ɛ>0.Definition 1.
If the similarity function of time seriesSim=f(xi(b),y)≤ɛ, the observed subseries xi(b) and referenced series y are similar.According to the literatures [1, 2], there are two cases of time series similarities, which are as follows: (1) if m=n and Sim=f(xi(b),y)≤ɛ, x and y are exactly matching; (2) if m>n, ∃xi(b)∈B, and Sim=f(xi(b),y)≤ɛ, the subseries xi(b) and y are subseries matching. Obviously, exactly matching is a special case of subseries matching. In this paper, subseries xi(b) and similarity measure function Sim=f(xi(b),y) are defined for unifying the above two cases of similarity matching of time series and measuring the similarity of xi(b) and y in the same dimension conveniently. The following definitions on similarity of UTS are all based on the unified similarity.


### 2.1. Common Similarity Measure Functions

In current research, the distance function of time seriesxi(b) and y, d(xi(b),y), is commonly used as the similarity measure function Sim=f(xi(b),y). The common distance metrics are as follows [17].(
1
) Euclidean distance:
(1)Sim=fxib,y=dxib,y=∑k=1n‍xikb-yk21/2.(
2
) City-block distance:
(2)Sim=fxib,y=dxib,y=∑k=1n‍xikb-yk.(
3
) Chebyshev distance:
(3)Sim=fxib,y=dxib,y=∑k‍xikb-yk.(
4
) Minkowski distance:
(4)Sim=fxib,y=dxib,y=∑k=1n‍xikb-ykp1/p.(
5
) Cosine distance:
(5)Sim=fxib,y=dxib,y=1-∑k=1nxikb-yk∑k=1nxikb2∑k=1nyk2.(
6
) Correlation distance:
(6)Sim=fxib,y=dxib,y=1-∑k=1n‍yikb-1n∑k=1n‍yikb2-1∑k=1n‍xikb-1n∑k=1n‍xikbyikb-1n∑k=1n‍yikb×∑k=1n‍xikb-1n∑k=1n‍xikb2∑k=1n‍yikb-1n∑k=1n‍yikb2-1.(
7
) Mahalanobis distance
(7)Sim=fxib,y=dxib,y=xkb-yV-1xkb-yT1/2.
In formula (7), matrix V is the covariance matrix of xi(b) and y. Mathematically, it can be proved that the distance formulas (1)–(3) are special cases of formula (4) with p=2,1,∞. In these distance functions, the Euclidean distance is frequently used in practice. Obviously, given the same dimension, the more the similarity between two vectors, the smaller the values of similarity measure functions (1)–(7), and vice versa.


### 2.2. Relevant Concepts of Time Series Transform

Since time seriesxi(b) and y are high-dimension data, xi(b),y∈X⊂Rn, straightforward analysis and processing of similarity of time series need huge computation burden which is unacceptable on both time and space complexities. Although measuring the similarity of two time series is intuitively straightforward, the result may be not very accurate. Thus, the time series xi(b) and y need to be properly transformed. The transformed time series are denoted as xi(b) and y′, and X′ denotes the transformed space, xib′,y′∈X′⊂Rn, and their transform factor is T. The transform should be lossless or lossy within a very small margin so that no or less accuracy loss of data is introduced by the transform. Through the space transform, the dimension of data is greatly reduced so that the data can be processed with lower complexity. Accordingly, it is very important to select a proper transform for solving this problem. For notational convenience the relevant definition is given as follows.Definition 2.
Let(X,ρ) and (X′,ρ′) be two measure spaces. If there exists a mapping T from X to X′, and ∀x,y∈X, ρ′(Tx,Ty)=ρ(x,y), then it can be said that X and X′ are isometric, and T is the isometric mapping from X to X′.Definition 3.
LetT be an operator (mapping) of the normed linear space from X to X′. If the following hold:(1)
additiveT(x+y)=Tx+Ty(x,y∈X),(2)
homogeneityT(αx)=αTx,then it can be said that T is a linear operator from X to X′.Definition 4.
S
(
X
,
X
′
) represents the all bounded linear operators of the normed linear space from X to X′. Let T,T1∈S(X,X′) and let α be arbitrary number. If ∀x∈X and the following hold:(1)
additive(T1+T)x=T1x+Tx,(2)
homogeneity(αT)x=α(Tx),then it can be said that S(X,X′) is a linear space.Definition 5.
LetX and X′ be two normed linear spaces and let T∈S(X,X′) be the linear operator from X to X′. If x=Tx′ and ∀x∈X, then it can be said that X and X′ are isometric and T is the norm preserving isomorphic mapping from X to X′.


### 2.3. Definition of Similarity Relation in Set Theory

Definition 6.
LetR be a relation in set A. If  ∀x∈A and (x,x)∈R, then it can be said that relation R is reflexive. If ∀x,y∈A, (x,y)∈R, and (y,x)∈R, then it can be said that relation R is symmetrical. If ∀x,y,z∈A, (x,y)∈R, (y,z)∈R, and there is (x,z)∈R, then it is said that relation R is transitive. If a relation R is both reflexive and symmetrical, it is a similarity relation.It should be noted that the similarity relation does not have the transitive property. For example, father and son are similar, and mother and son are also similar, but father and mother are very possible to be dissimilar. According to the above analysis of similarity of time series, the similarity measure functions are proposed based on the similarity relation of set theory.


### 2.4. Extended Similarity Definition of Time Series

According to the above discussion, the similarity measure function of time series not only satisfies the similarity relation in set theory, but also should be uniformed in the original spaceX and the transformed space X′. Objectively, the straightforward similarity measure of two time series is more accurate than nonstraightforward similarity measure in which the geometric triangle inequality is used for the similarity measure through the third-party time series. Thus, Definition 1 is extended as follows.Definition 7.
Given a linear operatorT from X to X′ and xi(b),y,z∈X⊂Rn, xib′,y′,z′∈X′⊂Rn are the transforms of xi(b),y,z by the operator T. When the similarity measure function Sim=f(*,*)≤ɛ (ɛ>0 is a given threshold of similarity), the time series xi(b),y are similar in the constraints of ɛ. Meanwhile, the similarity function Sim=f(*,*) should satisfy the following.(1)
Reflexive symmetrical positive definiteness, that is,Sim=f(xib,y)=f(y,xib)=f(xib′,y′)=f(y′,xib′)≥0, if and only if xi(b)=y, xi(b′)=y′, and the equation Sim=0 holds.(2)
Geometric triangle inequality:
fxib,z≤fxib,y+fy,z,f(xib′,z′)≤f(xib′,y′)+f(y′,z′).
The generalized similarity definition in different spaces is given by Definition7. The key problem is how to find the proper operator T and similarity measure function Sim=f(*,*).Lemma 8.
Any two norms of finite-dimension linear space are equivalent.Proof.
Letx1 and x2 be two norms of linear space X and let {e1,e2,…,en} be a linear basis of X. If ∀x∈X and x=∑k=1n‍akek, then there are positive integers A1,A2,B1,B2, which satisfy A1x1≤∑k=1n‍ak21/2≤B1x1 and A2x2≤∑k=1n‍ak21/2≤B2x2. Thus, A1x1≤B2x2≤(B1B2/A2)x1; that is, (A1/B2)x1≤x2≤(B1/A2)x1. Finally, it can be proved that x1 and x2 are equivalent.Theorem 9.
LetT be the norm preserving isomorphic mapping from X to X′. The time series xi(b),y∈X⊂Rn are transformed as xib′,y′∈X′⊂Rn by T. X has the usual definition of the norm ∥·∥, with which the distance (X,ρ) can be derived by the norm. Similarly, the distance (X′,ρ′) also can be derived by the norm ·. Then, consider the following. (1)
In spaceX, formulae (1), (2), (3), and (4) represent that the similarity measure function Sim=f(xi(b),y) is equivalent.(2)
In spacesX and X′, the similarity measure functions Sim=f(*,*) represented by xi(b)-y and xib′-y′ are equivalent.Proof.
(
1
) Since formulae (1), (2), (3), and (4) are 2-norm, 1-norm, ∞-norm, and p-norm of the vector difference, respectively, according to Lemma 8, formulae (1), (2), (3), and (4) can be easily proved by norm axioms that they satisfy Definition 7. Thereby it is proved.
(
2
) It may be known from Definitions 3 and 5 that xi(b)-y=(xi(b)-y)=Txib-Ty′=xib′-y′, and then it is easily proved by norm axioms that they satisfy Definition 7.


## 2.1. Common Similarity Measure Functions

In current research, the distance function of time seriesxi(b) and y, d(xi(b),y), is commonly used as the similarity measure function Sim=f(xi(b),y). The common distance metrics are as follows [17].(
1
) Euclidean distance:
(1)Sim=fxib,y=dxib,y=∑k=1n‍xikb-yk21/2.(
2
) City-block distance:
(2)Sim=fxib,y=dxib,y=∑k=1n‍xikb-yk.(
3
) Chebyshev distance:
(3)Sim=fxib,y=dxib,y=∑k‍xikb-yk.(
4
) Minkowski distance:
(4)Sim=fxib,y=dxib,y=∑k=1n‍xikb-ykp1/p.(
5
) Cosine distance:
(5)Sim=fxib,y=dxib,y=1-∑k=1nxikb-yk∑k=1nxikb2∑k=1nyk2.(
6
) Correlation distance:
(6)Sim=fxib,y=dxib,y=1-∑k=1n‍yikb-1n∑k=1n‍yikb2-1∑k=1n‍xikb-1n∑k=1n‍xikbyikb-1n∑k=1n‍yikb×∑k=1n‍xikb-1n∑k=1n‍xikb2∑k=1n‍yikb-1n∑k=1n‍yikb2-1.(
7
) Mahalanobis distance
(7)Sim=fxib,y=dxib,y=xkb-yV-1xkb-yT1/2.
In formula (7), matrix V is the covariance matrix of xi(b) and y. Mathematically, it can be proved that the distance formulas (1)–(3) are special cases of formula (4) with p=2,1,∞. In these distance functions, the Euclidean distance is frequently used in practice. Obviously, given the same dimension, the more the similarity between two vectors, the smaller the values of similarity measure functions (1)–(7), and vice versa.


## 2.2. Relevant Concepts of Time Series Transform

Since time seriesxi(b) and y are high-dimension data, xi(b),y∈X⊂Rn, straightforward analysis and processing of similarity of time series need huge computation burden which is unacceptable on both time and space complexities. Although measuring the similarity of two time series is intuitively straightforward, the result may be not very accurate. Thus, the time series xi(b) and y need to be properly transformed. The transformed time series are denoted as xi(b) and y′, and X′ denotes the transformed space, xib′,y′∈X′⊂Rn, and their transform factor is T. The transform should be lossless or lossy within a very small margin so that no or less accuracy loss of data is introduced by the transform. Through the space transform, the dimension of data is greatly reduced so that the data can be processed with lower complexity. Accordingly, it is very important to select a proper transform for solving this problem. For notational convenience the relevant definition is given as follows.Definition 2.
Let(X,ρ) and (X′,ρ′) be two measure spaces. If there exists a mapping T from X to X′, and ∀x,y∈X, ρ′(Tx,Ty)=ρ(x,y), then it can be said that X and X′ are isometric, and T is the isometric mapping from X to X′.Definition 3.
LetT be an operator (mapping) of the normed linear space from X to X′. If the following hold:(1)
additiveT(x+y)=Tx+Ty(x,y∈X),(2)
homogeneityT(αx)=αTx,then it can be said that T is a linear operator from X to X′.Definition 4.
S
(
X
,
X
′
) represents the all bounded linear operators of the normed linear space from X to X′. Let T,T1∈S(X,X′) and let α be arbitrary number. If ∀x∈X and the following hold:(1)
additive(T1+T)x=T1x+Tx,(2)
homogeneity(αT)x=α(Tx),then it can be said that S(X,X′) is a linear space.Definition 5.
LetX and X′ be two normed linear spaces and let T∈S(X,X′) be the linear operator from X to X′. If x=Tx′ and ∀x∈X, then it can be said that X and X′ are isometric and T is the norm preserving isomorphic mapping from X to X′.


## 2.3. Definition of Similarity Relation in Set Theory

Definition 6.
LetR be a relation in set A. If  ∀x∈A and (x,x)∈R, then it can be said that relation R is reflexive. If ∀x,y∈A, (x,y)∈R, and (y,x)∈R, then it can be said that relation R is symmetrical. If ∀x,y,z∈A, (x,y)∈R, (y,z)∈R, and there is (x,z)∈R, then it is said that relation R is transitive. If a relation R is both reflexive and symmetrical, it is a similarity relation.It should be noted that the similarity relation does not have the transitive property. For example, father and son are similar, and mother and son are also similar, but father and mother are very possible to be dissimilar. According to the above analysis of similarity of time series, the similarity measure functions are proposed based on the similarity relation of set theory.


## 2.4. Extended Similarity Definition of Time Series

According to the above discussion, the similarity measure function of time series not only satisfies the similarity relation in set theory, but also should be uniformed in the original spaceX and the transformed space X′. Objectively, the straightforward similarity measure of two time series is more accurate than nonstraightforward similarity measure in which the geometric triangle inequality is used for the similarity measure through the third-party time series. Thus, Definition 1 is extended as follows.Definition 7.
Given a linear operatorT from X to X′ and xi(b),y,z∈X⊂Rn, xib′,y′,z′∈X′⊂Rn are the transforms of xi(b),y,z by the operator T. When the similarity measure function Sim=f(*,*)≤ɛ (ɛ>0 is a given threshold of similarity), the time series xi(b),y are similar in the constraints of ɛ. Meanwhile, the similarity function Sim=f(*,*) should satisfy the following.(1)
Reflexive symmetrical positive definiteness, that is,Sim=f(xib,y)=f(y,xib)=f(xib′,y′)=f(y′,xib′)≥0, if and only if xi(b)=y, xi(b′)=y′, and the equation Sim=0 holds.(2)
Geometric triangle inequality:
fxib,z≤fxib,y+fy,z,f(xib′,z′)≤f(xib′,y′)+f(y′,z′).
The generalized similarity definition in different spaces is given by Definition7. The key problem is how to find the proper operator T and similarity measure function Sim=f(*,*).Lemma 8.
Any two norms of finite-dimension linear space are equivalent.Proof.
Letx1 and x2 be two norms of linear space X and let {e1,e2,…,en} be a linear basis of X. If ∀x∈X and x=∑k=1n‍akek, then there are positive integers A1,A2,B1,B2, which satisfy A1x1≤∑k=1n‍ak21/2≤B1x1 and A2x2≤∑k=1n‍ak21/2≤B2x2. Thus, A1x1≤B2x2≤(B1B2/A2)x1; that is, (A1/B2)x1≤x2≤(B1/A2)x1. Finally, it can be proved that x1 and x2 are equivalent.Theorem 9.
LetT be the norm preserving isomorphic mapping from X to X′. The time series xi(b),y∈X⊂Rn are transformed as xib′,y′∈X′⊂Rn by T. X has the usual definition of the norm ∥·∥, with which the distance (X,ρ) can be derived by the norm. Similarly, the distance (X′,ρ′) also can be derived by the norm ·. Then, consider the following. (1)
In spaceX, formulae (1), (2), (3), and (4) represent that the similarity measure function Sim=f(xi(b),y) is equivalent.(2)
In spacesX and X′, the similarity measure functions Sim=f(*,*) represented by xi(b)-y and xib′-y′ are equivalent.Proof.
(
1
) Since formulae (1), (2), (3), and (4) are 2-norm, 1-norm, ∞-norm, and p-norm of the vector difference, respectively, according to Lemma 8, formulae (1), (2), (3), and (4) can be easily proved by norm axioms that they satisfy Definition 7. Thereby it is proved.
(
2
) It may be known from Definitions 3 and 5 that xi(b)-y=(xi(b)-y)=Txib-Ty′=xib′-y′, and then it is easily proved by norm axioms that they satisfy Definition 7.


## 3. Similarity Measure of Linear Multivariable Time Series

In previous sections, we mentioned the definitions of similarity of univariable time series. The signal variable time series is represented in vector form mathematically. The more similar the two vectors, the shorter the distance between them. The distance of two identical vectors should be zero. Thus, the similarity function of univariable time series should be defined based on vector norm. Multivariable time series is represented in matrix mathematically. So, the similarity function of multivariable time series should be defined based on matrix norm.Definition 10.
Matrix norms: if the real functionf(A)=A, where A is any matrix A∈Rm×n, satisfies the following:(1)
positive definiteness:A≥0 and A=0, if and only if A=0,(2)
homogeneity: for any real numberα, αA=αA,(3)
triangle inequality: for∀A∈Rm×n, A+B≤A+B,(4)
compatibility: for∀A∈Rm×n, AB≤A·B,then it is said that A is a matrix norm in Rm×n, that is, the norm of matrix A.


### 3.1. Commonly Used Matrix Norm

The commonly used matrix norms are given as follows:(1)
A1=max⁡1≤j≤n∑i=1m‍aij, the maximum sum of absolute element of each column of matrix A, and A1 is also called the column norm of A;(2)
A∞=max⁡1≤i≤m∑j=1n‍aij, the maximum sum of absolute element of each row of matrix A, and A∞ is also called the row norm of A;(3)
A2=λmax⁡(ATA), wherein AT denotes matrix transpose of A and λmax⁡(ATA) is the maximum of absolute eigenvalue of ATA, and A2 is also called the 2-norm of A, or spectral norm;(4)
AF=∑i=1m‍∑j=1n‍aij21/2=[tr⁡(AHA)]1/2, wherein AH is conjugate transpose of A. AF is called the Frobenius norm (F-norm), which is similar to 2-norm in the form of vector, and also is compatible with the vector norm x2. Its advantage in the norm invariance after F-norm is multiplied by unitary matrix, that is, the following theorem.Theorem 11.
LetA∈Rn×m and U,V be m-rank and n-rank unitary matrices, respectively, and then UAF2=AF2=AVF2.Proof.
U
A
F
2
=
t
r
[
(
U
A
)
H
(
U
A
)
]
=
t
r
[
A
H
U
H
U
A
]
=
t
r
[
A
H
A
]
=
A
F
2. According to definition, we know that AF=AHF. With the above results, we have AVF2=AVHF2=VHAHF2=AHF2=AF2.
Same as vector norm, the equivalence of matrix norms has the following similar conclusions. For∀A∈Rn×m, any matrix norms of A are equivalent. Mathematically, in the above four kinds of norms, A1 and A∞ can be easily computed, and A2 and A1 have better properties and are widely applied. However, A2 is more complicated in engineering application and sensitive to the variation of matrix elements. AF can be computed more easily and thus is widely applied.


### 3.2. Definition of Similarity Functions of Multiple Variable Time Series

It is assumed thatX=(X1,X2,…,Xm) and Y=(Y1,Y2,…,Ym) are MTS, their samples are denoted as xi(t), yi(t), (i=1,2,…,m; t=1,2,…,n), m is the number of observations, and n is the size of observations. Obviously, they are n×m matrices, which are denoted as A(n×m) and B(n×m). Their definition of similarity function is as follows:
(8)Sim=fX,Y=A-B.


## 3.1. Commonly Used Matrix Norm

The commonly used matrix norms are given as follows:(1)
A1=max⁡1≤j≤n∑i=1m‍aij, the maximum sum of absolute element of each column of matrix A, and A1 is also called the column norm of A;(2)
A∞=max⁡1≤i≤m∑j=1n‍aij, the maximum sum of absolute element of each row of matrix A, and A∞ is also called the row norm of A;(3)
A2=λmax⁡(ATA), wherein AT denotes matrix transpose of A and λmax⁡(ATA) is the maximum of absolute eigenvalue of ATA, and A2 is also called the 2-norm of A, or spectral norm;(4)
AF=∑i=1m‍∑j=1n‍aij21/2=[tr⁡(AHA)]1/2, wherein AH is conjugate transpose of A. AF is called the Frobenius norm (F-norm), which is similar to 2-norm in the form of vector, and also is compatible with the vector norm x2. Its advantage in the norm invariance after F-norm is multiplied by unitary matrix, that is, the following theorem.Theorem 11.
LetA∈Rn×m and U,V be m-rank and n-rank unitary matrices, respectively, and then UAF2=AF2=AVF2.Proof.
U
A
F
2
=
t
r
[
(
U
A
)
H
(
U
A
)
]
=
t
r
[
A
H
U
H
U
A
]
=
t
r
[
A
H
A
]
=
A
F
2. According to definition, we know that AF=AHF. With the above results, we have AVF2=AVHF2=VHAHF2=AHF2=AF2.
Same as vector norm, the equivalence of matrix norms has the following similar conclusions. For∀A∈Rn×m, any matrix norms of A are equivalent. Mathematically, in the above four kinds of norms, A1 and A∞ can be easily computed, and A2 and A1 have better properties and are widely applied. However, A2 is more complicated in engineering application and sensitive to the variation of matrix elements. AF can be computed more easily and thus is widely applied.


## 3.2. Definition of Similarity Functions of Multiple Variable Time Series

It is assumed thatX=(X1,X2,…,Xm) and Y=(Y1,Y2,…,Ym) are MTS, their samples are denoted as xi(t), yi(t), (i=1,2,…,m; t=1,2,…,n), m is the number of observations, and n is the size of observations. Obviously, they are n×m matrices, which are denoted as A(n×m) and B(n×m). Their definition of similarity function is as follows:
(8)Sim=fX,Y=A-B.


## 4. Similarity Measure of Nonlinear Time Series

We are inspired by support vector machines (SVMs), where a classifier can convert the difficult nonlinear classification problem in input spaceX⊂Rm into simple linear classification problem in feature space Hk using kernel method. The essence is that the difficult classification of unclear similarity of the same class of samples and small difference of different classes of samples are converted from the input space into the feature space Hk in which the similarity of the same class of samples is enhanced and the difference of different classes of samples is enlarged. Thus, in this paper, the kernel method is introduced for the research of the similarity of nonlinear time series.In input spaceX⊂Rm, the researching time series X=(x1,x2,…,xm) is a m-dimension multivariable with n samples, and same as the researching series, the reference time series Y=(y1,y2,…,ym) is a m-dimension multivariable with n samples. In the feature space Hk, the nonlinear mapping of X and Y is denoted as Φ(X)=(Φ(x1),Φ(x2),…,Φ(xm)) and Φ(Y)=(Φ(y1),Φ(y2),…,Φ(ym)).Definition 12.
In the feature spaceHk, the inner product and norm are defined as follows:
(9)ΦX,ΦY=∑i=1n‍ΦxiΦyi,(10)ΦX2=ΦX,ΦY1/2=∑i=1n‍Φxi21/2.Definition 13.
The similarity function of the researching seriesX=(x1,x2,…,xm) and the reference time series Y=(y1,y2,…,ym) are defined as follows:
(11)Sim=fX,Y=ΦX-ΦY2.


## 5. Discussion and Analysis

### 5.1. Analysis on the Similarity of Linear Transformed Univariable Time Series

According to operator theory, both Fourier transform and wavelet transform are linear operators. Thus, the relevant conclusions on the similarity of time series based on Fourier transform and wavelet transform are obtained as follows.Lemma 14.
Letf,g∈L2(Rn), and then Fourier transforms of f and g, f^(ω),g^(ω)∈L2(Rn), have the following properties:(1)
invariant inner product(f^,g^)=(f,g),(2)
norm preservingf^=f.Proof.
Consider the following:
(
1
)
(12)
f
,
g
=
∫
-
∞
∞
‍
f
*
t
g
t
d
t
=
∫
-
∞
∞
‍
f
*
t
∫
-
∞
∞
‍
g
ω
^
exp
⁡
j
ω
t
d
ω
d
t
=
∫
-
∞
∞
‍
g
ω
^
f
*
t
exp
⁡
j
ω
t
d
t
d
ω
=
∫
-
∞
∞
‍
g
ω
^
f
t
exp
⁡
-
j
ω
t
d
t
*
d
ω
=
∫
-
∞
∞
‍
g
ω
^
f
ω
^
*
d
ω
=
f
^
,
g
^
.
(
2
) For the above equation, let f=g, and then there is f^=(f^,f^)=(f,f)=f.Inference 1. Time series xi(b),y∈X⊂Rn are transformed as xib′,y′∈X′ by discrete Fourier transform (DFT). The similarity functions Sim=f(*,*) is represented by norms xi(b)-y and xib′-y′ are equivalent.Proof.
According to Theorem9 and Lemma 14, the results are directly deduced.Analogously, the following conclusions are also obtained. Due to the limited space, the proof is not presented here.Inference 2. Time series xi(b),y∈X⊂Rn are transformed as xib′,y′∈X′ by discrete wavelet transform (DWT). The similarity function Sim=f(*,*) represented by norms xi(b)-y and xib′-y′ is equivalent.


### 5.2. Practice Computing Method of Similarity of Linear Multivariable Time Series

Let matricesAn×m and Bn×m represent MTS X=(x1,x2,…,xm) and Y=(y1,y2,…,ym), and let the covariance matrices between the columns in An×m and Bn×m be COV(A)m×m and COV(B)m×m. All eigenvalues of covariance matrices COV(A)m×m are arranged in descending order λα1,λα2,…,λαm and their corresponding standard orthogonal eigenvectors are α1,α2,…,αm. Similarly, all eigenvalues of covariance matrices COV(B)m×m are arranged in descending order λβ1,λβ2,…,λβm, and the corresponding standard orthogonal eigenvectors are β1,β2,…,βm. Thus, the eigenvectors of covariance matrices COV(A)m×m and COV(B)m×m are α=[α1,α2,…,αm] and β=[β1,β2,…,βm], respectively, and then their extended similarity function is defined as follows:
(13)Sim=fX,Y=α-β.According to principle component analysis, physical meaning of formula (13) is equivalent to that the distance (similarity) between the linear orthogonal transforms of An×m and Bn×m can be measured using the norms in the transformed space. Yang and Shahabi [13, 14] use the extended Frobenius norm to compute the similarity of MTS which is a special case of formula (13). Formula (13) can be understood by referring to the definition of similarity function of univariable time series transformed by linear operator.


### 5.3. Practical Computation of Similarity of Nonlinear Multivariable Time Series

Mathematically, it is not difficult to prove that the norm of formula (10) derived by the inner product of formula (9) satisfies the Parallelogram formula: ΦX+ΦY2+ΦX-ΦY2=2(ΦX2+ΦY2). Since ΦX-ΦY22=Φ(X),Φ(X)-2Φ(X),Φ(Y)+Φ(Y),Φ(Y), it does not need to know the mapping function explicitly. Instead, the kernel function K(x,y) is used to compute the similarity function defined in formula (11); that is,
(14)Sim=fX,Y=Kx,x-2Kx,y+Ky,y.Formula (14) shows that the nonlinear similarity measure of nonlinear time series in input space can be linearly measured in feature space through kernel method. Currently, commonly used kernel functions are as follows:(1)
linear kernel function:(15)Kx,y=xy,(2)
p-order polynomial kernel function:
(16)Kx,y=xy+1p,(3)
Gaussian radial basis RBF kernel function:(17)Kx,y=exp⁡-x-y22σ2,(4)
neural network kernel function:(18)Kx,y=tanhvxy+c.


## 5.1. Analysis on the Similarity of Linear Transformed Univariable Time Series

According to operator theory, both Fourier transform and wavelet transform are linear operators. Thus, the relevant conclusions on the similarity of time series based on Fourier transform and wavelet transform are obtained as follows.Lemma 14.
Letf,g∈L2(Rn), and then Fourier transforms of f and g, f^(ω),g^(ω)∈L2(Rn), have the following properties:(1)
invariant inner product(f^,g^)=(f,g),(2)
norm preservingf^=f.Proof.
Consider the following:
(
1
)
(12)
f
,
g
=
∫
-
∞
∞
‍
f
*
t
g
t
d
t
=
∫
-
∞
∞
‍
f
*
t
∫
-
∞
∞
‍
g
ω
^
exp
⁡
j
ω
t
d
ω
d
t
=
∫
-
∞
∞
‍
g
ω
^
f
*
t
exp
⁡
j
ω
t
d
t
d
ω
=
∫
-
∞
∞
‍
g
ω
^
f
t
exp
⁡
-
j
ω
t
d
t
*
d
ω
=
∫
-
∞
∞
‍
g
ω
^
f
ω
^
*
d
ω
=
f
^
,
g
^
.
(
2
) For the above equation, let f=g, and then there is f^=(f^,f^)=(f,f)=f.Inference 1. Time series xi(b),y∈X⊂Rn are transformed as xib′,y′∈X′ by discrete Fourier transform (DFT). The similarity functions Sim=f(*,*) is represented by norms xi(b)-y and xib′-y′ are equivalent.Proof.
According to Theorem9 and Lemma 14, the results are directly deduced.Analogously, the following conclusions are also obtained. Due to the limited space, the proof is not presented here.Inference 2. Time series xi(b),y∈X⊂Rn are transformed as xib′,y′∈X′ by discrete wavelet transform (DWT). The similarity function Sim=f(*,*) represented by norms xi(b)-y and xib′-y′ is equivalent.


## 5.2. Practice Computing Method of Similarity of Linear Multivariable Time Series

Let matricesAn×m and Bn×m represent MTS X=(x1,x2,…,xm) and Y=(y1,y2,…,ym), and let the covariance matrices between the columns in An×m and Bn×m be COV(A)m×m and COV(B)m×m. All eigenvalues of covariance matrices COV(A)m×m are arranged in descending order λα1,λα2,…,λαm and their corresponding standard orthogonal eigenvectors are α1,α2,…,αm. Similarly, all eigenvalues of covariance matrices COV(B)m×m are arranged in descending order λβ1,λβ2,…,λβm, and the corresponding standard orthogonal eigenvectors are β1,β2,…,βm. Thus, the eigenvectors of covariance matrices COV(A)m×m and COV(B)m×m are α=[α1,α2,…,αm] and β=[β1,β2,…,βm], respectively, and then their extended similarity function is defined as follows:
(13)Sim=fX,Y=α-β.According to principle component analysis, physical meaning of formula (13) is equivalent to that the distance (similarity) between the linear orthogonal transforms of An×m and Bn×m can be measured using the norms in the transformed space. Yang and Shahabi [13, 14] use the extended Frobenius norm to compute the similarity of MTS which is a special case of formula (13). Formula (13) can be understood by referring to the definition of similarity function of univariable time series transformed by linear operator.


## 5.3. Practical Computation of Similarity of Nonlinear Multivariable Time Series

Mathematically, it is not difficult to prove that the norm of formula (10) derived by the inner product of formula (9) satisfies the Parallelogram formula: ΦX+ΦY2+ΦX-ΦY2=2(ΦX2+ΦY2). Since ΦX-ΦY22=Φ(X),Φ(X)-2Φ(X),Φ(Y)+Φ(Y),Φ(Y), it does not need to know the mapping function explicitly. Instead, the kernel function K(x,y) is used to compute the similarity function defined in formula (11); that is,
(14)Sim=fX,Y=Kx,x-2Kx,y+Ky,y.Formula (14) shows that the nonlinear similarity measure of nonlinear time series in input space can be linearly measured in feature space through kernel method. Currently, commonly used kernel functions are as follows:(1)
linear kernel function:(15)Kx,y=xy,(2)
p-order polynomial kernel function:
(16)Kx,y=xy+1p,(3)
Gaussian radial basis RBF kernel function:(17)Kx,y=exp⁡-x-y22σ2,(4)
neural network kernel function:(18)Kx,y=tanhvxy+c.


## 6. Experimental Results

In our experiments, we take the nonlinear multivariate time series as a typical example without loss of generality for showing the accuracy of the proposed similarity measurement method. The similarity measurement function of formula (1) is used in the input space, and the similarity measurement function of formula (14) is used in the feature space. The Gaussian radial basis RBF kernel function of formula (17) is used for mapping the nonlinear samples to high-dimension space, which is low complexity compared with polynomial kernel function, especially the high rank kernel function. All samples in the original test and training sets are well mixed. The samples are randomly selected to construct the new test and training sets. Because the KNN classifier can decide a sample belong to the class in which more of k nearest samples are contains. Based on the proposed similarity measure function to verify the equivalence of time series in different spaces, KNN and kernel KNN classifiers are employed to classify the samples in the new sets in input space and feature space, respectively. Each random experiment is carried out 20 times. Then the classification accuracies in the experiments are analyzed and compared. Moreover, the parameter σ of Gaussian radial basis of RBF kernel is optimized in the experiments. The σ is initialized as a small value first. Subsequently, each random experiment for determining each value of σ is repeatedly carried out 20 times. The σ is increasingly adjusted according to the average classification accuracy of each experiment until the optimal value of σ is obtained. In our experiments, five published datasets, Cylinder-Bell-Funnel (CBF), Fish, Face (four) [18],Iris, and Wine [19], are tested.Presently, there were already some researching work on the classification of time series. One of the most common benchmark datasets is CBF [20] which was used by [21–23]. CBF dataset consists of three time series, Cylinder c(t), Bell b(t), and Funnel f(t), which are generated by the following equations:
(19)ct=6+ηXa,bt+ɛt,bt=6+ηXa,btt-ab-a+ɛt,ft=6+ηXa,btb-ab-t+ɛt,X[a,b]=1,ifa≤t≤b,else0,
where η and ɛ(t) are drawn from a standard normal distribution N(0,1), a is an integer drawn uniformly from the range [16,32], and (b-a) is an integer drawn uniformly from the range [32,96]. The three typical curves, Cylinder, Bell, and Funnel, are shown in Figures 1(a)–1(c), respectively. The curve of classification accuracy relative to σ is shown in Figure 1(d) and the classification accuracy rates of KNN and kernel KNN classifiers are also shown in Figure 1(e). It can be seen from these experimental results that the similarity of time series in original and feature spaces, which are measured with the proposed generalized similarity function defined by the distance of vector or matrix norm, is equivalent regardless of whether the time series are linearly or nonlinearly transformed. The same conclusion is obtained from the experimental results in Figures 2, 3, 4, and 5. Moreover, the average classification accuracies of each experiment repeatedly tested 20 times for five datasets are listed in Table 1, which also confirm our conclusion.Table 1
Discriminant accuracy comparison.
Datasets
Average accurate rate
KNN
Kernel KNN
CBF
0.862
0.862
Fish
0.793
0.792
Iris
0.953
0.953
Wine
0.728
0.724
Face (four)
0.893
0.893Test results of dataset CBF.
(a)
Class 1
(b)
Class 2
(c)
Class 3
(d)
Accurate rate with differentσ
(e)
Discriminant accuracy comparisonTest results of dataset Face (four).
(a)
Class 1
(b)
Class 2
(c)
Class 3
(d)
Class 4
(e)
Accurate rate with differentσ
(f)
Discriminant accuracy comparisonTest results of dataset Fish.
(a)
Class 1
(b)
Class 2
(c)
Class 3
(d)
Class 4
(e)
Class 5
(f)
Class 6
(g)
Class 7
(h)
Accurate rate with differentσ
(i)
Discriminant accuracy comparisonTest results of datasetIris.
(a)
Class 1:Iris setosa
(b)
Class 2:Iris versicolor
(c)
Class 3:Iris virginica
(d)
Accurate rate with differentσ
(e)
Discriminant accuracy comparisonTest results of dataset Wine.
(a)
Class 1
(b)
Class 2
(c)
Class 3
(d)
Accurate rate with differentσ
(e)
Discriminant accuracy comparison


## 7. Conclusion

Based on set theory, metric space theory, operator theory, matrix theory, and kernel method, the definition of similarity of time series is extended and unified theoretically to establish a generalized framework for the similarity measure of time series. In the generalized framework, the similarity of time series is defined as the distance of unified vector/matrix norm, which is suitable for both time series of univariable and multiple variables in any linear transformed space or nonlinear transformed space. The proposed similarity definition has been proven to be equivalent in original space and transformed space. The experimental results on some published time series datasets confirm that the theoretical deduction on the generality of similarity measure of time series defined in this paper is right.



---

*Source: 572124-2014-11-03.xml*