DEIM Forum 2013 E1-3

SAX 適用において利用者が注意すべき特性についての検討松田 成美†

大西 史花†

渡辺知恵美†† お茶の水女子大学理学部情報科学科 〒 112-8610 東京都文京区大塚 2-1-1
E-mail: †{g0920537,onishi.ayaka,chiemi}@is.ocha.ac.jp
あらまし 時系列データの表現手法はこれまで多くの研究者たちによって提案されてきた．その中の一つに， Lin らが提案した， Symbolic Aggregate Approximation （ SAX ） がある．SAX は有効な手法であるとして広く研究の場で使われているが，多様な時系列データ全てにおいて万能に適用できると限らない．SAX の利点を最大限に生かす為，利用者が注意すべき SAX の特性を明らかしたい．よって，本稿では SAX 適用時に起こりうる 2 つの問題点について指摘，検証を行う．1 つめに，「正規化された時系列データはガウス分布に従う」という前提条件は正しいのか，という点，2 つめに，実データと SAX 適用後のデータで，距離関係が逆転している可能性がある，という点である．
検証の結果，前者は成り立たない可能性が高く，その結果後者のような影響が生じるということが分かった．
キーワード

時系列データ

Narumi MATSUDA† , Ayaka ONISHI† , and Chiemi WATANABE†† Humanities and Sciences, Ochanomizu University 2-1-1 Ohtsuka, Bunkyo-ku, Tokyo, 112-8610 Japan
E-mail: †{g0920537,onishi.ayaka,chiemi}@is.ocha.ac.jp

1. は じ め に従う」という前提条件は正しいのか，という点である．SAX では，まずデータを正規化した後，文字列に変換するための操作

私たちの日常には，株価や医療，気象データのような，さまを行う．文字列変換の際，変換後の各文字が等確率で出現する

ざまな時系列データがあふれている．また，スマートフォンなようにデータの分割区間を設定する．この分割点は，「正規化さどの急速な普及により，一人一人が扱うデータ量も増え，そのれた時系列データはガウス分布に従う」という前提に基づき，管理により一層の効率化が求められている．また，できるだけガウス曲線に従って決定している．しかしここで，正規化されその情報を失うことなく正しく保持したまま，データ量を削減た時系列データは本当にガウス分布に従うのか，という疑問がして処理を高速化したいという要求が高まっている．そのため，出てくる．SAX 論文 [1] 中では，この前提条件が成り立つことデータ量の削減や処理時間短縮の面から索引の付与が不可欠とを，実験結果を以て示している．しかしながら，これはわずかなっている．

8 種類の時系列データについて検証した結果に基づいた見解でデータに索引を付与するさまざまな表現手法は，これまで多あり，他のデータでは成り立たない可能性がある．

くの研究者たちによって提案されてきた．その中の一つに， Linふたつめに，実データと SAX 適用後のデータで，距離関らが提案した， Symbolic Aggregate Approximation （ SAX係が逆転している可能性がある，という点である．データ上）[1] がある．SAX は有効な手法であるとして，広く研究の場の点 X ，Y ，Z があるとき，その距離関係が，実データではで使われている．しかしながら，多様なデータ全てにおいて汎| XY |<| Y Z | であるのに，SAX 適用後に | XY |>| Y Z | の用性の高い手法を提案することは難しく，SAX がすべての時ように逆転してしまうことがある．このような距離の逆転現象

系列データにおいて万能に適用できると限らない．扱うデータは，階層的クラスタリングや k 近傍法のように順序関係を重視によっては，常に正しいマイニング結果を得られない可能性もする手法では，逆転によって生じた誤差を必要以上に拡大してあるといえる．利用者が注意すべき SAX の特性がわかれば，しまう可能性がある．

SAX の利点を最大限に生かすことができるだろう．そこで本以上の可能性を検証するため，我々はいくつかの時系列デー

稿では， SAX 適用時に起こりうる問題点を指摘するため，以タを用いて， SAX を適用した場合と元データでの結果を比較下の２点について検証する．

する．そして，先に述べた可能性がどういうときに起こりうる

まずひとつめに，「正規化された時系列データはガウス分布にのかを調査する．この検証により，利用者が注意すべき SAXの特性がわかり，その利点を最大限に生かすことができる．本

