MINING TIME-SERIES DATA
Time-Series Database
Consists of sequences of values or events obtained
over repeated measurements of time (weekly,
hourly)
Stock market analysis, economic and sales
forecasting,
scientific
and
engineering
experiments, medical treatments etc.
Can also be considered as a Sequence database
Consists of a sequence of ordered events (time
optional)
Web page Traversal Sequence
Time-Series data can be analyzed to:
Identify correlations
Similar / Regular patterns, trends, outliers
Trend Analysis
Time Series involving a variable Y can be
represented as a function of time t, Y = F(t)
Goals of Time-Series Analysis
Modeling time series - To gain insight into the
mechanism
Forecasting time series - For prediction
Trend Analysis Components
Long-term or trend movements (trend curve):
general direction in which a time series is moving
over a long interval of time
Cyclic movements or cycle variations: long term
oscillations about a trend line or curve
e.g., business cycles, may or may not be
periodic
Seasonal movements or seasonal variations
i.e, almost identical patterns that a time series
appears to follow during corresponding
months of successive years.
Irregular or random movements
Time series analysis: decomposition of a time series
into these four basic movements
Additive Model: TS = T + C + S + I
Multiplicative Model: TS = T C
Adjusting Seasonal fluctuations
Given a series of measurements y 1, y,2, y3
influences of the data that are systematic /
calendar related must be removed
Fluctuations
conceal
true
underlying
movement of the series and non-seasonal
characteristics
De-seasonalize the data
Seasonal Index set of numbers showing the
relative values of a variable during the months of
a year
Sales during Oct, Nov, Dec 80%, 120% and
140% of average monthly sales Seasonal
index 80, 120, 140
Dividing original monthly data by seasonal
index De-seasonalizes data
Auto-Correlation Analysis
To detect correlations between ith element and (ik)th element k- lag
Pearsons coefficient can be used between <y1,
y2,yN-k> and <yk+1, yk+2, ..yN>
Estimating Trend Curves
The freehand method
Fit the curve by looking at the graph
Costly and barely reliable for large-scaled
data mining
The least-square method
Find the curve minimizing the sum of the
squares of the deviation di of points yi on the
curve from the corresponding data points i=1 n di2
The moving-average method
Moving Average Method
Smoothes the data
Eliminates cyclic, seasonal and irregular
movements
Loses the data at the beginning or end of a series
Sensitive to outliers (can be reduced by Weighted
Moving Average)
Assigns greater weight to center elements to
eliminate smoothing effects
Ex: 3 7 2 0 4 5 9 7 2
Moving average of order 3: 4 3 2 3 6 7 6
Weighted average (1 4 1): 5.5 2.5 1 3.5 5.5
8 6.5
Once trends are detected data can be divided by
corresponding trend values
Cyclic Variations can be handled using Cyclic
Indexes
Time-Series Forecasting
Long term / Short term predictions
ARIMA Auto-Regressive Integrated Moving
Average
Similarity Search
Normal database query finds exact match
Similarity search finds data sequences that differ
only slightly from the given query sequence
Two categories of similarity queries
Whole matching: find a sequence that is similar to
the query sequence
Subsequence matching: find all pairs of similar
sequences
Typical Applications
Financial market
Market basket data analysis
Scientific databases
Medical diagnosis
Data Reduction and Transformation
Time Series data high-dimensional data each
point of time can be viewed as a dimension
Dimensionality Reduction techniques
Signal Processing techniques
Discrete Fourier Transform
Discrete Wavelet Transform
Singular Value Decomposition based on PCA
Random projection-based Sketches
Time Series data is transformed and strongest
coefficients features
Techniques may require values in Frequency
domain
Distance
preserving
Ortho-normal
transformations
The distance between two signals in the time
domain is the same as their Euclidean
distance in the frequency domain
Indexing methods for Similarity Search
Multi-dimensional index
Use the index to retrieve the sequences that are at
most a certain small distance away from the query
sequence
Perform post-processing by computing the actual
distance between sequences in the time domain
and discard any false matches
Sequence is mapped to trails, trail is divided into
sub-trails
Indexing techniques
R-trees, R*-trees, Suffix trees etc
Subsequence Matching
Break each sequence into a set of pieces of window
with length w
Extract the features of the subsequence inside the
window
Map each sequence to a trail in the feature space
Divide the trail of each sequence into subtrails and
represent each of them with minimum bounding
rectangle
Use a multi-piece assembly algorithm to search for
longer sequence matches
Uses Euclidean distance (Sensitive to outliers)
Similarity Search Methods
Practically there maybe differences in the baseline
and scale
Distance from one baseline to another offset
Data has to be normalized
Sequence X = <x1, x2, ..xn> can be replaced by
X = <x1, x2, xn> where xi = xi - /
Two subsequences are considered similar if one
lies within an envelope of width around the
other, ignoring outliers
Two sequences are said to be similar if they have
enough non-overlapping time-ordered pairs of
similar subsequences
Parameters specified by a user or expert: sliding
window size, width of an envelope for similarity,
maximum gap, and matching fraction
Atomic matching
Find all pairs of gap-free windows of a small
length that are similar
Window stitching
Stitch similar windows to form pairs of large
similar subsequences allowing gaps between
atomic matches
Subsequence Ordering
Linearly order the subsequence matches to
determine whether enough similar pieces exist
Query Languages for Time Sequence
Time-sequence query language
Should be able to specify sophisticated queries
like
Find all of the sequences that are similar to
some sequence in class A, but not similar to
any sequence in class B
Should be able to support various kinds of
queries: range queries, all-pair queries, and
nearest neighbor queries
Shape definition language
Allows users to define and query the overall
shape of time sequences
Uses
human readable series of sequence
transitions or macros
Ignores the specific details
E.g., the pattern up, Up, UP can be used to
describe increasing degrees of rising slopes
Macros: spike, valley, etc.
