KNN с динамическими вставками в пространстве

Question

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

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

Answer 1

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

Answer 2

Проклятье Размерности мешает здесь.Возможно, вы захотите применить Анализ основных компонентов ( PCA ), чтобы уменьшить размерность, но, насколько я знаю, никто не может дать на это хороший ответ.

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

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

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

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

Answer 3

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

Answer 4

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

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

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