Come eseguire il partizionamento spaziale in n-dimensioni?

Question

Sto cercando di progettare un'implementazione di quantizzazione vettoriale come C ++ classe template in grado di gestire diversi tipi e dimensioni di vettori (per esempio 16 vettori dimensione di byte, o vettori 4d di doppie, ecc).

Ho letto su algoritmi, e capisco la maggior parte di esso:

qui e qui

Voglio realizzare il Linde-Buzo-Gray (LBG) algoritmo, ma sto avendo difficoltà a capire l'algoritmo generale per il partizionamento dei cluster. Credo necessario definire un piano (iperpiano?) Che divide i vettori in un cluster per cui v'è un numero uguale su ciascun lato del piano.

[modifica per aggiungere ulteriori informazioni] Questo è un processo iterativo, ma penso che mi metto trovando il baricentro di tutti i vettori, quindi utilizzare tale baricentro per definire il piano di scissione, ottenere il baricentro di ognuno dei lati del piano, continuando fino a quando ho il numero di cluster necessari per l'algoritmo VQ (iterazione ottimizzare per meno distorsione lungo la strada). L'animazione nel primo link qui sopra mostra piacevolmente.

Le mie domande sono:

Che cosa è un algoritmo per trovare l'aereo una volta che ho il baricentro?

Come faccio a testare un vettore per vedere se è su entrambi i lati di questo piano?

Answer 1

Se si inizia con un baricentro, allora dovrete dividerlo, in pratica raddoppiando e spostando leggermente i punti a parte in una direzione arbitraria. L'aereo è solo il piano ortogonale a quella direzione.

Ma non è necessario per calcolare quel piano.

Più in generale, la regione (i) è definito come l'insieme di punti che sono più vicini alla C_I baricentro rispetto a qualsiasi altro centroide. Quando si hanno due centroidi, ogni regione è uno spazio metà, così separato da una (iper) piano.

Come prova su un vettore x per vedere da quale parte del piano è? (Quella con due baricentri)

Basta calcolare la distanza || x-c1 || e || x ||-c2, l'indice del valore minimo (1 o 2) darà quale regione il punto x appartiene.

Più in generale, se si dispone di n baricentri, si dovrebbe calcolare tutte le distanze || x-C_I ||, e la x baricentro è più vicino a (ad esempio, per la quale la distanza è minima) vi darà la regione x è facente.

Answer 2

Io non riesco a capire l'algoritmo, ma la seconda domanda è facile:

chiamata Let V un vettore che si estende da qualsiasi punto sul piano punto-in-questione. Poi le bugie point-in-questione sullo stesso lato del (iper) piano come il normale N sse V · N > 0