random unit vector in multi-dimensionalen Raum

Arbeite ich an einem data mining-Algorithmus, bei dem ich möchten, wählen Sie eine zufällige Richtung von einem bestimmten Punkt in der feature-Raum.

Wenn ich wählen Sie eine zufällige Zahl für jede der n Dimensionen aus [-1,1] und dann normalisieren Sie den Vektor auf die Länge 1 bekomme ich eine gleichmäßige Verteilung über alle möglichen Richtungen?

Ich spreche nur theoretisch hier, da computer-generierte Zufallszahlen sind nicht wirklich zufällig.

InformationsquelleAutor Matt | 2011-06-08

36

Einen einfachen trick auszuwählen, die jede dimension von einer Gauß-Verteilung, dann normalisieren:
```
from random import gauss

def make_rand_vector(dims):
    vec = [gauss(0, 1) for i in range(dims)]
    mag = sum(x**2 for x in vec) ** .5
    return [x/mag for x in vec]
```
Zum Beispiel, wenn Sie möchten, dass ein 7-dimensionaler zufälliger Vektor, wählen Sie 7 zufällig Werte (aus einer Gauß-Verteilung mit Mittelwert 0 und Standardabweichung 1). Dann berechnen Sie die Größe des resultierenden Vektors mit dem Satz des Pythagoras Formel (Quadrat jeder Wert, fügen Sie die Quadrate, und nehmen Sie die Quadratwurzel des Ergebnisses). Schließlich teilen jeden Wert von der Größenordnung zu erhalten, wird eine normalisierte zufälliger Vektor.

Wenn Sie die Anzahl der Dimensionen ist groß, so hat dies den großen Vorteil, immer sofort zu arbeiten, während die Erzeugung zufälliger Vektoren, bis Sie eine finden, die zufällig eine Größenordnung kleiner als eins wird, dass der computer einfach hängen, bei mehr als einem Dutzend Dimensionen oder so, da die Wahrscheinlichkeit einer von Ihnen qualifying wird verschwindend klein.
- Schön! Danke für den zusätzlichen Vorschlag.
- Dies ist die standard-Lösung. Es funktioniert gut.
- Übrigens, dies ist, wie boost boost.org/doc/libs/1_47_0/boost/random/uniform_on_sphere.hpp implementiert. 😉
- Ich denke, das ist die beste Antwort! Es gibt jedoch eine kleine chance, dass Sie den null-Vektor (und somit eine Division durch null Fehler) jeder einmal in eine Weile
- Hier ist eine Referenz auf, warum diese Methode ist die richtige mathworld.wolfram.com/HyperspherePointPicking.html
- Eine kurze Erklärung, warum das funktioniert: Die Wahrscheinlichkeit P von einem Punkt zu einem gegebenen <x,y> ist P(x)*P(y). Die Gauß-Verteilung hat in etwa die form e^(-x^2), also e^(-x^2)*e^(-y^2) e^(-(x^2+y^2)). Das ist eine Funktion, die nur von der Entfernung des Punktes vom Ursprung, so dass die resultierende Verteilung ist Radial symmetrisch. Dies verallgemeinert sich leicht auf höhere Dimensionen.
- Zusätzlicher Hinweis: die Box–Muller-Transformation verwendet werden können, zu generieren unabhängige Paare von normalverteilten Variablen aus unabhängigen Paaren von gleichmäßig verteilt sind (kein 'Abfall').
- mit numpy dies wäre vec = numpy.random.randn(dims); return vec / numpy.linalg.norm(vec)
InformationsquelleAutor Bram Cohen
14

Werden Sie nicht erhalten einer gleichmäßig verteilten ensemble von Winkeln mit dem Algorithmus, den Sie beschrieben. Die Winkel werden voreingenommen in Richtung der Ecken des n-dimensionalen hypercube.

Dies kann behoben werden, nachdem alle Punkte mit Entfernung von mehr als 1 vom Ursprung. Dann sind Sie den Umgang mit einem kugelförmigen eher als ein dreidimensionales (n-dimensionale) Volumen, und Ihre Winkel sollten dann gleichmäßig über die Probe-Raum.

Pseudocode:

Sei n die Anzahl der Dimensionen, K ist die gewünschte Anzahl der Vektoren:
```
vec_count=0
while vec_count < K
   generate n uniformly distributed values a[0..n-1] over [-1, 1]
   r_squared = sum over i=0,n-1 of a[i]^2
   if 0 < r_squared <= 1.0
      b[i] = a[i]/sqrt(r_squared)  ; normalize to length of 1
      add vector b[0..n-1] to output list
      vec_count = vec_count + 1
   else
      reject this sample
end while
```
- Das ist, was ich war besorgt über. Ich war einfach nicht in der Lage zu formalisieren es in meinem Kopf die Art und Weise, die Sie beschrieben. Intuitiv weiß ich, dass ich möchte, dass meine Zufalls-Vektoren zu beschreiben einen Kreis. Ich bin einfach nicht sehen, wie die Umsetzung in code.
- Ich erweiterte meine Antwort ein bisschen, hoffe, das hilft.
- AH! Ich habe es. ich danke Ihnen sehr.
- Warum würden Sie verwenden einen Algorithmus mit nicht-deterministischen Ausführungszeit UND einen Zweig, wenn Sie sich lösen könnte, dies mit einem in geschlossener form Ausdruck?
InformationsquelleAutor Jim Lewis
2

Ich hatte das exakt gleiche Frage, wenn auch die Entwicklung eines ML-Algorithmus.

Ich kam zu dem gleichen Schluss wie Jim Lewis nach der Ziehung von Stichproben für die 2-d-Fall und Plotten Sie die resultierende Verteilung der Winkel.

Außerdem, wenn Sie versuchen, um daraus die Dichte-Verteilung für die Richtung, in 2d beim zeichnen nach dem Zufallsprinzip aus [-1,1] für die x - und y-Achse ,Sie werden sehen, dass:

f_X(x) = 1/(4*cos²(x)) , wenn 0 < x < 45⁰

und

f_X(x) = 1/(4*sin²(x)) , wenn x > 45⁰

wobei x der Winkel, und f_X ist die Wahrscheinlichkeits-Dichte-Verteilung.

Ich geschrieben habe über dieses hier:
https://aerodatablog.wordpress.com/2018/01/14/random-hyperplanes/

InformationsquelleAutor Carlos Teixeira
1

Gibt es eine boost-Implementierung des Algorithmus, dass die Stichproben aus normalverteilungen: random::uniform_on_sphere

InformationsquelleAutor killogre

-3

#define SCL1 (M_SQRT2/2)
#define SCL2 (M_SQRT2*2)

//unitrand in [-1,1].
double u = SCL1 * unitrand();
double v = SCL1 * unitrand();
double w = SCL2 * sqrt(1.0 - u*u - v*v);

double x = w * u;
double y = w * v;
double z = 1.0 - 2.0 * (u*u + v*v);

Code nicht mehr, ist schwer zu Lesen für nicht-mechanische Jungs wie mich. Alle Kommentare zu was es macht, warum es besser ist als die akzeptierte Antwort, oder was ?

InformationsquelleAutor MC Pee Pants

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.