Approximate entropy

In statistics, an approximate entropy (ApEn) is a technique used to quantify the amount of regularity and the unpredictability of fluctuations over time-series data. ^[1] For example, consider two series of data:

Series A: (0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...), which alternates 0 and 1.

Series B: (0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, ...), which has either a value of 0 or 1, chosen randomly, each with probability 1/2.

Moment statistics, such as mean and variance, will not distinguish between these two series. Nor will rank order statistics distinguish between these series. Yet series A is perfectly regular: knowing a term has the value of 1 enables one to predict with certainty that the next term will have the value of 0. In contrast, series B is randomly valued: knowing a term has the value of 1 gives no insight into what value the next term will have.

Regularity was originally measured by exact regularity statistics, which has mainly centered on various entropy measures. ^[1] However, accurate entropy calculation requires vast amounts of data, and the results will be greatly influenced by system noise, ^[2] therefore it is not practical to apply these methods to experimental data. ApEn was first proposed (under a different name) by A. Cohen and I. Procaccia, ^[3] as an approximate algorithm to compute an exact regularity statistic, Kolmogorov–Sinai entropy, and later popularized by Steve M. Pincus. ApEn was initially used to analyze chaotic dynamics and medical data, such as heart rate, ^[1] and later spread its applications in finance, ^[4] physiology, ^[5] human factors engineering, ^[6] and climate sciences. ^[7]

Algorithm

A comprehensive step-by-step tutorial with an explanation of the theoretical foundations of Approximate Entropy is available. ^[8] The algorithm is:

Step 1

Assume a time series of data ${\displaystyle u(1),u(2),\ldots ,u(N)}$. These are ${\displaystyle N}$ raw data values from measurements equally spaced in time.

Step 2

Let ${\displaystyle m\in \mathbb {Z} ^{+}}$ be a positive integer, with ${\displaystyle m\leq N}$, which represents the length of a run of data (essentially a window).
Let ${\displaystyle r\in \mathbb {R} ^{+}}$ be a positive real number, which specifies a filtering level.
Let ${\displaystyle n=N-m+1}$.

Step 3

Define ${\displaystyle \mathbf {x} (i)={\big [}u(i),u(i+1),\ldots ,u(i+m-1){\big ]}}$ for each ${\displaystyle i}$ where ${\displaystyle 1\leq i\leq n}$. In other words, ${\displaystyle \mathbf {x} (i)}$ is an ${\displaystyle m}$-dimensional vector that contains the run of data starting with ${\displaystyle u(i)}$.
Define the distance between two vectors ${\displaystyle \mathbf {x} (i)}$ and ${\displaystyle \mathbf {x} (j)}$ as the maximum of the distances between their respective components, given by

${\displaystyle {\begin{aligned}d[\mathbf {x} (i),\mathbf {x} (j)]&=\max _{k}{\big (}|\mathbf {x} (i)_{k}-\mathbf {x} (j)_{k}|{\big )}\\&=\max _{k}{\big (}|u(i+k-1)-u(j+k-1)|{\big )}\\\end{aligned}}}$

for ${\displaystyle 1\leq k\leq m}$.

Step 4

Define a count ${\displaystyle C_{i}^{m}}$ as

${\displaystyle C_{i}^{m}(r)={({\text{number of }}j{\text{ such that }}d[\mathbf {x} (i),\mathbf {x} (j)]\leq r) \over n}}$

for each ${\displaystyle i}$ where ${\displaystyle 1\leq i,j\leq n}$. Note that since ${\displaystyle j}$ takes on all values between 1 and ${\displaystyle n}$, the match will be counted when ${\displaystyle j=i}$ (i.e. when the test subsequence, ${\displaystyle \mathbf {x} (j)}$, is matched against itself, ${\displaystyle \mathbf {x} (i)}$).

Step 5

Define

${\displaystyle \phi ^{m}(r)={1 \over n}\sum _{i=1}^{n}\log(C_{i}^{m}(r))}$

where ${\displaystyle \log }$ is the natural logarithm, and for a fixed ${\displaystyle m}$, ${\displaystyle r}$, and ${\displaystyle n}$ as set in Step 2.

Step 6

Define approximate entropy (${\displaystyle \mathrm {ApEn} }$) as

