2A-1-2 部分時系列クラスタリングの 理論的基礎 IBM東京基礎研究所 井手 剛 | 2006/ / | 第20回 人工知能学会全国大会

目次 問題を理解する 滑走窓とずらし演算子の関係を理解する k平均クラスタリングを固有値問題に焼きなおしてみる 正弦波効果を導出してみる 実験結果 う、うなり？！ 白色雑音なのに正弦波？！ | 2006/ / |

問題を理解する | 2006/ / |

部分時系列クラスタリングとは： 1本の（長い）時系列から部分系列を多数生成し、それらをクラスタリング。クラスタ中心＝代表パターン、のはず。 滑走窓方式で部分時系列を生成 生成された部分系列を、独立なベクトルとしてk平均クラスタリング 各クラスターの総和平均が「クラスタ中心」 代表パターン | 2006/ / |

正弦波効果とは： 滑走窓式部分時系列クラスタリング（STSC）を使ってパターンを抽出すると、なぜか正弦波が出てくる！ Keoghによる衝撃的な報告： “Clustering of time series subsequences is meaningless”, ICDM ’03 k平均の結果、クラスタ中心は正弦波に！ 元のパターンとは似ても似つかない ほとんど入力時系列には依存しない こんなやつを30個づつ連結。長い時系列を作る なぜ正弦波が出るのかは未解決問題 K平均STSC実行 「なぜ」を問わぬ所に進歩はない！ クラスタ中心は正弦波に。 | 2006/ / |

滑走窓とずらし演算子の関係を理解する | 2006/ / |

時系列の最初と最後をつないで、リングにする。そのリングを1次元の周期格子だと思うと、時系列は、格子上の「状態」として理解できる。 格子点 l をひとつの基底 el だとみなし、時系列をn 次元ベクトルΓだと考えることにする。 格子点 l に値 xl を割り振る。 （人為的に）周期的境界条件を課す | 2006/ / |

部分系列 spは格子上の並進演算子を使ってスマートに表現できる。 「ずらして、ちょん切る」 n 1 後ろに p 歩ずらして第 1 ~ w サイトを切り出したもの ベクトル・行列表記は陰に要素を表すので、演算子の作用を表すのが苦手（見通し悪い）。 ※並進演算子（ずらし演算子）は基底の外積を使って表せる 状態 e2 を l だけずらしている例。 | 2006/ / |

k平均クラスタリングを固有値問題に焼きなおしてみる | 2006/ / |

k平均法は2乗誤差を最小化する算法。 その目的関数はρという行列を使ってシンプルに書ける。 Duda et al. の教科書参照。 クラスタ中心 われわれの表記では下記のように美しく表せる。 ただし、 クラスタ中心に対応する状態ベクトル 密度行列 と呼ぶ。 | 2006/ / |

k平均法の目的関数の最小化は、 密度行列についての固有値問題を解くことで達成できる。 Eの最小化は、下記の固有値問題と同等（説明略）。 ρは、部分系列を並べた行列Hを使って表せる： H = つまり、j 番目のクラスタ中心 u(j) は、行列HHTの固有ベクトルとしても求められる。 （HのSVDとも同等。） 密度行列（= HHT）の固有値問題として正弦波効果を調べてみよう。 | 2006/ / |

正弦波効果を導出してみる | 2006/ / |

密度行列はフーリエ表示でほとんど対角的となるので、 その固有状態はフーリエ状態（＝正弦波）そのもの。 ρは並進演算子を使って表せる（略 ←Dirac記法で書かないとなかなか気づかない！ ）。 そのため、フーリエ基底が相性よさそう。基底の変更をする。 波数。 この { fq } を基底にして w×w行列を作ると、ρの主要項は対角行列になることを示せる： （対角成分）＝（各フーリエ成分のパワー） 特定のfqのパワーが大きいときには、非対角成分の寄与は小さい。 特に、w =n （部分系列長＝全系列長）の時は第2項は厳密にゼロ。 定理 時系列の（窓幅wの）パワースペクトルにおいてある波数 f が支配的ならば、k 平均のクラスタ中心は波長 w / |q| の正弦波でよく近似される。これは入力時系列の詳細によらない。 | 2006/ / |

実験結果 | 2006/ / |

