歩数検出

統計と信号処理において、ステップ検出（ステップ平滑化、ステップフィルタリング、シフト検出、ジャンプ検出、エッジ検出とも呼ばれる）は、時系列または信号の平均レベルの急激な変化（ステップ、ジャンプ、シフト）を見つけるプロセスです。これは通常、変化検出または変化点検出として知られる統計的手法の特殊なケースと見なされます。多くの場合、ステップは小さく、時系列は何らかのノイズによって破損しており、ステップがノイズに隠れてしまう可能性があるため、問題は困難になります。そのため、統計アルゴリズムや信号処理アルゴリズムが必要になることがよくあります。

ステップ検出問題は、統計的プロセス制御^[1] (管理図が最も直接的に関連する方法)、探査地球物理学(坑井ログ記録を地層帯に分割する問題^[2] )、遺伝学(マイクロアレイデータを類似のコピー数領域に分離する問題[ ^3] )、生物物理学 (時間位置トレースに記録された分子機械の状態遷移を検出する^[4] )など、さまざまな科学的および工学的コンテキストで発生します。2D 信号の場合、エッジ検出の関連問題は、画像処理のために集中的に研究されてきました。^[5]

データが到着した時点でステップ検出を実行する必要がある場合、通常はオンラインアルゴリズムが使用され、^[6] これは逐次分析の特殊なケースになります。このようなアルゴリズムには、平均値の変化に適用される 古典的なCUSUM法が含まれます。 ^[7]

対照的に、オフラインアルゴリズムは、データが受信されてからかなり経ってからデータに適用されます。デジタル データ内のステップ検出用のオフライン アルゴリズムのほとんどは、トップダウン、ボトムアップ、スライディング ウィンドウ、またはグローバルメソッドに分類できます。

これらのアルゴリズムは、ステップがないという仮定から始まり、可能な候補ステップを1つずつ導入し、各候補をテストして、いくつかの基準（推定された基礎となる区分定数信号の最小二乗適合など）を最小化するステップを見つけます。一例として、 ステップワイズジャンプ配置アルゴリズムがあります。これは、地球物理学の問題で最初に研究され、^[2]最近では現代の生物物理学で使用されています。^[8]

ボトムアップ アルゴリズムはトップダウン方式とは「逆の」アプローチを採用し、最初にデジタル信号の各サンプル間にステップがあると想定し、次に候補となるすべてのマージに対してテストされたいくつかの基準に基づいてステップを連続的にマージします。

これらのアルゴリズムは、信号の小さな「ウィンドウ」を検討することで、ウィンドウ内で発生するステップの証拠を探します。ウィンドウは、1 回に 1 つの時間ステップずつ、時系列を「スライド」します。ステップの証拠は、統計的手順、たとえば 2 サンプルのStudent t 検定を使用してテストされます。または、メジアン フィルターなどの非線形フィルターを信号に適用します。このようなフィルターは、突然のステップを保持しながらノイズを除去しようとします。

グローバルアルゴリズムは、信号全体を一度に考慮し、何らかの最適化手順によって信号内のステップを見つけようとします。アルゴリズムには、ウェーブレット法^[9]や、凸最適化の方法を使用する全変動ノイズ除去などがあります。ステップをマルコフ連鎖としてモデル化できる場合は、隠れマルコフモデルもよく使用されます（生物物理学コミュニティで人気のあるアプローチ^[10]）。平均値の一意の値が少数しかない場合は、k平均法クラスタリングも使用できます。

ステップと（独立した）ノイズは理論的には無限の帯域幅を持ち、フーリエ基底で重なり合うため、ステップ検出のための信号処理アプローチでは、通常、ローパスフィルタなどの古典的な平滑化手法は使用されません。代わりに、ほとんどのアルゴリズムは明示的に非線形または時間変動型です。^[11]

ステップ検出の目的は、信号の平均における一連の瞬間的なジャンプを見つけることであるため、必要な基礎となる平均信号は区分的に一定です。このため、ステップ検出は、ノイズによって破損した区分的に一定の信号を回復する問題として有益に考えることができます。区分的に一定の信号には、いくつかのノットを持つ0 度スプライン、またはいくつかの一意のレベルを持つレベル セットという 2 つの補完モデルがあります。したがって、ステップ検出の多くのアルゴリズムは、0 度スプライン フィッティングまたはレベル セット回復方法として理解するのが最適です。

平均値の一意の値が少数しかない場合は、k-means クラスタリングや平均シフトなどのクラスタリング手法が適しています。これらの手法は、基礎となる区分定数信号のレベル セット記述を見つけるための方法として理解するのが最適です。

