Zum Inhalt springen
Zurück zu den Suchergebnissen

Semi-supervised K-Nearest Neighbors

Eingeführt von
Zhu, X. & Ghahramani, Z. (label propagation); Cover, T. & Hart, P. (KNN base)
Jahr
2002 (semi-supervised extension); 1967 (KNN base)
Typ
Semi-supervised classifier / label propagation
Familie
Machine learning

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Semi-supervised KNN erweitert den klassischen K-Nearest Neighbors-Algorithmus, um große Mengen unbeschrifteter Daten neben einem kleinen Satz beschrifteter Daten zu nutzen.

Durch den Aufbau eines KNN-Graphen über alle Beobachtungen und die Weitergabe bekannter Beschriftungen über die Kanten des Graphen leitet die Methode Beschriftungen für unbeschriftete Punkte ab, ohne dass eine teure manuelle Annotation jedes Samples erforderlich ist.

Die Intuition hinter der Methode

Stellen Sie sich ein Klassenzimmer vor, in dem nur eine Handvoll Schüler Namensschilder hat und der Rest anonym ist. Standard-KNN kann einen anonymen Schüler nur klassifizieren, indem es die Handvoll beschrifteter Nachbarn in der Nähe betrachtet. Semi-supervised KNN hingegen bildet den gesamten Raum als Netzwerk ab – jeder Schüler ist mit seinen nächsten Nachbarn verbunden – und verbreitet Beschriftungen von den beschrifteten Schülern nach außen, wie Tinte, die sich durch nasses Papier ausbreitet. Da das Netzwerk die Gesamtstruktur der Daten erfasst, erreichen die Beschriftungen unbeschriftete Punkte auf prinzipielle Weise, die die zugrunde liegende Geometrie respektiert, anstatt die unbeschriftete Mehrheit zu ignorieren.

Geschichte

Die Weitergabe von Beschriftungen auf KNN-Graphen wurde 2002 von Zhu und Ghahramani systematisiert, aufbauend auf Vapniks transduktiver SVM und früheren graphbasierten Diffusionsideen. Das Framework wurde im Band Semi-Supervised Learning (Chapelle et al., 2006) von MIT Press konsolidiert, der weiterhin als Standardreferenz gilt. Skalierbare approximative KNN-Bibliotheken (FAISS, Annoy) machten den Ansatz später auf Millionen von Punkten praktikabel, und er wird weiterhin als starke Baseline für die semi-überwachte Bild- und Textklassifizierung verwendet.

Wann wird sie eingesetzt?

Verwenden Sie semi-supervised KNN, wenn Sie einen kleinen beschrifteten Datensatz und einen großen unbeschrifteten Pool aus derselben Verteilung haben, die Daten in einem relativ niedrigdimensionalen Raum liegen (weniger als etwa 50 Merkmale) und Sie glauben, dass benachbarte Punkte zur selben Klasse gehören. Es eignet sich gut für die Klassifizierung von Bildausschnitten, die Textkategorisierung mit spärlichen Annotationen und medizinische Screening-Aufgaben, bei denen die Expertenbeschriftung teuer ist. Vermeiden Sie es, wenn beschriftete und unbeschriftete Daten aus unterschiedlichen Verteilungen stammen (Kovariatenverschiebung), der Merkmalsraum sehr hochdimensional ist (der KNN-Graph wird unzuverlässig), der Datensatz klein genug ist, dass ein vollständig überwachtes KNN bereits ausreicht, oder die Klassengrenzen nicht mit der lokalen Dichtestruktur der Daten übereinstimmen.

Grenzen und Hinweise

  • Die Graphkonstruktion skaliert quadratisch mit der Datensatzgröße, es sei denn, es werden approximative Nearest-Neighbor-Methoden verwendet.
  • Die Leistung verschlechtert sich in hochdimensionalen Räumen, in denen Distanzmetriken ihre Trennschärfe verlieren.
  • Geht davon aus, dass beschriftete und unbeschriftete Daten aus derselben Verteilung stammen; Kovariatenverschiebung bricht die Methode.
  • Erfordert sorgfältige Abstimmung von k, der Bandbreite der Kantengewichte und dem Mischparameter der Weitergabe.
  • Die Weitergabe von Beschriftungen kann anfängliche Beschriftungsfehler über große Teile des Graphen verstärken.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Nutzt günstige unbeschriftete Daten, um die Genauigkeit über das hinaus zu verbessern, was mit dem beschrifteten Datensatz allein möglich ist.
  • Keine parametrischen Modellannahmen: stützt sich nur auf die lokale Nachbarschaftsgeometrie.
  • Behandelt Mehrklassenprobleme natürlich ohne Modifikation.
  • Die Konstruktion des KNN-Graphen ist transparent und leicht zu inspizieren.
  • Funktioniert gut, wenn Klassen kompakte, gut getrennte Cluster im Merkmalsraum bilden.

Anwendungen

  • Bildklassifizierung mit einem kleinen Satz beschrifteter Bilder und einem großen unbeschrifteten Korpus.
  • Text- und Dokumentenkategorisierung, bei der manuelle Beschriftung teuer ist.
  • Klassifizierung von Krankenakten oder pathologischen Schnitten mit begrenzten Expertenannotationen.
  • Betrugserkennung, wenn nur eine kleine Anzahl bestätigter Betrugsfälle verfügbar ist.
  • Beschriftung von Sensordaten in industriellen IoT-Umgebungen mit spärlichen Ground-Truth-Ereignissen.

