Алгоритм K-ближайших соседей (KNN), дерево K-D и мгновенное распознавание рукописных цифр!

1. Что такое КНН

1.1 Популярное объяснение KNN

Что такое алгоритм K-ближайших соседей, то есть алгоритм K-ближайших соседей, именуемый алгоритмом KNN. Просто догадываясь из названия, его можно просто и грубо рассматривать как: K ближайших соседей. При K=1, алгоритм становится алгоритмом ближайшего соседа, то есть найти ближайшего соседа.

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

Как показано на рисунке выше, существует два разных типа выборочных данных, которые представлены маленькими синими квадратами и маленькими красными треугольниками, а данные, отмеченные зеленым кружком в середине рисунка, — это данные, подлежащие классификации. То есть теперь мы не знаем, к какой категории относятся зеленые данные в середине (маленький синий квадрат или маленький красный треугольник), и KNN решает эту проблему.

Если K=3, то ближайшие 3 соседа зеленой точки – это 2 маленьких красных треугольника и 1 маленький синий квадрат, а меньшинство принадлежит большинству.На основе статистических методов определяется, что классифицируемая зеленая точка принадлежит к красный треугольник 1 вид.

Если K=5, то ближайшими 5 соседями зеленой точки являются 2 красных треугольника и 3 синих квадрата, или меньшинство принадлежит большинству На основании статистических методов определяется, что классифицируемая зеленая точка принадлежит синему квадрату один тип.

Здесь мы видим, что, когда невозможно определить, к какой категории относится текущая классифицируемая точка, мы можем посмотреть на характеристики ее местоположения на основе статистической теории, измерить вес окружающих ее соседей и поставить Она классифицирована (или назначено) в категорию с большим весом. Это основная идея алгоритма K ближайших соседей.

1.2 Метрики расстояния для ближайших соседей

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

Каковы представления метрик расстояния?(Популяризируйте очки знаний, можете пропустить):

Евклидово расстояние, наиболее распространенное представление расстояния между двумя или более точками, также известное как евклидова метрика, которая определяется в евклидовом пространстве, например точка x = (x1,...,xn) и расстояние между y = (y1,. ..,уп) это:

$d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+...+(x_n-y_n)^2}=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}$
- Евклидово расстояние между двумя точками a(x1,y1) и b(x2,y2) на двумерной плоскости:
  
  $d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$
- Евклидово расстояние между двумя точками a(x1,y1,z1) и b(x2,y2,z2) в трехмерном пространстве:
  
  $d_{12}=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$
- Евклидово расстояние между двумя n-мерными векторами a(x11,x12,…,x1n) и b(x21,x22,…,x2n):
  
  $d_{12}=\sqrt{\sum_{k=1}^{n}(x_{1k}-x_{2k})^2}$
  
  Его также можно выразить как векторную операцию:
  
  $d_{12}=\sqrt{(a-b)(a-b)^T}$
Манхэттенское расстояние, мы можем определить формальный смысл манхэттенского расстояния как L1-расстояние или расстояние городского квартала, то есть сумму расстояний проекции отрезка, образованного двумя точками на оси, на фиксированную прямоугольную систему координат евклидова пространства . Например, на плоскости манхэттенское расстояние между точкой P1 с координатами (x1, y1) и точкой P2 с координатами (x2, y2) равно:, следует отметить, что манхэттенское расстояние зависит от вращения системы координат, а не от перемещения или отображения системы на оси координат.

С точки зрения непрофессионала, представьте, что вы едете от одного перекрестка до другого на Манхэттене.Является ли расстояние вождения расстоянием по прямой между двумя точками? По-видимому, нет, если только вы не сможете пройти через здание. Фактическое расстояние вождения - это «Манхэттенское расстояние», которое является источником названия Манхэттенское расстояние.В то же время, Манхэттенское расстояние также называют расстоянием городского квартала.
- Манхэттенское расстояние между двумя точками a(x1,y1) и b(x2,y2) на двумерной плоскости
  
  $d_{12}=|x_1-x_2|+|y_1-y_2|$
- Манхэттенское расстояние между двумя n-мерными векторами a(x11,x12,…,x1n) и b(x21,x22,…,x2n)
  
  $d_{12}=\sum_{k=1}^{n}|x_{1k}-x_{2k}|$
Расстояние Чебышева, если координатами двух векторов или двух точек p и q являются Pi и qi соответственно, то чебышевское расстояние между ними определяется следующим образом:

$D_{Chebyshev}(p,q)=max_i(|p_i-q_i|)$

