эффективный способ выполнения дискретного анализа voronoi

Question

Предположим, что у меня есть небольшое число точек в d-мерном пространстве, c_1, c_2, ..., c_N, где N составляет около 50-100.

Теперь у меня есть набор выборок x_1, x_2, ..., x_M в d-мерном пространстве, где M может быть как 1e7.

Существует ли эффективный способ выделения выборок x_1, x_2, ..., x_M таких, что для каждого j мы назначаем x_j точке c_k, для которой евклидово расстояние от x_j до c_k (для всех k) равно наименьший?

До сих пор я применяю подход грубой силы: для каждого j я просто вычислил расстояние x_j от всех c_k. В небольших размерах я легко могу это сделать, используя repmat в Matlab и некоторый векторный код.

Однако в больших габаритах я сталкиваюсь с проблемой памяти при выполнении repmat, особенно если M очень большой. Как следствие, запуск цикла for для итерации по каждому x_j становится очень медленным. Поскольку я должен выполнять эту процедуру кластеризации несколько раз, моя симуляция занимает больше времени, чем один день.

Любые идеи о том, как сделать процесс кластеризации более эффективным? Я попытался оглядеться, но нашел только кластеризацию k-mean, которая не относится ко мне, поскольку c_1, ..., c_N даны.

Answer 1

Ближайшие соседние структуры, такие как k-d деревья, работают очень плохо в высоких размерах (проклятие размерности). Мое первое предложение состояло в том, чтобы обработать образцы в кусках, которые достаточно велики, чтобы избежать накладных расходов интерпретатора MATLAB, но достаточно мала, чтобы они удобно входили в кеш.