Эффективно ли k-d дерево для поиска kNN. k поиск ближайших соседей

Question

Мне нужно осуществить поиск k ближайших соседей для 10-мерных данных в kd-дереве.

Но проблема в том, что мой алгоритм очень быстр для k = 1, но в 2000 раз медленнее для k> 1 (k = 2,5,10,20,100)

Это нормально для деревьев kd, или я что-то делаю?

Answer 1

Ну, в первую очередь это зависит от вашей конкретной реализации и набора данных.

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

Это также может зависеть от того, как вы найдете k соседей. Если ваш алгоритм ищет в дереве ближайшего соседа и сохраняет его, затем ищет второй ближайший и сохраняет его и т. Д., Тогда вы не выполняете поиск очень эффективно. Вместо этого сохраняйте текущий список k ближайших соседей и точек удара из списка, поскольку вы находите более близкие, проходящие через дерево. Таким образом, вы ищете один раз, а не k раз.

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

Answer 2

Я знаю, что на этот вопрос был дан ответ, но для более подробной информации о поисках KNN с k-d деревьями см. Bentley (1975: 514), Сообщения ACM 18 (9), сентябрь.