Umgang mit Krawatten, Gewichten und Abstimmungen in kNN

Ich programmiere einen kNN-Algorithmus und möchte Folgendes wissen:

Unentschieden:

1. Was passiert, wenn bei der Mehrheitsabstimmung kein eindeutiger Gewinner feststeht? ZB sind alle k nächsten Nachbarn aus verschiedenen Klassen, oder für k = 4 gibt es 2 Nachbarn aus Klasse A und 2 Nachbarn aus Klasse B?
2. Was passiert, wenn es nicht möglich ist, genau k nächste Nachbarn zu bestimmen, weil es mehr Nachbarn gibt, die den gleichen Abstand haben? ZB für die Liste der Entfernungen (x1;2), (x2;3.5), (x3;4.8), (x4;4.8), (x5;4.8), (x6;9.2)wäre es nicht möglich, die nächsten Nachbarn k = 3 oder k = 4 zu bestimmen, da der dritte bis fünfte Nachbar alle den gleichen Abstand haben.

Gewichte:

1. Ich habe gelesen, dass es gut ist, die k-nächsten Nachbarn zu gewichten, bevor man die Gewinnerklasse auswählt. Wie funktioniert das? Dh wie werden die Nachbarn gewichtet und wie wird dann die Klasse ermittelt?

Mehrheitsentscheidungsalternativen:

1. Gibt es andere Regeln / Strategien zur Bestimmung der Gewinnerklasse als die Mehrheitsentscheidung?

Der ideale Weg, um ein Unentschieden für einen k nächsten Nachbarn zu lösen, ist meiner Ansicht nach, k um 1 zu verringern, bis Sie das Unentschieden gelöst haben. Dies funktioniert immer, unabhängig vom Stimmengewichtungsschema, da ein Gleichstand unmöglich ist, wenn k = 1. Wenn Sie k erhöhen , bis Ihr Gewichtungsschema und die Anzahl der Kategorien vorliegen, können Sie keinen Gleichstand garantieren.

Wenn Sie kNN ausführen, müssen Sie eines berücksichtigen, nämlich, dass es sich nicht um einen streng mathematisch abgeleiteten Algorithmus handelt, sondern um einen einfachen Klassifikator / Regressor, der auf einer Intuition basiert. Die zugrunde liegende Funktion ändert sich nicht wesentlich, wenn sich die Argumente nicht ändern viel. Mit anderen Worten, die zugrunde liegende Funktion ist lokal nahezu konstant. Mit dieser Annahme können Sie den Wert der zugrunde liegenden Funktion in einem bestimmten Punkt durch einen (möglicherweise gewichteten) Mittelwert der Werte der nächsten k Punkte schätzen.

Wenn Sie dies bedenken, können Sie erkennen, dass es keinen klaren Gebot gibt, was zu tun ist, wenn es keinen klaren Gewinner bei der Mehrheitsabstimmung gibt. Sie können entweder immer ein ungerades k oder eine injektive Gewichtung verwenden.

Wenn sich die Nachbarn 3 bis 5 im gleichen Abstand vom interessierenden Punkt befinden, können Sie entweder nur zwei oder alle 5 verwenden. Beachten Sie auch hier, dass kNN kein Algorithmus ist, der aus einer komplexen mathematischen Analyse abgeleitet wurde, sondern nur a einfache Intuition. Es liegt an Ihnen, wie Sie mit diesen Sonderfällen umgehen möchten.

$\frac{1}{||x-y||^2}$

In diesem Jahr haben Samory Kpotufe und Abdeslam Boularias auch eine schöne Abhandlung über NIPS veröffentlicht, die sich mit der Frage der richtigen Gewichtung befasst. Ihre allgemeine Intuition ist, dass die zugrunde liegende Funktion in verschiedene Richtungen unterschiedlich variiert (dh ihre verschiedenen partiellen Ableitungen sind unterschiedlich groß), daher wäre es in gewissem Sinne ratsam, die Metriken / Gewichtung gemäß dieser Intuition zu ändern. Sie behaupten, dass dieser Trick im Allgemeinen die Leistung der kNN- und Kernel-Regression verbessert, und ich denke, dass sie sogar einige theoretische Ergebnisse haben, um diese Behauptung zu untermauern (obwohl ich nicht sicher bin, was diese theoretischen Ergebnisse tatsächlich behaupten, hatte ich keine Zeit zu gehen durch das ganze Papier noch). Das Papier kann kostenlos von ihren Websites oder nach dem Googeln von "Gradient Weights help Nonparametric Regressors" heruntergeladen werden.

Jetzt werden Sie wahrscheinlich wissen wollen, wie Sie das richtige k, die richtige Metrik, Gewichtung und die richtige Aktion finden können, wenn es Draws und so weiter gibt. Das Traurige ist, dass es grundsätzlich schwierig ist, nach gründlichem Nachdenken zu den richtigen Hyperparametern zu gelangen. Wahrscheinlich müssen Sie verschiedene Gruppen von Hyperparametern testen, um zu sehen, welche bei einem Validierungssatz gut funktionieren. Wenn Sie über einige Rechenressourcen verfügen und automatisch zu den richtigen Parametern für einen guten Satz von Hyperparametern gelangen möchten, gibt es eine neue Idee (die mir sehr gefällt), Gaußsche Prozesse für die ableitungsfreie Optimierung in dieser Einstellung zu verwenden.

Lassen Sie mich näher darauf eingehen. Das Ermitteln des Satzes von Hyperparametern (dh das Minimieren von Fehlern bei Validierungsdaten) kann als Optimierungsproblem angesehen werden. Leider können wir in dieser Einstellung nicht den Gradienten der Funktion ermitteln, die wir optimieren möchten (was wir normalerweise tun möchten, um einen Gradientenabstieg oder einige fortgeschrittenere Methoden durchzuführen). In dieser Einstellung können Gauß-Prozesse verwendet werden, um Sätze von Hyperparametern zu finden, bei denen die Wahrscheinlichkeit groß ist, dass sie eine bessere Leistung erbringen als die besten, die wir bis jetzt gefunden haben. Daher können Sie den Algorithmus iterativ mit einer Reihe von Hyperparametern ausführen und dann den Gaußschen Prozess fragen, für welchen Sie es am besten als Nächstes versuchen, für welche und so weiter.

Weitere Informationen finden Sie in dem Artikel "Praktische Bayesianische Optimierung maschineller Lernalgorithmen" von Jasper Snoek, Hugo Larochelle und Ryan P Adams (ebenfalls auf deren Websites oder über Google zu finden).

In Bezug auf diesen Teil der Krawatte ist die beste Grundidee für Krawatten in der Regel das zufällige Brechen. Wählen Sie daher eine zufällige Klasse aus, die die Abstimmung gewinnt, und wählen Sie zufällig eine Untergruppe gebundener Objekte aus, die groß genug sind, um k zu füllen.

Eine solche Lösung unterstreicht die Tatsache, dass dies pathologische Fälle sind, die einfach nicht genügend Informationen liefern, um eine Entscheidung im kNN-Regime zu treffen. Übrigens, wenn sie Ihren Daten gemeinsam sind, sollten Sie vielleicht eine differenziertere Entfernung ausprobieren?

Eine Möglichkeit besteht darin, den Algorithmus automatisch k erhöhen oder verringern zu lassen, bis Sie einen eindeutigen Gewinner erhalten.