稿では，SAX 適用時に起こりうる問題点についての具体例を用いた説明と，実験による検証結果について述べる．
本稿の構成は以下の通りである．第 2 節では本研究の研究対象手法である SAX について述べ，第 3 節では SAX を使用する際の問題点について述べる．第 4 節ではその問題が起こる場合の評価実験について述べ，そして第 5 節でまとめと今後の課題を述べる．

(a) 正規化した元データを(b) PAA 表現：各区間ご区分線で分割との平均値に置き換え(c) ガウス分布に従い分割点を(d) 対応する文字列にマッピ

設定

ング

2. SAXSAX とは， 時系列データを文字列に変換する手法である．
同じく時系列データの表現手法として，離散フーリエ変換や離散ウェーブレット変換などがある．それら 2 つとは異なり，最終的に文字列に変換されるということが SAX の大きな特徴である．これにより，パターン検索など，自然言語処理分野における文字列処理アルゴリズムが適用可能となる．その他の特徴
としては， 中間段階で Piecewise Aggregate Approximation

図1

時系列データへの SAX 適用( PAA ) [4] によって次元削減を行うことが挙げられる．PAAは時系列データをある区間で平均化する手法であり，離散フーれの領域を a , b , c とする．
（図 1(c)）そして，データを対応リエ変換や離散ウェーブレット変換などのような複雑な技術とする文字列に置き換える．
（図 1(d)）ここで得られた文字列は，比較すると直観的で単純である．それによって SAX 自体も単Ĉ = cˆ1 , cˆ2 , · · · , cˆ8 = bccbaaba と表せる．

純なアルゴリズムとなっており，他の既存手法と比較してマイ分割点は，ガウス曲線のもとで各記号が等確率で出現するよ

ニングのしやすい有効な手法として，多くの研究分野で使われうな領域に分割されるよう決定する．つまり，正規化された時ている．

系列はガウス分布に従うという前提条件に基づき，ガウス曲線の下の領域が同じ面積になるように分割する．したがって，

2. 1 SAX の適用手順
SAX の時系列データへの適用手順を以下に示す．
(1) データを平均 0，分散 1 の正規分布に従うように正規化

分割点はアルファベットサイズ a によって決まっており，入力データに依存しない．図 2 のように，分割点の値は，アルファベットサイズに応じてあらかじめ計算しておくことができる．

する(2) 正規化したデータを PAA 表現に変換する
i データの時間軸を等間隔に区分する (図 1(a))
ii 各区間ごとに平均値を計算し，データの値をその平均値に置き換える (図 1(b))(3) 文字列化
i 分割点を設定 (図 1(c))

図2a = 3 ∼ 10 のときの分割点の値 βiii 対応する文字列にマッピング (図 1(d))
たとえば，長さ n = 128 の時系列 C = c1 , c2 , · · · , c128 に

例えば，アルファベットサイズを 5 に設定した場合，4 つの分SAX を適用したいとする．準備として，2 個のパラメータ値

割点 β1 ∼ β4 は，(β1 , β2 , β3 , β4 ) = (−0.84, −0.25, 0.25, 0.84)をあらかじめ設定しておく必要がある．変換後のデータの長さのように求めておくことができる．

あるいは何個の文字に変換したいかを表す文字列長 w と，何種類の文字に変換するのかを表すアルファベットサイズ a である．ここでは，文字列長 w = 8 ，アルファベットサイズ a = 3とする．つまり，変換後のデータは 3 種類のアルファベット 8個からなる文字列となる．まず，この時系列データ C を平均0，分散 1 の正規分布に従うように正規化する．次に，正規化したデータの時間軸を等間隔に 8 分割（ w = 8 ）する．図 1(a)で，赤線が正規化した元データ C ，点線が区分線になっている．次に，各区間ごとに値を平均値に置き換える．これによって得られたデータは， C̄ = c¯1 , c¯2 , · · · , c¯8 と表せる．ここでは，アルファベットサイズ a = 3 に従って分割点を設定し，それぞ2. 2 データ間の距離ともに長さ n の 2 つの時系列データ Q, C 間の距離の定義を，元データと SAX 適用後データそれぞれについて説明する．
まず，元データでの Q, C 間の距離

D(Q, C)は以下の図3 で表されるユークリッド距離であり，式 (1) で求められる．
vu nu∑
D(Q, C) ≡ t (qi − ci )2(1)i=1

