Metoda cea mai apropiată de vecin: exemplu de lucru

Metoda celui mai apropiat vecin este cel mai simplu clasificator metric, care se bazează pe evaluarea asemănării diferitelor obiecte.

Obiectul analizat se referă la clasa la care fac parte subiecții eșantionului de antrenament. Să aflăm care este metoda celui mai apropiat vecin. Să încercăm să înțelegem această problemă complexă, să oferim exemple de tehnici diferite.

Ipoteza metodei

Metoda cea mai apropiată de vecin poate fi considerată algoritmul cel mai frecvent utilizat pentru clasificare. Un obiect care face obiectul clasificării aparține acelei clase y_i, căruia îi aparține cel mai apropiat obiect al eșantionului de formare x_i.

Specificitatea metodologiei celor mai apropiați vecini

Metoda k a celor mai apropiați vecini permite creșterea fiabilității clasificării. Obiectul analizat aparține aceleiași clase ca majoritatea vecinilor săi, adică obiectele k apropiate de acesta din proba analizată x_i. Atunci când rezolvăm probleme cu două clase, numărul de vecini va fi ciudat pentru a elimina situația de ambiguitate, în cazul în care același număr de vecini vor aparține diferitelor clase.

Tehnica cântăreților vecini

Metoda postgresql a celui mai apropiat vector vecin este utilizată atunci când numărul de clase nu este mai mic de trei, iar ciudățenia nu poate fi utilizată. Dar ambiguitatea apare chiar și în aceste cazuri. Apoi, vecinul i primește greutatea w_i, care scade cu gradul în creștere de vecin i. Obiectul se referă la o clasă care va avea o greutate totală maximă în rândul vecinilor apropiați.

Ipoteza compactă

În centrul tuturor metodelor de mai sus este ipoteza compactității. Aceasta implică o legătură între măsura de similitudine a obiectelor și apartenența lor la o clasă. În această situație, granița dintre diferitele vederi are o formă simplă, iar clasele creează zone mobile mobile în spațiul obiectelor. Sub astfel de domenii în analiza matematică, se obișnuiește să se înțeleagă seturi de margini închise. Această ipoteză nu este legată de percepția zilnică a acestui cuvânt.

Formula de bază

