Wie räumliche Partitionierung in n-Dimensionen durchzuführen?

Question

ich versuche eine Implementierung der Vektorquantisierung als C ++ Template-Klasse zu entwerfen, die verschiedenen Typen und Abmessungen von Vektoren verarbeiten kann (zum Beispiel 16 dimensionalen Vektoren von Bytes oder 4d Vektoren verdoppelt, etc).

Ich habe auf den Algorithmen zu lesen, und ich verstehe das meiste davon:

hier und hier

Ich will die Linde-Buzo-Gray (LBG) Algorithmus implementieren, aber ich habe Schwierigkeiten, zum Trennen der Cluster des allgemeinen Algorithmus herauszufinden. Ich glaube, ich brauche eine Ebene (Hyperebene & sgr) zu definieren, dass die Vektoren in einem Cluster teilt, so gibt es auf jeder Seite der Ebene eine gleiche Anzahl ist.

[bearbeiten weitere Informationen hinzufügen] Dies ist ein iterativer Prozess, aber ich denke, dass ich zunächst den Schwerpunkt aller Vektoren zu finden, dann diesen Schwerpunkt verwenden, um die Teilungsebene zu definieren, erhalten den Schwerpunkt jeder der Seiten der Ebene, fortgesetzt wird, bis ich die Anzahl der Cluster haben erforderlich für den VQ-Algorithmus (Iterieren zu optimieren für geringere Verzerrung auf dem Weg). Die Animation in den ersten Link oben zeigt es schön.

Meine Fragen sind:

Was ist ein Algorithmus, um das Flugzeug zu finden, sobald ich den Schwerpunkt habe?

Wie kann ich einen Vektor testen, um zu sehen, ob es auf beiden Seiten dieser Ebene ist?

Answer 1

Wenn Sie mit einem Schwerpunkt beginnen, dann werden Sie es geteilt haben, im Grunde durch Verdoppelung und leicht die Punkte auseinander in einer beliebigen Richtung bewegen. Das Flugzeug ist nur die Ebene senkrecht zu dieser Richtung.

Aber Sie brauchen nicht zu dieser Ebene zu berechnen.

allgemeiner der Bereich (I) als Satz von Punkten definiert, die auf den Schwerpunkt c_i näher als zu irgendeinem anderen Zentroid. Wenn Sie zwei Schwerpunkte haben, jede Region ist ein Halbraum, also durch eine (Hyper-) Ebene getrennt.

Wie auf einem Vektor zu Test x, auf welcher Seite der Ebene zu sehen ist? (Das mit zwei Zentroide)

berechnen Sie einfach den Abstand || x-c1 || und || x-c2 ||, der Index des Minimalwertes (1 oder 2) gibt Ihnen die Region den Punkt x gehört.

Generell, wenn Sie n Centroide haben, würden Sie alle Abstände || x-c_i berechnen ||, und der Schwerpunkt x am nächsten ist (dh, für die der Abstand minimal ist) gibt Ihnen die Region x Zugehörigkeit zu.

Answer 2

Ich verstehe nicht ganz, den Algorithmus, aber die zweite Frage ist einfach:

Lassen Sie uns Anruf V ein Vektor, der reicht von ein beliebiger Punkt auf der Ebene die Point-in-Frage. Dann werden die Punkt-in-Frage liegt auf der gleichen Seite der (hyper) -Ebene als die normale N iff V · N > 0