Theoretical Basis of Novelty Detection in Time Series Using Negative Selection Algorithms - Artificial Immune Systems - page 379

From the Condition 1 we have P NDS*- = P - , but S ⊆ P - , so the following is an essential

condition for a perfect novelty detection system:

Cond. 2. P NDS*- ⊇ S

It is then clear that the perfect novelty detection system requires P NDS*- to be a
superset 3 , of the given set of normal elements S . In general the separation of P
resulting form classify and classify_est mappings are not identical. Two types of
classification errors can be identified: type 1 - false positives and type 2 - false
negatives. They are expressed by two factors, error_rate ( also known as
false_alarm_rate ) and reject_rate defined as follows: error_rate = FN/TP+FN;
reject_rate = FP/TN+FP, where:
FP is the number of elements e for which: classify(e)=normal

∧ classify_est(e)=novel

FN is the number of elements e for which: classify(e)=novel classify_est(e)=normal

TP is the number of elements e for which: classify(e)= classify_est(e)= normal
TN is the number of elements e for which: classify(e)= classify_est(e)= novel
To compare any two detection systems ROC curves are commonly used. They
present the effect error_rate on reject_rate or the effect of false alarm rate on
detection_rate=1-reject_rate .

∧

2.3 Immunological Approach to ND

Artificial Immune Systems (AIS) follows the paradigm of natural immune system
(NIS) [13] which works as a natural self - non-self discrimination system. Therefore
Novelty Detection is one of the major areas of AIS application [17]. There were also
few attempts to apply them to a NDinTS problem [10, 11, 12, 14, 15, 16, 19]. Of a
special interest are the systems based on a Negative Selection Algorithm (NSA),
proposed in the first, so called naïve version by Forrest et al. in [9].
The NSA based immunological novelty detection systems use the negative
characterization scheme, which means that the model M is focused on representing
not the input data S itself, but its complement. Due to the imperfect nature of model
the two approaches are not equivalent [4]. A comprehensive analytical comparison of
positive and negative characterization schemes may be found in [4, 5], for
experimental comparisons see [15, 47]. There is a dispute whether the negative
characterization is a proper approach to AD/ND [17]. It is being criticized in [2, 47,
48]. The major drawbacks mentioned are high dependability on parameters values and
high computational cost. In [3] a response to these charges is given with the
suggestion that choosing proper values of parameters reduce the computational
complexity to linear.
Leaving this dispute apart in the rest of this work the negative characterization
based immunological system is discussed. The complement of input data set S is
modeled with a set of so called detectors.

Def. 14. An immunological model M IMM is a set D of detectors:
M IMM = df D, where D = df {d 1 , d 2 ,…, d k }

3 This superset can be regarded as a generalization of S .