While we believe our paper is self contained, this presentation contains:
1. Augmented and larger scale versions of experiments shown in the paper.
2. Additional experiments that we could not fit in the paper.
3. Comparisons to other techniques (deliberately omitted from the paper forreasons discussed therein).

We have changed the original screen shot only byadding a red circle to highlight the anomaly

In all the examples below, we have included screen dumps of the MIT ECG server
in order to allow people to retrieve the original data independent of us.
However, all data is also available from us in a convenient zip file.

This is KEY only, the next 8 slides show examples in this format

The annotated ECG from PhysioBank (two signals)

Anomalies (marked by redlines) found by the discord
discovery algorithm. Each of
the two traces weresearched independently.
0. 50-0. 5-1
500

1000

1500

2000

2500

3000

3500

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

1

0.5

0-0.5

4000

4500

5000

5.2
5
4.8
4.6
4.4
4.2
500

1000

1500

2000

2500

3000

3500

4000

4500

5000

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

6
5.554.54
3.5
3Each of the two traces were searched independently.

anomaly

at1795;

MITdis t

11. 0119

1. 5
10. 5
0-0. 5-101000

2000

3000

4000

5000

d0. 8
0. 6
0. 4
0. 2
0-0. 2-0. 4500

1000

1500

2000

2500

3000

3500

4000

Each of the two traces were searched independently.

4500

5000

10-1-2-3500

1000

1500

2000

2500

3000

3500

2500

3000

3500

d10-1-2-3500

1000

1500

2000

Each of the two traces were searched independently.

2.5
2
1.5
10.5
0-0.5500

1000

1500

2000

2500

3000

3500

2500

3000

3500

d0.50-0.5-1-1.5-2
500

1000

1500

2000

Each of the two traces were searched independently.

d2
1. 51
0. 50-0. 5500

1000

1500

2000

2500

3000

3500

500

1000

1500

2000

2500

3000

3500

0.6
0.4
0.2
0-0.2
-0.4

Each of the two traces were searched independently.

This is a dataset shown in a previous example

To demonstrate that the discord algorithm can find anomalies even with thepresence of linear trends, we added linear trend to the ECG data on the top. The newdata and the anomalies found are shown below. This is important in ECGs because ofthe wandering baseline effect, see Figure 11 in the paper.
543
2
10
500

1000

1500

2000

2500

3000

3500

4000

4500

5000

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

65
43
2
10

Each of the two traces were searched independently.

This example shows that the discord algorithm is not sensitive to the window size. In fact on all 8problems above, we can double or half the discord length and still find the anomalies. Below is justone example for clarity.

discord200-0. 5-1-1. 5-2-2. 5500

10

1000

y
1500

2000
d2500

3000

3500

2000

2500

30003500

2000

2500

3000

3500

2000

2500

3000

3500

Each of the two traces were searched independently.

-1-2500

1000

1500

discord100-0. 5-1-1. 5-2-2. 5
500

10

1000

1500

Each of the two traces were searched independently.

-1-2
500

1000

1500

Aiming attargetHand
above
holsterAiming attargetBrieflyswingsgun attarget,
but
does
not
aim
Actor misses
holster

Laughing and flailing hand

Hand resting at side
0100

200

300

400

500

The 2D time series was extracted from a video of an actor performing various actions with and without a replica gun. The
film strip above illustrates a typical sequence. The two time series measure the X and Y coordinates of the actors right hand.
The actor draws a replica gun from a hip mounted holster, aims it at a target, and returns it to the holster. Watching the video
we discovered that at about ten seconds into the shoot, the actor misses the holster when returning the gun. An off-camera(inaudible) remark is made, the actor looks toward the video technician, and convulses with laughter. At one point (frame450), she is literally bent double with laughter.
This is dataset ann_gun_CentroidA

Here is a longer subsection for context. Later in thispresentation we test two other algorithms on this dataset.

0200400

600

800

1000

1200

14001600

1800

2000

The next few slides demonstrate utility of discords in finding anomalies in Space Shuttle
Marotta Valve time series.
In every case, there are five examples of an Energize/De-Energize cycle. Exactly one cycle has
been annotated by a domain expert as been abnormal.
Each cycle is of length 1000, and we know in advance that an anomaly can be just a part of acycle, so we set the length of the discord to be an fraction of this (in particular, 128) for all
experiments shown here. (We note that we get correct results for all experiments here if wedouble or half this arbitrary choice.)

