2005 International Symposium on Nonlinear
Theory and its Applications (NOLTA2005)
Bruges, Belgium, October 18-21, 2005

Estimation of Embedding Dimension Using Self-Organizing Map
Haruna MATSUSHITA and Yoshifumi NISHIO
Department of Electrical and Electronics Engineering
Tokushima University
2-1 Minami-Josanjima, Tokushima 770-8506, Japan
Phone:+81-88-656-7470, Fax:+81-88-656-7471
Email: fharuna, nishiog@ee.tokushima-u.ac.jp

Abstract|In order to analyze the nonlinear timeseries, the embedding is very important. In the embedding process, We must determine the appropriate
embedding dimension to reconstruct with time-delay.
In this study, we propose a method to estimate the embedding dimension using Self-Organizing Map (SOM).
We can obtain the map re ecting the distribution stateof input data using SOM. We carry out simulations
for the time series obtained from the Henon map, theIkeda map, and the Lorenz equations, and con rm that
our method would be useful to estimate the appropriate embedding dimensions.

acteristics of the distribution of the points in the reconstructed attractors and 2) the characteristics wouldchange dramatically until the embedding dimensions
reaches to the appropriate value and would not change
beyond the value. We carry out computer simulations
for the time series obtained from the Henon map, theIkeda map, and the Lorenz equations with di erent delay time, and con rm that our method would be usefulto estimate the appropriate values of the embedding
dimensions.

1. Introduction

In order to analyze the nonlinear time series, reconstruction of attractors must be done rst. Suppose thed-dimensional state vector x(t) evolves according to an
unknown but continuous and deterministic dynamics.
In particular, we construct the state vector y (t) withdelay coordinates in the k -dimensional reconstructed
space as follows;y (t) = [x(t); x(t +  ); 1 1 1 ; x(t + (k 0 1) )]; (1)where k is the embedding dimension and  is the delaytime. The trajectory in the reconstructed state spaceis de ned as a sequence of k-dimensional vectors.
Figures 1-3 show the reconstructed attractors for thetime series obtained from the Henon map, the Ikeda
map, and the Lorenz equations with di erent delay
times, respectively, where, the total number of thedata points is N = 1000.

138

1.511x(t+2τ)

0.5x(t+τ)In the analysis of the time series come from nonlinear dynamical systems, the embedding is very important [1]. In the embedding process, the embedding
dimension k must be properly determined. If the current embedding dimension k is too small, points which
are really far apart will be brought arti cially close together. Conversely, if the embedding dimension is toolarge, the structure of the reconstructed attractor becomes coarse, consequently, when we analyze the nite
observed time series data, there is a sucient possibility that the shortage of data will bring about the false
analysis result. In addition, the calculation amount ofanalysis increase pro rata the embedding dimension,so, determining the appropriate embedding dimension
is very important.
A common procedure for determining the embedding dimension is the False Nearest Neighbors method(FNN method) [2]. However, the calculation amountis quite large for this method. In this study, we propose a method to estimate the embedding dimension
using Self-Organizing Map (SOM) [3]. SOM is unsupervised neural network introduced by Kohonen in
1982. Self-Organization is to change an internal structure to adjust to the signal from the outside. SOM isa model simplifying self-organization process of brain.
SOM obtains a statistical feature of input data. We
can obtain the map re ecting the distribution state of
input data using SOM. The motivations of our method
are as follows: 1) SOM could grasp the statistical char-

2. Embedding

00.5
0−0.5

−0.5

−1−1−1.5−1.5

10−1−0.50x(t)0.5

11.5x(t+τ)−1−1−0.500.5x(t)1(a) k = 2.
(b) k = 3.
Figure 1: Reconstructed attractor for Henon map.

2

1.5

1x(t+2τ)x(t+τ)

1.4

1

0.5

0.6
0.2

−0.2
2

0−0.5
−0.5

00.5x(t)

1

1.5

1.5

2

1

0.50x(t+τ)−0.5 −0.5

1.5

10.50x(t)(a) k = 2.
(b) k = 3.
Figure 2: Reconstructed attractor for Ikeda map.
201015510x(t+2τ)

0−50−10−10−1515−15−20−205−5−1001050−5x(t+τ)x(t)

201020(a) k = 2,  = 5.

−10−15 −10−51050FNN [%]x(t+τ)

