K-nearest neighbors problem

Angol

Főnév

K-nearest neighbors problem (tsz. K-nearest neighbors problems)

1. (informatika) A K-legközelebbi szomszéd (K-Nearest Neighbors, KNN) probléma a távolság- vagy hasonlóságalapú keresések egyik alapfeladata, amelynek célja, hogy egy adott lekérdezési ponthoz (query point) megtaláljuk a tanulóhalmazból („adatbázisból”) a ${\textstyle k}$ legközelebbi pontot.

---

1. Problémaformuláció

• Bemenet:

  1. Egy adatpontokból álló halmaz ${\textstyle {\mathcal {X}}=\{x_{1},\dots ,x_{n}\}\subseteq \mathbb {R} ^{d}}$.
  2. Egy távolságfüggvény ${\textstyle \mathrm {dist}$ :\mathbb {R} ^{d}\times \mathbb {R} ^{d}\to \mathbb {R} _{\geq 0}} (például euklideszi, Manhattan, Mahalanobis).
  3. Egy lekérdezési pont ${\textstyle q\in \mathbb {R} ^{d}}$.
  4. Egy pozitív egész ${\textstyle k\leq n}$.

• Kimenet: A ${\textstyle {\mathcal {X}}}$-beli pontok azon ${\textstyle k}$-es részhalmaza

  $$\mathrm {KNN} (q)={\bigl \{}\,x_{(1)},x_{(2)},\dots ,x_{(k)}{\bigr \}},$$

  ahol a rendezés úgy történik, hogy ${\textstyle \mathrm {dist} (q,x_{(1)})\leq \mathrm {dist} (q,x_{(2)})\leq \cdots }$.

---

2. Brute-force megoldás

A legegyszerűbb eljárás:

1. Minden adatponthoz kiszámoljuk ${\textstyle \mathrm {dist} (q,x_{i})}$ értékét: ${\textstyle O(nd)}$.
2. Rendezünk, vagy részben kiválasztjuk a legkisebb ${\textstyle k}$ értéket (heap-pel vagy Quickselecttel): további ${\textstyle O(n\log k)}$ idő.

Összesen: ${\textstyle O(n\,d+n\log k)}$. Kis adathalmazokra megfelelő, de nagy ${\textstyle n}$ vagy magas dimenzió (${\textstyle d}$) esetén lassú.

---

3. Gyorsító adatszerkezetek

3.1 KD-fa (KD-tree)

• ${\textstyle d}$ dimenzió mentén váltakozóan osztjuk fel rekurzívan a pontok terét hiper síkokkal.
• Lekérdezés: „branch-and-bound” módon haladunk le a fában, prun-oljuk azokat az ágakat, ahol a legközelebbi pont nem lehet bennük.
• Átlagos lekérdezési idő: ${\textstyle O(\log n)}$ kis ${\textstyle d}$-re, de a dimenzió növekedésével („átok”) romlik → gyakorlatban ${\textstyle d\lesssim 20}$.

3.2 Ball-fa (Ball-tree)

• A pontokat gömbökbe (ball) szervezzük, minden csomópont egy középpontot és sugárt tárol.
• Hasonló prune-elés: ha a lekérdezési ponttól nagyobb a távolság a gömbtől, mint a jelenlegi ${\textstyle k}$-adik legkisebb távolság, az ág eldobható.

3.3 VP-fa (Vantage-point tree)

• Minden csomópontban kijelölünk egy „vantage point”-ot, a többi pont távolságát ehhez kiszámolva particionálunk belső és külső gömbre.

3.4 Cover-tree, M-fa, R-fa

• Különböző fa- vagy rácsszerű struktúrák, amelyek a pontok közötti lefedettségre vagy minimum-maximum távolságokra építenek.

---

4. Approximate KNN (AKNN)

Nagy adat és/vagy magas dimenzió esetén gyakran elég közelítő eredmény:

1. Locality-Sensitive Hashing (LSH) – Hash-függvények, amelyek nagy valószínűséggel ugyanabba a bucketbe map-elik a valódi közelieket. – Parallellizálható, alacsony memóriaköltségű, de kvázi-probabilista garancia.
2. Random Projection – Johnson–Lindenstrauss lemma: magas ${\textstyle d}$-t lapítjuk alacsonyabb dimenzióra, miközben távolságokat közel megtartjuk.
3. Graph-based módszerek – Navigable Small World graf, Hierarchical Navigable Small World (HNSW): pontok k‐legközelebbieként élek, graf-bejárás a lekérdezés.
4. Quantization / Product Quantization – Adatok klaszterezése és tömörített kódtér, közelítő távolságszámítás gyors lookup-okkal.

---

5. Alkalmazások

• Osztályozás (KNN classifier) – Címkézett tanulóhalmaz esetén a lekérdezett pontot a ${\textstyle k}$ legközelebbi címkéjének többségi szavazata alapján kategorizáljuk.
• Reggresszió (KNN regression) – A lekérduési pont értékét a ${\textstyle k}$ legközelebbi pont értékeinek átlaga vagy súlyozott átlaga adja.
• Ajánlórendszerek – Felhasználók vagy termékek vektoros reprezentációja; hasonló profilok keresése.
• Képfeldolgozás, keresés – SIFT‐, CNN‐feature‐ök lekérdezése társkereső adatbázisban.
• Rendészeti adatbányászat – Anomália‐detektálás: a lekérdezési ponttól távol esők potenciális kilógók.

---

6. Összefoglaló

• A KNN-probléma: ${\textstyle k}$ legközelebbi pont keresése adott adatbázisban és távolságfüggvénnyel.
• Brute-force: egyszerű, de ${\textstyle O(n\,d)}$ lassú nagy adatra.
• Fa- és rácsszerkezetek (KD-fa, Ball-fa stb.): gyorsabb indexelést tesznek lehetővé, de korlátot jelent a dimenzió.
• Approximate módszerek (LSH, graf-alapú, quantization): nagy méretekben, magas dimenzióban is skálázhatók, kis pontosság-veszteséggel.
• Alkalmazások széles skálán: osztályozás, regresszió, ajánlórendszerek, anomália‐detektálás, képfeldolgozás.

További információk

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