Algoritmul -nearest neighbors ( 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.
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] .
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ă:
,î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:
unde este abaterea standard ; în acest caz, majoritatea valorilor se vor încadra în intervalul .
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
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:
,unde este distanța de la noua valoare la obiect .
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:
,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.
Învățare automată și extragerea datelor | |
---|---|
Sarcini | |
Învățarea cu un profesor | |
analiza grupului | |
Reducerea dimensionalității | |
Prognoza structurală | |
Detectarea anomaliilor | |
Modele grafice probabilistice | |
Rețele neuronale | |
Consolidarea învățării |
|
Teorie | |
Reviste și conferințe |
|