когда не будет работать поиск KNN по дереву KD?

Деревья K-d не слишком хорошо работают в больших измерениях (где вам нужно посетить много-много ветвей деревьев). Одним из практических правил является то, что если ваши данные имеют размерность k, дерево k-d это будет хорошо, только если у вас есть намного больше, чем 2^k точек данных.

В больших размерностях вместо этого вы, как правило, захотите переключиться на приблизительный поиск ближайшего соседа. Если вы еще не сталкивались с ним, FLANN ( github ) — очень полезная библиотека для этого (с API-интерфейсами C, C++, python и matlab); он имеет хорошие реализации деревьев k-d, поиска методом грубой силы и нескольких приближенных методов, а также помогает автоматически настраивать их параметры и легко переключаться между ними.

Это зависит от вашей функции расстояния.

Вы не можете использовать kd-деревья с произвольными функциями расстояния. Хотя нормы Минковского должны быть в порядке. Но во многих приложениях вы захотите использовать более продвинутые функции расстояния.

Кроме того, с увеличением размерности k-d-деревья работают гораздо хуже.

Причина проста: k-d-деревья избегают смотреть в точки, где одномерное расстояние до границы уже больше искомого порога, т.е. где для евклидовых расстояний (где z — ближайшая граница, y — близкая известная точка):

(x_j - z_j)      <=>   sqrt(sum_i((x_i - y_i)^2))
equivalently, but cheaper:
(x_j - z_j)^2    <=>   sum_i((x_i - y_i)^2)

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

Временная сложность для knn :O(k * lg(n))

где k — это k ближайших соседей, а lg(n) — высота kd-дерева

kd-trees не будут работать хорошо, если размеры набора данных велики из-за такого огромного пространства.

давайте рассмотрим, что у вас есть много точек вокруг начала координат, для простоты рассмотрим в 2-D

Если вы хотите найти k-ближайших соседей для любой точки, вам нужно искать по 4 осям, потому что все точки ближе друг к другу, что приводит к возврату к другой оси в kd-дереве,

Итак, для трехмерного пространства мы должны искать по 8 направлениям.

Чтобы обобщить для n-мерного числа, это 2^k

Таким образом, временная сложность становится O(2^k * lg(n))