Báo cáo hóa học: " Research Article An Energy-Based Similarity Measure for Time Series"

Chia sẻ: Linh Ha | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

48
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tuyển tập báo cáo các nghiên cứu khoa học quốc tế ngành hóa học dành cho các bạn yêu hóa học tham khảo đề tài: Research Article An Energy-Based Similarity Measure for Time Series

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo hóa học: " Research Article An Energy-Based Similarity Measure for Time Series"

Hindawi Publishing Corporation EURASIP Journal on Advances in Signal Processing Volume 2008, Article ID 135892, 8 pages doi:10.1155/2008/135892 Research Article An Energy-Based Similarity Measure for Time Series Abdel-Ouahab Boudraa,1, 2 Jean-Christophe Cexus,2 Mathieu Groussat,1 and Pierre Brunagel1 1 IRENav, Ecole Navale, Lanv´oc Poulmic, BP600, 29240 Brest-Arm´es, France e e 2 E3I2, EA 3876, ENSIETA, 29806 Brest Cedex 9, France Correspondence should be addressed to Abdel-Ouahab Boudraa, boudra@ecole-navale.fr Received 27 August 2006; Revised 30 March 2007; Accepted 24 July 2007 Recommended by Jose C. M. Bermudez A new similarity measure, called SimilB, for time series analysis, based on the cross-ΨB -energy operator (2004), is introduced. ΨB is a nonlinear measure which quantiﬁes the interaction between two time series. Compared to Euclidean distance (ED) or the Pear- son correlation coeﬃcient (CC), SimilB includes the temporal information and relative changes of the time series using the ﬁrst and second derivatives of the time series. SimilB is well suited for both nonstationary and stationary time series and particularly those presenting discontinuities. Some new properties of ΨB are presented. Particularly, we show that ΨB as similarity measure is robust to both scale and time shift. SimilB is illustrated with synthetic time series and an artiﬁcial dataset and compared to the CC and the ED measures. Copyright © 2008 Abdel-Ouahab Boudraa et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. 1. INTRODUCTION similarity measures using the ED or the CC do not include temporal information and the relative changes of the TSs. Thus, clustering algorithms based on these metrics, such as A Time Series (TS) is a sequence of real numbers where each k-means, fuzzy c-means, or hierarchical clustering, cannot one represents the value of an attribute of interest (stock or cluster TSs correctly [5]. In this paper, we introduce a new commodity price, sale, exchange, weather data, biomedical similarity measure, noted SimilB, which includes the tempo- measurement, etc.). TS datasets are common in various ﬁelds ral information and relative change of the TS. SimilB is based such as in medicine, ﬁnance, and multimedia. For example, on the ΨB operator [1], a nonlinear similarity function which in gesture recognition and video sequence matching using measures the interaction between two time-signals including computer vision, several features are extracted from each im- their ﬁrst and second derivatives [6]. Furthermore, the link age continuously, which renders them TSs [2]. Typical appli- established between ΨB operator and the cross Wigner-Ville cations on TSs deal with tasks like classiﬁcation, clustering, distribution shows that ΨB and consequently SimilB are well similarity search, prediction, and forecasting. These applica- suited to study nonstationary signals [1]. tions rely heavily on the ability to measure the similarity or dissimilarity between TSs [3]. Deﬁning the similarity of TSs THE ΨB OPERATOR 2. or objects is crucial in any data analysis and decision mak- ing process. The simplest approach typically used to deﬁne a similarity function is based on the Euclidean distance (ED) To measure the interaction between two real time signals, or some extensions to support various transformations such the cross Teager-Kaiser operator (CTKEO) has been deﬁned as scaling or shifting. The ED may fail to produce a correct [7]. This operator has been extended to complex-valued sig- nals noted ΨC , in [1]. The CTKEO, applied to signals x(t ) similarity measure between TSs because it cannot deal with and y (t ), is given by [x, y ] ≡ xy − x y , where [x, y ] is the ˙ ˙ ˙ ˙ outliers and it is very sensitive to small distortions in the time axis [4]. The Pearson correlation coeﬃcient (CC) is a popu- Lie bracket which measures the instantaneous diﬀerences in ˙ the relative rate of change between x and y . In the general lar measure to compare TSs. Yet, the CC is not necessarily case, if x and y represent displacements in some generalized coherent with the shape and it does not consider the order ˙ motions, [x, y ] has dimensions of energy (per unit mass), it of time points and uneven sampling intervals. Furthermore,
2 EURASIP Journal on Advances in Signal Processing 4. 5 is viewed as a cross-energy between x and y [7]. Based on ΨC function, a symmetric and positive function, called cross- 4 ΨB -energy operator, is deﬁned [1]. We have shown that time- delay estimation problem between two signals is an example 3. 5 of interaction measure between these two signals by ΨB [6]. Let x and y be two complex signals, ΨB is deﬁned as [1] 3 Amplitude 2. 5 1 ΨB (x , y ) = (1) ΨC (x , y ) + ΨC ( y , x ) , 2 2 ˙∗ ˙∗ ¨∗ ∗¨ where ΨC (x, y ) = (1/ 2)[x y + x y ] − (1/ 2)[x y + x y ]. The ˙˙ 1. 5 ΨB (x, y ) of complex signals x and y is equal to the sum of ΨB (x, y ) of their real and imaginary parts [1]: 1 0. 5 ΨB (x, y ) = ΨB xr , yr + ΨB xi , yi , (2) 1 2 3 4 5 6 7 8 9 10 Time where x(t ) = xr (t ) + jxi (t ) and y (t ) = yr (t ) + j yi (t ) and j de- f1 notes the imaginary unit. Subscripts r and i indicate the real f2 and imaginary parts of the complex signal. According to (2), f3 the ΨB (x, y ) is a real quantity, as expected for an energy oper- ator. To compute the analytic signals x(t ) or y (t ), the Hilbert Figure 1: Three sampled TSs with diﬀerent shapes. transform is used. In the following we give the expression of ΨB for analytic signals. Table 1: SimilB, the ED, the CC between f2 and f1 , and f2 and f3 in Figure 1. EXPRESSION OF ΨB FOR ASSOCIATED 3. ANALYTIC SIGNALS TSs ED CC SimilB Complex signals are used in various areas of signal process- f2 , f1 3.9955 0.0917 0.930 ing. In the continuous time, they appear, for example, in the f2 , f3 3.9955 0.0917 0.750 description for narrow-band signals. Indeed, the appropriate deﬁnition of instantaneous phase or amplitude of such sig- nals requires the introduction of the analytic signal, which is necessarily complex. Let x and y be two real signals, and Table 2: Classiﬁcation errors of clustering task using the SimilB, the xA and yA , respectively, their corresponding analytic signals: ED, and the CC for CBF.dat dataset. xA = x + j H (x) and yA = y + j H ( y ), where H (·) is the SimilB ED CC Hilbert transform.1 By applying the relation 0.222 0.888 0.888 1 d2 uv 1 uv − (uv + vu) = 2uv − ˙˙ ¨ ¨ ˙˙ (3) 2 dt 2 2 form of the operator noted ΨBd and operating on discrete- in (2), for (u, v) = (x, y ) and (u, v) = (H (x), H ( y )), respec- time signals x(n) and y (n). Three sample diﬀerences are ex- tively, it comes that ΨB (xA , yA ) is expressed directly in terms amined. For simplicity, we replace t by nTs (Ts is the sam- of x, y , H (x) and H ( y ) as pling period), x(t ) with x(nTs ) or simply x(n). Using the same reasoning as in [8] we obtain the following relations. ΨB x A , y A = 2 x y + H ( x ) H ( y ) ˙ ˙˙ (i) Two-sample backward diﬀerence: (4) 1 d2 x y + H (x )H ( y ) . − 2 dt 2 xk (n) − xk (n − 1) x(t ) −→ ˙ , Ts Equation (4) is used to calculate the interaction between con- xk (n) − 2xk (n − 1) + xk (n − 2) tinuous TSs. x(t ) −→ ¨ , Ts2 xk (n − 1) yk (n − 1) 4. DISCRETIZING THE CONTINUOUS-TIME ΨB (xk (t ), yk (t )) −→ ΨB OPERATOR Ts2 0.5 xk (n) yk (n − 2) + yk (n)xk (n − 2) − Discretized derivatives are combined to obtain from the con- , Ts2 tinuous version of ΨB an expression closely related to discrete ΨB xk (n − 1), yk (n − 1) ΨB xk (t ), yk (t ) −→ d , k ∈ {i, r }. Ts2 H (x ) = h (5) 1 x, where the frequency response of h is h( f ) = − j sign( f ).
Abdel-Ouahab Boudraa et al. 3 Table 3: Estimated TB value versus SNR signals s1 (t ) and s2 (t ) using SimilB. SNR = −6 dB SNR = −2 dB SNR = 1 dB SNR = 3 dB SNR = 5 dB SNR = 9 dB SimilB 300 ± 1 300 ± 1 s1 (t ), r1 (t ) 300 300 300 300 300 ± 2 300 ± 1 300 ± 1 300 ± 1 300 ± 1 s2 (t ), r2 (t ) 300 Finally, the discrete form of ΨB (x(t ), y (t )) is given by 10 Amplitude 5 ΨB x(t ), y (t ) 0 −5 ΨBd xr (n − 1), yr (n − 1) + ΨBd xi (n − 1), yi (n − 1) 0 20 40 60 80 100 120 140 −→ , Time Ts2 (6) Cylinder (a) where −→ denotes the mapping from continuous to discrete. 10 (ii) Two-sample forward diﬀerence: Amplitude 5 0 xk (n + 1) − xk (n) x(t ) −→ ˙ , −5 Ts 0 20 40 60 80 100 120 140 Time xk (n + 2) − 2xk (n + 1) + xk (n) x(t ) −→ ¨ , Ts2 Bell (b) xk (n + 1) yk (n + 1) ΨB xk (t ), yk (t ) −→ 10 Ts2 Amplitude 5 0.5 xk (n + 2) yk (n) + yk (n + 2)xk (n) − 0 , Ts2 −5 0 20 40 60 80 100 120 140 ΨBd xk (n + 1), yk (n + 1) ΨB xk (t ), yk (t ) −→ k ∈ {i, r }. Time , Ts2 Funnel (7) (c) Thus, from ΨB we obtain ΨBd shifted by one sample to Figure 2: The Cylinder-Bell-Funnel dataset (CBF.dat) [10]. the right and scaled by Ts−2 . Finally, the discrete form of ΨB (x(t ), y (t )) is given by (iii) Three-sample symmetric diﬀerence: ΨB x(t ), y (t ) ΨBd xr (n +1), yr (n +1) + ΨBd xi (n +1), yi (n +1) −→ . xk (n + 1) − xk (n − 1) Ts2 x(t ) −→ ˙ , 2Ts (8) xk (n + 2) − 2xk (n) + xk (n − 2) x(t ) −→ ¨ , 4Ts2 Note that for both asymmetric two-sample diﬀerences, ΨB ΨB xk (t ), yk (t ) is shifted by one sample and scaled by Ts−2 . If we ignore the xk (n +1) yk (n − 1)+ yk (n +1)xk (n − 1) 2xk (n) yk (n) − → − , one-sample shift and the scaling parameter, one can trans- 4Ts2 4Ts2 form ΨB (x(t ), y (t )) into ΨBd (x(n), y (n)) as follows: xk (n − 1) yk (n − 1) 0.5 xk (n) yk (n − 2) + yk (n)xk (n − 2) − 4Ts2 4Ts2 ΨB x(t ), y (t ) −→ ΨBd xr (n), yr (n) + ΨBd xi (n), yi (n) , xk (n +1) yk (n +1) 0.5 xk (n +2) yk (n)+ yk (n + 2)xk (n) (9) − + , 4Ts2 4Ts2 ΨBd xk (n), yk (n) ΨB xk (t ), yk (t ) = xk (n) yk (n) − 0.5 xk (n + 1) yk (n − 1) − ΨBd xk (n +1), yk (n +1) + 2ΨBd xk (n), yk (n) → + yk (n + 1)xk (n − 1) , k ∈ {i, r }. +ΨBd xk (n − 1), yk (n − 1) / 4Ts2 , k ∈ {i, r }. (10) (11)
4 EURASIP Journal on Advances in Signal Processing Euclidean Correlation SimilB 32 1 550 30 0. 9 28 500 0. 8 26 0. 7 24 450 Threshold Threshold Threshold 0. 6 22 0. 5 400 20 0. 4 18 350 16 0. 3 14 0. 2 300 12 123456789 172589364 172589364 Labels Labels Labels (a) (b) (c) Figure 3: Comparison of the SimilB, the ED, the CC on a clustering task. Labels (1,2,3), (4,5,6), and (7,8,9) correspond to Cylinder, Bell, and Funnel classes, respectively. Compared to asymmetric two-sample diﬀerences, the three- It is trivial that ΨB is time-shift invariant, that is, sample symmetric diﬀerence leads to more complicated ΨB (x1 , y1 ; t ) = ΨB (x, y ; t − t0 ). This property states that any time translations in the signals, x(t ) and y (t ), should be expression. Expression (11) corresponds to three-sample weighted moving average of ΨBd (xk (n), yk (n)). Note if x = preserved in their measure of interaction, ΨB (x, y ; t ). Thus, y , ΨBd is reduced to the Teager-Kaiser operator (TKO): ΨB (x, y ; t ) is robust to time shifts. ΨBd (x(n), x(n)) = x2 (n) − x(n + 1)x(n − 1) (see [9]). Finally, the asymmetric approximation is less complicated for imple- Amplitude scale: mentation and is faster than the symmetric one. x1 (t ) ←− α·x(t ), PROPERTIES OF ΨB 5. (14) y1 (t ) ←− β· y (t ). We provide here some new properties of ΨB [1]. We denote ΨB of x(t ) and y (t ) by ΨB (x, y ; t ) and denote by “← ” the It is easy to verify that ΨB (x1 , y1 ; t ) = α·βΨB (x, y ; t ). Thus, aﬀectation operation. the time where ΨB peaks, corresponding to the maximum of interaction between x(t ) and y (t ), is robust to amplitude scale. Similarity measure: Time scale: Ψ B (x , y ; t ) = ΨB ( y , x ; t ). (12) This is a basic requirement for most of similarity or distance x1 (t ) ←− x(at ), measures. (15) y1 (t ) ←− y (at ). Time shift: It is easy to verify that ΨB (x1 , y1 ; t ) = a2 ΨB (x, y ; t ). This property states that if the time of the two signals is com- x1 (t ) ←− x t − t0 , pressed by a scale a, then the energy of interaction is com- (13) pressed by a2 . y1 (t ) ←− y t − t0 .
Abdel-Ouahab Boudraa et al. 5 1 0.25 Signal X 0. 5 0. 2 Normalized frequency Signal X 0.15 0 −0.5 0. 1 Intersection frequency −1 0.05 0 50 100 150 200 0 50 100 150 200 Times Times (a) (b) 1 0.25 Intersection frequency 0. 5 0. 2 Normalized frequency Signal Y 0.15 0 −0.5 0. 1 Signal Y −1 0.05 0 50 100 150 200 0 50 100 150 200 Times Times (c) (d) Figure 4: Linear chirp TSs (parabolic phase). 1. 8 0.15 1. 6 0. 1 Ψ (Y , Y ) Ψ (X , X ) 1. 4 0.05 1. 2 Intersection frequency Amplitude Amplitude 0 1 0. 8 −0.05 0. 6 −0.1 0. 4 −0.15 Ψ (X , Y ) 0. 2 −0.2 0 0 50 100 150 200 0 50 100 150 200 Times Time Figure 5: Similarity measure using SimilB with a sliding window Figure 6: Similarity measure using CC with a sliding window anal- analysis. ysis. 5.1. ΨB -based similarity measure symmetric function whose value is large when x and y are A similarity measure S(x(t ), y (t )) is a function to compare somehow similar. The proposed similarity measure based on the TSs x(t ) and y (t ). Conventionally, this measure is a ΨB (x, y ), between x(t ) and y (t ), uses their interaction. A
6 EURASIP Journal on Advances in Signal Processing s1 (t ) 1 Amplitude 0.5 0 −0.5 −1 0 50 100 150 200 250 300 350 400 450 500 s2 (t ) 6 Amplitude 4 2 0 −2 0 50 100 150 200 250 300 350 400 450 500 Time (a) Signals s1 (t ) and s2 (t ) CC SimilB 1 500 0.9 400 0.8 300 0.7 200 Amplitude Amplitude 0.6 100 0.5 0 −100 0.4 −200 0.3 −300 0.2 −400 0.1 −500 0 0 50 100 150 200 250 300 350 400 450 500 0 50 100 150 200 250 300 350 400 450 500 Time Time (b) CC with a sliding window analysis (c) SimilB with a sliding window analysis Figure 7: Similarity measure using SimilB and CC of sinusoidal TSs. larger value indicates more interaction in energy between would show, for example, that the similarity values between f1 and f2 and that between f3 and f2 are diﬀerent. Results of TSs. If the input variables (or samples) of the TS x(t ) (or y (t )) have large range, then this can overpower the other in- the SimilB, the ED, and the CC between f2 and f1 and that put variables of y (t ) (or x(t )). Therefore, the proposed sim- between f2 and f3 are reported in Table 1. These results show ilarity measure, SimilB, is a normalized version of ΨB (x, y ) that SimilB is the unique measure which properly capture and is deﬁned as follows: the temporal information in the comparison of the shapes. √ The most studied TS classiﬁcation/clustering problem is the 2 T ΨB (x, y )dt Cylinder-Bell-Funnel dataset (noted CBF.dat) [10]. It is a 3- SimilB(x, y ) = . (16) ΨB (x, x) + Ψ2 ( y , 2 class problem. Typical examples of each class are shown in y )dt B T Figure 2. The classes are generated by the equations [10] T is the TS duration or the size of sliding window analysis. c(t ) = (6 + η)·X[a,b] (t ) + (t ) // Cylinder class, The similarity is symmetric when comparing two TSs: (t − a) b(t ) = (6 + η)·X[a,b] (t ). + (t ) // Bell class, (b − a) SimilB(x, y ) = SimilB( y , x) ∀(x, y ) ∈ C2 . (17) (b − t ) f (t ) = (6 + η)·X[a,b] (t ). + (t ) // Funnel class, (b − a) It is a basic requirement for most of similarity or distance X[a,b] = 1 if a ≤ t ≤ b, else X[a,b] = 0, measures. Note that if x = y then SimilB(x, y ) = 1. (18) where η and (t ) are drawn from a standard normal distribu- 6. RESULTS tion N (0, 1), a is an integer drawn uniformly from the range [16, 32], and (b − a) is an integer drawn uniformly from the SimilB (equation (17)) is combined with relations (10) and (11), and relation (3) or (4) to process discrete (Figure 2) and range [32, 96] (Figure 2). The task is to classify a TS as one continuous (Figures 1, 4, 7, and 8) data, respectively. The ef- of the three classes, Cylinder, Bell, or Funnel. We have per- fects of temporal information and the inclusion of the signal formed an experiment classiﬁcation on CBF.dat dataset con- derivatives are shown on nonstationary and stationary syn- sisting of 3 TSs of each class. TSs are clustered using group- thetic TSs. Figure 1 shows three TSs with diﬀerent shapes to average hierarchical clustering. The dendrograms are formed illustrate the limit of the ED and the CC. Since f1 , f2 , and f3 with nearest neighbor linkage for three of each type of TSs have diﬀerent shapes, then an appropriate similarity measure using SimilB measure, the ED, and the CC. We have averaged
Abdel-Ouahab Boudraa et al. 7 1 1 s1 (t) s2 (t) 0. 5 0 0 −1 0 20 40 60 0 20 40 60 80 Time Time (a) (d) 1 1 r2 (t) r1 (t) 0 0 −1 −1 0 200 400 600 0 200 400 600 Time Time (b) (e) Ë Ñ Ð (s2 (t), r2 (t)) Ë Ñ Ð (s1 (t), r1 (t)) 1 1 T T 0. 5 0 0 −0.5 −1 0 200 400 600 0 200 400 600 Time Time (c) (f) Figure 8: Similarity measure using SimilB of TSs of nonequal length. the classiﬁcation results over 45 runs. Figure 3 shows the re- Figure 6 shows that the maximum of similarity given by CC is located at t = 240. Thus, the CC fails to point out, as ex- sult of these averaged runs where both the ED and the CC fail to diﬀerentiate between the three classes. SimilB distin- pected (Figure 4), the maximum of similarity at Q. The in- guishes the three original classes as shown in Figure 3. Clas- teraction measure using SimilB and CC is performed using a sliding window analysis of size T . Diﬀerent T values rang- siﬁcation errors reported in Table 2 show that SimilB is more eﬀective than the ED and the CC. These results are expected ing from 3 to 91 have been tested. Globally, we found com- since the ED and the CC are not able to include the tempo- parable results. The CC is calculated with the same sliding window as for SimilB. Furthermore, as the IFs converge to Q ral information while SimilB using derivatives of the TS cap- or diverge from Q, the CC function has, globally, the same tures this kind of information. Moreover, these results may behavior and thus the similarity study of such TSs is diﬃ- be due to the fact that ΨB is local operator [1, 6] while the cult. This example shows that the SimilB is more eﬀective ED and the CC are global ones. Figure 4 shows an exam- ple of nonstationary TSs (two linear FM signals), x(t ) and to study nonstationary TSs than the CC. This may be due y (t ). The instantaneous frequency (IF) of x(t ) increases lin- the fact that the ΨB is nonlinear operator while the CC is early with time while that of y (t ) decreases with time. The linear one. Figure 7(a) shows an example of two sinusoidal point where the IFs intercept (Figure 4), noted Q, is located TSs, s1 (t ) and s2 (t ), of the same frequency and amplitude. TS at t = 125. Figure 5 shows the energy of each TS and the en- s2 (t ) presents a discontinuity located at t = 200. Both CC and SimilB are calculated with T set to 17. CC measure fails ergy of their interaction obtained with a sliding window anal- ysis of T = 15. The point Q corresponds to the maximum to detect the discontinuity and shows a maximum of interac- tion at t = 262 (Figure 7(b)). The result of SimilB is expected of similarity and also where the energy of x(t ) (SimilB(x, x)) (Figure 7(c)). Indeed, excepted for data point at t = 200, s1 (t ) and that of y (t ) (SimilB( y , y )) are equal. Away from Q, the and s2 (t ) are equal and ΨB behaves toward these two signals amplitude of interaction decreases because there is less sim- as the TKO applied to s1 (t ) (s2 (t )) and thus giving a constant ilarity between TSs (the TSs tend to be more and more dif- ferent). As the IFs converge from the time origin to Q (the output (square of the amplitude times the frequency) [9]. TSs tend to be equal), the interaction intensity of the TSs in- This example shows the interest of SimilB to track disconti- creases and the maximum of similarity is achieved at t = 125. nuities (Figure 7(c)). Two synthetic signals, s1 (t ) and s2 (t ), of
8 EURASIP Journal on Advances in Signal Processing nonequal lengths with size window observation T of 65 and ters. To conﬁrm the presented results, a large class of real TSs 81, respectively, are shown in Figures 8(a) and 8(d). These datasets must be studied as well as the results compared to two signals are time shifted by 300 samples and corrupted other methods particularly those including the temporal in- by additive Gaussian noise. The obtained signals, r1 (t ) and formation. r2 (t ), are shown in Figures 8(b) and 8(e), respectively. The attenuation coeﬃcient is set to 0.7. For both signals r1 (t ) and REFERENCES r2 (t ), a similarity measure would show, in theory, a maxi- mum of interaction located at t = 300. No warping pro- [1] J.-C. Cexus and A.-O. Boudraa, “Link between cross-Wigner distribution and cross-Teager energy operator,” Electronics Let- cess is used. We use the smallest TS length as a sliding win- ters, vol. 40, no. 12, pp. 778–780, 2004. dow and calculate SimilB, inside this window, between two [2] J. Alon, S. Sclaroﬀ, G. Kollios, and V. Pavlovic, “Discovering TSs of the same length. Outputs of SimilB are shown in Fig- clusters in motion time-series data,” in Proceedings of IEEE ures 8(c) and 8(f) indicating a net maximum at t = TB . Computer Society Conference on Computer Vision and Pattern As expected, both SimilB(s1 (t ), r1 (t )) and SimilB(s2 (t ), r2 (t )) Recognition (CVPR ’03), vol. 1, pp. 375–381, Madison, Wis, peak to TB = 300. Table 3 lists the TB values calculated for USA, June 2003. SimilB(s1 (t ), r1 (t )) and SimilB(s2 (t ), r2 (t )) for diﬀerent SNRs [3] R. Agrawal, C. Faloutsos, and A. Swami, “Eﬃcient similarity ranging from −6 dB to 9 dB. Each value of Table 3 corre- search in sequence databases,” in Proceedings of the 4th Inter- sponds to the average of an ensemble of twenty ﬁve trials of national Conference on Foundations of Data Organization and TB estimation. These results show that the performances of Algorithms (FODO ’93), vol. 730 of Lecture Notes in Computer SimilB are very close to that of the theory and also that SimilB Science, pp. 69–84, Chicago, Ill, USA, October 1993. [4] S. Chu, E. Keogh, D. Hart, and M. Pezzani, “Iterative deepen- works correctly for moderately noisy TSs. ing dynamic time warping for time series,” in Proceedings of the 2nd SIAM International Conference on Data Mining, Arlington, 7. CONCLUSION Va, USA, April 2002. [5] C. S. M¨ ller-Levet, F. Klawonn, K. H. Cho, and O. Wolken- o Relative change of amplitude and the corresponding tempo- hauer, “Fuzzy clustering of short time-series and unevenly ral information are well suited to measure similarity between distributed sampling points,” in Proceedings of the 5th Inter- TSs. In this paper, a new nonlinear similarity measure for TS national Symposium on Intelligent Data Analysis (IDA ’03), analysis, SimilB, which takes into account the temporal in- vol. 2810 of Lecture Notes in Computer Science, pp. 330–340, formation is introduced. Using the ﬁrst and second deriva- Berlin, Germany, August 2003. tives of the TS, SimilB is able to capture temporal changes [6] Z. Saidi, A.-O. Boudraa, J.-C. Cexus, and S. Bourennane, and discontinuities of the TS. Some new properties of ΨB “Time-delay estimation using cross-ΨB -energy operator,” In- ternational Journal of Signal Processing, vol. 1, no. 1, pp. 28–32, are presented showing, particularly, that the interaction mea- 2004. sure is robust both to time shift and amplitude scale. It is also [7] P. Maragos and A. Potamianos, “Higher order diﬀerential en- shown that if the time of the signals is scaled by a factor, the ergy operators,” IEEE Signal Processing Letters, vol. 2, no. 8, pp. corresponding interaction energy is proportional to that of 152–154, 1995. the original ones. Thus, the time corresponding to the max- [8] P. Maragos, J. F. Kaiser, and T. F. Quatieri, “On amplitude imum of interaction is unchanged by time scale. Note that and frequency demodulation using energy operators,” IEEE SimilB is not a unique measure of similarity based on ΨB op- Transactions on Signal Processing, vol. 41, no. 4, pp. 1532–1550, erator. Diﬀerent similarity based on ΨB can be constructed. 1993. To process continuous analytic TSs an expression of ΨB is [9] J. F. Kaiser, “Some useful properties of Teager’s energy opera- provided. The discrete version of ΨB , for its implementation, tors,” in Proceedings of IEEE International Conference on Acous- is presented and three derivative approximations are exam- tics, Speech, and Signal Processing (ICASSP ’93), vol. 3, pp. 149– ined. Only the asymmetric approximation which is less com- 152, Minneapolis, Minn, USA, April 1993. [10] N. Saito, Local feature extraction and its application using a li- plicated and less time consuming is implemented. Results of diﬀerent synthetic TSs (stationary and nonstationary) show brary of bases, Ph.D. thesis, Yale University, New Haven, Conn, USA, 1994. that SimilB performs better than the ED and the CC and [11] D. Dimitriadis and P. Maragos, “An improved energy demod- show the interest to take into account the relative changes ulation algorithm using splines,” in Proceedings of IEEE Inter- of the TSs. Compared to generative models (HMM, GMM, national Conference on Acoustics, Speech, and Signal Process- . . . ) or distance kernel-based methods, SimilB is nonpara- ing (ICASSP ’01), vol. 6, pp. 3481–3484, Salt Lake, Utah, USA, metric approach that does not require the speciﬁcation of a May 2001. kernel or the selection of a probability distribution. Further- more, SimilB is fast and easy to implement. SimilB may be viewed as a data-driven approach because no a priori infor- mation about the signals or parameters setting is required. The processed TSs are either noiseless or moderately noisy. For very noisy TSs, the robustness of SimilB must be studied. In a future work, we plan to use smooth splines to give more robustness to SimilB [11]. We also plan to include the Sim- ilB measure in a clustering process or algorithm such as fuzzy c-means or k-means for classiﬁcation of TSs in diﬀerent clus-