順序保存カーネルを用いた時系列データ分類

順序保存カーネルを用いた時系列データ分類

Time series data classification using order preserving kernel

柏葉祐輝

1

_成澤和志

1

_篠原歩

1

Yuki Kashiwaba

1

_{Kazuyuki Narisawa}

1

_{Ayumi Shinohara}

1

1

_{東北大学大学院 情報科学研究科}

1

_{Graduate School of Information Sciences, Tohoku University}

Abstract: In this paper, we propose a new similarity measure for time series data, that is called

k-gram order preserving kernel. This kernel depends on the similarity of the shapes of data instead

of that of the values. Moreover, we propose a new classification method using the kernel without adjusting the parameter k. Furthermore, we confirm the superiority of the proposed method by computer experiment.

1

はじめに

時系列データは，工学や医療，経済など様々な分野で 活用されており，時系列データ解析に関する研究は盛 んに行われている．また，センサ技術の発達により，容 易に時系列データを取得することができるようになっ たため，扱うデータが非常に大規模になっている．そ のため，時系列データをより高精度かつ高速に解析す る手法が求められている． デ ー タ 解 析 の 基 本 的 な 問 題 の ひ と つ に ク ラ ス 分 類問題がある．クラス分類問題では，特徴ベクトル X ∈ X とラベル y ∈ {+1, −1} の組の集合 S = {(X1, y1) ,· · · , (Xm, ym)} が学習データとして与えら れ，未知のデータを分類するための識別関数 f :X → {+1, −1} を出力する．ここで，X を入力空間と呼ぶ． クラス分類は，大きく線形分類と非線形分類に分ける ことができる．非線形クラス分類では，カーネル関数 を用いて暗に事例を特徴空間へ写像してから解析を行 うことが一般的である．入力空間_{X の事例 X が非線形} 変換 ϕ :X → Y で特徴空間 Y へ写像されるとすると， カーネル関数は特徴空間での事例の内積_{⟨ϕ(X), ϕ(X}′)⟩ を計算する関数である．文字列データに対しては，事 例を長さ k の部分文字列を次元とする特徴空間へ写像 する k-gram カーネル [10] を用いた手法が分類問題に おいて高い精度を出している． 時系列データのクラス分類を行うためには，2 つの 時系列データ間の近さを定義する必要がある．データ 間の近さとして，類似度や距離など様々な類似性指標 が提案されきた [1, 4, 11]．時系列データに対する類似 性指標として，ユークリッド距離 [4] やユークリッド距 離を改良した Dynamic Time Warping（DTW） [1] な どが知られており，これらの類似性指標は各時刻での 値を用いて計算している． しかし，時系列データの近さを評価する場合には個々 の値よりも，系列内の相対的な順序関係を用いた方が 有用である場合がある．例えば，音楽データにおいて， 同じメロディーを C 調で弾いた場合と，G 調で弾い た場合では各時刻に鳴っている音名は違うが，全体と しての音程 (音の高低差) は一致しているため，特徴が 類似しているデータであるといえる．このような時系 列データの形状に対する類似性を用いてパターン照合 を行う技術として，順序保存照合と呼ばれる方法があ る [2, 3, 8, 9]． 順序保存照合問題とは，時系列テキスト T とパター ン P が与えられたとき，P と順序同型な T の部分系 列を出力する問題である．ここで，順序同型とは，系 列内の各値の順序関係が一致している関係のことをい う [9]．系列が順序同型であるかを判定するためには， 系列を順序関係で表す必要がある．系列をこのような 順序関係による表現に変換することは，順序保存符号 化，もしくは単に符号化と呼ばれている [2] [3]． 本研究では，k-gram カーネルの特徴空間の次元を， 長さ k の順序保存符号化した系列に拡張することで，系 列の形状を特徴とする類似性指標として k-gram 順序 保存カーネルを提案する．また，k-gram 順序保存カー ネルを単純にクラス分類手法に適用すると，パラメー タ k を適切に設定しなければならないという問題があ る．そこで，k を設定せずにクラス分類を行う分類手 法として二重ブースティングを提案する．さらに，計 算機実験によって k-gram 順序保存カーネルを用いた 提案手法と既存の類似性指標を用いた場合で，分類問 題における正答率と計算時間を比較する． 人工知能学会研究会資料 SIG-FPAI-B502-04

