k-nearest neighbors algorithm

k-nearest neighbors algorithm (tsz. k-nearest neighbors algorithms)

1. (informatika)

A k-Nearest Neighbors (k-NN) egy felügyelt gépi tanulási algoritmus, amelyet osztályozási (classification) és regressziós (regression) feladatokra is használnak. Az algoritmus alapötlete egyszerű: egy adott új adatpontot annak a k legközelebbi ismert szomszédja alapján sorolunk be.

• Adott egy címkézett adathalmaz (tanulóhalmaz).
• Egy új mintát szeretnénk osztályozni.
• A minta legközelebbi k szomszédját (legtöbb esetben Euklideszi távolság alapján) kiválasztjuk.
• Az új minta osztályát a szomszédok többségi osztálya (vagy regresszió esetén az átlagos értéke) alapján határozzuk meg.

1. Válassz ki egy k értéket (pl. k = 3).
2. Számítsd ki a távolságot az ismeretlen pont és az összes tanulópont között.
3. Rendezés és kiválasztás: válaszd ki a k legközelebbi adatpontot.
4. Többségi szavazás (osztályozás) vagy átlagolás (regresszió).
5. Rendeld hozzá a megfelelő osztályt vagy értéket az új mintához.

• Euklideszi távolság: A leggyakrabban használt metrika, a két pont közötti „egyenes vonal”. Képlete:

  $${\displaystyle {\sqrt {\sum (x_{i}-y_{i})^{2}}}}$$

• Manhattan-távolság: Az értékek abszolút különbségeinek összege – olyan, mintha rácson sétálnánk. Képlete:

  $${\displaystyle \sum |x_{i}-y_{i}|}$$

• Minkowski-távolság: Egy általános távolságmérték, amely tartalmazza az Euklideszi (p=2) és Manhattan (p=1) távolságokat is. Képlete:

  $${\displaystyle \left(\sum |x_{i}-y_{i}|^{p}\right)^{1/p}}$$

• Hamming-távolság: Kategóriák esetén alkalmazzák – megadja, hogy hány pozícióban térnek el az elemek. Példa: 101010 vs 100110 → különbség 2 pozícióban → távolság = 2

Egy új pontot szeretnél osztályozni. A három legközelebbi szomszéd osztályai:

• Piros, Piros, Kék

Többségi szavazás alapján az új pont osztálya: Piros ✅

• k választása:
  • Kis k → érzékeny a zajra (túlillesztés)
  • Nagy k → simítja a döntési határokat (alulillesztés veszélye)
  • Általában páratlan szám, hogy elkerüljük a döntetleneket
• Súlyozás:
  • Egyes k-NN verziók súlyozzák a szomszédokat a távolságuk alapján → közelebbi pont nagyobb súlyt kap

• Egyszerű, intuitív működés
• Nem tanul előre, nincs modellépítés → lazy learning
• Nem feltételez adatdisztribúciót

• Lassú nagy adathalmazok esetén (minden keresésnél újra kell számolni a távolságokat)
• Nehézkes magas dimenzióban (curse of dimensionality)
• Nem skálafüggetlen → jellemzők normalizálása fontos

• Képfelismerés
• Ajánlórendszerek
• Orvosi diagnózis
• Szövegkategorizálás
• Hangminták osztályozása

A k-NN egy egyszerű, de hatékony algoritmus, amely a hasonlóság elvén működik. Bár nem mindig a leggyorsabb vagy legpontosabb, kiváló alapmodell vagy referencia a többi tanulási algoritmus összehasonlítására. Megfelelő adatelőkészítés és k paraméter választása esetén intuitív, pontos és jól alkalmazható sokféle problémára.

• k-nearest neighbors algorithm - Szótár.net (en-hu)
• k-nearest neighbors algorithm - Sztaki (en-hu)
• k-nearest neighbors algorithm - Merriam–Webster
• k-nearest neighbors algorithm - Cambridge
• k-nearest neighbors algorithm - WordNet
• k-nearest neighbors algorithm - Яндекс (en-ru)
• k-nearest neighbors algorithm - Google (en-hu)
• k-nearest neighbors algorithm - Wikidata
• k-nearest neighbors algorithm - Wikipédia (angol)