Abstandsmetrik und Fluch der Dimensionen

In einigen Fällen habe ich einen Hinweis gelesen, dass Sie möglicherweise einen "Fluch der Dimensioalität" haben, wenn Sie viele Parameter und versuchen, eine "Ähnlichkeitsmetrik" zwischen diesen Vektoren zu finden. Ich glaube, es bedeutete, dass die meisten Ähnlichkeitswerte gleich sind und Ihnen keine nützlichen Informationen geben. Mit anderen Worten, fast alle Partnervektoren haben eine mittlere Entfernungsbewertung, die für die Kategorisierung oder Clusterbildung usw. nicht nützlich ist. $(x_1, x_2, \ldots, x_n)$

Wissen Sie, wo ich mehr darüber erfahren kann?

Gibt es Metriken, die weniger unter diesem Effekt leiden?

distance similarities metric Gerenuk
quelle

Antworten:

Einige klassische Beobachtungen zu Entfernungen in hochdimensionalen Daten:

K. Beyer, J. Goldstein, R. Ramakrishnan und U. Shaft, ICDT 1999: "Wann sind die nächsten Nachbarn sinnvoll?"
CC Aggarwal, A. Hinneburg und DA Keim, ICDT 2001: "Über das überraschende Verhalten von Distanzmetriken im hochdimensionalen Raum"

Ein paar neuere Untersuchungen zu diesem Thema, bei denen Nachbarn und Hubness gemeinsam genutzt werden:

ME Houle, H.-P. Kriegel, P. Kröger, E. Schubert und A. Zimek, SSDBM 2010: "Können Entfernungen zwischen geteilten Nachbarn den Fluch der Dimensionalität besiegen?"
T. Bernecker, ME Houle, H.-P. Kriegel, P. Kröger, M. Renz, E. Schubert und A. Zimek, SSTD 2011: "Rangfolge der Ähnlichkeitsqualität in Zeitreihen"
N. Tomašev, M. Radovanović, D. Mladenić und M. Ivanović. Adv. KDDM 2011: "Die Rolle von Hubness beim Clustering hochdimensionaler Daten"
Erinnere dich nicht an die anderen, suche nach "Hubness", das war ihre hochdimensionale Beobachtung

Diese sind interessant, da sie auf einige populäre Missverständnisse über den Fluch der Dimensionalität hinweisen . Im Wesentlichen zeigen sie, dass die theoretischen Ergebnisse - bei denen davon ausgegangen wird, dass die Daten iid sind - für Daten mit mehr als einer Verteilung im Allgemeinen nicht zutreffen. Der Fluch führt zu numerischen Problemen und einem Verlust der Diskriminierung innerhalb einer einzelnen Verteilung, während es noch einfacher sein kann , zwei gut getrennte Verteilungen zu unterscheiden.

Einiges davon sollte ziemlich offensichtlich sein. Angenommen, Sie haben Objekte, die in jeder Dimension iid sind, und in jeder Dimension eine andere Gruppe von Objekten, die iid sind. Der Unterschied zwischen den Objekten aus zwei unterschiedlichen Sätzen wird immer Größen größer als ein Abstand innerhalb eines einzigen Satzes, und das Problem wird auch erhalten mit zunehmender Dimensionalität leichter . $A_i\sim \mathcal{N}(0;1)$ $B_i\sim \mathcal{N}(100;1)$

Ich empfehle, diese Arbeit von Houle et al. Zu lesen, vor allem, weil sie zeigt, dass Sie die Dinge möglicherweise etwas zu einfach machen, wenn Sie behaupten, "diese Daten sind hochdimensional und aufgrund des Fluches der Dimensionalität können sie nicht analysiert werden". Trotzdem ist das eine Linie, die überall verwendet wird. "Unser Algorithmus funktioniert aufgrund des Fluches der Dimensionalität nur für niedrigdimensionale Daten." "Unser Index funktioniert aufgrund des Fluches der Dimensionalität nur für bis zu 10 Dimensionen." Yadda yadda yadda. Viele dieser Aussagen zeigen anscheinend nur, dass solche Autoren nicht verstanden haben, was bei hoher Dimensionalität in ihren Daten und Algorithmen passiert (oder eine Entschuldigung brauchten). Houle et al. Lösen Sie das Rätsel nicht vollständig (noch? Dies ist ziemlich neu), aber sie überdenken zumindest viele der populären Aussagen.

Wenn hohe Dimensionalität ein so großes Problem wäre, wie kommt es dann, dass Menschen im Text Mining gerne Dimensionalitäten in der Größenordnung von 10000-100000 verwenden, während Menschen in anderen Bereichen bei nur 10 Dimensionen aufgeben?!?

Was den zweiten Teil Ihrer Frage betrifft : Die Kosinusähnlichkeit scheint weniger unter der Dimensionalität zu leiden . Abgesehen davon sollten klassische -Norms in Ordnung sein , solange Sie verschiedene Verteilungen unterscheiden, die numerische Genauigkeit steuern und sich nicht auf von Hand ausgewählte Schwellenwerte verlassen möchten (da Sie diese möglicherweise mit vielen signifikanten Ziffern angeben müssen). $L_p$

Allerdings Cosinus ist auch vom Fluch der Dimensionalität beeinflusst , wie in diskutiert:

M. Radovanović, A. Nanopoulos und M. Ivanović, SIGIR 2010. "Über die Existenz hartnäckiger Ergebnisse in Vektorraummodellen."

Hat aufgehört - Anony-Mousse
quelle

Aggarwal CC, Hinneburg A., Keim, DA (2001), "Über das überraschende Verhalten von Distanzmetriken im hochdimensionalen Raum"
Beyer K., Goldstein J., Ramakrishnan R., Shaft U. (1999), "Wann sind die nächsten Nachbarn sinnvoll?", ICDE-Konferenzverfahren.

user603
quelle

Klingt interessant :) Ich hoffe, ich kann eine Kopie davon bekommen. Wissen Sie, ob es für dieses Problem Lösungen mit normalen Metriken gibt?

Gerenuk

(+1) das sieht sehr interessant aus.

Elvis

@Gerenuk: Was meinst du mit "normalen" Metriken? Auch beide Papiere sind verfügbar. online, ungated, als pdfs

user603

L_{k}

$L_k$

L_{k}

$L_k$

Fractional L_p-Normen verbergen nur das Problem. Ich glaube, das Ergebnis tendiert dann zu so etwas wie dem minimalen Attributunterschied, der für eine große Anzahl von Dimensionen in der Praxis genauso bedeutungslos wird. Es löst nur das Problem, dass die Zahlen immer größer werden. Die Dimensionsreduzierung funktioniert in einigen Fällen, aber betrachten Sie den Fall, wenn Sie nicht weiter kommen. Was dann? Außerdem beträgt die Dimensionsreduzierung im Wesentlichen "640.000 Dimensionen sollten für jeden ausreichen". Text liegt üblicherweise im Bereich von 10 ^ 5. Was ist mit Video?

Hat aufgehört - Anony-Mousse

Ebenfalls:

Robert J. Durrant, Ata Kabán: Wann ist der nächste Nachbar sinnvoll: Ein umgekehrter Satz und Implikationen. J. Complexity 25 (4): 385 & ndash; 397 (2009)
Ata Kabán: Über das Distanzkonzentrationsbewusstsein bestimmter Datenreduktionstechniken. Pattern Recognition 44 (2): 265 & ndash; 277 (2011)
Ata Kabán: Nichtparametrische Erkennung bedeutungsloser Entfernungen in hochdimensionalen Daten. Statistics and Computing 22 (2): 375 & ndash; 385 (2012)

Axt
quelle