3.8 Algoritam k-najbližih suseda

Neka se naš skup za obučavanje sastoji od parova brojeva \((x_1,x_2)(x_1,x_2)\) i odgovarajućih imena klasa. Parove možemo da prikažemo kao tačke u ravni gde prva koordinata \(x_1\) označava vrednost na x-osi, a druga koordinata \(x_2\) vrednost na y-osi. U praksi vrednosti \(x_1\) i \(x_2\) uvek vežemo za neke konkretne atribute, na primer, temperaturu i vlažnost vazduha, ali sada o njima možemo da razmišljamo kao o nekim uopštenim vrednostima. Neka svaki od parova brojeva pripada jednoj od dveju klasa: crvenim trouglovima ili plavim kvadratima. Kako imamo samo dve klase, zaključuješ da je reč o binarnoj klasifikaciji. Zamisli sada da zeleni krug predstavlja novu instancu, novi par brojeva, za koji treba da odredimo kojoj klasi pripada: da li je to crveni trougao ili plavi kvadrat.

Skup za obučavanje

Algoritam k-najbližih suseda je algoritam klasifikacije koji kaže da prvo fiksiramo broj suseda (okolnih instanci) k na neku konkretnu vrednost i da zatim odredimo koliko među k-najbližih suseda ima crvenih i plavih: crveni sused je instanca koja pripada crvenoj klasi, a plavi sused instanca koji pripada plavoj klasi. Ako , na primer, broj k fiksiramo na vrednost 3, tri najbliža suseda zelenog kruga se nalaze unutar pune kružnice. To su dva crvena trougla i jedan plavi kvadrat.

 Dalje , algoritam k-najbližih suseda kaže da novu instancu, tj. novi par tačaka, pridružujemo klasi brojnijeg suseda: ako su crveni susedi brojniji, za novu instancu ćemo reći da pripada crvenoj klasi i, slično, ako su plavi susedi brojniji, za novu instancu ćemo reći da pripada plavoj klasi. Ovaj vid zaključivanja možeš da razumeš i kao izreku ”s kim si, takav si” u svetu mašinskog učenja.

 U našem primeru, kada je vrednost broja k fiksirana na 3, zaključićemo da zeleni krug treba da pridružimo crvenoj klasi jer imamo dva crvena suseda i jednog plavog.

 Hajde da vidimo šta će se dogoditi ako broja k fiksiramo na vrednost 5. Na slici je ovo susedstvo prikazano isprekidanom kružnicom. Kako se sada tu nalaze tri plava kvadrata i dva crvena trougla, zaključak bi bio da zeleni krug treba da pridružimo plavoj klasi.

 Ova sekcija je uparena sa Jupyter sveskom 08-k-nearest_neighbors.ipynb. Da bi mogao da pratiš sadržaj dalje, klikni na link, a potom i na dugme   da bi se sadržaj otvorio u okruženju   Google Colab  . Ukoliko sveske pregledaš na lokalnoj mašini, među sadržajima pronađi svesku sa istim imenom i pokreni je. Za detaljnije instrukcije pogledaj sekciju   Hands-on zona   i lekciju   Jupyter sveske za vežbu  .

Prateći materijal sadrži pomenuti skup tačaka i aplikaciju u kojoj možeš da ispitaš šta će se dogoditi ako odabereš neku drugu vrednost broja k. S obzirom na to da algoritam treba da odluči kojih suseda ima više, mudro je da biraš neparne vrednosti broja k.

 Primetimo da osim od broja suseda k, rezultat algoritma zavisi i od načina na koji merimo udaljenosti do suseda! Da bismo pronašli najbliže susede, moramo nekako da izmerimo rastojanje do njih.

 Do sada smo se na časovima matematike susretali sa rastojanjem koje se zove euklidsko. Podsetimo se, euklidsko rastojanje između tačaka \(A\)i \(B\) se računa kao dužina duži koja spaja tačke \(A\) i \(B\). Na primer, za tačke \(A =(0,0)\) i \(B =(3,4)\) euklidsko rastojanje se računa kao \(\sqrt{(3 − 0)^2 +(4 − 0)^2} = 5\)

Euklidsko rastojanje

Postoje i mnoga druga rastojanja. Na primer, može ti biti zaniljivo Menhetn rastojanje. Za razliku od euklidskog rastojanja koje računa”hipotenuzu” trougla određenog tačkama \(A\) i \(B\) i \(O\) (ako pratimo prethodnu sliku), Menhetn rastojanje računa zbir ”kateta” ovog trougla. Za tačke \(A\) i \(B\) vrednost Menhetn rastojanja bi iznosila \(| 3 − 0 | + | 4 − 0 | = 7\). 

