Лучшая структура данных для многомерного поиска ближайшего соседа

Question

Я на самом деле работаю с данными большого размера (~50.000-100.000 объектов), и поиск ближайших соседей должен быть выполнен по ним. Я знаю, что KD-Trees имеет низкую производительность при увеличении размеров, а также я читал, что в целом все структуры данных с разделением пространства имеют тенденцию выполнять исчерпывающий поиск с данными большого размера.

Кроме того, следует учитывать два важных факта (упорядоченных по релевантности):

• Точность: должны быть найдены ближайшие соседи (не приближения).
• Скорость: поиск должен быть максимально быстрым. (Время для создания структуры данных не очень важно).

Итак, мне нужен совет по поводу:

1. Структура данных для выполнения к-нн.
2. Если будет лучше использовать подход ANN (примерный ближайший сосед), устанавливая его как можно точнее?

Answer 1

Могу ли я выполнить поиск NN в многомерном пространстве?

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

В результате, в многомерном пространстве нужно искать приблизительный ближайший сосед (ANN). Если честно, это обязательно.

Какую структуру данных выполнять ANN?

Я бы предложил LSH или несколько деревьев RKD. В своем ответе я упомянул несколько хороших библиотек, которые выполняют ANN на C++. Однако обратите внимание, что LSH решил проблему R-ближайшего соседа, поэтому вы указываете параметр R, который фактически является радиусом. Затем LSH будет искать NN внутри этого R из точки запроса, поэтому вы не можете запросить k NN.

С другой стороны, деревья RKD могут сделать это и вернуть вам k NN. У меня есть проект, который строит лес из деревьев RKD и выполняет поиск ANN в C++, но он нацелен только на большие измерения. Он может обрабатывать наборы данных GIST из 10^6 изображений в 960 измерениях за < 1 с, причем около 90% выходных данных являются истинными ближайшими соседями. Имя это kd-GeRaF. Он будет обновлен в следующем месяце с помощью распространяемой версии, но он уже протестирован и готов к использованию. У этого также есть симпатичный логотип.:)

---

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

Answer 2

Я не думаю, что было бы разумно проводить кластеризацию в таких многомерных данных. Есть проклятие проблемы размерности.

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

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

Некоторые возможные решения перечислены на этой странице, https://en.wikipedia.org/wiki/Clustering_high-dimensional_data

2.1 Подпространственная кластеризация

2.2 Прогнозируемая кластеризация

2.3 Гибридные подходы

2.4 Корреляционная кластеризация