CLASSIFICATION AND DETECTION OF ABNORMAL EVENTS IN TIME SERIES OF GRAPHS - Data Mining in Time Series Databases - page 139

filter is widely used for removing impulsive noise. A median filter is com-
puted by sliding a window of length

L

over data values in a time series.
At each step the output to this process is the median of values within
the window. This process is also termed the running median [35]. In the
following we discuss four different approaches to abnormal change detec-
tion that utilise median filters. All these approaches assume that a time
series of graphs ( ) is given. The median graph of a

subsequence of these graphs can be computed using either graph distance
measure

G 1 ,...,G n ,G n +1 ,...

d 1 or d 2 .

6.1. M edian vs. S ingle Graph, A djacent in Time (msa)
Given the time series of graphs, we compute the median graph in a window
of length

is a parameter that is to be specified by the user
dependent on the underlying application. Let

L ,where L

˜

G n bethemedianofthe

( ˜ sequence ( G n ,G n +1 ) can be used to measure

abnormal change. We classify the change between

G n−L +1 ,...,G n ). Then d

G n and G n +1 as abnormal

( ˜ if d G n ,G n +1 ) is larger than some threshold.

Increased robustness can be expected if we take the average deviation

ϕ , of graphs ( G n−L +1 ,...,G n ) into account. We compute

n

1
L

( ˜

ϕ d G n ,G i )

= (6.1)

i = n−L +1

and classify the change between G n and G n +1 abnormal if

( ˜

d G n ,G n +1 ) ≥ αϕ

(6.2)

where is a parameter that needs to be determined from examples of

normal and abnormal change. Note that the median

α

˜

G n is,bydefinition,a

graph that minimises in Eq. (6.1).

In Section 5 it was pointed out that

ϕ

˜

G n is not necessarily unique. If

˜ ˜ ˜

several instances of G n exist, one can apply Eqs. (6.1)

and (6.2) on all of them. This will result in a series of values

G n 1 ,..., G n 1 of

ϕ 1 ,...,ϕ 1

( ˜ ( ˜

and a series of values G n 1 ,G n +1 ). Under a conservative

scheme, an abnormal change will be reported if

d G n 1 ,G n +1 ) ,...,d

( ˜

d G n 1 ,G n− 1 ) ≥ αϕ 1 ∧···∧

( ˜

d ≥ αϕ t .

By contrast a more sensitive change detector is obtained if a change is
reported as soon as there exists at least one

G n t ,G n +1 )

i for which

( ˜ d G n i ,G n +1 ) ≥ αϕ i , 1 ≤ i ≤ t.