多くのアルゴリズムは、ステップを検出するために、ノイズの多い信号に0度スプラインを明示的に当てはめます（ステップワイズジャンプ配置法^{[2] [8]を含む）が、}全変動ノイズ除去^[12]など、何らかの変換を行った後にスプラインフィッティング法と見なすことができる他の一般的なアルゴリズムもあります。

上記のアルゴリズムはすべて、特定の状況では特定の利点と欠点を持っていますが、これらのステップ検出アルゴリズムの驚くほど多くのものは、より一般的なアルゴリズムの特殊なケースです。^[11]このアルゴリズムは、グローバル関数の最小化を伴います。^[13]

ここで、x _i ( i  = 1, ....,  N )は長さNの離散時間入力信号、m _{i は}アルゴリズムから出力される信号です。目標は、出力信号mに関して H [ m ] を最小化することです。関数の形式によって、特定のアルゴリズムが決まります。たとえば、次のように選択します。 ${\displaystyle \scriptstyle \Lambda }$

${\displaystyle \Lambda ={\frac {1}{2}}\left|x_{i}-m_{j}\right|^{2}I(i-j=0)+\gamma \left|m_{i}-m_{j}\right|I(i-j=1)}$

ここで、条件Sが偽の場合はI ( S ) = 0 となり、それ以外の場合は 1 となり、正規化パラメータを持つ全変動ノイズ除去アルゴリズムが得られます。同様に、 ${\displaystyle \gamma }$

${\displaystyle \Lambda =\min \left\{{\frac {1}{2}}\left|m_{i}-m_{j}\right|^{2},W\right\}}$

入力信号 xで初期化された適応ステップサイズオイラー積分器を使用すると、平均シフトアルゴリズムにつながります。^[13]ここでW  > 0は平均シフトカーネルのサポートを決定するパラメータです。別の例は次のとおりです。

${\displaystyle \Lambda ={\frac {1-\exp(-\beta |m_{i}-m_{j}|^{2}/2)}{\beta }}\cdot I(|i-j|\leq W)}$

双対フィルタにつながります。ここで は音調カーネルパラメータ、W は空間カーネルサポートです。さらに別の特殊なケースは次のとおりです。 ${\displaystyle \scriptstyle \beta >0}$

${\displaystyle \Lambda ={\frac {1}{2}}\left|x_{i}-m_{j}\right|^{2}I(i-j=0)+\gamma \left|m_{i}-m_{j}\right|^{0}I(i-j=1)}$

信号に貪欲に0度スプラインを当てはめようとするアルゴリズムのグループを指定します。^{[2] [8]}ここで、x  = 0の場合は0、それ以外の 場合は1と定義されます。${\displaystyle \scriptstyle \left|x\right|^{0}}$

の特定の選択によって定義される式（ 1 ）の関数の多くは凸関数であり、凸最適化の方法を使用して最小化することができます。他の関数は非凸関数ですが、これらの関数を最小化するさまざまなアルゴリズムが考案されています。^[13]${\displaystyle \scriptstyle \Lambda }$

ステップ検出のための古典的な変分法はポッツモデルである。これは非凸最適化問題によって与えられる。

${\displaystyle u^{*}=\arg \min _{u\in \mathbb {R} ^{N}}\gamma \|\nabla u\|_{0}+\|u-x\|_{p}^{p}}$

項は ジャンプの数にペナルティを課し、項はデータxへの忠実度を測定します。パラメータ γ > 0 は、規則性とデータ忠実度のトレードオフを制御します。最小化器は区分的に一定であるため、ステップは勾配の非ゼロ位置によって与えられます。およびについては、におけるポッツ問題の正確な解を与える高速アルゴリズムがあります 。 ^{[14] [15] [16] [17]}${\displaystyle \|\nabla u\|_{0}=\#\{i:u_{i}\neq u_{i+1}\}}$${\displaystyle \|u-x\|_{p}^{p}=\sum _{i=1}^{N}|u_{i}-x_{i}|^{p}}$${\displaystyle u^{*}}$${\displaystyle \nabla u^{*}}$${\displaystyle p=2}$${\displaystyle p=1}$${\displaystyle O(N^{2})}$

• 時系列セグメンテーション

• PWCTools: 区分定数ノイズ除去によるステップ検出のための柔軟な Matlab および Python ソフトウェア
• Pottslab: Potts モデルに基づく区分定数推定のための Matlab ツールボックス