So funktioniert es

So funktioniert es

1

Ein Graph wird über alle Beobachtungen – sowohl beschriftete als auch unbeschriftete – aufgebaut. Jeder Knoten entspricht einem Datenpunkt, und gerichtete oder ungerichtete Kanten verbinden jeden Knoten mit seinen k nächsten Nachbarn im Merkmalsraum. Die Wahl von k steuert, wie lokal oder global Beschriftungen weitergegeben werden: kleines k hält die Weitergabe eng; großes k erlaubt Beschriftungen, über größere Lücken zu springen.

2

Kantengewichte erfassen die Stärke der Ähnlichkeit zwischen verbundenen Knoten, typischerweise über einen Gaußschen (RBF) Kernel, der auf die euklidische Distanz zwischen Merkmalsvektoren angewendet wird. Ein Bandbreitenparameter sigma steuert, wie schnell die Ähnlichkeit mit der Entfernung abnimmt. Stärkere Kanten übertragen Beschriftungen während der Weitergabe leichter.

Formel
w_{ij} = \exp(-\|x_i - x_j\|^2 / \sigma^2)
3

Beschriftungen werden iterativ von beschrifteten Knoten zu unbeschrifteten Nachbarn verbreitet. In jeder Iteration aktualisiert jeder Knoten seine weiche Beschriftungsverteilung als gewichtete Kombination der aktuellen Verteilungen seiner Nachbarn und seiner eigenen ursprünglichen Beschriftung (falls beschriftet). Ein Mischparameter alpha gleicht den Einfluss der Graphenstruktur gegenüber den harten Beschriftungen aus, und die Iteration wird fortgesetzt, bis die Verteilungen konvergieren.

Formel
F \leftarrow \alpha W D^{-1} F + (1-\alpha) Y
4

Sobald die Weitergabe konvergiert ist, wird jedem unbeschrifteten Knoten die Klasse mit dem höchsten Soft-Label-Score in seiner konvergierten Verteilung zugewiesen. Beschriftete Knoten werden während des gesamten Prozesses auf ihre wahren Beschriftungen fixiert, sodass bekannte Beschriftungen niemals überschrieben werden.

Formel
\hat{y}_i = \arg\max_c F_{ic}

Häufige Fallstricke

  • Konstruktion des KNN-Graphen ohne Normalisierung der Merkmale, wodurch Merkmale mit hoher Varianz die Distanzberechnungen dominieren.
  • Festlegen von k zu groß, was echte Klassengrenzen verwischt und übermäßig geglättete Beschriftungsverteilungen erzeugt.
  • Ignorieren der Möglichkeit, dass unbeschriftete Daten außerhalb der Verteilung im Verhältnis zum beschrifteten Datensatz liegen.
  • Berichterstattung über die Genauigkeit auf unbeschrifteten Knoten, als ob es sich um eine unverzerrte Testschätzung handelt – unbeschriftete Knoten sind während des Trainings in den Graphen eingeflossen.
  • Überspringen von Konvergenzprüfungen und Verwendung einer festen, willkürlichen Anzahl von Weitergabeiterationen.

Häufig gestellte Fragen

Wie wähle ich k?

Beginnen Sie mit k im Bereich von 5-15 und stimmen Sie durch die Genauigkeit auf einem zurückgehaltenen beschrifteten Validierungsdatensatz ab. Kleineres k ergibt schärfere, lokalere Grenzen; größeres k erlaubt Beschriftungen, weiter zu propagieren, birgt aber das Risiko, echte Klassengrenzen zu überschreiten.

Kann ich die Methode ehrlich bewerten, wenn die meisten Daten unbeschriftet sind?

Halten Sie einen separaten beschrifteten Testdatensatz zurück, der niemals zum Graphen hinzugefügt wird. Knoten im Graphen – auch unbeschriftete – sind Teil des Trainings, daher darf kein beschrifteter Knoten, der an der Graphkonstruktion teilnimmt, auch als Testpunkt dienen.

Was ist, wenn mein Datensatz zu groß ist, um einen vollständigen KNN-Graphen zu erstellen?

Verwenden Sie approximative Nearest-Neighbor-Bibliotheken wie FAISS oder Annoy, um den Graphen in O(n log n) statt O(n^2) zu konstruieren, und wenden Sie dann die Label-Propagation auf den spärlichen approximativen Graphen an.

Übertrifft semi-supervised KNN immer supervised KNN?

Nicht unbedingt. Wenn unbeschriftete Daten außerhalb der Verteilung liegen oder der Merkmalsraum sehr hochdimensional ist, ist der Graph verrauscht und die Weitergabe kann die Leistung beeinträchtigen. Vergleichen Sie immer mit einer überwachten KNN-Baseline, bevor Sie einen Vorteil durch unbeschriftete Daten behaupten.

Ist das dasselbe wie Label Spreading oder Label Propagation in scikit-learn?

Eng verwandt. Scikit-learns LabelPropagation und LabelSpreading implementieren den Rahmen von Zhu und Ghahramani unter Verwendung eines KNN- oder RBF-Kernel-Graphen, sodass sie direkte Implementierungen der hier beschriebenen Methode sind.

Verwandte Methoden

Quellen

  1. Zhu, X. & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    Publikationsreferenz öffnen
    Kopiert.
  2. Chapelle, O., Scholkopf, B. & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    Kopiert.