Manis George, Aktaruzzaman Md, Sassi Roberto
Department of Computer Science and Engineering, University of Ioannina, Ioannina 45110, Greece.
Department of Computer Science and Engineering, Islamic University Kushtia, Kushtia 7003, Bangladesh.
Entropy (Basel). 2018 Jan 13;20(1):61. doi: 10.3390/e20010061.
Sample Entropy is the most popular definition of entropy and is widely used as a measure of the regularity/complexity of a time series. On the other hand, it is a computationally expensive method which may require a large amount of time when used in long series or with a large number of signals. The computationally intensive part is the similarity check between points in dimensional space. In this paper, we propose new algorithms or extend already proposed ones, aiming to compute Sample Entropy quickly. All algorithms return exactly the same value for Sample Entropy, and no approximation techniques are used. We compare and evaluate them using cardiac inter-beat () time series. We investigate three algorithms. The first one is an extension of the k d -trees algorithm, customized for Sample Entropy. The second one is an extension of an algorithm initially proposed for Approximate Entropy, again customized for Sample Entropy, but also improved to present even faster results. The last one is a completely new algorithm, presenting the fastest execution times for specific values of , , time series length, and signal characteristics. These algorithms are compared with the straightforward implementation, directly resulting from the definition of Sample Entropy, in order to give a clear image of the speedups achieved. All algorithms assume the classical approach to the metric, in which the maximum norm is used. The key idea of the two last suggested algorithms is to avoid unnecessary comparisons by detecting them early. We use the term to refer to those comparisons for which we know a priori that they will fail at the similarity check. The number of avoided comparisons is proved to be very large, resulting in an analogous large reduction of execution time, making them the fastest algorithms available today for the computation of Sample Entropy.
样本熵是最流行的熵的定义，被广泛用作衡量时间序列的规律性/复杂性的指标。另一方面，它是一种计算成本高昂的方法，在处理长序列或大量信号时可能需要大量时间。计算密集的部分是在高维空间中各点之间的相似性检查。在本文中，我们提出了新的算法或扩展了已有的算法，旨在快速计算样本熵。所有算法返回的样本熵值完全相同，并且未使用近似技术。我们使用心脏搏动间期（）时间序列对它们进行比较和评估。我们研究了三种算法。第一种是kd - 树算法的扩展，专为样本熵定制。第二种是最初为近似熵提出的算法的扩展，同样专为样本熵定制，但也进行了改进以获得更快的结果。最后一种是全新的算法，对于特定的嵌入维度、容忍度、时间序列长度和信号特征，它具有最快的执行时间。将这些算法与直接根据样本熵定义得出的直接实现方式进行比较，以便清晰地展示所实现的加速效果。所有算法都采用经典的度量方法，即使用最大范数。最后两种算法的关键思想是通过尽早检测来避免不必要的比较。我们使用术语“无效比较”来指代那些我们事先知道在相似性检查中会失败的比较。事实证明，避免的比较数量非常大，从而导致执行时间大幅减少，使它们成为目前计算样本熵最快的算法。
