カテゴリー: 論文

「Time-series clustering – A decade review」という論文を読んだ。過去10年間の時系列クラスタリングの研究動向についてサーベイした論文。クラスタ手法のみではなく、効率や品質、複雑性などの観点での動向も調べられている。

」という論文を読んだ。過去10年間の時系列クラスタリングの研究動向についてサーベイした論文。クラスタ手法のみではなく、効率や品質、複雑性などの観点での動向も調べられている。

背景

近年、ストレージの増加や計算性能の向上により、バイオロジー、ファイナンス、気象などなど様々な分野でデータが大量に蓄積されてきている。それらのデータは必然的に時系列データとして扱うことができ、データマイニングの研究ターゲット（例えば可視化、分類、要約、トレンド解析など）とされてきた。

時系列データのクラスタリングの課題として、一般的に時系列データは大規模なものになりやすくメモリに乗りきらない場合がある、高次元になりやすい、類似度の計算が（時系列データはノイズや外れ値が入っていることが多く、系列ごとに長さが異なることが一般的なため）複雑なものになる、といった点がある。

ほとんどの時系列クラスタリングは3カテゴリーに分類できる。一つ目は Whole time-series clustering。これは個別の時系列データに対してのクラスタリング。二つ目は Subsequence clustering。単一の時系列からスライディングウィンドウなどにより部分系列を複数取り出して、クラスタリングするカテゴリー。三つ目は Time point clustering。これは時間的な近さと値の関係をもとにしてクラスタリングするパターン。

多くの研究では Whole time-series clusteringのパターンがとられており、著者らの分類によると Whole time-series clusteringはさらに3つの特徴で細かく分類できる。shape-basedアプローチは古典的なクラスタリングアルゴリズムを時系列データそのものに対して利用する。feature-basedアプローチはいったん生の時系列データを低次元の特徴量のベクトルに落とし込んでからクラスタリングを行う。model-basedの手法は一つの時系列データを1組のパラメトリックなモデルのパラメータに変換して、複数のパラメータに対してクラスタリング手法を用いてクラスタリングする。

時系列クラスタリングにおいて重要な要素の一つは次元削減である。時系列データはノイズも多く、系列長が長くなるとクラスタリングの計算コストが増えるために適切な次元削減を施してから、クラスタリングする場合がある。
近年よく使われるデータの表現方法は、Data adaptive（任意の長さのセグメントに対してデータを圧縮できる）, Non-data adaptive（固定長のデータに適する）, Model-based（マルコフモデルのようにモデルでデータを表現する）, Data dictated（Model-basedとは対照的に圧縮率はデータに応じて決定される）の４種類に分類できる。それぞれの分類ごとにデータを表現するアルゴリズムがいくつか挙げられている。
そのほかにもclipped seriesと呼ばれる、データの値を平均より上か下かで0/1のbit列として扱うような形式でも、時系列の変化の形をクラスタリングするのには十分であるという研究結果もある。

類似度について

時系列データの類似度はクラスタリングにおいて重要な役割を果たす。何をもとに２つの時系列が似ているとするのかは様々な手法が提案されている。
ノイズが乗っているだけの系列どうしは似ていると判断してほしいし、増幅されているものや、間が途切れていたりする場合も似ている時系列と判断したいかもしれない。
一般的に類似度計算の手法が重視する観点が3つあり、それぞれ異なったアプローチが要求される。

1. 時間の観点で似ている時系列を見つける。
   単純なユークリッド距離による類似度が用いられる。生の時系列データに対して計算すると高コストのことがあるため、フーリエ変換などを施してから計算されることが多い。
2. 形状の観点で似ている時系列を見つける。
   いつパターンが起こったのかよりも、形が似ているかどうかを重要視する類似度計算手法。Dynamic time Warpingのような手法が使われる。
3. 変化の観点で似ている時系列を見つける。
   隠れマルコフモデルやARMA系列のようなモデルが使われる。例えば自己回帰のパターンが似ているモデルどうしは同じタイミングで変化するので似ていることになる。長期間の時系列データに適している。

様々な類似度が提案されているが、計算量と精度のトレードオフの関係もあったり、ユークリッド距離でも十分な精度が得られるといった研究もあるそうなので、どれを使うべきかはケースバイケースなのかもしれない。

4章 Time-series cluster prototype