Это также равно экстремальному значению следующей метрики Lp: $\lim_{x \to \infty}(\sum_{i=1}^{n}|p_i-q_i|^k)^{1/k}$ , поэтому расстояние Чебышева также называют метрикой L∞.

С математической точки зрения расстояние Чебышева является мерой, полученной из равномерной нормы (или называемой супремум-нормой), а также типом инъективного метрического пространства.

В плоской геометрии, если декартовы координаты двух точек p и q равны (x1, y1) и (x2, y2), то расстояние Чебышева равно:

$D_{Chess}=max(|x_2-x_1|,|y_2-y_1|)$

Друзья, игравшие в шахматы, возможно, знают, что король может одним ходом переместиться на любую из 8 соседних клеток. Итак, сколько шагов нужно королю, чтобы пройти от сетки (x1, y1) до сетки (x2, y2)? . Вы обнаружите, что минимальное количество шагов всегда равно max( | x2-x1 | , | y2-y1 | ) steps . Существует аналогичная мера расстояния, называемая расстоянием Чебышева.
- Чебышевское расстояние между двумя точками a(x1,y1) и b(x2,y2) на двумерной плоскости:
  
  $d_{12}=max(|x_2-x_1|,|y_2-y_1|)$
- Расстояние Чебышева между двумя n-мерными векторами a(x11,x12,…,x1n) и b(x21,x22,…,x2n):
  
  $d_{12}=max_i(|x_{1i}-x_{2i}|)$
  
  Другой эквивалентной формой этой формулы является
  
  $d_{12}=lim_{k\to\infin}(\sum_{i=1}^{n}|x_{1i}-x_{2i}|^k)^{1/k}$
Минковский Расстояние(РАССТОЯНИЕ МИНКОВСКОГО), расстояние - это не расстояние, а набор определений расстояния.

Расстояние Минковского между двумя n-мерными переменными a(x11,x12,…,x1n) и b(x21,x22,…,x2n) определяется как:

$d_{12}=\sqrt[p]{\sum_{k=1}^{n}|x_{1k}-x_{2k}|^p}$

где p — переменный параметр. Когда p = 1, это манхэттенское расстояние. Когда p = 2, это евклидово расстояние При p→∞ это расстояние Чебышева
В зависимости от переменных параметров расстояние Мина может представлять собой класс расстояний.
нормализованное евклидово расстояние, стандартизированное евклидово расстояние является улучшенным решением недостатков простого евклидова расстояния. Идея стандартного евклидова расстояния: поскольку распределение компонентов данных в каждом измерении различно, сначала «стандартизируйте» каждый компонент до среднего значения и равной дисперсии. Что касается того, насколько стандартизированы среднее значение и дисперсия, сначала просмотрите некоторые статистические данные.

Если предположить, что математическое ожидание или среднее (среднее) выборочного набора X равно m, а стандартное отклонение (стандартное отклонение, корень дисперсии) равно s, то «стандартизованная переменная» X* для X выражается как: (Xm) /s, а математическое ожидание стандартизованной переменной равно 0, а дисперсия равна 1. То есть процесс стандартизации выборочной совокупности описывается формулой:

$X^*=\frac{X-m}{s}$

Нормализованное значение = (значение до нормализации - среднее значение компонентов) / стандартное отклонение компонентов После простого вывода можно получить формулу для стандартизированного евклидова расстояния между двумя n-мерными векторами a(x11,x12,...,x1n) и b(x21,x22,...,x2n):

$d_{12}=\sqrt{\sum_{k=1}^{n}(\frac{x_{1k}-x_{2k}}{s_k})^2}$
Расстояние Махаланобиса

Имеется M выборочных векторов X1~Xm, ковариационная матрица обозначается как S, а среднее значение обозначается как вектор μ, тогда расстояние Махаланобиса от выборочного вектора X до u выражается как:

$D(X)=\sqrt{(X-u)^TS^{-1}(X_i-X_j)}$
- Если ковариационная матрица представляет собой единичную матрицу (независимую и одинаково распределенную между каждым вектором выборки), то формула принимает вид, то есть евклидово расстояние:
  
  $D(X_i,X_j)=\sqrt{(X_i-X_j)^T(X_i-X_j)}$
- Если ковариационная матрица является диагональной матрицей, формула становится нормализованным евклидовым расстоянием.
Преимущества и недостатки расстояния Махаланобиса: не зависит от размерности, исключает интерференцию корреляции между переменными.
Расстояние Баркола

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