${\displaystyle \mathrm {ApEn} (m,r,N)(u)=\phi ^{m}(r)-\phi ^{m+1}(r)}$

Parameter selection

Typically, choose ${\displaystyle m=2}$ or ${\displaystyle m=3}$, whereas ${\displaystyle r}$ depends greatly on the application.

An implementation on Physionet, ^[9] which is based on Pincus, ^[2] use ${\displaystyle d[\mathbf {x} (i),\mathbf {x} (j)]<r}$ instead of ${\displaystyle d[\mathbf {x} (i),\mathbf {x} (j)]\leq r}$ in Step 4. While a concern for artificially constructed examples, it is usually not a concern in practice.

Example

Illustration of the Heart Rate Sequence

Consider a sequence of ${\displaystyle N=51}$ samples of heart rate equally spaced in time:

${\displaystyle \ S_{N}=\{85,80,89,85,80,89,\ldots \}}$

Note the sequence is periodic with a period of 3. Let's choose ${\displaystyle m=2}$ and ${\displaystyle r=3}$ (the values of ${\displaystyle m}$ and ${\displaystyle r}$ can be varied without affecting the result).

Form a sequence of vectors:

${\displaystyle {\begin{aligned}\mathbf {x} (1)&=[u(1)\ u(2)]=[85\ 80]\\\mathbf {x} (2)&=[u(2)\ u(3)]=[80\ 89]\\\mathbf {x} (3)&=[u(3)\ u(4)]=[89\ 85]\\\mathbf {x} (4)&=[u(4)\ u(5)]=[85\ 80]\\&\ \ \vdots \end{aligned}}}$

Distance is calculated repeatedly as follows. In the first calculation,

${\displaystyle \ d[\mathbf {x} (1),\mathbf {x} (1)]=\max _{k}|\mathbf {x} (1)_{k}-\mathbf {x} (1)_{k}|=0}$ which is less than ${\displaystyle r}$.

In the second calculation, note that ${\displaystyle |u(2)-u(3)|>|u(1)-u(2)|}$, so

${\displaystyle \ d[\mathbf {x} (1),\mathbf {x} (2)]=\max _{k}|\mathbf {x} (1)_{k}-\mathbf {x} (2)_{k}|=|u(2)-u(3)|=9}$ which is greater than ${\displaystyle r}$.

Similarly,

${\displaystyle {\begin{aligned}d[\mathbf {x} (1)&,\mathbf {x} (3)]=|u(2)-u(4)|=5>r\\d[\mathbf {x} (1)&,\mathbf {x} (4)]=|u(1)-u(4)|=|u(2)-u(5)|=0<r\\&\vdots \\d[\mathbf {x} (1)&,\mathbf {x} (j)]=\cdots \\&\vdots \\\end{aligned}}}$

The result is a total of 17 terms ${\displaystyle \mathbf {x} (j)}$ such that ${\displaystyle d[\mathbf {x} (1),\mathbf {x} (j)]\leq r}$. These include ${\displaystyle \mathbf {x} (1),\mathbf {x} (4),\mathbf {x} (7),\ldots ,\mathbf {x} (49)}$. In these cases, ${\displaystyle C_{i}^{m}(r)}$ is

${\displaystyle \ C_{1}^{2}(3)={\frac {17}{50}}}$

${\displaystyle \ C_{2}^{2}(3)={\frac {17}{50}}}$

${\displaystyle \ C_{3}^{2}(3)={\frac {16}{50}}}$

${\displaystyle \ C_{4}^{2}(3)={\frac {17}{50}}\ \cdots }$

Note in Step 4, ${\displaystyle 1\leq i\leq n}$ for ${\displaystyle \mathbf {x} (i)}$. So the terms ${\displaystyle \mathbf {x} (j)}$ such that ${\displaystyle d[\mathbf {x} (3),\mathbf {x} (j)]\leq r}$ include ${\displaystyle \mathbf {x} (3),\mathbf {x} (6),\mathbf {x} (9),\ldots ,\mathbf {x} (48)}$, and the total number is 16.

At the end of these calculations, we have

${\displaystyle \phi ^{2}(3)={1 \over 50}\sum _{i=1}^{50}\log(C_{i}^{2}(3))\approx -1.0982}$

