Mis on k-lähedaste naabrite algoritm (kNN)?

kNN (k-lähim naabrid) on mitteparameetriline meetod, mida kasutatakse klassifikatsiooniks ja regressiooniks. Idee on lihtne: objekt klassifitseeritakse selle naabrite enamuse häälteenamusega, kus objektile omistatakse klass, mis on kõige levinum tema k lähima naabri seas. Regressiooni puhul prognoositakse k lähima naabri märkide keskmist väärtust.

Põhipunktid:

• k parameeter: Lähimate naabrite arv, mida arvestatakse otsuse tegemisel. k valik mõjutab tulemust tugevalt. Väike k võib olla tundlik müra suhtes, suur k võib ignoreerida kohalikke struktuure.
• Kauguse metrika: Kasutatakse andmepunktide "läheduse" määramiseks. Kõige levinumad: Eukleidiline kaugus, Manhattan kaugus.
• Omadused:
  • "Hiline" algoritm: õppimine puudub või on minimaalne (lihtsalt salvestatakse õppandmed). Ennustamine toimub ainult päringu ajal.
  • Lihtne teostada ja mõista.
  • Ennustamise jõudlus võib suurte andmekogumite puhul kannatada, kuna tuleb arvutada kaugused kõigi õppemudelite näidete vahel.
  • Tundlik tunnuste skaalale.
  • Võib halbade tulemustega töötada andmetel, millel on kõrge müra tase.

Tööetapid (klassifikatsiooni jaoks):

1. Valige k väärtus.
2. Valige kauguse metrika.
3. Uue objekti jaoks, mille jaoks tuleb teha ennustus: a. Arvutage kaugus selle objekti ja kõigi õppematerjalide vahel. b. Valige k lähimat objekti õppematerjalist. c. Määrake nende k objekti kõige sagedamini esinev klass. d. Omistage sellele uuele objektile see klass.

Näide (pseudokood):

# Eukleidilise kauguse arvutamise funktsioon
def euclidean_distance(p1, p2):
    # ... kauguse arvutamine ...

# Funktsioon leida `k` lähimat naabrit ja teha prognoos klassile
def predict(training_data, new_data_point, k, distance_metric):
    kaugused = []
    iga data_point kohta — training_data:
        dist = distance_metric(new_data_point, data_point['features'])
        kaugused.append((dist, data_point['label']))

    # Sorteeri kauguse järgi ja vali `k` lähimat
    kaugused.sort(key=lambda x: x[0])
    k_lähimat = kaugused[:k]

    # Hääletuse arvutamine klasside vahel
    hääled = {}
    iga dist, label — k_lähimat:
        hääled[label] = hääled.get(label, 0) + 1

    # Määra klass, millel on kõige rohkem hääli
    prognoositud_klass = max(hääled, key=hääled.get)
    tagasta prognoositud_klass