K-ближайший сосед, называемый KNN, представляет собой контролируемый непараметрический алгоритм машинного обучения. Самое необычное в KNN то, что в отличие от других алгоритмов KNN ничего не изучает и не создает модель. Вместо этого он сохраняет все обучающие данные и использует весь набор во время прогнозирования. В этом техническом письме вместо того, чтобы углубляться в практическую реализацию кодирования, мы узнаем о концепциях и механизме KNN, функциях и характеристиках, которые он содержит, приложениях в ML и так далее.
Что такое КНН?
Известно, что KNN является самым простым и понятным из всех контролируемых алгоритмов машинного обучения. Его можно использовать как для задач регрессии, так и для задач классификации. Он использует близость для поиска ближайших соседей или групп точек данных для неизвестной точки данных. По сути, он измеряет сходство между двумя или более точками данных. В линейной геометрии мы определяем сходство, вычисляя расстояние между ними. То же самое относится и к KNN. Предполагается, что подобные точки существуют в непосредственной близости и все экземпляры соответствуют точкам в n-мерном пространстве Rn.
«K» в KNN относится к количеству соседей, которые алгоритм считает назначенными между всеми точками данных. Например, в случае K=3 весь обучающий набор, а также новые точки данных будут назначены любому из 3-х соседей. Это значение «K» требуется KNN перед инициализацией.
KNN на самом деле не строит традиционную известную модель во время обучения, вместо этого он просто сохраняет все точки обучающих данных. Весь этот набор используется в момент предсказания. Чтобы эффективно реализовать этот длинный расчет, KNN использует сложную структуру данных с разделением пространства, известную как дерево k-d, для организации точек данных в k-мерном пространстве.
Примечательные моменты по характеристикам KNN
KNN — это метод обучения на основе экземпляров, потому что вместо изучения явных описаний целевой функции он просто сохраняет обучающие образцы. Обобщение откладывается до тех пор, пока не потребуется классифицировать новый экземпляр. Когда KNN сталкивается с новым экземпляром, он сначала проверяет его связь с сохраненными образцами, чтобы присвоить значение целевой функции новому экземпляру.
KNN называется методом ленивого обучения, потому что он не выводит какую-либо дискриминационную функцию, а вместо этого откладывает обработку до тех пор, пока не будет выполнена классификация для нового экземпляра. Ключевым преимуществом ленивого обучения является то, что оно не оценивает какую-либо целевую функцию для всего пространства, но KNN может оценивать ее локально и по-разному для каждого нового экземпляра, подлежащего классификации.
KNN — это непараметрический алгоритм, потому что он не делает никаких предположений о функциональной форме функции отображения, кроме шаблона распределения данных, который, вероятно, будет иметь аналогичную выходную переменную. Он способен вписаться в большое количество функциональных форм.
Как это работает тогда?
Как мы уже знаем, для работы KNN требуется число «K». Во время обучения (хотя оно на самом деле ничему не учится) все очки сохраняются.
Во время прогнозирования он вычисляет расстояние между всеми точками данных каждой обучающей выборки, используя любой метод расстояния, такой как Евклидов, Манхэттен, Минковский и т. д. (шаг 2). В случае вещественных входных данных всегда предпочтительнее использовать евклидово значение. Затем KNN сортирует значение расстояния в порядке возрастания.
Затем для нового экземпляра выбираются ближайшие точки «k». Из этих выбранных K-соседей подсчитывается общее количество точек данных для каждой категории или метки. Затем на основе голосования новый экземпляр классифицируется по меткам, для которых номер соседа максимален. Например, при K=3 из 3 ближайших соседей целевого экземпляра 1 принадлежит к классу A, а 2 принадлежит к классу B (шаг 3). Затем цель будет помечена как класс B на основе голосования большинства.
Чем регрессия с использованием KNN отличается от классификации?
Хотя KNN можно использовать для решения как типов классификации, так и типов регрессии, обычно он используется только для задач классификации. В задачах классификации метка цели определяется большинством голосов, то есть наиболее частым числом классов вокруг соседей целевой точки данных. Технически, когда есть только две категории, требуется большинство более 50%. Но в случае более двух требуемый процент порога большинства соответственно уменьшался.
Однако, поскольку задачи регрессии имеют дело с непрерывными переменными, применение голосования по большинству вообще невозможно. Итак, для предсказания используется среднее расстояние k ближайших соседей.
Как рассчитывается расстояние?
Обычно Евклидово расстояние используется в большинстве распространенных случаев, особенно когда признаки представляют собой реальное значение.
Учитывая две точки, A (x1, y1) и B (x2, y2), расстояние измеряется как d = √[ (x2 — x1)^2 + (у2 — у1)^2].
Есть много других популярных дистанционных методов, которые также считаются не менее важными. Лучший метод расстояния требуется выбирать либо по свойствам данных, либо по настройке гиперпараметров.
Манхэттенское расстояние используется для расчета между реальными векторами с использованием суммы их абсолютной разности. Аналогичным образом вычисляется Расстояние Хэмминга между двумя бинарными векторами. Индекс Жаккара, также известный как Коэффициент подобия Жаккара, вычисляет расстояние, оценивая сходство и разнообразие наборов выборок. Его лучше всего использовать с неструктурированными наборами данных, т. е. аудио, изображениями и т. д.
Как выбрать оптимальное количество соседей k?
Не существует конкретного метода определения значения k. С ним нужно поиграть, настроив гиперпараметр, чтобы получить наилучшее значение k. Оптимальное число зависит от набора данных, поскольку зашумленный набор данных имеет тенденцию работать лучше с большим числом k.
Всегда разумно выбирать нечетное значение «k», когда набор данных имеет четное количество классов. Это делается для того, чтобы избежать ничьей. Точно так же в случае наличия нечетного количества классов «k» должно быть четным числом. Ничьи можно разорвать, изменив значение «k» на ±1.
Идею компромисса смещения и дисперсии также можно увидеть в KNN. При выборе k следует соблюдать баланс. Например, если k=1, неизвестный экземпляр всегда будет относиться к той же категории, что и его единственный ближайший сосед. Это приведет к высокой дисперсии и низкому смещению. Обычно смещение = 0 при k = 1. По мере того, как мы увеличиваем значение смещения k, оно начинает увеличиваться. Для очень высокого значения k, поскольку смещение стало очень высоким, ошибка обучения сильно возрастает, что приводит к недообучению нашей модели. Когда k становится очень большим, сложность алгоритма также постепенно увеличивается, поскольку ему приходится учитывать больше соседей.
Помимо перекрестной проверки, есть еще один популярный метод выбора «k», то есть метод квадратного корня. Этот метод подразумевает, что «k» должно быть квадратным корнем из числа обучающих выборок. Следует отметить, что этот метод не следует рассматривать как эмпирическое правило.
Что следует учитывать перед использованием KNN?
Обучающие данные должны быть проверены задолго до того, как делать прогнозы с помощью KNN. В случае, если у нас есть пропущенные значения, расстояние между этими выборками не может быть рассчитано. Либо мы должны исключить эти точки, либо вписать пропущенные значения.
Наряду с обработкой пропущенных значений следует также отметить, что KNN использует весь набор данных и принимает решение только во время прогнозирования. С увеличением размера набора данных сложность возрастала. В случае большого куска данных во время выполнения будет много обработки, что может отрицательно сказаться на производительности. Итак, мы должны использовать KNN со сравнительно небольшим набором данных; она варьируется в зависимости от вычислительной мощности системы.
KNN хорошо подходит для данных меньшего размера, то есть для небольшого количества входных функций. По мере роста измерений KNN становится жертвой «Проклятия размерности».
Одна из основных проблем данных с более высокими размерностями заключается в том, что по мере роста размерности или количества признаков растет и пространство выборки. Чтобы представить данные в более высоких измерениях, данные помещаются в очень маленькое пространство измерения, оставляя большую часть пространства пустым. Таким образом, данные становятся разреженными. Например, если мы работаем с набором данных из 1 объекта, у нас есть 7 точек данных, а пространство выборки равно 10, тогда у нас есть 10–7 = 3 пробела на одномерном графике. Когда функция удваивается, пространство выборки становится равным 10² = 100, поэтому остается 100–7 = 93 места. Пространство данных растет экспоненциально, но не точки данных. Таким образом, точки данных, которые кажутся очень близкими в 1D или 2D плоскости, могут казаться очень далекими при построении в более высоком измерении. Это широко известно как проклятие размерности.
Чтобы избежать этого, мы можем либо выполнить выбор признаков, чтобы отсортировать важные признаки, либо использовать алгоритм уменьшения размерности, такой как PCA.
Один из обязательных методов, который мы не должны пропустить, — это нормализация данных. При расчете расстояния мы должны поддерживать диапазон всех функций в масштабе, подобном [0, 1]. В случае, если набор данных имеет гауссово распределение, лучше стандартизировать данные.
Подходящие сценарии для использования KNN
Компилируя вышеизложенное, KNN работает лучше всего, когда у нас есть относительно небольшой и низкоразмерный набор данных, все выборки помечены и не содержат шума, а функции представлены в нормализованной форме. Его также можно использовать на основе конкретных типов задач или наборов данных с определенным шаблоном.
Вот подробная статья, основанная на Визуализациях с использованием KNN на различных типах наборов данных [Ссылка].
KNN также может использоваться для создания механизмов рекомендаций, он предлагает решения различных финансовых проблем и экономического прогнозирования. Типы задач идентификации по образцу, такие как Классификация изображений или Классификация рукописных цифр, имеют широкий вариант использования с использованием KNN. Кроме того, KNN используется для выполнения некоторых предопределенных необходимых задач в сочетании с другими алгоритмами машинного обучения. Используется для заполнения пропущенных значений с помощью KNNImputer. При выполнении кластеризации DBScan KNN используется для нахождения оптимального значения гиперпараметра эпсилон.
Заключительная мысль
Мы всесторонне обсудили различные концепции и функции алгоритма KNN. Будучи ленивым учеником, KNN не имеет периода обучения, прост в реализации и адаптируется для учета любых новых случаев, но требует постоянного мониторинга после повторного развертывания и в процессе производства.
Но KNN очень чувствителен к зашумленным данным, склонен к переобучению и требует масштабирования функций. Будь то многомерный или большой набор данных, оба могут негативно повлиять на KNN.
У него очень мало гиперпараметров для настройки, в основном значение «K» и используемые метрики расстояния являются популярными гиперпараметрами настройки KNN. Конечно, KNN — это автономный алгоритм, но он широко используется в сочетании с другими алгоритмами машинного обучения.
Пожалуйста, не стесняйтесь добавлять любые пункты, которые, возможно, были упущены в этой статье.
Я хотел бы связаться с вами через LinkedIn.
