Universal SAX: 空間充填曲線を利用した SAX の多次元時系列データへ

DEIM Forum 2012 D4-4
Universal SAX:
SAX
…
112-8610
2-1-1
{onishi.ayaka, chiemi}@is.ocha.ac.jp
E-mail: E-mail:
Lin
Symbolic Aggregate
Approximation (SAX)
SAX
Universal SAX
SAX
Symbolic Aggregate approximation
2
1.
1
1
SAX
Universal SAX
U-SAX
Lin
1
Symbolic Aggregate
1
Approximation (SAX) [6]
SAX
1
[9]
xyz
3
3
SAX
SAX
x
[6]
1
SAX
1
2
SAX
3
3
SAX
x
4
Universal SAX
5
6
[3][10]
2. SAX
SAX
1
w
1
a
2
SAX
1
1
SAX
2: SAX
dist(qො, cො)
qො
cො
3
SAX
[1][8]
4
dist(a,d)
-0.67
d
0.67
1.34
SAX
1: SAX
SAX
(1)
SAX
(2)
(3)
a
b
3
c
2
2
(4)
(2)
SAX
(3)
SAX
SAX
2
Q
C
3: SAX
2
2
SAX
2
dist(qො, cො)
(A)
෡
Q
C෠
(B)
n
SAX
a
3.
SAX
SAX
Universal SAX
4.
SAX
[7]
Universal SAX
Li
[12]
SAX
…
Universal SAX
[7]
2
SAX
1
Li
1
…
SAX
SAX
1
4.1
4.2
Universal SAX
[12]
SAX
4.1…
…
…
1
[4]
4
Z-ordering[5]
4
3
1
1
SAX
SAX
SAX
4:
Z-ordering
2
…
1
1
2୩ × 2୩
(1)
(2)
(1)
1
(2)
2୩ × 2୩
(3)
(2)
k
resolution
5
…
2
X
k=2
Y
(3)
(2)
(51,46,40,38,27,28,…
10,17,15,1)
a଴ , aଵ , aଶ , aଷ
5
(4)
6
6
(4)
(4)
(4)
5:
…
a଴
5
aଵ a଴
aଶ
a଴
aଷ
Z-ordering
Z-ordering
Z-ordering
…
k[3]
4.2 …
SAX
Universal
6: 2
Universal SAX
2
SAX
Universal SAX
2
Universal SAX
…
6
(2)
…
SAX
(1)
t ଴ , tଵ , … , t ୬
6
2
x଴ , xଵ , … , x୬ିଵ
7
2
7
(4)
8: (1)Br
2
(2)Br
2
… Universal SAX
SAX
9
x଴, y଴
dist(x଴, y଴ )
dist′("d", "b")
1
1
xଵ, yଵ
2
dist(xଵ, yଵ )
dist′("c", "b")
0
SAX
dist൫x଴, y଴ ൯ ≧ dist′("d", "b")
9
SAX
7: Universal SAX
…
2
…
8
(2)
k
7
a
49
k=7
2 7 =128
128
9:
Universal SAX
Block resolution Br
1.
2.
8
a=49 Br
5 25
2
k=7
3.
1
Learning Repository
… 1
Character Trajectories Data Set
2858
1
SAX
3
… 2
6
Z-ordering
1
x
Z-ordering
3
y
2
11
(4)
{data1, data2,
10
data3}, {data11,data12,data13}, {data21, data22, data23},
{data101, data102, data103}, {data171, data172, data173},
10
{data226, data227, data228}
2
0
1
SAX
12
…
(1)
(2)
Z-ordering
SAX
k = 10
MdSAX
(4)
a = 20
k = 10
MdSAX
Universal SAX
k = 10
a = 53
a=20
MdSAX
a=7
MdSAX
SAX
2
7ଶ = 49
10: Z-ordering
3
SAX
1
SAX
11:
5.
UCI[11]
Machine
(3)
a=7
20ଶ = 400
Universal SAX
SAX
Universal SAX
…
…
…
12:
(1)
(2) (4)
(2)
(4)
(2)
(2)
53
20, (4)
(2)
400
7
MdSAX
(3)
2
49
(4)
SAX
6.
…
SAX
…
…
[1] Apostolico A, Bock M. E, and Lonardi, S. :
Monotony of Surprise and Large-Scale Quest for
Unusual Words. In proceedingsof the 6th Int’l
Conference on Research , " In Computational
Molecular Biology, 2002 Washington, DC, April
18-21. pp 22-31.
[2] Christos FALOUTSOS. : 5.1 SPACE FILLING
CURVES, " In SEARCHING MULTIMEDIA
DATABASES BY CONTEXT , 1996, pp27-34
[3] Dengsheng Zhang and Guojun Lu. : Review of shape
representation and description techniques, " In
Pattern Recognition, Vol. 37, 2004.
[4] D. Hilbert. :Über die stetige Abbildung einer Linie
auf ein Flächenstück, " In Math. Ann. 38, 1891,
pp459-460.
[5] J.A. Orenstein. :Spatial query processing in an
object-oriented database system, " In SIGMOD, 1986,
pp326-336.
[6] Jessica Lin, Eamonn Keogh, Stefano Lonardi and
Bill Chiu. : A Symbolic Representation of Time
Series, with Implications for Streaming Algorithms,"
In SIGMOD workshop, 2003.
[7] Li Wei, Keogh, E. and Xiaopeng Xi. : SAXually
Explicit Images: Finding Unusual Shapes," In the
IEEE International Conference on Data Mining series
(ICDM), 2006.
[8] Lonardi, S. : Global Detectors of Unusual Words:
Design, Implementation, and Applications to Pattern
Discovery, " In Biosequences. PhD thesis,
Department of Computer Sciences, Purdue University,
August, 2001.
[9]
and
. :
SAX
, " In deim2011, March 2011
[10] Sven Loncaric. : A survey of shape analysis
techniques, " In Pattern Recognition, Vol. 31, 1998.
[11] UCI.
:
http://archive.ics.uci.edu/ml/index.html,"
February 2012
[12] Yoshiki Tanaka and Kuniaki Uehara. : Discover
Motifs in Multi Dimensional Time-Series Using The
Principal Component Analysis And The MDL
Principle, " In Workshop on Machine Learning and
Data Mining in Pattern Recognition(MLDM), 2003.