|
VizTree
Data visualization techniques are very
important for data analysis, since the human eye has been frequently
advocated as the ultimate data-mining tool. However, there has been
surprisingly little work on visualizing massive time series datasets. To
this end, we developed VizTree, a time series pattern discovery and
visualization system based on augmenting suffix trees. VizTree visually
summarizes both the global and local structures of time series data at the
same time. In addition, it provides novel interactive solutions to many
pattern discovery problems, including the discovery of frequently occurring
patterns (motif discovery), surprising patterns (anomaly detection), and
query by content. The user interactive paradigm allows users to visually
explore the time series, and perform real-time hypotheses testing.
Click here for demo. The executable can be downloaded here (make sure you read the README first). The C# code is available upon request.
|
Step 1: Subsequence Extraction and Discretization (via SAX) |
Using a sliding window of size n (user input), extract subsequences via a sliding window. Then discretize each subsequence via SAX, e.g., like the following (the figure shows the discretization of just one subsequence). The time series is converted to string "baabccbc" (see the SAX website for more details). Do this for every subsequence (or selected subsequences if the numerosity option is turned on).
|
|
Step 2: Insertion |
Push the data into a depth-limited, augmented suffix tree.The frequencies of the strings are encoded as the
thickness of branches. The following figure summarizes these steps.
|
|
VizTree Overview |
The design of VizTree follows the Visual Information Seeking Mantra: "Overview, zoom & filter, details-on-demand" championed by Dr. Ben Shneiderman.Since the frequency of each string (pattern) is encoded in the line thickness, thick branches represent frequent patterns, whereas think braches represent infrequent or potentially anomalous patterns.
The example above shows the power consumption time series. A "normal" weekly pattern has 5 peaks, one for each day of the week. If we click on the branch "bab" (a thin branch), we can see that the subsequence mapped to this particular string (shown in the Detail 1 window) indeed has a different pattern: it has 3 peaks instead of 5, as a result of a short, Christmas week.
DiffTree |
If training data is available, we can visualize the distributional differences of patterns between the training data and the testing data. The steps are summarized as follows.
Blue lines: under-represented patterns (pattern is more common in A)
Green lines: over-represented patterns (pattern is more common in B)
Red lines: surprising patterns
For the example below, the blue ECG data is the reference data, and the green ECG data is the testing data. The resulting tree shows the differences in pattern distributions in the two datasets. The surprising patterns are ranked. Clicking on the branch ranked #1, the anomalous heartbeat in the green time series is shown (also highlighted in the time series window).
Relevant Publications |
Back to Main Page