Wann ist „Nächster Nachbar“ heute sinnvoll?

1999 stellten Beyer et al. gefragt, wann ist "Nächster Nachbar" sinnvoll?

Gibt es seit 1999 bessere Möglichkeiten zur Analyse und Visualisierung der Auswirkung der Abstandsflachheit auf die NN-Suche?

Bietet [ein gegebener] Datensatz aussagekräftige Antworten auf das 1-NN-Problem? Das 10-NN-Problem? Das 100-NN-Problem?

Wie würden Sie Experten diese Frage heute angehen?

Änderungen Montag, 24. Januar:

Wie wäre es mit "Abstand Whiteout" als kürzere Bezeichnung für "Abstand Ebenheit mit zunehmender Dimension"?

Ein einfacher Weg, um "Entfernungs-Whiteout" zu betrachten, besteht darin, 2-NN auszuführen und Entfernungen zum nächsten Nachbarn und zum zweitnächsten Nachbarn zu zeichnen. Das folgende Diagramm zeigt dist ₁ und dist ₂ für einen Bereich von n-Clustern und Dimensionen von Monte Carlo. Dieses Beispiel zeigt einen ziemlich guten Abstandskontrast für die skalierte absolute Differenz | dist ₂ - dist ₁ |. (Die relativen Differenzen | dist ₂ / dist ₁ | → 1 als Dimension → ∞ werden also unbrauchbar.)

Ob in einem gegebenen Kontext absolute oder relative Fehler verwendet werden sollten, hängt natürlich vom "realen" vorhandenen Rauschen ab: schwierig.

Vorschlag: immer 2-NN ausführen; 2 Nachbarn sind nützlich, wenn sie in der Nähe sind, und nützlich, wenn nicht.

Bildbeschreibung hier eingeben

machine-learning k-nearest-neighbour denis
quelle

Beyer et al. scheinen einen etwas anderen Aspekt des NN-Problems anzusprechen. Für (binäre) Klassifikationszwecke ist es jedoch ein klassisches Ergebnis, dass die 1-NN-Klassifikation im schlimmsten Fall die doppelte Fehlerwahrscheinlichkeit des Bayes-Klassifikators (dh des optimalen Klassifikators) asymptotisch aufweist. Mit anderen Worten, der erste nächste Nachbar enthält "mindestens die Hälfte der Informationen" über die Bezeichnung des Ziels, wie dies der beste Klassifikator tut. In diesem Sinne scheint das 1-NN ziemlich relevant zu sein. (Siehe Cover & Hart (1967) für mehr. Ich bin überrascht, dass Beyer et al. Es nicht zitieren.)

Kardinal

@cardinal, die Cover-Hart-Bindung scheint überhaupt nicht von der Dimension abzuhängen, wie sagt man einen anderen Aspekt?

Denis

Ja, ich glaube, das ist wahr, und dies war größtenteils mein Argument, es zur Sprache zu bringen. 1-NN scheint in diesem Sinne ziemlich relevant zu sein, dh die Tatsache, dass es in der Dimension des Merkmalsraums (so) gut (theoretisch) einheitlich funktioniert, scheint ihm dabei zu helfen, für sich zu stehen, unabhängig davon, wie sich das nächste und das nächste verhalten Die am weitesten entfernten Nachbarn befinden sich in einem großen Raum. Ich frage mich, ob Beyer sich dieses (klassischen) Ergebnis überhaupt bewusst war.

Kardinal

@ cardinal Der Anfang von Seite 24 in Cover und Hart sieht aus wie eine Stelle, an der möglicherweise ein Problem in ihrem Beweis auftaucht, in dem Schritt, in dem Cover und Hart argumentieren, dass jedes RV x \ in X die Eigenschaft hat, die jede offene Kugel um x hat Nicht-Null-Maß. Wenn wir die Geometrie der Hypersphäre betrachten, sehen wir, dass das Volumen des Inneren der Hypersphäre mit zunehmender Dimension kleiner wird, so dass die offene Kugel um x im Inneren nur x enthält. Alternativ dazu liegen über die SLLN die iid-RVs x im metrischen Raum X alle mit der Wahrscheinlichkeit eins auf der Oberfläche der Hypersphäre.

