ホームページ >テクノロジー周辺機器 >AI >8つの時系列分類方法のまとめ
8つの時系列分類方法のまとめ
- 王林転載
- 2023-05-06 10:04:061896ブラウズ
時系列の分類は、機械学習および深層学習モデルを適用するための一般的なタスクの 1 つです。この記事では8種類の時系列分類方法について説明します。これは、単純な距離またはマージンに基づく方法から、ディープ ニューラル ネットワークを使用する方法まで多岐にわたります。この記事は、すべての時系列分類アルゴリズムの参考記事として機能することを目的としています。
- 単一変数 TS は、(通常は) 実数値の順序付きセットです。
- 多変量 TS は、一変量 TS のセットです。各タイムスタンプは実数値のベクトルまたは配列です。
- p ノルム (マンハッタン距離、ユークリッド距離など)
- 動的タイム ワーピング (DTW)
- # #Afterメトリックを決定する際には、通常、k 近傍 (KNN) アルゴリズムが適用され、新しい TS とトレーニング データ セット内のすべての TS の間の距離が測定されます。すべての距離を計算した後、最も近い k 個の距離を選択します。最後に、新しい TS は、k 個の最近傍の過半数が属するクラスに割り当てられます。
最も一般的なノルムは間違いなく p ノルム、特にユークリッド距離ですが、TS 分類タスクには適さないという 2 つの大きな欠点があります。ノルムは同じ長さの 2 つの TS に対してのみ定義されるため、実際には同じ長さのシーケンスを取得できるとは限りません。標準では各時点の 2 つの TS 値を個別に比較するだけですが、ほとんどの TS 値は相互に相関しています。
そして、DTW は p ノルムの 2 つの制限を解決できます。 Classic DTW は、タイムスタンプが異なる可能性がある 2 つの時系列ポイント間の距離を最小限に抑えます。これは、わずかにずれたり歪んだ TS も同様であるとみなされることを意味します。以下の図は、p ノルム ベースのメトリクスと DTW の仕組みの違いを視覚化したものです。
KNN と組み合わせた DTW は、TS 分類のさまざまなベンチマーク評価のベースライン アルゴリズムとして使用されます。
KNN は、決定木手法を使用して実装することもできます。たとえば、近隣フォレスト アルゴリズムは、距離測定を使用して TS データを分割するデシジョン ツリーのフォレストをモデル化します。
間隔ベースの方法と周波数ベースの方法
間隔ベースの方法では、通常、TS が複数の異なる間隔に分割されます。各サブシーケンスは、個別の機械学習 (ML) 分類器をトレーニングするために使用されます。分類子のセットが生成され、各分類子は独自の間隔で動作します。個別に分類されたサブシリーズ間で最も一般的なクラスを計算すると、時系列全体の最終ラベルが返されます。
時系列フォレスト
間隔ベースのモデルの最も有名な代表は、時系列フォレストです。 TSF は、初期 TS のランダムなサブシーケンスに基づいて構築された決定木のコレクションです。各ツリーは、クラスを範囲に割り当てる役割を果たします。
これは、要約特徴 (通常、平均、標準偏差、および傾き) を計算して、各区間の特徴ベクトルを作成することによって行われます。次に、計算された特徴に基づいてデシジョン ツリーがトレーニングされ、すべてのツリーの多数決によって予測が得られます。各ツリーは初期 TS の特定のサブシーケンスのみを評価するため、投票プロセスが必要です。
TSF に加えて、他の間隔ベースのモデルもあります。 TSF のバリアントでは、サブシリーズの中央値、四分位範囲、最小値と最大値などの追加機能が使用されます。古典的な TSF アルゴリズムと比較すると、Random Interval Spectral Ensemble (RISE) アルゴリズムと呼ばれるかなり複雑なアルゴリズムがあります。
RISE
RISE アルゴリズムは、2 つの点で従来の TS フォレストとは異なります。
各ツリーは単一の TS 間隔を使用します- (平均、傾きなどの概要統計を使用する代わりに) TS から抽出されたスペクトル特徴を使用してトレーニングされます
- RISE テクノロジーでは、各デシジョン ツリーは、フーリエ、自己相関、自己回帰、部分自己相関のさまざまな機能セットに基づいて構築されます。アルゴリズムは次のように機能します:
TS の最初のランダムな間隔を選択し、これらの間隔で上記の特徴を計算します。次に、抽出された特徴を組み合わせて新しいトレーニング セットが作成されます。これらに基づいて、決定木分類器がトレーニングされます。これらのステップは最終的に、さまざまな構成を使用して繰り返され、単一の決定木分類器のランダム フォレストであるアンサンブル モデルが作成されます。
辞書ベースの方法
辞書ベースのアルゴリズムは、辞書の構造に基づく別のタイプの TS 分類器です。これらは多数の異なる分類子をカバーしており、場合によっては上記の分類子と組み合わせて使用できます。
対象となる辞書ベースの手法のリストは次のとおりです:
- バッグオブパターン (BOP)
- シンボリックフーリエ近似 (SFA)
- 個別の BOSS
- BOSS アンサンブル
- ベクトル空間の BOSS
- 契約可能な BOSS
- ランダムな BOSS
- WEASEL
このタイプの方法では、通常、最初に TS をシンボル シーケンスに変換し、スライディング ウィンドウを通じてそこから「単語」を抽出します。最終的な分類は、「単語」の分布を決定することによって行われます。これは通常、「単語」を数えて並べ替えることによって行われます。このアプローチの背後にある理論は、時系列は類似している、つまり、類似した「単語」が含まれている場合は同じクラスに属することを意味します。辞書ベースの分類器の主なプロセスは通常同じです。
- TS で特定の長さのスライディング ウィンドウを実行します。
- 各サブシーケンスを (特定の長さと固定文字セットを含む) 「単語」に変換します。
- これらのヒストグラムを作成します
最も一般的な辞書ベースの分類器のリストを次に示します:
Bag-of-Patterns アルゴリズム
Bag-of-Patterns (BOP) アルゴリズムは、テキスト データの分類に使用される Bag-of-Words アルゴリズムと同様に機能します。このアルゴリズムは、単語の出現回数をカウントします。
数値 (ここでは生の TS) から単語を作成するための最も一般的な手法は、記号集約近似 (SAX) と呼ばれます。 TS は最初に異なるブロックに分割され、各ブロックは正規化されます。つまり、ブロックの平均は 0、標準偏差は 1 になります。
通常、単語の長さは、サブシーケンス内の実際の値の数よりも長くなります。したがって、各ブロックに対してさらにビニングが適用される。次に、各ビンの実際の平均値が計算され、文字にマッピングされます。たとえば、-1 未満のすべての値には文字「a」が割り当てられ、-1 を超え 1 未満のすべての値は「b」、1 を超えるすべての値は「c」になります。以下の画像は、このプロセスを視覚化したものです。
ここでは、各セグメントには 30 個の値が含まれており、これらの値は 6 個のグループに分割され、各グループには 3 つの可能な文字が割り当てられ、5 文字の単語が形成されます。各単語の出現数は最終的に要約され、最近傍アルゴリズムに挿入することによって分類に使用されます。
シンボリックフーリエ近似
上記の BOP アルゴリズムの考え方とは異なり、BOP アルゴリズムでは、元の TS が文字、単語の順に離散化され、同様のフーリエ係数を適用できます。 TS方式へ。
最も有名なアルゴリズムは記号フーリエ近似 (SFA) で、2 つの部分に分けることができます。
計算された係数のサブセットを保持しながら、TS の離散フーリエ変換を計算します。
- 教師あり: 単変量特徴選択は、統計 (F 統計や χ2 統計など) に基づいて上位の係数を選択するために使用されます。
- 教師なし: 通常、最初の係数が取得されます。 TS
- 監視: インスタンス エントロピーの不純物基準が最小化されるようにビニング エッジを計算します。
- 教師なし: フーリエ係数の極値に基づいて (ビンは均一です)、またはこれらの分位数に基づいてビンのエッジを計算します (各ビンの係数の数は同じです)
- スライディングを通じて TS のサブシーケンスを抽出します。ウィンドウ メカニズム
- 各セグメントに SFA 変換を適用し、順序付けられた単語のセットを返します。
- 各単語の頻度を計算し、TS 単語のヒストグラムを生成します。
- 適用することにより、 KNN など。アルゴリズムは、分類のためにカスタム BOSS メトリック (ユークリッド距離の小さな変化) を組み合わせます。
Contractable BOSS
Contractable BOSS (cBOSS) アルゴリズムは、従来の BOSS メソッドよりも計算がはるかに高速です。
高速化は、パラメーター空間全体に対してグリッド検索を実行するのではなく、そこからランダムに選択されたサンプルに対してグリッド検索を実行することによって実現されます。 cBOSS は、各基本分類子のデータのサブサンプルを使用します。 cBOSS は、特定のパフォーマンスしきい値を超えるすべての分類子ではなく、固定数の最良の基本分類子のみを考慮することでメモリ効率を向上させます。
ランダム化 BOSS
BOSS アルゴリズムの次のバリエーションは、ランダム化 BOSS (RBOSS) です。この方法では、スライディング ウィンドウの長さの選択に確率的プロセスが追加され、個々の BOSS 分類子の予測が巧みに集約されます。これは cBOSS バリアントに似ており、ベースラインのパフォーマンスを維持しながら計算時間を短縮します。
WEASE
TS 分類子抽出 (WEASEL) アルゴリズムは、SFA 変換で異なる長さのスライディング ウィンドウを使用することにより、標準 BOSS メソッドのパフォーマンスを向上させることができます。他の BOSS 亜種と同様に、さまざまな長さのウィンドウ サイズを使用して TS を特徴ベクトルに変換し、その後 KNN 分類器によって評価されます。
WEASEL は、特定の特徴導出方法を使用し、χ2 検定を適用する各スライディング ウィンドウの重複しないサブシーケンスのみを使用して、最も関連性の高い特徴をフィルターで除外します。
WEASEL と多変量教師なしシンボル (WEASEL MUSE) を組み合わせて、コンテキスト情報を各特徴にエンコードすることで TS から多変量特徴を抽出およびフィルター処理します。
シェイプレット ベースの方法
シェイプレット ベースの方法では、初期時系列のサブシーケンス (つまりシェイプレット) のアイデアが使用されます。シェイプレットは、クラスの代表として使用するために選択されます。これは、シェイプレットには、異なるクラスを区別するために使用できるクラスの主な特性が含まれていることを意味します。最適な場合には、同じクラス内の TS 間の局所的な類似性を検出できます。
次の図は、シェイプレットの例を示しています。これは TS 全体の単なるサブシーケンスです。
シェイプレットに基づくアルゴリズムを使用するには、どのシェイプレットを使用するかを決定する必要があります。シェイプレットのセットを手動で作成して選択することも可能ですが、これは非常に難しい場合があります。シェイプレットは、さまざまなアルゴリズムを使用して自動的に選択することもできます。
Shapelet 抽出に基づくアルゴリズム
Shapelet Transform は、Lines らによって提案された Shapelet 抽出に基づくアルゴリズムであり、現在最も一般的に使用されているアルゴリズムの 1 つです。 n 個の実数値観測値の TS が与えられると、シェイプレットは長さ l の TS のサブセットによって定義されます。
シェイプレットと TS 全体の間の最小距離は、ユークリッド距離 (またはその他の距離メトリック) を使用して測定できます。シェイプレット自体と、TS から始まる長さ l のすべてのシェイプレットの間の距離です。
次に、アルゴリズムは、長さが特定の範囲内にある k 個の最良のシェイプレットを選択します。このステップは、ある種の一変量特徴抽出とみなすことができ、各特徴はシェイプレットと特定のデータセット内のすべての TS の間の距離によって定義されます。次に、シェイプレットはいくつかの統計に基づいてランク付けされます。これらは通常、クラスを区別する能力に従ってシェイプレットをランク付けする f 統計または χ² 統計です。
上記の手順を完了すると、任意のタイプの ML アルゴリズムを適用して、新しいデータ セットを分類できます。たとえば、knn ベースの分類器、サポート ベクター マシン、ランダム フォレストなどです。
理想的なシェイプレットを見つける際のもう 1 つの問題は、トレーニング サンプルの数に応じて指数関数的に増加する、ひどい時間計算量です。
Shapelet 学習ベースのアルゴリズム
Shapelet 学習ベースのアルゴリズムは、Shapelet 抽出に基づくアルゴリズムの制限を解決しようとします。このアイデアは、クラスを特定のデータセットから直接抽出するのではなく、クラスを区別できる一連のシェイプレットを学習することです。
これを行うと、主に 2 つの利点があります。
- トレーニング セットには含まれていないが、カテゴリを強く区別するシェイプレットを取得できます。
- データセット全体に対してアルゴリズムを実行する必要がないため、トレーニング時間を大幅に短縮できます
しかし、このアプローチには、微分可能な最小化関数と選択された分類子の欠点。
ユークリッド距離を置き換えるには、勾配降下法または逆伝播アルゴリズムを通じてシェイプレットを学習できるように、微分可能関数に依存する必要があります。最も一般的なのは、引数の指数の合計の対数を取得することで最大値を滑らかに近似する LogSumExp 関数に依存します。 LogSumExp 関数は厳密には凸ではないため、最適化アルゴリズムが正しく収束しない可能性があり、不正な極小値が発生する可能性があります。
そして、最適化プロセス自体がアルゴリズムの主要コンポーネントであるため、調整のために複数のハイパーパラメーターを追加する必要があります。
しかし、この方法は実際には非常に便利で、データに対して新しい洞察を生み出すことができます。
カーネル ベースのアプローチ
シェイプレット ベースのアルゴリズムのわずかなバリエーションが、カーネル ベースのアルゴリズムです。特定の TS から特徴を抽出するランダム コンボリューション カーネル (最も一般的なコンピューター ビジョン アルゴリズム) を学習して使用します。
ランダム コンボリューション カーネル変換 (ROCKET) アルゴリズムは、この目的のために特別に設計されています。 。これは、長さ、重み、バイアス、拡張、およびパディングが異なる多数のカーネルを使用し、固定分布からランダムに作成されます。
カーネルを選択した後、クラスを区別するために最も関連性の高い特徴を選択できる分類器も必要です。元の論文では、予測を実行するためにリッジ回帰 (線形回帰の L2 正規化変種) が使用されました。これを使用する利点は 2 つあります。1 つは、マルチクラス分類問題であっても計算効率が高いこと、2 つ目は、相互検証を使用して固有の正則化ハイパーパラメータを微調整することが簡単であることです。
カーネルベースのアルゴリズムまたは ROCKET アルゴリズムを使用する主な利点の 1 つは、それらを使用する際の計算コストが非常に低いことです。
特徴ベースの方法
特徴ベースの方法は、通常、特定の時系列に対して何らかの種類の特徴抽出を使用するほとんどのアルゴリズムをカバーでき、分類アルゴリズムによって予測が実行されます。
特徴については、単純な統計特徴からより複雑なフーリエベースの特徴まで。このような機能の多くは hctsa (https://github.com/benfulcher/hctsa) で見つけることができますが、特に大規模なデータセットの場合、各機能を試して比較することは不可能な作業になる可能性があります。そこで、典型的な時系列特徴量（catch22）アルゴリズムが提案されました。
catch22 アルゴリズム
この方法は、強力な分類パフォーマンスを必要とするだけでなく、冗長性をさらに最小限に抑えるために、小規模な TS 特徴セットを推論することを目的としています。 catch22 は、hctsa ライブラリから合計 22 の機能を選択しました (ライブラリには 4000 以上の機能が提供されています)。
このメソッドの開発者は、93 の異なるデータセットでさまざまなモデルをトレーニングして 22 個の特徴を取得し、それらのセットで最もパフォーマンスの高い TS 特徴を評価することで、依然として優れたパフォーマンスを維持する子を取得しました。分類子は自由に選択できるため、調整するもう 1 つのハイパーパラメータになります。
マトリックス プロファイル分類子
もう 1 つの機能ベースのメソッドは、マトリックス プロファイル (MP) 分類子であり、解釈可能な結果を提供しながらベースライン パフォーマンスを維持できる、解釈可能な MP ベースの TS 分類子です。
設計者は、シェイプレットベースの分類子から Matrix Profile という名前のモデルを抽出しました。このモデルは、TS のサブシーケンスとその最近傍間のすべての距離を表します。このようにして、MP は、互いによく似た TS の部分配列であるモチーフや、互いに異なる配列を表す不協和音などの TS の特徴を効果的に抽出することができます。
理論的な分類モデルとしては、任意のモデルを使用できます。この方法の開発者は決定木分類器を選択しました。
前述の 2 つの方法に加えて、sktime はさらにいくつかの機能ベースの TS 分類子も提供します。
モデル アンサンブル
モデル アンサンブルは、それ自体はスタンドアロンのアルゴリズムではありませんが、さまざまな TS 分類器を組み合わせて、より適切に組み合わせられた予測を作成する手法です。モデル アンサンブルは、多数のデシジョン ツリーを使用するランダム フォレストと同様に、複数の個別のモデルを組み合わせることで分散を削減します。また、さまざまなタイプの異なる学習アルゴリズムを使用すると、学習される特徴の範囲がより広範かつ多様になり、それがクラスの識別の向上につながります。
最も人気のあるモデル アンサンブルは、Hierarchical Vote Collective of Transformation-based Ensembles (HIVE-COTE) です。これには、さまざまな種類の同様のバージョンが存在しますが、共通しているのは、各分類子の加重平均を使用して、異なる分類子からの情報、つまり予測を組み合わせていることです。
Sktime は 2 つの異なる HIVE-COTE アルゴリズムを使用します。1 つ目は、シェイプレット変換分類子 (STC)、TS フォレスト、RISE、および cBOSS を含む推定器ごとの確率を組み合わせます。 2 つ目は、STC、Diverse Canonical Interval Forest Classifier (DrCIF、TS Forest のバリアント)、Arsenal (ROCKET モデルのコレクション)、および TDE (BOSS アルゴリズムのバリアント) の組み合わせによって定義されます。
最終的な予測は、CAWPE アルゴリズムによって取得されます。このアルゴリズムは、トレーニング データ セットで見つかった分類器の相対推定品質によって取得された各分類器に重みを割り当てます。
次の図は、HIVE-COTE アルゴリズムの動作構造を視覚化するために使用される一般的な図です:
深層学習ベースの手法
深層学習に基づくアルゴリズムについて、各アーキテクチャの詳細をすべて説明するには、独自の長い記事を書くことができます。ただし、この記事では、一般的に使用される TS 分類ベンチマーク モデルと手法の一部のみを提供します。
深層学習ベースのアルゴリズムは非常に人気があり、コンピューター ビジョンや NLP などの分野で広く研究されていますが、TS 分類の分野ではあまり一般的ではありません。ファワズら。 TS 分類のための深層学習に関する論文で、現在の既存の手法を徹底的に研究しました: 概要 6 つのアーキテクチャを持つ 60 以上のニューラル ネットワーク (NN) モデルが研究されました:
- 多層パーセプトロン
- 完全畳み込み NN (CNN)
- エコーステート ネットワーク (リカレント NN に基づく)
- エンコーダー
- マルチスケール ディープ CNN
- Time CNN
上記のモデルのほとんどは、もともとさまざまなユースケース向けに開発されました。したがって、さまざまなユースケースに応じてテストする必要があります。
2020 年には、InceptionTime ネットワークも開始されました。 InceptionTime は 5 つの深層学習モデルのアンサンブルであり、それぞれが Szegedy らによって最初に提案された InceptionTime によって作成されました。これらの初期モジュールは、TS の短いサブシーケンスと長いサブシーケンスから関連する特徴と情報を抽出しながら、異なる長さの複数のフィルターを TS に同時に適用します。次の図は、InceptionTime モジュールを示しています。
これは、フィードフォワード方式でスタックされ、残差と接続された複数の初期モジュールで構成されます。最後に、グローバル平均プーリングと完全に接続されたニューラル ネットワークによって予測結果が生成されます。
下の図は、単一の初期モジュールの動作を示しています。
概要
この記事でまとめたアルゴリズム、モデル、手法の膨大なリストは、時系列分類法の広大な分野を理解するのに役立つだけでなく、お役に立てば幸いです。help
以上が8つの時系列分類方法のまとめの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。