Permutation entropy — a natural complexity measure for time series
Christoph Bandt and Bernd Pompe
Institute of Mathematics and Institute of Physics, University of Greifswald, Germany
(February 18, 2002)
We introduce complexity parameters for time series based
on comparison of neighboring values. The definition directly
applies to arbitrary real–world data. For some well–known
chaotic dynamical systems it is shown that our complexity
b ehaves similar as Lyapunov exponents, and is particularly
useful in the presence of dynamical or observational noise.
The advantages of our method are its simplicity, extremely
fast calculation, its robustness and invariance with respect to
non–linear monotonous transformations.
05.45.Tp, 05.45.-a, 02.50.-r
I. COMPLEXITY MEASURES FOR TIME SERIES
Various measures of complexity were developed to
compare time series and distinguish regular, (e.g. pe-
riodic), chaotic and random behavior. Among others,
it has been reported that complexity of heart and brain
data can distinguish healthy and sick subjects and some-
times even predict heart attack or epileptic seizure [1].
The main types of complexity parameters are entropies,
fractal dimensions, Lyapunov exponents. They are all de-
fined for typical orbits of presumably ergodic dynamical
systems, and there are profound relations between these
quantities which allow to compute one from the other
[2,3].
Problem. The basic conceptual problem is that
these definitions are not made for an arbitrary series of
observations {x
1
, x
2
, ...}. As a consequence, there is also
a computational problem. Many ingenious algorithms,
tricks and recipes have been developed during the last 20
years in order to estimate complexity measures from real–
world time series [4–7]. They work wonderfully when
the time series is simulated from a low-dimensional dy-
namical system, but most of them break down as soon
as noise is added to the series. For real–world series,
“noise elimination”requires careful preprocessing of the
data and fine-tuning of parameters, and the results can-
not be reproduced without specifying details of the method.
One idea to overcome these problems is application of
Kolmogorov–Chaitin algorithmic complexity to orbits of
dynamical systems [7–9].
Our approach. We go another way, defining simple
complexity measures which are easily calculated for any
type of time series, be it regular, chaotic, noisy or from
reality. A practical and a theoretical example were cho-
sen to compare our complexity with established concepts.
In Sec. I II, we recognize voiced sounds in a speech signal.
In Sec. IV, we show for the well–known family of logis-
tic maps that our permutation entropy is very similar to
Lyapunov exponents over the range of several thousand
parameter values. Most importantly, it yields meaning-
ful results in the presence of observational and dynamical
noise (Sec. V).
Source entropy. Given a stationary time se-
ries {x
t
}, most complexity parameters measure in one
or the other way the multitude of different vectors
(x
t+1
, ..., x
t+n
) for various n, passing then with n to ∞.
If the x
t
attain a finite number M of values, the classical
source entropy h of Shannon measures the mean condi-
tional uncertainty of the future x
t+1
given the whole past
. . . x
t−1
, x
t
. We have 0 ≤ h ≤ log M, with h = 0 if the se-
ries is perfectly predictable from the past and h = log M
iff all values are independent and uniformly distributed.
Large h indicates high complexity. Shannon’s entropy
can be generalized by R´enyi’s α–entropies [2,4,10].
Partitions. If the x
t
attain infinitely many values,
it is common to replace them by a symbol sequence {s
t
}
with finitely many symbols, and calculate source entropy
for the s
t
. We can use a partition X = P
1
∪ ... ∪ P
m
of
the set of values and define s
t
= i if x
t
is in P
i
. Then
we can increase the number m of pieces and get a limit
for fine resolution which is the Kolmogorov–Sinai entropy
h
K
, an isomorphism invariant of the dynamical system
[2,3,11]. For special generating partitions, no such limit
is needed. These partitions are difficult to find, how-
ever, even for two-dimensional examples like the Henon
system [12]. For unimodal maps, the critical point de-
fines a generating partition [13] but any misplacement
of the partition point gives an entropy smaller than h
K
[14]. Our viewpoint (cf. [15]) is that the symbol sequence
must come naturally from the x
t
, without further model
assumptions. Thus we suggest to take partitions given by
comparison of neighboring values x
t
. For interval maps,
this is similar to using generating partitions [16].
II. BASIC DEFINITIONS
The following definitions apply to an arbitrary time se-
ries, with a weak stationarity assumption explained be-
low. In the sequel we neglect equal values x
t
∗
= x
t
,
t
∗
6= t, and consider only inequalities between the x
t
.
This is justified if the values x
t
have a continuous distri-
bution so that equal values are very rare. Otherwise, we
can numerically break equalities by adding small random
perturbations.
Our entropies are calculated for different embedding
1
下载后可阅读完整内容，剩余4页未读，立即下载
langjue1989
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- 李兴华Java基础教程：从入门到精通
- U盘与硬盘启动安装教程：从菜鸟到专家
- C++面试宝典：动态内存管理与继承解析
- C++ STL源码深度解析：专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手：数据管理与企业增值的战略
- Eclipse IDE基础教程：从入门到精通
- Shell脚本专家宝典：全面学习与资源指南
- Tomcat安装指南：附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华：必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