Bob Durrant

Siehe auch L1- oder L.5-Metriken für Clustering .

Denis

Antworten:

Ich habe keine vollständige Antwort auf diese Frage, kann jedoch auf einige analytische Aspekte eine teilweise Antwort geben. Warnung: Ich habe seit dem ersten Artikel unten an anderen Problemen gearbeitet. Es ist also sehr wahrscheinlich, dass es noch andere gute Dinge gibt, die mir nicht bekannt sind.

Zunächst ist anzumerken, dass Beyer et al. Trotz der Überschrift "Wann ist der nächste Nachbar sinnvoll?" Tatsächlich eine andere Frage beantworteten, nämlich wann ist NN nicht sinnvoll? Wir haben das Gegenteil zu ihrem Theorem unter einigen zusätzlichen milden Annahmen über die Größe der Stichprobe in Wann ist 'nächster Nachbar' sinnvoll: Ein umgekehrter Theorem und Implikationen bewiesen. Journal of Complexity, 25 (4), August 2009, S. 385–397.und zeigten, dass es Situationen gibt, in denen (theoretisch) keine Konzentration von Entfernungen auftritt (wir geben Beispiele an, aber im Wesentlichen muss die Anzahl der Nichtrauschmerkmale mit der Dimensionalität wachsen, sodass sie in der Praxis selten auftreten). Die Referenzen 1 und 7, die in unserem Aufsatz zitiert werden, geben einige Beispiele dafür, wie die Entfernungskonzentration in der Praxis gemindert werden kann.

In einem Artikel meines Vorgesetzten, Ata Kaban, wird untersucht, ob diese Probleme mit der Entfernungskonzentration trotz der Anwendung von Dimensionalitätsreduktionstechniken im Abschnitt Über das Bewusstsein für Entfernungskonzentration bei bestimmten Datenreduktionstechniken bestehen . Mustererkennung. Vol. 44, Ausgabe 2, Februar 2011, S. 265–277. . Es gibt auch ein paar nette Diskussionen.

$k$

Bob Durrant
quelle

Danke Bob, +1. Zugehörige Frage: Hätten Sie eine Faustregel für die Auswahl eines Werts für die gebrochene Metrik q (oder sollte ich das als separate Frage stellen)?

Denis

q = 1 / p

$q=1/p$

p > 1

$p>1$

p

$p$

l_{0}

$l_0$

p = 1

$p=1$

l_{1}

$l_{1}$

l_{q = 1 / p}

$l_{q=1/p}$

p > 1

$p>1$

p

$p$

\sum | a_{j} - b_{j} |^{q}

$\sum |a_j - b_j|^q$

1 / q

$1/q$

< q <

$< q <$

ℓ_{p}

$\ell_{p}$

Sie könnten auch an der Analyse von Nachbarschaftskomponenten von Goldberger et al. Interessiert sein .

Hier wird eine lineare Transformation gelernt, um die erwarteten korrekt klassifizierten Punkte über eine stochastische Auswahl der nächsten Nachbarschaft zu maximieren.

Als Nebeneffekt wird aus den Daten die (erwartete) Anzahl der Nachbarn ermittelt.

bayerj
quelle

Danke bayer Es scheint, dass "Fernunterricht" boomt - scholar.goo hat seit 2008 50 Titel. Aber ist das Boom-Papier oder wird es wirklich gebraucht? Fußnote, der Code für nca lautet "Iterationen ... mindestens 100000 für gute Ergebnisse". In Fußnote 2 scheinen die meisten Arbeiten zum Fernunterricht eine Mahalanobis-Distanz zu modellieren. Würdest du andere Distanzmodelle kennen?

denis

Ich habe unterschiedliche Erfahrungen mit NCA - es läuft für mich normalerweise ziemlich schnell zusammen. Kasse "Dimensionsreduktion durch Lernen einer invarianten Abbildung" von LeCun und "Minimal Loss Hashing für kompakte Binärcodes" von Norouzi.

bayerj