Die vorliegende Übersetzung wurde maschinell erstellt. Im Falle eines Konflikts oder eines Widerspruchs zwischen dieser übersetzten Fassung und der englischen Fassung (einschließlich infolge von Verzögerungen bei der Übersetzung) ist die englische Fassung maßgeblich.

Wie funktioniert RCF

Amazon SageMaker Random Cut Forest (RCF) ist ein unbeaufsichtigter Algorithmus zur Erkennung anomaler Datenpunkte innerhalb eines Datensatzes. Das sind Beobachtungen, die von ansonsten gut strukturierten oder nach Mustern geordneten Daten abweichen. Solche Auffälligkeiten können sich als unerwartete Spitzen in Zeitreihendaten, unterbrochener Periodizität oder unklassifizierbaren Datenpunkten manifestieren. Sie sind einfach zu beschreiben, denn wenn sie in einem Diagramm dargestellt werden, sind sie meist leicht von "regulären" Daten unterscheidbar. Sind diese Anomalien in einem Datensatz enthalten, kann dies zu einer erheblichen Komplexitätssteigerung einer Machine-Learning-Aufgabe führen, da sich "reguläre" Daten häufig in einem einfachen Modell darstellen lassen.

Die Hauptidee hinter dem RCF Algorithmus besteht darin, einen Wald aus Bäumen zu erzeugen, in dem jeder Baum anhand einer Partition einer Stichprobe der Trainingsdaten ermittelt wird. Beispielsweise wird zunächst eine zufällige Stichprobe aus den Eingabedaten gezogen. Diese randomisierte Stichprobe wird dann entsprechend der Anzahl der Einzelstrukturen in der Gesamtstruktur partitioniert. Jede Struktur erhält eine solche Partition und organisiert ein Punkte-Subset in einer k-d-Struktur. Die Anomaliebewertung, die einem Datenpunkt von einer Struktur zugeordnet wurde, wird als erwartete Änderung der Strukturkomplexität definiert, wenn der Struktur dieser Punkt hinzugefügt wird. Dies verhält sich umgekehrt proportional zur resultierenden Tiefe des Punkts in der Struktur. Random Cut Forest weist die Anomaliebewertung durch Berechnung der durchschnittlichen Bewertung jeder einzelnen Struktur und Skalierung des Ergebnisses unter Berücksichtigung der Stichprobengröße zu. Der RCF Algorithmus basiert auf dem in Referenz [1] beschriebenen Algorithmus.

Datenstichprobe nach dem Zufallsprinzip

Der erste Schritt des RCF Algorithmus besteht darin, eine Zufallsstichprobe der Trainingsdaten zu erhalten. Angenommen, wir möchten ein Beispiel der Größe von Datenpunkten insgesamt sampeln. Sind das Trainingsdaten klein genug, kann der gesamte Datensatz verwendet werden und es könnten Elemente nach dem Zufallsprinzip aus diesem Datensatz gezogen werden. Meist sind das Trainingsdaten jedoch zu umfangreich, um alle einzubeziehen, daher ist dieses Verfahren nicht anwendbar. Stattdessen wird eine als "Reservoir-Sampling" bezeichnete Methode genutzt.

Reservoir-Sampling ist ein Algorithmus zur effizienten Ziehung von Stichproben aus einem Datensatz nach dem Zufallsprinzip , wobei die Elemente im Datensatz nur einzeln oder in Stapeln beobachtet werden können. Tatsächlich funktioniert Reservoir-Sampling auch dann, wenn nicht a priori bekannt ist. Wenn nur eine Stichprobe angefordert wird, z. B. wenn , sieht der Algorithmus wie folgt aus:

Algorithmus: Reservoir-Sampling

Dieser Algorithmus wählt eine zufällige Stichprobe mit für alle aus. Wenn zutrifft, ist der Algorithmus komplizierter. Außerdem muss zwischen zufälligen Stichproben mit und ohne Ersetzung unterschieden werden. RCFführt auf der Grundlage der in [2] beschriebenen Algorithmen eine erweiterte Reservoirprobenahme ohne Ersatz anhand der Trainingsdaten durch.

Ein RCF Modell trainieren und Schlussfolgerungen ziehen

Der nächste Schritt besteht RCF darin, anhand der zufälligen Datenstichprobe einen nach dem Zufallsprinzip abgeholzten Wald zu konstruieren. Zunächst wird die Stichprobe in gleich große Partitionen partitioniert. Die Anzahl der Partitionen entspricht der Anzahl der Strukturen in der Gesamtstruktur. Anschließend wird jede Partition an eine einzelne Struktur gesendet. Die Struktur organisiert die eigene Partition rekursiv in eine binäre Struktur, indem sie die Datendomain in Begrenzungsrahmen partitioniert.

