Euklidischer Abstand ist normalerweise nicht gut für spärliche Daten?

Ich habe irgendwo gesehen, dass klassische Entfernungen (wie die euklidische Entfernung) schwach diskriminierend werden, wenn wir mehrdimensionale und spärliche Daten haben. Warum? Haben Sie ein Beispiel für zwei spärliche Datenvektoren, bei denen die euklidische Distanz nicht gut funktioniert? In diesem Fall welche Ähnlichkeit sollten wir verwenden?

Hier ist ein einfaches Spielzeugbeispiel, das den Effekt der Dimension in einem Diskriminierungsproblem veranschaulicht, z. B. das Problem, mit dem Sie konfrontiert sind, wenn Sie sagen möchten, ob etwas beobachtet wird oder nur ein zufälliger Effekt beobachtet wird (dieses Problem ist ein Klassiker der Wissenschaft).

Heuristik. Das Hauptproblem hierbei ist, dass die euklidische Norm jeder Richtung die gleiche Bedeutung beimisst. Dies stellt einen Mangel an Vorkenntnissen dar, und wie Sie sicherlich in großen Dimensionen wissen, gibt es kein kostenloses Mittagessen (dh wenn Sie keine Ahnung haben, wonach Sie suchen, gibt es keinen Grund, warum ein Geräusch nicht so aussieht, wie Sie sind) auf der Suche nach, das ist Tautologie ...).

Ich würde sagen, dass es für jedes Problem eine Informationsgrenze gibt, die erforderlich ist, um etwas anderes als Lärm zu finden. Diese Grenze hängt in gewisser Weise mit der "Größe" des Gebiets zusammen, das Sie im Hinblick auf den "Geräusch" -Pegel (dh den Gehalt an nicht informativen Inhalten) erkunden möchten.

In großen Dimensionen können Sie, wenn Sie vorher festgestellt haben, dass Ihr Signal spärlich ist, nicht spärliche Vektoren mit einer Metrik entfernen (dh benachteiligen), die den Raum mit spärlichen Vektoren ausfüllt, oder mithilfe einer Schwellenwerttechnik.

Rahmen Angenommen, ein Gaußschen Vektor mit Mittelwert und diagonale Kovarianz ( bekannt ist ) und dass Sie die einfache Hypothese zu testen ,$\xi$$\nu$$\sigma Id$$\sigma$

Teststatistik mit Energie . Die Intuition, die Sie sicherlich haben, ist, dass es eine gute Idee ist, die Norm / Energie Ihrer Beobachtung , um eine Teststatistik zu erstellen. Tatsächlich können Sie eine standardisierte zentrierte (unter ) Version der Energie . Das macht einen kritischen Bereich auf Ebene der Form für ein gut ausgewähltes$\mathcal{E}_n=\frac{1}{n}\sum_{i=1}^n\xi_i^2$$\xi$$H_0$$T_n$$T_n=\frac{\sum_i\xi_i^2-\sigma^2}{\sqrt{2n\sigma^4}}$$\alpha$$\{T_n\geq v_{1-\alpha}\}$$v_{1-\alpha}$

Kraft der Prüfung und Dimension. In diesem Fall ist es eine einfache Wahrscheinlichkeitsübung, die folgende Formel für die Stärke Ihres Tests zu zeigen:

$$P_{\theta}(T\leq v_{1-\alpha})=P\left (Z\leq \frac{v_{1-\alpha}}{\sqrt{1+2\|\theta\|_2^2/(n\sigma^2)}}-\frac{\|\theta\|^2_2}{\sqrt{2n\sigma^4+2\sigma^2\|\theta\|_2^2/(n\sigma^2)}}\right )$$ mit eine Summe von iid Zufallsvariablen mit und .$Z$$n$$\mathbb{E}[Z]=0$$Var(Z)=1$