We tested on 3 different challenges, of increasing difficulty. Note that all the annotations
shown are those of the domain expert.

Space Shuttle Marotta Valve:
Example of a normal cycle

Energizing

De-Energizing

This is Figure 5 in the paper.
0100

200300400500

600

700

800

9001000

Test 1: A simple problem

This is dataset TEK16.txt

Poppet pulled
significantly out of
the solenoid
before energizing

Space Shuttle Marotta Valve Series

0500

1000

1500

2000

2500

3000

In this case the anomaly is very obvious, and thediscord (marked in red) easily finds it.

This is Figure 6 in the paper.

3500

4000

The DeEnergizing
phase is normal

4500

5000

Test 2: A more subtle problem
Space Shuttle Marotta Valve Series

0500

This is dataset TEK17.txt

Poppet pulled
significantly out of
the solenoid
before energizing

1000

1500

2000

2500

3000

3500

4000

4500

5000

Here the discord (marked in red) easily finds the anomaly
marked by the domain expert, but it is not obvious (at thisscale) what the anomaly was.
A zoom-in of the anomaly, and the 4 corresponding
segments from the normal cycle (left), explains what thediscord discovered. Only the anomalous cycle has a“double hump”.
These are from Figures 7 and 8 in the paper.
050

100

150

Poppet pulled out of thesolenoid before
energizing

Corresponding
section ofother cycles

Discord

Discord
1500

2000

2500

050100Test 3: Finding multiple discords
Jammedpoppet

0.645

Slower recovery
beforeDe-Energizingphase

3.528
0.595

0.669

0.979

0500

1000

1500

2000

2500

3000

3500

4000

4500

5000

In this example we consider the problem of knowing when
an discord is significant.
We found the top 12 discords (only 6 are shown above forclarity). The top 2 correspond to true anomalies, in red wesee a missing small peak before the large plateau, and ingreen we see a slower recovery before the de-energizing
phase. The next 4 discords are shown in pink.

4

True anomalies

3Distance

Space Shuttle
Marotta ValveSeries

2.594

If we plot the discords scores against K (left) we can seethat we could potentially assess the significance of andiscord with some kind of “knee finding” algorithm.

Normal sequences

21This example was not in the paper.

002

46k

8

1012

The next 6 slides are larger versions of the examples shown in the paper.

Premature ventricular contraction

02000

Supraventricular escape beat

4000

6000

3-discord, d = 18.9361, location = 4017

8000

Premature ventricular contraction

10000

2-discord, d = 21.7285, location = 10014

12000

14000

16000

1-discord, d = 25.0896, location = 10871The time series is record mitdb/x_mitdb/x_108 from the PhysioNet Web Server (The local copy in the UCR archive iscalled mitdbx_mitdbx_108.txt). It is a two feature time series, here we are looking at just the MLII column.
Cardiologists from MIT have annotated the time series, here we have added colored makers to draw attention to thoseannotations.
Here we show the results of finding the top 3 discords on this dataset. We chose a length of 600, because this a little longer
than the average length of a single heartbeat.

1st Discord

3rd Discord

This is Figure 12 in the paper.

2nd Discord

MIT-BIH Arrhythmia Database: Record 108r0S
5000

10000

r
15000

This is part of Record qtdbsele0606from the PhysioBank QT Database (qtdb)(the local copy inthe UCR archive is called qtdbsele0606.txt )A cardiologist noted subtle anomalies in this dataset. Let us see if the discord algorithm can find them.

-3-4-5-6-7

0

500

1000

1500

2000

2500

-3.5
ST Wave-4-4.5

How was the discord able to find thisvery subtle Premature ventricular
contraction? Note that in the normalheartbeats, the ST wave increases
monotonically, it is only in thePremature ventricular contractions that
there is an inflection.NB, this is notnecessary true for all ECGS-5-5.5-6-6.5 050

100

150

200

250

300

350

400

450500

The time taken was 0.3% of the time for brute force
This is figures 12/13 in the paper.
R23T

P

1
Q
S

4

r
900

1000

1100

1200

Discord

The is file chfdbchf15.txt

BIDMC Congestive Heart Failure Database: Record 15

r0500010000

The time taken was 0.047% of the time for brute force
This is Figure 11 in the paper.

15000

Shallow breaths as waking cycle begins

