« 読了：「R言語徹底解説」 | メイン | 読了：Japkowicz & Stepeh (2002) 機械学習におけるクラス不均衡問題について実験しました »
2018年4月30日 (月)
Montero, P., Vilar, J.A. (2014) TSclust: An R Package for Time Series Clustering. Journal of Statistical Software, 62(1).
時系列クラスタリングのRパッケージTSclustのビニエット. 仕事の都合で読んだ。
イントロダクション
時系列間の類似性をどうやって調べるか。いろんなアプローチがある。
- 時系列を一対一に対応させ、ユークリッド距離なりなんなりを求める。
- それぞれの時系列からなんらかの特徴を抽出し(自己相関とか)、それを比べる。結局は次元縮約していることになる。
- それぞれの時系列の背後になんらかのモデルをあてはめ(ARIMAモデルとか)、モデルを比べる。
- 時系列の複雑性を比べる。たいていはコルモゴロフ複雑性に基づく指標を用いる。
とかとか。類似性さえ決まってしまえば、あとは一般的な分類手法(k-meansとか)などを用いて分析することが多い。
というわけで、ご紹介しましょう、TSclustパッケージです。時系列間のさまざまな類似性指標をご提供します。ついでにクラスタリングアルゴリズムもご提供します。
TSclustが提供する類似性指標
$X_T = (X_1, \ldots, X_T)^T, Y_T = (Y_1, \ldots, Y_T)^T$とします。
第1グループ, モデル・フリーなアプローチ。
まずはローデータに基づくタイプから。
- Minkowski距離:
$d_{L_q}(X_T, Y_T) = \left( \sum_t(X_t - Y_t)^q\right)^{1/q}$。
$q$は正の整数で、1ならマンハッタン距離、2ならユークリッド距離になる。時間のシフトやスケーリングにきわめて敏感。時点は独立とみなされ、時点のpermutationに対して不変。 - Frechet距離。時系列から「順序を変えないm時点」$r$を次のように抜き出す。
$r = ((X_{a_1}, Y_{b_1}), \ldots, (X_{a_m}, Y_{b_m}))$
ここで$a_1 = b_1 = 1, a_m = b_m = T$。$a_{i+1}$は$a_i$と$a_{i+1}$のどちらか。$b_{i+1}$も同様。[いまいち腑に落ちない。それってすごくたくさん作れない？]
さて、こうして抜き出しうる$r$のすべての集合を$M$として、
$d_F(X_T, Y_T) = min_{r \in M} \left( max_{i = 1, \ldots, m} |X_{a_i} - Y_{b_i}|\right)$
要するに、時系列を扱うというより、順番だけを気にするわけだ。シフトやスケーリングに影響されない。$X$と$Y$の長さが違っていてもOK。 - Dynamic time warping距離 (DTW)。$M$をつくるところまでFrechet距離と同じで、
$d_{DTW}(X_T, Y_T) = min_{r \in M} \left( \sum_{i = 1, \ldots, m} |X_{a_i} - Y_{b_i}|\right)$ - 値における近接性と、その値の周りでの動的挙動における近接性の両方をカバーする適応的非類似性。まず、動的挙動のほうは一次の時間相関係数で捉える。
$CORT(X_T, Y_T) = \frac{\sum_t(X_{t+1}-X_t)(Y_{t+1}-Y_T)}{\sqrt{\sum_t(X_{t+1}-X_t)^2}\sqrt{\sum_t(Y_{t+1}-Y_{t})^2}}$
煩雑になるから省略したけど、どのサメーションも$t=1$から$T-1$まで回る。で、
$d_{CORT}(X_T, Y_T) = \phi_k[CORT(X_T, Y_T)] \times d(X_T, Y_t)$
とする。$d$は上記の$d_{L_q}$で$d_F$でも$d_DTW$でもよい。$\phi_k[\cdots]$は適応的なチューニング関数で、たとえば$k$を0以上の値として
$\phi_k(u) = 2 / (1+\exp(ku))$
とする、とか。
次に、時系列のなんらかの特徴に基づくタイプとしては
- 相関ベースの距離。まずPearson相関 $COR(X_T, Y_T)$という手がある。これをちょっと変形する提案もある。[省略するが、相関が負のときに非類似度がぐっと大きくなるようにするらしい。どういう動機があるんだろうか]
- 自己相関ベースの距離。$1$時から$L$次までの自己相関のベクトルを$\hat{\rho}_{X_T}, \hat{\rho}_{Y_T}$として、
$d_{ACF}(X_T, Y_T) = \sqrt{(\hat{\rho}_{X_T} - \hat{\rho}_{Y_T})^T \Omega (\hat{\rho}_{X_T} - \hat{\rho}_{Y_T})}$
$\Omega$は重み行列で、もし$I$にすれば、自己相関ベクトルのユークリッド距離になる。次数につれて減らしていくという手もある。なお、自己相関のかわりに偏自己相関を使うという手もある。 - ピリオドグラム・ベースの距離。[話が時間領域から周波数領域に移る。こういう話、超苦手なので、パス...]
- ノンパラメトリック・スペクトル推定量に基づく非類似性指標 [まだ周波数領域の話が続いている。パス...]
- 離散ウェーブレット変換に基づく非類似性指標 [どこまで続く泥濘ぞ。パス...]
- シンボル表現SAXに基づく非類似性指標。まず時系列を標準化する。で、これを$w$個の同じ長さのセグメントに切って、セグメント内で平均する(これをピースワイズ累積近似 PAA という)。で、なんだかよくわからんのだが、これを正規分布上の分位点に変換し、さらに文字に変換する(これをシンボリック累積近似 SAX という)。最後に文字列同士の距離をどうにかして求める。[←ま、全くわからん... あっけにとられた。ま、要するに次元縮約の方法なのであろう。見なかったことにしたい]
第2グループ, モデル・ベースなアプローチ。
まずはそれぞれの時系列にARIMAモデルをあてはめる。構造は手で決めてもいいし、AICとかで自動選択してもいい。推定は普通GLSでやる。
- Piccolo距離。まず時系列が非定常なら差分をとって定常にし、季節性があったら除去する[←か、軽くいうねえ... 全然違う時系列がたくさんあったらどうするんだ]。で、AR($k_1$), AR($k_2$)ををあてはめる(次数はAICかBICで選ぶ)。長さ$k_1, k_2$のパラメータ・ベクトルが得られるので、短い方の尻に0をいれて長い方に合わせる。で、差の二乗和の平方根を非類似性指標とする。[いやー、これはあれだな、長い時系列が少数あるときの手法だなあ]
- Maharaj距離 [略]
- Cepstralベースの距離
第3グループ、複雑性ベースの距離。
[圧縮ベースの指標、permutation distribution clusteringというのが挙げられている。誰がそんなもん読むか、全面的にパスだ。とはいえ、最後に出てきた話はこれらの話とは毛色が違い、ちょっと面白いのでメモしておくと...]
よく使われている非類似性指標では、複雑性の高い時系列同士は非類似性が高くなり、複雑なやつと簡単な奴が類似してしまう傾向があるので、既存の非類似性指標が複雑性の影響を受けないように補正するというアイデアがある。
いま、ローデータベースの類似性指標$d(X_T, Y_T)$があるとしよう。これを補正したい。まず、なんでもいいから複雑性を定義する。たとえば
$CE(X_T) = \sqrt{\sum_t^{T-1} (X_t - X_{t+1})^2}$
次に、$CE(X_T)$と$CE(Y_T)$のうち大きい方を小さい方で割り(複雑性が異なる程度を表す)、これを$d(X_T, Y_T)$に掛けてやる。こうすると複雑性が異なる時系列同士の非類似性が高くなる。[←なるほどねえ。細かい工夫があるものだ]
第4グループ、予測ベースの手法。将来の時点についての予測の分布が似ている奴同士を類似しているとみなす。当然ながらこの手法の結果は他のとは全然違ってくる。予測のためのモデルとしては、いろんなタイプの自己回帰モデルが使える。
時系列クラスタリングのツール
まあとにかくこのようにして、ペアワイズの非類似性行列が得られたとしましょう。クラスタリングのためには、p値に基づく階層クラスタリングのアルゴリズム、真のクラスタがわかっているときにそれとクラスタを比較するツール、などをご用意している。
もちろん他のパッケージも活用して下さい。たとえば:
- stats::hclust() [階層クラスタリング]
- cluster::agnes() [これも階層クラスタリング]
- cluster::diana() [これも階層クラスタリング。いま気がついたけど、clusterパッケージの関数名ってむりやり女性の名前にしているのだろうか...]
- cluster::pam() [k-medoids法。そうか、あとで時系列クラスタリングではk-means法はだめだという話が出てくるけど、k-medoidsならいいのか]
- clValid::clValid() [クラスタリングの妥当性を調べる関数]
- fpc::cluster.stats() [クラスタの距離ベース統計量を出してくれる由]
- clvパッケージ
非類似性指標を選ぶときの考慮事項
まず、形に基づく非類似性が欲しいのか、動的構造に基づく非類似性が欲しいのかを考えること。
- 前者の場合は、ローデータベースの指標か複雑性ベースの指標がよいだろう。ただし、データに含まれている特定の歪みに対して不変な指標をうまく選ばねばならない場合もある。たとえば、全体的な値の大きさの違いを事前の標準化で取り除くとか、時系列がワープしてる箇所に影響されないようにDTWを使うとか。一般に、形に基づく非類似性は短い時系列向き。
- 後者の場合は、特徴ベースの指標かモデル・ベースの指標がよいだろう。ただし、それぞれの指標が仮定している規則性に気をつけること。たとえば、TSclustが提供するモデルベースの指標は、背後に定常で線形な過程があるときにのみ使える。予測ベースの指標は1次自己回帰構造を仮定している。
- 予測ベースの指標は他とは全然ちがって、将来予測が似ている奴をくっつける。
クラスタリングの目的がはっきりしたら、上記指針で指標が絞り込める。次はパラメータをうまく調整せよ。計算時間も留意事項だ。
クラスタリングのアルゴリズムにも気をつけなさい。たとえば、ふつうのk-meansは「時系列の集合の重心」と時系列との距離を求めることになるけど、そんな重心が正しく定義できるかどうかわからない。Ward法はユークリッド距離が前提だけど、ユークリッド距離でいいのかわからない。
[なるほどね... この節を読んだだけでも、目を通した甲斐があった]
事例
[TSclustパッケージの使用例を３つ紹介。略]
。。。勉強になりました。
時系列の類似性って、いきなりユークリッド距離とか相関とったりしてはいかんのだろうとなんとなく思ってたのだが、それは場面による話であって、一概にダメともいえないようだ。ふうん。
それはそうと、あれですかね、やっぱし、いったん類似性行列を作んないといけないんですかね。何十万本も時系列があるときはどうしたらいいんだろうか。
論文：データ解析(2018-) - 読了：Montero & Vilar (2014) RのTSclustパッケージで時系列クラスタリング