Letecký slovník

Co je k nejbližších sousedů (kNN)?

Machine Learning · Classification 8 jazyky
Definice
Algoritmus k nejbližších sousedů (kNN) je metoda učení s učitelem, která bodu přiřadí třídu, kterou má většina z jeho k nejbližších uložených bodů.

Definice

Algoritmus k nejbližších sousedů (kNN) je metoda učení s učitelem, která zařadí bod podle nejčastější třídy mezi jeho k nejbližšími uloženými body.

kNN nemá explicitní krok trénování. Ukládá označené příklady a výpočet provádí až při příchodu dotazu. Scikit-learn to nazývá učení založené na instancích bez zobecňování.

Jak funguje

  1. Zvolte k a míru vzdálenosti. Nejčastější volbou je euklidovská vzdálenost.
  2. Najděte k uložených bodů nejblíže dotazovanému bodu.
  3. Dotazovanému bodu přiřaďte třídu, kterou má většina z těchto k bodů.

Ve výchozím nastavení má každý soused jeden hlas. Ve váženém kNN se bližší sousedé počítají více, například s váhou 1/d, kde d je vzdálenost k sousedovi.

Volba k

Nejlepší hodnota k závisí na datech. Větší k potlačí šum, ale hranice tříd jsou méně výrazné. Křížová validace najde z dat dobrou hodnotu k. U dvou tříd se lichým k vyhnete shodným hlasům.

Omezení

  • Mají-li příznaky různé jednotky nebo měřítka, může normalizace každého příznaku výrazně zlepšit přesnost.
  • Vyhledávání hrubou silou porovnává dotaz s každým uloženým bodem. S rostoucím počtem bodů se to stane neproveditelným.
  • Vyhledávání se stromovou strukturou, například KD stromem, je rychlé jen v nízkých dimenzích (pod zhruba 20). Ve vysokých dimenzích je euklidovská vzdálenost také méně užitečná, protože všechny vektory jsou od dotazu téměř stejně daleko.
  • Knihovny jako Faiss prohledávají velké množiny vektorů. Nabízejí přesné vyhledávání a komprimované indexy. Komprimované indexy dávají méně přesné vyhledávání.

Historie

Evelyn Fix a Joseph Hodges metodu poprvé vyvinuli v roce 1951 v zprávě pro USAF School of Aviation Medicine. Thomas Cover a Hart publikovali „Nearest neighbor pattern classification“ v roce 1967. Při neomezeném množství trénovacích dat není chybovost pravidla nejbližšího souseda (1-NN) horší než dvojnásobek Bayesovy chyby.

Často kladené otázky

Jak se v kNN volí k?
Vyzkoušejte několik hodnot k pomocí křížové validace a ponechte tu, která dává nejlepší výsledek na datech vyčleněných z učení. Nejlepší k závisí na datech. Větší k potlačí šum, ale hranice tříd jsou méně výrazné. U úlohy se dvěma třídami se lichým k vyhnete shodným hlasům.
Potřebuje kNN trénink?
Ne, kNN nemá explicitní krok trénování. Ukládá označené příklady a veškeré výpočty provádí až při příchodu dotazu. Scikit-learn to nazývá učení založené na instancích bez zobecňování.
Co je vážené kNN?
Vážené kNN nechává bližší sousedy počítat ve hlasování více než vzdálenější. Častou volbou je váha 1/d, kde d je vzdálenost k sousedovi. Ve scikit-learn je výchozí rovnoměrná váha a weights = 'distance' dává váhy úměrné převrácené hodnotě vzdálenosti.

Reference

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)

Toto je referenční položka. TarmacView poskytuje služby inspekce drony a neprodává zařízení ani materiály popsané v tomto slovníku.

Začněte Potřebujete ověřit osvětlení vašeho letiště? TarmacView kontroluje PAPI, dráhu a přibližovací osvětlení dronem mezi pohyby letadel a dodává zprávu o shodě určenou pro vašeho regulátora. Inspekce vozovky a překážek jsou ve vývoji.
Pokračovat ve čtení

Zjistit více

03 STRÁNKY
Matice záměn
glossary

Matice záměn

Matice záměn je tabulka, která počítá, jak model klasifikace zařazuje položky do predikovaných tříd. Jak ji číst a které metriky z ní plynou.

FAISS
glossary

FAISS

FAISS je open-source knihovna, která v rozsáhlé množině najde vektory nejblíže dotazu. Typy indexů, exaktní a přibližné vyhledávání, kosinová podobnost.

Přenosové učení
glossary

Přenosové učení

Přenosové učení (transfer learning) znovu využívá model natrénovaný na jedné úloze k lepšímu učení nové úlohy. Typy přenosového učení, extrakce příznaků a dotrénování, kdy předtrénovat a kde se to setkává s kontrolou zpevněných ploch.