POSSE-kNN: Pathwise Out-of-Bag Selected Subspace Ensembles for Binary Classification

Stellen Sie sich vor, Sie versuchen, den besten Weg durch einen dichten, nebligen Wald zu finden, um ein bestimmtes Ziel zu erreichen. In der Welt der Informatik ist das ein wenig wie „maschinelles Lernen“, bei dem Algorithmen versuchen, kluge Vermutungen basierend auf Daten anzustellen. Eine beliebte Art, dies zu tun, ist „k-Nearest Neighbors“ (kNN). Denken Sie bei kNN an einen Touristen, der die fünf nächsten Personen, die er sieht, nach dem Weg fragt. Wenn die meisten dieser fünf Leute „links abbiegen“ sagen, biegt der Tourist links ab. Das ist einfach und funktioniert gut in offenen Feldern, aber es kann in einem Wald mit gewundenen Pfaden verwirrend werden. Wenn die „Links-abbiegen“-Leute in einer langen, gekrümmten Linie stehen, könnte ein Tourist, der nur nach den Personen schaut, die ihm in einer geraden Linie am nächsten stehen, die ganze Gruppe übersehen und sich verlaufen.

Dieses Paper befasst sich genau mit diesem Problem: Wie helfen wir unserem digitalen Touristen, durch gekrümmte, tückische Pfade im Datenwald zu navigieren, ohne stecken zu bleiben? Die Forscher entwickeln eine bessere Version der „Frage die Nachbarn“-Strategie. Sie suchen nicht nur nach den nächsten Personen; sie suchen nach den Menschen, die in einer logischen Kette miteinander verbunden sind, wie Trittsteine über einem Bach. Sie verwenden auch einen cleveren Trick namens „Out-of-Bag“ (OOB)-Screening, was so ist, als ließe man eine Gruppe von Kundschaftern ihre eigenen Karten vor einer Übungsrunde testen, bevor die eigentliche Reise beginnt, und behält nur die Karten, die sie nicht verloren haben.

Die Geschichte des Papers: Ein besserer Weg, den Pfad zu finden

Die Forscher, Zardad Khan und sein Team, stellten eine neue Methode namens POSSE-kNN vor. Sie können sich das als ein Super-Team von Entdeckern vorstellen, die versuchen, ein Rätsel zu lösen. Anstatt dass ein einzelner Entdecker auf die Karte schaut, erschaffen sie 500 verschiedene „Kandidaten“-Entdecker. Jeder von ihnen ist ein wenig anders: Sie betrachten den Wald durch eine leicht unterschiedliche Linse (zufällige Merkmals-Subräume) und nehmen einen einzigartigen Pfad, um ihre Nachbarn zu finden.

So funktioniert ihre spezielle „Pathwise“-Methode (pfadbasierte Methode): Stellen Sie sich vor, Sie sind der Entdecker, der an einem Abfragepunkt (dem Ort, an dem Sie eine Entscheidung treffen müssen) steht.

1. Der erste Schritt: Sie schauen sich um und finden die dem Sie am nächsten stehende Person.
2. Die Kettenreaktion: Anstatt nach der nächsten Person zu suchen, die Ihnen am nächsten steht, suchen Sie nach der Person, die der ersten Person, die Sie gerade gefunden haben, am nächsten steht. Dann finden Sie die Person, die der diesen Person am nächsten steht.
3. Der Pfad: Sie führen dies fort, bis Sie eine Kette von $k$ Personen haben. Dies erzeugt einen „Pfad“, der der lokalen Form der Menge folgt, selbst wenn diese Menge gekrümmt oder verdreht ist. Dies ist viel klüger, als einfach die fünf Personen zu wählen, die Ihnen in einer geraden Linie am nächsten stehen, da diese alle in einem seltsamen, wenig hilfreichen Cluster stehen könnten.

