サンプルエントロピーの計算コストが低い

サンプルエントロピーはエントロピーの最も一般的な定義であり、時系列の規則性/複雑さの尺度として広く使用されています。一方、これは、長いシリーズまたは多数の信号で使用される場合、大量の時間を必要とする計算上の高価な方法です。計算的に集中的な部分は、m寸法空間のポイント間の類似性チェックです。この論文では、サンプルエントロピーを迅速に計算することを目的とした新しいアルゴリズムを提案するか、すでに提案されているアルゴリズムを拡張します。すべてのアルゴリズムは、サンプルエントロピーの値とまったく同じ値を返し、近似技術は使用されません。心臓間（RR）時系列を使用してそれらを比較および評価します。3つのアルゴリズムを調査します。最初のものは、サンプルエントロピー用にカスタマイズされたK D -Treesアルゴリズムの拡張です。2つ目は、おおよそのエントロピー用に最初に提案されたアルゴリズムの拡張であり、サンプルエントロピー用に再びカスタマイズされましたが、さらに速い結果をもたらすために改善されました。最後のものは、まったく新しいアルゴリズムであり、M、R、時系列の長さ、および信号特性の特定の値に対して最も速い実行時間を提示します。これらのアルゴリズムは、達成されたスピードアップの明確な画像を提供するために、サンプルエントロピーの定義から直接生じる簡単な実装と比較されます。すべてのアルゴリズムは、最大標準が使用されるメトリックに対する古典的なアプローチを想定しています。最後に提案された2つのアルゴリズムの重要なアイデアは、それらを早期に検出することで不必要な比較を避けることです。私たちは、類似性チェックで失敗するという先験的な比較を参照するために、不要な用語を使用します。回避された比較の数は非常に大きいことが証明されているため、実行時間が類似して大幅に短縮され、サンプルエントロピーの計算のために今日利用可能な最速のアルゴリズムになります。

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 m 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 (RR) 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 m, r, 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 unnecessary 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.