Să analizăm mai detaliat metoda celui mai apropiat vecin. În cazul în care învățarea propusă tipul probei „obiect-răspuns» X ^ m = {(x_1, y_1), dots, (x_m, y_m) } - dacă funcția setată la distanță rho (x, x „) pentru o multitudine de obiecte care este reprezentată sub forma unui model adecvat de similitudine a obiectelor, deoarece valoarea acestei funcții crește, similaritatea dintre obiectele x, x `scade.

Pentru orice obiect u, construim obiectele eșantionului de antrenament x_i pe măsură ce distanțele la u cresc:

Rho (u, X_ {1} u) leq rho (u, X_ {2} u) leq cdots leq rho (u, X_ {u} m-),

unde x_ {i-u} caracterizează obiectul eșantion de antrenament, care este vecinul i al obiectului original u. Utilizăm această notație pentru răspunsul la vecinul i: y_ {i-u}. Ca rezultat, obținem că un obiect arbitrar u provoacă o schimbare în numerotarea propriului eșantion.

Determinarea numărului de vecini k

Metoda celui mai apropiat vecin la k = 1 este capabilă să ofere o clasificare eronată, nu numai pe obiectele de emisie, ci și pentru alte clase situate în apropiere.

Dacă luăm k = m, algoritmul va fi cât mai stabil posibil și degenerat într-o valoare constantă. De aceea, pentru fiabilitate, este important să nu permitem indicatorii extreme k.

În practică, criteriul de control al alunecării este folosit ca indicator optim k.

Abolirea emisiilor

Obiectele de formare sunt în mare parte inegale, dar printre ele există și cele care au caracteristici caracteristice clasei și se numesc standarde. Cu apropierea subiectului de eșantionul ideal, probabilitatea apartenenței la o anumită clasă este mare.

Cât de eficientă este metoda celor mai apropiați vecini? Un exemplu poate fi analizat pe baza categoriilor de obiecte periferice și neinformative. Se presupune că mediul înconjurător este înconjurat de alți reprezentanți ai acestei clase. Dacă le eliminați din eșantion, calitatea clasificării nu va fi afectată.

Pentru a intra într-o astfel de mostră poate fi un anumit număr de emisii de zgomot care sunt "în grosul" unei alte clase. Eliminarea are în principal un efect pozitiv asupra calității clasificării efectuate.

Dacă obiectele non-informative și de zgomot sunt eliminate din eșantion, mai multe rezultate pozitive pot fi așteptate în același timp.

Mai întâi de toate interpolare prin cel mai apropiat vecin permite îmbunătățirea calității clasificării, reducerea cantității de date stocate, reducerea timpului de clasificare, care este cheltuit pentru selectarea celor mai apropiate standarde.

Utilizarea probelor extra-mari

Metoda cea mai apropiată de vecin se bazează pe stocarea efectivă a obiectelor de antrenament. Pentru a crea eșantioane super-mari, utilizați probleme tehnice. Sarcina nu este pur și simplu să păstreze o cantitate semnificativă de informații, ci și într-un interval de timp minim pentru a reuși să găsească un obiect arbitrar u printre cei mai apropiați vecini k.

Pentru a face față acestei sarcini, se folosesc două metode:

• subțirați eșantionul aruncând obiecte care nu sunt informative;
• aplicați structuri eficiente speciale și indici de date pentru căutarea instantanee a celor mai apropiați vecini.

Reguli pentru selectarea metodologiei

Clasificarea a fost considerată mai sus. Metoda celui mai apropiat vecin este utilizată pentru a rezolva problemele practice în care funcția de distanță rho (x, x `) este cunoscută în prealabil. La descrierea obiectelor, vectorii numerici folosesc valoarea euclidiană. O astfel de alegere nu are o justificare specială, însă implică măsurarea tuturor semnelor "pe o scară unică". Dacă acest factor nu este luat în considerare, atunci valoarea metrică va fi dominată de semnul care are cele mai mari valori numerice.

În prezența unui număr semnificativ de caracteristici, calculând distanța ca sumă de abateri pentru caracteristicile specifice, apare o problemă de dimensionalitate serioasă.

Într-un spațiu de dimensiuni mari, toate obiectele vor fi departe unul de celălalt. În analiza finală, un eșantion arbitrar al vecinilor apropiați de obiectul studiului k va fi arbitrar. Pentru a elimina această problemă, se selectează un număr mic de semne informative. Algoritmii pentru calcularea estimărilor sunt construiți pe baza diferitelor seturi de caracteristici și pentru fiecare individ își construiesc funcția de proximitate.

concluzie

Calculele matematice implică adesea utilizarea unei varietăți de tehnici care au propriile caracteristici, avantaje și dezavantaje distincte. Metoda considerată a celor mai apropiați vecini permite rezolvarea problemelor destul de grave legate de caracterizarea obiectelor matematice. Conceptele experimentale, bazate pe tehnica analizată, sunt acum folosite în mod activ în instrumentele de inteligență artificială.

În sistemele expert, este necesar nu numai să se clasifice obiecte, ci și să se demonstreze utilizatorului o explicație a clasificării în cauză. În această metodă, explicațiile pentru un astfel de fenomen sunt exprimate prin relația obiectului cu o anumită clasă și, de asemenea, prin localizarea acesteia față de proba utilizată. Specialiști ai industriei juridice, geologi, medici, acceptă această logică "precedentă", o folosesc în mod activ în studiile lor.

Pentru ca metoda analizată să fie cât mai de încredere posibilă, eficientă, să ducă rezultatul dorit, este necesar să se ia indicatorul minim k și, de asemenea, să nu se permită emisii din obiectele analizate. De aceea se aplică metodologia de selectare a standardelor, iar valorile sunt optimizate.