実験結果（1/3）: CBFデータに対する理論の確認。パワースペクトルとクラスタリング結果の対応を理論は完全に説明する（k=3, w=128）。 いずれも |q| = 1 にウェイトが集中。 波長wの正弦波が出るはず。 k平均クラスタ中心 波長wが３つ。 波長wが２つと、w/2がひとつ ↑固有ベクトル間の直交条件による SVD | 2006/ / |

実験結果（2/3）:もっと面白い例。Synthetic Control Chartという標準データでは、「うなり」がクラスタ中心において観測される（k=2, w=60） 。 このようなインスタンスを100個づつ連結して、長い時系列を作る。 パワースペクトルはCBFデータと異なるので、クラスタリング結果も異なるはず。 |q| = 4, 5, 6 にピーク この3つの波が干渉して「うなり」を起こす。 うなりの波長も含めて、理論は下記のクラスタリング結果を完全に説明する。 | 2006/ / |

実験結果（3/3）: Normalデータだけをクラスタリングしたらどうなるか。窓幅が全時系列長に近づくにつれ、正弦波が現れる（k=2, w=60と6000）。 k=2, w=n=6000 (全時系列長＝部分系列長) パワースペクトルがほぼフラットでも、ほぼ純粋な正弦波になる。 → 波数混合は起こらず、一番強いパワーを持つ波数にウェイト集中。 | 2006/ / |

まとめ | 2006/ / |

まとめ 正弦波効果の理論的理解は、データマイニング、機械学習における未解決の重要課題だった。 1次元格子上での密度行列理論を展開することで、正弦波効果の理論的由来をあらわに示すことに初めて成功した。 それは、ここ数年発展してきた spectral clusteringの理論の、新しい別の定式化になっており、機械学習の観点で意義深い。 本論文の結果は、正弦波の擬パターンを回避する方法を考える上での重要な出発点となっており、工学的観点からも意義深い。 | 2006/ / |

ありがとうございました。 | 2006/ / |

時系列の最初と最後をつないで、リングにする。そのリングを1次元の周期格子だと思うと、時系列は、格子上の「状態」として理解できる。 格子点 l をひとつの基底 el だとみなし、時系列をn 次元ベクトルΓだと考えることにする。 格子点 l に値 xl を割り振る。 （人為的に）周期的境界条件を課す | 2006/ / |

部分系列 spは格子上の並進演算子を使ってスマートに表現できる。 Dirac記号は、並進演算子を陽に書けるので猛烈に見通しがよくなる。 n 1 後ろにp歩ずらして第1~wサイトを切り出したもの ベクトル・行列表記は陰に要素を表すので、演算子の作用を表すのが苦手（見通し悪い）。 ※並進演算子（ずらし演算子）の具体的表現 状態 | 2 ＞を l だけずらしている例。 | 2006/ / |

k平均法は2乗誤差を最小化する算法。 その目的関数はρという線形演算子でシンプルに書ける。 Duda et al. の教科書参照。 クラスタ中心 われわれの表記では下記のように美しく表せる。 ただし、 クラスタ中心に対応する状態ベクトル 統計力学の用語を流用して、密度演算子、と呼ぶ | 2006/ / |

k平均法の目的関数の最小化は、ρについての固有値問題を解くことで達成できる。それは通常の行列演算で計算可能。 Eの最小化は、下記の固有値問題と同等（説明略）。 などを普通のw次元のベクトルに戻して書き表すこともできる。 H = つまり、j 番目のクラスタ中心 u(j) は、行列HHTの固有ベクトルとしても求められる ρ（もしくはHHT）の固有値問題として正弦波効果を調べてみよう。 | 2006/ / |

密度演算子ρの行列表現を求める。 ρはフーリエ表示でほとんど対角的となるので、その固有状態はフーリエ状態（＝正弦波）そのもの。 ρは並進演算子を使って表せる（略 ←Dirac記法で書かないとなかなか気づかない！ ）。 そのため、フーリエ基底が相性よさそう。基底の変更をする。 波数。 のような w×w行列を作ると、 特定のfqのパワーが大きいときには、非対角成分の寄与は小さい。 フーリエ成分 fq のパワー 特に、w =n （部分系列長＝全系列長）の時は第2項は厳密にゼロ。 定理 時系列の（窓幅wの）パワースペクトルにおいてある波数 f が支配的ならば、k 平均のクラスタ中心は波長 w / |q| の正弦波でよく近似される。これは入力時系列の詳細によらない。 | 2006/ / |