Information Technology Reference
In-Depth Information
Theoretical Basis of Novelty Detection in Time Series
Using Negative Selection Algorithms
Rafał Pasek
Wrocław University of Technology, 27 Wybrzeże Wyspiańskiego 50-370 Wrocław, Poland
rafal.pasek@pwr.wroc.pl
Abstract.
Theoretical basis of Novelty Detection in Time Series and its relation-
ships with State Space Reconstruction are discussed. It is shown that the
methods for estimation of optimal state-space reconstruction parameters may be
used for the estimation of immunological novelty detection system's para-
meters. This is illustrated with a V-detector system detecting novelties in
Mackey-Glass time series.
1 Introduction
Novelty Detection in Time Series (NDinTS) problem is a time-sensitive version of a
general Novelty Detection (ND) problem known also as Anomaly Detection. Many
different formulations of this problem exist in the literature, including both the time-
sensitive [10, 11] and time-insensitive version [6, 14]. They all have three common
elements: (1) problem space, with the finite or infinite number of elements; (2) input
data, which is a set of elements that belongs to the normal class; (3) result, which is a
mapping that classifies all elements as normal or novel. Therefore, Anomaly
Detection can be seen as a two-class classification problem, in which only the
examples from one class are available for the training [6]. The typical solution relies
on the model of known normal data, a distance measure and a threshold value to
decide whether the element is normal or novel. A wide review of existing approaches
can be found in [1].
The problem of Novelty Detection in Time Series was also approached using the
Artificial Immune Systems based on the Negative Selection Algorithm (NSA). This
approach, as many others, utilizes the sliding window procedure [10, 11, 12, 14, 15,
16, 19] to reduce the problem to a time-insensitive variant. Theoretical analysis of this
procedure shows, that it is an equivalent to the Method of Delays (MOD) - a well
known procedure in the domain of system's dynamics reconstruction. It is then
possible to find sliding window's parameters using existing methods for estimation of
optimal reconstruction parameters.
The rest of this paper is organized as follows. In section 2 the formal definitions of
Novelty Detection and its time-sensitive variant are introduced and also the NSA based
approach and sliding window procedure are defined. Section 3 is a short introduction
to the analysis of dynamical systems and state space reconstruction. Basing on this it is
