On the distance norms for detecting anomalies in multidimensional datasets

• Autorzy: Chmielewski A. , Wierzchoń S. T.

Warianty tytułu

PL

O metrykach odległości dla wielowymiarowych zbiorów danych wykorzystywanych w algorytmie selekcji negatywnej o wartościach rzeczywistych

• Języki publikacji: EN

Abstrakty

EN

One of the key parameters of algorithms for anomaly detection is the metric (norm) applied to calculate the distance between every two samples which reflect its proximity. It is especially important when we operate on real-valued high dimensional datasets, i.e. when we deal with the problem of intruders detection in computer networks. As observed, the most popular Euclidean norm becomes meaningless in higher than 15-dimensional space. This means that other norms should be investigated to improve the effectiveness of real-valued negative selection algorithms. In this paper we present results for the following norms: Minkowski, fractional distance and cosine.

PL

Jednym z kluczowych parametrów algorytmów wykrywania anomalii jest metryka (norma) służąca do obliczania odległości pomiędzy dwiema próbkami, która odzwierciedla ich podobieństwo. Jest ona szczególnie istotna w przypadkach operowania na zbiorach o wielu wymiarach takich, z jakimi mamy do czynienia w przypadku wykrywania intruzów w sieciach komputerowych. Zaobserwowano, że najczęściej stosowana norma euklidesowa staje się bezużyteczna w przestrzeniach o wymiarach większych niż 15. Oznacza to konieczność stosowania innych norm, które pozwoliłyby na zwiększenie skuteczności algorytmu selekcji negatywnej o wartościach rzeczywistych. W artykule prezentujemy wyniki uzyskane dla normy Minkowskiego, Lm, przy zmianach parametru m w zakresie (0, 2] oraz dla odległości kosinusowej.

Słowa kluczowe

EN

negative selection; anomaly detection; Minkowski norm; fractional distance metric

PL

selekcja negatywna; wykrywanie anomalii; norma Minkowskiego z ułamkowym wykładnikiem; odległość kosinusowa

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2007
• Tom: Z. 2
• Strony: 39--49
• Opis fizyczny: Bibliogr. 14 poz., rys., wykr.

Twórcy

autor

Chmielewski A.

autor

Wierzchoń S. T.

• Bialystok Technical University, Faculty of Computer Science

Bibliografia

• [I] Aggarwal C, Hinneburg A., Keim D.A., On the surprising behavior of distance metrics in high dimensional space, In Proc. of the 8th InternationalConference on Database Theory, ICDT 2001, London, pp. 420-434.
• [2] Beyer, K., Goldstein, J., Ramakrishnan, R., Shaft, U. When is „nearest neighbor" meaningful, In Proc. of the 7th ICDT, LNCS 1540, Springer 1999, pp. 217-235.
• [3] Chmielewski A., Wierzchoń S. T., Badanie przydatności algorytmu generującego V-detektory do klasyfikacji wybranych zbiorów, Inżynieria wiedzy i systemy ekspertowe. T.l, Wrocław (Poland), 2006, pp. 13-22.
• [4] Chmielewski A., Wierzchoń S. T., Comparing real-valued negative selection algorithms for intrusion detection applications, In Proc. of the 13th International Multi-Conference, Advanced Computer Systems (ACS2006), Vol. 1, Międzyzdroje (Poland), 2006, pp. 387-395.
• [5] Chmielewski A., Wierzchoń S.T., V-Detector algorithm with tree-based structures, In Proc. of the International Multiconference on Computer Science and Information Technology, Wisła (Poland), 2006, pp. 9-14.
• [6] Forrest S., Perelson A., Allen L., Cherukuri R., Self-nonself discrimination in a computer. In Proceedings IEEE Symposium on Research in Security and Privacy, Los Alamitos, CA, 1994. IEEE Computer Soc. Press, pp. 202-212.
• [7] Gonzalez F., Dasgupta D., Nino L.F., A randomized real-valued negative selection algorithm. In: J. Timmis, P.J. Bentley, E. Hart, eds., Proceedings of the 2nd International Conference on Artificial Immune Systems (ICARIS-2003), LNCS 2787, Springer-Verlag, 2003, pp. 261-272.
• [8] Hettich S., Bay S. D., KDD Cup 1999 Data (1999), http://kdd.ics.uci.edu.
• [9] Ji Z., Dasgupta D., Real-valued negative selection algorithm with variable-sized detectors, In Genetic and Evolutionary Computation GECCO-2004, Seattle (USA), Part I. LNCS 3102, Springer-Verlag, 2004, pp. 287-298.
• [10] Stibor, T., J. Timmis und C. Eckert: On the use of hyperspheres in artificial immune systems as antibody recognition regions, In Proc. of the 5th International Conference on Artificial Immune Systems (ICARIS-2006), LNCS, Springer-Verlag, Oeiras (Portugal), 2006, pp. 215-228.
• [11] Stibor, Thomas, Jonathan Timmis und Claudia Eckert: A comparative study of real-valued negative selection to statistical anomaly detection techniąues, In Proc. of the 4th International Conference on Artificial Immune Systems(ICARIS-2005), Banff (Canada), LNCS, Springer, Berlin/Heidelberg, 2005, pp. 262-275.
• [12] Wierzchoń S.T., Deriving concise description of non-self patterns in an artificial immune system, In L. C. Jain, J. Kacprzyk, eds., New Learning Paradigms in Soft Computing, Physica-Verlag 2001, pp. 438-458.
• [13] Wierzchoń S.T. Sztuczne systemy immunologiczne. Teoria i zastosowania. Akademicka Oficyna Wydawnicza ELIT, Warszawa 2001.
• [14] Weber R., Schek H.-J., Blott S„ A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces, In Proc. of VLDB Conference, 1998.