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

人工知能学会研究会資料
SIG-FPAI-B502-04
順序保存カーネルを用いた時系列データ分類
Time series data classification using order preserving kernel
柏葉祐輝 1 成澤和志 1 篠原歩 1
Yuki Kashiwaba
Kazuyuki Narisawa1
Ayumi Shinohara1
1
東北大学大学院情報科学研究科
Graduate School of Information Sciences, Tohoku University
1
1
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 classiﬁcation method using the kernel without
adjusting the parameter k. Furthermore, we conﬁrm 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 順序保存カーネルを用いた
提案手法と既存の類似性指標を用いた場合で，分類問
題における正答率と計算時間を比較する．
−1−
2
準備
時系列データは測定した時間 i をインデックスとした
実数 xi ∈ R を並べて表すことができる．データ長 N
の時系列データ X は以下のように表すことができる．
定義 2 (順序保存符号化出現頻度) 長さ N の時系列
データ X = (x1 , x2 , · · · , xN ) と長さ k ≤ N の符号
化系列 C = (c1 , c2 , · · · ck ) が与えられたとき，
ϕC (X) =
N∑
−k+1
(
(
) )
match Code X(i,k) , C
i=1
X = (x1 , x2 , · · · , xN ) ただし xi ∈ R
また，時系列データ X の i 番目から始まる長さ m 部
分系列 (xi , xi+1 , · · · , xi+m−1 ) (1 ≤ i ≤ N − m + 1) を
X(i,m) と表記する．
時系列データに対して，順序同型 [9] と呼ばれる関
係を定義する．
を X における C の順序保存符号化出現頻度と言う．こ
こで，
{
1 (a = b)
match (a, b) =
0 (otherwise)
である．
定義 1 (順序同型) 長さ N の 2 つの時系列データ X =
(x1 , x2 , · · · , xN ) と Y = (y1 , y2 , · · · , yN ) が与えられた
とき，任意の 1 ≤ i, j ≤ N に対して xi ≤ xj ⇔ yi ≤ yj
が成り立つとき，X と Y は順序同型であるという．
ここで，長さ k のすべての符号化系列からなる集合を
C k = {C | C は長さ k の符号化系列 } とする．k-gram
順序保存カーネル（k-gram Order Preserving Kernel:
OPKk ）を以下のように定義する．
時系列データが順序同型であるかを判定するために
は，時系列データ上の各点の値を直接用いるのではな
く，各点の値を相対的な大小関係で表す必要がある．時
系列データをこのような大小関係に変換することを順
序保存符号化，もしくは単に符号化と呼ぶ．時系列デー
タを符号化したものを符号化系列と言い，系列 X の符
号化系列を Code (X) で表す．時系列データの部分系列
を符号化したものを符号化部分系列と言う．符号化し
た系列が一致していれば順序同型である．
符号化の表現には様々な方法が提案されている [2, 3]．
中でも最も直感的な表現方法は，自然表現 [8] である．
自然表現では，時系列データの各点の値を系列内順位で
表現する．例えば，時系列データ X = (10, 15, 30, 21, 9)
と Y = (13, 19, 31, 25, 7) を自然表現で符号化した系列
Codenr (X)，Codenr (Y ) は以下のように表現される．
定義 3 (k-gram 順序保存カーネル) データ長 N ,M
の時系列データ X = (x1 , x2 , · · · , xN )，Y
=
(y1 , y2 , · · · , yM ) と任意の整数 k ≤ min(N, M ) が与え
られたとき，X と Y の k-gram 順序保存カーネルを以
下のように定義する．
∑
OPK k (X, Y ) =
⟨ϕC (X), ϕC (Y )⟩
Codenr (X) = (2, 3, 5, 4, 1)
Codenr (Y ) = (2, 3, 5, 4, 1)
このとき，時系列データ X と Y は符号化した系列が
一致しているため順序同型である．
3
3.1
C∈C k
例 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)
であるため，それぞれの順序保存符号化出現頻度は，
提案方法
k-gram 順序保存カーネル
ここでは，順序同型を用いた類似性指標として，
k-gram 順序保存カーネルを提案する．この指標は，テ
キスト間の類似度を表す k-gram カーネル [10] を時系
列データに対応させたものと言える．
まず，時系列データに含まれる符号化部分系列の出
現頻度を表す順序保存符号化出現頻度を定義する．
−2−
ϕ(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 順序保存カー
ネルは，
OPK 3 (X, Y )
=
2×3+1×0+0×1+
1×2+1×0+0×1
=
Algorithm 1: AdaBoost(tmax , ϵ)
1 弱仮説集合を H とする;
2 D1 を初期の事例生成確率分布とし，t ← 1 とする;
3 Repeat
4
分布 Dt で優位度が最も高い弱仮説 h ∈ H を ht とする;
5
ht の重みを αt とする;
(∑t
)
f (X) = sign
6
i=1 αi hi (X) ;
7
Dt+1 を ht と Dt をもとに更新 ;
8
t←t+1 ;
9 Until (t = tmax ) or (学習データでの統合仮説の正答率 ≥ ϵ);
10 得られた統合仮説 f (X) を出力;
8
となる．
長さ k の符号化系列の集合 C k の大きさは，符号化
の方法によっても変わるが，ほとんどの場合 k に対し
て指数的に増加していく．例えば，同じ値を許す系列
に対する自然表現では，C k の大きさは以下の式で表さ
れる Ordered Bell Number [7] となる．
k ( )
∑
k
a(k) =
a(k − i)
i
i=1
仮説を一つ選び出し，重みを付けて統合仮説に線形結
合していく．この動作を 9 行目に示す終了条件を満た
すまで繰り返す．このとき，T 回繰り返しが行われた
とすると，以下のような統合仮説 f (X) を出力する．
f (X) = sign
( T
∑
)
αt ht (X)
t=1
そこで，k-gram 順序保存カーネルを効率的に計算す
るため，系列 X に含まれている符号化系列に対しての
み出現頻度を数えることでカーネル計算をする．長さ
N の系列 X に含まれているすべての符号化部分系列の
出現頻度は，佐藤らの提案した接尾辞計数表現による
符号化と計算アルゴリズムを用いることで O(kN ) 時
間で計算することができる [12, 13]．このアルゴリズム
を用いれば，系列 X, Y の k-gram 順序保存カーネルは
O(k(|X| + |Y |)) 時間で計算することができる．
また，本論文では k-gram 順序保存カーネルを以下
のように正規化して利用する．
OPK k (X, Y )
NormalOPK k (X, Y ) = √
OPK k (X, X)OPK k (Y, Y )
以降，正規化した k-gram 順序保存カーネルを単に
k-gram 順序保存カーネルと呼ぶ．
3.2
3.2.1
k-gram 順序保存カーネルを用いたクラ
ス分類手法
ただし，
{
sign(n) =
+1 (n ≥ 0)
，
−1 (otherwise)
αt は統合仮説における弱仮説 ht の重みである．
AdaBoost は弱仮説 h1 , h2 , · · · , ht−1 が間違いやすい事
例に対して正答率の高い弱仮説 ht を統合仮説に追加す
ることで, その弱点を補おうという考えに基づいている．
本論文では，AdaBoost の弱仮説として k-gram 順序
保存カーネルを基にした関数を提案する．学習データ
として S = {(X1 , y1 ) , · · · , (Xm , ym )} が与えられたと
き，弱仮説集合 Hkop を以下のように定義する．
Hkop = {h(X, k) = sign(OPK k (Xi , X) − OPK k (Xj , X))
| 1 ≤ i, j ≤ m s.t. yi = +1, yj = −1}
ただし，パラメータ k は事前に与えられているとす
る．弱仮説集合を Hkop として AdaBoost を行うこと
で，k-gram 順序保存カーネルを用いた時系列データ分
類ができるようになる．
単純なクラス分類手法
クラス分類には，様々な手法が提案されているが，本
論文ではブースティング [6] と呼ばれる学習アルゴリ
ズムを用いる．ブースティングは，弱仮説と呼ばれる
50%以上の正答率をもつ識別関数 h を組み合わせて，正
答率の高い統合仮説 f を生成する学習手法である．ブー
スティングアルゴリズムはいくつか提案されているが，
本研究では AdaBoost [5] と呼ばれるアルゴリズムを使
用する．
Algorithm 1 に AdaBoost のアルゴリズムを示す．
AdaBoost は，ステップ t において弱仮説集合から弱
3.2.2
二重ブースティング
3.2.1 節で提案した k-gram 順序保存カーネルを用い
た分類手法では，あらかじめパラメータ k を設定する
必要があった．しかし，時系列データによって最適な
k の値は変わるため，事前に k を設定することは非常
に困難である．ここでは，事前にパラメータ k を設定
せずに分類を行う分類手法として，二重ブースティン
グ（Double Boosting: DB）を提案する．二重ブース
ティングのアルゴリズムを Algorithm 2 に示す．
−3−
以下のような多数決関数 F を求める．


∑
F (X) = sign
fi (X)
Algorithm 2: DB(tmax1 , ϵ1 , tmax2 , ϵ2 )
1 I1 = {} とする;
2 k ← 2 とする;
3 Repeat
4
5
6
7
8
9
10
11
12
13
14
15
16
Hkop を弱仮説集合として AdaBoost(tmax1 , ϵ1 ) を実行し，
得られた統合仮説を
fk とする;
∪
I1 ← I1 {fk } ;
k ←k+1 ;
Until (終了条件を満たす)or (k が最大)
fi ∈ I1 の学習データに対する正答率 ri を求める;
I2 = {fi | ri = 1.0} とする;
if |I2 | ≤ 1
I1 を弱仮説集合として AdaBoost(tmax2 , ϵ2 );
得られた統合仮説を F とする;
else
fi ∈ I2 の多数決関数を F とする;
endif
関数 F を出力
学習データとして，S = {(X1 , y1 ) , · · · , (Xm , ym )}
が与えられているとする．二重ブースティングでは，ま
ず k = 2 から順に，Hkop を弱仮説集合として AdaBoost
を行い，統合仮説 fk を生成する．得られた統合仮説 fk
は集合 I1 の要素として追加する．k は fk を求める度
に 1 ずつ増やしながら更新していくが，終了条件が満
たされる，または k が最大になった時点で更新を終了
する．ただし，終了条件は以下のように定義する．
(終了条件) Algorithm 2 の 3 行目から 7 行
目の繰り返しにおいて k
=
l であるとす
る．4 行目の AdaBoost 内で行われた繰り返
し回(数を Tl ，得られた統合仮説を fl (X)
=
(
))
∑Tl
+
−
sign
t=1 αt sign OPK l (Xt , X) − OPK l (Xt , X)
とする．ただし，Xt+ , Xt− は AdaBoost 内の t 回目の
繰り返しにおいて弱仮説を決定するために用いた正例
と負例である．このとき，すべての 1 ≤ t ≤ Tl に対し
て，OPK l (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 であった場合は，
fi ∈I2
もし，|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 順序保存
−4−
表 1: ランダムデータセットでの計算時間 [秒]
L
ED
DTW OPK5 OPK10 DB-OPK
102
103
104
1.62
3.17
5.55
94.71
43.84 8304.03
3.64
20.44
93.17
4.21
38.98
263.84
表 3: Rate = 0.8 における各類似指標の正答率
N
ED DTW
OPKk
DB-OPK
0
1
2
3
5.83
108.98
1805.54
表 2: Rate = 0.5 における各類似指標の正答率
N
ED DTW
OPKk
DB-OPK
0
1
2
3
0.996 1.000 0.984 (k = 6)
0.992 0.833 0.984 (k = 7)
0.978 0.748 0.983 (k = 6)
0.989 0.788 0.987 (k = 7)
4.2.1
1.000
1.000
1.000
1.000
表 4: Rate = 1.0 における各類似指標の正答率
N
ED DTW
OPKk
DB-OPK
1.000
0.999
1.000
1.000
0
1
2
3
カーネルの計算時間がデータ長 L に比例して増加する
のに対し，DTW の計算時間はデータ長 L の 2 乗に比
例して増加するためである．
また，k-gram 順序保存カーネルを用いた二重ブース
ティング（DB-OPK）は，単純な分類手法を繰り返し実
行して最終的な統合仮説を求めるため，単独で k-gram
順序保存カーネルを用いた場合に比べて遅い結果となっ
ている．表 1 より二重ブースティングの計算時間は，
データ長 L に比例して増加していることが分かる．こ
れは，二重ブースティングにおいて k を決定するため
の繰り返しが，データ長に依存せずほぼ一定の回数と
なるため，全体の計算時間がカーネルの計算にのみ依
存するためと考えられる．
これより，k-gram 順序保存カーネルはデータ長の大
きいデータに対して，DTW よりも高速に計算するこ
とが可能であるといえる．
4.2
0.994 1.000 0.986 (k = 6)
0.986 0.839 0.987 (k = 6)
0.978 0.626 0.986 (k = 6)
0.973 0.610 0.981 (k = 8)
正答率の比較実験
実験設定
ここでは，ノイズや異常値を含んでいるようなデー
タに対する分類精度の比較を行う．ただし，k-gram 順
序保存カーネルの単純な分類手法では k = 2∼50 で実
験を行い，最も正答率の良い k の結果を採用する．
実験に使用するデータは，すべて人工的に生成した
長さ 1000 の時系列データとする．データ数は，学習
データは正例 50 個，負例 50 個とし，テストデータは
正例 100 個，負例 100 個とする．
正例，負例データは以下のような方法で生成する．ま
ず，1 以上 10 以下の自然数をランダムに発生させ並べ
た，長さ 1000 の系列 X = (x1 , x2 , · · · , x1000 ) を，正
例用と負例用に 2 つ生成する．次に，この系列 X に
対して，以下のようにノイズと異常値を混入させるこ
とで，データ X ′ を生成する．xi を平均，標準偏差を
0.991 1.000 0.982 (k = 6)
0.988 0.882 0.988 (k = 6)
0.961 0.519 0.983 (k = 7)
0.963 0.523 0.983 (k = 7)
1.000
1.000
0.999
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
−5−
に対して L が十分に大きければ，k-gram 順序保存カー
ネルは異常値が混入した時系列データに対しても正し
く類似度を測ることができると考えられる．
また，k-gram 順序保存カーネルに関して，二重ブー
スティングがすべてのパラメータにおいて単純な分類
手法の正答率を上回っている．さらに，単純な分類手
法では正答率の最も良い k がパラメータによって変わ
るため，事前に最適な k を与えることが難しいことも
分かる．したがって，k の設定をする必要がない二重
ブースティングは，正答率の観点では単純な分類手法
よりも性能の良い分類手法であるといえる．
5
むすび
本論文では，時系列データの形状による類似性指標
として，k-gram 順序保存カーネルを提案した．さらに，
事前にパラメータ k を設定せずにクラス分類を行う手
法として，二重ブースティングを提案した．また，実
験的に k-gram 順序保存カーネルが既存の類似性指標
の DTW より高速に計算可能で，異常値が混入した時
系列データに対しても高精度に分類可能であることを
示した．
今後の課題としては，二重ブースティングの高速化
が挙げられる．二重ブースティングでは，k を更新し
ながら単純な分類手法を繰り返し行うが，単純な分類
手法はそれぞれ独立に実行可能である．そのため，並
列処理などの手法を用いることでアルゴリズムの高速
化が見込めると考えられる．
参考文献
[1] Donald J. Berndt and James Cliﬀord. 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 suﬃx 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 classiﬁcation 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.
−6−

Download Report