Vergleich von Algorithmen zur Ausreißererkennung in höherdimensionalen Räumen

Abstract

Die vorliegende Diplomarbeit beschreibt die Probleme, die bei der Ausreißererkennung in höherdimensionalen Räumen vorkommen, und stellt Algorithmen vor, die in der Lage sind, Ausreißer in solchen Räumen zu finden. Die ersten Kapitel beinhalten eine allgemeine Einführung in die Thematik, führen den Begriff Ausreißer ein und gehen auf den Unterschied zu Noise und Novelty ein. Danach wird ein kurzer Überblick über Algorithmen zur Ausreißererkennung gegeben. Im Weiteren wird der "Fluch der Dimensionalität" dargestellt. Dieser Begriff bezeichnet die geringer werdende Aussagekraft von Metriken mit wachsender Dimension, verursacht durch die abnehmende Dichte des Datenraums. Die notwendigen Sätze zu Aussagen zum Verhalten von Metriken in höherdimensionalen Räumen werden bewiesen. Im Anschluss werden die Algorithmen "Ausreißererkennung in Unterräumen", "Ausreißererkennung mit Hilbert-Kurven" und "Angle Based Outlier Detection" sowie ihre Eigenschaften detailliert erklärt. Diese Algorithmen wurden speziell für die Ausreißererkennung in höherdimensionalen Räumen entwickelt. Sie basieren allerdings auf jeweils unterschiedlichen Ideen um Ausreißer zu finden, was die Frage aufwirft, ob ein Algorithmus den anderen überlegen ist. In den letzten beiden Kapiteln versuchen wir, diese Frage zu beantworten, indem wir mit diesen Algorithmen Ausreißer in Datenräumen suchen und die Ergebnisse dieser Suche analysieren.

This master thesis describes the problems that occur at outlier detection in high-dimensional spaces and presents algorithms which are able to find outliers in such spaces. The first chapters lead into the topic, introduce the term outlier and describe the distinction to noise and novelty. Next the "curse of dimensionality" is presented. This concept denotes the weaker significance of a metric if the dimension increases, caused by the low density of high-dimensional data spaces. The required theorems covering the behavior of metrics in high-dimensional spaces are proved. Subsequently the algorithms "Outlier Detection in Subspaces", "Outlier Detection using Hilbert curves" and "Angle Based Outlier Detection" and their characteristics are explained. These algorithms were designed specifically for outlier detection in high-dimensional spaces. Each of them is based on its own idea to find outliers, raising the question: Is one algorithm superior to the other algorithms? In the final chapters we try to answer this question by searching for outliers in data spaces with these algorithms and analyze the results of these searches.