Как выполнить пространственные разбиение в N-размерах?

Question

Я пытаюсь разработать реализацию вектора квантования в качестве класса шаблона C ++, который может обрабатывать разные типы и размеры векторов (например, 16 измерительных векторов байтов, или 4D векторов удваиваний и т. Д.).

Я читал в алгоритмах, и я понимаю больше всего:

здесь а также здесь

Я хочу реализовать алгоритм Linde-Buzo-Grey (LBG), но мне трудно выяснить общий алгоритм для разделения кластеров. Я думаю, что мне нужно определить самолет (гиперплоскость?), Которая разбивает векторы в кластере, поэтому на каждой стороне самолета есть равное число.

Редактировать, чтобы добавить дополнительную информациюЭто итерационный процесс, но я думаю, что начну с нахождения центров всех векторов, затем используйте этот центр, чтобы определить плоскость расщепления, получить центроид каждой из сторон плоскости, продолжая до тех пор, пока у меня нет количества кластеров необходимо для алгоритма VQ (итерации для оптимизации для меньшего искажения по пути). Анимация в первой ссылке выше показывает ее красиво.

Мои вопросы:

Что такое алгоритм, чтобы найти самолет, когда у меня есть центроидный?

Как я могу проверить вектор, чтобы увидеть, если он по обе стороны от этого самолета?

Answer 1

Если вы начнете с одного центроида, то вам придется разделить его, в основном, удваивая его и слегка перемещая точки друг от друга в произвольном направлении. Самолет - это просто плоский ортогональный к этому направлению.

Но вам не нужно вычислять этот самолет.

В целом регион (I) определяется как набор точек, которые ближе к центру Centroid C_I, чем на любой другой центр. Когда у вас есть два центроида, каждый регион - это половина пространства, таким образом разделена (гипер) плоскостью.

Как проверить на вектор X, чтобы увидеть, на какую сторону самолета это? (это с двумя центроидами)

Просто вычислите расстояние || X-C1 || и || X-C2 ||, индекс минимального значения (1 или 2) даст вам, какой регион точка X принадлежит.

В более общем целом, если у вас есть n центроида, вы бы вычислили все расстояния || X-C_I ||, а центроид X ближе всего к (т. Е. Для которого расстояние минимально) даст вам регион X принадлежащий.

Answer 2

Я не совсем понимаю алгоритм, но второй вопрос легко:

Давай позвоним Внимание Вектор, который простирается от любая точка на самолете к точечный вопрос. Тогда точка в вопросе лежит на той же стороне (гипер) плоскости, как обычно N. IFF. V · N. > 0