Для дискретных распределений вероятностей p и q в одной и той же области X это определяется как:

в:

$BC(p,q)=\sum_{x\in_{}X}\sqrt{p(x)q(x)}$

- коэффициент Бхаттачарьи.
Расстояние Хэмминга

Расстояние Хэмминга между двумя строками одинаковой длины s1 и s2 определяется как минимальное количество подстановок, необходимых для замены одной строки на другую. Например, расстояние Хэмминга между строками «1111» и «1001» равно 2. Применение: Кодирование информации (для повышения отказоустойчивости минимальное расстояние Хемминга между кодами должно быть максимально большим).
Угловой косинус

Косинус прилежащего угла в геометрии можно использовать для измерения разницы в направлении двух векторов, и эта концепция заимствована в машинном обучении для измерения разницы между выборочными векторами.
- Формула косинуса угла между вектором A(x1,y1) и вектором B(x2,y2) в двумерном пространстве:
  
  $cos\theta=\frac{x_1x_2+y_1y_2}{\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}}$
- Косинус угла между двумя n-мерными точками выборки a(x11,x12,...,x1n) и b(x21,x22,...,x2n):
  
  $cos\theta=\frac{a*b}{|a||b|}$
Диапазон значений косинуса прилежащего угла: [-1,1]. Чем больше косинус угла, тем меньше угол между двумя векторами, и чем меньше косинус угла, тем больше угол между двумя векторами. Когда направления двух векторов совпадают, косинус прилежащего угла принимает максимальное значение 1, а когда направления двух векторов полностью противоположны, косинус прилежащего угла принимает минимальное значение -1.
Коэффициент подобия Жаккара

Доля элементов пересечения двух множеств A и B в объединении A и B называется коэффициентом подобия Жаккара двух множеств и обозначается символом J (A, B). Коэффициент сходства Жаккара является мерой сходства между двумя множествами.

$J(A,B)=\frac{|A\cap_{}B|}{|A\cup_{}B|}$

Понятие, противоположное коэффициенту подобия Жаккара, - это расстояние Жаккара:

$J_{\delta}(A,B)=1-J(A,B)=\frac{|A\cup_{}B|-|A\cap_{}B|}{|A\cup_{}B|}$
Коэффициент Пирсона

В статистике коэффициент корреляции продукта и момента Пирсона используется для измерения корреляции (линейной корреляции) между двумя переменными, X и Y, со значением от -1 до 1. Обычно о силе корреляции переменных судят по следующим диапазонам значений:

0,8-1,0 очень сильная корреляция 0,6-0,8 Сильная корреляция 0,4-0,6 Умеренная корреляция 0,2-0,4 Слабая корреляция 0,0-0,2 Очень слабая корреляция или ее отсутствие

Короче говоря, сценарии применения различных «расстояний» просто резюмируются следующим образом:

Пространственное: евклидово расстояние,
Путь: Манхэттенская дистанция, Шахматный король: Чебышевская дистанция,
Унифицированная форма трех вышеупомянутых: расстояние Минковского,
взвешенное: нормализованное евклидово расстояние,
Исключить размеры и зависимости: расстояние Махаланобиса,
Зазор вектора: косинус прилежащего угла,
Разница в кодировании: расстояние Хэмминга,
Установите приближение: коэффициент подобия Жаккара и расстояние,
Корреляция: коэффициент корреляции и расстояние корреляции.

Выбор значения 1,3 К

Если вы выберете небольшое значение K, это эквивалентно прогнозированию с обучающими примерами в меньшем поле, ошибка аппроксимации «обучения» будет уменьшена, и только обучающие примеры, которые близки или похожи на входные примеры, будут способствовать предсказанию. результатов., при этом проблема в том, что будет возрастать ошибка оценки "обучения", иными словами,Уменьшение значения K означает, что общая модель усложняется и может происходить переобучение;
Если выбрано большее значение K, это эквивалентно использованию обучающих примеров в большей области для прогнозирования.Преимущество заключается в том, что ошибка оценки обучения может быть уменьшена, но недостаток заключается в том, что ошибка аппроксимации обучения будет увеличиваться. В это время обучающие экземпляры, которые далеки (не похожи) от входного экземпляра, также будут воздействовать на предиктор, делая предсказание неверным, иУвеличение значения K означает, что общая модель становится проще.
K=N, совершенно недостаточно, потому что неважно, какой входной экземпляр в это время, это всего лишь простое предсказание, что он принадлежит к самому утомленному в обучающем экземпляре Модель слишком проста и игнорирует много полезного информация в учебном экземпляре.