Then we repeat the above steps for ${\displaystyle m=3}$. First form a sequence of vectors:

${\displaystyle {\begin{aligned}\mathbf {x} (1)&=[u(1)\ u(2)\ u(3)]=[85\ 80\ 89]\\\mathbf {x} (2)&=[u(2)\ u(3)\ u(4)]=[80\ 89\ 85]\\\mathbf {x} (3)&=[u(3)\ u(4)\ u(5)]=[89\ 85\ 80]\\\mathbf {x} (4)&=[u(4)\ u(5)\ u(6)]=[85\ 80\ 89]\\&\ \ \vdots \end{aligned}}}$

By calculating distances between vector ${\displaystyle \mathbf {x} (i),\mathbf {x} (j),1\leq i\leq 49}$, we find the vectors satisfying the filtering level have the following characteristic:

${\displaystyle d[\mathbf {x} (i),\mathbf {x} (i+3)]=0<r}$

Therefore,

${\displaystyle \ C_{1}^{3}(3)={\frac {17}{49}}}$

${\displaystyle \ C_{2}^{3}(3)={\frac {16}{49}}}$

${\displaystyle \ C_{3}^{3}(3)={\frac {16}{49}}}$

${\displaystyle \ C_{4}^{3}(3)={\frac {17}{49}}\ \cdots }$

At the end of these calculations, we have

${\displaystyle \phi ^{3}(3)={1 \over 49}\sum _{i=1}^{49}\log(C_{i}^{3}(3))\approx -1.0982}$

Finally,

${\displaystyle \mathrm {ApEn} =\phi ^{2}(3)-\phi ^{3}(3)\approx 0.000010997}$

The value is very small, so it implies the sequence is regular and predictable, which is consistent with the observation.

Python implementation

importmathdefapprox_entropy(time_series,run_length,filter_level)->float:"""    Approximate entropy    >>> import random    >>> regularly = [85, 80, 89] * 17    >>> print(f"{approx_entropy(regularly, 2, 3):e}")    1.099654e-05    >>> randomly = [random.choice([85, 80, 89]) for _ in range(17*3)]    >>> 0.8 < approx_entropy(randomly, 2, 3) < 1    True    """def_maxdist(x_i,x_j):returnmax(abs(ua-va)forua,vainzip(x_i,x_j))def_phi(m):n=time_series_length-m+1x=[[time_series[j]forjinrange(i,i+m-1+1)]foriinrange(time_series_length-m+1)]counts=[sum(1forx_jinxif_maxdist(x_i,x_j)<=filter_level)/nforx_iinx]returnsum(math.log(c)forcincounts)/ntime_series_length=len(time_series)returnabs(_phi(run_length+1)-_phi(run_length))if__name__=="__main__":importdoctestdoctest.testmod()

MATLAB implementation

• Fast Approximate Entropy from MatLab Central
• approximateEntropy

Interpretation

The presence of repetitive patterns of fluctuation in a time series renders it more predictable than a time series in which such patterns are absent. ApEn reflects the likelihood that similar patterns of observations will not be followed by additional similar observations. ^[10] A time series containing many repetitive patterns has a relatively small ApEn; a less predictable process has a higher ApEn.

Advantages

The advantages of ApEn include: ^[2]

• Lower computational demand. ApEn can be designed to work for small data samples (${\displaystyle N<50}$ points) and can be applied in real time.
• Less effect from noise. If data is noisy, the ApEn measure can be compared to the noise level in the data to determine what quality of true information may be present in the data.

Limitations

The ApEn algorithm counts each sequence as matching itself to avoid the occurrence of ${\displaystyle \log(0)}$ in the calculations. This step might introduce bias in ApEn, which causes ApEn to have two poor properties in practice: ^[11]

1. ApEn is heavily dependent on the record length and is uniformly lower than expected for short records.
2. It lacks relative consistency. That is, if ApEn of one data set is higher than that of another, it should, but does not, remain higher for all conditions tested.

Applications

ApEn has been applied to classify electroencephalography (EEG) in psychiatric diseases, such as schizophrenia, ^[12] epilepsy, ^[13] and addiction. ^[14]

See also

• Recurrence quantification analysis
• Sample entropy

References