ま た ，SAX 適 用 後 デ ー タ で のQ, C間の距離

M IN DIST (Q̂, Ĉ) は図 4 で表される文字列間の距離であり，(a) 文字列間距離

図6(b) 距離表

アルファベットサイズ a = 4 のとき

図 3 元データ間の距離（ユークリッド距離）

3. SAX の注意点の検証

式 (2) で求められる．

SAX を時系列データに適用する際，その特徴から考えられる 2 つの可能性について指摘する．

3. 1 「正規化した時系列はガウス分布に従う」という前提
条件

SAX 論文中では，8 個の異なる時系列データから抽出した長さ 128 のサブシーケンスデータを用い，それぞれ正規化してガウス分布に従うか調べる実験を行っている．正規化したデータ
図 4 SAX 適用後データ間の距離（文字列間の距離）値の累積分布の正規確率をプロットし，その視覚的特徴から用いたデータがガウス分布に従っていることを示している．その√M IN DIST (Q̂, Ĉ) ≡vu w∑nut (dist(qˆi , cˆi ))2w i=1

結果，全ての時系列データでも同じようにいえるとして議論を進めている．

(2)

正規化した時系列データがガウス分布に従っているという前提条件が成り立つことの利点は，文字列化の際，変換する文字変換後の 2 つの文字 qˆi , cˆi 間の距離 dist(qˆi , cˆi ) は文字 qˆi がの種類数に応じた分割点をあらかじめ決定できる，ということ

とりうる値と文字 cˆi がとりうる値の差が最少となるときの最であるまた，分割点に応じてあらかじめ距離表を作成しておく少値で表わされる．たとえば図 5 で，文字 a と文字 d の距離はことが可能であり，計算時間の短縮につながる．

dist(a, d) ，文字 a と文字 b の距離は dist(a, b) ，文字 b と文
字 d の距離は dist(b, d) によって定義される．

しかしながら， SAX 論文中で用いたデータが偏った結果を導いている可能性を否定できない．つまり SAX 論文中で用いたデータ以外のデータでも同じような結果が得られるとは限らないということである．そこで他のデータで同じように正規確率がガウス分布に従うか検証し，従わない場合もあることを示す．
たとえば，同じような傾向を持つデータを考える．お茶の水
女子大学情報科学科（お茶大情報科）1 年生 5 人分の，1 日のツイッターでのツイート数を時間ごとに表した時系列データ（図7）があるとする．
図5

文字列間の距離 dist(qˆi , cˆi )ここで第 2. 節で述べたように，「正規化した時系列はガウス分布に従う」という前提条件に基づいて分割点を決定していることに改めて注目する．分割点の値はデータに依存せず，分割数，すなわちアルファベットサイズに応じて決まっている（図??）ため，文字列間の距離もアルファベットサイズに応じて決まる．
以下の図 6 でアルファベットサイズ a = 4 の時の例を示す．

3 つの分割点は (0.67 , 0 , -0.67) である．文字列間の距離は距離表のように決まっており，dist(a, d) = 1.34 ， dist(a, b) = 0

図 7 お茶大情報科 1 年生の 1 日のツイート数， dist(b, d) = 0.67 となる．
この 5 人は通学，授業，睡眠など生活リズムがほぼ同じである．そのため，授業中や睡眠時間のツイート数は少なく，休み時間や放課後，夕方から夜にかけてのツイート数が多くなっているなど，グラフの傾向が似ていることがわかる．この 5 つの時系列データを正規化し，その頻度をヒストグラムで示した．
（図 7）見た目から，ガウス分布に従っていないことがわかる．

図 9 距離の逆転現象 : 距離関係が，実データでは | XY |<| Y Z | であるのに，SAX 適用後では | XY |>| Y Z | のように表されてしまう

図 8 ツイート数の頻度分布のほうが data3 , data4 間の距離より大きいとする．しかし，SAX 適用後に距離を測定するとき，このデータ上のある地点また，ガウス分布に従うことを数値的に確認するために，で，先ほど述べたような距離の逆転現象が起こる，ということ

