Sie sagen, der Algorithmus ist: k-Nächster-Nachbar-Algorithmus mit k = Anzahl der verwendeten Trainingspunkte. Ich definiere dies als jms-k-nächster Nachbar .
Da die VC Dimension die größte Zahl der Ausbildungsstellen, die durch den Algorithmus mit zertrümmert werden können Zug Fehler 0, die VC - Dimension von jms-k-nearest-neighbor kann nur k oder 0 sein.
1 Trainingsinstanz => k = 1: Während des Trainings speichert der jms-1-next-neighbour genau diese Instanz. Während der Anwendung auf genau demselben Trainingssatz ist die eine Instanz der gespeicherten Trainingsinstanz am nächsten (da sie identisch sind), sodass der Trainingsfehler 0 ist.
Ich stimme also zu, dass die VC-Dimension mindestens 1 beträgt.
2 Trainingsinstanzen => k = 2: Möglicherweise liegt nur dann ein Problem vor, wenn die Bezeichnungen unterschiedlich sind. In diesem Fall stellt sich die Frage, wie die Entscheidung für ein Klassenlabel getroffen wird. Eine Mehrheitsentscheidung führt nicht zu einem Ergebnis (VC = 0?). Wenn wir eine Mehrheitsabstimmung verwenden, die umgekehrt nach Entfernung gewichtet ist, beträgt die VC-Dimension 2 (vorausgesetzt, es ist nicht zulässig, dieselbe Trainingsinstanz zweimal mit unterschiedlichen Bezeichnungen zu haben In diesem Fall wäre die VC-Dimension aller Algorithmen 0 (denke ich).
Es gibt keinen Standardalgorithmus für k-nächste Nachbarn, es handelt sich eher um eine Familie mit derselben Grundidee, aber unterschiedlichen Varianten, wenn es um Implementierungsdetails geht.
Verwendete Ressourcen: VC-Dimensionsfolien von Andrew Moore