Самый быстрый k ближайший сосед с произвольной метрикой?

Question

Вопрос с этим вопросом - «произвольная метрика». Если вы не знаете, что это такое, это просто способ измерения расстояния между точками. (В «реальном» мире 1-мерное расстояние - это просто абсолютная величина разницы между двумя точками).

Достаточно пред-lims. Я пытаюсь найти быстрый К ближайшему соседу алгоритма с этими свойствами:

• работ по произвольной метрике
• несколько легко реализовать
• оптимизированы для нахождения расстояния из набора точек в другой набор пунктов

Wikipedia дает список алгоритмов и подходов, но ничего не касается реализации.

ОБНОВЛЕНИЕ: метрика - это сходство с косинусом, которое делает не удовлетворительным качеством треугольника. Однако кажется, что я могу использовать «угловое сходство» (согласно Википедии).

ОБНОВЛЕНИЕ: прецедент естественный язык обработка. «Векторы» - это «контекст» данного слова, представленный двоичными свойствами (например, название документа). Таким образом, хотя может быть только несколько свойств (сейчас я просто использую 3), каждый вектор имеет произвольно большую размерность (в примере заголовка каждый заголовок в базе данных будет соответствовать размеру в векторе).

UPDATE: Для любопытных, я реализующая этот алгоритм:

http://josquin.cs.depaul.edu/~mramezani/papers/IEEEIS.pdf

UPDATE: Алгоритм нужно будет найти ближайших соседей для около десятка пунктов приблизительно 100s точек. Среднее измерение, вероятно, будет очень большим, скажем, 50, (я действительно еще не знаю). И да, меня интересует алгоритм, а не библиотека. И да, оценки, вероятно, достаточно хороши.

Answer 1

Я бы посоветовал вам обратиться за чувствительным к местоположению хэшированием (LSH), который сейчас находится в тренде. Это уменьшает размерность высокоразмерных данных, но я не уверен, будет ли ваше измерение соответствовать этому алгоритму. См. Википедию page для получения дополнительной информации.

Вы можете использовать свой собственный показатель, но в целом вы можете сделать это во многих алгоритмах. Надеюсь это поможет.

Вы можете пойти на деревья RKD, лес из них, но, возможно, сейчас это слишком много.