Какво е алгоритъмът k-близки съседи (kNN)?

kNN (k-близки съсед) е непараметричен метод, използван за класификация и регресия. Идеята е проста: обектът се класифицира от мнозинството гласове на неговите съседи, където обектът се присвоява към класа, който е най-разпространен сред неговите k най-близки съседи. За регресия се предсказва средната стойност на етикетите на k-те най-близки съседи.

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

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

Етапи на работа (за класификация):

1. Изберете стойност k.
2. Изберете метрика за разстояние.
3. За нов обект, за който трябва да се направи предсказание: a. Изчислете разстоянието между този обект и всички обекти в обучаващия набор. b. Изберете k-те най-близки обекта от обучаващия набор. c. Определете най-често срещания клас сред тези k обекта. d. Присвоете на новия обект този клас.

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

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

# Функция за намиране на k-те най-близки съседи и предсказване на класа
def predict(training_data, new_data_point, k, distance_metric):
    разстояния = []
    за всеки data_point в training_data:
        dist = distance_metric(new_data_point, data_point['features'])
        разстояния.append((dist, data_point['label']))

    # Подреждане по разстояние и избор на k-те най-близки
    разстояния.sort(key=lambda x: x[0])
    k_nearest = разстояния[:k]

    # Броене на гласовете за класовете
    гласове = {}
    за dist, label в k_nearest:
        гласове[label] = гласове.get(label, 0) + 1

    # Определяне на класа с най-много гласове
    predicted_class = max(гласове, key=гласове.get)
    връщане predicted_class