Koje rastojanje ćemo odabrati zavisi od prirode zadatka i smisla koji imaju atributi sa kojima radimo. U opštem slučaju možemo da oprobamo više rastojanja i odaberemo ono za koje dobijamo najbolje rezultate. O tome ćemo još govoriti u nastavku. Važno je naglasiti da funkcija mora da zadovoljava neka određena matematička svojstva da bi je proglasili rastojanjem pa zato ne može baš svaka funkcija da nam bude od pomoći.

 Baš kao i drugi algoritmi mašinskog učenja, algoritam k-najbližih suseda se obučava nad skupom za treniranje. Zanimljivo je primetiti da se faza učenja u ovom algoritmu zapravo svodi samo na čuvanje skupa podataka. U drugim algoritmima, kao što je linearna regresija ili logistička regresija, videli smo da se u ovoj fazi izračunavaju vrednosti nekih parametara koji se pojavljuju u modelu tako što se traži minimum funkcije greške. Algoritam k-najbližih suseda nije takav. Preslikavanje koje učimo nije određeno nekom konkretnom funkcijom već samim podacima i koracima koje treba da sprovedemo. Zato je uobičajeno da modele koji imaju ovo svojstvo zovemo   neparametarskim modelima  .

 Algoritam k-najbližih suseda ceo posao realizuje u toku primene, tj. odlučivanja o tome kojoj klasi pripada nova instanca. Kada treba klasifikovati novu instancu, prvo izračunamo rastojanje nove instance od svih instanci u skupu podataka za treniranje. Zatim sortiramo ova rastojanja od najmanjeg do najvećeg. Prva k rastojanja zadržavamo (jer su to rastojanja do k najbližih suseda) i biramo instance iz skupa za treniranje na koje se odnose. Dalje pratimo šta se događa u prostoru njihovih obeležja i tražimo najbrojnije obeležje, tj. najbrojniju klasu. Kao što smo videli u uvodnom primeru, novu instancu treba da pridružimo klasi koja je najbrojnija.

 Ovaj algoritam je jednostavno i implementirati pa zasučimo rukave i počnimo!

Zamislićemo da radimo sa skupom podataka koji smo do sada koristili i da svaka instanca ima oblik \((x1, x2, obelezje\) gde je obelezjeobelezje vrednost 0 za crvenu boju ili 1 za plavu.

Za merenje rastojanja između instanci koristićemo funkciju euklidsko_rastojanje, koja je definisana sledećim blokom koda:

def euclidean_distance(instance1, instance2):
  return np.sqrt((instance1[0]-instance2[0])**2 + (instance1[1]-instance2[1])**2)

Sam algoritam k-najbližih suseda je predstavljen sledećim blokom koda:

def kNN(k, instances, new_instance, classes={0: 'red', 1: 'blue'}):

  # first, calculate the distances between the new instance and all instances in the dataset
  distances = [euclidean_distance(instance, new_instance) for instance in instances]

  # then sort the distances, extract the k smallest ones and the corresponding instances
  # declare them as neighbors
  neighbors = np.argsort(distances)[0:k]

  # then read the labels of the neighbors and count them
  neighbor_labels = [instances[neighbor][2] for neighbor in neighbors]
  label_counts = np.bincount(neighbor_labels)

  # the label of the new instance will be the label of the most frequent neighbor
  label = np.argmax(label_counts)

  return classes[label]

U njemu, kao što smo diskutovali, sprovodimo sledeće korake:

1. izračunavamo rastojanje od nove instance do svih instanci u skupu podataka,
2. zatim sortiramo rastojanja i izdvajamo k najmanjih,
3. instance kojima odgovaraju izdvojena rastojanja proglašavamo susedima,
4. u skupu izdvojenih suseda prebrojavamo najbrojnije,
5. zaključujemo da nova instanca pripada klasi najbrojnijeg suseda.

 Funkciju kNN možeš da probaš u pratećoj svesci. Na engleskom jeziku se algoritam k-najbližih suseda zove   k-nearest-neighbours   pa se često susreće skraćeno ime   k-NN  . Otuda i ime funkcije.

Ostalo je još da naučimo kako to da odaberemo baš najbolju vrednost broja k. O tome ćemo govoriti u sledećoj lekciji.

Show answer

Show answer