ジャック-ベラ検定を用いる．以下で，ジャック-ベラ検定についが頻繁に起こったとする．このとき，データ全体同士での距離て簡単に説明する．
ジャック-ベラ検定
ジャック-ベラ検定とは，統計学において標本データがガウス関係が，SAX 適用後， data1 , data2 間の距離より data3 ,data4 間の距離のほうが大きくなり，データ間の距離の逆転が起こってしまう．

分布に従う尖度と歪度を有しているかどうかを調べる適合度検定である．検定統計量 JB は，以下のように定義される．
[]n1
JB =S 2 + (K − 3)264

N ：標本数，S：歪度，K ：尖度
もし標本分布がガウス分布であれば，この検定統計量は自由度2 のカイ二乗分布に従う．有意水準が 5 ％として，この数値が大体 6 よりも小さければ，ガウス分布と見なして構わない．
お茶大情報科 1 年生の 1 日のツイート数データを正規化したデータにジャック-ベラ検定を適用してみると，JB = 16.9 > 6

図 10

元データでは (data1,data2 の距離)>(data3,data4 の距離) だが， SAX 適用後， (data1,data2 の距離)<(data3,data4 の距離) となり，データ間の距離の逆転現象が起こっていることがわかるという結果が得られた．従って，このデータがガウス分布に従っていないことが数値的にも示された．

このようなデータセットに，階層的クラスタリングを行う．

我々は，この例のように，データの傾向が同じであるデータ

階層的クラスタリングは，もっとも距離の近いデータをグルーセットを使用する場合，「正規化した時系列はガウス分布に従う」プ化していく，ということを繰り返すようなクラスタリング法という前提条件が成り立たないのではないかと予測している．

である．元データでは図 11 のような結果になるのは明らかで

3. 2 距離の逆転現象ある．しかし， SAX 適用後のデータでは，元データと異なる結果となってしまう．

第 2. 節で述べたとおり， SAX による符号変換はガウス分布の等面積分割によって行われる．この時，それぞれの領域の幅は中心が密，外側が疎となる．例えば図 9 のようなデー
タ上の 3 点 X, Y, Z を考えると，実際の距離関係は明らかに| XY |<| Y Z | である．しかし， SAX 適用後では X は文字b ， Y は文字 d ， Z は文字 e に変換されるため，dist(b, d), dist(d, e) によって求められる．2. で述べた距離表に従ってこ

元データ

れを計算すると，XY 間の距離は dist(b, d) = 0.5 ， Y Z 間の図 11 クラスタリング結果

距離は dist(d, e) = 0 となる．従って | XY |>| Y Z | となり，距離関係が逆転してしまう．
このような逆転現象はクラスタリングの精度に悪影響を与えると考える．以下に簡単な例を示す．
下の図 10 のような 4 つのデータからなるデータセットがあるとする．元データでの距離関係が， data1 , data2 間の距離SAX 適用後データ

図 11 のようなクラスタリング結果の違いが，距離の逆転現象によるものなのか，また，距離の逆転現象がどういうときに起こるのかを，今後検証する．そのための実験方法について第4. 節で述べる．

4. 実

験

実験のために，以下の 2 つのデータを用いる．
データ 1

筆圧データ [2]

UCI の Machine Learning Repository 中の Character Trajectories Data Set である．(図 12(a)) このデータは同一人物から得た 2858 個の筆跡データセットで，ペンタブレットによ(a) 筆圧データる入力を軌跡と筆圧からなる 3 次元のデータとして取得したものである．本実験ではこの中から筆圧のデータだけを取り出して，1 次元のデータとして扱うことにする．
データ 2Control Chart [3]Robert Alcock（1999）により生成された 600 の合成データである．(図 12(b)) 100 ずつ，ノーマル，サイクリック（周期的），増加傾向，減少傾向，上方移動，下方移動の 6 種類に分(b) ControlChart類されている．本実験では簡単のため，6 種類から 17 個ずつ，

図 13 ヒストグラムとジャック-ベラ検定結果

計 102 個のデータを取り出して扱った．

(a) 筆圧データ(b) ControlChart

図 14

実距離関係は | AB |<| CD | だが，SAX 文字列間距離は逆になっている

図 12 デ ー タ 例られる．しかしながら，筆圧データでは 44.8 ％となり，半分近4. 1 「正規化した時系列はガウス分布に従う」という前提条くが逆転しているという結果になっている．

