Como realizar particionamento espacial em dimensões N?

Question

Estou tentando projetar uma implementação da quantização de vetores como uma classe de modelo C ++ que pode lidar com diferentes tipos e dimensões de vetores (por exemplo, 16 vetores de dimensão de bytes ou vetores 4D de duplas, etc.).

Eu tenho lido os algoritmos e entendo a maior parte:

aqui e aqui

Quero implementar o algoritmo Linde-Buzo-Gray (LBG), mas estou tendo dificuldades para descobrir o algoritmo geral para particionar os clusters. Eu acho que preciso definir um avião (hiperplano?) Que divide os vetores em um cluster para que haja um número igual em cada lado do plano.

Editar para adicionar mais informaçõesEste é um processo iterativo, mas acho que começo encontrando o centróide de todos os vetores e, em seguida, uso esse centróide para definir o plano de divisão, obtenha o centróide de cada um dos lados do avião, continuando até que eu tenha o número de aglomerados necessário para o algoritmo VQ (iterando para otimizar para menos distorção ao longo do caminho). A animação no primeiro link acima mostra bem.

Minhas perguntas são:

O que é um algoritmo para encontrar o avião quando eu tenho o centróide?

Como posso testar um vetor para ver se está em ambos os lados desse avião?

Answer 1

Se você começar com um centróide, terá que dividi -lo, basicamente dobrando -o e afastando um pouco os pontos em uma direção arbitrária. O avião é apenas o avião ortogonal para essa direção.

Mas você não precisa calcular esse avião.

De maneira mais geral, a região (i) é definida como o conjunto de pontos mais próximos do centróide C_I do que para qualquer outro centróide. Quando você tem dois centróides, cada região é meio espaço, assim separada por um plano (hiper).

Como testar em um vetor x para ver de que lado do avião é? (isso é com dois centróides)

Basta calcular a distância || x-c1 || e || x-c2 ||, o índice do valor mínimo (1 ou 2) fornecerá a qual região a que o ponto X pertence.

De maneira mais geral, se você tiver n centróides, calcularia todas as distâncias || x-c_i ||, e o centróide x é mais próximo de (ou seja, para o qual a distância é mínima) fornecerá a você a região X é pertencer.

Answer 2

Não entendo muito bem o algoritmo, mas a segunda pergunta é fácil:

Vamos ligar V um vetor que se estende a partir de qualquer ponto do avião para o ponto em questão. Então o ponto em questão fica no mesmo lado do plano (hiper) que o normal N iff V · n > 0