2

準備

時系列データは測定した時間 i をインデックスとした 実数 xi ∈ R を並べて表すことができる．データ長 N の時系列データ X は以下のように表すことができる． X = (x1, x2,· · · , xN)  ただし xi∈ R また，時系列データ X の i 番目から始まる長さ m 部 分系列 (xi, xi+1,· · · , xi+m−1) (1≤ i ≤ N − m + 1) を X(i,m)と表記する． 時系列データに対して，順序同型 [9] と呼ばれる関 係を定義する． 定義 1 (順序同型) 長さ N の 2 つの時系列データ X = (x1, x2,· · · , xN) と Y = (y1, y2,· · · , yN) が与えられた とき，任意の 1≤ i, j ≤ N に対して xi≤ xj ⇔ yi≤ yj が成り立つとき，X と Y は順序同型であるという． 時系列データが順序同型であるかを判定するために は，時系列データ上の各点の値を直接用いるのではな く，各点の値を相対的な大小関係で表す必要がある．時 系列データをこのような大小関係に変換することを順 序保存符号化，もしくは単に符号化と呼ぶ．時系列デー タを符号化したものを符号化系列と言い，系列 X の符 号化系列を Code (X) で表す．時系列データの部分系列 を符号化したものを符号化部分系列と言う．符号化し た系列が一致していれば順序同型である． 符号化の表現には様々な方法が提案されている [2, 3]． 中でも最も直感的な表現方法は，自然表現 [8] である． 自然表現では，時系列データの各点の値を系列内順位で 表現する．例えば，時系列データ X = (10, 15, 30, 21, 9) と Y = (13, 19, 31, 25, 7) を自然表現で符号化した系列 Codenr(X)，Codenr(Y ) は以下のように表現される． Codenr(X) = (2, 3, 5, 4, 1) Codenr(Y ) = (2, 3, 5, 4, 1) このとき，時系列データ X と Y は符号化した系列が 一致しているため順序同型である．

3

提案方法

3.1

k-gram 順序保存カーネル

ここでは，順序同型を用いた類似性指標として， k-gram 順序保存カーネルを提案する．この指標は，テ キスト間の類似度を表す k-gram カーネル [10] を時系 列データに対応させたものと言える． まず，時系列データに含まれる符号化部分系列の出 現頻度を表す順序保存符号化出現頻度を定義する． 定義 2 (順序保存符号化出現頻度) 長さ N の時系列 データ X = (x1, x2,· · · , xN) と長さ k ≤ N の符号 化系列 C = (c1, c2,· · · ck) が与えられたとき， ϕC(X) = N_−k+1∑ i=1

