Was ist Downsampling?

Downsampling ist eine gängige Datenverarbeitungstechnik, die Ungleichgewichte in einem Datensatz durch Entfernen von Daten aus der Mehrheitsklasse ausgleicht, sodass die Größe der Minderheitsklasse erreicht wird. Dies steht im Gegensatz zum Upsampling, bei dem Punkte der Minderheitsklasse neu gesampelt werden. Sowohl Python scikit-learn als auch Matlab enthalten integrierte Funktionen zur Implementierung von Downsampling-Techniken.

Downsampling für Data Science wird oft mit Downsampling in der digitalen Signalverarbeitung (Digital Signal Processing, DSP) verwechselt. Die beiden sind im Grunde ähnlich. Beim Downsampling für die digitale Signalverarbeitung (auch Dezimierung genannt) werden die Bandbreite und die Abtastrate des Samplers verringert, wodurch einige der Originaldaten aus dem Originalsignal entfernt werden. Der Prozess der Verringerung der Stichprobenhäufigkeit wird oft durch die Reduzierung der Stichprobenrate um einen ganzzahligen Faktor durchgeführt, wobei nur eine von jeder n-ten Stichprobe beibehalten wird. Dies geschieht mithilfe eines Tiefpassfilters, auch als Anti-Aliasing-Filter bekannt, um die Hochfrequenz-/Rauschkomponenten eines zeitdiskreten Signals um den zuvor erwähnten ganzzahligen Faktor zu reduzieren.

Downsampling zum Datenausgleich kann auch mit Downsampling zur Bildverarbeitung verwechselt werden. Wenn Daten viele Merkmale enthalten, wie bei hochauflösenden MRT-Bildern, können Berechnungen teuer werden. Downsampling in der Bildverarbeitung reduziert somit die Dimensionalität jedes Datenpunkts durch Faltung. Dies ist nicht dasselbe wie das Ausbalancieren des Datensatzes: Es handelt sich um eine Optimierungstechnik, die später eine Interpolation erfordert, um die Originaldaten wiederherzustellen.

Downsampling ist eine effektive Methode zur Beseitigung von Ungleichgewichten innerhalb eines Datensatzes. Ein unausgewogener Datensatz ist als ein Datensatz definiert, in dem eine Klasse im Vergleich zur wahren Population stark unterrepräsentiert ist, was wiederum zu unbeabsichtigten Verzerrungen führt. Stellen Sie sich zum Beispiel Folgendes vor: Ein Modell wird darauf trainiert, Bilder zu klassifizieren, die eine Katze oder einen Hund zeigen. Der verwendete Datensatz besteht zu 90 % aus Katzen und zu 10 % aus Hunden. Katzen sind in diesem Szenario also überrepräsentiert. Und wenn wir einen Klassifikator haben, der jedes Mal Katzen vorhersagt, wird er eine Genauigkeit von 90 % bei der Klassifizierung von Katzen, aber 0 % bei der Klassifizierung von Hunden erreichen. In diesem Fall führt der unausgewogene Datensatz dazu, dass Klassifikatoren die Genauigkeit der Mehrheitsklasse auf Kosten der Minderheitsklasse bevorzugen. Das gleiche Problem kann bei Datensätzen mit mehreren Klassen auftreten.¹

Der Prozess des Downsampling wirkt dem Problem des unausgewogenen Datensatzes entgegen. Es werden Punkte der Mehrheitsklasse identifiziert, die basierend auf bestimmten Kriterien entfernt werden müssen. Diese Kriterien können sich je nach gewählter Downsampling-Technik ändern. Dadurch wird der Datensatz ausgeglichen, indem die Anzahl der Stichproben für eine überrepräsentierte Mehrheitsklasse effektiv verringert wird, bis der Datensatz ein gleichmäßiges Verhältnis der Punkte über alle Klassen hinweg enthält.

Ungleichgewichte lassen sich durch einfaches Auftragen der Anzahl der Datenpunkte in jeder Klasse erkennen. Dies sagt jedoch nichts darüber aus, ob sie das Modell stark beeinträchtigen. Glücklicherweise können wir anhand von Leistungskennzahlen messen, wie gut eine Downsampling-Technik das Ungleichgewicht zwischen den Klassen korrigiert. Die meisten dieser Metriken beziehen sich auf binäre Klassifizierungen, bei denen es nur zwei Klassen gibt: eine positive und eine negative. Normalerweise ist die positive Klasse die Minderheitsklasse, während die negative Klasse die Mehrheitsklasse ist. Zwei beliebte Metriken sind ROC-Kurven (Receiver Operating Characteristic) und Precision-Recall-Kurven.¹

• Weniger Speicherbedarf: Wenn Speicherplatz Geld kostet, z. B. beim Cloudspeicher, wäre Downsampling dem Upsampling vorzuziehen, um Kostensteigerungen zu vermeiden.²
  
• Schnelleres Training: Durch Downsampling werden Datensätze verkleinert und die CPU- oder GPU-Belastung beim Training verringert, was wirtschaftlicher und umweltfreundlicher ist.
• Weniger anfällig für Überanpassung: Durch Upsampling werden aus den alten Daten neue Daten generiert, was dazu führen kann, dass Modelle zu stark an die gegebenen Daten angepasst werden. Im Gegensatz dazu ist Downsampling, wobei Daten gelöscht werden, von diesem Problem nicht betroffen.²

• Verlust von Informationen: Das Löschen von Punkten aus der Mehrheitsklasse kann zu einem Verlust wichtiger Informationen führen. Dies wird dann zum Problem, wenn die Klassifizierung der Mehrheitsklasse genau stimmen muss. Ein weiteres Problem besteht darin, dass der Datensatz zu klein wird, um das Modell darauf zu trainieren.²
  
• Eingeführte Verzerrung: Die verbleibenden Stichprobenpunkte der Mehrheitsklasse können eine verzerrte Menge der Originaldaten sein, was sich negativ auf die Leistung des Klassifikators auswirkt.

Das zufällige Downsampling ist eine Löschtechnik, bei der zufällige Punkte in der Mehrheitsklasse ohne Ersatz ausgewählt und aus dem Datensatz gelöscht werden, bis die Größe der Mehrheitsklasse der Größe der Minderheitsklasse entspricht. Dies ist eine einfache Möglichkeit, eine Teilmenge von Daten zu Ausgleichszwecken nach dem Zufallsprinzip zu löschen. Diese Technik kann jedoch dazu führen, dass wichtige Muster oder Häufigkeitsverteilungen in der Mehrheitsklasse verschwinden, was sich negativ auf die Leistung des Klassifikators auswirkt.²

Near-Miss-Downsampling ist eine Technik, die darauf abzielt, die Klassenverteilung auszugleichen, indem bestimmte Beispiele für Mehrheitsklassen nach dem Zufallsprinzip eliminiert werden.

Konzeptionell arbeitet Near Miss nach dem Prinzip, dass Daten an Orten aufbewahrt werden sollten, an denen die Mehrheits- und Minderheitsklassen sehr nahe beieinander liegen, da diese Orte uns wichtige Informationen zur Unterscheidung der beiden Klassen liefern.³ Diese Punkte werden im Allgemeinen als „schwer“ zu erlernende Datenpunkte bezeichnet. Das Near-Miss-Downsampling erfolgt im Allgemeinen in zwei Schritten:

• Schritt 1: Berechnen Sie den paarweisen Abstand zwischen allen Instanzen der Mehrheits-Minderheits-Klasse.
• Schritt 2: Entfernen Sie auf der Grundlage der berechneten Entfernungen Instanzen der Mehrheitsklasse, die weiter von den Minderheitspunkten entfernt sind.

Es gibt drei Varianten des Near-Miss-Algorithmus, die eine eindeutigere Methode zur Auswahl der zu entfernenden Mehrheitsklasseninstanzen bieten.

