Permutation (symbolic)

Entropies.SymbolicPermutation — Type

SymbolicPermutation(m::Int; b::Real = 2)

A symbolic permutation probabilities estimator using motifs of length m, based on Bandt & Pompe (2002)^{[BandtPompe2002]}.

If the estimator is used for entropy computation, then the entropy is computed to base b (the default b = 2 gives the entropy in bits).

The motif length must be ≥ 2. By default m = 2, which is the shortest possible permutation length which retains any meaningful dynamical information.

source

Entropies.entropy — Method

entropy(x::Dataset, est::SymbolicPermutation, α::Real = 1)
entropy!(s::Vector{Int}, x::Dataset, est::SymbolicPermutation, α::Real = 1)

Compute the generalized order α permutation entropy of x, using symbol size est.m.

Probability estimation

An unordered symbol frequency histogram is obtained by symbolizing the points in x, using probabilities(::Dataset{N, T}, ::SymbolicPermutation). Sum-normalizing this histogram yields a probability distribution over the symbols

A pre-allocated symbol array s, where length(x) = length(s), can be provided to save some memory allocations if the permutation entropy is to be computed for multiple data sets.

Entropy estimation

After the symbolization histogram/distribution has been obtained, the order α generalized entropy is computed from that sum-normalized symbol distribution.

Note: Do not confuse the order of the generalized entropy (α) with the order m of the permutation entropy (est.m, which controls the symbol size). Permutation entropy is usually estimated with α = 1, but the implementation here allows the generalized entropy of any dimension to be computed from the symbol frequency distribution.

Let $p$ be an array of probabilities (summing to 1). Then the Rényi entropy is

\[H_\alpha(p) = \frac{1}{1-\alpha} \log \left(\sum_i p[i]^\alpha\right)\]

and generalizes other known entropies, like e.g. the information entropy ($\alpha = 1$, see ^{[Shannon1948]}), the maximum entropy ($\alpha=0$, also known as Hartley entropy), or the correlation entropy ($\alpha = 2$, also known as collision entropy).

source

Entropies.probabilities — Method

probabilities(x::Dataset, est::SymbolicPermutation)
probabilities!(s::Vector{Int}, x::Dataset, est::SymbolicPermutation)

Compute the unordered probabilities of the occurrence of symbol sequences constructed from the data x. A pre-allocated symbol array s, where length(x) = length(s), can be provided to save some memory allocations if the probabilities are to be computed for multiple data sets.

source

Example

This example reproduces the permutation entropy example on the logistic map from Bandt and Pompe (2002).

using DynamicalSystems, PyPlot, Entropies

ds = Systems.logistic()
rs = 3.5:0.001:4
N_lyap, N_ent = 100000, 10000

# Generate one time series for each value of the logistic parameter r
lyaps, hs_entropies, hs_chaostools = Float64[], Float64[], Float64[]

for r in rs
    ds.p[1] = r
    push!(lyaps, lyapunov(ds, N_lyap))

    # For 1D systems `trajectory` returns a vector, so embed it using τs
    # to get the correct 6d dimension on the embedding
    x = trajectory(ds, N_ent)
    τs = ([-i for i in 0:6-1]...,) # embedding lags
    emb = genembed(x, τs)

    # Pre-allocate symbol vector, one symbol for each point in the embedding - this is faster!
    s = zeros(Int, length(emb));
    push!(hs_entropies, entropy!(s, emb, SymbolicPermutation(6, b = Base.MathConstants.e)))

    # Old ChaosTools.jl style estimation
    push!(hs_chaostools, permentropy(x, 6))
end

f = figure(figsize = (10,6))
a1 = subplot(311)
plot(rs, lyaps); ylim(-2, log(2)); ylabel("\$\\lambda\$")
a1.axes.get_xaxis().set_ticklabels([])
xlim(rs[1], rs[end]);

a2 = subplot(312)
plot(rs, hs_chaostools; color = "C1"); xlim(rs[1], rs[end]);
xlabel("\$r\$"); ylabel("\$h_6 (ChaosTools.jl)\$")

a3 = subplot(313)
plot(rs, hs_entropies; color = "C2"); xlim(rs[1], rs[end]);
xlabel("\$r\$"); ylabel("\$h_6 (Entropies.jl)\$")
tight_layout()
savefig("permentropy.png")

Utils

Some convenience functions for symbolization are provided.

Entropies.symbolize — Function

symbolize(x::Dataset{N, T}, est::SymbolicPermutation) where {N, T} → Vector{Int}

Symbolize the vectors in x using Algorithm 1 from Berger et al. (2019)^[Berger2019].

The symbol length is automatically determined from the dimension of the input data.

Example

Computing the order 5 permutation entropy for a 7-dimensional dataset.

using DelayEmbeddings, Entropies
D = Dataset([rand(7) for i = 1:1000])
symbolize(D, SymbolicPermutation(5))

source

Entropies.encode_motif — Function

encode_motif(x, m::Int = length(x))

Encode the length-m motif x (a vector of indices that would sort some vector v in ascending order) into its unique integer symbol, using Algorithm 1 in Berger et al. (2019)^[Berger2019].

Note: no error checking is done to see if length(x) == m, so be sure to provide the correct motif length!

Example

# Some random vector
v = rand(5)

# The indices that would sort `v` in ascending order. This is now a permutation 
# of the index permutation (1, 2, ..., 5)
x = sortperm(v)

# Encode this permutation as an integer.
encode_motif(x)

source

BandtPompe2002Bandt, Christoph, and Bernd Pompe. "Permutation entropy: a natural complexity measure for time series." Physical review letters 88.17 (2002): 174102.
Rényi1960A. Rényi, Proceedings of the fourth Berkeley Symposium on Mathematics, Statistics and Probability, pp 547 (1960)
Shannon1948C. E. Shannon, Bell Systems Technical Journal 27, pp 379 (1948)
Berger2019Berger, Sebastian, et al. "Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code." Entropy 21.10 (2019): 1023.
Berger2019Berger, Sebastian, et al. "Teaching Ordinal Patterns to a Computer: Efficient Encoding Algorithms Based on the Lehmer Code." Entropy 21.10 (2019): 1023.