Čo je to algoritmus k najbližších susedov (kNN)?

kNN (k-blízkych susedov) je neparametrická metóda používaná na klasifikáciu a regresiu. Myšlienka je jednoduchá: objekt je klasifikovaný väčšinovým hlasovaním jeho susedov, kde sa objekt priraďuje k triede, ktorá je najrozšírenejšia medzi jeho k najbližšími susedmi. Pri regresii sa predpovedá priemerná hodnota značiek k najbližších susedov.

Kľúčové aspekty:

• Parameter k: Počet najbližších susedov, ktorí sa zohľadňujú pri rozhodovaní. Výber k výrazne ovplyvňuje výsledok. Malé k môže byť citlivé na šum, veľké k môže ignorovať lokálne štruktúry.
• Metóda vzdialenosti: Používa sa na určenie "blízkosti" medzi dátovými bodmi. Najbežnejšie: euklidovská vzdialenosť, manhattanská vzdialenosť.
• Vlastnosti:
  • "Lenivý" algoritmus: učenie chýba alebo je minimálne (len uloženie tréningových dát). Predpoveď sa vykonáva iba pri požiadavke.
  • Jednoduchý na implementáciu a pochopenie.
  • Výkon pri predpovedaní môže trpieť pri veľkých dátových súboroch, pretože je potrebné vypočítať vzdialenosti ku všetkým trénovacím príkladom.
  • Citlivý na škálovanie znakov.
  • Môže zle fungovať na dátach s vysokou úrovňou šumu.

Fázy práce (pre klasifikáciu):

1. Vybrať hodnotu k.
2. Vybrať metriku vzdialenosti.
3. Pre nový objekt, pre ktorý je potrebné urobiť predpoveď: a. Vypočítať vzdialenosť medzi týmto objektom a všetkými objektmi v tréningovej sade. b. Vybrať k najbližších objektov z tréningovej sady. c. Určiť najčastejšie sa vyskytujúcu triedu medzi týmito k objektmi. d. Priradiť novému objektu túto triedu.

Príklad (pseudokód):

# Funkcia na výpočet euklidovskej vzdialenosti
def euclidean_distance(p1, p2):
    # ... výpočet vzdialenosti ...

# Funkcia na nájdenie k najbližších susedov a predpovedanie triedy
def predict(training_data, new_data_point, k, distance_metric):
    vzdialenosti = []
    pre každý data_point v training_data:
        dist = distance_metric(new_data_point, data_point['features'])
        vzdialenosti.append((dist, data_point['label']))

    # Triedenie podľa vzdialenosti a výber k najbližších
    vzdialenosti.sort(key=lambda x: x[0])
    k_nearest = vzdialenosti[:k]

    # Počítanie hlasov tried
    hlasy = {}
    pre dist, label v k_nearest:
        hlasy[label] = hlasy.get(label, 0) + 1

    # Určenie triedy s najväčším počtom hlasov
    predicted_class = max(hlasy, k=hlasy.get)
    return predicted_class