Generieren eines hochdimensionalen Datensatzes, bei dem der nächste Nachbar bedeutungslos wird

7

In der Zeitung " Wann ist 'Nächster Nachbar' sinnvoll? " Lesen wir das:

Wir zeigen, dass sich unter bestimmten allgemeinen Bedingungen (in Bezug auf Daten- und Abfrageverteilungen oder Arbeitsbelastung) mit zunehmender Dimensionalität die Entfernung zum nächsten Nachbarn der Entfernung zum entferntesten Nachbarn nähert. Mit anderen Worten, der Kontrast in Abständen zu verschiedenen Datenpunkten wird nicht mehr vorhanden. Die Bedingungen, unter denen dies identifiziert wurde, sind viel breiter als die Annahme unabhängiger und identisch verteilter Dimensionen (IID), die andere Arbeiten annehmen.

Meine Frage ist, wie ich einen Datensatz generieren soll, der diesen Effekt erzeugt.

Ich habe drei Punkte mit jeweils 1000 Dimensionen mit Zufallszahlen zwischen 0 und 255 für jede Dimension erstellt, aber Punkte erzeugen unterschiedliche Abstände und reproduzieren nicht das, was oben erwähnt wurde. Es scheint, dass sich ändernde Dimensionen (z. B. 10 oder 100 oder 1000 Dimensionen) und Bereiche (z. B. [0,1]) nichts ändern. Ich bekomme immer noch unterschiedliche Entfernungen, was beispielsweise für Clustering-Algorithmen kein Problem sein sollte!

Bearbeiten: Ich habe mehr Proben ausprobiert, basierend auf meinen Experimenten konvergieren die Abstände zwischen Punkten nicht zu einer beliebigen Zahl, im Gegenteil, die maximalen und minimalen Abstände zwischen Punkten werden deutlicher. Dies steht auch im Widerspruch zu dem, was im ersten Beitrag von Need more intuition für den Fluch der Dimensionalität und auch für viele andere Orte geschrieben wurde, die dasselbe behaupten wie https://en.wikipedia.org/wiki/Clustering_high-dimensional_data#Problems . Ich würde es immer noch begrüßen, wenn mir jemand mit einem Code oder einem realen Datensatz zeigen könnte, dass ein solcher Effekt in praktischen Szenarien vorliegt.

machine-learning clustering dataset k-nearest-neighbour high-dimensional U66
quelle
100 Dimensionen würden bereits als sehr hochdimensional gelten (im Vergleich zu den 2, 3 oder vielleicht 4-dimensionalen realen Anwendungen, für die ursprünglich euklidische Abstände verwendet wurden). Erwarten Sie keine großen Veränderungen zwischen 100 und 1000. Entfernungen sind unterschiedlich, OK, aber um wie viel?
David Ernst
Die Entfernung ist selbst für 1 Million Dimensionen auf sinnvolle Weise unterschiedlich. Jetzt, wo ich darüber nachdenke, ist vielleicht meine Zufallszahlengenerierung das Problem. Im Moment generiere ich einfach Zufallszahlen in einem bestimmten Bereich und widme sie jeder Dimension, aber ich denke, ein genauerer Ansatz besteht darin, so etwas wie eine multivariate Normalverteilung zu verwenden, um Zufallszahlen zu erzeugen.
U66
Ich habe die multivariate Normalverteilung von Apache verwendet und kann den Effekt immer noch nicht replizieren !!!
U66

Antworten:

4

Lesen Sie einige der neueren Folgeartikel wie:

Houle, ME, Kriegel, HP, Kröger, P., Schubert, E. & Zimek, A. (2010, Juni). Können Entfernungen zwischen geteilten Nachbarn den Fluch der Dimensionalität besiegen? . In der Internationalen Konferenz über wissenschaftliches und statistisches Datenbankmanagement (S. 482-500). Springer Berlin Heidelberg.

und

Zimek, A., Schubert, E. & Kriegel, HP (2012). Eine Umfrage zur unbeaufsichtigten Erkennung von Ausreißern in hochdimensionalen numerischen Daten. Statistical Analysis and Data Mining, 5 (5), 363-387.

Wenn ich mich richtig erinnere, zeigen sie die Eigenschaften des theoretischen Distanzkonzentrationseffekts (der bewiesen ist) und die Einschränkungen, warum sich die Realität sehr unterschiedlich verhalten kann. Wenn diese Artikel nicht hilfreich sind, rufen Sie mich an und ich überprüfe die Referenzen erneut (habe nur das, woran ich mich erinnere, in Google Scholar eingegeben und die Artikel nicht erneut heruntergeladen).

Beachten Sie, dass der "Fluch" nicht sagt, dass sich der Unterschied der Entfernungen zum nächsten und am weitesten entfernten Nachbarn 0 nähert. noch dass die Entfernungen zu einer bestimmten Zahl konvergieren würden. sondern dass der relative Unterschied zum absoluten Wert gering wird. Dann können zufällige Abweichungen dazu führen, dass Nachbarn falsch eingestuft werden.

Ignorieren Sie in diesem Bereich nicht den Bruch, den erwarteten Wert und d→∞::

limd→∞E(distmax⁡(d)−distmin⁡(d)distmin⁡(d))→0
Hat aufgehört - Anony-Mousse
quelle
Hallo, danke für die Information, die Hauptfrage bleibt jedoch unbeantwortet, wie wir ein Beispiel erzeugen können, das diesem Effekt ähnelt. Außerdem habe ich diesen Satz "relativer Unterschied zum absoluten Wert" nicht ganz verstanden. Können Sie mehr erklären?
U66
hmmm ... Ich denke, ich könnte den Effekt erfolgreich replizieren, der Punkt liegt in der Division (z. B. ist es der relative Abstand von (max-min) zum minimalen Punkt und nicht die einfachen Abstände). Wenn ich die Abmessungen vergrößere, wird der relative Abstand kleiner. Dies gilt für den Ursprung und auch für alle anderen Punkte im Datensatz.
U66
"Relative Entfernung" bezieht sich genau auf diese Unterteilung. Es ist ziemlich klar, dass die absoluten Werte nicht gegen eine Konstante konvergieren.
Hat aufgehört - Anony-Mousse
2

Ich hatte auch vorher noch nichts davon gehört, daher bin ich wenig defensiv, da ich gesehen habe, dass echte und synthetische Datensätze in hohen Dimensionen die Behauptung des fraglichen Papiers wirklich nicht unterstützen.

Als ersten, schmutzigen, ungeschickten und vielleicht nicht guten ersten Versuch würde ich vorschlagen, eine Kugel in einer Dimension Ihrer Wahl zu erzeugen (ich mache das so ) und dann eine Abfrage in die Mitte von zu stellen Die Sphäre.

In diesem Fall liegt jeder Punkt in der gleichen Entfernung zum Abfragepunkt, sodass der nächste Nachbar einen Abstand hat, der dem am weitesten entfernten Nachbarn entspricht.

Dies ist natürlich unabhängig von der Dimension, aber es ist das, woran man nach dem Betrachten der Zahlen des Papiers dachte. Es sollte ausreichen, um Sie anzustarren, aber es können sicherlich bessere Datensätze generiert werden, falls vorhanden.

Bearbeiten über:

Die Abstände für jeden Punkt wurden größer mit mehr Dimensionen !!!!

Dies wird erwartet, denn je höher der dimensionale Raum ist, desto spärlicher ist der Raum und desto größer ist der Abstand. Darüber hinaus wird dies erwartet, wenn Sie zum Beispiel an die euklidische Distanz denken, die mit zunehmenden Dimensionen größer wird.

gsamaras
quelle