Mi a k-legközelebbi szomszédok (kNN)?
Definíció
A k-legközelebbi szomszédok (kNN) algoritmus felügyelt tanulási módszer, amely egy pontot a k legközelebbi tárolt pontjának többségi osztályával sorol be.
A kNN-nek nincs külön tanítási lépése. Tárolja a címkézett példákat, és a számítást akkor végzi, amikor lekérdezés érkezik. A scikit-learn ezt példányalapú, nem általánosító tanulásnak nevezi.
Működés
- Válassza ki a k értéket és a távolságmértéket. Az euklideszi távolság a leggyakoribb választás.
- Keresse meg a k tárolt pontot, amely a lekérdezési ponthoz a legközelebb van.
- Adja a lekérdezési pontnak azt az osztályt, amelyet e k pont többsége visel.
Alapértelmezés szerint minden szomszédnak egy szavazata van. Súlyozott kNN-nél a közelebbi szomszédok többet számítanak, például 1/d súllyal, ahol d a szomszéd távolsága.
A k megválasztása
A legjobb k értéke az adattól függ. A nagyobb k csökkenti a zajt, de elmosódottabbá teszi az osztályhatárokat. A keresztvalidáció az adatokból talál jó k értéket. Két osztálynál a páratlan k elkerüli a döntetlen szavazatokat.
Korlátok
- Ha a jellemzők különböző mértékegységűek vagy skálájúak, minden jellemző normalizálása sokat javíthat a pontosságon.
- A teljes keresés (brute force) a lekérdezést minden tárolt ponttal összehasonlítja. Ez kivitelezhetetlenné válik, ahogy a pontok száma nő.
- A fa alapú keresés, például a KD-fa, csak alacsony dimenzióban (kb. 20 alatt) gyors. Magas dimenzióban az euklideszi távolság is kevésbé hasznos, mert minden vektor közel egyformán messze esik a lekérdezéstől.
- Az olyan könyvtárak, mint a Faiss, nagy vektorhalmazokban keresnek. Pontos keresést és tömörített indexeket kínálnak. A tömörített indexek kevésbé pontos keresést adnak.
Történet
Evelyn Fix és Joseph Hodges 1951-ben, az USA légierejének repülőorvosi iskolájának (USAF School of Aviation Medicine) egyik jelentésében dolgozta ki először a módszert. Thomas Cover és Hart 1967-ben publikálta a „Nearest neighbor pattern classification” című cikket. Korlátlan mennyiségű tanítóadat mellett az 1-legközelebbi-szomszéd szabály hibaaránya nem lehet rosszabb a Bayes-hibaarány kétszerénél.
Gyakran Ismételt Kérdések
- Hogyan válasszuk meg a k értékét a kNN-ben?
- Próbáljon ki több k értéket keresztvalidációval, és tartsa meg azt, amelyik a legjobb eredményt adja a tanításban nem használt, külön adatokon. A legjobb k az adattól függ. A nagyobb k csökkenti a zajt, de elmosódottabbá teszi az osztályhatárokat. Kétosztályos feladatnál a páratlan k elkerüli a döntetlen szavazatokat.
- Szükséges-e tanítás a kNN-hez?
- Nem, a kNN-nek nincs külön tanítási lépése. Tárolja a címkézett példákat, és a teljes számítást akkor végzi, amikor lekérdezés érkezik. A scikit-learn ezt példányalapú, nem általánosító tanulásnak nevezi.
- Mi a súlyozott kNN?
- A súlyozott kNN a közelebbi szomszédok szavazatát jobban számítja, mint a távolabbiakét. Gyakori választás az 1/d súly, ahol d a szomszéd távolsága. A scikit-learnben az alapértelmezett az egyenlő súly, a weights = 'distance' pedig a távolság reciprokával arányos súlyokat ad.
Hivatkozások
- sklearn-neighbors
- scikit-learn User Guide, 1.6 Nearest Neighbors scikit-learn
- wikipedia-knn
- k-nearest neighbors algorithm Wikipedia
- faiss-readme
- Faiss: a library for efficient similarity search and clustering of dense vectors Meta Research (facebookresearch/faiss on GitHub)
- faiss-getting-started
- Faiss wiki: Getting started Meta Research (facebookresearch/faiss on GitHub)
Ez egy referenciabejegyzés. A TarmacView drónos ellenőrzési szolgáltatásokat nyújt, és nem árulja az ebben a szószedetben leírt felszereléseket vagy anyagokat.