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

Question

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

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

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

Итак, мне нужно несколько советов о:

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

Answer 1

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

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

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

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

2,1 Сабспейс кластеризация

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

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

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

Answer 2

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

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

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

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

Я бы предложил LSH или несколько деревьев RKD. В моем answer здесь я упоминаю некоторые хорошие библиотеки, которые выполняют 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, который говорит, что оптимальная структура данных зависит от данных.