クラスタを代表する時系列(prototype)をどのように表すかにも大きく分けて3通りある。

1. medoidをprototypeとする。要するにクラスタ内の分布の中で一番中央値的な時系列を代表とする。
2. 平均値を使う。固定長の場合は単純に平均値を取れば良い。Dynamic Time WarpingやLongest Common Sub-Sequenceのように可変長の時系列をクラスタリングする距離を用いている場合にも、平均的なprototypeを作成する手法が提案されている。
3. local searchを使う。medoidを求めて、warping pathで平均prototypeを求める。その後平均prototypeに対して、新しいwarping pathを計算する。この手法がほかの手法よりも精度の良いprototypeが得られるのかは分かってはいないようだ。

5章 時系列クラスタリングアルゴリズム

6種類に分けられる。

1. 階層クラスタリング
   agglomerative(bottom-up)やdivisive(top-down)な手法によって階層クラスタリングできる。細かい調整ができないため、一般的には他の手法と組み合わせて使われることも多い。
   結果を可視化して分類の理解に役立つことや、事前にクラスタ数を決めなくても良いことなどが、時系列クラスタリングであっても長所である。弱点として計算量が系列数の2乗のオーダーなので小さなデータセットに適用先が限定されることがある。
2. Partitioning clustering
3. 
   事前に設定されたクラスタ数kにより、k個のクラスタに分類する手法。k-Meansがよく知られた手法であるが、時系列データに対してはk-Medoidsアルゴリズムが使われることが多い。
   クラスタに属するか否かを分ける手法に対して、ある度合いでどのクラスタに属するか、という指標でクラスタリングするFCM(Fuzzy c-Means)というような手法も提案されており、話者特定のようなタスクに応用された事例がある。
4. Model-based clustering
   クラスタごとに1つのモデルを作って、クラスタ内のデータはそのモデルに誤差のノイズが加わって得られたと考えるクラスタリング手法。統計的なアプローチやニューラルネットワークの手法が用いられる。
   一般的にモデルベースのクラスタリングは2つの欠点がある。1つはパラメータを設定する必要があるが、そのパラメータはユーザのある仮定（間違っている可能性がある）に基づいており、低い精度につながる場合があることだ。2点目は大規模データセットに対してモデルの構築に時間がかかり遅い。
5. Density-based clustering
   DBSCANが有名な手法であるが、データの密度が高い近くの空間に向けてクラスタを拡大していく手法。
   時系列データについては多変量の場合複雑度が高くなるため、あまり使われない。
6. Grid-based clustering
   データをグリッドセルに分けてからグリッドのクラスタリングを行う手法。時系列データに使われた例は今のところないらしい。
7. Multi-step clustering
   数は少ないがいくつかの研究では複数の手法を組み合わせて時系列クラスタリングを行っている。例えば、形状の類似度でクラスタリングしてから、時間的な類似度でクラスタリングをかける、といったような今まで挙げた手法を組み合わせて、精度向上や速度向上を目指した手法が提案されている。

6章 時系列クラスタリングの評価手法

時系列クラスタリングの評価手法としては例えば以下のような点に従うことが推奨されている。
・アルゴリズムの評価にはデータセットの複数区間を用いること
・実験を注意深く設計することでバイアスの混入を防ぐこと
・可能ならばデータとアルゴリズムを自由に入手可能とすること
・新しい類似度の指標は簡単で安定しているユークリッド距離のような指標と比較可能であること

大きく分けて可視化と数量的な指標による評価方法が存在する。
数値的なクラスタリング指標にはGround Truthなどとの比較によるExternal indexと、クラスタ内だけの情報によるInternal indexに二分される。

7章 Conclusion

時系列クラスタリングの研究はいろいろと行われているが、一般的なクラスタリング手法が上手く働くのを阻害するような要因が存在している。例えば高次元なデータやノイズ、高い相関などが阻害要因である。

様々な研究は高次元なデータを低次元に落とし込む手法と距離をどのように設定するかをターゲットとして行われている。時系列クラスタリングの研究には図に挙げられている通り４種類の課題が存在しており、それらに対する研究成果がサーベイとして本論文では示されていた。著者らは今後の研究の方向性としては、これらの課題に対して既存の手法もしくは新規手法を組み合わせたハイブリッドなクラスタリングアルゴリズムを考えてい方向に進んでいくだろうと、展望を述べている。