SMOTE — Chawla, Bowyer, Hall, Kegelmeyer (2002)
PDF: https://studium.alexium-core.de/01_arbeiten/01_zulassungsarbeit/B_literatur/pdfs/CBHK02.pdf
Rechtsstatus
Open Access via Journal of Artificial Intelligence Research (JAIR). Kann als Anlage der Zulassungsarbeit im Abgabeordner beigelegt werden.
Bibliographische Angaben
Journal-Paper in Journal of Artificial Intelligence Research Band 16, S. 321-357, 2002. Herausgegeben von AI Access Foundation und Morgan Kaufmann Publishers. DOI: 10.1613/jair.953.
- Nitesh V. Chawla — Department of Computer Science and Engineering, University of South Florida, Tampa
- Kevin W. Bowyer — Department of Computer Science and Engineering, University of Notre Dame, Indiana
- Lawrence O. Hall — Department of Computer Science and Engineering, University of South Florida, Tampa
- W. Philip Kegelmeyer — Sandia National Laboratories, Livermore, Kalifornien
Beschaffung
- JAIR Open Access, kostenfrei als PDF verfuegbar
- Status: ☑ beschafft ☑ gelesen ☑ zitierte Stellen im PDF markiert
Methodik / Charakter der Quelle
Peer-reviewed Methoden-Paper mit empirischer Evaluation. Fuehrt das SMOTE-Verfahren (Synthetic Minority Over-sampling TEchnique) ein: Statt Minderheitsklassen-Beispiele mit Zuruecklegen zu vervielfachen, werden synthetische Beispiele durch lineare Interpolation im Merkmalsraum zwischen einem Minderheitspunkt und einem seiner k naechsten Klassenkameraden (Standard k = 5) erzeugt. Die Kombination mit Random-Undersampling der Mehrheitsklasse wird auf 9 Datensaetzen und 3 Klassifikatoren (C4.5, Ripper, Naive Bayes) getestet und mit reinem Undersampling, Loss-Ratio-Variation und Prior-Variation verglichen. Bewertung ueber ROC-Kurven, AUC und ROC-Konvex-Huelle (Provost & Fawcett).
Kernbeitraege:
- SMOTE-Algorithmus (S. 328–329, Pseudocode); Standard k = 5
- Kombination von SMOTE-Oversampling mit Random-Undersampling der Mehrheitsklasse (S. 331)
- ROC- und AUC-basierte Evaluation statt Accuracy (S. 322–323)
- Erweiterungen: SMOTE-NC fuer gemischt numerisch/nominale Daten (Sec. 6.1, S. 348) und SMOTE-N fuer rein nominale Daten mit Value Difference Metric (Sec. 6.2, S. 349)
Kernaussagen
- SMOTE-Grundprinzip (S. 328): Fuer jeden Minderheitspunkt werden die k naechsten Minderheits-Nachbarn im Merkmalsraum bestimmt (Implementierung k = 5); zwischen Punkt und zufaellig gewaehltem Nachbarn wird ein Zufallspunkt (Faktor gap ∈ [0,1]) auf der Verbindungsstrecke als synthetischer Datenpunkt eingefuegt.
- Kombination mit Undersampling (S. 331): Die Mehrheit wird per Zufalls-Entfernen reduziert, bis die Minderheit einen vorgegebenen Prozentsatz der Mehrheit erreicht; der Klassifikations-Bias wird dadurch zugunsten der Minderheit umgekehrt.
- Interpolation statt Replikation (S. 326–328, Fig. 3–4): Reine Replikation erzeugt sehr kleine, spezifische Blattregionen (Overfitting, groessere Baeume); SMOTE dagegen zwingt den Klassifikator zu groesseren, allgemeineren Entscheidungsregionen.
- Bewertungsmetrik (S. 322–323): ROC-Kurven, AUC via Trapezregel, ROC-Konvex-Huelle nach Provost & Fawcett (2001). Punkte auf der Konvex-Huelle sind unabhaengig von Kostenverteilung potenziell optimal.
- Empirisches Hauptergebnis (S. 339 + S. 352): In 44 von 48 Experimenten dominiert SMOTE + Undersampling im ROC-Raum das reine Undersampling. Ausnahmen: Pima (Naive Bayes gewinnt), Oil (Under-Ripper besser), Can (Ueberlappung).
- Typische Skalierung (S. 331 + Tab. 3, S. 345): SMOTE 100–500 %, Undersampling 10–2000 %; optimale Werte variieren datensatzabhaengig stark (Mammography 400 %, Oil 500 %, Adult 50 %).
- Baum-Klassifikator-Bezug: Alle bauminternen Argumente stuetzen sich auf C4.5 (Quinlan 1992) — Random Forests kommen im Paper nicht vor.
AUC-Werte (Tab. 3, S. 345 — C4.5 als Basisklassifikator)
Werte skaliert x10000, Bestwerte fett:
| Dataset | Under | 50 SMOTE | 100 SMOTE | 200 SMOTE | 300 SMOTE | 400 SMOTE | 500 SMOTE |
|---|---|---|---|---|---|---|---|
| Pima | 7242 | 7307 | |||||
| Phoneme | 8622 | 8644 | 8661 | ||||
| Satimage | 8900 | 8957 | 8979 | 8963 | 8975 | 8960 | |
| Forest Cover | 9807 | 9832 | 9834 | 9849 | 9841 | 9842 | |
| Oil | 8524 | 8523 | 8368 | 8161 | 8339 | 8537 | |
| Mammography | 9260 | 9250 | 9265 | 9311 | 9330 | 9304 | |
| E-state | 6811 | 6792 | 6828 | 6784 | 6788 | 6779 | |
| Can | 9535 | 9560 | 9505 | 9505 | 9494 | 9472 | 9470 |
Woertliche Zitate (Reserve)
Zitat 1 — SMOTE-Grundprinzip (S. 328):
„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. […] Our implementation currently uses five nearest neighbors. […] 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.” (S. 328)
Zitat 2 — Kombination mit Undersampling (S. 331):
„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. […] 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.” (S. 331)
Zitat 3 — Replikation vs. Synthese (S. 328):
„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.” (S. 328)
Zitat 4 — Empirisches Kernergebnis (S. 352):
„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.” (S. 352)
Bezug zur Zulassungsarbeit
Primaerquelle Nr. 5 (methodische Sach-Quelle) fuer Kap. 4.4 der Zulassungsarbeit. Belegt die zwei offenen \beleg{CBHK02}-Stellen mit Buchseiten:
- Kap. 4.4 (SMOTE-Grundprinzip):
\cite[S.~328, Sec.~4.2]{CBHK02}— Interpolation zwischen Datenpunkt und k = 5 zufaellig gewaehlten Nachbarn. - Kap. 4.4 (Kombination mit Undersampling):
\cite[S.~331, Sec.~4.3]{CBHK02}— Random-Undersampling der Mehrheit zur Bias-Umkehr.
Bruecke zur Fallstudie PNRB15 (Kap. 5): Prytz et al. verwenden dasselbe Verfahren (SMOTE + Undersampling) mit hoeherem k (14–20) und 700–1000 % Oversampling in einem Random-Forest-Setting.
Verwandte Quellen
- PNRB15 — verwendet SMOTE + Undersampling in der industriellen RF-Anwendung (Kap. 5.3 der Zulassungsarbeit)
- BFOS84 — CART als konzeptuelle Basis der Baum-Argumentation im Paper (via Quinlan 1992 / C4.5)
- Bre01 — Random Forests, die im Paper nicht behandelt werden, aber in PNRB15 mit SMOTE kombiniert werden