Metoda k-nejbližšího souseda

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. září 2019; kontroly vyžadují 5 úprav .

Algoritmus -nejbližší sousedé $k$ ( k-NN) je metrický algoritmus pro automatickou klasifikaci nebo regresi objektů .

V případě použití metody pro klasifikaci je objekt přiřazen do třídy, která je nejběžnější mezi sousedy tohoto prvku, jejichž třídy jsou již známé. V případě použití metody pro regresi je objektu přiřazena průměrná hodnota objektů, které jsou mu nejblíže, jejichž hodnoty jsou již známé. $k$ $k$

Algoritmus lze aplikovat na vzorky s velkým počtem atributů (multidimenzionální). Chcete-li to provést, před aplikací musíte definovat funkci vzdálenosti ; klasickou verzí takové funkce je euklidovská metrika [1] [2] .

Normalizace

Různé atributy mohou mít různé rozsahy reprezentovaných hodnot ve vzorku (například atribut A je reprezentován v rozsahu od 0,1 do 0,5 a atribut B je zastoupen v rozsahu od 1000 do 5000), pak hodnoty vzdálenosti mohou být vysoce závislé na atributech s větším rozsahem. Data proto obvykle podléhají normalizaci. Při shlukové analýze existují dva hlavní způsoby normalizace dat: minimální normalizace a Z-normalizace.

Minimax normalizace se provádí následovně:

x'=(x-\min[X])/(\max[X]-\min[X])

v tomto případě budou všechny hodnoty ležet v rozsahu od 0 do 1; diskrétní binární hodnoty jsou definovány jako 0 a 1.

Z-normalizace:

x'=(xM[X])/\sigma[X]

kde je standardní odchylka ; v tomto případě bude většina hodnot spadat do rozsahu . $\sigma$ $(-3\sigma ;3\sigma )$

Zvýraznění významných atributů

Některé významné atributy mohou být důležitější než jiné, takže každému atributu lze přiřadit určitou váhu (například vypočítanou pomocí testovacího vzorku a optimalizace chyby rozptylu). Každému atributu tedy bude přiřazena váha , takže hodnota atributu bude spadat do rozsahu (pro normalizované hodnoty pomocí metody minimax). Pokud je například atributu přiřazena váha 2,7, bude jeho normalizovaná vážená hodnota ležet v rozsahu $k$ $z_{k}$ $[0;z_{k}\max(k)]$ $[0;2,7]$

Vážená cesta

U vážené metody se bere v úvahu nejen počet určitých tříd, které spadaly do oblasti, ale také jejich vzdálenost od nové hodnoty.

Pro každou třídu je určeno skóre blízkosti: $j$

Q_{j}=\sum _{{i=1}}^{n}{\frac {1}{d(x,a_{i})^{2}}}

kde je vzdálenost od nové hodnoty k objektu . $d(x,a_{i})$ $X$ ${\displaystyle a_{i))$

Která třída má vyšší hodnotu blízkosti, je tato třída přiřazena k novému objektu.

Pomocí této metody můžete vypočítat hodnotu jednoho z atributů klasifikovaného objektu na základě vzdáleností od objektů, které spadly do oblasti, a odpovídajících hodnot stejného atributu pro objekty:

x_{k}={\frac {\sum _{{i=1}}^{n}{k_{i}d(x,a_{i})^{2}}}{\součet _{{i =1}}^{n}{d(x,a_{i})^{2}}}}

kde je -tý objekt, který spadl do oblasti, je hodnota atributu daného objektu , je nový objekt a je -tý atribut nového objektu. $a_{i}$ $i$ $k_i$ $k$ $a_{i}$ $X$ $x_k$ $k$

Odkazy

↑ S. Madeh Piryonesi, Tamer E. El-Diraby. Role analýzy dat ve správě infrastrukturních aktiv: Překonání problémů s velikostí dat a kvalitou // Journal of Transportation Engineering, část B: Pavements. — 2020-06. — Sv. 146 , iss. 2 . — S. 04020022 . — ISSN 2573-5438 2573-5438, 2573-5438 . - doi : 10.1061/JPEODX.0000175 . Archivováno 12. dubna 2020.
↑ Hastie, Trevor. Prvky statistického učení: dolování dat, inference a predikce: s 200 plnobarevnými ilustracemi . - New York: Springer, 2001. - xvi, 533 stran s. - ISBN 0-387-95284-5 , 978-0-387-95284-0. Archivováno 9. srpna 2020 na Wayback Machine

kNN a Potential Energy (applet), EM Mirkes a University of Leicester. Applet umožňuje porovnat dvě klasifikační metody.
Daniel T. Larose, Objevování znalostí v datech: Úvod do dolování dat

Strojové učení a dolování dat
Úkoly	Klasifikační problém Učení bez učitele Učení za pomoci učitele Regresní analýza AutoML Pravidla asociace Extrakce funkcí Trénink vlastností Žebříčkový trénink Gramatické odvozování Online učení
Učení s učitelem	metoda k-nejbližšího souseda Naivní Bayesův klasifikátor rozhodovací strom Podpora vektorového stroje Lineární regrese Logistická regrese perceptron Soubory modelů Pytlování posilování náhodný les Relevantní vektorová metoda
shluková analýza	metoda k-means Metoda fuzzy shlukování Hierarchické shlukování EM algoritmus BŘÍZA LÉK DBSCAN OPTIKA Střední posun
Redukce rozměrů	Faktorová analýza Metoda hlavní součásti CCA ICA LDA Nezáporná expanze matice t-SNE
Strukturální prognózy	Graf pravděpodobnosti modelu Bayesovská síť Skrytý Markovův model CRF
Detekce anomálií	metoda k-nejbližšího souseda Místní úroveň emisí
Grafové pravděpodobnostní modely	Bayesovská síť Markovská síť Skrytý Markovův model
Neuronové sítě	Limitovaný Boltzmannův stroj samoorganizující se mapa Aktivační funkce Sigmoid softmax Radiální základní funkce Metoda zpětného šíření Hluboké učení Vícevrstvý perceptron Rekurentní neuronová síť dlouhodobá krátkodobá paměť Řízený rekurentní blok Konvoluční neuronová síť U-síť Autokodér
Posílení učení	Markovský proces Bellmanova rovnice Chamtivý algoritmus Q-learning SARSA Časový rozdíl (TD)
Teorie	Vapnik-Chervonenkis teorie Dilema zkreslení Teorie počítačového učení Empirická minimalizace rizika Occam se učí PAC učení Statistická teorie učení
Časopisy a konference	NeurIPS ICML ML JMLR ArXiv:cs.LG