2015__SIGMOD__k-Shape - Efficient and Accurate Clustering of Time Series

## Memo - [[2018__Middleware__Sieve Actionable Insights from Monitored Metrics|Sieve]]で使用されている。 - [k-Shapeによる時系列クラスタリングの論文：「k-Shape: Efficient and Accurate Clustering of Time Series」を読んだ - Fire Engine](https://blog.tsurubee.tech/entry/2019/02/06/223555) - [時系列データクラスタリングとk-Shape – Cyber Garage (Memo)](http://www.cybergarage.org/memo/timeseries_clustering-kshape/) - [時系列クラスタリング手法のk-shapeの論文を一部読んでみた - さとけんの練習帳](https://sakatoken.hatenadiary.jp/entry/2019/06/12/022901) ## ABSTRACT 多くの分野にわたる時間データの拡散と普遍性により、時系列の分析とマイニングに大きな関心が寄せられている。クラスタリングは、その探索力の高さだけでなく、他の手法の前処理やサブルーチンとしても利用されており、最もポピュラーなデータマイニング手法の一つである。本論文では、時系列クラスタリングのための新しいアルゴリズムであるk-Shapeを紹介する。k-Shapeは、スケーラブルな反復的精緻化手順に依存しており、同質で分離されたクラスタを生成する。距離尺度として、k-Shapeは時系列の形状を考慮して比較するために、[[相互相関]]尺度の正規化版を使用しています。この距離尺度の特性に基づいて、時系列のクラスタへの割り当てを更新するために、クラスタの中心を計算する方法を開発した。k-Shapeのロバスト性を実証するために、我々のアプローチを、分割的、階層的、特殊なクラスタリング手法に対して、最も単純な距離尺度の組み合わせで実験的に評価した。さらに、k-Shapeはスケーラブルではない（したがって非現実的な）組み合わせに対しても、同様の精度を達成する1つの例外を除いて優れた結果を示している。しかし、k-Shapeとは異なり、この組み合わせは距離測定のチューニングを必要とし、k-Shapeよりも2桁遅いのです。全体的に、k-Shapeはドメインに依存せず、高精度で効率的な時系列のクラスタリング手法であり、幅広い応用が可能であると考えられる。 ## 1. INTRODUCTION 時間的、または逐次的なデータマイニングは、データが自然にシーケンスで構成されている問題を扱います[34]。このようなデータシーケンスは、タイミングに関する明示的な情報を含んでいる場合（株式、au-dio、音声、ビデオなど）、または値の順序付けが推測できる場合（ストリームや手書きなど）、時系列シーケンスと呼ぶことにします。天文学、生物学、気象学、医学、金融、ロボット工学、工学など、ほぼすべての分野で大量の時系列シーケンスが出現しています[1, 6, 25, 27, 36, 52, 70, 76]。時系列の普遍性は、クエリ [2, 19, 45, 46, 48, 62, 74, 79]、インデックス作成 [9, 13, 41, 42, 44, 77]、分類 [37, 56, 68, 88]、クラスタリング [43, 54, 64, 87, 89]、およびそのようなデータのモデル化 [4, 38, 86] に大きな関心を寄せている。時系列データに適用されるすべての手法の中で、クラスター化は、コストのかかる人間の監視や時間のかかるデータのアノテーションに依存しないため、最も広く利用されている。クラスタリングを用いることで、基礎となるデータの中の興味深いパターンや相関関係を識別し、要約することができる [33]。ここ数十年の間に、時系列配列のクラスタリングは、強力な単独の探索手法としてだけでなく、他の作業のための前処理やサブルーチンとしても注目されてきた [5, 16, 25, 47, 60, 64, 66, 87, 89]。 ![[Pasted image 20220211215433.png]] [[クラスタリング]]を含むほとんどの時系列解析技術は、距離尺度の選択に決定的に依存する。2 つの時系列シーケンスを比較する際の重要な問題は、我々が議論するように、シーケンスに特徴的な様々な歪みをどのように扱うかということです。この点を説明するために、よく知られているECGFiveDaysデータセット[1]を考えてみましょう。これらのシーケンスは全体的に似ているように見えますが、2つの異なるクラスのうちの1つに属するパターンを示しています（図1参照）。クラスAは急激な上昇、下降、さらに緩やかな上昇を特徴とし、クラスBは緩やかな上昇、下降、さらに緩やかな上昇を特徴とする。理想的には、形状に基づいたクラスタリング手法は、振幅や位相の違いに関係なく、形状の類似性に基づいて同じクラスタに配置され、類似のパターンを示すシーンを示す図1のクラスのようなパーティションを生成する必要があります。形状の概念を正確に定義することができないため、データに内在する複数の固有の歪みに対して不変性を提供するために、多くの距離測定が提案されてきた [11, 12, 14, 19, 20, 22, 55, 75, 78, 81]。しかし，振幅と位相の不変性を提供する距離尺度は非常によく機能することが示されており [19, 81]，そのため，そのような距離尺度は形状に基づくクラスタリングに用いられる [53, 59, 64, 87]．このような困難さと，ある領域から別の領域への不変量の必要性の違いから，新しいクラスタリングアルゴリズムの作成よりも，新しい距離測定法の作成の方が注目されてきた．一般的に距離尺度の選択はクラスタリングアルゴリズムそのものよりも重要であると考えられている[7]．その結果、時系列のクラスタリングは、デフォルトの距離測定値を時系列に適したものに置き換えるか、既存のクラスタリングアルゴリズムを直接使用できるように時系列を「フラット」なデータに変換することで、古典的なクラスタリング手法に大部分を依存している[83]。しかし、クラスタリング法の選択は以下のような影響を与える。(i) クラスタリングの均質性と分離の表現方法がそれぞれ異なるため精度、(ii) 計算コストが手法によって異なるため効率性に影響を与える。例えば、スペクトル・クラスタリング [21] や[[階層的クラスタリング]] [40] のある種のバリエーションは、[[k-means]] [50] や k-mededoids [40] のような分割法よりも、密度に基づいたクラスタ（すなわち、データの残りの部分よりも密度の高い領域）を識別するのに適している。一方で，k-meansは高次アーキシャル法，スペクトル法，k-mededoids法よりも効率的である．残念なことに，形状に基づいたクラスタリングのための最先端のアプローチは，スケールとシフトが不変である距離測定法を用いた分割法を用いているが，主に2つの欠点がある．(i)これらのアプローチは計算コストの高い手法や距離測定法に依存しているため，大量のデータに対応することができない[53, 59, 64, 87]；(ii)これらのアプローチは特定の領域のために開発されたものである[87]；あるいはその有効性は限られた数のデータセットに対してしか示されていない[53, 59]．さらに、最も成功している形状ベースのクラスタリング手法は、大域的なアラインメントが適切であることが多いにもかかわらず、局所的な非線形配列のアラインメントを介して位相不変性を扱う。例えば，図１の心電図データセットでは，効率的な線形ドリフトは２つのクラスの配列のパターンの根本的な違いを明らかにすることができるが，高価な非線形アラインメントでは，各配列の増加や減少に対応するすべての増加や減少が一致してしまい，２つのクラスを区別することが難しくなる（図１参照）。重要なことは、我々の知る限りでは、これらのアプローチは、お互いに対して、他の分割法に対して、あるいは階層法やスペックトラール法のような異なるアプローチに対して、これまで広範囲に評価されたことがないということです。本論文では、後述するように、このような実験的評価を行う。本論文では、形状に基づく時系列クラスタリングのための新しいアルゴリズムであるk-Shapeを提案する。具体的には、k-Shapeはk-meansとは異なる距離尺度とセントロイドの計算方法の両方を使用しています。上で述べたように、k-Shapeは時系列シーケンスを比較しながら形状を保持しようとします。そのためには、k-Shapeはスケーリングやシフトに不変な距離尺度を必要とする。他のクラスタリングアプローチ[53, 64, 87]とは異なり、k-Shapeでは相互相関統計量を適用し、以下のことを示す。(i) スケールとシフトに依存しない時系列の距離尺度を原理的に導出する方法、(ii) この距離尺度がどのようにして効率的に計算できるかを示す。相互相関の正規化されたバージョンの特性に基づいて、クラスターの中心点を計算する新しい方法を開発した。距離測定とk-Shapeの有効性を実証するために、48のデータセットを対象に大規模な実験評価を行い、厳密な統計解析を用いて時系列に対する最新の距離測定とクラスタリングアプローチを比較した。結果の再現性を確保するために、ソースコードを公開し、公開データセットを使用するなどの措置をとった。その結果、我々の距離尺度はユークリッド距離（ED）[20]を上回り、最も性能の高い距離尺度[19, 81]である制約付き動的時間歪曲（cDTW）[72]と同様の結果を得ており、チューニングを必要とせず、1桁の速さを実現していることが示された。例えば、図1の心電図データセットでは、我々の距離測定は98.9%の片寄り分類精度を達成しており、このタスクに対するcDTWの精度、すなわち79.7%を大幅に上回っています。クラスタリングについては、文献で報告されているのとは対照的に、EDを用いたk-meansアルゴリズムがロバストなアプローチであり、距離尺度やセントロイド計算の不適切な変更がその性能を低下させる可能性があることを示した。さらに、単純な分割法は、最も競争力のある距離尺度を持つ階層法やスペクトル法よりも優れており、距離尺度よりも重要ではないと考えられているアルゴリズムの選択が、距離尺度の選択と同じくらい重要であることを示している。同様に、我々は、スケーラブル、非スケーラブルなすべての分割法、階層法、スペクトル法を精度の点で上回ることを示した。しかし、このアプローチには、k-Shapeで回避できる問題があります。(i) k-medoids が dis-similarity 行列を計算する必要があるため、スケーリングができず、特に速度が遅く、k-Shape よりも 2 桁遅い。対照的に、k-Shapeはシンプルでパラメータのない距離測定を使用します。特に図１の心電図データセットのように、類似しているが位相がずれたシーケンスを含むアプリケーションでは、k-Shapeは84％のクラスタリング精度を達成しており、これはcDTWを用いたk-medeedidsの53％の精度を大幅に上回っている。本論文では、まず、時系列のクラスタリングに関する最新の技術の詳細なレビューと、我々が注目している問題の正確な定義について述べる（第2節）。次に、我々の新しいアプローチを以下のように紹介する。 - 我々は、スケール、トランスレート、シフト不変の分散測定値がどのようにして相互相関測定値から原理的に導出されるのか、また、この測定値がどのようにして効率的に計算されるのかを示す（第3.1節）。 - 我々は、距離尺度が使用されている場合にクラスタのセントロイドを計算する新しい方法を提示する(3.2節)。 - また、時系列クラスタリングのためのセントロイドに基づくアルゴリズムであるk-Shapeを開発しました(3.3節)。 - 大規模な実証実験的評価を行うことで、我々のアイデアを評価する（第4節、第5節）。最後に関連する研究(第6節)と我々の研究の意味合い(第7節)について考察する。 ## 2. PRELIMINARIES 本節では、関連する理論的背景を概説する（2.1節）。また，時系列データでよく見られる歪み（セクション2.2）と，そのようなデータに対する最も一般的な歪み尺度（セクション2.3）について議論する．次に，時系列データのクラスタリング（セクション2.4）およびセントロイドの計算（セクション2.5）に対する既存のアプローチを総括する．最後に, 我々の問題意識を正式に示す(セクション2.6)． ### 2.1 Theoretical Background クラスタリングの難しさここでクラスタは，均質性（クラスタ内のオブザベーションの類似性）と分離（異なるクラスタからのオブザベーションの非類似性）の概念で特徴づけされる．均質性と分離を捉える多くのクラスタリング基準が提案されているが [35] ，最小クラスタ内2乗距離和は，それらの両方を表現するので，最もよく使用される．n 個のオブザベーションの集合X = { ⃗x1,...,⃗xn}，ここで ⃗xi ∈ Rm，およびクラスタの数 k < nが与えられると，目的は，Xをk個の対不一致クラスタ P = {p1 , .... pk }に分割し，クラスタ内二乗距離の和を最小化することである． ![[Pasted image 20220211220729.png|400]] ここで、⃗cj はパーティション pj∈P のセントロイドである。ユークリッド空間において、これは k≥2 [3] に対して、次元数 m=2 [51] でも NP-hard な最適化問題である。大域的最適解を求めることは困難であるため、k-means法[50]などのヒューリスティックを用いて局所的最適解を求めることがよく行われる。具体的には、k-meansはデータ点をk個のクラスタにランダムに割り当て、その後、反復毎に2つのステップを実行する反復手順を用いる。(i)割り当てステップでは、各データポイントは、距離関数を用いて決定されるその最も近いセントロイドのクラスタに割り当てられる。(ii)絞り込みステップでは、クラスタのメンバーの変更を反映するためにクラスタのセントロイドが更新される。アルゴリズムは、クラスターメンバーシップに変化がないとき、あるいは最大反復回数に達したときに収束する。シュタイナー数列。絞り込みステップでは、k-meansはクラスタの代表となる新しいセントロイドを算出する。セントロイドは、他のすべてのデータ点への二乗距離の和を最小化するデータ点として定義される。したがって、使用される距離尺度に依存する。このようなセントロイドを見つけることは、Steinerの配列問題[63]として知られている：パーティションpj∈Pが与えられると、対応するセントロイド⃗cjが満たす必要がある。 ![[Pasted image 20220211220813.png|400]] EDを用いる場合、セントロイドは算術平均の性質を利用して計算することができる[18]。観測値のアラインメントが必要な多くの場合、この問題は多重配列アラインメント問題と呼ばれ、NP完全であることが知られている[80]。時系列の文脈では、Dynamic Time Warping (DTW) (セクション2.3参照)がアライメントを伴う時系列配列の比較に最も広く用いられており、DTW下での平均配列を求める多くのヒューリスティクスが提案されている (セクション2.5参照)。 ### 2.2 Time-Series Invariances ドメインに基づき、配列はしばしば何らかの形で歪んでおり、配列を有意に比較するために、距離尺度は多くの不変性を満たす必要がある。本節では、一般的な時系列の歪みとその不変量について概説する。より詳細なレビューについては[7]を参照されたい．スケーリング不変量と平行移動不変量．多くの場合、振幅（スケーリング）やオフセット（平行移動）の違いにもかかわらず、シーケンスの類似性を認識することが有用である。つまり、ある配列⃗xを⃗x′ = a⃗x + b（a、bは定数）と変換しても、⃗xの他の配列に対する類似性は変化しないはずである。例えば、外国為替市場における通貨価値の季節変動を、インフレに偏ることなく分析するために、これらの不変量は有用であろう。シフト不変性。2つの配列が類似しているが位相が異なる場合（グローバルアライメント）、あるいは配列の中で一致する部分としない部分がある場合（ローカルアライメント）、それでも類似しているとみなす必要がある場合がある。例えば、心拍は計測を開始するタイミングによって位相がずれる（グローバルアライメント）し、手書きのフレーズは文字の大きさや単語間のスペースによってアライメントが必要（ローカルアライメント）である。 **一様なスケーリング不変性**　配列の長さが異なる場合、短い方の配列を伸ばしたり、長い方の配列を縮めたりして、効果的に比較できるようにすること。例えば、心拍の計測時間が異なる場合、この不変性が必要となる。 **オクルージョン（Occlusion）不変性**　部分配列が欠落している場合でも、一致しない部分配列を無視することで比較することができる。この不変性は、手書きの文字にタイプミスがあったり、文字が欠けていたりする場合に有効である。 **複雑さの不同性（Complexity invariance）**。配列の形状は似ているが、複雑さが異なる場合、用途に応じて類似度を低くしたり、高くしたりすることがある。例えば、屋内と屋外で録音された音声信号は、屋内の信号よりもノイズが多いにもかかわらず、類似しているとみなされることがある。多くのタスクでは、時系列を比較する際に、上記の不変性の一部または全部が必要とされる。適切な不変性を満たすためには、クラスタリングの前にデータを前処理し、対応する歪みを除去することができる。例えば、データを[[Z-score]][29]することで、スケーリング不変量と並進不変量を実現することができる。しかし、前処理で実現できない不変性については、歪み不変性を満たすような高度な距離尺度を定義することができる。次節では、そのような最も一般的な距離尺度をレビューする。 ### 2.3 Time-Series Distance Measures 時系列比較のための2つの最新アプローチは、まずシーケンスをZ正規化し、次にその類似性を決定するために距離尺度を使用し、場合によってはより多くの不変性を捕捉する。最も広く使用されている距離指標は、単純な[[ユークリッド距離]] (ED) [20]である。EDは長さmの2つの時系列⃗x = (x1,...,xm) と⃗y = (y1,...,ym) を以下のように比較する。 ![[Pasted image 20220211221222.png|400]] もう一つの有名な距離尺度は[[DTW]] [72]である。DTWは、局所的な（非線形）アライメントを提供するEDの拡張と見なすことができる。これを実現するために、m×mの行列Mが構成されxyの任意の2点間のEDが設定されています。ワーピングパス W = {w1,w2,...,wk} は、k ≥ m で、連続したパスである。 xyの間のマッピングをいくつかの制約の下で定義する行列要素のユースセット[44]である。 ![[Pasted image 20220211221302.png|400]] この経路は、行列Mに対して、動的計画法により、以下の漸化式を評価することで計算することができる。 $γ(i,j)=ED(i,j)+min{γ(i-1,j -1),γ(i,j -1)}$とする。ワーピングパスは、行列M上のセルの部分集合のみを訪れるように制約するのが一般的である。部分集合行列の形状をバンドと呼び、バンドの幅をワーピングウィンドウと呼ぶ。制約付き動的時間ワーピング（cDTW）で最も頻繁に使用されるバンドは、Sakoe- Chibaバンドである[72]。図2aはEDとDTWによる2つの配列のアライメントの違いを示し、図2bは幅5セルのSakoe-Chibaバンドで制約されたcDTWのワープ経路（暗いセル）（明るいセル）を示している。最近、Wangら[81]は9つの距離尺度とそのいくつかの変種を広範囲に評価した。また，cDTWはDTWより若干優れており，計算時間が大幅に短縮される．cDTWをさらに高速化するために、いくつかの最適化が提案されている[65]。次のセクションでは、これらの距離尺度を利用することができるクラスタリングアルゴリズムについてレビューします。 ### 2.4 Time-Series Clustering Algorithms 時系列をクラスタリングする方法はいくつか提案されている。すべてのアプローチは、一般的に既存のアルゴリズムを修正し、デフォルトの距離尺度を時系列の比較に適したバージョンに置き換えるか（raw-based手法）、シーケンスを「フラット」データに変換し、古典的なアルゴリズムで直接使用できるようにするか（feature-based手法とmodel-based手法）[83]のいずれかである。raw-based手法は、距離尺度に関する膨大な文献（セクション2.3参照）を容易に利用することができ、DTWのような特定の尺度が提供する障害は一般的であり、したがって、ほとんどすべてのドメインに適していることが示されている[19]。これに対し、特徴量やモデルに基づくアプローチは、通常、ドメイン依存であり、異なるドメインへの適用には、特徴量やモデルを変更する必要がある。このような特徴ベースやモデルベースの手法の欠点から，本論文ではraw-basedアプローチを採用する．生に基づく手法としては，凝集型、階層型，スペクトル型，パーティショナル型クラスタリングが有名である[7]．階層的クラスタリングでは、最も広く使われている「リンク」クリエイトは、単一リンク、平均リンク、完全リンクのバリアントです[40]。スペクトルクラスタリング[58]は、他の種類のデータに対する成功により、最近再び注目され始めています[7]。分割法の中では、k-means [50]とk-medoids [40]が最も代表的な例である。分割法のうち，拡大縮小，並進，移動に対して不変な距離尺度を用いるものは，形状に基づくアプローチとみなす．k-medoids は k-means と異なり、全データ配列の非類似度行列を計算し、実際の配列をクラスタの中心とするのに対し、 k- means は人工配列を中心とする計算を必要とし、ED 以外の距離尺度を容易に適応できない（セクション 2.1 参照）ため、通常 k-medoids が好まれる [83]．しかし、これらの手法のうち、データセットのサイズに対して線形に拡張できるのはk-meansクラスのアルゴリズムのみである。最近、k-meansは以下のように修正された。(i) DTW距離尺度 [64] と (ii) 時系列シーケンスのペアワイズ・スケーリングとシフトを提供する距離尺度 [87] で動作するようにk-meansが修正された。これらの変更は両方ともクラスタ中心を計算する新しいアプローチに依存しており、次にレビューする。 ### 2.5 Time-Series Averaging Techniques 平均配列、あるいはクラスタリングの文脈ではセントロイドの計算は困難な作業であり、時間配列の比較に用いられる距離尺度に決定的に依存する（セクション2.1参照）。ここで、平均配列の計算のための最新の方法をレビューする。 [[ユークリッド距離]]では、算術平均の性質を利用して平均列を計算する（例えば、k-means アルゴリズムのセントロイドの計算の場合と同様）。しかし、DTWは多くの時系列のタスクに適しているため[44, 65]、いくつかの方法がDTWの下で時系列配列の平均化を行うために提案されている。非線形アライメントと平均化フィルタ（NLAAF）[32]は、平均化シーケンスの各座標がDTWによって生成されるマッピングの中心として計算される、単純なペアワイズ法を使用する。この方法は、1つのペアしか残らないまで、配列のペアに順次適用される。Prioritized Shape Averaging (PSA) [59]は、配列の平均化に階層的な方法を使用する。平均的な配列の座標は、DTWによって結合された2つの時系列配列の座標の重み付けされた中心値として計算される。初期状態では、すべての配列は重み1を持ち、木のノードで生成される各平均配列は、平均化した配列の数に対応する重みを持つ。以前のアプローチの高い計算コストを避けるために、Ranking Shape-based Template Matching Framework (RSTMF) [53] は、配列のすべてのペアの距離を計算する代わりに、他のすべてのクラスタセントロイドへの配列の距離を見ることによって、時系列配列の順序を近似的に決定する。これらの手法のいくつかの欠点により、Dynamic Time Warp-ing Barycenter Averaging (DBA) [64]という、データから最初に選んだ配列の座標を繰り返し再採点する、より頑健な手法が開発された。平均的な配列の各座標は、DTWの使用と関連した他の配列の1つ以上の座標のbarycenter1を使用して更新される。これらの方法の中で、DBAはDTWを使用した場合、最も効率的で正確な平均化アプローチであると思われる[64]。行列分解に基づく別の平均化手法は、K-Spectral Centroid Clustering (KSC) [87]の一部として提案され、ペアワイズスケーリングとシフトのための距離尺度が使用されているときに、クラスタのセントロイドを計算する。第3節で紹介する我々のアプローチでも、セントロイドを計算するために行列分解に依存している。 ### 2.6 Problem Definition ドメインが異なれば，データの歪みに対する不変性も異なるが（セクション2.2参照），我々は，一般的に十分なスケーリングとシフトに対する不変性を持つ距離尺度に着目する（セクション2.3参照）[19]．さらに、このような距離尺度を容易に採用するために、2.4節で論じたように、raw-basedクラスタリングアプローチに分析を集中させることにする。次に、我々の新しいクラスタリングアルゴリズムであるk-Shapeを紹介する。 ## 3. K-SHAPE CLUSTERING ALGORITHM 我々の目的は、時系列クラスタリングのための、ドメインに依存しない、正確でスケーラブルなアルゴリズムを開発することであり、スケーリングやシフトに不変な距離尺度を用いる。我々は、時系列シーケンスの形状を保持することができる新しいセントロイドベースのクラスタリングアルゴリズムであるk-Shapeを提案する。具体的には、まず、相互相関測度を用いた距離測度について述べる（3.1 節）。そして，この距離尺度に基づき，時系列クラスタのセントロイドを計算する方法を提案する（セクション3.2）．このアルゴリズムは、配列の数に線形に比例し、均質で分離の良いクラスタを生成する反復的な洗練手順に依存している（セクション3.3）。 ### 3.1 Time-Series Shape Similarity 先に述べたように、形状に基づく類似性を捉えるには、振幅と位相の歪みを扱える距離尺度が必要である。しかし、DTW のような歪みに対する不変性を持つ距離尺度は計算量が多い（2.3 節参照）。この効率的な制限を回避するために，我々は相互相関測定の正規化されたバージョンを採用する．相互相関は、信号や画像処理に広く用いられている、時間的に遅れた信号の類似性を示す尺度である。しかし、相互相関は信号間の一対一の点を比較する尺度であるため、時系列比較の問題に対する実験評価ではほとんど無視されてきた。その代わりに、数十年前のDTWの適用[8]に始まり、この問題に対する研究は、一対多または一対一の点を比較する弾性距離尺度に焦点を当ててきた[11, 12, 44, 55, 78]。特に，時系列比較のための最新の距離測定法（[19, 81]では9種類，[26]では48種類）の包括的かつ独立した実験評価は，相互相関を考慮しないものであった．ドメインやアプリケーションごとに異なるニーズは、データおよび相互相関尺度の適切な正規化を見つけるプロセスを阻害します。さらに、相互相関の非効率的な実装により、DTWと同程度に遅くなる可能性がある。これらの欠点の結果として、相互相関は時系列距離測定法として広く採用されていない。このセクションの残りの部分では、これらの欠点に対処する方法を示す。具体的には、ドメインに依存しない効率的な正規化を選択する方法を示し、効率的かつ効果的に時系列を比較するための形状ベースの距離尺度を導く。 **相互相関測度（Cross-correlation measure）** 相互相関は、2つの$\vec{x} = (x_1,\ldots, x_m)$, $\vec{x} = (y_1,\ldots, y_m)$ の類似性を、それらが適切に配置されていなくても決定できる統計的な尺度である。シフト不変性を達成するために、相互相関$\vec{y}$を静止させ$\vec{x}$を$\vec{y}$上でスライドさせて、⃗xのシフトsごとにその内積を計算する。数列のシフトを以下のように表す。 ![[Pasted image 20220211230838.png|400]] $s∈[-m, m]$で可能なすべてのシフト$\vec{x}_(s)$を考慮した場合。$CC_w(x,y)=(c_1,...,c_w)$ という長さ2m-1の相互相関列を生成し、次のように定義する。 ![[Pasted image 20220211230920.png|600]] ここで、Rw-m(⃗x,⃗y)は、順番に次のように計算される。 ![[Pasted image 20220211230951.png|500]] $CC_w(\vec{x},\vec{y})$が最大となる位置wを計算することが目標である。このwの値に基づいて、⃗yに対する⃗xの最適なシフトは、⃗x（s）、ここでs = w - mとなる。ドメインやアプリケーションによっては，CCw(⃗x,⃗y)の異なる正規化が必要であろう．最も一般的な正規化は，バイアス付き推定量$NCC_b$，不偏推定量$NCC_u$，および係数正規化$NCC_c$であり，これらは以下のように定義される． ![[Pasted image 20220211231026.png]] 相互相関の正規化以外にも、時系列に内在する歪みを除去するための正規化が必要な場合があります。図3は、長さm = 1024の2つのシーケンス⃗xと⃗yの相互相関正規化が時系列の正規化によってどのように影響されるかを示しています。(付録Aでは、他の時系列正規化における相互相関バリアントの分類精度についても詳しく説明しています)。CCw(⃗x,⃗y)に適用された正規化とは無関係に、生成されたシーケンスは長さ2047となる。図3aは、⃗xと⃗yをz正規化することで振幅の違いを取り除き、両者が並んでいること、つまりシフトが不要であることを示したもので、このとき、⃗xと⃗yをz正規化することで振幅の違いがなくなる。CCw(⃗x,⃗y)が w∈[1025,2047] (または w∈[1,1023]) で最大になる場合、⃗xまたは⃗yの一方を i - 1024だけ右に（または 1024 - iだけ左に）シフトさせなければならない。そうでなければ、w = 1024の場合、⃗xと⃗yは適切に配置され、これは我々の例で期待されることです。図3bは，⃗xと⃗yをz正規化せず，偏った推定量を用いた場合，NCCはw = 1797で最大となり，1797 - 1024 = 773回左にシフトしていることを示しています．また，⃗xと⃗yをz正規化し，不偏推定量を用いると，NCCuはw = 1694で最大となり，1694 - 1024 = 670回シーケンスが右にシフトすることがわかる（図3c）．最後に、⃗xと⃗yをz正規化し、係数正規化を使用すると、NCCcはw = 1024で最大となり、これはシフトが必要ないことを示す（図3D）。 ![[Pasted image 20220211230821.png]] 上記の例で示されるように、データと相互相関尺度の正規化は、生成される相互相関シーケンスに大きな影響を与える可能性があり、距離尺度の作成は自明なタスクではありません。さらに、図3で見たように、複数の時系列を一対一で比較した相互相関列は、正規化によってその振幅が異なる。したがって、このようなシーケンスを有意に比較するためには、指定された範囲内の値を生成する正規化を使用する必要がある。形状に基づく距離(SBD)。形状に基づく距離尺度を考案するために、また、これまでの議論を踏まえて、データの正規化に関係なく、-1から1の間の値を与える係数正規化を使用する。係数正規化とは、相互相関シーケンスを個々のシーケンスの自己相関の幾何平均で割ることである。シーケンスの正規化後、NCCc(⃗x,⃗y)が最大になる位置wを検出し、以下の距離尺度を導出する。 ![[Pasted image 20220211231155.png|600]] は 0 から 2 の値をとり、0 は時系列シーケンスの完全な類似性を示す。ここまでは、シフト不変性についての説明である。スケーリング不変性については、各列⃗x を ⃗x′ = ⃗x-μ に変換することで、以下のようになる。σ であり、その平均値μは0、標準偏差σは1である。SBDの効率的な計算：式6より、すべてのwの値に対するCCw(⃗x,⃗y)の計算には、時系列長をmとするとO（m2）の時間が必要である。畳み込み定理[39]は、2つの時系列の畳み込みが、時系列の個々の[[離散フーリエ変換]]（DFT）の積の[[逆離散フーリエ変換]]（IDFT）として計算できることを述べており、ここでDFTは次の通りである。 ![[Pasted image 20220219194856.png|500]] ![[Pasted image 20220219194914.png|500]] ここで、j = √-1 です。相互相関は、一方の時系列を時間的に反転させた場合の2つの時系列の畳み込みとして計算され、⃗x= ⃗x [39] これは周波数領域で複素共役（＊で表す）をとることと同じである。したがって、式6は、すべてのmについて、次のように計算できる。 ![[Pasted image 20220219195110.png]] しかし、DFT と IDFT は依然として O(m ) の時間を必要とする。高速フーリエ変換（FFT）アルゴリズム[15]を用いると、O(m log(m))に短縮される。データおよび相互相関の正規化も効率的に計算できるため、SBDの全体的な時間複雑度はO(mlog(m))のままです。さらに、再帰的アルゴリズムでは、FFTを2のべき乗のサイズに分割して計算します[24]。したがって、FFT計算のパフォーマンスをさらに向上させるために、CC(⃗x,⃗y)が正確な2のべき乗でない場合、⃗xと⃗yに0を詰め、2m-1の後に次の2のべき乗の長さに到達させるのである。アルゴリズム1は、この効率的でパラメータフリーの尺度が、最新の数学ソフトウェアを用いて数行のコードでどのように計算されるかを示している。 ![[Pasted image 20220219195140.png]] 本節では、形状に基づく距離計測を導き出すために、効果的な相互相関とデータの正規化を示した。また、重要な点として、相互相関距離尺度を効率的に計算する方法についても議論した。SBDはcDTWやDTWと同程度の結果を出しながら、桁違いに高速であることを実験評価（セクション4と5）で示す。次に、クラスタのセントロイドを抽出し、クラスタデータを上述の形状ベースの距離尺度と整合的に表現することが重要な問題である。 ### 3.2 Time-Series Shape Extraction ### 3.3 Shape-based Time-Series Clustering ## 6. RELATED WORK 本論文では、効率的でドメインに依存しない時系列クラスタリングに焦点を当てた。第2節では、時系列クラスタリングに関する技術の現状を詳細に説明したが、簡潔さのために繰り返さない。具体的には、セクション2.1では関連する理論的背景を要約し、セクション2.2では時系列によく見られる歪みをレビューし、セクション2.3では時系列に対する最も一般的な最新の距離測定法について論じた。(また，セクション2.3では，時系列に対する最も一般的な最新の距離測定法について議論した（時系列距離測定法についての詳細なレビューと評価については，[19, 81]を参照されたい）．セクション2.4では、時系列をクラスタリングするための既存のアプローチに焦点を当てました。(最後に、セクション2.5では、多くの時系列クラスタリングアルゴリズムに含まれるセントロイドの計算方法について議論した。本論文で論じたように、我々は時系列の形状に基づくクラスタリングに焦点を当てる。形状ベースのクラスタリングアルゴリズム以外にも、統計ベースのアプローチは、時系列をクラスタリングするための記述的特徴として、特徴（82）、モデルの係数（38）、時系列の一部（すなわち、シェイプレット）［89］を要約する尺度を使用する。しかし、統計的手法では、複数のパラメータを調整する必要があり、その場しのぎの判断になりがちである。また、その有効性は、孤立したデータに対してのみ確立されており、ドメインに依存しない方法ではない。その代わりに、形状に基づくアプローチは一般的であり、距離尺度に関する膨大な文献を活用することができる。文献から得られた最も性能の良い形状ベースアプローチは、スケール不変およびシフト不変の距離尺度と組み合わせたパーティショナルな方法である。分割法の中でも、k-medoids [40]は、任意の形状ベース距離尺度を容易に採用できるため、最も人気のある手法である[19, 81]．しかし，k-medoids は全時系列間の非類似度行列を計算する必要があり，特に時間がかかり，スケールアップができない．最近の代替アプローチ[32, 53, 59, 64, 87]では、k-means [50]が注目されているが、これはスケーラブルであるが、同じ特性（例えば、スケーリング、トランスレーション、シフト）をサポートするために、距離尺度がアルテアされるとセントロイド計算方法を変更する必要がある。DTWは最も有力な形状ベースの距離尺度であるため[19, 81]、k-meansアプローチの大半は、DTWと組み合わせて使用する新しいセントロイド計算方法を提案している[32, 53, 59, 64]。k-DBAはこれらのアプローチの中で最も堅牢であることが示されている[64]。これは、時系列のペアワイズスケーリングとシフティングを同時に提供する、異なる形状ベースの距離測定に焦点を当てたアプローチである。残念ながら、このようなペアワイズ・スケーリングとシフティング、ひいてはKSCの有効性は、限られた数のデータセット以外では確立されていない。完全を期すために、[28] [[2005__SIGMOD__BRAID - Stream Mining through Group Lag Correlations]]はfMRIデータのファジークラスタリングにおいて、距離指標として相互相関を用い、セントロイドの計算には算術平均の特性を用いていることに留意されたい。(セクション5で、我々はk-AVG+SBDが我々の非ファジィの設定に対して競争力がないことを示した)。最後に、相互相関はfMRIデータをクラスタリングのための特徴量に変換するために使用され[31]、また、ストリームマイニング、パターン抽出、時系列モニタリングにも使用されました[61, 73, 85, 90]。 ## 7. CONCLUSIONS 時系列の形状を保持した分割型クラスタリングアルゴリズムであるk-Shapeを発表した．k-Shapeは時系列を効率的に比較し，スケーリングやシフトの不変性を排除して効率的に中心値を計算することが可能である．我々の広範な評価により、k-Shapeは最新のパーティショナルクラスタリング、階層的クラスタリング、およびスペクトルクラスタリング手法をすべて凌駕し、唯一同等の性能を達成した手法があることが示された。しかし、この手法はk-Shapeと比較して2桁遅く、k-Shapeとは異なり距離測定のチューニングが必要である。全体として、k-Shapeは時系列クラスタリングのためのドメインに依存しない、正確で、スケーラブルなアプローチである。