Dieses Verfahren lässt sich am besten anhand eines Beispiels darstellen. Angenommen, eine Struktur erhält folgenden zweidimensionalen Datensatz. Die entsprechende Struktur wird mit dem Stammknoten initialisiert:

Abbildung: Ein zweidimensionaler Datensatz, bei dem die meisten Daten in einem Cluster (blau) liegen, mit Ausnahme eines anomalen Datenpunkts (orange). Die Struktur wird mit einem Stammknoten initialisiert.

Der RCF Algorithmus organisiert diese Daten in einem Baum, indem er zunächst einen Begrenzungsrahmen der Daten berechnet, eine zufällige Dimension auswählt (Dimensionen mit höherer „Varianz“ mehr Gewicht einräumt) und dann nach dem Zufallsprinzip die Position einer Hyperebene bestimmt, die durch diese Dimension „geschnitten“ wird. Die daraus entstehenden Teilräume definieren ihre eigene Unterstruktur. In diesem Beispiel wird durch den Schnitt ein einzelner Punkt vom Rest der Stichprobe getrennt. Die erste Ebene der resultierenden Binärstruktur umfasst zwei Knoten. Einer enthält die Unterstruktur der Punkte links vom erfolgten Schnitt, der andere stellt den einzelnen Punkt auf der rechten Seite dar.

Abbildung: Ein zufälliger Schnitt, der den zweidimensionalen Datensatz partitioniert. Bei einem anormalen Datenpunkt ist die Wahrscheinlichkeit, dass dieser isoliert in einem Begrenzungsrahmen in geringerer Strukturtiefe liegt, höher als bei anderen Punkten.

Danach werden Begrenzungsrahmen für die linke und die rechte Hälfte der Daten berechnet. Dieser Prozess wird so lange wiederholt, bis alle Endknoten der Struktur einen einzelnen Datenpunkt aus der Stichprobe darstellen. Wenn der einzelne Punkt weit genug weg liegt, ist die Wahrscheinlichkeit, dass ein zufälliger Schnitt zur Isolierung des Punkts führt, höher. Diese Beobachtung führt zur Annahme, dass die Strukturtiefe praktisch umgekehrt proportional zur Anomaliebewertung ist.

Bei der Durchführung von Inferenzen mit einem trainierten RCF Modell wird der endgültige Anomaliewert als Durchschnitt aller von jedem Baum gemeldeten Werte angegeben. Beachten Sie, dass der neue Datenpunkt in der Struktur häufig noch nicht vorhanden ist. Um die Bewertung für den neuen Datenpunkt zu ermitteln, wird der Datenpunkt in die vorhandene Struktur eingefügt. Diese Struktur wird dann effizient (und temporär) auf dieselbe Weise wie oben im Trainingsverfahren beschrieben neu aufgebaut. Das heißt, die resultierende Struktur sieht aus, als ob der Eingabedatenpunkt Teil der Stichprobe gewesen wäre, aus der die Struktur zuerst generiert wurde. Die gemeldete Bewertung verhält sich umgekehrt proportional zur Tiefe des Eingabepunkts in der Struktur.

Auswählen von Hyperparametern

Die wichtigsten Hyperparameter, die zur Abstimmung des RCF Modells verwendet werden, sind und. num_trees num_samples_per_tree Eine Erhöhung von num_trees führt zu einer Reduzierung der Stördaten in Anomaliebewertungen, da die finale Bewertung aus dem Mittelwert der von den einzelnen Strukturen gemeldeten Bewertungen entsteht. Der optimale Wert ist abhängig von der Anwendung, aber wir empfehlen, zu Beginn 100 Strukturen zu verwenden, um ein Gleichgewicht zwischen Stördaten in der Bewertung und Modellkomplexität zu schaffen. Beachten Sie, dass sich die Inferenzzeit proportional zur Anzahl der Strukturen verhält. Obwohl auch die Trainingszeit betroffen ist, wird sie vom oben beschriebenen Reservoir-Sampling-Algorithmus dominiert.

Der Parameter num_samples_per_tree bezieht sich auf die erwartete Anomaliedichte im Datensatz. Insbesondere num_samples_per_tree sollte so gewählt werden, dass 1/num_samples_per_tree dem Verhältnis von anormalen Daten zu normalen Daten entspricht. Wenn beispielsweise 256 Stichproben pro Struktur verwendet werden, erwarten wir, dass die Daten Anomalien im Verhältnis von 1/256 oder ca. 0,4 % der Zeit aufweisen. Auch hier gilt, dass der optimale Wert für diesen Hyperparameter von der Anwendung abhängt.

Referenzen