Мало знаний, большой вызов! Эта статья участвует в "Необходимые знания для программистов«Творческая деятельность.

Оглядываясь назад на KNN:

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

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

В это время мы можем использовать более быстрый метод расчета — дерево kd.

что такое кд дерево

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

Двумерная (k=2) прямоугольная область:

Трехмерная (k=3) прямоугольная область:

Обратите внимание, что k в дереве kd представляет количество объектов, то есть размерность данных, а k в k ближайших соседей относится к k ближайшим соседям новой точки экземпляра.

Как построить дерево kd

принцип

входить:k-мерный набор пространственных данных:

x_i=(x_i⁽¹⁾,маленький_i⁽²⁾,...,Икс_i^(k))^T,маленький_i^(l)Верхний индекс представляет l-е собственное значение

вывод:кд дерево

1. Начало: создание корневого узла.

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

Если мы выберем х⁽¹⁾, возьмите ее за ось координат, найдите точку разделения и разрежьте суперпрямоугольную область на две подобласти. обычно выбирают х⁽¹⁾В качестве точки отсечения используется медиана данных в направлении, а из корневого узла генерируются левый и правый дочерние узлы с глубиной 1. Координаты левого узла меньше точки отсечения, а координаты правого узла больше, чем точка отсечения.

2. Повторить: выбор и вырезание оставшихся элементов

Перейдите к узлу глубины j, выберите x⁽¹⁾- ось деления, l = j (mod k) + 1, со всеми экземплярами x в области узла⁽¹⁾Медиана координат используется в качестве точки сегментации, которая непрерывно делит область на две подобласти.

3. Стоп: получить дерево kd

Прекратить разбиение до тех пор, пока в двух подобластях не останется экземпляров, то есть будет получено kd-дерево.

Пример объяснения

входить:

вывод:кд дерево

Для удобства пометьте точки данных в наборе данных для визуального отображения:

1. Первый разрез

Поскольку размерность обучающего набора данных равна 2, вы можете выбрать одну функцию. С тем же успехом можно выбрать х⁽¹⁾ось координат, x⁽¹⁾Данные в отсортированы от меньшего к большему, а именно: 2, 4, 5, 7, 8, 9

Медиана может выбрать 7, то естьВозьмите (7, 2) в качестве корневого узла, чтобы разделить всю область.

Левый дочерний узел меньше 7, правый дочерний узел больше 7.

2. Второй сплит

Снова разделите площадь:

Добавьте 1 к первой функции с x⁽²⁾является координатной осью.

Для левой области после первого разделения установите x⁽²⁾Данные в сортируются от меньшего к большему, а именно: 2, 3, 4, 7

Медиана равна 4, а координаты точки сегментации равны(5, 4), а затем нарисуйте горизонтальную линию для второго разделения.

Точно так же для правой области после первого разделения установите x⁽²⁾Данные в отсортированы от меньшего к большему соответственно: 1, 6

Поскольку есть только две точки, вы можете также выбрать 6 в качестве точки разделения, а координаты точки разделения в правой области(9, 6), проведите горизонтальную линию для второго разделения.

3. Продолжайте сегментировать

Добавьте 1 ко второму признаку, к x⁽³⁾— ось координат, и здесь есть только x⁽¹⁾и х⁽²⁾, поэтому только для х⁽¹⁾Разделять. Или напрямую вычислите 2(mod 2)+1=1, чтобы получить выбранную функцию.

это хорошо видноА(2,3),Д(4,7),Е(8,1)Три точки экземпляра еще не были разделены, поэтому возьмите эти точки в качестве корневого узла и нарисуйте линию, перпендикулярную x.⁽¹⁾Линия оси разделена.

4. Нарисуйте дерево kd

Корневыми узлами в этих подразделениях являются:

Уровень 1: (7, 2)

Второй уровень: (5, 4), (9, 6)

Уровень 3: (2, 3), (4, 7), (8, 1)

Нарисуйте дерево kd в соответствии с этим уровнем:

как искать дерево kd

принцип

входить:Построенное дерево kd, целевая точка x

вывод:ближайший сосед x

Найдите «текущую ближайшую точку»:Начиная с корневого узла, рекурсивно посетите дерево kd, найдите конечный узел, содержащий x, и используйте этот конечный узел как «текущую ближайшую точку».

Проследить:Возврат и итерация вдоль корня дерева с расстоянием между целевой точкой и «текущей ближайшей точкой». Текущая ближайшая точка должна существовать в области, соответствующей дочернему узлу узла, и проверить другой дочерний узел родителя узел дочернего узла. Имеет ли соответствующая область более близкую точку.

При возврате к корневому узлу поиск заканчивается, и последняя «текущая ближайшая точка» является ближайшим соседом x.

Пример объяснения

В качестве примера возьмем сгенерированное выше дерево kd:

Case 1

входить:дерево kd, целевая точка x=(2.1,3.1)

вывод:ближайший сосед цели

Найдите текущую ближайшую точку:Начиная с корневого узла, x=(2.1,3.1) находится в левой подобласти корневого узла (7, 2), продолжается до левой подобласти, определяемой (5, 4), и продолжается до (2 , 3) В правой подобласти , (2, 3) текущий ближайший сосед.

Проследить:Нарисуйте окружность с (2.1, 3.1) в качестве центра и расстоянием от найденного ближайшего соседа в качестве радиуса. Других точек в этой области нет, затем докажите, что (2, 3) является (2.1, 3.1) ближайшим соседом .

Case 2

входить:дерево kd, целевая точка x=(2, 4.5)

вывод:ближайший сосед целевой точки

Найдите текущую ближайшую точку:Начиная с корневого узла, x=(2, 4.5) находится в левой подобласти корневого узла (7, 2), продолжается до верхней подобласти, определяемой (5, 4), и продолжается до (4 , 7) В левой подобласти , (4, 7) текущий ближайший сосед.

Проследить:Мы рисуем круг с (2, 4,5) в качестве центра и расстоянием между двумя точками (2, 4,5) до (4, 7) в качестве радиуса.В этой области есть два узла, а именно (2, 3) И (5, 4), вычислив расстояние от (2, 4,5) до этих двух точек, получается, что расстояние до (2, 3) является ближайшим, тогда (2, 3) является ближайшей точкой. Затем нарисуйте круг с (2, 4.5) в качестве центра и расстоянием между двумя точками (2, 4.5) до (2, 3) в качестве радиуса.В это время в круге нет других узлов, что указывает на то, что можно убедиться, что (2 , 3) ​​является ближайшим соседом (2, 4.5).

Использованная литература:

Анализ данных доктора Джейн

Видео материал:

3.3 Метод k-ближайших соседей — что такое kd-дерево

3.3 Метод k-ближайших соседей — построение дерева kd

3.3 метод k-ближайших соседей — поиск дерева kd