Algorytm minimalnego drzewa rozpinającego w zastosowaniu do budowy efektywnego lasu izolacji dla detekcji anomalii
Type
Thesis
Subtype
Doctoral thesis
Authors/Creators
Promoter
Karczmarek, Paweł
Additional promoter
Dolecki, Michał
PBN affiliation
information and communication technology
Date
2024
Abstract PL
Niniejsza dysertacja wprowadza innowacyjne algorytmy detekcji anomalii, oparte na metodzie Isolation Forest (lasu izolacji, IF). Rozprawa rozpoczyna się przedstawieniem zarysu problematyki detekcji anomalii, obejmującym przegląd ogólnych metod stosowanych w tym obszarze. W dalszej części pracy szczegółowo omówiona została metoda IF, wraz z kluczowymi koncepcjami niezbędnymi przy implementacji nowych technik. Przeanalizowano opracowania dotyczące modyfikacji metody IF. W ramach tego przeglądu, szczególny nacisk położono na te publikacje, które koncentrują się na ulepszeniach i rozszerzeniach bazowej metody IF. Rozprawa obejmuje wprowadzenie pięciu nowych algorytmów detekcji anomalii. Wśród nich znajdują się dwie metody redukcji atrybutów, stosowane w procesie przygotowania danych, oparte na technikach grupowania: metodzie 𝑘-średnich oraz grupowaniu rozmytym
Fuzzy C-Means. Ponadto, opracowano metodę, która usprawnia wybór wartości atrybutu w węzłach izolacji, wykorzystując zoptymalizowany algorytm grupowania, bazujący na minimalnym drzewie rozpinającym. W ramach kolejnych dwu metod, wprowadzone zostały nowatorskie rozwiązania w konstrukcji drzew izolacji, polegające na izolacji elementów poprzez ich scalanie algorytmem minimalnego drzewa rozpinającego. Nowo wprowadzone drzewa izolacji charakteryzują się dwoma składnikami oceny anomalności: jednym związany z poziomem elementu w drzewie izolacji oraz drugim związanym z odległością elementu od najbliższego węzła liścia. Pierwsza z wymienionych metod wykorzystuje funkcję oceny, stosując sumowanie wprowadzonych składników oceny anomalności. Natomiast druga technika wprowadza integrację znormalizowanych składników oceny anomalności z wykorzystaniem bloku reguł rozmytych w modelu wnioskowania Takagi-Sugeno. Przeprowadzono wyczerpującą serię eksperymentów nowo zaproponowanych podejść, mającą na celu ocenę algorytmów oraz ich porównanie z istniejącymi technikami konkurencyjnymi. Badania objęły 26 rzeczywistych zbiorów danych. Zmierzone zostały miary jakości klasyfikacji niezależne od doboru progu detekcji, takie jak pole powierzchni pod krzywą charakterystyki operacyjnej odbiornika oraz pole powierzchni pod krzywą precyzji-czułości. Dodatkowo dla metod wyznaczono optymalne wartości progu detekcji oraz obliczono wartości miar zależnych od doboru tego progu, tj. dokładność, precyzja, czułość, swoistość, częstość fałszywych alarmów oraz miara F1. Wyniki tych badań jednoznacznie potwierdzają, że nowo wprowadzone rozwiązania charakteryzują się wysoką skutecznością. Ponadto, analizie poddano również inne charakterystyki, w tym czasy reakcji algorytmów dla fazy treningowej i fazy oceny, oraz dokonano dogłębnej analizy hiperparametrów. Dostosowanie hiperparametrów metod pozwoliło na zidentyfikowanie możliwości ich modyfikacji, tak aby zoptymalizować działanie algorytmów z myślą o konkretnych zadaniach. W ramach demonstracji skuteczności nowych podejść w separacji próbek anomalnych i normalnych przedstawiono graficzną reprezentację separowalności, wykorzystując znormalizowane wartości funkcji oceny poszczególnych algorytmów. W celu wizualizacji charakterystyk nowo opracowanych algorytmów przygotowano cztery sztucznie wygenerowane, osadzone w przestrzeni dwuwymiarowej zbiory danych. Opracowano mapy cieplne odzwierciedlające wartości funkcji oceny, zarówno dla pojedynczych drzew izolacji, jak i dla złożonych lasów składających się ze stu drzew. Ponadto, przedstawiono graficzną reprezentację procesu detekcji anomalii, wykorzystując optymalnie wyznaczony próg detekcji. Prezentowane wyniki ponownie potwierdzają bardzo dobre właściwości detekcyjne nowo wprowadzonych metod. W końcowej części rozprawy przeprowadzono syntezę wyników eksperymentów i analiz, sformułowano istotne wnioski oraz zarysowano perspektywy przyszłych prac badawczych. Kierunki dalszego rozwoju zaproponowanych technik czerpią inspirację zarówno z obserwacji efektów eksperymentów, jak i z dogłębnej analizy mechanizmów działania omawianych algorytmów.
Abstract EN
This dissertation introduces innovative anomaly detection algorithms based on the Isolation Forest (IF) method. The thesis begins by presenting an overview of the anomaly detection issue, encompassing a review of general methods used in this field. Subsequently, the IF method is discussed in detail, along with key concepts necessary for the implementation of the novel techniques. Studies regarding modifications of the IF method have been analyzed. Within this review, particular emphasis is placed on those publications focused on the improvements and extensions of the basic IF algorithm.
The dissertation includes the introduction of five new anomaly detection algorithms. Among them are two attribute reduction methods used in the data preprocessing process, based on clustering techniques such as 𝑘-Means and Fuzzy 𝐶-Means. Furthermore, a method has been developed to improve the selection of the attribute value at isolation nodes, using an optimized clustering algorithm based on the minimal spanning tree.Within the next two methods, innovative solutions have been introduced in the construction of isolation trees, involving the isolation of elements through their merging using the minimal spanning tree algorithm. The newly introduced isolation trees are characterized by two components of anomaly assessment: one associated with the level of the element in the isolation tree and the other with the distance of the element from the nearest leaf node. The first of the mentioned methods utilizes the assessment function by summing the introduced components of anomaly assessment. The second technique introduces the integration of normalized components of anomaly assessment using the fuzzy rules block in the Takagi-Sugeno inference model. A comprehensive series of experiments on newly proposed approaches have been conducted to evaluate the algorithms and compare them with existing competitive techniques. The studies involved 26 real-world datasets. Measures of classification quality independent of the detection threshold selection were measured, such as the area under the receiver operating characteristic curve and the area under the precision-recall curve. Additionally, optimal detection threshold values for the methods were determined, and values of measures dependent on this threshold were calculated, namely accuracy, precision, recall, specificity, false alarmratio, and F1 measure. The results of these studies unequivocally confirm that the newly introduced solutions are characterized by high effectiveness. Moreover, other characteristicswere also analyzed, including the response times of the algorithms in the training and evaluation phases, and a thorough analysis of hyperparameters was conducted. Adjusting the hyperparameters of the methods allowed for identifying possibilities for their modification to optimize the performance of the algorithms with specific tasks in mind. To demonstrate the effectiveness of the new approaches in separating anomalous samples from normal ones, a graphical representation of the separability was presented, using normalized values of the assessment function of individual algorithms. To visualize the characteristics of the newly developed algorithms, four artificially generated, two-dimensional anomaly detection datasets were prepared. Heatmaps reflecting the assessment function values were developed, both for individual isolation trees and for complex forests consisting of one hundred trees. In addition, a graphical representation of the anomaly detection processwas presented, using the optimally determined detection threshold. The presented results again confirm the very good detection properties of the newly introduced methods. In the final part of the dissertation, a synthesis of the results of experiments and analyses was conducted, key conclusions were formulated, and prospects for future research work were outlined. The directions for further development of the techniques proposed are inspired both by the observation of the effects of the experiments and by a deep understanding of the operation mechanisms applied in the discussed algorithms.
Statistics
15Views Gałka, Ł. (2024). Algorytm minimalnego drzewa rozpinającego w zastosowaniu do budowy efektywnego lasu izolacji dla detekcji anomalii. https://hdl.handle.net/20.500.14629/18665
Loading...
Files
Rozprawa Doktorska Łukasz Gałk...
PDF 12.32 MB
Licence
Closed Access
Accessibility issue?Request a WCAG-compliant file
Publication available in collections: