CBHK02 (Chawla, Bowyer, Hall, Kegelmeyer 2002) — SMOTE: Synthetic Minority Over-sampling Technique

CBHK02 — SMOTE: Synthetic Minority Over-sampling Technique

Bibliografische Angaben

Nitesh V. Chawla, Kevin W. Bowyer, Lawrence O. Hall, W. Philip Kegelmeyer, „SMOTE: Synthetic Minority Over-sampling Technique”, Journal of Artificial Intelligence Research 16, S. 321–357, 2002. DOI: 10.1613/jair.953.

Methodik

Methoden-Paper mit begleitender empirischer Evaluation. Die Autoren stellen ein neues Oversampling-Verfahren fuer unbalancierte Klassifikationsprobleme vor: Statt Minderheitsbeispiele mit Zuruecklegen zu vervielfachen (Replikation), werden synthetische Beispiele im Merkmalsraum entlang der Verbindungsgeraden zwischen einem Minderheitspunkt und einem seiner k naechsten Klassenkameraden interpoliert (Standard k = 5). SMOTE wird mit einem Random-Undersampling der Mehrheitsklasse kombiniert. Die Evaluation erfolgt auf neun realen und synthetischen Datensaetzen (Pima, Phoneme, Satimage, Forest Cover, Oil, Mammography, E-state, Can, Adult) mit drei Basisklassifikatoren (C4.5 Release 8, Ripper, Naive Bayes), 10-fache Kreuzvalidierung, Bewertung ueber ROC-Kurven, Area Under the Curve (AUC) und ROC-Konvex-Huelle (Provost & Fawcett).

Kernaussagen

• SMOTE-Grundprinzip (S. 328): Fuer jeden Minderheits-Datenpunkt werden die k naechsten Minderheits-Nachbarn im Merkmalsraum bestimmt (Implementierung: k = 5); je nach benoetigtem Oversampling-Grad werden davon zufaellig Nachbarn ausgewaehlt und zwischen Ausgangspunkt und Nachbar ein Zufallspunkt (gap ∈ [0, 1]) auf der Verbindungsstrecke als synthetischer Punkt eingefuegt.
• Kombination mit Undersampling (S. 331): Die Mehrheitsklasse wird durch zufaelliges Entfernen von Datenpunkten reduziert, sodass die Minderheitsklasse einen vorgegebenen Prozentsatz der Mehrheitsklasse erreicht. Die Kombination von SMOTE (Oversampling) und Random-Undersampling verschiebt den Bias des Lerners von der Mehrheits- zur Minderheitsklasse.
• Warum synthetisch statt Replikation (S. 326–328, Fig. 3): Minority-Replikation erzeugt sehr kleine, immer spezifischere Entscheidungsregionen (Overfitting); Interpolation dagegen zwingt den Klassifikator, groessere, allgemeinere Regionen fuer die Minderheitsklasse zu bilden (bessere Generalisierung; illustriert am Mammography-Datensatz, Fig. 3a–c und Fig. 4 fuer Baumgroesse).
• Evaluations-Metrik: ROC & AUC (S. 322–323): Accuracy ist bei stark unbalancierten Klassen ungeeignet; stattdessen werden ROC-Kurven (percent TP gegen percent FP), AUC ueber die Trapezregel und die ROC-Konvex-Huelle (Provost & Fawcett 2001) verwendet. Punkte auf der Konvex-Huelle sind potenziell optimal, unabhaengig von Kostenverteilung und Klassenpriors.
• Empirisches Hauptergebnis (Abstract, Sec. 5.3, S. 339 + Sec. 7, S. 352): In 44 von 48 durchgefuehrten Experimenten dominiert SMOTE + Undersampling im ROC-Raum das reine Undersampling der Mehrheitsklasse (basierend auf AUC und Konvex-Huelle). Ebenfalls schlaegt SMOTE das Variieren des Loss-Ratios in Ripper und das Aendern der Klassenpriors in Naive Bayes.
• Typische Skalierungsfaktoren (Sec. 5, S. 331 + Tab. 3, S. 345): Fuer C4.5 wurde die Minderheitsklasse pro Datensatz auf 100 %, 200 %, 300 %, 400 % oder 500 % ihrer urspruenglichen Groesse aufgeblasen; die Mehrheit auf 10 %–2000 % undersampled. Die optimalen Werte in Tab. 3 (fetter Eintrag) variieren stark je Datensatz (z. B. Mammography 400 % SMOTE, Oil 500 %, Adult nur 50 %).
• Baum-Klassifikator-Bezug (S. 328): SMOTE wird durchgehend am Beispiel von C4.5-Entscheidungsbaeumen (Quinlan 1992) illustriert: „decision regions”, „decision tree size” (Fig. 4), „terminal nodes/leaves” (S. 328); die Fig.-3-Argumentation ist unmittelbar baum-basiert. Random Forests werden im Paper nicht behandelt.

Woertliche Zitate

Zitat 1 — SMOTE-Grundprinzip (Buch-S. 328, Sec. 4.2 SMOTE)

„We propose an over-sampling approach in which the minority class is over-sampled by creating ‚synthetic’ examples rather than by over-sampling with replacement. […] We generate synthetic examples in a less application-specific manner, by operating in ‚feature space’ rather than ‚data space’. The minority class is over-sampled by taking each minority class sample and introducing synthetic examples along the line segments joining any/all of the k minority class nearest neighbors. Depending upon the amount of over-sampling required, neighbors from the k nearest neighbors are randomly chosen. Our implementation currently uses five nearest neighbors. For instance, if the amount of over-sampling needed is 200 %, only two neighbors from the five nearest neighbors are chosen and one sample is generated in the direction of each. Synthetic samples are generated in the following way: Take the difference between the feature vector (sample) under consideration and its nearest neighbor. Multiply this difference by a random number between 0 and 1, and add it to the feature vector under consideration. This causes the selection of a random point along the line segment between two specific features.”

Deutsche Uebersetzung (arbeitseigen): „Wir schlagen einen Oversampling-Ansatz vor, bei dem die Minderheitsklasse durch das Erzeugen synthetischer Beispiele vergroessert wird — nicht durch Oversampling mit Zuruecklegen. […] Wir arbeiten weniger anwendungsspezifisch im Merkmalsraum statt im Datenraum: Fuer jeden Datenpunkt der Minderheitsklasse werden entlang der Verbindungsstrecken zu seinen k naechsten Klassennachbarn synthetische Beispiele eingefuegt. Je nach benoetigter Oversampling-Menge werden aus den k naechsten Nachbarn zufaellig welche ausgewaehlt; unsere Implementierung verwendet derzeit fuenf naechste Nachbarn. […] Die synthetischen Punkte entstehen wie folgt: Die Differenz zwischen dem betrachteten Merkmalsvektor und seinem naechsten Nachbarn wird mit einer Zufallszahl zwischen 0 und 1 multipliziert und zum Ausgangsvektor addiert — das ergibt einen zufaelligen Punkt auf der Verbindungsstrecke zwischen den beiden Merkmalsvektoren.”

Passung: Direkter Beleg fuer Kap. 4.4 Aussage 1 des Manuskripts (SMOTE-Grundprinzip, k = 5, Interpolation zwischen Punkt und zufaellig gewaehltem Nachbarn). Vorschlag Marker: \cite[S.~328, Sec.~4.2]{CBHK02}.

Zitat 2 — Kombination Oversampling + Undersampling (Buch-S. 331, Sec. 4.3 Under-sampling and SMOTE Combination)

„The majority class is under-sampled by randomly removing samples from the majority class population until the minority class becomes some specified percentage of the majority class. This forces the learner to experience varying degrees of under-sampling and at higher degrees of under-sampling the minority class has a larger presence in the training set. […] By applying a combination of under-sampling and over-sampling, the initial bias of the learner towards the negative (majority) class is reversed in the favor of the positive (minority) class. Classifiers are learned on the dataset perturbed by ‚SMOTING’ the minority class and under-sampling the majority class.”

Deutsche Uebersetzung (arbeitseigen): „Die Mehrheitsklasse wird durch zufaelliges Entfernen von Datenpunkten so weit reduziert, bis die Minderheitsklasse einen vorgegebenen Prozentsatz der Mehrheitsklasse ausmacht. Dadurch erfaehrt der Lerner unterschiedliche Undersampling-Grade; bei staerkerem Undersampling ist die Minderheitsklasse im Trainingsdatensatz staerker vertreten. […] Durch die Kombination aus Under- und Oversampling wird der ursprueng­liche Bias des Lerners zugunsten der negativen (Mehrheits-)Klasse in einen Bias zugunsten der positiven (Minderheits-)Klasse umgekehrt. Die Klassifikatoren werden auf dem Datensatz trainiert, der durch ‚SMOTING’ der Minderheits- und Undersampling der Mehrheitsklasse gestoert wurde.”

Passung: Direkter Beleg fuer Kap. 4.4 Aussage 2 des Manuskripts (Kombination mit Undersampling zur ausgeglicheneren Trainingsverteilung). Vorschlag Marker: \cite[S.~331, Sec.~4.3]{CBHK02}.

Zitat 3 — Motivation gegen Replikation (Buch-S. 328, Sec. 4.1)

„If we replicate the minority class, the decision region for the minority class becomes very specific and will cause new splits in the decision tree. This will lead to more terminal nodes (leaves) as the learning algorithm tries to learn more and more specific regions of the minority class; in essence, overfitting. Replication of the minority class does not cause its decision boundary to spread into the majority class region.”

Passung: Erklaerung, warum synthetische Interpolation der reinen Replikation vorzuziehen ist — relevant fuer den Uebergang zur Fallstudie PNRB15 (Kap. 5.3), in der ebenfalls interpolierte SMOTE-Beispiele verwendet werden.

Zitat 4 — ROC-Konvex-Huelle (Buch-S. 322, Sec. 2)

„The Area Under the Curve (AUC) is an accepted traditional performance metric for a ROC curve (Duda, Hart, & Stork, 2001; Bradley, 1997; Lee, 2000). The ROC convex hull can also be used as a robust method of identifying potentially optimal classifiers (Provost & Fawcett, 2001). If a line passes through a point on the convex hull, then there is no other line with the same slope passing through another point with a larger true positive (TP) intercept. Thus, the classifier at that point is optimal under any distribution assumptions in tandem with that slope.”

Passung: Belegt die Wahl von AUC und ROC-Konvex-Huelle als Bewertungsmetriken bei unbalancierten Klassen. Verknuepft mit Kap. 5.4 der Zulassungsarbeit (Profit-Metrik in PNRB15 setzt genau hier an, wo klassische Accuracy versagt).

Zitat 5 — Kern-Zusammenfassung (Buch-S. 352, Sec. 7 Summary)

„The results show that the SMOTE approach can improve the accuracy of classifiers for a minority class. […] The combination of SMOTE and under-sampling performs better than plain under-sampling. […] Out of a total of 48 experiments performed, SMOTE-classifier does not perform the best only for 4 experiments. […] Our method of synthetic over-sampling works to cause the classifier to build larger decision regions that contain nearby minority class points.”

Passung: Kernaussage zur Wirksamkeit von SMOTE — Basisreferenz fuer das SMOTE-Konzept in Kap. 4.4 der Zulassungsarbeit.

Bezug zur Zulassungsarbeit

Primaerquelle Nr. 5 (methodische Sach-Quelle). Konkret belegt CBHK02 die zwei offenen \beleg{CBHK02}-Stellen in Kap. 4.4: das SMOTE-Grundprinzip (Interpolation zwischen Minderheitspunkt und k naechsten Nachbarn, Standard k = 5; Zitat 1, S. 328) und die Kombination mit Random-Undersampling der Mehrheitsklasse (Zitat 2, S. 331). Der Uebergang zur Fallstudie PNRB15 (Kap. 5) ist inhaltlich konsistent: dort werden dieselben Prinzipien (SMOTE + Undersampling) mit hoeherem k (14–20) und groesseren Skalierungsfaktoren (700–1000 %) auf einen industriellen Random-Forest-Fall angewendet. Random Forests behandelt CBHK02 nicht explizit — die Baum-Argumentation im Paper stuetzt sich durchgaengig auf C4.5 (Quinlan 1992) und ist damit die konzeptuelle Vorstufe zur RF-Anwendung in PNRB15.

SUMMARY: SMOTE-Paper CBHK02 gelesen; zwei woertliche Zitate mit Buchseiten (S. 328 und S. 331) fuer die offenen Kap.-4.4-\beleg-Stellen dokumentiert.