• Version 1: Diese Version behält die Instanzen der Mehrheitsklasse mit der geringsten durchschnittlichen Entfernung zu den N-nächstgelegenen Instanzen der Minderheitsklasse bei. Die resultierenden Daten können potenziell ungleichmäßig verteilt sein, wobei einige Punkte der Mehrheitsklasse in der Nähe vieler Punkte der Minderheitsklasse liegen und andere in der Nähe sehr weniger, was sowohl zu einer geringen Präzision als auch zu einer geringen Trefferquote führt.⁴

• Version 2: Bei dieser Version der Near-Miss-Downsamplingmethode werden die Instanzen der Mehrheitsklasse mit der geringsten durchschnittlichen Distanz zu den N-am weitesten entfernten Instanzen der Minderheitsklasse beibehalten. Im Gegensatz zur ersten Version wird hierbei eine gleichmäßigere Verteilung der Mehrheitsklasse erreicht, was zu besseren Ergebnissen des Klassifikators führt.⁴

• Version 3: Diese Version behält die Proben der Mehrheitsklasse bei, die den Instanzen der Minderheitsklasse am nächsten kommen. Sie funktioniert in zwei Schritten. Zunächst werden die M-nächsten Nachbarn der Mehrheitsklasse jeder Instanz der Minderheitsklasse beibehalten. Dann werden aus den verbleibenden Instanzen der Mehrheitsklasse diejenigen mit der größten durchschnittlichen Entfernung identifiziert und beibehalten. Da diese Version die Instanzen der Mehrheitsklasse beibehält, die mit vielen Instanzen der Minderheitsklasse in Verbindung stehen, kann sie eine hohe Präzision, aber eine geringe Trefferquote aufweisen.⁴

Condensed Nearest Neighbors (kurz CNN, nicht zu verwechseln mit Convolutional Neural Networks) versucht, eine Teilmenge eines Datensatzes zu finden, die ohne Verlust der Modellleistung für das Training verwendet werden kann. Dazu wird eine Teilmenge der Daten ermittelt, die zum Trainieren eines Modells verwendet werden kann, das den gesamten Datensatz korrekt vorhersagt.

CNN-Downsampling kann in die folgenden Schritte unterteilt werden:⁵

1. Erstellen Sie einen neuen Datensatz, S, der alle Instanzen der Minderheitsklasse und eine einzelne zufällig ausgewählte Instanz der Mehrheitsklasse enthält.
2. Trainieren Sie einen 1-NN-Klassifikator auf dem neuen Datensatz S.
3. Verwenden Sie für alle Datenpunkte der Mehrheitsklasse, die nicht in S enthalten sind, den 1-NN-Klassifikator, um ihre Bezeichnung vorherzusagen. Wenn der 1-NN-Klassifikator die Bezeichnung korrekt vorhersagt, verwerfen Sie den Punkt. Andernfalls fügen Sie es zu S hinzu.

Wie bei der Methode „Near Miss“ werden bei diesem Verfahren im Wesentlichen alle Instanzen der Mehrheitsklasse entfernt, die weit von der Entscheidungsgrenze entfernt sind, also Punkte, die sich leicht klassifizieren lassen. Es stellt auch sicher, dass alle Daten in unserem ursprünglichen Datensatz korrekt vorhergesagt werden können, indem nur die Daten innerhalb von S verwendet werden. Auf diese Weise kann der Datensatz erheblich verkleinert werden, während die Entscheidungsgrenze einigermaßen gut erhalten bleibt.

Dieses Bild zeigt ein Beispiel für die Anwendung von verdichteten nächsten Nachbarn unter Verwendung von 1 nächsten Nachbarn und 21 nächsten Nachbarn auf zwei Datensätze. Die oberen beiden Bilder wurden vor der Anwendung der verdichteten nächsten Nachbarn erstellt, die unteren beiden danach. Wie man sehen kann, bleibt die Entscheidungsgrenze relativ gut erhalten.