В практических приложениях значение K обычно принимает относительно небольшое значение.Например, метод перекрестной проверки (просто говоря, часть выборки используется как обучающая выборка, а другая часть — как тестовая) используется для выбора оптимального значения K.

1.4 Процесс алгоритма классификации ближайших соседей KNN

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

2. Реализация KDD: дерево KD

Kd-дерево — это сокращение от K-мерного дерева, которое представляет собой точку данных в k-мерном пространстве (например, двумерном (x, y), трехмерном (x, y, z), k-мерном (x1 , y, z..)) Структура данных, разделенная на , в основном используется при поиске ключевых данных в многомерном пространстве (например, поиск диапазона и поиск ближайшего соседа). По сути, Kd-дерево — это сбалансированное бинарное дерево.

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

2.1 Построение дерева KD

Псевдокод построения дерева kd показан на следующем рисунке:

Приведен еще один простой и наглядный пример для введения алгоритма построения дерева k-d. Предположим, что есть 6 двумерных точек данных {(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}, точки данных расположены в двухмерном пространстве, как показано на рисунке ниже. Чтобы эффективно находить ближайших соседей, дерево kd принимает идею «разделяй и властвуй», то есть все пространство делится на несколько небольших частей.Сначала толстая черная линия делит пространство на две части, а затем в двух подпространствах тонкая черная линия делит все пространство на две части, пространство делится на четыре части, и, наконец, воображаемая черная линия еще больше делит эти четыре части.

6 двумерных точек данных {(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)} Конкретные шаги для построения kd дерево следующие:

ОК: разделить домен=x. В частности: отклонения данных 6 точек данных в измерениях x и y составляют 39 и 28,63 соответственно, поэтому отклонение по оси x больше, поэтому значение разделенного поля равно x;
ОК: данные узла = (7,2). В частности: отсортируйте данные в соответствии со значением в измерении x, медианное значение 6 данных (так называемое медианное значение, то есть значение среднего размера) равно 7, поэтому поле Node-data является точка данных (7,2). Таким образом, разделенной гиперплоскостью этого узла является линия x=7, проходящая через (7,2) и перпендикулярная: оси split=x;
Определить: левое подпространство и правое подпространство. А именно: разбить гиперплоскость x=7, чтобы разделить все пространство на две части: часть x
Как упоминалось в приведенном выше алгоритме, построение дерева kd является рекурсивным процессом, мы можем получить дочерние узлы первого уровня (5, 4) и (9, 6), повторив процесс корневого узла для данных в левое подпространство и правое подпространство.Одновременно разделите пространство и набор данных дальше и так далее, пока пространство не будет содержать только одну точку данных.

В то же время, после разделения пространства, показанного выше, мы видим, что точка (7,2) может быть корневым узлом, а две толстые красные косые черты от корневого узла указывают на (5,4) и (9, 6) — левый и правый потомки корневого узла, а (2,3), (4,7) — левый и правый потомки (5,4) (соединены двумя тонкими красными косыми чертами), наконец, (8 ,1) — левый дочерний элемент (9,6) (соединен тонкой красной косой чертой). Таким образом формируется следующее дерево k-d:

Для k-мерных данных с n экземплярами временная сложность построения kd-дерева составляет O(knлогин).

Алгоритм дерева kd можно разделить на две части.Помимо приведенной выше части об алгоритме установления структуры данных самого дерева kd, другая часть включает в себя различные операции, такие как вставка, удаление и поиск (поиск ближайшего соседа) на установленном дереве kd.алгоритм. Далее, давайте по очереди рассмотрим операции вставки, удаления и поиска дерева kd.

2.2 Вставка дерева KD

Элементы вставляются в дерево K-D аналогично двоичному дереву поиска. По сути, значения координаты x сравниваются на слоях с четными номерами, а значения координаты y сравниваются на слоях с нечетными номерами. Когда мы достигнем нижней части дерева (то есть, когда появится нулевой указатель), мы также найдем позицию, в которую будет вставлен узел. Форма результирующего дерева K-D зависит от порядка, в котором были вставлены узлы. Учитывая N точек, средняя стоимость вставки и извлечения одной из них составляет O(log2N).

Процесс вставки выглядит следующим образом:

Должно быть ясно, что во время описанного здесь процесса вставки каждый узел разделяет плоскость, в которой он находится, на две части. По этой причине Чикаго делит все узлы на плоскости на две части: одна часть содержит все узлы, значение координаты x которых меньше 35, а другая часть имеет значение координаты x узлов, большее или равное 35. Точно так же Mobile делит все узлы, у которых значение координаты x больше 35, на две части, значение координаты Y некоторых узлов меньше 10, а значение координаты Y другой части узлов больше или равно до 10. Следующие Торонто и Баффало также делятся по правилу деления на два.

2.3 Удаление дерева KD

Удаление дерева KD можно реализовать с помощью рекурсивной процедуры. Предположим, что мы хотим удалить узел (a,b) из дерева K-D. Если оба поддерева (a,b) пусты, замените (a,b) пустым деревом. В противном случае найдите подходящий узел в поддереве (a,b), чтобы заменить его, например (c,d), затем рекурсивно удалите (c,d) из дерева K-D. После удаления (c,d) замените (a,b) на (c,d). Предположим, что (a,b) является идентификатором X, тогда его замещающим узлом является либо узел с максимальной координатой X в левом поддереве (a,b), либо x в правом поддереве (a,b). с минимальной координатой.

Давайте возьмем реальный пример (источник: Электронный курс Китайского университета геонаук, ошибка исходного курса была исправлена ниже), как показано на рисунке ниже, исходное изображение и соответствующее дерево kd, теперь нужно удалить узел A. на рисунке см. ряд шагов удаления:

Чтобы удалить узел A на приведенном выше рисунке, выберите узел с наименьшим значением координаты X в правом поддереве узла A, здесь C, и C становится корнем, как показано ниже:

Найдите узел в правом поддереве C, чтобы заменить предыдущую позицию C,

Вот D, и левое поддерево D превращается в его правое поддерево, D заменяет предыдущую позицию C, как показано ниже:

В новом правом поддереве D найдите узел с наименьшей координатой X, здесь H, где H заменяет позицию D,

Найдите значение с наименьшей координатой Y в правом поддереве D, здесь I, замените I исходной позицией H, чтобы узел A был успешно удален из графа, как показано на следующем рисунке:

Удаление узла из дерева K-D обходится дорого, и ясно, что удаление корня поддерева ограничено количеством узлов в поддереве. Пусть TPL(T) обозначает общую длину пути дерева T. Видно, что сумма размеров поддеревьев в дереве равна TPL(T)+N. TPL случайной вставки N точек для формирования дерева составляет O (N * log2N), что означает, что верхняя граница средней стоимости удаления случайно выбранного узла из случайно сформированного дерева K-D составляет O (log2N).

2.4 Алгоритм поиска ближайшего соседа дерева KD

Псевдокод алгоритма запроса дерева K-D выглядит следующим образом:

Я написал рекурсивную версию функции поиска 2D-дерева kd для сравнения:

Пример

Звездочка указывает на запрашиваемую точку Точка запроса (2, 4.5). С помощью бинарного поиска можно быстро найти ближайшую приблизительную точку на пути поиска. Найденные листовые узлы не обязательно являются ближайшими соседями, ближайший сосед обязательно находится ближе к точке запроса и должен располагаться в области круга с точкой запроса в центре и проходить через листовой узел. Чтобы найти истинного ближайшего соседа, также требуется соответствующая операция «возврата». То есть алгоритм сначала выполняет поиск в обратном направлении по пути поиска, чтобы увидеть, есть ли точки данных, которые ближе к точке запроса.

поиск по бинарному дереву: Сначала найдите узел (5,4) из (7,2).При поиске гиперплоскость делится на y = 4. Поскольку точкой поиска является значение y, равное 4,5, введите правое подпространство, чтобы найти (4), 7), образуя путь поиска , но расстояние между (4,7) и целевой точкой поиска составляет 3,202, а (5,4) и поиск. Расстояние между точками равно 3,041, поэтому (5,4) — ближайшая точка к точке запроса;
отступление: Создайте круг с (2, 4,5) в качестве центра и 3,041 в качестве радиуса, как показано на рисунке ниже. Видно, что окружность пересекается с гиперплоскостью y = 4, поэтому для поиска нужно войти в левое подпространство (5,4), то есть добавить к пути поиска узел (2,3), чтобы получить ; Затем выполните поиск (2,3) листового узла, (2,3) ближе к (2,4.5), чем (5,4), поэтому ближайший сосед обновляется до (2,3), а ближайшее обновленное расстояние равно 1,5;
Возврат, чтобы найти (5,4), до тех пор, пока, наконец, не вернется к корневому узлу (7,2), создайте круг с (2,4.5) в качестве центра и 1,5 в качестве радиуса и не пересекайте гиперплоскость с x = 7 , как показано на рисунке. В этот момент путь поиска возвращается, и возвращается ближайшая соседняя точка (2,3), а ближайшее расстояние равно 1,5.

