Rivalry2

HTML Diff

0 added 24 removed

Original 2026-01-01

Modified 2026-02-26

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

2 На рисунке выше вы можете увидеть координатную плоскость, на которой расположены:

3 <ul><li>"Заболевшие" красные точки</li>

4 <li>"Здоровые" синие точки</li>

5 <li>"Опасные зоны" - розовые окружности вокруг красных точек</li>

6 </ul>Синяя точка подвергается риску заболеть, если она входит в опасную зону - располагается слишком близко к красной точке. Другими словами, чтобы синяя точка не заболела, расстояние между ней и красной точкой должно быть вышепорогового значения.

7 В этом примере задача сводится к поиску синих точек с высоким риском заболеть. Один из способов решения такой задачи - это кластеризация на основе методов машинного обучения. Но есть и альтернатива - этоKD-деревья, о которых мы и поговорим в этом уроке.

8 <h2>Что такое KD-деревья</h2>

9 KD-деревья- это дерево, вершины которого представлены в форме точек в некоторой K-мерной системе координат. Еще их называютK-dimensional treesили "K-мерные деревья".

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

11 Обратим внимание, что эффективность поиска ближайших соседей в KD-дереве снижается при больших значениях K.

12 В качестве правила обычно принимают, что число вершин в дереве должно быть намного больше значения 2^K. Если это правило не соблюдать, то алгоритм поиска на основе KD-дерева будет работать с почти той же скоростью, что и обычный последовательный поиск.

13 <h2>Как устроено KD-дерево</h2>

14 Чтобы изучить строение KD-дерева, возьмем для примера 13 точек в двумерной системе координат:

15 Чтобы построить по ним дерево, мы будем руководствоваться следующим алгоритмом:

16 <ol><li>Выберем ось в наборе данных</li>

17 <li>Найдем на этой осимедианное значение числа точек. Для двумерного пространства это значит, что справа и слева от значения должно быть одинаковое число точек. Если у нас четное число точек, то можно левое подпространство сделать больше правого</li>

18 <li>Проведем линию, которая разделит пространство на две части</li>

19 <li>Изменим ось и нарисуем свою медиану для каждого нового подпространства</li>

20 </ol>Пройдя эти четыре шага, мы выполним первоеразделениедерева. Далее мы повторяем все шаги до тех пор, пока точек больше не останется.

21 Посмотрим, как разделение работает на нашем примере - двумерном KD-дереве с 13 точками:

22 Этап 1. Разделим пространство на основании оси X:

23 Этап 2. Выполним второе разделение на основании оси Y:

24 Этап 3. Продолжаем разделение, пока это возможно:

25 Этап 4. Строим итоговое дерево, исходя из разделения пространства:

26 На последнем рисунке видно, что получившееся дерево аналогично сбалансированному бинарному дереву. Разница только в том, что в качестве полезной нагрузки в KD-дереве хранится точка с координатами.

27 В таком случае JavaScript-код узла будет выглядеть так:

28 - Javascript

29 - Java

30 - Python

31 - PHP

32 <h2>Операции над KD-деревом</h2>

28 <h2>Операции над KD-деревом</h2>

33 Основное отличие KD-дерева можно увидеть при работе с методом, который отвечает за построение дерева из массива точек:

29 Основное отличие KD-дерева можно увидеть при работе с методом, который отвечает за построение дерева из массива точек:

34 - Javascript

35 - Java

36 - Python

37 - PHP

38 Вызвать построение дерева можно при помощи следующего примера:

30 Вызвать построение дерева можно при помощи следующего примера:

39 - Javascript

40 - Java

41 - Python

42 - PHP

43 Структура KD-дерева не отличается от бинарного дерева. Поэтому методы удаления и вставки узлов работают так же, как в бинарном дереве:

31 Структура KD-дерева не отличается от бинарного дерева. Поэтому методы удаления и вставки узлов работают так же, как в бинарном дереве:

44 - Javascript

45 - Java

46 - Python

47 - PHP

48 Удаление:

32 Удаление:

49 - Javascript

50 - Java

51 - Python

52 - PHP

53 Еще одной отличительной особенностью KD-дерева считается реализация метода поиска ближайшего соседа:

33 Еще одной отличительной особенностью KD-дерева считается реализация метода поиска ближайшего соседа:

54 - Javascript

55 - Java

56 - Python

57 - PHP

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

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

59 <h3>Процесс поиска ближайших соседей</h3>

35 <h3>Процесс поиска ближайших соседей</h3>

60 <ol><li>Инициализация:<ul><li>Поиск начинается с корневого узла дерева и заданной точки, для которой необходимо найти ближайшие соседи.</li>

36 <ol><li>Инициализация:<ul><li>Поиск начинается с корневого узла дерева и заданной точки, для которой необходимо найти ближайшие соседи.</li>

61 </ul></li>

37 </ul></li>

62 <li>Рекурсивный поиск:<ul><li>На каждом уровне дерева происходит сравнение координат искомой точки с координатами узла. В зависимости от результата сравнения, поиск продолжается в одном из дочерних узлов (левом или правом).</li>

38 <li>Рекурсивный поиск:<ul><li>На каждом уровне дерева происходит сравнение координат искомой точки с координатами узла. В зависимости от результата сравнения, поиск продолжается в одном из дочерних узлов (левом или правом).</li>

63 <li>Если текущий узел ближе к искомой точке, чем уже найденные соседи, он добавляется в список лучших соседей.</li>

39 <li>Если текущий узел ближе к искомой точке, чем уже найденные соседи, он добавляется в список лучших соседей.</li>

64 </ul></li>

40 </ul></li>

65 <li>Обновление списка лучших соседей:<ul><li>Если количество найденных соседей меньше заданного максимума, или если текущий узел ближе, чем самый дальний из уже найденных, он добавляется в список.</li>

41 <li>Обновление списка лучших соседей:<ul><li>Если количество найденных соседей меньше заданного максимума, или если текущий узел ближе, чем самый дальний из уже найденных, он добавляется в список.</li>

66 <li>Если список заполнен, удаляется самый дальний сосед, чтобы освободить место для нового.</li>

42 <li>Если список заполнен, удаляется самый дальний сосед, чтобы освободить место для нового.</li>

67 </ul></li>

43 </ul></li>

68 <li>Проверка других поддеревьев:<ul><li>После проверки одного из дочерних узлов, если расстояние до текущего узла позволяет, происходит проверка другого дочернего узла. Это необходимо для того, чтобы убедиться, что не пропущены более близкие соседи.</li>

44 <li>Проверка других поддеревьев:<ul><li>После проверки одного из дочерних узлов, если расстояние до текущего узла позволяет, происходит проверка другого дочернего узла. Это необходимо для того, чтобы убедиться, что не пропущены более близкие соседи.</li>

69 </ul></li>

45 </ul></li>

70 </ol><h2>Выводы</h2>

46 </ol><h2>Выводы</h2>

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

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

72 Поиск ближайших соседей - это одна из популярных задач, стоящих перед программистами. Результаты ее решения нужны в медицине, геологии, картографии и прочих прикладных областях, связанных с кластеризацией пространственных объектов.

48 Поиск ближайших соседей - это одна из популярных задач, стоящих перед программистами. Результаты ее решения нужны в медицине, геологии, картографии и прочих прикладных областях, связанных с кластеризацией пространственных объектов.