Information Technology Reference
In-Depth Information
of
r
-chunk detectors, but
not
recognized with any set of
r
-contiguous detectors.
We demonstrate this converse statement on an example, a formal approach is
provided in [14].
Example 2.
Given a Hamming shape-space
U
{
0
,
1
}
5
,aset
S
=
{
01011
,
01100
,
01110
,
10010
,
10100
,
11100
}
of self elements and a detector
length
r
=3.
All possible generable
r
-contiguous detectors for the complementary space
U
{
0
,
1
}
5
\
S
are
D
r−contiguous
=
{
00000
,
00001
,
00111
,
11000
,
11001
}
.
All possible generable
r
-chunk detectors are
D
r−chunk
=
{
0
|
000
,
0
|
001
,
0
|
110
,
1
|
000
,
1
|
011
,
1
|
100
,
2
|
000
,
2
|
001
,
2
|
101
,
2
|
111
}
.
The set
D
r−contiguous
recognizes the elements
P
1
=
U
{
0
,
1
}
\
(
S
∪{
01010
,
01101
,
10011
,
10101
,
11101
,
11110
}
),
5
whereas the set
D
r−chunk
recognizes the elements
P
2
=
U
{
0
,
1
}
5
\
(
S
∪{
10011
,
01010
,
11110
}
). Hence
|P
1
|≤|P
2
|
.
Example 2 shows, that the set of
r
-chunk detectors
D
r−chunk
recognizes more
elements of
U
{
0
,
1
5
than the set of
r
-contiguous detectors
D
r−contiguous
and there-
fore the
r
-chunk matching rule subsumes the
r
-contiguous rule.
3
Hamming Negative Selection
Forrest et al. [1] proposed a (generic
2
) negative selection algorithm for detecting
changes in data streams. Given a shape-space
U
=
S
seen
∪
S
unseen
∪
N
which
is partitioned into training data
S
seen
and testing data (
S
seen
∪
N
).
The basic idea is to generate a number of detectors for the complementary space
U
S
unseen
∪
S
seen
and then to apply these detectors to classify new (unseen) data as self
(no data manipulation) or non-self (data manipulation).
\
Algorithm 1.
Generic Negative Selection Algorithm
input
:
S
seen
= set of self seen elements
output
:
D
= set of generated detectors
begin
1
.
Define self as a set
S
seen
of elements in shape-space
U
2
.
Generate a set
D
of detectors, such that each fails to match any element in
S
seen
3
.
Monitor (seen and unseen) data
δ ⊆ U
by continually matching the
detectors in D against
δ
.
end
The generic negative selection algorithm can be used with arbitrary shape-
spaces and anity functions. In this paper, we focus on Hamming negative
2
Applicable to arbitrary shape-spaces.