件の検証
それぞれのデータにおける値の頻度分布を調査する．調査方法は，ヒストグラムを作成し，視覚的に確認する方法と，3. 1
で述べたジャック-ベラ検定を用いて，数値的に確認する方法の逆転現象が起こる確率
理論値

0〜0.87 ％筆圧データ

44.80 ％

Control Chart

0.10 ％

2 つである．結果は図 13 のようになり，ガウス分布に従わないことが分かる．

4. 2 距離の逆転現象が起こる場合と確率の検証
まず定性的分析として，距離の逆転現象が起こる理論確率を

表 1 距離の逆転現象が起こる確率

この原因として考えられる可能性として，実際はガウス分布に従っていないデータに対し，従っているものとみなしてＳＡ求めた．この理論確率とは，4 つの時系列データにおけるあるＸを適用したため，ということが考えられる．SAX 適用時の1 時点を考えたとき，図 14 の例のような逆転現象がデータ全分割点の設定は，4. でも指摘したように，ガウス分布に従うと体で起こる確率のことである．SAX 適用後の文字種類数が 50いう前提条件に基づいて行う．従って，前提条件が成り立たな個であるとき，その確率は 0〜0.87 ％であった．この程度であいデータへの SAX 適用では，本来なら細かく分割されるべきれば，逆転が起こっていてもデータ全体には大きな影響は与え部分の分割が大まかに分割されるなど，分割点の設定が不適当ないといえる．
次に定量的分析として，データを用いて距離の逆転現象がであった可能性がある．

起こる実際の確率を求めた．実データ間の距離と SAX 適用後データ間の距離それぞれの測定は，タイムワーピングに基づいて行った．その結果，逆転が起こる確率は表 1 のようになった．
この結果より， Control Chart では実際の計算値による確率と理論値で大きな差がないことが分かる．従って距離の逆転現象が起こる確率は非常に低く，データへの影響は少ないと考え

また，筆圧データに階層的クラスタリングを適用した結果は
図 15 のようになった．簡単のため，9 データ（ test1，2，3，4，12，45，90，92，94）のみをクラスタリングした．元データを基準とし， SAX 適用後に結果が異なっている部分を見ていく．

test2，4 と test45 に着目すると，元データでは階層の下位でクラスタリングされているが，SAX 適用後では，かなり上位
でクラスタリングされている．また， test92，94 と test1，12

も同様である．このように，SAX 適用によって距離の逆転現象が頻繁に起きた場合，クラスタリング結果にも影響を与えてしまうことが分かった．

(a) 元データ(b) SAX 適用後データ

図 15

筆圧データにおけるクラスタリング結果：元データと SAX 適用後データでクラスタリング結果が異なっている

5. まとめと今後の課題
本稿では， SAX の概要について説明し，SAX 適用時に起こりうる問題点について具体例とともに説明した．また，扱うデータによっては，クラスタリング結果が実際と大きくかけ離れてしまう可能性を指摘した．実験の考察より，「正規化したデータがガウス分布に従う」という前提条件は成り立たない可能性が高く，それが距離の逆転現象を引き起こす原因となる可能性が高いといえる．従って SAX 適用時には，正規化したデータがガウス分布に従っているか否かを調べ，従っていない場合には分割点の設定方法を変えるなどの考慮をする必要があるといえる．今後の課題として，他の多様なデータにおいて距離の逆転現象が起こる確率を求め，確率が高くなるときのデータの傾向を分析したい．また，クラスタリング結果へ大きく影響を与える時の傾向についても分析したい．最終的には，正規化したデータがガウス分布に従わない場合の分割法について，有効な手法を提案していきたい．

文

献[1] Jessica Lin， Eamonn Keogh， Stefano Lonardi， and Bill
Chiu．: A Symbolic Representation of Time Series， withImplications for Streaming Algorithms，In SIGMOD workshop， 2003．
[2] Ben H Williams，UCI Machine Learning Repository．:
http://archive．ics．uci．edu/ml/index．html，February

2012[3] Dr Robert Alcock，Synthetic Control Chart Time Series．:
http://archive．ics．uci．edu/ml/databases/synthetic_control/[4] Yi， B， K．
， and Faloutsos， C．: Fast Time Sequence Indexing for Arbitrary Lp Norms．In proceedings of the 26st
VLDB Conference， Cairo， Egypt， 2000．