2.5 Улучшение алгоритма поиска ближайшего соседа дерева kd: алгоритм BBF

Точки экземпляров распределяются случайным образом, тогда средняя вычислительная сложность поиска дерева kd составляет O(logN), где N — обучающее дерево экземпляров. Следовательно, kd-дерево больше подходит для поиска k-ближайших соседей, когда количество обучающих экземпляров намного больше, чем пространственное измерение.Когда пространственное измерение близко к количеству обучающих экземпляров,Его эффективность быстро падает, как только он падает до «до освобождения»: скорости линейного сканирования.

Это также из-за описания на четвертом шаге вышеприведенного алгоритма поиска k-ближайших соседей: «При возврате к корневому узлу поиск окончен», завершение сравнения запросов каждой ближайшей соседней точки в конечном итоге вернется к корневой узел. Это приводит к множеству ненужных посещений с возвратом и сравнений с узлами. Когда эти избыточные потери ищутся для многомерных данных, эффективность поиска станет довольно низкой, поэтому что можно сделать, чтобы улучшить этот исходный kd Что насчет Алгоритм поиска ближайшего соседа по дереву?

Из приведенного выше стандартного процесса запроса дерева kd видно, что «откат» в процессе поиска определяется «путем запроса», а некоторые свойства некоторых точек данных на пути запроса не учитываются. Простая идея улучшения состоит в том, чтобы отсортировать узлы на «пути запроса», например, в соответствии с расстоянием между соответствующей разделительной гиперплоскостью (также называемой бином) и точкой запроса.То есть проверки с возвратом всегда начинаются с узла дерева с наивысшим приоритетом (Best Bin).