Das Prinzip des Tomek-Link-Downsampling besteht darin, das Rauschen in den Daten durch Entfernen von Punkten in der Nähe der Entscheidungsgrenze zu reduzieren und die Klassentrennung zu erhöhen. Zunächst werden „Tomek-Links“ identifiziert – eine Gruppierung von zwei Punkten aus verschiedenen Klassen, ohne dass es einen dritten Punkt gibt, der einer der beiden am nächsten liegt.²

Für alle Tomek-Links wird der Punkt innerhalb der Mehrheitsklasse gelöscht. Durch das Entfernen eines Mehrheitsklassenpunkts, der nahe an einem Minderheitsklassenpunkt liegt, erhöht sich die Klassentrennung. Ein Nachteil dieser Methode ist die hohe Rechenkomplexität bei der Berechnung aller paarweisen Abstände zwischen den Punkten der Mehrheits- und der Minderheitsklasse.² Tomek-Link-Downsampling ist am effektivsten, wenn es mit anderen Techniken kombiniert wird.

Die Nearest-Neighbors-Downsampling-Methode (ENN) ähnelt der Tomek-Link-Downsampling-Methode, bei der das Ziel darin besteht, Beispiele in der Nähe der Entscheidungsgrenze zu entfernen, um die Klassentrennung zu verbessern. Im Allgemeinen werden bei dieser Methode Datenpunkte entfernt, die sich in ihrer Klasse von der Mehrheit ihrer Nachbarn unterscheiden.² Das bedeutet, dass in diesem Zuge Datenpunkte der Mehrheitsklasse entfernt werden, bei denen die Mehrheit der nächsten Nachbarn zur Minderheitsklasse gehört, und umgekehrt. Die Mehrheit kann in diesem Zusammenhang frei definiert werden: Sie kann bedeuten, dass mindestens ein Nachbar einer anderen Klasse angehört oder dass der Anteil der Nachbarn einer anderen Klasse einen bestimmten Schwellenwert überschreitet.

ENN-Downsampling wird normalerweise mit 3 nächsten Nachbarn durchgeführt, wie unten dargestellt.

Dies ist eine Strategie mit gröberer Körnung, da sie die allgemeine Nachbarschaft von Punkten und nicht einen einzelnen Nachbarn betrachtet, aber es ist eine effiziente Methode, um Rauschen in den Daten zu beseitigen. ENN-Downsampling ist am effektivsten, wenn sie mit anderen Techniken kombiniert wird.

Aktuelle Entwicklungen im Bereich Downsampling drehen sich um die Integration von Deep Learning. Dies wird bei der Bildverarbeitung und medizinischen Daten verwendet, bei denen neuronale Netze zum Downsampling der Daten eingesetzt werden.⁶ Ein Beispiel hierfür ist SOM-US, das ein zweischichtiges neuronales Netz verwendet.⁷ In den letzten Jahren wurde aktives Lernen auch auf Downsampling angewendet, um die Auswirkungen unausgewogener Daten zu mildern.⁸ Experimente haben gezeigt, dass diese Modelle deutlich besser abschneiden als herkömmliche Techniken.

Aktuelle Forschungsarbeiten im Bereich Downsampling befassen sich auch mit der Kombination mit anderen Techniken, um Hybridtechniken zu entwickeln. Eine Möglichkeit besteht aus einer Kombination aus Downsampling und Upsampling der Daten, um die Vorteile beider Verfahren zu nutzen: SMOTE+Tomek Link, Agglomerative Hierarchical Clustering (AHC) und SPIDER sind einige Beispiele hierfür.⁹ Techniken auf Algorithmenebene können auch Ideen aus herkömmlichen Downsampling-Techniken einbeziehen, wie z. B. beim Hard Example Mining, bei dem sich das Training nur auf die „schwierigeren“ Datenpunkte konzentriert.² Sie zeigen jeweils eine bessere Leistung als die Verwendung jeder Technik einzeln.