15tor. If the number of the false nearest neighbors is not
smaller than a suciently small value, the embedding
dimension is de ned to be too small.
Figure 4 shows the simulation results of FNN
method for the Henon map, the Ikeda map, and theLorenz equations with  = 5 and 10. The horizontal
axis is the embedding dimension and the vertical axis
is the number of the false nearest neighbors (percentage).
We can see from the gure that k = 2 is enough for
the Henon map and the Lorenz equations with  = 5.
While the Ikeda map and the Lorenz equations with
 = 10 have some amount of false nearest neighbors
for k = 2 and hence k = 2 is not sucient to embed
the information of these time series. For k = 3, thenumbers of the false nearest neighbors becomes almost
zero for all of the time series data.

x(t)(b) k = 3,  = 5.

1015510x(t+2τ)

0−52345(a) Henon map and Ikeda map.

0−5−10−10−1515−15−20−20Henon map
Ikeda map

Embedding dimension k

5−100x(t)1020105x(t+τ)

0−5−10−15 −15 −10−5051015FNN [%]x(t+τ)

15100
8060
40
2001x(t)(c) k = 2,  = 10.
(d) k = 3,  = 10.
Figure 3: Reconstructed attractor for Lorenz equations.

τ=5τ = 10234

5Embedding dimension k(b) Lorenz equations with di erent delay time.
Figure 4: Simulation results of FNN method.

3. False Nearest Neighbor method
The FNN method is that if the current embedding dimension k is sucient to resolve the dynamics, points which were close each other in the kdimensional reconstructed attractor should remainclose in the (k + 1)-dimensional reconstructed attractor. Conversely, if the embedding dimension is toosmall, points which are really far apart will be broughtarti cially close together.
The FNN algorithm is explained as follows. Take
one point in the k -dimensional reconstructed attractor, nd its nearest neighbor in the attractor, and thencalculate the distance between them. Re-calculate
the distance between the same points, but in the(k + 1)-dimensional reconstructed attractor. If the recalculated distance is more than a certain xed multiple of the original distance, these two points are said tobe \false nearest neighbors (FNN)." The xed multiple
is chosen as from 2 to 15. Repeat the process for all of
the points in the k -dimensional reconstructed attrac-1008060
40
2001

4. SOM method
4.1. Algorithm of SOM method

We explain the learning algorithm of SOM and themethod of determining the embedding dimension using
SOM. m neurons are connected on a one-dimensionalline like a rope (where the rst neuron and m neuron are not connected). The input vectors y(t) are thepoints in the k-dimensional reconstructed attractor.
th[PHASE 1](SOM1) The initial values of all the weight vectors
w are given over the input space at random.

[PHASE 2](SOM2) An input vector y(t) is inputted to all theneurons at the same time in parallel.

139(SOM3) We nd the winner neuron c(t) by calcuiiii

1ik

10.5x(t+τ)i

1.5x(t+2τ)

lating the distances between the input vector y(t)and the weight vector w = (w 1; w 2; 1 1 1 ; w ) (i =1; 2; 1 1 1 ; m) of neuron i, according to;c(t) = arg minfkw 0 y (t)kg:
(2)

00.5
0

−0.5

−0.5

−1
−1

1