match(Code(X(i,k) ) , C) を X における C の順序保存符号化出現頻度と言う．こ こで， match (a, b) = { 1 (a = b) 0 (otherwise) である． ここで，長さ k のすべての符号化系列からなる集合を Ck _{={C | C は長さ k の符号化系列 } とする．k-gram}

順序保存カーネル（k-gram Order Preserving Kernel:

OPKk）を以下のように定義する． 定義 3 (k-gram 順序保存カーネル) デ ー タ 長 N ,M の 時 系 列 デ ー タ X = (x1, x2,· · · , xN)，Y = (y1, y2,· · · , yM) と任意の整数 k ≤ min(N, M) が与え られたとき，X と Y の k-gram 順序保存カーネルを以 下のように定義する． OPKk(X, Y ) = ∑ C∈Ck ⟨ϕC(X), ϕC(Y )⟩ 例 1 時系列データ X = (2, 5, 3, 4, 7, 9, 6) と時系列デー タ Y = (30, 42, 48, 38, 67, 79, 90, 69, 48) の 3-gram 順序 保存カーネルを考える．この例では，簡単のため符号 化方法として同じ値を許さない系列に対する自然表現 を用いる．まず，X と Y の長さ 3 の符号化部分系列は， Codenr ( X(1,3) ) = (1, 3, 2), Codenr ( X(2,3) ) = (3, 1, 2) Codenr ( X(3,3) ) = (1, 2, 3), Codenr ( X(4,3) ) = (1, 2, 3) Codenr ( X(5,3) ) = (2, 3, 1) Codenr ( Y(1,3) ) = (1, 2, 3), Codenr ( Y(2,3) ) = (2, 3, 1) Codenr ( Y(3,3) ) = (2, 1, 3), Codenr ( Y(4,3) ) = (1, 2, 3) Codenr ( Y(5,3) ) = (1, 2, 3), Codenr ( Y(6,3) ) = (2, 3, 1) Codenr ( Y(7,3) ) = (3, 2, 1) であるため，それぞれの順序保存符号化出現頻度は， ϕ(1,2,3)(X) = 2 ϕ(1,2,3)(Y ) = 3 ϕ(1,3,2)(X) = 1 ϕ(1,3,2)(Y ) = 0 ϕ(2,1,3)(X) = 0 ϕ(2,1,3)(Y ) = 1 ϕ(2,3,1)(X) = 1 ϕ(2,3,1)(Y ) = 2 ϕ(3,1,2)(X) = 1 ϕ(3,1,2)(Y ) = 0 ϕ(3,2,1)(X) = 0 ϕ(3,2,1)(Y ) = 1

となる．よって，系列 X と Y の 3-gram 順序保存カー ネルは， OPK3(X, Y ) = 2× 3 + 1 × 0 + 0 × 1 + 1× 2 + 1 × 0 + 0 × 1 = 8 となる． 長さ k の符号化系列の集合Ck _{の大きさは，符号化} の方法によっても変わるが，ほとんどの場合 k に対し て指数的に増加していく．例えば，同じ値を許す系列 に対する自然表現では，_Ck_{の大きさは以下の式で表さ}

れる Ordered Bell Number [7] となる．

a(k) = k ∑ i=1 ( k i ) a(k− i) そこで，k-gram 順序保存カーネルを効率的に計算す るため，系列 X に含まれている符号化系列に対しての み出現頻度を数えることでカーネル計算をする．長さ N の系列 X に含まれているすべての符号化部分系列の 出現頻度は，佐藤らの提案した接尾辞計数表現による 符号化と計算アルゴリズムを用いることで O(kN ) 時 間で計算することができる [12, 13]．このアルゴリズム を用いれば，系列 X, Y の k-gram 順序保存カーネルは O(k(|X| + |Y |)) 時間で計算することができる． また，本論文では k-gram 順序保存カーネルを以下 のように正規化して利用する． NormalOPKk(X, Y ) = OPKk(X, Y ) √

OPKk(X, X)OPKk(Y, Y )

以降，正規化した k-gram 順序保存カーネルを単に k-gram 順序保存カーネルと呼ぶ．

3.2

k-gram 順序保存カーネルを用いたクラ

ス分類手法

3.2.1 単純なクラス分類手法 クラス分類には，様々な手法が提案されているが，本 論文ではブースティング [6] と呼ばれる学習アルゴリ ズムを用いる．ブースティングは，弱仮説と呼ばれる 50%以上の正答率をもつ識別関数 h を組み合わせて，正 答率の高い統合仮説 f を生成する学習手法である．ブー スティングアルゴリズムはいくつか提案されているが， 本研究では AdaBoost [5] と呼ばれるアルゴリズムを使 用する． Algorithm 1 に AdaBoost のアルゴリズムを示す． AdaBoost は，ステップ t において弱仮説集合から弱

Algorithm 1: AdaBoost(tmax, ϵ)

弱仮説集合を H とする; 1 D1を初期の事例生成確率分布とし，t← 1 とする; 2 Repeat 3 分布 Dtで優位度が最も高い弱仮説 h∈ H を htとする; 4 htの重みを αtとする; 5 f (X) = sign(∑ti=1αihi(X)); 6 Dt+1を htと Dtをもとに更新 ; 7 t← t + 1 ; 8 Until (t = tmax) or (学習データでの統合仮説の正答率≥ ϵ); 9 得られた統合仮説 f (X) を出力; 10 仮説を一つ選び出し，重みを付けて統合仮説に線形結 合していく．この動作を 9 行目に示す終了条件を満た すまで繰り返す．このとき，T 回繰り返しが行われた とすると，以下のような統合仮説 f (X) を出力する． f (X) = sign ( _T ∑ t=1 αtht(X) ) ただし， sign(n) = { +1 (n≥ 0) −1 (otherwise) ， αt は 統 合 仮 説 に お け る 弱 仮 説 ht の 重 み で あ る ． AdaBoost は弱仮説 h1, h2,· · · , ht−1が間違いやすい事 例に対して正答率の高い弱仮説 htを統合仮説に追加す ることで, その弱点を補おうという考えに基づいている． 本論文では，AdaBoost の弱仮説として k-gram 順序 保存カーネルを基にした関数を提案する．学習データ として S =_{(X1, y1) ,· · · , (Xm, ym)} が与えられたと き，弱仮説集合 Hk opを以下のように定義する． Hkop={h(X, k) = sign(OPKk(Xi, X)− OPKk(Xj, X)) | 1 ≤ i, j ≤ m s.t. yi= +1, yj =−1} ただし，パラメータ k は事前に与えられているとす る．弱仮説集合を Hk opとして AdaBoost を行うこと で，k-gram 順序保存カーネルを用いた時系列データ分 類ができるようになる． 3.2.2 二重ブースティング 3.2.1 節で提案した k-gram 順序保存カーネルを用い た分類手法では，あらかじめパラメータ k を設定する 必要があった．しかし，時系列データによって最適な k の値は変わるため，事前に k を設定することは非常 に困難である．ここでは，事前にパラメータ k を設定 せずに分類を行う分類手法として，二重ブースティン グ（Double Boosting: DB）を提案する．二重ブース ティングのアルゴリズムを Algorithm 2 に示す．

Algorithm 2: DB(tmax1, ϵ1, tmax2, ϵ2) I1={} とする; 1 k← 2 とする; 2 Repeat 3 Hk opを弱仮説集合として AdaBoost(tmax1, ϵ1) を実行し， 4   得られた統合仮説を fkとする; I1← I1∪{fk} ; 5 k← k + 1 ; 6 Until (終了条件を満たす)or (k が最大) 7 fi∈ I1の学習データに対する正答率 riを求める; 8 I2={fi| ri= 1.0} とする; 9 if |I2| ≤ 1 10 I1を弱仮説集合として AdaBoost(tmax2, ϵ2); 11 得られた統合仮説を F とする; 12 else 13 fi∈ I2の多数決関数を F とする; 14 endif 15 関数 F を出力 16 学習データとして，S = {(X1, y1) ,· · · , (Xm, ym)} が与えられているとする．二重ブースティングでは，ま ず k = 2 から順に，Hk opを弱仮説集合として AdaBoost を行い，統合仮説 fkを生成する．得られた統合仮説 fk は集合 I1の要素として追加する．k は fkを求める度 に 1 ずつ増やしながら更新していくが，終了条件が満 たされる，または k が最大になった時点で更新を終了 する．ただし，終了条件は以下のように定義する． (終 了 条 件) Algorithm 2 の 3 行 目 か ら 7 行 目 の 繰 り 返 し に お い て k = l で あ る と す る ．4 行 目 の AdaBoost 内 で 行 わ れ た 繰 り 返 し 回 数 を Tl，得 ら れ た 統 合 仮 説 を fl(X) = sign(∑Tl t=1αtsign ( OPKl(Xt+, X)− OPKl(Xt−, X) )) とする．ただし，X+ t , Xt−は AdaBoost 内の t 回目の 繰り返しにおいて弱仮説を決定するために用いた正例 と負例である．このとき，すべての 1≤ t ≤ Tlに対し て，OPKl(Xt+, Xt−) = 0 であれば終了条件を満たす とする． 二重ブースティングでは終了条件が満たされれば，そ れ以上 k を更新してもそれまでに得られた仮説以上の 精度をもつ仮説は得られないと仮定している．また， k-gram 順序保存カーネルのパラメータ k の取り得る値 の最大値は定義 3 で示したように，入力された 2 つの 時系列データのデータ長のうち小さい方のデータ長で ある．そのため，終了条件を満たさなくても，k が最 大になった時点で更新を終了する． 次に，仮説 fi ∈ I1の学習データに対する正答率 ri を求める．そして，ri= 1.0 となる仮説 fiを要素とし てもつ集合を I2とする．このとき，|I2| ≤ 1 であれば， I1を弱仮説集合として AdaBoost を実行し，最終的な 統合仮説 F を求める．一方，|I2| ≥ 2 であった場合は， 以下のような多数決関数 F を求める． F (X) = sign  ∑ fi∈I2 fi(X)   もし，_|I2| ≥ 2 のときに AdaBoost を適用してしまう と，弱仮説 fi∈ I2が 1 個のみで構成される統合仮説が 生成される．しかし，I2に含まれる仮説はすべて同精 度であるため，いずれか 1 つを選ぶよりもすべての仮 説を考慮した方が識別率の高い統合仮説を生成できる と考えられる．したがって，二重ブースティングでは |I2| ≥ 2 の場合に限り，AdaBoost を適用せず，多数決 関数として F を出力する．このようなアルゴリズムを 用いることで，事前に k の設定をすることなく k-gram 順序保存カーネルを用いた時系列データ分類を行うこ とができる．

4

実験

k-gram 順序保存カーネルの性能を評価するため，計 算時間および分類における正答率を計算機を用いて比 較実験する．比較する手法は以下の 4 つとする． • Algorithm 1 + ユークリッド距離（ED） • Algorithm 1 + DTW（DTW） • Algorithm 1 + OPK（OPKk） • 二重ブースティング（DB-OPK） 計算機は CPU：Xeon EE5-2609 2.4GHz，メモリ： 256GB，OS：Debian wheezy を使用する．

4.1

計算時間の比較実験

4.1.1 実験設定 ここでは，それぞれの類似性指標による計算時間を 比較する．ただし，計算時間とは最終的な統合仮説の 生成までにかかった時間のことである．使用するデー タは，0 以上 100 以下のランダムな実数からなる時系 列データで，データ長 L = 100, 1000, 10000 の 3 種類 とする．また，データ数は正例 50 個，負例 50 個を用 いる．本実験では，それぞれのデータ長に対して 10 回 学習を行った平均時間を測定する． 4.1.2 実験結果 表 1 に実験結果を示す．結果より，ユークリッド距 離（ED）が最も計算が速く，続いて k-gram 順序保存 カーネル，最も計算が遅いのが DTW であることが分 かる．これは，ユークリッド距離と k-gram 順序保存

表 1: ランダムデータセットでの計算時間 [秒]

L ED DTW OPK5 OPK10 DB-OPK

102 1.62 3.17 3.64 4.21 5.83 103 _{5.55 94.71 20.44 38.98 108.98} 104 _{43.84 8304.03 93.17 263.84 1805.54} 表 2: Rate = 0.5 における各類似指標の正答率 N ED DTW OPKk DB-OPK 0 0.996 1.000 0.984 (k = 6) 1.000 1 0.992 0.833 0.984 (k = 7) 0.999 2 0.978 0.748 0.983 (k = 6) 1.000 3 0.989 0.788 0.987 (k = 7) 1.000 カーネルの計算時間がデータ長 L に比例して増加する のに対し，DTW の計算時間はデータ長 L の 2 乗に比 例して増加するためである． また，k-gram 順序保存カーネルを用いた二重ブース ティング（DB-OPK）は，単純な分類手法を繰り返し実 行して最終的な統合仮説を求めるため，単独で k-gram 順序保存カーネルを用いた場合に比べて遅い結果となっ ている．表 1 より二重ブースティングの計算時間は， データ長 L に比例して増加していることが分かる．こ れは，二重ブースティングにおいて k を決定するため の繰り返しが，データ長に依存せずほぼ一定の回数と なるため，全体の計算時間がカーネルの計算にのみ依 存するためと考えられる． これより，k-gram 順序保存カーネルはデータ長の大 きいデータに対して，DTW よりも高速に計算するこ とが可能であるといえる．

4.2

正答率の比較実験

4.2.1 実験設定 ここでは，ノイズや異常値を含んでいるようなデー タに対する分類精度の比較を行う．ただし，k-gram 順 序保存カーネルの単純な分類手法では k = 2∼50 で実 験を行い，最も正答率の良い k の結果を採用する． 実験に使用するデータは，すべて人工的に生成した 長さ 1000 の時系列データとする．データ数は，学習 データは正例 50 個，負例 50 個とし，テストデータは 正例 100 個，負例 100 個とする． 正例，負例データは以下のような方法で生成する．ま ず，1 以上 10 以下の自然数をランダムに発生させ並べ た，長さ 1000 の系列 X = (x1, x2,· · · , x1000) を，正 例用と負例用に 2 つ生成する．次に，この系列 X に 対して，以下のようにノイズと異常値を混入させるこ とで，データ X′を生成する．xiを平均，標準偏差を 表 3: Rate = 0.8 における各類似指標の正答率 N ED DTW OPKk DB-OPK 0 0.994 1.000 0.986 (k = 6) 1.000 1 0.986 0.839 0.987 (k = 6) 1.000 2 0.978 0.626 0.986 (k = 6) 1.000 3 0.973 0.610 0.981 (k = 8) 1.000 表 4: Rate = 1.0 における各類似指標の正答率 N ED DTW OPKk DB-OPK 0 0.991 1.000 0.982 (k = 6) 1.000 1 0.988 0.882 0.988 (k = 6) 1.000 2 0.961 0.519 0.983 (k = 7) 0.999 3 0.963 0.523 0.983 (k = 7) 0.998 1.0 とする正規分布にしたがって生成された乱数 niと する．これにより，系列 X を素にしたノイズ入り系列 X′ = (n1, n2,· · · , n1000) を生成する．さらに，X′ に 対して Rate の確率で，n1,· · · , n1000の値のうち N 個 の値を 10000 倍することで，異常値を入れる．この操 作を正例，負例に対してそれぞれ 150 回繰り返すこと でデータを作成する． 本実験では，混入確率 Rate = 0.5, 0.8, 1.0 と混入個 数 N = 0, 1, 2, 3 を組み合わせた 12 通りのパラメータ によるデータセットを用いて実験を行う．また，分類の 結果は，上述のようにして作成した 10 個のデータセッ トでの結果の平均とする． 4.2.2 実験結果 表 2，表 3，表 4 に混入数と各類似性指標による正 答率の関係を示す．k-gram 順序保存カーネルの単純な 分類手法には，正答率のほかに最も正答率が高かった k の値も記載している． いずれの混入確率でも，既存の類似性指標を用いた場 合は，混入数 N が大きくなるにつれて正答率が下がっ ていることが分かる．特に，DTW は大幅に正答率が 低下していることが分かる．これは，DTW が 2 つの 時系列データの各点を必ず対応させるため，異常値を 含んだ時系列データに弱いという性質が原因と考えら れる． 一方，どのパラメータの場合を見ても k-gram 順序 保存カーネルは，高い正答率であり，異常値による影 響を受けにくいことが分かる．この結果の原因として 以下のような考察ができる．データ長 L の時系列デー タ X を考えたとき，X に含まれる長さ k の部分列は L− k + 1 個である．もし，X に N 個の異常値が入っ たとしても，異常値によって順序関係が変わる可能性 のある部分列は高々kN 個までである．つまり，k と N

に対して L が十分に大きければ，k-gram 順序保存カー ネルは異常値が混入した時系列データに対しても正し く類似度を測ることができると考えられる． また，k-gram 順序保存カーネルに関して，二重ブー スティングがすべてのパラメータにおいて単純な分類 手法の正答率を上回っている．さらに，単純な分類手 法では正答率の最も良い k がパラメータによって変わ るため，事前に最適な k を与えることが難しいことも 分かる．したがって，k の設定をする必要がない二重 ブースティングは，正答率の観点では単純な分類手法 よりも性能の良い分類手法であるといえる．

5

むすび

本論文では，時系列データの形状による類似性指標 として，k-gram 順序保存カーネルを提案した．さらに， 事前にパラメータ k を設定せずにクラス分類を行う手 法として，二重ブースティングを提案した．また，実 験的に k-gram 順序保存カーネルが既存の類似性指標 の DTW より高速に計算可能で，異常値が混入した時 系列データに対しても高精度に分類可能であることを 示した． 今後の課題としては，二重ブースティングの高速化 が挙げられる．二重ブースティングでは，k を更新し ながら単純な分類手法を繰り返し行うが，単純な分類 手法はそれぞれ独立に実行可能である．そのため，並 列処理などの手法を用いることでアルゴリズムの高速 化が見込めると考えられる．

参考文献

[1] Donald J. Berndt and James Clifford. Finding patterns in time series: A dynamic programming approach. In PAKDD.

[2] Sukhyeun Cho, Joong Chae Na, Kunsoo Park, and Jeong Seop Sim. A fast algorithm for order-preserving pattern matching. Information

Processing Letters, Vol. 115, No. 2, pp. 397–402,

2015.

[3] Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Order-preserving incomplete suffix trees and order-preserving indexes. In SPIRE, pp. 84–95, 2013.

[4] Christos Faloutsos, M. Ranganathan, and Yannis Manolopoulos. Fast subsequence matching in time-series databases. In SIGMOD, pp. 419–429, 1994.

[5] Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal

of Computer and System Sciences, Vol. 55,

No. 1, pp. 119–139, 1997.

[6] M. Kearns. Thoughts on hypothesis boosting, 1988.

[7] Jinil Kim, Amihood Amir, Joong Chae Na, Kunsoo Park, and Jeong Seop Sim. On representations of ternary order relations in numeric strings. In ICABD, pp. 46–52, 2014. [8] Jinil Kim, Peter Eades, Rudolf Fleischer,

Seok-Hee Hong, Costas S. Iliopoulos, Kunsoo Park, Simon J. Puglisi, and Takeshi Tokuyama. Order-preserving matching. Theoretical Computer Science, Vol. 525, No. 13, pp. 68–79, 2014.

[9] Marcin Kubica, Tomasz Kulczynski, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. A linear time algorithm for consecutive permutation pattern matching. Information Processing Letters, Vol. 113, No. 12, pp. 430–433,

2013.

[10] Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins. Text classification using string kernels.

Journal of Machine Learning Research, Vol. 2,

pp. 419–444, 2002. [11] 中村哲也, 瀧敬士, 野宮浩揮, 上原邦昭. Amss : 時 系列データの効率的な類似度測定手法 (データマ イニング). 電子情報通信学会論文誌. D, 情報・シ ステム, Vol. 91, No. 11, pp. 2579–2588, 2008. [12] 佐藤雄介, 成澤和志, 篠原歩. 順序保存符号化 n-gram の高速な出現頻度計算手法. 情報処理学 会研究報告 2015-AL-151(1), pp. 1–8, 2015. [13] 佐藤雄介, 成澤和志, 篠原歩. 接尾辞係数表現に よる順序保存 n グラム出現頻度の効率的な計算. 2014 年度冬の LA シンポジウム, 2015.