Metoda k-cel mai apropiat vecin

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 septembrie 2019; verificările necesită 5 modificări .

Algoritmul -nearest neighbors $k$ ( k-NN) este un algoritm metric pentru clasificarea sau regresia automată a obiectelor .

În cazul utilizării metodei de clasificare, obiectul este atribuit clasei care este cea mai comună între vecinii acestui element, ale cărei clase sunt deja cunoscute. În cazul utilizării metodei de regresie , obiectului i se atribuie valoarea medie a obiectelor cele mai apropiate de el, ale căror valori sunt deja cunoscute. $k$ $k$

Algoritmul poate fi aplicat mostrelor cu un număr mare de atribute (multidimensionale). Pentru a face acest lucru, înainte de a aplica, trebuie să definiți funcția de distanță ; versiunea clasică a unei astfel de funcții este metrica euclidiană [1] [2] .

Normalizare

Diferite atribute pot avea diferite intervale de valori reprezentate în eșantion (de exemplu, atributul A este reprezentat în intervalul de la 0,1 la 0,5, iar atributul B este reprezentat în intervalul de la 1000 la 5000), apoi valorile distanței poate fi foarte dependent de atribute cu intervale mai mari. Prin urmare, datele sunt de obicei supuse normalizării. În analiza clusterului, există două modalități principale de normalizare a datelor: normalizarea minimax și normalizarea Z.

Normalizarea Minimax se face după cum urmează:

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

în acest caz, toate valorile se vor situa în intervalul de la 0 la 1; valorile binare discrete sunt definite ca 0 și 1.

Normalizare Z:

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

unde este abaterea standard ; în acest caz, majoritatea valorilor se vor încadra în intervalul . $\sigma$ $(-3\sigma ;3\sigma )$

Evidențierea atributelor semnificative

Unele atribute semnificative pot fi mai importante decât altele, astfel încât o anumită pondere poate fi atribuită fiecărui atribut (de exemplu, calculată folosind un eșantion de testare și optimizarea erorii de varianță). Astfel, fiecărui atribut i se va atribui o pondere , astfel încât valoarea atributului să se încadreze în interval (pentru valori normalizate folosind metoda minimax). De exemplu, dacă unui atribut i se atribuie o pondere de 2,7, atunci valoarea sa ponderată normalizată se va afla în intervalul $k$ $z_{k}$ $[0;z_{k}\max(k)]$ $[0;2,7]$

Mod ponderat

Cu o metodă ponderată, se ia în considerare nu numai numărul anumitor clase care au căzut în zonă, ci și distanța acestora față de noua valoare.

Pentru fiecare clasă se determină un punctaj de proximitate: $j$

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

unde este distanța de la noua valoare la obiect . $d(x,a_{i})$ $X$ $a_{i)$

Care clasă are o valoare de proximitate mai mare, acea clasă este atribuită noului obiect.

Folosind metoda, puteți calcula valoarea unuia dintre atributele obiectului clasificat pe baza distanțelor de la obiectele care au căzut în zonă și a valorilor corespunzătoare ale aceluiași atribut pentru obiecte:

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

unde este al-lea obiect care a căzut în zonă, este valoarea atributului obiectului dat , este noul obiect și este al-lea atribut al noului obiect. $a_{i}$ $i$ $k_i$ $k$ $a_{i}$ $X$ $x_k$ $k$

Link -uri

↑ S. Madeh Piryonesi, Tamer E. El-Diraby. Rolul analizei datelor în gestionarea activelor de infrastructură: depășirea problemelor legate de dimensiunea și calitatea datelor // Journal of Transportation Engineering, Part B: Pavements. — 2020-06. — Vol. 146 , iss. 2 . — P. 04020022 . — ISSN 2573-5438 2573-5438, 2573-5438 . - doi : 10.1061/JPEODX.0000175 . Arhivat 12 aprilie 2020.
↑ Hastie, Trevor. Elementele învățării statistice: extragerea datelor, inferența și predicția: cu 200 de ilustrații color . - New York: Springer, 2001. - xvi, 533 pagini p. - ISBN 0-387-95284-5 , 978-0-387-95284-0. Arhivat pe 9 august 2020 la Wayback Machine

kNN și Energie potențială (applet), EM Mirkes și Universitatea din Leicester. Appletul vă permite să comparați două metode de clasificare.
Daniel T. Larose, Discovering Knowledge in Data: O Introduction to Data Mining

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbare medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG