Data Cleaning

Data Cleaning kann auf unterschiedlichen Algorithmen basieren. Einer davon ist der Isolation Forest Algorithmus, auf welchen wir in diesem Artikel unseren Fokus legen.

Was ist ein Isolation Forest Algorithmus?

Der Isolation Forest Algorithmus wurde 2008 von Fei Tony Liu, Kai Ming Ting und Zhi-Hua Zhou entwickelt. Es ist ein unüberwachter Lernalgorithmus, der zur Familie der Entscheidungsbäume gehört. An dieser Stelle ist es sinnvoll, den Begriff „unüberwachtes Lernen“ (engl. „unsupervised learning“) zu erläutern. Hierbei handelt es sich um Machine-Learning-Methoden, die es ermöglichen, ohne vorgegebene Muster die Zusammenhänge in Daten explorativ zu erkennen. In der Praxis bedeutet dies, dass der Algorithmus keine historischen Daten braucht und direkt an einer gegebenen Datenmenge anwendbar ist. Im Kontext der Anomalieerkennung muss der Algorithmus also nicht wissen, welche Merkmalsausprägungen auf eine Anomalie hindeuten, sondern findet diese selbst heraus.

Dieser Ansatz macht sich zunutze, dass Anomalien Variablenwerte haben, die sich stark von den erwarteten Mittelwerten unterscheiden und dass sie nur mit einer sehr geringen Wahrscheinlichkeit auftreten. Diese Eigenschaften ermöglichen es, Anomalien von den restlichen Daten zu isolieren. Der Algorithmus funktioniert hervorragend mit sehr großen multidimensionalen Datensätzen und hat sich als sehr effektive Methode erwiesen.

Wie funktioniert der Isolation Forest Algorithmus?

Der Kern des Algorithmus besteht darin, Anomalien zu isolieren, indem Entscheidungsbäume mit zufälligen Attributen erstellt werden:

Schritt #1 : Hier wählt der Algorithmus eine Variable und ihre Ausprägung, die zwischen dem Minimum und Maximum der Variable liegt, nach dem Zufallsprinzip. Die Datenpunkte werden in zwei Gruppen aufgeteilt: „kleiner gleich“ und „größer“ als die gewählte Ausprägung, und im Fall einer qualitativen Variablen, „gehört“ und „gehört nicht“ zu der gewählten Menge an Ausprägungen. Dieser Vorgang wird für jede Teilmenge unabhängig wiederholt, bis jede Teilmenge genau einen Datenpunkt enthält. Beim Betrachten des resultierenden Baums können normale und anormale Punkte anhand ihrer durchschnittlichen Pfadlänge unterschieden werden. Je kürzer der Isolationsweg ist, desto mehr weist er auf eine Anomalie hin. Dies ist nur ein Entscheidungsbaum und wie der Name des Algorithmus sagt, werden viele „Bäume“ bzw. ein ganzer „Wald“ benötigt. Deswegen wird der gesamte Vorgang mit immer wieder neuen zufälligen Ausgangspunkten über mindestens 100 Schleifen wiederholt.

Schritt #2: Darauf aufbauend wird im nächsten Schritt ein Anomalie-Scoring erstellt. Diese Funktion berechnet eine Durchschnittspfadlänge vom Baumansatz (auch Wurzel genannt) und normiert diese auf ein Intervall [0, 1]. Ziel ist es, ein analytisch eingeschränktes und vergleichbares Maß für jeden Datenpunkt zu definieren.

Die dann verwendete Scoring-Funktion ist gegeben durch: S(x,n)=2^(-E[h(x)]/c(n))

Definition:

h (x) – Pfadlänge des Datenpunktes x im gegebenen Isolationsbaum

E [h(x)] – Durchschnittspfadlänge des Datenpunktes x in allen Isolationsbäumen

c(n) – Durchschnittspfadlänge über alle Datenpunkte und Isolationsbäume

Dementsprechend haben Datenpunkte mit Pfadlängen kürzer als der Durchschnitt einen Scoring-Wert von mehr als 0,5.

Je höher der Scoring-Wert, desto kürzer die durchschnittliche Pfadlänge und somit die Wahrscheinlichkeit, dass es sich um eine Anomalie handelt.

Schritt #3: Als letztes wird der gewünschte und vom Benutzer definierte Anteil (Kontaminationsniveau) der Datenpunkte mit dem höchsten Scoring als Anomalien ausgegeben. Diese sollten weiter analysiert werden, um die Ursachen der Unvereinbarkeit mit dem vorliegenden Datenmuster zu ergründen, umso entsprechende Maßnahmen durchführen zu können.

Ein Vorteil des Isolation Forest Algorithmus ist, dass dieser recht unkompliziert ist und seine Ergebnisse einfach zu interpretieren sind. Er liefert eine fertige Liste der Datenanomalien. Ebenso zählt Schnelligkeit zum Vorteil: Die Zeitkomplexität ist linear, das heißt auch, bei sehr großen Datenmengen findet der Isolation Forest Algorithmus eine effiziente Lösung. Außerdem kann er sowohl bei quantitativen als auch qualitativen Daten angewendet werden, was bei vielen anderen Algorithmen ausgeschlossen ist. Da das Verfahren hervorragend mit multidimensionalen Datensätzen funktioniert, bekommen Nutzer:innen gleichzeitig ein ganzheitliches Bild von den untersuchten Daten.

Ein Nachteil ist, dass die Datenpunkte mit einem hohen Scoring nicht direkt isoliert werden – das Kontaminationsniveau wird manuell eingestellt und sollte ggf. angepasst werden. Die Anomalien werden durch zufällige Verteilungen identifiziert, deswegen könnte es in sehr seltenen Fällen dazu kommen, dass dies nicht korrekt erfolgt. Um das Risiko zu minimieren, empfiehlt es sich, die Anzahl der verwendeten Entscheidungsbäume zu erhöhen.