permutation entropy

We calculate the permutation entropy of a time series by first decomposing the series into its dynamic elements. Specifically, for each moving block of length D, we characterize the block as one of D! possible sequences, using the function ordinal-idx. This function ranks the elements of the blocks. For example, a block of length D=5 would be ranked as follows:

(ordinal-idx [0 0 4 1 3]) => (0 1 3 4 2)

The ordinal-idx output sequence is then used as a bin, and we count the number of blocks in the original time series that fall within each of the D! bins:

(defn permutation-count
  "Returns a map of the ordinal sequences of length `D` and their
  count; note that the offset is fixed at 1"
  [D ts]
  (let [subs (partition D 1 ts)]
    (frequencies (map ordinal-idx subs))))

Note that the blocks are defined as the partitions of the time series of length D, where the window advances by one element to define a new block. If there are T periods, for example, there will be T - D + 1 blocks. We map the ordinal-idx across this sequence of blocks, and the permutation-count function will return a Clojure map that associates the bin (indexed by an ordinal sub-sequence) to the number of blocks that fall within that bin. There are D! key-value pairs in the returned map:

(permutation-count 5 random-ts) => {(0 1 2 3 4) 5, (0 1 2 4 3) 6, ... }

After this, we extract the values (the frequencies) from the returned map, and use them in the final, compound function:

(defn permutation-entropy
  "Normalixed permutation entropy based on the Shannon entropy
  distribution"
  [D ts]
  (let [pi-seq (to-freq (vals (permutation-count D ts)))
        scale-by (* -1 (/ 1 (i/log2 (i/factorial D))))]
    (* scale-by
       (reduce + (map log-fn pi-seq)))))

This function sums the scaled the frequencies from the permutation-count map, and then scales the sum again by the normalization factor to return the appropriate Shannon entropy value.