KNN

Definicija i Osnovne Karakteristike

Algoritam K-najbližih suseda (eng. K-Nearest Neighbours - KNN) je jednostavan algoritam za klasifikaciju, koji funkcioniše tako što svrstava novi primer u klasu na osnovu njegovih “K” najbližih suseda iz trening skupa. Osnovna pretpostavka jeste da bliske tačke (na osnovu prediktora) biti često isto klasifikovane.

Algoritam vrši predikciju za novu tačku tako što pronađe K njoj najbližih tačaka za koje je već poznata klasa, i onda za klasu nove tačke izabere najpristutniju klasu među K najbližih suseda.

Ovaj algoritam nije tipičan kao mnogi drugi klasifikacioni modeli jer nema fazu treninga u kojoj se optimizuju parametri. Sve što je potrebno za primenu KNN-a jeste da se zadrže podaci iz trening skupa i koriste za upoređivanje sa novim podacima prilikom predikcije.

Jedini parametar ovog algoritma jeste hiperparametar K, koji označava broj najbližih suseda koje uzimamo u obzir prilikom klasifikacije novog primera. Hiperparametri su parametri koje ne možemo direktno optimizovati kroz proces treninga, često jer značajno menjaju strukturu modela, ili zato što uvek imaju negativan efekat na grešku modela pri treningu (regularizacioni hiperparametri - o ovome više u narednim časovima).

Ovaj algoritam se lako može prilagoditi i za regresione probleme, gde bi predikcija bila prosek vrednosti K najbližih suseda umesto klasifikacione odluke.

Prednosti KNN algoritma

1. Jednostavnost: KNN je intuitivan i lak za implementaciju, što ga čini privlačnim rešenjem za jednostavne klasifikacione zadatke.
2. Fleksibilnost: KNN može da prepozna i razlikuje kompleksne strukture u podacima, jer omogućava da se prostor deli proizvoljnim oblicima. Ovo ga razlikuje od algoritama poput logističke regresije, koja koristi linearnu granicu za razdvajanje klasa.

Mane KNN algoritma

1. Odabir hiperparametra K: Iako algoritam nema klasične parametre, odabir K može značajno uticati na tačnost klasifikacije. Niske vrednosti K mogu dovesti do preprilagođavanja (eng. overfitting), dok preveliko K može dovesti do potprilagođavanja (eng. underfitting).
2. Neefikasnost u predviđanju: KNN zahteva da se svi podaci iz trening skupa sačuvaju i upotrebe tokom predviđanja, što može predstavljati memorijski problem kada imamo veliki skup podataka. Osim toga, za svaku novu predikciju, KNN mora da računa udaljenosti do svih tačaka u trening skupu, što može biti vrlo vremenski zahtevno. Suprotno tome, logistička regresija može da čuva samo svoje koeficijente, čime štedi memoriju i ubrzava predikciju.

Skaliranje podataka i važnost u KNN algoritmu

Skaliranje podataka je standardna praksa za mnoge modele mašinskog učenja. U mnogim situacijama, skaliranje nije neophodno - na osnovni model linearne ili logistitčke regresije nema nikakvog uticaja - koeficijenti se lako prilagode bilo kojoj skali podataka. Ipak, na KNN algoritam skaliranje ima veliki uticaj.

Kada se koriste neskalirane ili originalne vrednosti prediktora za KNN algoritam, može doći do problema dominacije atributa s većim opsegom vrednosti:

Ako su atributi u različitim opsezima (npr. jedan atribut varira od 1 do 1000, dok drugi varira između 0 i 1), onda će atribut sa većim opsegom dominirati pri proračunu udaljenosti. Time će se gubiti važnost drugih atributa, čak i ako sadrže korisne informacije za klasifikaciju.

Sa druge strane, skaliranjem podataka, obično standardizacijom (postavljanjem prosečne vrednosti na nulu i standardne devijacije na jedan) ili normalizacijom (ograničavanjem vrednosti karakteristika u opsegu [0, 1] ili [-1, 1]), atributi postaju uporedivi. Na taj način svaki atribut jednako doprinosi pri proračunu udaljenosti, omogućavajući modelu da bolje prepozna strukturu podataka i tačnije klasifikuje nove primere.