kNN с динамическими вставками в тусклом пространстве

Question

Я ищу метод быстрого доступа к ближайшему соседу (надеюсь, O (log n)) для точек с большими размерами (обычно ~ 11-13 мер). Я бы хотел, чтобы он работал оптимально во время вставок после инициализации структуры. Дерево KD пришло мне в голову, но если вы не занимаетесь массовой загрузкой, а делаете динамические вставки, то дерево kd перестает быть сбалансированным, а балансировка afaik - дорогостоящая операция.

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

Answer 1

Здесь находится Curse of Dimensionality. Вы можете рассмотреть возможность применения Основного анализа компонентов (PCA), чтобы уменьшить размерность, но, насколько я знаю, для этого нет большого ответа.

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

Я упростил дальнейшее измерение путем квантования оставшихся измерений строго, так что все многомерное пространство было отображено в 32-битное целое число. Я использовал это как ключ на карте STL (красно-черное дерево), хотя я мог бы использовать хеш-таблицу. Я смог добавить миллионы записей динамически к такой структуре (на основе RAM, конечно) примерно через минуту или две, и поиски в среднем занимали миллисекунду в среднем, хотя данные были отнюдь не равномерно распределены. Поиски требовали тщательного перечисления значений в размерах, которые были сопоставлены с 32-битным ключом, но были достаточно надежными для использования в коммерческом продукте. Я считаю, что он используется по сей день в iTunes Match, если мои источники верны. :)

Суть в том, что я рекомендую вам взглянуть на ваши данные и сделать что-то обычай, который использует в нем функции, чтобы быстро индексировать и искать. Найдите размеры, которые больше всего отличаются друг от друга и являются самыми независимыми друг от друга. Квантируйте их и используйте их как ключ в индексе. Каждое ведро в индексе содержит все элементы, которые разделяют этот ключ (вероятно, будет больше одного). Чтобы найти ближайших соседей, посмотрите на «близкие» ключи и в каждом ковше найдите близлежащие значения. Удачи.

p.s. Я написал статью о своей технике, доступной here. Извините за paywall. Возможно, вы можете найти бесплатную копию в другом месте. Дайте мне знать, если у вас есть какие-либо вопросы по этому поводу.

Answer 2

Другая структура данных, которая приходит на ум, является обложкой. В отличие от деревьев KD, которые были первоначально разработаны для ответа на запросы диапазона, эта структура данных оптимальна для запросов ближайшего соседа. Он использовался в задачах n-body, которые включают в себя вычисление k ближайших соседей всех точек данных. Такие проблемы возникают и в схемах оценки плотности (окна «Парзен»). Я не знаю достаточно о вашей конкретной проблеме, но я знаю, что есть онлайн-версии этой структуры данных. Посмотрите страницу Александра Грея, и это link

Answer 3

Если вы используете Bucket Kd-Tree с достаточно большим размером ковша, это позволяет дереву лучше понять, где разделить, когда листья становятся слишком полными. Ребята из Robocode делают это в чрезвычайно суровых временных ограничениях, при этом случайные вставки происходят на лету и kNN с k> 80, d> 10 и n> 30k менее чем за 1 мс. Ознакомьтесь с этим kD-Tree Tutorial, в котором объясняется куча усовершенствований kD-Tree и способы их реализации.

Answer 4

По моему опыту, размеры 11-13 не так уж плохи - если вы навалом. Оба загруженных R-деревьями (в отличие от k-d-деревьев они остаются сбалансированными!), А k-d-деревья должны работать намного лучше, чем линейное сканирование.

Как только вы идете полностью динамично, мои переживания намного хуже. Грубо: с загруженными массами деревьями я вижу 20-кратное ускорение, с инкрементально построенными R-деревьями всего 7 раз. Так оно делает окупится, чтобы часто перестроить дерево. И в зависимости от того, как вы упорядочиваете свои данные, это может быть намного быстрее, чем вы думаете. Объемная загрузка для k-d-дерева, который я использую, - O(n log n), и я читал, что есть вариант O(n log log n). С низким постоянным коэффициентом. Для R-дерева Sort-Tile-Recursive - лучшая объемная загрузка, которую я видел до сих пор, а также O(n log n) с низким постоянным коэффициентом.

Так что да, в большой размерности я бы подумал просто перезагрузить дерево время от времени.