Взяв в качестве примера приведенный выше запрос (2, 4.5), алгоритм поиска выглядит следующим образом:

Поместите (7,2) в приоритетную очередь;
Извлеките (7,2) из приоритетной очереди и извлеките его левый дочерний элемент (5,4), поскольку (2,4.5) находится на левой стороне разделяющей гиперплоскости (7,2).
При этом, согласно механизму BBF «поиск левого/правого поддерева, в очереди сохраняются одноуровневые узлы, соответствующие этому слою, а именно правые/левые узлы», а одноуровневые узлы, соответствующие (5,4 ) являются правыми дочерними узлами.Точка (9,6) нажата в очереди приоритетов
В это время приоритетная очередь {(9,6)}, а лучшая точка - (7,2); затем извлекается конечный узел (4,7) и приоритетная очередь {(2,3) , (9) ,6)}, "лучшая точка" есть (5,4);
Извлеките узел с наивысшим приоритетом (2,3) и повторяйте шаг 2, пока очередь приоритетов не станет пустой.

2.6 Применение дерева KD

Алгоритм поиска SIFT+KD_BBF, подробности см. в ссылках в конце статьи.

3. Некоторые вопросы о KNN

В k-средних или kNN мы используем евклидово расстояние для вычисления расстояния между ближайшими соседями. Почему бы не использовать манхэттенское расстояние?

**Ответ:** Мы не используем манхэттенское расстояние, потому что оно вычисляет только горизонтальное или вертикальное расстояние, существуют ограничения по размерам. С другой стороны, евклидово расстояние можно использовать для задач расчета расстояний в любом пространстве. Поскольку точки данных могут существовать в любом пространстве, евклидово расстояние является более подходящим выбором. Например: представьте себе шахматную доску, ходы, сделанные слоном или ладьей, рассчитываются по манхэттенскому расстоянию, потому что это движения в соответствующих горизонтальном и вертикальном направлениях.
В чем преимущество KD-Tree по сравнению с KNN для быстрого сравнения характеристик изображений?

A: Это значительно экономит время и деньги. Если расстояние между точкой и линией > минимальной точки, нет необходимости возвращаться к предыдущему слою, если

4. Ссылки

От алгоритма K-ближайшего соседа, измерения расстояния до дерева KD, алгоритма SIFT+BBF

5. Случай распознавания рукописных цифр

Система распознавания рукописных цифр KNN

【Машинное обучение легко понять серия статей】

автор:@mantchs

Гитхаб:GitHub.com/NLP-love/ml…

Приглашаются все желающие присоединиться к обсуждению! Улучшайте этот проект вместе! Номер группы: [541954936]