Stage II sleep
0Eyes closed, awake or stage I sleep

500

1000

Eyes open, awake

1500

2000

A time series showing a patients respiration (measured by thoraxextension), as they wake up. A medical expert, Dr. J. Rittweger, manuallysegmented the data. The 1-discord is a very obvious deep breath taken as
the patient opened their eyes. The 2-discord is much more subtle andimpossible to see at this scale. A zoom-in suggests that Dr. J. Rittweger
noticed a few shallow breaths that indicated the transition of sleepingstages.

Institute for Physiology. Free University of Berlin.
Data shows respiration (thorax extension), sampling rate 10 Hz.
This is Figure 9 in the paper.

This is dataset nprs44
Beginning at 15500
Ending at 22000
The beginning and ending points were chosen forvisual clarity (given the small plot size) they do
not effect the results

Awake Stage I sleep

Stage II sleep
0500

1000

1500

2000

Eyes Closed

2500

3000

3500

4000

A time series showing a patients respiration(measured by thorax extension), as they wakeup. A medical expert, Dr. J. Rittweger,
manually segmented the data.

Institute for Physiology.Free University of Berlin.
Data shows respiration (thorax extension), sampling rate
10 Hz.
This is Figure 10 in the paper.

This is dataset nprs43
Beginning at 1
Ending at 4000
The beginning and ending points were chosen forvisual clarity (given the small plot size) they do
not effect the results

2500

One years power demand at a Dutch research facility

2000

4.826

1500

1000

4.3511

4.56

4x 10
500

0

0.5

1

1.5

2

2.5

Ascension Thursday

SundaySaturdayFridayThursdayednesdayWTuesdayM
onday

Liberation Day

Dec 25Sunday100200300

400500

3.5

New years eve 1997

New years day 1997

03600700

Typical Week from the Dutch Power
Demand Dataset

Good Friday
Easter Sunday

0100

200300400500This is dataset power_data
This is Figure 15 from the paper. Many more details about thisdataset are available in this paper:van Wijk J. J. and van Selow E. R. Cluster and calendarbased visualization oftime series data. In Proc. IEEE Symposium on Information Visualization,pages 4-9, Oct. 25-26, 1999.

6007004Comparisons to other techniques
As we noted in the paper, any comparisons we could do to other techniques are probably unfair to therival methods.
This is because discords only require a single parameter, and as we have seen above, we can typical
double or half this parameter without effecting the results.
In contrast, most other anomaly detection schemes require require 3 to 7 parameters , including someparameters for which we may have poor intuition, such as Embedding dimension, Kernel function,
SOM topology or number of Parzen windows.
Nevertheless, comparisons to rival methods are a cornerstone of science, and we have shown someof the results below. We selected the experiments where the rival techniques did the best. While weactually did comparisons to the 4 techniques listed in [1], we only show two of these in the experiments
below. These two techniques were chosen because they each have at least 20 references and eachperformed reasonably well on at least one dataset.
The two rival techniques are:
• Immunology (IMM) inspired approach (5 parameters) [2].
• TSA-tree Wavelet based approach (3 parameters) [3].
For each rival technique, for each experiment, we spent one hour of human time searching for the bestparameters.
[1] Keogh, E., Lonardi, S. and Ratanamahatana, C. (2004). Towards Parameter-Free Data Mining. In proceedings of the tenth ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining. Seattle, WA, Aug 22-25, 2004.
[2] D. Dasgupta and S. Forrest, Novelty Detection in Time Series Data Using Ideas from Immunology Proceedings of the 5th International
Conference on Intelligent Systems, Reno, June, 1996
[3] C. Shahabi, X. Tian. & W. Zhao. TSA-tree: a wavelet-based approach to improve the efficiency of multi-level surprise and trend queries. InProc. of 12th Int'l Conf. on Scientific and Statistical Database Management. pp 55-68, 2000.

The training data used by IMM only
(The first 1,000 data points of chfdbchf15)

The anomaly
The test data (from 1,0001
to 3000 of dataset of chfdbchf15)

discord discovery

500

1000

1500

thisexperiment,experiment,we
weInInthis
cansaysaythatthatallallthethecanalgorithmsfind
findthethealgorithms
anomaly.The
TheIMMIMM
anomaly.
approachhashasaaslightlyslightly
approachhigherpeak
peakvalue
valuejust
just
IMM higher
afterthetheanomaly,
anomaly,but
but
after
thatmay
maysimply
simplyreflectreflectthattheslight
slightdiscretization
discretization
theTSA-tree ofofthe
thetimetimeaxis.
axis.
thenext
nextslide,slide,weweInIntheconsidermore
moreofofthe
theconsider
time series…
2000 time series…

