読了:Liao (2005) 時系列クラスタリング法レビュー

Liao, T.W. (2005) Clustering of time series data: A survey. Pattern Recognition, 38, 1857-1874.

 ほんとは年明けからロイヤリティ・プログラム関連の文献を集めていて、さっさと読みはじめなきゃと思ってたんだけど、パンデミックで世界が激変するなか、そうした話題がなんだかすべて虚ろに思えてきてしまい、当面の仕事とは無関係な本や論文ばかりを読んでいた。
 これもそのひとつで、しばらく前にめくった奴。当座の仕事とはあんまり関係ないんだけど、でもこういうのはいつ突然必要になるかわからないから、前もって勉強しておかなきゃ、などと自分に言い訳しながら適当にぱらぱらと目を通した。一種の逃避である。データ解析の仕事だっていつまで続けられるのかわからないのにね… 人の営みとは哀しいものだ。

1. イントロダクション
 本論文は時系列データ・クラスタリングの基礎を紹介し、研究を概観する。
 クラスタリングの目的とは、ラベルなしのデータセットについて、データを等質なグループへと客観的に組織化することによって、データセットの構造を同定することにある。ここでいう等質なグループとは、グループ内の類似性が最小化され、グループ間の非類似性が最大化されているようなグループのことである。[←ここでいきなり類似性という概念を持ち出すのは論点先取じゃないのかなあ? たとえば潜在クラスモデルはクラスタリングの一手法たりえるけど、類似性という概念は含まれていないよね]
 クラスタリングはたいてい静的データを対象とする。[以下、partitioning, hierarchical, density-based(DBSCANとかのこと), grid-based, model-basedの5つにわけて主要手法を概観。SOMはmodel-basedに分類されており、grid-basedの例としてはSTINGといのが挙げられている。なにそれ、知らないわ…]

2. 時系列クラスタリングの基礎
 時系列データのクラスタリング手法はいろいろあるけれど、発想としては次の3つに分けられる。

  • raw-data-basedアプローチ: 静的データをクラスタリングするためのアルゴリズムを、時系列データ用に改修する。主な改修点は類似性指標。
  • feature-basedアプローチ: 時系列を低次元の特徴ベクトルに変換し、静的データ用のアルゴリズムでクラスタリングする。
  • model-basedアプローチ。時系列をモデリングしてパラメータ推定値なり残差なりを出し、静的データ用のアルゴリズムでクラスタリングする(または、パラメータを推定すること自体がクラスタリングになっている)。

ここで使われている静的データ用のアルゴリズムとは、partitioning, hierarchical, model-basedが多い。それらほぼすべてが、2つの時系列間の距離ないし類似性の算出を必要とする。

2.1 クラスタリングのアルゴリズム/手続き
主に使われてきたのは次の4つ。

  • relocationクラスタリング。(1)初期クラスタリングを行う。これを\( C \)とする。(2)非類似性行列を求める。(3)\( C \)のメンバーのひとつを再配置して \( C’ \)をつくる。良し悪しは一般化Ward基準関数で決める。(3)を繰り返す。この手法は時系列が同じ長さのときだけ使える。
  • 凝集型階層クラスタリング。単純リンケージとかWard法とか。いったん結合を決定したらもう調整が効かないというのが弱点。距離さえ定義できれば時系列の長さが異なっていてもよい。なお分割型アルゴリズムもあるけどあまり使われていない。
  • k-meansとファジーc-means(kといってもcといっても同じこと)。[…k-meansアルゴリズムの説明。メモ省略…] これを拡張したのがDunn(1974), Bezdek(1987)で[…メモ省略…]。時系列の長さが同じ場合のほうがうまくいく。なぜなら長さがちがっているとクラスタ中心という概念があいまいになるから。
  • 自己組織化マップ。[…アルゴリズムの説明。メモ省略…] これも時系列の長さがちがうとうまくいかない。