Aber warten Sie, 500 Entdecker sind viel Lärm. Einige könnten schlecht darin sein, zu navigieren. Deshalb nutzt das Team das Out-of-Bag (OOB)-Screening. Vor dem endgültigen Rennen schickt das Team jeden der 500 Entdecker auf eine Übungsrunde unter Verwendung eines Datensatzes, mit dem sie nicht trainiert wurden. Wenn sich ein Entdecker während der Übung verirrt, fliegt er aus dem Team. Die Forscher behielten die besten 25 % der Entdeker (die besten 125 von 500) und ließen sie über die endgültige Antwort abstimmen. Es ist wie eine Reality-Show, in der die Juroren die Teilnehmer eliminieren, die die Herausforderung nicht bestanden haben, sodass nur die Champions übrig bleiben, um den Gewinner zu bestimmen.

Was sie herausgefunden haben

Das Team testete diese neue POSSE-kNN-Methode an zehn verschiedenen Datensätzen (das sind wie zehn verschiedene Arten von Wäldern, die von kleinen medizinischen Aufzeichnungen bis hin zu größeren Ingenieursdaten reichen). Sie verglichen sie mit sechs anderen etablierten Methoden, einschließlich Standard-kNN, Random Forests und Support Vector Machines (SVM).

Die Ergebnisse waren sehr vielversprechend. Über alle Bereiche hinweg schnitt POSSE-kNN in den Gesamtranglisten am besten ab.

• Genauigkeit (Accuracy): Es traf im Durchschnitt 0,740 Mal die richtige Antwort. Dies war der höchste Wert unter allen getesteten Methoden.
• Zuverlässigkeit: Es erzielte auch die besten Werte bei Cohen's Kappa (0,412), einem Maß dafür, wie gut die Methode mit der Wahrheit übereinstimmt, und beim Brier-Score (0,175), der misst, wie sicher und korrekt seine Wahrscheinlichkeitsschätzungen waren.

Die Methode belegte den ersten Platz oder teilte sich den ersten Platz bei acht von zehn Datensätzen. Das Paper ist jedoch vorsichtig damit, nicht zu behaupten, dass es ein Allheilmittel für alles sei. Bei zwei spezifischen Datensätzen (einer namens ILPD und einem namens Chscase Vine) schnitten andere Methoden etwas besser ab. Beispielsweise war bei den Chscase-Vine-Daten eine lineare Methode namens SVM besser, was darauf hindeutet, dass der „Wald“ manchmal tatsächlich eine gerade Linie ist und ein komplexer Pfad nicht benötigt wird.

Die Frage nach der Anzahl der Nachbarn

Die Forscher spielten auch mit der Größe der Gruppe und änderten die Anzahl der Nachbarn ($k$) auf 3, 5 oder 7. Sie fanden heraus, dass die Methode für einige Wälder (wie den „Heart“-Datensatz) hervorragend funktionierte, egal welche Zahl sie wählten. Aber für andere (wie „ILPD“) half die Änderung der Anzahl nicht viel, und manchmal war eine andere Strategie besser. Dies deutet darauf hin, dass die Pfadmethode zwar leistungsstark ist, man aber dennoch die Einstellungen je nach dem spezifischen Problem anpassen muss, das man löst.

Das Fazit

Das Paper kommt zu dem Schluss, dass POSSE-kNN ein starkes, wettbewerbsfähiges Werkzeug ist. Es legt nahe, dass wir durch die Kombination einer „Trittstein“-Art, Nachbarn zu finden, mit einem strengen „Übungsrunde“-Filter bessere Klassifikatoren für schwierige Daten aufbauen können. Es behauptet nicht, alle Probleme in der Welt des maschinellen Lernens gelöst zu haben, aber es zeigt, dass es oft eine bessere Idee ist, einem Pfad zu folgen, anstatt nur zu schauen, wer einem in einer geraden Linie am nächsten steht, wenn die Daten gekrümmt und komplex sind. Die Autoren merken an, dass zukünftige Arbeiten untersuchen sollten, wie man dies noch schneller macht und wie man die Einstellungen automatisch feinabstimmt, aber für den Moment ist es ein solider Schritt nach vorn, um Computern zu helfen, durch die unordentlichen, gewundenen Wälder der realen Daten zu navigieren.