Negative selection algorithms on strings with efficient training and linear-time classification

Michael Elberfeld, Johannes Textor*

*Korrespondierende/r Autor/-in für diese Arbeit
17 Zitate (Scopus)


A string-based negative selection algorithm is an immune-inspired classifier that infers a partitioning of a string space Σℓ into "normal" and "anomalous" partitions from a training set S containing only samples from the "normal" partition. The algorithm generates a set of patterns, called "detectors", to cover regions of the string space containing none of the training samples. Strings that match at least one of these detectors are then classified as "anomalous". A major problem with existing implementations of this approach is that the detector generating step needs exponential time in the worst case. Here we show that for the two most widely used kinds of detectors, the r-chunk and r-contiguous detectors based on partial matching to substrings of length r, negative selection can be implemented more efficiently by avoiding generating detectors altogether: for each detector type, training set S⊆Σℓ and parameter r≤ℓ one can construct an automaton whose acceptance behaviour is equivalent to the algorithm's classification outcome. The resulting runtime is O(|S|ℓr|Σ|) for constructing the automaton in the training phase and O(ℓ) for classifying a string.

ZeitschriftTheoretical Computer Science
Seiten (von - bis)534-542
PublikationsstatusVeröffentlicht - 16.02.2011


Untersuchen Sie die Forschungsthemen von „Negative selection algorithms on strings with efficient training and linear-time classification“. Zusammen bilden sie einen einzigartigen Fingerprint.