1. Pincus, S. M.; Gladstone, I. M.; Ehrenkranz, R. A. (1991). "A regularity statistic for medical data analysis". Journal of Clinical Monitoring and Computing . 7 (4): 335–345. doi:10.1007/BF01619355. PMID   1744678. S2CID   23455856.
2. Pincus, S. M. (1991). "Approximate entropy as a measure of system complexity". Proceedings of the National Academy of Sciences . 88 (6): 2297–2301. Bibcode:1991PNAS...88.2297P. doi: 10.1073/pnas.88.6.2297 . PMC   51218 . PMID   11607165.
3. Cohen, A.; Procaccia, I. (1985). "Computing the Kolmogorov entropy from time signals of dissipative and conservative dynamical systems". Physical Review A . 28 (3): 2591(R). Bibcode:1985PhRvA..31.1872C. doi:10.1103/PhysRevA.31.1872.
4. Pincus, S.M.; Kalman, E.K. (2004). "Irregularity, volatility, risk, and financial market time series". Proceedings of the National Academy of Sciences . 101 (38): 13709–13714. Bibcode:2004PNAS..10113709P. doi: 10.1073/pnas.0405168101 . PMC   518821 . PMID   15358860.
5. Pincus, S.M.; Goldberger, A.L. (1994). "Physiological time-series analysis: what does regularity quantify?". The American Journal of Physiology . 266 (4): 1643–1656. doi:10.1152/ajpheart.1994.266.4.H1643. PMID   8184944. S2CID   362684.
6. McKinley, R.A.; McIntire, L.K.; Schmidt, R; Repperger, D.W.; Caldwell, J.A. (2011). "Evaluation of Eye Metrics as a Detector of Fatigue". Human Factors . 53 (4): 403–414. doi:10.1177/0018720811411297. PMID   21901937. S2CID   109251681.
7. Delgado-Bonal, Alfonso; Marshak, Alexander; Yang, Yuekui; Holdaway, Daniel (2020-01-22). "Analyzing changes in the complexity of climate in the last four decades using MERRA-2 radiation data". Scientific Reports. 10 (1): 922. Bibcode:2020NatSR..10..922D. doi: 10.1038/s41598-020-57917-8 . ISSN   2045-2322. PMC   6976651 . PMID   31969616.
8. Delgado-Bonal, Alfonso; Marshak, Alexander (June 2019). "Approximate Entropy and Sample Entropy: A Comprehensive Tutorial". Entropy. 21 (6): 541. Bibcode:2019Entrp..21..541D. doi: 10.3390/e21060541 . PMC   7515030 . PMID   33267255.
9. "PhysioNet". Archived from the original on 2012-06-18. Retrieved 2012-07-04.
10. Ho, K. K.; Moody, G. B.; Peng, C.K.; Mietus, J. E.; Larson, M. G.; levy, D; Goldberger, A. L. (1997). "Predicting survival in heart failure case and control subjects by use of fully automated methods for deriving nonlinear and conventional indices of heart rate dynamics". Circulation . 96 (3): 842–848. doi:10.1161/01.cir.96.3.842. PMID   9264491.
11. Richman, J.S.; Moorman, J.R. (2000). "Physiological time-series analysis using approximate entropy and sample entropy". American Journal of Physiology. Heart and Circulatory Physiology . 278 (6): 2039–2049. doi:10.1152/ajpheart.2000.278.6.H2039. PMID   10843903. S2CID   2389971.
12. Sabeti, Malihe (2009). "Entropy and complexity measures for EEG signal classification of schizophrenic and control participants". Artificial Intelligence in Medicine . 47 (3): 263–274. doi:10.1016/j.artmed.2009.03.003. PMID   19403281.
13. Yuan, Qi (2011). "Epileptic EEG classification based on extreme learning machine and nonlinear features". Epilepsy Research . 96 (1–2): 29–38. doi:10.1016/j.eplepsyres.2011.04.013. PMID   21616643. S2CID   41730913.
14. Yun, Kyongsik (2012). "Decreased cortical complexity in methamphetamine abusers". Psychiatry Research: Neuroimaging . 201 (3): 226–32. doi:10.1016/j.pscychresns.2011.07.009. PMID   22445216. S2CID   30670300.