The training data used by IMM only
(The first 1,000 data points of chfdbchf15)

The anomaly

The test data (from 1,001 to15,000 of dataset of chfdbchf15)

Wecan
canseeseehereherethat
thatthetheIMMIMMapproach
approachhashasWemanyfalse
falsepositives,positives,ininspite
spiteofofvery
verycareful
carefulmanyparametertuning.
tuning.ItItsimply
simplycannot
cannothandle
handleparameter
complexdatasets.
datasets.
complex
Boththetheotherotheralgorithms
algorithmsdo
dowellwellhere.
here.
Both
Notethat
thatthis
thisproblem
problemisisininFigure
Figure1111ininpaper
paper
Note

discorddiscovery

IMM

TSA-tree

05000

10000

15000

The training data used by IMM only
(The first 700 data points of qtdbsele0606)

The test data(from 701 to 3,000 ofdataset ofqtdbsele0606)

Thisexample
exampleisisFigure
Figure12/13
12/13ininthe
theThispaper.
paper.
Recallthat
thatwewediscussed
discussedthis
this
Recallexampleabove,above,ititisisinteresting
interesting
examplebecausethe
theanomaly
anomalyisisextremely
extremely
becausesubtle.
subtle.
Hereonly
onlythethediscord
discorddiscovery
discovery
Herealgorithmcan
canfindfindthetheanomaly.
anomaly.
algorithm

The anomaly
discorddiscovery
IMM
TSA-tree
0500

1000

1500

2000

R

2500

23
T

P

1Q
S

4r
900

1000

1100

1200

Discord

How was the discord able to find this very subtle
Premature ventricular contraction? Note that in thenormal heartbeats, the ST wave increases
monotonically, it is only in the Premature
ventricular contractions that there is an
inflection.NB, this is not necessary true for all ECGSThe training data used by IMM only
4 normal cycles of Space Shuttle Marotta Valve Series

Poppet pulled
significantly out of thesolenoid before
energizing

The test data
TEK17.txt

Space Shuttle Marotta Valve Series

Thisexample
exampleisisFigure
Figure7/8
7/8ininthe
theThispaper.
paper.

discorddiscovery

Herethetheanomaly
anomalyvery
verysubtle.
subtle.
HereOnlythethediscord
discorddiscovery
discoveryalgorithm
algorithm
Only
canfindfindthetheanomaly.
anomaly.
canIMM
TSA-tree
0500

1000

1500

2000

2500

3000

3500

4000

4500

A reminder of the cause of the anomaly

5000

Poppet pulled out of thesolenoid before
energizing

Corresponding
section ofother cycles

Discord

Discord
1500

2000

2500

050

100

The training data used by IMM only
3 normal cycles of gun draw.

The test data
the first 13 cycles ofann_gun_CentroidA

discorddiscovery

Thisexample
exampleisisnot
notininthe
thepaper,paper,thetheThis
causeofofthe
the“anomaly”“anomaly”isisexplained
explained
cause
above
above
Onlythethediscord
discorddiscovery
discoveryalgorithm
algorithm
Only
canfindfindthetheanomaly.
anomaly.
canIMM
TSA-tree
0200

400

600

800

1000

1200

1400

1600

1800

2000

Recall that we have seen this example before…

Aiming attargetAiming attargetHand
above
holster

Briefly swings
gun at target,
but does notaim

Hand resting at side
0100

200

Actor misses holster
300

Laughing and flailing hand
400500Below are some larger versions of figures from the paper, for reference.

This is figure 1 from the paper

ECG qtdb/sel102 (excerpt)
0200

400

600

800

1000

1200

1400

Raw time series

0500

1000

1500

2000

2500

This is figure 4 fromthe paper

Subsequence extracted
C1
Converted to SAX^
C1caa
Inserted into array
1caa

Augmented Trie

3cb2cab1c3caa3b::

::

::

::

::

::

::

::

::

::

((m – n)) -1cbb2((m – n)acb1aacb9(m – n) -1acbc77a2
1

3731cb((m – n)) +1bca2cac

23 (m – n)+1