Comment effectuer un partitionnement dans l'espace n dimensions?

Question

Je suis en train de concevoir une implémentation de Vector Quantification comme c ++ classe modèle qui peut gérer différents types et dimensions des vecteurs (par exemple 16 des vecteurs de dimension d'octets, etc., ou des vecteurs 4d de doubles).

Je l'ai lu sur les algorithmes, et je comprends la plus grande partie:

et ici

Je veux mettre en œuvre le Linde-Buzo-Gray (LBG) algorithme, mais je vais avoir des difficultés pour trouver l'algorithme général pour le partitionnement des clusters. Je pense que je dois définir un plan (hyperplan?) Qui divise les vecteurs dans un cluster donc il y a un nombre égal de chaque côté du plan.

[modifier pour ajouter plus d'informations] Ceci est un processus itératif, mais je pense que je commence par déterminer le barycentre de tous les vecteurs, utilisez alors que barycentre pour définir le plan de séparation, obtenir le barycentre de chacun des côtés du plan, continue jusqu'à ce que j'ai le nombre de grappes nécessaire pour l'algorithme de VQ (itération d'optimiser la distorsion moins le long de la voie). L'animation dans le premier lien ci-dessus montre gentiment.

Mes questions sont les suivantes:

Qu'est-ce qu'un algorithme pour trouver le plan une fois que je le barycentre?

Comment puis-je tester un vecteur pour voir si elle est de part et d'autre de ce plan?

Answer 1

Si vous commencez avec un centre de gravité, alors vous devrez diviser, essentiellement en doublant et se déplaçant légèrement à part les points dans une direction arbitraire. Le plan est que le plan orthogonal à cette direction.

Mais vous n'avez pas besoin de calculer ce plan.

Plus généralement, la région (i) est défini comme l'ensemble des points qui sont plus proches du centre de gravité c_i que de tout autre centroïde. Lorsque deux centres de gravité, chaque région est un demi-espace, donc séparés par un plan (hyper).

Comment tester sur un vecteur x pour voir de quel côté du plan, il est? (C'est avec deux centres de gravité)

Il suffit de calculer la distance || x ||-c1 et || x ||-c2, l'indice de la valeur minimum (1 ou 2) vous donnera quelle région du point x appartient.

Plus généralement, si vous avez n centroïdes, vous calculer toutes les distances || x ||-C_I, et le barycentre x est le plus proche de (c.-à-dont la distance est minime) vous donnera la région x est appartenant à.

Answer 2

Je ne comprends pas tout à fait l'algorithme, mais la deuxième question est facile:

Appelons V un vecteur qui étend de un point quelconque sur le plan le point en question. Ensuite, le point se trouve en question sur le même côté du plan (hyper) comme normale N iff V · N > 0