Производительность метода досады Vs. KD-Tree

Question

Производительность метода досады Vs. KD-Tree

Я занимаюсь исследованием приближенных алгоритмов ближайшего соседа.

Недавно я нашел библиотеку "Раздражающий", которая делает удивительную работу по поиску КНН с разумной скоростью. Для более глубокого анализа вы можете просмотреть слайды встречи.

Прочитав слайды и изучив исходный код, я не вижу причины, по которой этот алгоритм работает с многомерными данными лучше, чем KD-Tree.

KD-Tree - это отличный алгоритм NN, однако в больших измерениях он достигает времени работы, которое практически идентично поиску методом грубой силы [O(n^2)], и, таким образом, он требует проверки множества соседних листьев.

Причина в том, что в больших измерениях объем единичной сферы становится намного меньше (вы можете посмотреть здесь).

Единственное отличие, которое я обнаружил в библиотеке Annoy, заключается в том, что разбиение пространства выполняется с помощью гиперплоскостей, а не разбиения по одному измерению за раз.

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

3

algorithm performance knn nearest-neighbor approximate-nn-searching

Источник

user1311859 08 май '16 в 23:12

1 ответ

Решение

Другие вопросы по тегам algorithm performance knn nearest-neighbor approximate-nn-searching

user2411320 09 май '16 в 13:58 2016-05-09 13:58 · Accepted Answer · 2016-05-09 13:58

Прочитайте этот раздел раздражения:

Как это работает:
Использование случайных проекций и построение дерева. На каждом промежуточном узле дерева выбирается случайная гиперплоскость, которая делит пространство на два подпространства. Эта гиперплоскость выбирается путем выборки двух точек из подмножества и взятия эквидистантной от них гиперплоскости.
Мы делаем это k раз, чтобы получить лес из деревьев. K должен быть настроен в соответствии с вашими потребностями, посмотрев, какой у вас компромисс между точностью и производительностью.

Ключ здесь - лес деревьев, я полагаю. Вы сравниваете с KD-деревом, которое является довольно старой структурой данных и, как вы сказали, страдает от проклятия размерности.

Я думаю, что использование леса рандомизированных деревьев KD было бы хорошим совпадением здесь.

Например, мой kd-GeRaF предлагает хорошее объяснение этого (см. Статью). Однако, если количество измерений относительно мало, то есть около 100, то FLANN тоже должен быть интересным. FLANN старше kd-GeRaF, но меня сильно вдохновляет.

Я не вижу, как LSH используется в Annoy, как предлагается в комментариях, но если это так, то для леса RKD это не проблема.