Dies bedeutet, dass die Leistung Ihres Tests um die Energie Ihres Signals und um verringert wird . In der Praxis bedeutet dies, dass Sie, wenn Sie die Größe Ihres Problems erhöhen und gleichzeitig die Signalstärke nicht erhöhen, Ihrer Beobachtung nicht aussagekräftige Informationen hinzufügen (oder den Anteil nützlicher Informationen in den Informationen verringern) Sie haben): Dies ist wie das Hinzufügen von Rauschen und reduziert die Leistung des Tests (dh es ist wahrscheinlicher, dass Sie sagen, dass nichts beobachtet wird, während tatsächlich etwas vorhanden ist).$\|\theta\|^2_2$$n$$n$

Auf dem Weg zu einem Test mit einer Schwellenwertstatistik. Wenn Sie nicht viel Energie in Ihrem Signal haben, aber eine lineare Transformation kennen, die Ihnen dabei hilft, diese Energie in einem kleinen Teil Ihres Signals zu konzentrieren, können Sie eine Teststatistik erstellen, die nur die Energie für die Kleinen auswertet Teil Ihres Signals. Wenn Sie im Voraus wissen, wo es konzentriert ist (zum Beispiel, dass es keine hohen Frequenzen in Ihrem Signal geben kann), können Sie im vorhergehenden Test eine Leistung erhalten, bei der durch eine kleine Zahl und fast ersetzt wird das gleiche ... Wenn Sie es nicht im Voraus wissen, müssen Sie es abschätzen, dies führt zu bekannten Schwellenwerttests.$n$$\|\theta\|^2_2$

Beachten Sie, dass dieses Argument genau die Wurzel vieler Papiere ist, wie z

• Ein Antoniadis, F. Abramovich, T. Sapatinas und B. Vidakovic. Wavelet-Methoden zur Funktionsanalyse von Varianzmodellen. International Journal on Wavelets and its applications, 93: 1007–1021, 2004.
• MV Burnashef und Begmatov. Ein Problem der Signalerkennung führt zu einer stabilen Verteilung. Wahrscheinlichkeitstheorie und ihre Anwendungen, 35 (3): 556–560, 1990.
• Y. Baraud. Nicht asymptotische Minimax-Testrate bei der Signalerkennung. Bernoulli, 8: 577–606, 2002.
• J Fan. Signifikanztest basierend auf Wavelet-Thresholding und Neyman-Trunkierung. JASA, 91: 674–688, 1996.
• J. Fan und SK Lin. Signifikanztest, wenn Daten Kurven sind. JASA, 93: 1007–1021, 1998.
• V. Spokoiny. Testen adaptiver Hypothesen unter Verwendung von Wavelets. Annals of Statistics, 24 (6): 2477–2498, Dezember 1996.

Ich glaube, es ist nicht so sehr die Sparsamkeit, sondern die hohe Dimensionalität, die normalerweise mit spärlichen Daten verbunden ist. Aber vielleicht ist es noch schlimmer, wenn die Daten sehr dünn sind. Denn dann ist der Abstand zweier Objekte wahrscheinlich ein quadratischer Mittelwert ihrer Länge, oder

Diese Gleichung ist trivial, wenn . Wenn Sie die Dimensionalität und Spärlichkeit so weit erhöhen, dass sie für fast alle Attribute gilt, ist der Unterschied minimal.$\forall_i x_i=0 \vee y_i=0$

Schlimmer noch: Wenn Sie Ihre Vektoren auf die Länge normiert haben , ist der euklidische Abstand zweier beliebiger Objekte mit hoher Wahrscheinlichkeit .$||x||=1$$\sqrt{2}$

So wie eine Faustregel für euklidischen Abstand sein verwendbar (Ich bin nicht nützlich oder sinnvoll behaupten) sollten die Gegenstände nicht Null in sein von Attributen. Dann sollte es eine vernünftige Anzahl von Attributen geben, bei denenso wird die Vektordifferenz nützlich. Dies gilt auch für alle anderen normbedingten Unterschiede. Weil in der Situation über$3/4$$|y_i| \neq |x_i-y_i| \neq |x_i|$$|x-y| \rightarrow_p |x + y|$

Ich denke nicht, dass dies ein wünschenswertes Verhalten ist, damit Distanzfunktionen weitgehend unabhängig von der tatsächlichen Differenz oder der absoluten Differenz werden, die zur absoluten Summe konvergiert!

