kNN (k-ближайших соседей) — это непараметрический метод, используемый для классификации и регрессии. Идея проста: объект классифицируется большинством голосов его соседей, где объект присваивается классу, наиболее распространенному среди его k ближайших соседей. Для регрессии предсказывается среднее значение меток k ближайших соседей.
Ключевые аспекты:
- Параметр k: Количество ближайших соседей, учитываемых при принятии решения. Выбор
k сильно влияет на результат. Малое k может быть чувствительно к шуму, большое k может игнорировать локальные структуры.
- Метрика расстояния: Используется для определения "близости" между точками данных. Наиболее распространенные: евклидово расстояние, манхэттенское расстояние.
- Особенности:
- "Ленивый" алгоритм: обучение отсутствует или минимально (просто сохранение обучающих данных). Предсказание происходит только во время запроса.
- Прост в реализации и понимании.
- Производительность на этапе предсказания может страдать при больших наборах данных, так как требуется вычисление расстояний до всех обучающих примеров.
- Чувствителен к масштабу признаков.
- Может плохо работать на данных с высоким уровнем шума.
Этапы работы (для классификации):
- Выбрать значение
k.
- Выбрать метрику расстояния.
- Для нового объекта, для которого нужно сделать предсказание:
a. Вычислить расстояние между этим объектом и всеми объектами в обучающем наборе.
b. Выбрать
k ближайших объектов из обучающего набора.
c. Определить наиболее часто встречающийся класс среди этих k объектов.
d. Присвоить новому объекту этот класс.
Пример (псевдокод):
python