In other words, the winner neuron c(t) is the neuron
with the weight vector nearest to the input vector y(t).
(a) k = 2.
(b) k = 3.
In this study, Euclidean distance is used for (2).
Figure 5: Learning of SOM for Henon map.
(SOM4) The weight vector of the neurons are updated as;
w (s + 1) = w (s) + h ( ) (s)(y(t) 0 w (s)); (3)where s is the learning step. h ( ) (s) is called theneighborhood function and it is described as follows; kr 0 r k2 ()h ( ) (s) = (s) exp 0;(4)22 (s)where (s) is the learning rate, r and r ( ) are thevectorial locations on the display grid, and (s) corresponds to the widths of the neighborhood functions.
(a) k = 2.
(b) k = 3.
(s) and (s) decrease with time according to the folFigure 6: Learning of SOM for Ikeda map.
lowing equations;(s) = (0) (1 0 s=T ) ;(5)(s) = (0) (1 0 s=T ) ;After [PHASE 2], we calculate the distance L acwhere T is the maximum number of the learning.
cording3]. The probability density func(SOM5) The steps from (SOM2) to (SOM4) are re- tions of tothe[PHASEdistances
L for all of the cases are shownpeated for all the input data.
in Fig. 8. We can see that there are obvious di erences[PHASE 3]
between the graphs of k = 1 and k = 2, however, are(SOM6) After learning, we calculate the distance L not big di erences between k = 2, 3, 4 and 5. Thisbetween the weight vectors of the adjacent two neu- is attributed to the fact that k = 1 is too small torons.
embed the information of the time series for all of thedata and that k = 2 is enough or somewhat close tokw 0 w +1 kp; (j = 1; 2; 1 1 1 ; m 0 1):(6) appropriate value. These results agree well the results
L=kobtained by using the FNN method in Fig. 4.
4.2. Simulation Results
Let us observe the graphs more carefully paying atWe simulated the method of determining the embed- tentions on the graphs corresponding to k = 2. The reding dimension using SOM. Input data are N = 1000 sults for the Ikeda map are shown in Fig. 8(b). Amongpoints obtained from the Henon map, the Ikeda map, the graphs corresponding to k = 2, 3, 4, and 5, only
and the Lorenz attractors with di erent  , which are the graph of k = 2 is a little bit apart from the others.
the same as the data in the FNN method. The simula- This result suggests that some information would betion was performed as changing the embedding dimen- submerged in the 2-dimensional reconstructed attracsion k from 1 to 5. Each SOM has m = 300 neurons. tor. Similar feature can be seen in Fig. 8(d). Namely,
The parameters of the learning are chosen as follows; for the data obtained from the Lorenz attractors with = 10, embedding to the 2-dimensional state space(0) = 0:95; (0) = 9:
submerges some information of the time series.
We repeat [PHASE 2] 20 times (namely the maximum
As a result from these gures, we could estimate
number of the learning is T = 20000). The results of the appropriate values of the embedding dimensions
the learning for the cases of k = 2 and k = 3 are shown as k = 2, k = 3, k = 2, and k = 3 for the Henon map,in Figs. 5-7. We can see that the SOMs can obtain the Ikeda map, the Lorenz attractors with  = 5, andstatistical features of the reconstructed attractors.
the Lorenz attractors with  = 10, respectively.
0−1.5
−1.5

i

i

−1

−0.5

00.5x(t)11.5x(t+τ)−1−0.5−100.51x(t)ic t ;i2c t ;i1.5

1.4

c tx(t+τ)c t ;i1x(t+2τ)

i

0.5

10.6
0.2

−0.2
20

i

c t

−0.5
−0.5

j

j

140

0

0.5x(t)

1

1.5

2

1.5

1x(t+τ)0.5

0−0.5 −0.500.5x(t)

11.5

2015
10

15−55

35

−5−10−10−15
15−15−100x(t)10102050−5x(t+τ)(a) k = 2,  = 5.

k=1
k=2
k=3
k=4
k=540

0−10−15 −10−51050x(t)(b) k = 3,  = 5.

Percentage [%]x(t+2τ)x(t+τ)

0−20−20

45

10

530
2520
15
1020

515
1010x(t+2τ)x(t+τ)

50−5−100x(t)10200.1

LL

0.15

0−5−1515−150.05(a) Henon map.

545

−10−10−20−200015

105x(t+τ)0−5−10−15 −15 −10−50

510

k=1
k=2
k=3
k=4k=5401535x(t)Percentage [%](c) k = 2,  = 10.
(d) k = 3,  = 10.
Figure 7: Learning of SOM for Lorenz attractors.

3025201510

5. Conclusion

5References

00

0.05

0.1

L

0.15

0.2

(b) Ikeda map.
45

k=1
k=2
k=3
k=4
k=540
35

Percentage [%]In this study, we have proposed the method ofdetermining the embedding dimension using SelfOrganizing Map. By using this method, we can determine the embedding dimension, and obtain the transitof the reconstructed state. In the future, we con rm
the e ectiveness of this method by applying to thehigher dimensional and more complex chaos.

30252015
10[1] N. H. Packard, J. P. Crutch eld, J. D. Farmar,and R. S. Shaw, \Geometry from a Time Series,"
L
Physical Review Letters, vol.45, No.9, pp.712-716,(c) Lorenz attractors ( = 5).
1980.
[2] Matthew B. Kennel and Henry D. I. Abarbanel,\Determining embedding dimension for phasespace reconstruction using a geometrical construction,"Physical Review A, vol.45, No.6, pp.34033411, 1992.
[3] T. Kohonen, Self-Organizing Maps, Berlin,Springer, vol. 30, 1995.
[4] Matthew B. Kennel and Henry D. I. AbarL
banel, \False Neighbors and False Stands: A(d)Lorenzattractors( = 10).
Reliable Minimum Embedding Dimension Algorithm,"Physical Review E, vol.66, 2002.
Figure 8: Probability density functions of distances L
between the weight vectors of the adjacent two neurons.
5000.5

1

1.5

45

k=1
k=2
k=3
k=4
k=540
35

Percentage [%]

230
2520
15
10

500

141

0.5

11.52