2.2 類似性/距離の指標
主に用いられてきたのは、

  • ユークリッド距離、RMS距離、Mikowski距離。ベクトル\(x_i, v_j\)について、順に
    $$ d_E = \sqrt{\sum_{k=1}^P (x_{ik} – v_{jk})^2} $$ $$ d_{rms} = d_E / n $$ $$ d_m = \sqrt[q]{\sum_{k=1}^P (x_{ik} – v_{jk})^q} $$ ただし\(q\)は正の整数。最大値で割って規準化することもある。
  • ピアソンの相関係数 \(cc\)。ないし、これに関連する距離が用いられることもある。fuzzy c-meansでは$$d_{cc}^1 = \left( \frac{1-cc}{1+cc}\right)^\beta $$とか$$d_{cc}^2 = 2(1-cc)$$とかが用いられることがある(\(\beta\)は0以上)。
  • short time series (STS)距離。それぞれの時系列をピーズワイズ線形関数だとみて、2つの時系列の対応する傾きの差の二乗の合計をとる。[←へー]
  • dynamic time warping (DTW)距離。時系列 \(Q = q_1, q_2, \ldots, q_i, \ldots, q_n\)と\(R=r_1, r_2, \ldots, r_j, \ldots, r_m\)があるとして、距離\(d(q_i, r_j)\)を要素に持つ\(n \times m\)行列を考える。で、次の条件を満たすwarping path \(W = w_1, w_2, \ldots, w_k, \ldots, w_K\)を求める。(1)境界条件。パスの始点と終点は行列の\((1,1)\)と\((n,m)\)であること。(2)連続性条件。パスは隣接セルを進むこと。(3)単調性条件。パスの点は時間に対して単調であること[左上角から右下角に進む途中で上や左には戻れないってことですかね]。こうしてできるパスの\(w_k\)の和の最小値を\(K\)で割った値をDTW距離と呼ぶ。動的計画で簡単に求まる。
  • 確率ベースの距離関数。[これちょっと面白いので細かくメモを取るぞ…] この関数を提案したのはKumar et al.(2002 Conf)で、季節性を持つパターンのクラスタリングのための提案であった。2つの季節性 \(A_i, A_j\)の間の距離を、\(H_0: A_i \sim A_j\)を棄却する確率として定義する。\(A_i\)の要素は\(N(x_{it}, \sigma^2_{it})\)からの独立標本、\(A_j\)の要素は\(N(x_{jt}, \sigma^2_{jt})\)からの独立標本だと仮定すると、\(\sum_{t=1}^{T} \frac{(x_{it} – x_{jt})^2}{\sigma^2_{it}+\sigma^2_{jt}}\)は自由度\(T-1\)のカイ二乗分布に従うはずである。そこで下式を距離とする: $$ d_{ij} = \chi^2_{T-1} \left( \sum_{t=1}^{T} \frac{(x_{it} – x_{jt})^2}{\sigma^2_{it}+\sigma^2_{jt}} \right)$$ [ううむ、わかるようでわからん。要するに時系列を正規ホワイトノイズとみて、パラメータの間の距離を測っているわけでしょ? 時系列がホワイトノイズでなかったらどうなるの?]
  • カルバックライブラー距離。[メモ省略]
  • Jダイバージェンスと対象Chernoff情報ダイバージェンス。[周波数領域の話だ… 超苦手なのでパス]
  • 交差相関関数に基づく非類似性指標。時系列\(x_i, v_j\)のラグ\(\tau\)の交差相関を\( \rho^2_{i,j}(\tau) \)として、$$d_{i,j} = \sqrt{ \frac{ 1-\rho^2_{i,j}(0) }{ \sum_\tau \rho^2_{i,j}(\tau) } }$$ ただし、分母の総和は最大ラグまで回す。類似性は\( s_{i,j} = \exp(-d_{i,j}) \)とする。[要するに、発想としては1-相関係数なんだけど、そのまま使うんじゃなくて、ラグを取りまくって得られた相関の最大値で基準化するってことっすね。求め方はわかるが、こういうのを考えた動機が知りたい…]
  • ふたつの発話された語の非類似性[これは意味がよくわからなかった。パス]

2.3 クラスタリングの結果を評価する基準

  • 既知の正解がある場合。正解を\(G\), クラスタリングの結果を\(C\), いずれもクラスタ数は\(k\)とする。集合の要素のcardinalityを\(|\cdot|\)と書く[勘弁してよ、もう…]。このとき、$$Sim(G_i, C_j) = \frac{2|G_i \cap C_j|}{|G_i| + |C_j|}$$として$$Sim(G,C) = \frac{1}{k} \sum_{i=1}^k \max_{1 \leq j \leq k} Sim(G_i, C_j)$$と定義できる。
  • 正解は未知だが\(k\)は既知の場合。まず、ある時系列\(X\)に振られたウェイトを\(w(X)\), 2本の時系列\(X, Y\)の\(t\)における非類似性を\(d_t(X, Y)\)、あるクラスタ\(C_j)\)に属している時系列の重みの総和を\(w(C_j) = \sum_{X \in C_j} w(X)\)とする。時点\(t\)について$$ p_t(C_j) = \frac{1}{2w(C_j)} \sum_{X,Y \in C_j} w(X) w(Y) d_t(X,Y)$$と定義し、さらに$$p(C_j) = \sum_{t=1}^T \alpha_t(C_j) p_t(C_j)$$と定義する[おいおい\(\alpha_t(\cdot)\)ってなんだよ…]。で、すべての分割パターンの集合を\(P_k\)として、\(\sum_{j=1}^k p(C_j)\)を最小にする\(C\)が最適な分割だと考える。
  • \(k\)が未知の場合。Baragonaという人は、上で述べた交差相関関数に基づく類似性\(s_{i,j}\)を使って[…式が書いてあるけどよくわからん]。ほかに、データが共分散行列が等しい混合正規分布から得られてていると仮定してAICとかBICとかintegrated completed likelihood(ICL)とかで決めるやりかたもある[ICLってなんだ…]

