部分時系列クラスタリングの理論的基礎

Tokyo Research Laboratory
2A-1-2
部分時系列クラスタリングの
理論的基礎
IBM東京基礎研究所
井手剛
| 2006/ / | 第20回人工知能学会全国大会
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
目次
 問題を理解する
 滑走窓とずらし演算子の関係を理解する
 k平均クラスタリングを固有値問題に焼きなおしてみる
 正弦波効果を導出してみる
 実験結果


Page 2
う、うなり？！
白色雑音なのに正弦波？！
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
問題を理解する
Page 3
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
部分時系列クラスタリングとは： 1本の（長い）時系列から部分系列を多数
生成し、それらをクラスタリング。クラスタ中心＝代表パターン、のはず。
 滑走窓方式で部分時系列を生成
 生成された部分系列を、独立なベク
トルとしてk平均クラスタリング
各クラスターの総和平均
が「クラスタ中心」
代表パターン
Page 4
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
正弦波効果とは：滑走窓式部分時系列クラスタリング（STSC）を使ってパ
ターンを抽出すると、なぜか正弦波が出てくる！
 Keoghによる衝撃的な報告： “Clustering
of time series subsequences is
meaningless”, ICDM ’03
 k平均の結果、クラスタ中心は正弦波に！
元のパターンとは似ても似つかない
ほとんど入力時系列には依存しない


なぜ正弦波が出るのかは未解決問題
「なぜ」を問わぬ所に進歩はない！
Page 5
| 2006/ / |
こんなやつを30個
づつ連結。長い時
系列を作る
K平均STSC実行
クラスタ中心は正弦波に。
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
滑走窓とずらし演算子の関係を理解する
Page 6
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
時系列の最初と最後をつないで、リングにする。そのリングを1次元の周期
格子だと思うと、時系列は、格子上の「状態」として理解できる。
{xt | t  1,2,..,n}
x1 x2
xn
t2
tn
t1
格子点 l をひとつの基底 el だとみ
なし、時系列をn 次元ベクトルΓだ
と考えることにする。
格子点 l に値 xl を割り振る。
（人為的に）周期的境界条件を課す
Page 7
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
部分系列 spは格子上の並進演算子を使ってスマートに表現できる。
「ずらして、ちょん切る」
w
n
1
n
1
後ろに p 歩ずらして第 1 ~ w サイト
を切り出したもの
※並進演算子（ずらし演算子）は基底の外積を使って表せる
状態 e2 を l だけずらしている例。
Page 8
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
k平均クラスタリングを固有値問題に焼きなおしてみる
Page 9
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
k平均法は2乗誤差を最小化する算法。
その目的関数はρという行列を使ってシンプルに書ける。
k平均クラスタリングは、2乗誤差を最小にする算法。
Duda et al. の
教科書参照。
クラスタ中心
われわれの表記では下記のように美しく表せる。
ただし、
密度行列と呼ぶ。
Page 10
| 2006/ / |
クラスタ中心に対応する
状態ベクトル
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
k平均法の目的関数の最小化は、
密度行列についての固有値問題を解くことで達成できる。
Eの最小化は、下記の固有値問題と同等（説明略）。
ρは、部分系列を並べた行列Hを使って表せる：
つまり、j 番目のクラスタ中心 u(j) は、行列HHTの固有ベ
クトルとしても求められる。
H=
（HのSVDとも同等。）
密度行列（= HHT）の固有値問題として正弦波効果を調べてみよう。
Page 11
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
正弦波効果を導出してみる
Page 12
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
密度行列はフーリエ表示でほとんど対角的となるので、
その固有状態はフーリエ状態（＝正弦波）そのもの。
ρは並進演算子を使って表せる（略 ←Dirac記法で書かないとなかなか気づかない！）。
そのため、フーリエ基底が相性よさそう。基底の変更をする。
波数。
この { fq } を基底にして w×w行列を作ると、ρの主要項は対角行列になることを示せる：
（対角成分）＝（各フーリエ成分のパワー）
特定のfqのパワーが大きいときに
は、非対角成分の寄与は小さい。
特に、w =n （部分系列長＝全系列長）の時は第2項は厳密にゼロ。
定理
時系列の（窓幅wの）パワースペクトルにおいてある波数 f が支配的ならば、k 平均のクラ
スタ中心は波長 w / |q| の正弦波でよく近似される。これは入力時系列の詳細によらない。
Page 13
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
実験結果
Page 14
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
実験結果（1/3）: CBFデータに対する理論の確認。パワースペクトルとクラ
スタリング結果の対応を理論は完全に説明する（k=3, w=128）。
CBFデータについてのパワースペクトル。
いずれも |q| = 1 にウェイトが集中。
波長wの正弦波が出るはず。
k平均クラ
スタ中心
波長wが３つ。
波長wが２つと、w/2がひとつ
SVD
Page 15
| 2006/ / |
↑固有ベクトル間の直交条件による
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
実験結果（2/3）:もっと面白い例。Synthetic Control Chartという標準デー
タでは、「うなり」がクラスタ中心において観測される（k=2, w=60）。
このようなインスタンスを100個づ
つ連結して、長い時系列を作る。
パワースペクトルはCBFデータと異
なるので、クラスタリング結果も異
なるはず。
|q| = 4, 5, 6 にピーク
この3つの波が干渉して「うなり」を起こす。
うなりの波長も含めて、理論は下記のクラスタリング結果を完全に説明する。
Page 16
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
実験結果（3/3）: Normalデータだけをクラスタリングしたらどうなるか。窓幅
が全時系列長に近づくにつれ、正弦波が現れる（k=2, w=60と6000）。
k=2, w=60
k=2, w=n=6000 (全時系列長＝部分系列長)
パワースペクトルがほぼフラットでも、ほぼ純粋な正弦波になる。
→ 波数混合は起こらず、一番強いパワーを持つ波数にウェイト集中。
Page 17
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
まとめ
Page 18
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
まとめ
 正弦波効果の理論的理解は、データマイニング、機械学習における未解決の重要
