Algoritam k najbližih suseda (KNN)

Definicija i osnovne karakteristike

Ako idete na dečji rođendan i treba da kupite poklon za dete o čijim hobijima i interesovanjima ne znate mnogo, već samo znate da je u pitanju desetogodišnji dečak, postavili biste sebi pitanje: “Šta desetogodišnji dečaci vole?” i ako znate nekog drugog takvog dečaka, mogli biste da iskoristite njegova interesovanja za odluku o poklonu. Pretpostavka ovde je da će deca istog pola i istog uzrasta često imati slična interesovanja, odnosno iskoristili znanje o ciljnoj promenljivoj (interesovanje/preferenca o poklonu) slične opservacija za inferencu nepoznate opservacije. Ova ideja leži u srži sledećeg algoritma.

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 \(k\) najbližih tačaka (po euklidskom rastojanje, u prostoru definisanom vrednostima prediktora) iz trening skupa. Osnovna pretpostavka jeste da će tačke sa bliskim vrednostima prediktora često pripada istoj klasi.

Algoritam vrši predviđanje 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 klasifikacioni model. Ovaj model nije verovatnosni, a ni 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 predviđanja.

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 je nemoguće diferencirati po njima, i 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 ciljne promenljive 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.