Eine gebräuchliche Lösung ist die Verwendung von Abständen wie dem Kosinusabstand. Bei einigen Daten funktionieren sie sehr gut. Grob gesagt betrachten sie nur Attribute, bei denen beide Vektoren ungleich Null sind. Ein interessanter Ansatz wird in der unten stehenden Referenz besprochen (sie haben ihn nicht erfunden, aber ich mag ihre experimentelle Bewertung der Eigenschaften) ist die Verwendung von gemeinsamen nächsten Nachbarn. Selbst wenn die Vektoren x und y keine gemeinsamen Attribute haben, können sie gemeinsame Nachbarn haben. Das Zählen der Anzahl von Objekten, die zwei Objekte verbinden, hängt eng mit den Grafikabständen zusammen.

Es gibt viele Diskussionen über Distanzfunktionen in:

• Können gemeinsam genutzte Nachbarentfernungen den Fluch der Dimensionalität besiegen?
  ME Houle, H.-P. Kriegel, P. Kröger, E. Schubert und A. Zimek
  SSDBM 2010

und wenn Sie keine wissenschaftlichen Artikel bevorzugen, auch auf Wikipedia: Curse of Dimensionality

Ich würde vorschlagen , mit Start- Cosinus - Abstand , nicht euklidische, für alle Daten mit den meisten Vektoren nahezu orthogonal, 0. Um zu sehen , warum, schauen . Wenn 0 ist, reduziert sich dies auf : ein mieses Maß für die Entfernung, wie Anony-Mousse betont.$x \cdot y \approx$
$|x - y|^2 = |x|^2 + |y|^2 - 2\ x \cdot y$
$x \cdot y \approx$$|x|^2 + |y|^2$

Der Kosinusabstand entspricht der Verwendung vonoder Projizieren der Daten auf die Oberfläche der Einheitskugel, also alle= 1. Dann ist eine ganz andere und gewöhnlich bessere Metrik als die einfache euklidische. mag klein sein, aber es wird nicht von lauten maskiert .$x / |x|$$|x|$$|x - y|^2 = 2 - 2\ x \cdot y$
$x \cdot y$$|x|^2 + |y|^2$

$x \cdot y$ ist für spärliche Daten meist nahe 0. Wenn zum Beispiel und jeweils 100 Terme ungleich Null und 900 Nullen haben, sind beide in nur etwa 10 Terms ungleich Null (wenn die Terme ungleich Null zufällig gestreut sind).$x$$y$

Normalisierung von / =kann für spärliche Daten langsam sein; Es ist schnell im Scikit-Lernen .$x$$|x|$

Zusammenfassung: Beginnen Sie mit der Kosinusdistanz, aber erwarten Sie keine Wunder bei alten Daten.
Erfolgreiche Metriken erfordern Evaluierung, Optimierung und Domänenkenntnisse.

Ein Teil des Fluches der Dimensionalität besteht darin, dass sich Daten von der Mitte weg ausbreiten. Dies gilt für multivariate Normalen und auch dann, wenn die Komponenten IID (sphärische Normalen) sind. Aber wenn Sie streng über die euklidische Distanz sprechen möchten, selbst im niedrigdimensionalen Raum, wenn die Daten eine Korrelationsstruktur haben, ist die euklidische Distanz nicht die geeignete Metrik. Wenn wir annehmen, dass die Daten mit einigen Nicht-Null-Kovarianzen multivariat normal sind, und aus Gründen der Argumentation annehmen, dass die Kovarianzmatrix bekannt ist. Dann ist der Mahalanobis-Abstand das geeignete Abstandsmaß und entspricht nicht dem euklidischen Abstand, auf den er sich nur reduzieren würde, wenn die Kovarianzmatrix proportional zur Identitätsmatrix ist.

Ich glaube, dies hängt mit dem Fluch der Dimensionalität / Maßkonzentration zusammen, aber ich kann die Diskussion, die diese Bemerkung motiviert, nicht mehr finden. Ich glaube, es gab einen Thread zu Metaoptimize, aber ich konnte ihn nicht googeln ...

