Классификация. Метод k-ближайших соседей

Метод k-ближайших соседей

Wiki

Метод k ближайших соседей (англ. k-nearest neighbor algorithm) - метод автоматической классификации объектов. Основным принципом метода ближайших соседей является то, что объект присваивается тому классу, который является наиболее распространённым среди соседей данного элемента.

Соседи берутся исходя из множества объектов, классы которых уже известны, и, исходя из ключевого для данного метода значения k высчитывается, какой класс наиболее многочислен среди них.

https://www.spc-consulting.ru/dms/machine%20learning/machinelearning/Overviews/KNearestNeighborsIntroductoryOverview%20.htm

Метод K - Ближайших соседей: Вводный Обзор

Классификация

Чтобы наглядно описать принципы работы метода K - Ближайших соседей, рассмотрим задачу классификации новых объектов (точек запроса) среди некоторого количества уже известных примеров. Эта задача проиллюстрирована ниже; примеры (известные экземпляры) отмечены знаком "+" или "-", а точки запроса - красным кружочком. Наша цель заключается в оценке (классификации) отклика точек запроса с использованием специально выбранного числа их ближайших соседей. Другими словами, мы хотим узнать, как классифицировать точки запроса: как знак "+" или как знак "-".

Для начала рассмотрим результат работы процедуры анализа К - БС с использованием одного ближайшего соседа. Ясно, что в этом случае отклик точки запроса будет предсказан как знак плюс (т.к. ближайшая соседняя точка имеет знак плюс). Теперь увеличим число используемых ближайших соседей до двух. На этот раз процедура К - БС не сможет классифицировать отклик точки запроса по причине того, что вторая ближайшая точка имеет знак минус и оба знака равноценны (т.е. победа с одинаковым количеством голосов). На следующем шаге увеличим число используемых ближайших соседей до 5. Таким образом, будет определена целая окрестность точки запроса (на графике ее граница отмечена красной окружностью). Так как в области содержится 2 точки со знаком "+" и 3 точки со знаком "-", алгоритм К - БС присвоит знак "-" отклику точки запроса.