Is negative selection appropriate for anomaly detection?

ABSTRACT

Negative selection algorithms for hamming and real-valued shape-spaces are reviewed. Problems are identified with the use of these shape-spaces, and the negative selection algorithm in general, when applied to anomaly detection. A straightforward self detector classification principle is proposed and its classification performance is compared to a real-valued negative selection algorithm and to a one-class support vector machine. Earlier work suggests that real-value negative selection requires a single class to learn from. The investigations presented in this paper reveal, however, that when applied to anomaly detection, the real-valued negative selection and self detector classification techniques require positive and negative examples to achieve a high classification accuracy. Whereas, one-class SVMs only require examples from a single class.

REFERENCES

• 1: M. Ayara, J. Timmis, L. de Lemos, R. de Castro, and R. Duncan. Negative selection: How to generate detectors. In 1st Int. Conf. on Artificial Immune Systems, pages 89--98, September 2002.
• 2: Justin Balthrop , Fernando Esponda , Stephanie Forrest , Matthew Glickman, Coverage and Generalization in an Artificial Immune System, Proceedings of the Genetic and Evolutionary Computation Conference, p.3-10, July 09-13, 2002
• 3: C.-C. Chang and C.-J. Lin. LIBSVM: a Library for Support Vector Machines (http://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf), December 2004.
• 4: D. Dasgupta, S. Forrest. Novelty Detection in Time Series Data Using Ideas from Immunology. In Proc. of the 5th Int. Conf. on Intelligent Systems. IEEE Computer Society Press, 1996.
• 5: D. G. Osmond. The turn-over of B-cell populations. Immunology Today, 14(1):34--37, 1993.
• 6: Leandro R. de Castro , Jonathan Timmis, Artificial Immune Systems: A New Computational Intelligence Paradigm, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 7: Patrik D'haeseleer, An Immunological Approach to Change Detection: Theoretical Results, Proceedings of the Ninth IEEE Computer Security Foundations Workshop, p.18, March 10-12, 1996
• 8: Elad Yom-Tov. An Introduction to Pattern Classification. In Advanced Lectures on Machine Learning, volume 3176 of LNCS, pages 1--20. Springer-Verlag, 2004.
• 9: F. Esponda, S. Forrest, and P. Helman. A formal framework for positive and negative detection schemes. IEEE Transactions on Systems, Man and Cybernetics Part B: Cybernetics, 34(1):357--373, 2004.
• 10: T. Fawcett. ROC graphs: Notes and practical considerations for data mining researchers. Technical Report HPL-2003-4, Hewlett Packard Laboratories, Jan. 17 2003.
• 11: A. Freitas and J. Timmis. Revisiting the Foundations of Artificial Immune Systems: A Problem Oriented Perspective. In Proc. of the 2nd Int. Conf. on Artificial Immune Systems, volume 2787 of LNCS, pages 229--241. Springer, September 2003.
• 12: F. González, D. Dasgupta, and G. Gomez. The effect of binary matching rules in negative selection. In Genetic and Evolutionary Computation -- GECCO-2003, volume 2723 of LNCS, pages 195--206, Chicago, 12-16 July 2003. Springer-Verlag.
• 13: F. González, D. Dasgupta, and R. Kozma. Combining negative selection and classification techniques for anomaly detection. In Congress on Evolutionary Computation, pages 705--710. IEEE, May 2002.
• 14: F. A. González, D. Dasgupta, and L. F. Niño. A Randomized Real-Valued Negative Selection Algorithm. In Proc. of the 2nd Int. Conf. on Artificial Immune Systems (ICARIS), volume 2787 of LNCS, pages 261--272, Edinburgh, UK, 2003. Springer-Verlag.
• 15: S. A. Hofmeyer. An Interpretative Introduction to the Immune System, 2000.
• 16: C.-W. Hsu, C.-C. Chang, and C.-J. Lin. A Pratical Guide to Support Vector Classification (http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf), July 2003.
• 17: C. A. Janeway, P. Travers, M. Walport, and M. Shlomchik. Immunologie. Spektrum Akademischer Verlag, 2002.
• 18: Z. Ji and D. Dasgupta. Real-valued negative selection algorithm with variable-sized detectors. In Genetic and Evolutionary Computation -- GECCO-2004, Part I, volume 3102 of LNCS, pages 287--298, Seattle, WA, USA, 26-30 June 2004. Springer-Verlag.
• 19: K.-R. Müller, S. Mika, G. Ratsch, K. Tsuda, and B. Schölkopf. An Introduction to Kernel-Based Learning Algorithms. Transactions on Neural Networks, 12(2):181--201, 2001.
• 20: J. K. Percus, O. E. Percus, and A. S. Perelson. Predicting the Size of the T-Cell Receptor and Antibody Combining Region from Consideration of Efficient Self-Nonself Discrimination. Proc. of National Academy of Sciences USA, 90:1691--1695, 1993.
• 21: A. S. Perelson and G. Oster. Theoretical studies of clonal selection: minimal antibody repertoire size and reliability of self-nonself discrimination. In J. Theor. Biol., volume 81, pages 645--670, 1979.
• 22: Stephanie Forrest , Alan S. Perelson , Lawrence Allen , Rajesh Cherukuri, Self-Nonself Discrimination in a Computer, Proceedings of the 1994 IEEE Symposium on Security and Privacy, p.202, May 16-18, 1994
• 23: B. Schölkopf. Statistical learning and kernel methods. Technical Report MSR-TR-2000-23, Microsoft Research (MSR), Feb. 2000.
• 24: B. Schölkopf, J. C. Platt, S.-T. Shawe-Taylor, A. J. Smola, and W. Williamson. Estimating the support of a high-dimensional distribution. Technical Report MSR-TR-99-87, Microsoft Research (MSR), Nov. 1999.
• 25: A. Secker, A. A. Freitas, and J. Timmis. AISEC: An artificial immune system for e-mail classification. In Proc. of the 2003 Congress on Evolutionary Computation CEC2003, pages 131--138, Canberra, 8-12 Dec. 2003. IEEE Press.
• 26: T. Stibor, K. M. Bayarou, and C. Eckert. An investigation of R-chunk detector generation on higher alphabets. In Genetic and Evolutionary Computation -- GECCO-2004, Part I, volume 3102 of LNCS, pages 299--307, Seattle, WA, USA, 26-30 June 2004. Springer-Verlag.
• 27: P. Vlachos. StatLib. http://lib.stat.cmu.edu.
• 28: A. Watkins and L. Boggess. A new classifier based on resource limited artificial immune systems. In Proc. of the 2002 Congress on Evolutionary Computation CEC2002, pages 1546--1551. IEEE Press, 2002.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Pattern analysis

General Terms:
Algorithms

Keywords:
anomaly detection, artificial immune systems, negative selection, one-class SVM, positive selection