Идея алгоритма k- ближайших соседей (k-NN) заключается в использовании неизвестных характеристик примера, которые известны, для определения его классификации.

Сначала в алгоритм передаются некоторые классифицированные образцы. Когда дается новая неклассифицированная выборка, алгоритм находит k ближайших соседей для новой выборки и определяет, какой должна быть ее классификация в соответствии с классификацией классифицированных выборок, которые были заданы как обучающая выборка.

Алгоритм иногда называют ленивой классификацией, потому что во время "обучения" он ничего не делает - просто сохраняет образцы, и вся работа выполняется во время классификации.

Алгоритм

К алгоритму -NN является одним из наиболее простых из всех алгоритмов машинного обучения. Недостатком алгоритма k-NN является его чувствительность к локальной структуре данных.

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

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

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

Часто точность классификации k-NN может быть значительно улучшена, если метрика расстояния изучена с помощью специализированных алгоритмов, таких как анализ компонентов ближайшего соседства с большим запасом или соседства.

Полезные ссылки

• алгоритм k-ближайших соседей - википедия

• k-ближайшие соседи - Классификация

• Как работает алгоритм k-NN