Bei Textdaten führt die Normalisierung der Vektoren mit TF-IDF und die anschließende Anwendung der Cosinus-Ähnlichkeit wahrscheinlich zu besseren Ergebnissen als der euklidische Abstand, da lange Dokumente (mit vielen Wörtern) dieselben Themen haben können und daher kurzen Dokumenten mit einer hohen Anzahl gemeinsamer Dokumente sehr ähnlich sind Wörter. Das Verwerfen der Vektornorm hilft in diesem speziellen Fall.

Ein axiomatisches Maß für die Sparsity ist die sogenannte Zählung, die die (endliche) Anzahl von Nicht-Null-Einträgen in einem Vektor zählt. Mit diesem Maß besitzen die Vektoren und die gleiche Sparsität. Und absolut nicht die gleiche Norm. Und (sehr dünn) hat dieselbe Norm wie , ein sehr flacher, nicht spärlicher Vektor. Und absolut nicht die gleiche Anzahl.$\ell_0$$(1,0,0,0)$$(0,21,0,0)$$\ell_2$$(1,0,0,0)$$\ell_2$$\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)$$\ell_0$

Diese Funktion, weder eine Norm noch eine Quasinorm, ist nicht glatt und nicht konvex. Abhängig von der Domäne sind ihre Namen Legionen, zum Beispiel: Kardinalitätsfunktion, Numerositätsmaß oder einfach Sparsamkeit oder Sparsamkeit. Es wird aus praktischen Gründen oft als unpraktisch angesehen, da seine Verwendung zu schwierigen NP-Problemen führt .

Während Standardabstände oder -normen (wie der Euklidische Abstand) leichter zu ermitteln sind, ist eines ihrer Probleme ihre Homogenität:für . Dies kann als nicht intuitiv angesehen werden, da das Skalarprodukt den Anteil von Null-Einträgen in Daten nicht ändert ( ist -homogen).$\ell_2$$1$

In der Praxis kann man sich also auf Kombinationen von ( ) wie Lasso, Grat oder elastische . Die Norm (Manhattan oder Taxicab-Distanz) oder ihre geglätteten Avatare sind besonders nützlich. Seit Arbeiten von E. Candès und anderen kann man erklären, warum eine gute Annäherung an : Eine geometrische Erklärung . Andere haben in zum Preis von Nichtkonvexitätsproblemen gemacht.$\ell_p(x)$$p \ge1$$\ell_1$$\ell_1$$\ell_0$$p < 1$$\ell_p(x)$

Ein weiterer interessanter Weg ist die erneute Axiomisierung des Begriffs der Sparsamkeit. Eine der jüngsten bemerkenswerten Arbeiten ist Comparing Measures of Sparsity von N. Hurley et al., Die sich mit der Sparsamkeit von Verteilungen beschäftigt. Aus sechs Axiomen (mit lustigen Namen wie Robin Hood, Scaling, Rising Tide, Cloning, Bill Gates und Babies) ergaben sich einige Sparsity-Indizes: einer basiert auf dem Gini-Index, ein weiterer auf Normverhältnissen, insbesondere dem One-Over-Over-Index. Zwei (siehe unten):$\frac{\ell_1}{\ell_2}$

Obwohl nicht konvex, werden einige Konvergenzbeweise und einige historische Referenzen in Euklid in einem Taxifahrzeug beschrieben: Sparse Blind Deconvolution with Smoothed Regularization$\frac{\ell _1}{\ell_2}$ .

Der Aufsatz Über das überraschende Verhalten von Distanzmetriken in hochdimensionalen Räumen diskutiert das Verhalten von Distanzmetriken in hochdimensionalen Räumen.

Sie übernehmen die Norm und schlagen die Manhattan Norm als die effektivste in hochdimensionalen Räumen für Clusterzwecke vor. Sie führen auch eine gebrochene Norm , die der Norm ähnlich ist, jedoch mit .$L_k$$L_1$ $L_f$$L_k$$f \in (0..1)$

Kurz gesagt, sie zeigen, dass für hochdimensionale Räume die Verwendung der euklidischen Norm als Standard wahrscheinlich keine gute Idee ist. In solchen Räumen haben wir normalerweise wenig Intuition, und das exponentielle Aufblasen aufgrund der Anzahl der Dimensionen ist mit der euklidischen Entfernung schwer zu berücksichtigen.