kNN (k-ближайших соседей) — это непараметрический метод, используемый для классификации и регрессии. Идея проста: объект классифицируется большинством голосов его соседей, где объект присваивается классу, наиболее распространенному среди его k ближайших соседей. Для регрессии предсказывается среднее значение меток k ближайших соседей.

Ключевые аспекты:

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

Этапы работы (для классификации):

Выбрать значение k.
Выбрать метрику расстояния.
Для нового объекта, для которого нужно сделать предсказание: a. Вычислить расстояние между этим объектом и всеми объектами в обучающем наборе. b. Выбрать k ближайших объектов из обучающего набора. c. Определить наиболее часто встречающийся класс среди этих k объектов. d. Присвоить новому объекту этот класс.

Пример (псевдокод):

# Функция для вычисления евклидова расстояния
def euclidean_distance(p1, p2):
    # ... расчёт расстояния ...

# Функция для поиска k ближайших соседей и предсказания класса
def predict(training_data, new_data_point, k, distance_metric):
    distances = []
    for data_point in training_data:
        dist = distance_metric(new_data_point, data_point['features'])
        distances.append((dist, data_point['label']))

    # Сортировка по расстоянию и выбор k ближайших
    distances.sort(key=lambda x: x[0])
    k_nearest = distances[:k]

    # Подсчёт голосов классов
    class_votes = {}
    for dist, label in k_nearest:
        class_votes[label] = class_votes.get(label, 0) + 1

    # Определение класса с наибольшим количеством голосов
    predicted_class = max(class_votes, key=class_votes.get)
    return predicted_class

Что такое алгоритм k-ближайших соседей (kNN)?