課題だった。
 1次元格子上での密度行列理論を展開することで、正弦波効果の理論的由来をあ
らわに示すことに初めて成功した。
 それは、ここ数年発展してきた spectral clusteringの理論の、新しい別の定式化
になっており、機械学習の観点で意義深い。
 本論文の結果は、正弦波の擬パターンを回避する方法を考える上での重要な出
発点となっており、工学的観点からも意義深い。
Page 19
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
ありがとうございました。
Page 20
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
時系列の最初と最後をつないで、リングにする。そのリングを1次元の周期
格子だと思うと、時系列は、格子上の「状態」として理解できる。
{xt | t  1,2,..,n}
x1 x2
xn
t2
tn
t1
格子点 l をひとつの基底 el だとみ
なし、時系列をn 次元ベクトルΓだ
と考えることにする。
格子点 l に値 xl を割り振る。
（人為的に）周期的境界条件を課す
Page 21
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
部分系列 spは格子上の並進演算子を使ってスマートに表現できる。
Dirac記号は、並進演算子を陽に書けるので猛烈に見通しがよくなる。
w
n
1
n
1
後ろにp歩ずらして第1~wサイトを切り出したもの
※並進演算子（ずらし演算子）の具体的表現
状態 | 2 ＞を l だけずらしている例。
Page 22
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
k平均法は2乗誤差を最小化する算法。
その目的関数はρという線形演算子でシンプルに書ける。
k平均クラスタリングは、2乗誤差を最小にする算法。
Duda et al. の
教科書参照。
クラスタ中心
われわれの表記では下記のように美しく表せる。
ただし、
統計力学の用語を流用し
て、密度演算子、と呼ぶ
Page 23
| 2006/ / |
クラスタ中心に対応する
状態ベクトル
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
k平均法の目的関数の最小化は、ρについての固有値問題を解くことで達成
できる。それは通常の行列演算で計算可能。
Eの最小化は、下記の固有値問題と同等（説明略）。
などを普通のw次元のベクトルに戻して書き表すことも
できる。
つまり、j 番目のクラスタ中心 u(j) は、行列HHTの固有ベ
クトルとしても求められる
H=
ρ（もしくはHHT）の固有値問題として正弦波効果を調べてみよう。
Page 24
| 2006/ / |
© Copyright IBM Corporation 2006
Tokyo Research Laboratory
密度演算子ρの行列表現を求める。 ρはフーリエ表示でほとんど対角的とな
るので、その固有状態はフーリエ状態（＝正弦波）そのもの。
ρは並進演算子を使って表せる（略 ←Dirac記法で書かないとなかなか気づかない！）。
そのため、フーリエ基底が相性よさそう。基底の変更をする。
波数。
のような w×w行列を作ると、
特定のfqのパワーが大きい
ときには、非対角成分の寄
与は小さい。
フーリエ成分 fq のパワー
特に、w =n （部分系列長＝全系列長）の時は第2項は厳密にゼロ。
定理
時系列の（窓幅wの）パワースペクトルにおいてある波数 f が支配的ならば、k 平均のクラ
スタ中心は波長 w / |q| の正弦波でよく近似される。これは入力時系列の詳細によらない。
Page 25
| 2006/ / |
© Copyright IBM Corporation 2006

Download Report