Fast internal relative evaluation of outlier solutions (Fast IREOS)

Abstract

Die automatische Erkennung von Ausreißern ist ein wichtiger Schritt während der Datenaufbereitung und -verarbeitung von modernen Anwendungen, die maschinelles Lernen und Data-Mining nutzen.Eine verlässliche Erkennung dieser Datenanomalien spielt eine besonders wichtige Rolle bei Anwendungen in der Medizin, im Finanzwesen und in der Industrie.Aus diesem Grund ist die Weiterentwicklung und Optimierung von effizienten und effektiven Algorithmen zur Ausreißererkennung wünschenswert.Die Hauptanwendungsfälle von unüberwachtem Lernen zur Extraktion von unbekannten Informationen sind einerseits das Clustern, als auch die Erkennung von Ausreißern.Jedoch sind sie oft fehleranfällig, da sie auf Kriterien und Parametern beruhen, die Modelle vorgeben die den Daten nicht entsprechen. Dies macht eine Form von Validierung notwendig, welche entweder extern (ground truth) oder intern (Struktur der Daten) geschehen kann.Obwohl es in der Literatur einige Ressourcen zu interner Validierung für Clustering gibt, so sind diese in der Domäne der Ausreißererkennung unterrepräsentiert.Ursprünglich veröffentlicht im Jahr 2015, ist IREOS eine der wenigen existierenden, internen Validierungsmethoden im Gebiet der Ausreißererkennung.Das Ziel dieser Diplomarbeit ist eine Untersuchung von IREOS bezüglich Performance, sowie Möglichkeiten, um den Algorithmus weiter zu beschleunigen.Die Verwendung verschiedener Klassifikatoren wie lineare und baumartige Klassifikatoren wurde in Bezug auf die ursprüngliche Technik untersucht, indem mehrere Datensets auf einer alternativen Implementierung von IREOS unter Verwendung der Programmiersprache Julia ausgeführt wurden.Neben dem direkten Vergleich mit der Leistung von IREOS, ging es bei dieser Arbeit vor allem darum, die Laufzeit zu verbessern und gleichzeitig die Qualität der Ergebnisse des Algorithmus beizubehalten, indem sichergestellt wird, dass die resultierenden Zahlen innerhalb des Bereichs der von IREOS erzielten Werte bleiben.Einige der getesteten Klassifikatoren zeigten statistisch gesehen ähnliche Ergebnisse wie die ursprüngliche Implementierung.Der schnellste Klassifikator konnte eine Berechnung für die IREOS über 50 Minuten benötigte, auf etwa 1 Sekunde reduzieren. In unseren Experimenten lieferten insbesondere baumartige Klassifikatoren und nicht-lineare SVMs qualitativ sehr ähnliche und konsistente Ergebnisse, mit nur einem Bruchteil der Ausführungszeit von IREOS.Die Ergebnisse zeigen das Potenzial von weniger komplexen Klassifikatoren, die intern für die Erkennung von Anomalien verwendet werden, und die Einschränkungen in Bezug auf ihre Stabilität bei verschiedenen Parametereinstellungen.

Automatic outlier detection marks an important step in the process of data preparation and processing for modern applications of machine learning and data mining.Accurately identifying and eliminating anomalies within data plays an important role in real-world applications found in medical, financial, and industrial fields.Thus, the development and optimization of efficient and accurate implementations of outlier detection algorithms is highly desired.Unsupervised learning, either clustering or anomaly/outlier detection, are very common tools to extract a priori unknown information about the data under analysis.However, they often fail, as they are based on criteria or parameters that may impose models that are not natural to the data. Validation is necessary, both externally (i.e., compared with a ground truth) and internally (i.e., based on the inherent properties of data). And, although there are many methods for internal validation of clustering, the internal validation of outlier solutions is still underrepresented in the literature and remains a challenge in the field of data mining.Originally released in 2015, IREOS is one of the few existing internal validation methods for anomaly detection algorithms.This thesis aims to investigate the behavior and performance of the recently introduced technique IREOS and to find ways to speed up the applied algorithm and implementation thereof.The use of different classifiers such as linear and tree-based classifiers concerning the original technique was studied by running multiple datasets on a self-written alternative implementation of IREOS using the Julia Programming Language.In addition to the direct comparison to the performance of IREOS, the primary focus of this work was to improve already existing evaluations of outlier detection while retaining the quality of the algorithm’s output by ensuring the resulting outlier scores remain within the range of those obtained by IREOS.Under empirical evidence, some of those tested predictors showed statistically similar results to the original implementation.The fastest predictor was able to speed up a calculation IREOS needed over 50 minutes to around 1 second. In our experiments, especially tree-based predictors and nonlinear support vector machines deliver highly similar and consistent results with only a fraction of the execution time of IREOS.Results show the potential of lightweight predictors being used internally for anomaly detection and the limitations in regard to their stability over different parameter settings.