[Julia] SAX (Symbolic Aggregate approXimation)を復習した


レポジトリです

系列データの離散化法として(おそらく)最も有名なSAXを復習しました.簡単にまとめると

  1. 系列データをいくつかの部分系列に分割
  2. 個別の部分系列で平均値を計算
  3. 記号と分割点(breakpoints)を計算
  4. 個別の平均値がどの記号に当て嵌まるのか分割点から計算

という手法です.Keoghらの前提では分割点の計算にガウス分布を使っていますが, 世の中のノラ実装を見ていると,適当にuniform dist.と仮定して記号化してるものもありました.

Keoghらのbreakpoints計算方法はサイトにMatlabコードが公開されていて簡単です.

startRange = 2;
stdc = 1;
endRange = 512;
table = cell(endRange-startRange, 1);
for r = startRange:endRange
  table{r-startRange+1} = norminv((1:r-1) / r, 0, stdc);
end

Juliaにはnorminvが実装されていないので少し考えましたが,とりあえずStatsFunsライブラリに実装 されているnorminvcdf関数で代用しました.計算結果も同じでした(Matlabの実行結果は Octave 4.0.0で確認,JuliaはJulia 0.5で確認.どちらもUbuntu 16.04で実行). Juliaでは

v = collect(1:n-1) / n
vv = [norminvcdf(0.0, 1.0, elem) for elem in v]

のように計算しましたが,collectいらないと思います(未確認). 少し動作テストしたら,実際のデータに入れてみたいと思います.

人工データ例

元データ(random walkで作成)

正規化したデータとSAX(横バーで表現)

適当に検索して出てきた日本語の論文(全国大会など)

関連サイト