Transcript S - 國立雲林科技大學

國立雲林科技大學
National Yunlin University of Science and Technology
Visually Mining and Monitoring Massive Time Series
Author: Jessica Lin, Eamonn Keogh,
Stefano Lonardi, Jeffrey P. Lankford,
and Donna M. Nystrom
Reporter: Wen-Cheng Tsai
2007/05/09
SIGKDD,2004
1
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Outline



Motivation
Objective
Method
─



V-Tree
Experience
Conclusion
Personal Comments
2
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Motivation


Moments before the launch of every space vehicle,
engineering discipline specialists must make a critical go/nogo decision.
To reduce the possibility of wrong go/no-go decisions
─
─

To mine the archival launch data from previous missions.
To visualize the streaming telemetry data in the hours before launch.
Electronic strip charts do not provide any useful higherlever information that might be valuable to the analyst.
3
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Objective

We propose VizTree, a time series pattern discovery and
visualization system based on augmenting suffix trees.
4
Intelligent Database Systems Lab
Method---Viz-Tree
N.Y.U.S.T.
I. M.
Step 1: Discretization (via SAX)
The following time series is converted to string "acdbbdca"
Step 2: Insertion
The following tree is of depth 3, with alphabet size of 4.
The frequencies of the strings are encoded as the thickness of branches.
5
Intelligent Database Systems Lab
Method---Viz-Tree
N.Y.U.S.T.
I. M.
Subsequence Matching and Motif Discovery via VizTree
This example demonstrates subsequence matching and motif discovery. We want to
find a U-shaped pattern, so we'd try something that starts high, descends, and then
ascends again. Clicking on "abdb" shows such patterns.
Motif Discovery
6
Intelligent Database Systems Lab
Method---Viz-Tree
N.Y.U.S.T.
I. M.
Anomaly Detection
7
Intelligent Database Systems Lab
Viz-Tree
N.Y.U.S.T.
I. M.
Anomaly Detection by Diff-Tree
8
Intelligent Database Systems Lab
How do we obtain SAX?
N.Y.U.S.T.
I. M.
C
C
0
20
40
60
80
100
120
c
c
c
First convert the time
series to PAA
representation, then
convert the PAA to
symbols
It take linear time
9
b
b
a
-
0
20
b
a
40
60
80
100
120
baabccbc
Intelligent Database Systems Lab
SAX characterization
N.Y.U.S.T.
I. M.
 Lower bounding of Euclidean distance
Q
Q’
S
S’
DLB(Q’,S’)
D(Q,S)
D(Q,S
)
n
2
  qi  si 
i 1
DLB(Q’,S’)

 Dimensionality Reduction

M
2
(
sr

sr
)(
qv

sv
)
i
i

1
i
i
i 1
SAX
(Symbolic Aggregate Approximation)
baabccbc
10
Intelligent Database Systems Lab
Experience
N.Y.U.S.T.
I. M.
11
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Conclusion

We proposed VizTree, novel visualization framework for time series
that summarizes the global and local structures of the data.

We demonstrated how pattern discovery can be achieved very
efficiently with Viz Tree
─
─
Lower bounding of Euclidean distance
Dimensionality Reduction
12
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Personal Comments

Advantages
─
─

Disadvantage
─

Dimensionality Reduction
Lower bounding distance measures
…
Application
─
Time series
13
Intelligent Database Systems Lab