時系列の類似性検索における上界関数による効率化

Kobe University Repository : Kernel
Title
時系列の類似性検索における上界関数による効率
化(Efficient Similarity Retrieval with Upper Bound for
Time Series)
Author(s)
瀧, 敬士 / 中村, 哲也 / 上原, 邦昭
Citation
電子情報通信学会論文誌. D, 情報・システム,J91D(12):2926-2938
Issue date
2008-12-01
Resource Type
Journal Article / 学術雑誌論文
Resource Version
publisher
DOI
URL
http://www.lib.kobe-u.ac.jp/handle_kernel/90000828
Create Date: 2017-04-01
時系列の類似性検索 における上界 関数 による効率化
瀧
敬士fa)
中村
哲也I
上原
邦 昭Ib)
E侃C
i
e
n
tSi
mi
l
a
r
i
t
yRe
t
r
i
e
v
a
lwi
t
hUppe
rBo
undf
o
rTi
meSe
r
i
e
s
Ke
i
s
hiTAKI
l
a) T
e
t
s
uyaNAKAMURAla
ndKuni
a
kiUEHARAlb)
,
,
あらま し 近年,時系列の分類 に関する研究が盛んに行われている.その一つ として多次元時系列の類似性検
索 に有効な手法 An
gul
arMe
t
r
i
c
sf
o
rSha
peSi
mi
l
ar
i
t
y(
AMSS)がある.AMSSは時系列 をベ ク トル系列 とし
て扱い,個々のベ ク トルの角度 を比較 して類似度 を計測 し,動的計画法 を用いてベク トル系列間全体の類似度 を
計算する手法である. また,角度の比較 にはコサ イン類似度 を用いているため,ノイズのような部分は類似度に
影響 を与 えないようにで きるという特徴がある. しか しなが ら,計算 コス トが高いとい う問題点を抱えている.
本論文では,AMSSを用いた検索のフィルタリングとして上界関数 を導入 して,計算 コス トを削減する手法を提
案する.ここで上界関数 とは,本来の関数 より必ず大 きな値 となる近似値 を求める関数である.具体的には,ベ
ク トル系列 を合成ベ ク トル系列 に変換 して,近似値 を求めている.上界関数 を用いるため,類似 しない時系列を
f
a
l
s
edi
s
mi
s
s
l な しに検索対象か ら取 り除 くことがで きるとい う特徴がある.最終的に,上界関数の正当性 を示
a
すために,数学的帰納法による証明について述べ る.
キーワー ド データマイニ ング,時系列,類似度,次元圧縮
1. ま え が き
題 が あ る.例 えば, 同 じ動 きを行 う軌跡 で も,動 く方
時系列 デー タマ イニ ングの分 野 で は,分 類 や クラス
には,類似 度 を正確 に測定 で きない.
向が異 な ってい た り,観 測 す る初期位 置が異 なる場合
タ リング, イ ンデ クシ ングの ため に,時系列 間の類似
度 を計 測 す る手 法が提 案 されて い る t
3
]
,
[
8
]
.類似 度 計
arMe
t
r
i
c
sf
♭r
上 記 の問題 を解 決 す るため ,Angul
ShapeSi
mi
l
ar
i
t
y(
AMSS) とい う手法 が提 案 され て
測手法 と して,Dyna
mi
cTi
meWar
pi
ng (
DTW )が
1
]
.AMSSは時系列 をベ ク トル系列 (
注"と して扱
いる [
知 られてい る [
2
上 DTW は時系列 の長 さを動 的 に整 合
い,ベ ク トル 間の角度 のみ を比較 して類似 度 を計算す
し,時系列 間の類似度 を求めてい る. しか し,時系列 間
る手法 で あ る. また,デ ー タ整合 の問題 を解決す るた
を完全 にマ ッチ ングす る性 質 か ら, ノイズ に弱 い とい
め に,動 的計 画法 を用 い て各 ベ ク トル間の類似度 を足
LCSS)に
う問題 があ る.この ため,最長共通部分列 (
し合 わせ て,ベ ク トル系列 間の類似 度 を計算 してい る.
3
]
.
基づ い て類似 度 を計 測 す る手 法 が提 案 され て い る [
更 に,角 度 の比 較 に は コサ イ ン類 似 度 を用 い てお り,
しか し,LCSSの類似度 は,時系 列全体 に対 す る類似
ベ ク トル間 の角度 が 7
T
/
2以 上 の場 合 には,類似 度 を
部 分 時系列 の割 合で表 され るの みで, どの くらい部分
O と してい る. このため, ノイズ と通常 の デ ー タ間の
時系列が似 てい るか とい う情報 は もってい ない. また,
よ うにベ ク トル間の角度 が大 き く異 なった場合,類似
部分 時系 列 の類似性 を判 断す るための しきい値 は一意
度 は 0とな る. したが って,部 分時系列 の方向が極度
に決定 で きない.更 に,DTW と LCSSは,時系列 の
に異 な る際 には,仮 に部分 時系 列 が動 的計画法 によ り
座標値 を用 いて類似性 を計 測 してい るため ,類似 す る
マ ッチ した場 合 で も,類似度 の総和 は変化せず, ノイ
時系列 間で も,適切 に類似 度 を求め られない とい う間
ズの影響 を受 け ない こ とにな る.
一般 に,計 算 コス トは時 系 列 に内在 す る問題 で あ
I神戸大学大学 院工学研 究札
る.す なわ ち,大規模 時系 列 の場 合,すべ てのデー タ
神戸市
Graduate School of Engi
neer
i
ng, Robe Uni
ver
si
t
y, 1-1
Rokkodai
cho,Nadaku,Kobeshi
,657-8501Japan
a)Emai
l
二t
aki
◎ai
.
cs.
s
ci
t
ec.
kobeu.
ac,
j
p
b)Emai
l
二uehar
a@kobeu･
ac.
j
p
2
9
26
電子情報通信学会論文誌
(
往 1):時系列 が多変量時系列 の場合 も時系列の ことをベ ク トル系列 と
呼ぶが,本論文では時系列の隣 り合 う 2点の座標値 を結ぶ ことにより作
成 され るベ ク トルによって構成 され る系列 の ことをベ ク トル系列 と呼ぶ.
D Vol
.｣
91
-D No.
1
2 pp.29
26
-2
938 ㊤ (
社)電子情報通信学会 2
00
8
論文/時系列の類似性検索における上界関数による効率化
点の組合せ に対 して類似度 を計算す るため,膨大 な計
算 コス トがかかるとい う問題がある. この ような問題
を解決するために,多 くの研究者が高速化手法 を提案
してい る [
4:
l
,[
1
4上 例 えば,時系列 をシ ンボル列 で表
現す る Symbol
i
cAggr
e
ga
t
eappr
oxi
mat
i
on (
SAX)
では,次元圧縮 を導入 して [
9
]
,長 さ n の時系列 を任
意長 W の シンボル列 に圧縮 して,計算 コス トの削減
W ≪ n). また,時系
を図る手法が提案 されている (
列のデー タ数 は計算 コス トに大 きく関係す るので,検
索候補 を削減す るため,氏t
r
e
eなどのイ ンデ ックスを
使用する手法 も提案 されている [
8
]
.
しか し, これ らの手法では, もとのデー タの詳細が
座標系 の影響 をな くす ため,Q と C をベ ク トル系列
′
＼
Q と e に変換す る.
6-(
q
2-ql
)
,
(
q
3-q
2
)
,
･
･
･
,
(
qLQ-q
LQ-1
)
-前,
重,
…,
q
T
k
(
N -LQ- 1)
(
3)
C
2-C1
)
,
(
C
3-C
2
)
,
…,
(
c
Lc-C
Lc-1
)
6 -(
-音,
尋,
.
.
.
,
c
T
R
i
(
M -Lc- 1)
(
4)
また,宙 と 可 の間の角 を 0 とす る と,右 ,可 閣の
類似度 は以下の ように計算 される.
Si
n(
i
,
i)-c
os
O
扉.
ぢ
失われた り,f
a
l
s
edi
s
mi
s
s
alが生 じて しまう可能性が
(
5)
l
雷I
l
ぢl
ある.f
a
l
s
edi
s
mi
s
s
alとは,本来,検索 されるべ き解
まで検索候補 か ら外 して しまうこ とである.例 えば,
もし 0>7
T
/
2であれば,Si
n(
i
,
i)は無条件 で 0とな
SAX は時系列 をシンボル列 で表すため, もとのデー
2な らば,式 (
5)によ り類似度が計
る.逆 に,β≦灯/
タの詳細が失われる. また,検索 の高速化 のため に検
索候補数 を削る場合,関数 によっては,本来,検索結
果 として返 されるべ き解 まで捨 て られて しまう可能性
がある.このため,DTW には下界関数,LCSSには
叫 ,[
11
]
,[
1
3]
.これ らの関
上界関数が提案 されている [
数は, もとの距離や類似度 よ り必ず小 さ く, または必
ず大 きくなる関数 を用いて, もとのデータの詳細 さを
失わず,f
a
l
s
edi
s
mi
s
s
alを生 じず に,類似性のない時
系列のみをフィルタリングする目的で導入 されている.
本論文では,AMSSに対 して上界関数 を導入 し,計
算コス トの軽減 について検討する.AMSSでの上界 関
数は,ベ ク トル系列 を合成ベ ク トル系列へ と次元削減
して,類似度 を求める ものである.合成ベ ク トル系列
の要素数は, もとのベ ク トル系列の要素数 よ りも明 ら
かに少な くなるため,計算 コス トを下げることがで き
.
■
ヽ
算 される. また,Q と
∂間の全体 の類似度 は以下の
再帰関数 を用いて計算 される.
S(
i
,
i)-M axl
S(
i
-1,
3
'
-1
)
+2Si
m(
i
,
i)
,
S(
i
-2,
ill
)
+Si
n(
i
ll,
i)
+2Si
m(
i
,
3
'
)
,
S(
i
-1,
i-2)
+Si
n(
i
,
i-i
)
+2Si
m(
i
,
i)
]
(
6)
S(
i
,
1)-S(
1,
i)--∞,S(
1,
1)-Si
n(
1,1)
ここで,S(
i
,
i
)は Qの i番 目と e の j番 目までの時
′
ヽ
系列で とり得 る最大の類似度 となる.最終的 に,Q と
e の類似度 は以下の式で得 られる.
AMSS(
a a)-S(
N,
M)
(
7
)
,
3. 上 界 関 数
る.また,合成ベ ク トル系列 による類似度 関数 は上界
上 界 関 数 UBAMS
S(
Q,C)と は ,本 来 の 類 似 度
関数 となるために,必ず もとのベ ク トル系列の情報 を
保有 している.最後 に,本手法の正当性 を評価す る実
AM SS(
Q,
C)を, よ り少 ない計 算 コス トで近似 的
に求める関数である. このため,二つの時系列 Q,C
験 を行い,類似性計測 における効果 を示す.
の類似性 を求める場合,以下の式 を満たす必要がある.
2. AMSS
まず AMSSによる時系列 間の類似度計算 の概要 を
示す. ここで Q と C を,あるサ ンプ リング レー トで
得 られた,時間 と実数値で構成 される,それぞれ長 さ
LQ と Lc の時系列 と仮定す る.
Q-ql,q2,
-,
q
LQ(
∈Rk)
,
C
2,‥.,
C
Lc(
∈Rk)
C - cl
UBAMSS(
Q,
C)≧AM SS (
Q,
C)
(
8)
ここで,Q との類似度が ∈以上の時系列 をデー タベー
スか ら検索す る場合 を考 える.デー タベ ース中の時系
列 C に対 して,本来の類似度 を計算する前 に,上界関
S<Eであれば,式 (
8)
数 を計算 す る. もし UBAMS
か ら以下の式が成 り立つ.
AM SS(
Q,
C)≦UBAMSS(
Q C)<e
,
(
9)
2927
論文/時系列の類似性検索 における上界関数 による効率化
r
e
gl
O
nS
e
c
t
o
rOfq
c
o
"
.
g
r
e
gi
o
nS
e
c
t
o
rOfqc
o
mg
Sc
o
,
a(
a,h)
Sc
o
m(
9-1
,
h-1
)
o
>
Ccmh
4
r
e
gi
o
nS
e
c
t
o
rOfcc
o
mA
+(
2c
nd+c
n_
S
ub
d)･
Si
mco
m(,
h)
9
g
7:mh
r
e
g1
0
nS
e
c
t
o
rOfc
c
o
mA
= m aX
+(
2c
nh+c
n_
S
ub
h)･
Si
mcom( ,
h)
@)ove
r
l
a
p
(
a
)s
e
par
at
e
a
Sc
o
m(
9,
hll
)
図 4 Regi
ons
ec
t
or間の類似度 を決定す る各状態
Fi
g.
4 Eac
hs
t
at
et
odeci
des
i
mi
l
ar
i
t
ybe
t
weenr
egl
On
s
ec
t
or
.
t
i
on),r
e
gi
ons
e
c
t
or間が重なっている場合 (
o
ve
r
l
ap)
の二つの状態がある.重 なっている場合 とは,合成ベ
ク トルがほ とん ど類似 していることを表すので,類似
e
gi
ons
e
c
t
or
度 を 1とする.一方,離れている場合 は r
を用いて類似度 を計算すればよい.そ こで,合成ベ ク
ノ
ヽ
トル系列 Qc
o
mの
蒜
E
39番 目の合成ベ ク トル 百
Sc
o
m(
911
,
h)
.
;と合
+(
2c
nv+c
n_
s
ub
v) L
Si
mc
o
m(
g,
h)
(
1
3)
c
nd- M i
nl
百
蒜 .
;･
num,
c
T
n
c
nh- Mi
n[
q
T
;
石
蒜
.
nun,
･
n
um]
.
言I
num -1
]
c
nv - Mi
nl
窮吉
宗.
;.
nun -1,
c
T
n
nl
c
nd,
(
q
T
;
c
ns
ub
d-M i
.
num]
･
num 一房蒜 .
完･
num)
】
成ベ ク トル系列 Cc
o
m の h番 目の合成ベ ク トル c
T
a
n[
c
nh, (拓 訂;
.
n um
c
ns
ub
h- Mi
のr
e
gi
ons
e
c
t
or間の角 を β
｡
｡
m とす る と (
図 4(
a)参
(
蛋;
完.
;.
nun -房吉
蒜.
言.
nun)
】
c
n_
s
ub
v-Mi
nl
c
nv,
T
照),q
E
とc
T
a
のr
e
gi
ons
e
c
t
or間の類似度 は
以下の式で計算 される.
一 房 吉宗 .
完･
num)
]
ノ
ヽ
a)- AM SSc
o
m(Qcom ,ecom)
UBAMSS(
Q,
- sc.
m(
N'
,
M'
)
s
i
- co
-
(9,h,-
c
l
?
.
SOc
o
-
i
S::ral
r
a
a
,
ti
on
i
(
1
0)
∂
｡
｡
m とは以下 の式 の よ うに,各座標 平 面 の r
e
gi
on
s
e
c
t
or間の角度の最小値で表 される.
Ocom
- mi(
Ocom l
x],Ocom
n
ly ],
･
･ ･)
(l
l)
ここで,x座標平面での r
e
ions
g
e
c
t
or間の角度 O
c
o
ml
x]
は以下の式で求め られる.
x
]
i
fqcom･
Lag
l
x
]
>c
com ･
Ua
n
9
l
x
]
ccom･
L ngl
x
]- qco
m･
U n
9l
x
]
q
c
o
m.
Longl
xト
β
｡
｡
m回 -
Cc
o
m･
Uangl
(
1
4)
ここで Sc
o
m(
9,
h)は Qc
o
m の 9番 目と e
c
om の h番
目までの合成 ベ ク トル系列 間の最大 の類似度 になる.
′
ヽ
･
num,c
T
a ･
num はそれぞれ Qc
o
mの
g 番 目と ec
o
m の h番 目の合成ベ ク トル を構 成す る
なお,す
蒜
I
i
コ
もとのベ ク トル数 を表 している.いか なる二つの Qと
∂において も,以下の不等式が成 り立つ.
UBAMSS(
a,
a)≧ AM SS(
a 6)
,
(
1
5)
したが って,以上 の手法 を上界関数 として,似 ていな
い時系列 を検索対象か ら外す ことによ り,効率的 な検
n
a
a
el
s
ei
fc
c
o
m･
Langl
x]>q
c
o
m･
Ua
ngl
x]
(
1
2)
また,他の平面 について も同様 に して求めることがで
きる.
索 を実現 で きる.なお,式 (
1
5)については付録 で証
明す る.
4. データ圧縮 のためのベ ク トル合成
時系列 中の部分ベ ク トル列 を一つのベ ク トルに合成
する ｢
ベ ク トル合成｣手法 について説明す る.時系列
そ して, もとの部分ベ ク トルの類似度の定義 と同様
には,少 な くとも滑 らかなに変化す るデー タ,振動 の
に,O
c
o
m が 打/2以上離れていれば類似度 を Oとする.
多 い デー タの 2種類 が存在 す る.本論 文 で は, これ
また,各 r
e
gi
ons
e
c
t
orのいず れかが図 4(
b)の よう
に重 なる場合 には類似度 を 1とす る.
ら二つの観点か ら合成手法 を検討 している.それぞれ
"
Ⅷr
i
at
i
onalangl
e
s
"と "
var
i
at
i
onalar
ea" と呼ぶ.
e
gi
ons
e
c
t
or間の類似度 を式 (
1
0)によ り
すべ ての r
Ⅷr
i
at
i
onalangl
e
sとは,上界関数の緊密性 を高める
計算 した後,r
e
gi
ons
e
c
t
or系列 間,つ ま り,合成ベ ク
ノ
ヽ
トル系列 Qc
o
mとec
o
m 間の類似度 を求め るための再
ために,合成ベ ク トルによ り作 られる r
egi
ons
e
c
t
orの
帰関数 を式 (
1
3)の ように定める.
Ua
ngl
x]
-q
T
a ･
La
ngl
x]が
s
e
c
t
orで は中心角 拓 完 ･
中心角 に制約 をかける条件 である.図 2(
b)の r
e
gi
on
292
9
電子情報通信学会論文誌 2
008/1
2Vol
.J91
-D No.
1
2
しきい値 よ り小 さい値 を とる ように制 約 をか けてい
る.v
ar
i
at
i
onalangl
e
sは比 較 的単調 な軌跡 を してい
るデー タに有効 である.逆 に,ベ ク トルの角度が急激
ことがで きない とい う問題 があ る.
v
ar
i
at
i
onalar
e
aは,ベ ク トルを合成 した場合 に生 じ
る, もとのベ ク トル と合成 したベ ク トル間の領域 を情
報損 の量 と して考 え,その領域 の面積 を制約条件 とし
ar
i
a
t
i
onalar
e
aは,var
i
at
i
onal
て用 いる ものであ る.v
angl
e
sほ ど角度 の変化 には敏感 にならず,ノイズや激
しい変動 をす る軌道 に対 して も効果 的 にベ ク トル合成
で きる とい う利点がある.逆 に,Ⅷr
i
at
i
onalangl
e
sと
比べ る と,多 くのベ ク トル を合成 す るため緊密生が低
くなる とい う問題 が ある.
4.I Vari
at
i
onalang
les
ベ ク トル合成 はただ闇雲 に実行す れば よい わけで は
ズム
Tabl
e 1 Vect
or c
ombi
nati
ons al
gor
i
t
hm by var
i
ati
onalangl
es.
0 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1
に変化 してい る波形 で は,多 くのベ ク トルを合成 す る
表 1 Var
i
at
i
onalangl
eSに よるベ ク トル合成 の アルゴ リ
combi
ne_
angl
e(
Q)-Q｡
om
tart;
s
Q- (
q
7･qi,
･
L
･
,
喝
Qcom -.
(
)
;
Th r e
s
h
)
; //vectorsequence
//c
ombi
ne
dve
ct
orse
q
ue
nc
e
- Othre
Bh;
i- 2;
3- 1;
whi
l
e h ≦ 〟)
Ova
Cal
cvari
at
i
onal
angl
p
･(
弔,
q
I)
;
i
f(
∂v
a,[
1】≦ Thresh&& .,,&&Ova
r回 ≦ Thr esh)
,
-
i++;
conti
nue;
茄古記 - vect
or_
combi
ne (
Q,3
'
,i- 1);
add (
Qcom,
転石謡);
q■
■i
)
と
i++;
Cont
i
nue;
r
eturnQc｡m ;
end;
な く,AMSSか ら得 られ る類似 度 と上界 関数 か ら得
られ る類似度 の値が,で きるだけ近 くなる ように合成
こ
q3
e
gi
ons
e
c
t
orの 中心
す る こ とが望 ま しい .そ こで ,r
e
gi
on
角 に制約 をか けて,似 ているベ ク トルのみか ら r
吉
qc
o
m1AJ
s
e
c
t
orを構 成 す る ようにベ ク トル合成 す る.具体 的
Oth, esh
よ り小 さければベ ク トルを合成す る.なお, し
Al
+AZ
(
b)
には,合 成途 中のベ ク トル系 列 か ら作 られ る r
e
gi
on
s
e
c
t
orの中心角 を表 すパ ラメー タ Ova, が , しきい値
三
q3
;
(
C
1
図 5 Var
i
at
i
onalar
ea
Fi
g.5 Var
i
at
i
onalar
ea.
きい値 が小 さければ小 さいほ ど, もとのベ ク トル系列
と合成ベ ク トルが よ り近 い形状 となるため緊密性 は高
くなる. ここで,
Ovarl
n]-
図 5(
a)のベ ク トル系列 の うち,前 と 宙 に よ りベ ク
b)
),領域
トル合成が行 われた場合 (
図 5(
q
T
E
=･
Uangln]一 q
T=
･
Langl
n]
(
1
6)
A l が この
合成 に よって生 じる v
a
r
i
a
t
i
ona
la
r
e
aとな る. また,
C
)の ように 前 ,重 ,重 か らベ ク トル合成 され
図 5(
であ るので,Ovar がすべ ての次元 において OthreBh よ
ar
i
a
t
i
onala
r
e
aとなる.す なわ
た場合 ,A l+A 2 が v
りも小 さけれ ば,一 つ の合成 ベ ク トル と して合 成 さ
ち,ベ ク トル 前 と 重 を合成す るか どうか決 める と
れ る.
き,v
ar
i
at
i
onalar
e
aA l を評価 し,A l が しきい値 よ
Ⅷr
i
at
i
onalangl
e
sに よるベ ク トル合 成 アル ゴ リズ
′
＼
ムを表 1に示す.Q ｡｡m は合成ベ ク トル を記録す る配
列 で あ る. まず は じめ に, しきい値 Thr
e
s
h を決定
e
gi
ons
e
c
t
orの 中心角 を決定 す る
す る. しきい値 は r
りも小 さい場合,扉 と 重 が合成 される.同様 に,ベ
ク トル (扉 ,
重,
宿 )の合成 につ いて は
評価 される.
(
Al+A2) が
ベ ク トル合 成 の ア ル ゴ リズ ム を表 2 に示 す. ま
値 であ る. また,Cal
c
_
vari
at
i
onal
_
angl
e(
重,
香 )は,
ず は じめ に , しきい値 Thr
e
s
h を決 定 す る.具 体
宙 と雷 の間の角
を計算す る関数であ る.次 に合
ar
i
a
t
i
onala
r
e
a を求 め て
的 に は ,全 体 時 系 列 の v
成す る 有 の角度 と Ova, を比較 して,Ova, の値が しき
(表 2 の 3行 目),情 報 損 の 許 容 量 を決 定 す る値
e
s
h を超 えるまでそれ までのベ ク トル をま と
い値 Thr
W(
0.
0≦ W ≦ 1
.
0)を設 定 す る .W が 大 きけ れ ば,
めて合成す る.
情報損 は大 き くな り,ベ ク トル系列本 来の形 か ら離 れ
Ova,
4.2 Vari
at
i
onl
a ar
ea
るが,逆 にデー タ圧縮量 は大 き くなる. なお, しきい
var
i
at
i
onalar
e
aとは,ベ ク トル を合成 した場合 に
re
s
h値 は Th
生 じる情報損 の量 を領域 で表 した ものである.例 えば,
2930
At
ot
al*W
と して計 算 される.以上
の考 え方 に従 って,一つずつ合成す るベ ク トル を追加
論文/時系列の類似性検索 における上界関数 による効率化
表 2 Var
i
at
i
onalar
eaに よるベ ク トル合成 の例
Tabl
e2 Vect
orcombi
nat
i
onsal
gori
thm by
var
i
ati
onalar
ea.
表 3 上界 関数 を用 いた最近傍検索 アル ゴ リズ ム
Tabl
e3 1near
estnei
ghbors
ear
chal
gori
t
hm wi
th
upperbounds.
combi
ne_
area (
Q)= Qcor
n
s
tar
t;
a- (
q7
,
q
i,...,す万); //veciorsequence
Qc
om - (
)
;
//C
omb
i
ne
dve
ct
orse
q
uenc
e
At
ot
aJ- Cal
c_
t
ot
aLvari
at
i
onaLarea (
Q);
■
ot
al*W;
Tf
"esh - At
i- 2;
3- I;
whi
l
eh ≦ 〃)
search(
Q,C)
S
tart;
om Q;
makeQcom fr
maェsi
mi
l
ari
t
y- -∝)
;
geta Ccom f
r
om da
t
ab
ase;
i
fCcom doesnotexi
s
t
r
eturn resul
t;
c
al
c
ul
at
eUBA禦S
S(
Qco-,eco- )
;
i
fUBAM SS(
Qcom,ecom )< maxsi
mi
l
ari
t
y
Apa,t
i
aL- Cal
cvari
at
i
onal
area (
i
,
3
1
);
i
f(
Apart
i
al≦ Thresh)
getaL
i
meser
iesa f
r
om dat
ab
ase;
c
al
cur
at
eAM SS(
Q,C)
;
mi
l
ari
ty
i
fAM SS(
Q,C)>marBi
resul
t- a,maxsi
mi
l
arit
y - AM SS(
Q,
C)
;
goto4.
i++;
conti
nue;
百品 宗 - ve
ct
or_
combi
ne (
Q,J
A
,
i-1);
add (
ecom,百品 );
end;
J = i;
i++;
conti
nue;
∋com;
r
eturn(
end;
表 4 デー タセ ッ トの性 質
Tabl
e4 Char
act
erofdat
as
et
s.
Datas
et
bal
l
oon
buoys
ens
or
bur
s
t
net
wor
k
し,その都度 Ca
l
c
I
Var
i
at
i
o
naLare
a(
i
,
i
)に よ り,ベ
Lengt
h
char
act
or
4,
002 compl
i
cat
ed
55,
964 compl
i
cat
ed
9,
382
smooth
18,
000
smoot
h
,
j間の累積 Var
i
t
at
i
ona
l ar
eaを調べ , し
ク トル系列 i
re
s
hを超 えるまでベ ク トル合成す る.
きい値 Th
5. 実
度 AMSS(
Q,C)を計算す る. これ も最大類似 度 よ り
験
大 きい場合 には最大類似度 を更新す る.そ して,次 の
本章では,以下の点 に従 って,我 々の手法が有効 で
あることを示す.
合成 ベ ク トル列 を取 り出 して同様 の処理 を行 う. これ
をすべ ての時系列 に対 して行 って,最終 的 に最大類似
(1) ベ ク トル合成 の性 能
度 を もつ時系列 を検索結果 として返す.
(
2) AMSSのための上界 関数 の効果
5.1 ベ ク トル合成 に よるデー タ圧縮
まず,ベ ク トル合成 に関す る実験 と して,デー タ圧縮
デ ー タ圧 縮 の効 果 を確 か め るた め に ,v
ar
i
at
i
onal
の効果 を確 かめ る.そ して,効率 的 な類似度計測 の観
点か ら,AMSSの上界 関数 を用 いた場合の検索の正当
angl
e
sの しきい値 を o≦ Oth,eth ≦ 45,var
i
at
i
onal
ar
e
aにお け る情 報損 の 許 容 量 を決 定 す る重 み W を
性 を証明す る.検索 には k- 1の場合の近傍検索 を用
0.
0≦ W ≦ 0.
5の範 囲 と し,ベ ク トル合 成 の実験 を
いる.近傍検索 とは.問合せ Q と数値 kが与 え られ
[
4
]で使 用 されてい る一次元
行 う. なお,本実験 で は,
たときに,Q に最 も類似 した k個 のデー タを検索す る
のデー タセ ッ トを用 いてい る. このデー タは時系列 の
ものである.
デー タマ イニ ングのため に無償 で提供 されてい るデー
上界 関数 を用 いた近傍検索 で は,実際 に検索 を行 う
タであ り, ノイズ を含 むデー タ,周期性 のあ るデー タ
前 に,デー タベ ース中のすべ ての時系列 に対 して,令
2の デー タセ ッ トで構 成 され てい る.そ
な ど様 々な 3
成ベ ク トル列 を作成 してお く.そ して,問合せ 時系列
の中で,本節 では表 4の もの を用 いてい る. また,吹
Qが与 えられる と,表 3のアル ゴリズム を用 いて近傍
節 か らの実験 において も同一のデー タセ ッ トを用 いて
検索 を行 う.
い る.
ar
i
at
i
onalar
e
aか Ⅷr
i
at
i
onalangl
e
sを
まず は,v
用 い て Q か ら合成 ベ ク トル列
′
＼
Q ｡｡m
を作成 す る.吹
′
ヽ
i
at
i
onalangl
e
sを用 いたデー タ圧縮 の結
図 6は Ⅷr
果 を示 してい る.横 軸 は r
e
gi
ons
e
c
t
orの 中心 角 の し
にデー タベースか ら合成ベ ク トル列 Ccom を一つ取 り
きい値
ecom ) を計算す る.これが こ
出 して UB AM SS(Q com ,
あ る.圧 縮 率 は, も との 時系 列 の長 さに対 す る圧 縮
れ までの最大類似度 よ り大 きい場合 には,本来 の類似
され た時系 列 の長 さの割 合 で表 してい る.結 果 か ら,
Othreth,縦軸 は圧 縮率
c
o
mpre
s
s
i
o
nr
at
eで
2931
電子情報通信学会論文誌 2
008/1
2Vbl
.J91
-D No.
1
2
Co
mpr
e
s
s
i
onwi
t
hva
ia
r
t
i
ona
la
r
e
a
Compr
es
s
i
onwi
h va
t
ia
r
t
i
ona
la
n gl
es
9
0
98
7
(
0
5
4 3 2 1
0 00 0 0 0 0 0 0
a
t
t
!
JuOt
S
S
aJdu ou
8
0
7
6 5 4
U
▲
O O
O
3 2
O O
33tu uOTSS
aJdu o3
b
n
u
e
P
w
y
.
S
,
e
k
n
S
O
r
0
0
0
10
20
30
0.
1
0.
2
40
a
ngl
et
hr
e
t
hol
d
0.
3
0.
4
0.
5
W
図 8 Var
i
ati
onalar
ea を用 いたデー タ圧縮 の結 果
図 6 Var
i
ati
onalangl
esを用 い たデー タ圧縮 の結 果
Fi
g.
6 Dat
ar
educt
i
onbyvar
i
at
i
onalangl
es.
Fi
g.
8 Compr
es
si
onr
at
ebyvar
i
ati
onalar
ea.
60
0
軌跡 を もつ デー タに対 して有効 で あ る こ とが分 か る.
500
しか しなが ら,デー タのサ ンプ リング と座標値の関係
400
によっては有効 で ない場合 もある.
300
a
r
i
at
i
onala
r
e
aを制約条件 と して用 いたベ ク
次にv
200
1
00
00
トル合成 の結果 を図 8 に示す.横軸 は W ,縦軸は圧縮
o
h
u
y
t
∼
L
^
い
仰
ぎ
叫
.
州
,
′
､こ
,
O
∧
O
,
ゞ
(
,
"
,
Y
"
,
y
L
,
小
山
U
}
U
J
t
J
y
t
+
50
1
00
1
50
200
250
図 7 時系列 net
wor
k の軌跡
Fi
g.7 Shapesoft
r
aj
ect
or
yofdat
a"
net
wor
k.
"
率c
o
mpre
s
s
i
o
nr
at
eを示 している.v
ar
i
at
i
onalar
e
a
に よるベ ク トル合成 で は,v
a
r
i
a
t
i
onalangl
e
sの よ う
に しきい値 による圧縮率 のば らつ きが少 な く,すべ て
のデー タに対 して適切 に圧縮で きていることが分かる.
s
hut
t
l
e,bur
s
tは小 さい しきい値 で も適切 にベ ク トル
この実験 よ り,ベ ク トル合成 に よ り十分 にデータ量
合成 されている こ とを表 してい る. これは, これ らの
が圧縮 で きるこ とが証 明 された. これは時系列 間の類
デー タの軌跡 が滑 らかで,時系列 中のベ ク トルの方向
似 度 の計算 を効率化 す るため に有効 であ る. しか し,
がそろっているためであ る.
ベ ク トル系列 の大部分 を合成 して しまうと,上界関数
一 方 ,ba
ll
oon と buo
ys
e
ns
orの圧 縮 性 能 は悪 く,
に よる類似 度 とも との類似度 との緊密性 が低 くな り,
しきい値 を大 き くしない と多 くのベ ク トルが合成 され
多 くの時系列 を検索対象か ら除 くこ とがで きな くなる.
ない ことが分か る. この原 因は,時系列 中のベ ク トル
この ようなデー タ圧縮 と上界 の性能の関係 については
が振動 してお り,小 さな しきい値 の制約 で は,ほ とん
次節以降で説 明す る.
e
t
wor
k
どベ ク トル合成 され ないためであ る. また,n
は図 7の よ うな滑 らか な軌 跡 を してい る に もかか わ
5.2 上界の緊密性
まず上界 の 緊密性 を調べ る.緊密性 は上界 (
下界 )
らず,他 のデー タと比較 して,圧縮 の性 能が悪 い結果
.
0に近い
関数 ともとの類似 度関数 との比 で表 され, 1
となってい る. これ は,ne
t
wor
kの座標値 がサ ンプ リ
ほ ど,上界 (
下界 )関数の性 能が高い といえ,上界関
ング レー トと比 較 して極 端 に大 きい こ とが原 因で あ
数 を用 いた検索 時 に多 くの検索候補数の削減 を期待 で
る.実 際 ,ne
t
wor
kはサ ンプ リング点 1
00あ た りで
きる. ここでは,[
4]で掲載 されている既存の DTW の
起 こっている変局点 の ほか に も,小 さな振動 を繰 り返
下界 関数 と比較 を行 う.対象 とす るのは LBKi
n[
8
]
,
して,時系列が変化 してい る.座標値 がサ ンプ リング
LBYi[
1
4]
,LBKe
ogh[
4]であ る･
レー トと比較 して小 さい場合,振動時 の角度変化 も微
LBKi
m では,各時系列か ら特徴ベ ク トルを抽 出 し,
小 な もの とな り,適切 な圧縮 を行 うこ とがで きる. し
Yiの下界 関数 は,時系列 の値
下界 が定義 され,LB-
t
wor
kの ように座標値 が大 きい場合 では,大
か し,ne
の最大値 と最小値 を用 いて定義 されてい る.そ して,
きな変局点以外 の角度変化 で もしきい値 よ り大 きな値
LBKe
oghは ワ- ビング制約内の最大値 と最′
J
､
値 を用
となるため に適切 な圧縮が行 われない.この こ とか ら,
いて定義 され るてい る.
va
r
i
at
i
onalangl
e
sに よるベ ク トル合成 は,滑 らか な
2932
og
h らの研究で用 いた もの と同 じ本実験 では,Ke
窟文/時系列の類似性検索 における上界関数による効率化
me
a
nva
l
ue
sof32da
t
a
s
e
t
0
ノ(
X)7 /
▲
U5 4 3●2 ,0
0 00 0 0 00 0
S
S
aqもf
一
0
表 5 検索結 果の比較
Tabl
e5 Compar
i
s
onofr
et
r
i
evalr
es
ul
t
s.
1
dat
aO
dat
a1
dat
a2
dat
a3
dat
a4
dat
a5
dat
a6
dat
a7
dat
a8
dat
a9
tO.
O dV
れ
o
o.
0叫く
1
0
40
0慧1
0
'
NN
D
V
0t
.
D
LW
033[･中1
NdDNV
鳥
叫
^･
ql
uZ
T
X･
q1
/
L
U
5
4
3
0
■
2
0
●
0
1●
t
O
.
〇由V
SOOd 出V
T
暮d dJI
0.
NDNV
0.
IDZ一
q
N.
ODNV
q1
すべ てのデー タセ ッ トの 緊密 性 の平均 を図 9 に示
ar
i
at
i
onal
す.本実験 では,AMSSの上界 の緊密性 を v
息
･
q1
で行 い,平均値 を算 出す る.
oa¥
t
L
[TX
0
して,緊密性 を計算 す る. この過程 をすべ ての時系 列
a
)
TTj
て,5
0個 の うちの 1個 か ら他 の 49個 の時系 列 を比較
0
32の デ ー タセ ッ トか ら
2Jt
2
JSup
実験 の ため に, そ れ ぞ れ の
5
4の時 系列 を ラ ンダム に 5
0個 抽 出す る.そ し
長さ2
0
次元 デー タの デ ー タセ ッ トを用 い てい る [
4
]
.
me
a
nva
l
ue
sof32
da
t
a
s
e
t
0
図 9 緊密性 の平均
Fi
g.
9 Meansoft
i
ght
nes
s･
AMSS AMSSwi
t
hUpperBound
dat
a3
dat
a3
dat
a17
dat
a17
dat
a19
dat
a19
dat
aO
dat
aO
dat
a38
dat
a38
dat
a22
dat
a22
dat
a39
dat
a39
dat
a9
dat
a9
dat
a9
dat
a9
dat
a44
dat
a44
図 10 フ ィル タリング率 の平均
Fi
g.1
0 Meansoff
il
t
er
i
ngr
at
e.
2,
1.
0,
2.
0) と var
i
at
i
onalangl
e
s
a
ng
le
s(Oth,eth -0.
(
W - 0.
0
01
,
0.
005,
0.
01)につ い て調べ てい る. 同様
また, フ ィル タ リングに よ り f
al
s
edi
s
mi
s
s
alを生 じ
Ki
n,LBYi
,LBI
Ke
og
h
に,DTW の下界である LB-
ない こ とを付 録 2.で数 学 的 な証 明 に よ り,上界 関数
について も調べ てい る.
の類似 度 が もとの類似 度 よ りも大 き くな る こ とを示 し
結果 か ら,v
ar
i
a
t
i
onalangl
e
s,v
ar
i
at
i
onalar
e
aに
てい る.そ して,すべ ての検索対象 を比較す る と,実際
よるベ ク トル合 成 は ,既 存 手 法 で 最 も緊密 性 の高 い
al
s
edi
s
mi
s
s
l が生 じない こ とを確 認 で きた.確認
a
にf
LBKe
oghよ り更 に緊密 で ある こ とが確 認で きる. こ
結 果 の一部 と して, デ ー タ ne
t
wor
kの da
t
aO-dat
a9
れ は,本 手 法 に よるデ ー タ圧 縮 で定 義 され た上 界 が ,
に対 して検 索 を行 った確 認 結 果 を表 5 に示 す. こ こ
類似 時系列検 索 の効率 化 に有効 で あ る こ とを示 してい
で,上界 関数 には v
ar
ia
t
i
onalangl
e
s (Oth,eth -1.
0)
る.す なわ ち,緊密性 の高 い上界 を用 いれ ば, よ り低
を用 い てい る.
い計算 コス トでの類似 時系 列 の検 索が可 能 になる.
そ して,すべ て のデ ー タセ ッ トの フ ィル タ リング率
5.
3 上界 に よるフ ィル タ リン グ
の平均 を図 1
0に示 す.本 実験 で は,ベ ク トル合 成 に
最後 に,類似 す る時系 列 デ ー タの検索 にお け る フ ィ
はv
ar
i
at
i
onalangl
e (Oth eth - 0.
2,
1
.
0,
2.
0) と v
ar
i
,
ル タリングの効果 を示す.上界 を用 いた検 索 を実行 し,
a
t
i
onalangl
e
s(
W - 0.
001,
0.
005,
0.
01) を用 い て上
フ ィル タ リング率 を求 め ,[
41で掲 載 され てい る DTW
界 を計算 し, フィル タリング率 を調べ てい る.同様 に,
の下界 関数 に よる フ ィル タ リング率 と比 較 す る. フ ィ
DTW の下界 で あ る LBKi
n,LBYi
,LBKe
oghに
ル タリング率 とは, どれだ け似 てい ない検索対 象 を外
つ い て も調 べ てい る.
す ことがで きたか を表す値 で,1
.
0に近 いほ ど上界 (
下
結果 か ら,v
ar
i
at
i
ona
l angl
e
s (0伽 eth -0.
2)に よ
罪) 関数の性 能が 良 い とい え る.更 に, この値 が大 き
る上界 の フ ィル タ リング率 が ,最 も高 い値 を示 してい
いほ ど,検索 にかか る時 間 を短縮 す る こ とが で きる.
る. また ,v
ar
i
at
i
onalangl
e (Oth,eth -1,
0,
2.
0) と
2
9
3
3
電子情報通信学会論文誌 2
008/1
2Vbl
.J91
-D No.
1
2
ba
l
l
oon
var
i
at
i
onalang
le
s(
W- 0.
001,
0.
005,
0.
01)による上
は ともに 0
-1までの制 限 された催 しか とる ことが な
0.
類似度 は高 くな り,緊密性 も必然 的に高 くなる.その
4
0.
Ke
oghよ り高 いが,フィル タリン
ため,緊密性 は LB-
5
い. また,比較す る時系列が似 ていれば似 てい るほ ど,
u
O
具体 的には,DTW では 0-∝'までの距離 を計算 し,
類似度 を算 出 しているが,AMSSの類似度,上界 関数
a
t
よる ものだ と考 え られ る.
aJ
t!J U叫) !n
T 3
aX3
9
8
7
′ 6
∧
U
0
A
U
0
が悪 くなってい る.これは,AMSSの類似度の定義 に
O
) 8 7
6
0
. 0. .
0
0.
a)｡J 叫upa tlTj
界の フィル タリング率 は LBKe
og
h と比較す る と性能
1
0.
9
0.
8
0.
7
0.
6
グ率 は低 い とい う結果が生 じている. しか し,ベ ク ト
c
ompr
es
s
i
onr
a
t
e
Ki
n,
ル合成 による上界 関数 の フィル タリング率 は LB-
s
hut
t
l
e
E
!
tO
!
を終 える までの時 間 を指す. したが って,上界関数 を
0.
4
a
t
)
!
Ja ′0 u 4
T
n33Xa
X
l
2
(
0
0. 0
0
次 に, フィル タリング率 と実行時 間短縮率 の関係 を
調べ る. ここで,実行 時 間は検索 要求が きてか ら検索
6
4.
0
0
●a
9 盲 JB
uu
)
TTJ
で きる.
8.
0
LBYi手法 よ り勝 ってお り,上界 関数の妥 当性が確認
0.
5
用い ない場合 は,検索対象 と最 も類似度 の高 いデー タ
を求め る時間であ り,上界 関数 を用 いた場合 では表 3
の検索 アル ゴリズム を実行す る時間であ る.実行 時 間
短縮率 は両者 の時間の比 に よ り表 している.使用す る
デー タは 3
2のデー タセ ッ トか ら特 に bal
l
oon,s
hut
t
l
e
とい うデー タを用いている.これは,s
hut
t
l
eは滑 らか
l
l
oonは振幅 の激 しい
な軌跡 を措 くデー タであ り,ba
1
.
0 0.
9 0.
8 0.
7 0.
6 0.
5 0.
4 0.
3
c
ompr
e
s
s
i
o
nr
a
t
e
図 11 bal
l
oon と shut
tl
eの フ ィル タリング率 と実行時間
の短 縮率
Fi
g.ll Fi
l
t
eri
ngr
at
eandexecuti
ont
i
mer
at
eofba1
l
oonandshut
t
l
e.
デー タとい う特徴 をもっていることによる.これ らの二
つのデー タに Ⅷr
i
at
i
onalangl
e
s
,v
a
r
i
a
t
i
onalar
e
aを
適用 した場合 の有効性 を検証 す る. なお,v
a
r
i
at
i
onal
angl
e
s,var
i
at
i
onalar
e
aはそれぞれ, しきい値 によっ
て圧縮 率 が異 なるの で, 同 じ尺度 で比較す るため に,
デー タの圧縮率 とフ ィル タ リング率 と実行時 間短縮率
の関係 を調べ ている.
図 11は ba
l
l
oon,s
hut
t
l
eにお けるフ ィル タリング
率 と実行 時 間短 縮 率 を示 して い る. また,DTW に
LBKe
oghを用 いた場 合の実行 時 間短縮率 は bal
l
oon
で は O.
53,s
hut
t
l
eで は 0.
4 となって い る(
注2). この
図 にお い て,横 軸 はベ ク トル合 成 を行 った ときの圧
縮 率 ,縦 軸 は フ ィル タ リ ング率 と実 行 時 間短 縮率 で
あ る.T_
ang,T_
are
aはそ れ ぞ れ,var
i
at
i
onalan-
な検索が可能 になってい る.
また,s
hut
t
l
eで は va
r
i
a
t
i
ona
la
r
e
aの優位性がわず
hut
t
l
eが滑 らかな軌跡であ
か に確認で きる.これは,s
るために,v
a
r
i
a
t
i
onalangl
e
sでは多 くのベ ク トルを一
度 に合成 しす ぎ,緊密性 が低 くなっていることが原 因
l
l
oonでは v
a
r
i
a
t
i
onal
である と考 え られ る.逆 に,ba
l
oonが振
angl
e
sの優位性 が確認 で きる. これは,bal
動 の激 しいデー タであ るため に,v
ar
i
a
t
i
onalar
e
aで
は繰 り返す方向の違 うベ ク トルを合成 して しまい,緊
密性 が下が ってい る こ とが原 因であ る と考 え られる.
しか しなが ら,両手法 とも, フ ィル タリングを用 いな
Ke
oghと同程度の検索効率であ
い場合 に比べ て,LBる4
0-50%程度 の時 間で検索 で きてい る.
,v
ar
i
at
i
onalar
e
aを用 い た場 合 の実行 時 間短 縮
gl
e
s
any,F_
areaはそれぞれ,va
r
i
a
t
i
onalangl
e
s
,
率 ,F_
var
i
at
i
onala
r
e
aを用 い た場 合 の フィル タ リング率 を
表 してい る.ba
l
l
oon,s
hut
t
l
eともに, フ ィル タリン
グ率 が増加す る と,実行時 間が短縮 される こ とが分か
る.す なわち,高い フ ィル タリング率 によ り,効率 的
2934
6. む す び
本研 究 で は,類似 時系列 の検索 を高速化 す るため,
(
注 2):実行時 間短縮 率 につ いては 刷 で 言及が なか ったため ,[
4】に掲
載 されてい る ように,我 々が実装 した ものである.
論文/時系列の類似性検索 における上界関数 による効率化
表 6 ラベ ル 4の t
e
S
tデ ー タに対 す る DTW ,AMSSの
検索結果上位 3個
Tabl
e6 Ret
r
i
evalr
es
ul
tofDTW andAMSSf
ort
es
t
dat
aofl
abel4.
AMSS
dat
a
cl
as
s
t
r
ai
Ⅰ
1
【
83]
t
r
ai
n【
178]
t
r
ai
n【
11
4]
4
12
4
DTW
dat
a
name
t
r
ai
n【
392]
t
r
ai
n【
321]
t
r
ai
n【
307]
4
4
15
図 12 基準 時系列
Fi
g.12 Bas
i
clt
i
mes
er
i
esdat
a.
ベ ク トル合成 を用 いた上界 関数 に よる フ ィル タリング
を実装 した.本手法 は,f
al
s
edi
s
mi
s
s
alを生 じず,時
系列 間の類似度 を効率的 に計算す る こ とが で きる. こ
の ことを実証す るために,上界が成 り立つ こ とを数学
図 13 時 間伸縮 に よる時系列 の変化
的帰納法 に よって証明 した.ベ ク トル合成 の評価実験
Fi
g.13 Tr
ansi
ti
onbyt
i
mewar
pi
ng.
では,デー タ量削減の正当性 を証 明す るこ とがで きた.
また,上界 に よるフ ィル タリングを評価 して,ベ ク ト
ル合成が有効 であ ることを示 した.
本手法 は,｢
AMSSの時間伸縮 による脆弱性｣,｢
va
r
i
-
a
t
i
ona
langl
e
sの汎用性 ｣｢
var
i
a
t
i
onala
r
e
aに よるベ
ク トル合成｣,｢
上界 関数 の緊密性｣ とい う問題点 を抱
えている.
to
･
x
5
o
L
i
o
u
まず,時 間伸 縮 に よ る脆 弱 性 につ い て検 証 す る.
i
i
図 1
4 振 幅の変化 に よる時系 列の変化
AMSSの分類性 能 自体 は [
1
]で議 論 を行 ってお り,[
5
]
Fi
g.1
4 Tr
ans
i
t
i
onbyampl
i
t
ude･
の一次元 のデ ー タセ ッ トにお け る分 類 性 能 は付 録 の
.
て
表 A･
1の ようになっている. ここで,DTW は最適
なワ- ビング制約 を用 いた もので,L
CS
Sについては
2点間の差異が 1
0%内であれば類似 となる ように して
いる.そ して,最 も誤差が少 なか った値 を太字で示 し
V
三
(
a
)
o
･
…
』
仲)
亀
,o
L
o
5
k
ている.これ よ り,AMSSが類似度測定 関数 と して妥
図 15 時 間伸縮 と振幅の変化 を組み合わせ た時系列の変化
当な ものであることが確認 で きる.
Fi
g.15 Tr
ans
i
t
i
onbyt
i
mewar
pi
ngandampl
i
t
ude.
,
しか し,詳細 を見 る と AMSSは時 間伸 縮 に弱 い こ
とが分かる.例 えば,デー タセ ッ ト5
0wor
ds中のラベ
図1
2と図 1
3(
a)
,(
b)間の類似度 を DTW ,AMSSで
ルが 4で あ る t
e
s
tとい うデー タ用 い た場 合,DTW ,
求 め る.DTW で は類似度 が ともに 0とな り,AMSS
AMSSの検索結果 の うち上位 3個 を表 6に示す. こ
で は ともに 0.
95となる.DTW の類似度 は AMSSと
こで,t
r
ai
nl
二
i
]は i番 目の訓練 デー タを示す.
異 な り,0 に近 い ほ ど,時系 列 が似 て い る とい え る.
表 よ り,両手法 とも正 しく検索 がで きているこ とが
確認で きるが,AMSSの ラベ ル 1
2のデー タの方が ラ
ベル 4のデー タよ りも類似度が高い結果 となっている.
そのため,時間の伸縮 に対 して DTW で は類似度 の変
化 が起 こ らず,AMSSに比べ て優位 が確認 で きる.
また,図 1
4,図 1
5の ように,振 幅の変化 や,時 間
これ はデー タ 5
0wor
dsが時系 列 中で時 間伸縮 を起 こ
伸 縮,振 幅変化 を組 み合 わせ た変化 を与 えた もの に対
してお り,AMSSでは時間伸縮 によ り適切 な類似度 を
して 同様 に計 算 す る と,表 7の よ うにな る.結 果 よ
求め られていない こ とが原 因であ る.
り,AMSSは,時 間伸縮 ,振 幅の変化 に対 して,類似
時 間伸 縮 の脆 弱 性 につ い て更 に詳 細 に検 討 す る.
度 の変化 が起 こるが,時 間の伸 張 と振 幅の増加 が 同時
図1
2の ような時系列があった場合 ,図 1
3(
a)は図 1
2
に起 こる場合 ,あ るい は時 間の短縮 ,振 幅 の減少が 同
の時 間 を 2倍 に伸 張 した デー タ,図 1
3(
b)は時 間 を
時 に起 こる場合 に対 しては頑強であ る こ とが確認 で き
1
/
2に短縮 したデー タを表 す. これ らのデー タの うち
る.この ように,AMSSは DTW と異 な り,時系列 の
2935
電子情報通信 学会論文誌 2008/12Vbl
.J91-D No.12
表 7 時 系列 の変化 に よる類似 度 の変化
Tabl
e7 Di
f
r
er
enceofs
i
mi
l
ar
i
t
ybyt
i
mes
er
i
es
t
r
ans
l
at
i
on.
DTW
時 間伸縮
振 幅 変化
(
a)
0
(
a)
1
(
b)
0
組 合せ
(
b) (
a) (
b)
0.
5 1 0.
5
(
C) (
d)
1 0.
5
ベ ク トル数 を増 や した方が,緊密性 は低 くなるが,ベ
ク トル を近似 す る とい う観点 で は, (
C
)のベ ク トル合
成 の方が もとのベ ク トル系列か らの誤差が小 さ く,全
体 と しては近似 の精度が上が る場合 も存在す る可能性
が あ る.
最後 に,上界 関数の緊密性 につ いて述べ る.本論文
′
0
番
5
弟
5
7 ′
U 5 4
7
｡7
7 エ
リ
4 3 2
1
1
1 2 3
の要素 か ら上界 関数 を定義 したが,構成ベ ク トル系列
の角度分布 を用いれば, よ り緊密性 を高 くす ることが
で き,更 な る類 似 性 時系 列検索 の効 率化 が で きる と
つ
J つ
▲ l
4 つ
J 2
0
では,ベ ク トル系列 の最大角度 と最小角度 とい う二つ
0
考 え られ る.今後 は, これ らの弱点 を改善す る必要が
ある.
文
1 2 3 4
仲)
(
a
)
(
C
)
図 16 ベ ク トル合成 に よる類似 度 の変化
Fi
g.1
6 Changeofs
i
mi
l
ar
i
t
ybyvec
t
orc
ompos
i
t
i
on.
[
1
] 中村哲 也 ,瀧
献
敬 士 ,上原 邦照 , "
AMSS:時系 列 デー タ
D), γol
.
J91
D,
の 効 率 的 な類 似 度 測 定 手 法 ,
"信 学論 (
no.
ll,pp.
2579-2588,
Nov.2008.
[
2] D･
JIBer
ndtand I.Clif
f
or
d, "
Fi
ndi
ng pa
t
t
er
nsi
n
"Adt
i
mes
er
i
e
s:A dynami
cpr
ogr
ammi
ngappr
oac
h,
形 に依存 して類似性 が決定す るため,単純 な時 間伸縮
には弱 い こ とになる.
ar
i
at
i
onalangl
e
sの汎用性 につ い て検 討 す
次 に,v
ar
i
at
i
onalangl
e
sは,座標値 とサ ンプ リング レー
る.v
トの関係 に よっては,滑 らか な軌跡 を してい るデー タ
であ って も適切 にデー タ圧縮 を行 えない.加 えて,滑
らか な軌跡 を してい るデー タ と振動 の激 しいデー タで
vance
si
n Knowl
edge Di
s
c
over
y and Dat
a Mi
ni
ng,
pp.
229-248.AAAI
,1
996.
os,and 班.Manni
l
a, "
Fi
ndi
ng
[
3] G･Das D･Gunopul
,
" Pr
oc･Fi
r
s
tEur
opean Sympos
i
mi
l
art
i
mes
er
i
es,
s
i
um on Pr
i
nci
pl
esofDat
a Mi
ni
ng and Knowl
e
dge
Di
s
c
over
y,pp.
88-1
00,1997.
Exacti
nde
xi
ng ofdynami
ct
i
mewar
p[
4] E･Keogh, "
i
ng,
"Proc.28th Internati
onalConf
er
ence on Ver
y
Lar
geDat
aBas
es,pp.
406-417,2002.
は,同 じしきい値 によるデー タ圧縮量 の差が大 き く異
[
5] E･ Keogh The UCR Ti
me Ser
i
es Dat
a Mi
ni
ng
なる. この ように,一意 な しきい値 で同様 のベ ク トル
Ar
c
hi
ve,20061ht
t
p:
//www.
c
s.
uc
r,
edu/eamonn/
ar
i
at
i
onalangl
e
sは汎
を行 うこ とが で きない ため,v
,
TSDMA/i
nde
x･
ht
ml
l
6] E･Keogh K･Chakr
abar
t
i
,MLPaz2
:
ani
,and S.
,
用性 に欠 けてい る.
Mehr
ot
r
a, "
Local
l
y adapt
i
ve di
mens
i
onal
i
t
yr
educ
-
ar
i
a
t
i
onalar
e
aにつ い て も問題 点 が あ る.
次 に,v
va
r
i
a
t
i
onalar
e
aは , どの よ う な デ ー タで もデ ー タ
量 を削 減 で きるが ,上 界 が あ ま り緊 密 で は な い 場
合 が あ る . これ は ベ ク トル 合 成 方 法 に よ る もの で
6の (
a)の よ うなベ ク トル系 列
あ る.例 え ば ,図 1
Q(
(
1,
1
)
,
(
1,
3)
,
(
1,
1
)
)C(
(
1,
3)
,
(
1,
3)
,
(
1
,
3))が あ る
場合,それぞれのベ ク トルの時間軸か らの角度 は系列 Q
では 45度,71.
6度,45度 とな り,系列 Cでは 63.
4度,
t
i
onf
ori
nde
xi
ngl
ar
get
i
mes
er
i
esdat
abas
es
,
"Proc.
200l ACM SI
GMOD I
nt
er
nat
i
onalConf
er
ence on
ManagementofDat
a,pp.
151
-162,2001.
[
7] E･Ke
og
h ,X･Xi
,L･Wei
,andC･
A･Rat
n amahat
a
ana,
The UCR T
i me Ser
i
es Cl
as
s
i
ic
f
at
i
on/Cl
us
t
eri
ng
Homepage,2006.
ht
t
pソ/www･
cs･
ucr
･
edu/ eamonn/t
i
mes
er
i
e
s
dat
a/
,
63.
4度 ,63.
4度 となる.これ らか ら類似度 を算 出す る
とc
os
(
45-63･
4)
+c
os
(
71.
6-63･
4)
+c
os
(
45-63.
4)-
2.
89とな る. こ こで, (
b)
,(
C)の よ うに合 成 ベ ク ト
n ,S･Par
k,andW ･
W ･Chu,"
Ani
nde
xbas
e
d
[
8] S･
一
W ･Ki
appr
oac
hf
ors
i
mi
l
ar
i
t
ys
ear
c
hs
uppor
t
i
ngt
i
mewar
p-
"Proc･17thlnternai
ngi
nl
ar
ges
equencedat
abas
es,
t
i
ona
l Conf
er
enc
eonDat
aEngL
neer
i
ng,pp.
607-61
4,
2001.
[
9】 J▲Li
n,E･Keogh,S.Lonar
di
,andB･Chi
u,"
As
ymbol
i
cr
epr
es
ent
at
i
onoft
i
mes
er
i
eswi
t
hi
mpl
i
cat
i
ons
ル系 列 を生 成 した場 合 ,上 界 関 数 の 定 義 を用 い て
f
ors
t
r
eami
ngal
gor
i
t
hms,
"Proc.8thACM SIGMOD
b)の よ うなベ ク トル 合 成 で は
類 似 度 を求 め る と (
Wor
ks
hop on Res
each I
s
s
ues i
n Dat
a Mi
ni
ng and
2*
c
os
(
71･
6-63.
4)+c
os
(
45-63･
4)-2.
93,(
C
)の
ようなベ ク トル合成 で は 3*
c
os
(
71.
6-63.
4)-2.
97
となる. この ように,緊密性 の観 点か らい うと,合成
2936
Knowl
edgeDi
s
c
over
y,pp.
2-ll
,2003.
[
101 大 桃 諭 ,陳 漢 雄 ,古 瀬 - 隆 ,大保 信 夫 , "タイム ワビ ングに基づ く時系列 デー タの類似検索 ,
"DBSJ,分冊 4,
m0.
1,pp.
17-20,2005.
論文/時系列 の類似性検索 における上界関数 に よる効率化
表 A･1 最近傍分類におけるユークリッド距離,DTW ,
LCSS,AMSSの性能
Tabl
eA･1 Cl
as
s
i
icat
f
i
on per
f
or
manceofEucl
i
dean
di
s
t
ance,war
pi
ngwi
ndow DTW ,LCSS
AMSSwi
t
h1
near
e
s
tnei
ghbor
.
[
11
] Y･ Sakur
ai M･ Yos
hi
kawa, and C･ Fal
out
s
os,
u
FTW :Fas
ts
i
mi
l
ar
i
t
ys
ear
c
hundert
het
i
mewar
p,
"Proc･24th ACM SIGMOD-SIGACTi
ngdi
s
t
anc
e,
,
SI
GART Sympos
i
um onPr
i
nci
pl
e
sofDat
abas
eSys
t
ems
,pp.
326-337,2005.
[
12
｣ Y･Tanaka,K.I
wamot
o,and K･Uehar
a,"
Di
s
cover
yoft
i
me
s
er
i
e
smot
i
ff
r
om mul
t
i
di
mens
i
onaldat
a
"Mach.Learn.
,vol
.
58,m0.
2bas
edonMDLpr
l
nCi
pl
e,
3,pp.
269-300,2005.
i
el
ef
ther
i
ou, D･Gunopul
os,
[
1
3] M･Vl
achos, M･Hadj
and E.Ke
ogh,"
Ⅰ
nde
xi
ng mul
t
i
di
mens
i
onalt
i
me
s
er
i
eswi
t
hs
uppor
tf
ormul
t
i
pl
edi
s
t
anc
emeas
ur
e,
"
Pr
oc.9t
h ACM SI
GKDD I
nt
er
nat
i
onalConf
er
ence
on Knowl
edgeDi
s
cover
yand Dat
aMi
ni
ng,pp.
216225,2003.
[
1
41 BI
KIYi
,H･
V･Jagadi
s
h,andC.Fal
out
s
oS
,"Ef
nci
ent
r
et
r
i
evalofs
i
mi
l
art
i
mes
equenc
esundert
i
mewar
pi
ng,
"Proc.14th Internati
onalConf
er
enc
eon Dat
a
Engl
neer
i
ng,PP.
201
-208,1998.
付
録
1. AMSSの分類性能
Dat
as
et
GunPoi
nt
Tr
ace
Fi
s
h
OSU Leaf
Swedi
s
hLeaf
Co庁e
e
Adi
ac
Be
ef
50Wor
ds
Eucl
i
dean
0.
087
0.
240
0.
217
0.
483
0.
213
0.
25
0.
389
0.
467
0.
369
DTW
LCSS
0.
087 0.
040
0.
010 0.
090
0.
160 0.
11
4
0.
384 0.
306
0.
157 0.
290
0.
179 0.
214
0.
391 0,
675
0.
467 0.
500
0.
242 0.
352
AMSS
0.
000
0.
000
0.
040
0.
103
0.
104
0.
143
0.
345
0.
433
0.
242
Li
ght
i
ng2
Face(
f
our
)
Face(
al
l
)
Li
ght
i
ng7
CBF
0.
246
0.
216
0.
286
0.
425
0.
148
0.
131
0.
114
0.
192
0.
288
0.
004
0.
21
3 0.
180
0.
307 0.
261
0.
393 0.
275
0.
438 0.
301
0.
084 0.
522
Synt
he
t
i
cCont
r
ol
W af
er
ECG
01
i
VeOi
l
TwoPat
t
er
ns
0.
120
0.
005
0.
120
0.
133
0.
09
0.
017
0.
005
0.
120
0.
167
0.
0015
0.
273 0.
527
0.
017 0.
011
0.
1
90 0.
170
0.
500 0.
200
0.
000 0.
090
一次 元 時 系 列 に対 して ,Euc
l
i
de
an距離 ,DTW ,
LCS
S,AMSSに よる 1
Ne
a
r
e
s
tNe
i
ghborを用 い た
分類性能 を表 A.
1に示す.実験 には,UCRTi
meSe
-
r
i
e
sCl
a
s
s
i
ic
f
at
i
on/Cl
us
t
e
r
i
ngPa
get
7
]で配布 されて
0個 のデー タセ ッ トを使用 してい る.
いる 2
2. 上界の証明
al
s
edi
s
mi
s
s
al
上界関数 を用 いた フ ィル タリングで f
を生 じさせ ないため には,不等式 (
1
5)を証 明す る必
とc
T
n
(
A･
6)
Sc
o
m(
9,
h)≧S(
i
,
y)
(
Al
7)
Sc
o
m(
9,
h)≧ S(
i
,
V)
(
A･
8)
式 (
1
0)よ り,合成 ベ ク トル間 ともとのベ ク トル間の
類似度 の関係 は以下の ようになる.
1
5)が成 り立 つ こ とは,数学 的帰
要が あ る.不等式 (
納法 によって証明で きる.なお,合成ベ ク トル
Sc
o
m(
9
,
h)≧ S(
x,
V)
Si
m(
x,
y)≦?i
mc
o
m(
9,
h)
拓 .
;
図 A1
1は,部分ベ ク トル系列
は,それぞれ以下 の部分 時系列 のベ ク トル
(
A･
9)
ノ
ヽ
Qc
o
m と ecom
の類
似度 を求め るための再帰関数 を,ベ ク トル 雇 ,
尋 問の
か らなる もの とす る.
類似度 を用 いて表 した ものである. ここで,太線 の大
-前,
･
-,
q
7,
川,
前
q
T
;
(
Al
l
)
i
fg- 1t
he
ns - 1,i
fg- N/
t
h
e
nt- N
c
T
a
- 己 ,.･
･,
尋,
...,
記
(
A･
2
)
i
fh- lt
h
e
nu- 1,i
fh- M't
h
e
nv- M
ここで,以下の三つの式が成 り立 つ と仮定す る.
(
A･
3)
Sc
o
m(
9-1,
h)≧S(
S
,
y)
(
A･
4)
Sc
o
m(
911,
h-1)≧S(
S
,
u)
間の類似 度 を表 し,太線 のマス
の中の小 マス は 重 ,
尋 問の類似度 を表 してい る.
1 を見 る と,r
e
ion4 (
g
(
x
,
V
)時 点 で の類 似
図 A･
S(
x,V))へ到達す るには,reg
ion1 (
(,
u)時点で
S(
S,
u
)
)
,r
e
ion2 (
g
(
x,
u
)時点 での類似 度
S(
I,
u)
),r
e
ion3 (
g
(,
u)時点 で の類似 度 S(
S,
y
)
)
か ら小 マス を通 り,小 マスの類似度 であ る S
i
m(,
y)
度
a
の類似 度
I
I
Sc
o
,
n
(,
h-1)≧S(
I,
u
)
9
マス は 百品完.;,
c
T
a
(
A･
5)
を足 してい け ば よい . こ こで ,式 (
6)の制 限 を受 け
る場 合 に r
e
gi
on lか ら r
e
gi
on4へ 行 くこ とを考 え
る.再 帰 関数 に よる と斜 め の移 動 で は小 マ ス の類似
度 の 2倍 が 足 し合 わ され る .つ ま り r
e
gi
on4で の
この仮定の もとで,以下 の三つの式が成 り立つ こ とを
e
ion lで の類 似 度 に Si
g
m(
x,
y)の値 を
類似度 は r
示す.
(
2
Mi
n(
V- u,
i-S
)+abe(
(
V-u)-(
i-S
)
)
)個足す
2937
電子情報通信学会論文誌 2
008/1
2Vbl
.J91
-D No.
1
2
一
一
■
c
o
mh
1
′
ヽノ
ヽ
UBAMS
S(
Q,
C)-Sc
o
m(
N'
,
M'
)
･
.
i
Cc
o
mA
一
C
Fu
I Fu
'
;
h
'
ド :
司･
Z ー
◆
◆
◆
■
一
■
こ
qc
o
mgl
l
Fv
≧S(
N,
M)-AMSS(
Q,
a)
(
A･
1
4
)
この結果か ら,類似す る時系列の検索 において,f
al
s
e
,
I
J
i
,,
溢
I
…
招
!
≡
: ■
:
′
′･
.
_
l
l
:
:
.
:
.
:
.
:
ー
い
▼
∴
'
●
→
di
s
mi
s
s
alを生 じない ことが保証で きる.
{
7
.
m(
有.
召I
∼
1
L
)
on_
4
=
qc
o
mg
c
o
m(
q
-C
F
F
S
●
■
●
S
s
s
t
i
i
′
1
轟
a∫
h
一
l
再
mc
o(
q
-c
o
mg
I
:r
e
B
1
0
n
1
･
1
i
L
I
∼
K
(
平成 20年 1月 25 日受付 ,6月 11日再受付)
T
ei
on3
瀧
敬士
平 19神戸大 ･工 ･情報知能工学卒.現
図 A･1 再帰 関数の模式 図
Fi
g.
A･1 A pat
t
er
ndi
agram ofr
ecur
si
vef
uncti
on.
荏 ,同大大学 院工学研究科博士前期課程在
学 中.
ことなる.この結果,不等式 (
A･
5)
,(
A･
9
)か ら,以下
の不等式が得 られる.
S(
I,
V)≦ S(
a,
u)+(
2Mi
n(
V-u,i- A)
中村
+l(V-u)-(
i-S)
I
)
Si
n(
I,
y)
≦Sc
o
m(
9-1
,
h-1
)+(
2c
nd+c
nS
ub
d
)
･
Si
mc
o
m(,
h
)
(
A･
1
0)
哲也
平 18神戸大 ･工 ･情報知能工学卒.現
荏,同大大学院工学研究科博士前期課程在
学 中.
9
同様 に, S(
x,
V)が S(
I ,
u)か ら計算 され る と,以
下の不等式が得 られる.
S(
x,
V)≦Sc
o
m(9-
1
,
h
)
+(
2c
nh+c
nS
ub
h)
9,
h)
･
Si
mc
o
m(
(
A･
1
1
)
上原
邦昭
(
正月)
昭 53阪大 ･基礎工 ･情報工学卒.昭 58
同大大学院博士後期課程単位取得退学.同
産業科学研 究所助手,講師,神戸大学工学
また,S(
x,V)が S(
S,
y)か ら計算 されると,以下の不
等式が得 られる.
部情報知能工学科助教授 ,同都市安全研究
セ ンター教授 を経 て,現在同大学院工学研
究科教授 .工博.人工知能,特 に機械学習,
S(
x,
V)≦Sc
o
m(
a,
h- 1)+(
2
c
nv + c
r
LS
ub
v)
･
Si
mc
o
m(9,
h
)
(
A･
12)
いかなる x に関 して も,これ ら三つの不等式のいずれ
1
3)か ら,
も常 に真であ る. これ らの不等式 と不等式 (
A･
6)が成 り立 つ. この証 明の過程 に従 うと,
不等式 (
不等式 (
A･
7)が真であることも同様 に証明 される.
不等式 (
A･
8)が成 り立つ ことを示すために,不等式
(
A･
6)
,(
A･
7
)において x- i
,
y- V とす る.そ して,
不等式 (
A1
8)で 9-N′
,
h- M ′とすれば,以下の不
等式 を得 る.
Sc
o
m(N′M′)≧ S(N M )
,
,
最終的に,式 (
6
)
,(
1
4
)か ら,不等式
ことが証明で きる.
2938
(
A1
1
3)
(
1
5
)が成立す る
マ ルチ メデ ィア処理 の研 究 に従事 .人工知能学会,計量国語学
会, 日本 ソフ トウェア科学会,AAAI各会員.