3. 時系列クラスタリングの主要なアプローチ

3.1 raw-data-basedアプローチ
このアプローチでは、ふつう時間間隔は時系列間で同じ。長さは同じだったり違っていたりする。

  • Kosmelj & Batagelj (1990 J.Classification): relocation clustering. 一般化Ward基準を使っている
  • Lio et al.(2002): k-meansなどいくつかのアルゴリズムを比較
  • Golay et al.(1998): MRIデータでfuzzy c-means. 距離をいくつか比較
  • van Wijk & van Selow (1999): 凝集型階層クラスタリング
  • Kumar et al.(2002): 誤差が独立に正規分布に従うと仮定した距離関数を提案
  • Wismuller et al.(2002): 最小自由エネルギーベクトル量子化による決定論的アニーリング[そういわれてもなんのことだかさっぱり]
  • Moller-Levet et al.(2003): STS距離でfuzzy c-means
  • Kakizawa et al.(1998 JASA): 階層クラスタリングとk-means. J divergence と対称Chernoff情報ダイバージェンスを使用 [←これか…上で紹介されてたわけわかんない奴は…]
  • Shumway(26): カルバック・ライブラー弁別情報指標

[…こんな感じで研究が紹介されていくんだけど(あと2本ある)、めんどくさくなってきたし、Table 1.にきれいに整理されているのでメモは中断。表頭にとっている軸は勉強になるのでメモしておくと, (1)変数は単一か複数か, (2)長さは同じか違うか、(3)距離指標, (4)クラスタリングアルゴリズム, (5)評価基準, (6)適用分野]

3.2 feature-basedアプローチ
どんな特徴を使うのがよいかは適用分野に依存する、というのが難しいところ。
[研究紹介. 6本紹介されている。面倒になったので飛ばした。Table 2に要約されていて、表頭は(1)変数は単一化複数か, (2)特徴, (3)特徴選択(しないというのも含む), (4)距離指標, (5)アルゴリズム, (6)評価基準, (7)適用分野]

3.3 model-basedアプローチ
[研究紹介. 14本紹介されている。Table 3に要約されていて、表頭は(1)変数は単一か複数か, (2)モデル, (3)モデルの出力のうち関心ある部分(「係数」とか「残差」とか), (4)距離指標, (5)クラスタリングアルゴリズム, (6)評価基準, (7)適用分野. ろくに読んでいないけど、なんだか面白かった2本だけメモしておく]

  • Baran & Mazzola (1999 J.Comput.Graph.Stat): 楽譜の構造と演奏の構造のあいだにどういう関係があるかという研究。階層平滑化モデルという、バンド幅の階層構造と係数ベクトルからなるモデルを考えて[←???]、推定されたバンド幅を凝集的階層クラスタリングにかけて可視化する。
  • Ramoni et al. (2002, Mach.Learning): Bayesian clustering by dynamics, 略してBCDを提案。\(n\)本の単変量離散値時系列があるとして、それぞれをマルコフ連鎖に変換してからクラスタリングする(凝集的階層クラスタリング)。各クラスタが遷移行列を持つと考え、事後確率を最大化するモデルを選ぶ[←どの遷移行列とどの遷移行列をくっつけるか、ということかしらん]。[この後にもいろいろ書いてあるけど、元論文を読まないと理解できそうにない。ま、要するに時系列を時間一様な1次マルコフ過程として捉えると考えるということであろう。面白そうではあるが、自分の仕事の中でそういう場面があるかというと、ううううむ、ちょっと思いつかないかなあ]

4. 考察
[…レビューした研究の特徴。略…]
 概して言えば、時系列データのクラスタリングのあいだの主な違いは類似性の求め方にある。類似性さえ決まればあとは一般的なクラスタリングアルゴリズムが使える。ところがどんな類似性がよいかはデータに依存する。鍵はデータの特徴の理解と類似性指標の設計にある。
[…今後の展開とか。略…]

…先端の話を追いかけたレビューなので、仕事のうえで役に立つかどうかでいえば、前に読んだTSClustパッケージのビニエットのほうがはるかに役に立つんだけど、ま、なんだか勉強になったような気がしますってことで、ひとつ…