logo

Algoritam K-najbližeg susjeda (KNN) za strojno učenje

  • K-Nearest Neighbor jedan je od najjednostavnijih algoritama strojnog učenja koji se temelji na tehnici nadziranog učenja.
  • K-NN algoritam pretpostavlja sličnost između novog slučaja/podataka i dostupnih slučajeva i stavlja novi slučaj u kategoriju koja je najsličnija dostupnim kategorijama.
  • K-NN algoritam pohranjuje sve dostupne podatke i klasificira novu podatkovnu točku na temelju sličnosti. To znači da kada se pojave novi podaci, oni se mogu lako klasificirati u kategoriju dobrog paketa korištenjem K-NN algoritma.
  • K-NN algoritam se može koristiti za regresiju kao i za klasifikaciju, ali uglavnom se koristi za probleme klasifikacije.
  • K-NN je a neparametarski algoritam , što znači da ne donosi nikakve pretpostavke o temeljnim podacima.
  • Također se naziva a algoritam lijenog učenika jer ne uči odmah iz skupa za obuku, već pohranjuje skup podataka i u vrijeme klasifikacije izvodi radnju na skupu podataka.
  • KNN algoritam u fazi obuke samo pohranjuje skup podataka i kada dobije nove podatke, onda te podatke klasificira u kategoriju koja je mnogo slična novim podacima.
  • Primjer:Pretpostavimo da imamo sliku stvorenja koje izgleda slično mački i psu, ali želimo znati je li to mačka ili pas. Dakle, za ovu identifikaciju, možemo koristiti KNN algoritam, jer radi na mjeri sličnosti. Naš model KNN pronaći će slične značajke novog skupa podataka slikama mačaka i pasa i na temelju najsličnijih značajki smjestiti će ga u kategoriju mačaka ili pasa.
Algoritam K-najbližeg susjeda (KNN) za strojno učenje

Zašto nam treba K-NN algoritam?

Pretpostavimo da postoje dvije kategorije, tj. Kategorija A i Kategorija B, i imamo novu podatkovnu točku x1, pa će ta podatkovna točka ležati u kojoj od ovih kategorija. Za rješavanje ove vrste problema potreban nam je K-NN algoritam. Uz pomoć K-NN-a možemo lako identificirati kategoriju ili klasu određenog skupa podataka. Razmotrite dijagram u nastavku:

Algoritam K-najbližeg susjeda (KNN) za strojno učenje

Kako K-NN radi?

Rad K-NN-a može se objasniti na temelju donjeg algoritma:

    Korak 1:Odaberite broj K susjedaKorak 2:Izračunajte euklidsku udaljenost od K broj susjeda Korak-3:Uzmite K najbližih susjeda prema izračunatoj euklidskoj udaljenosti.Korak-4:Među ovim k susjedima izbrojite broj podatkovnih točaka u svakoj kategoriji.Korak-5:Dodijelite nove podatkovne točke onoj kategoriji za koju je broj susjeda maksimalan.Korak-6:Naš model je spreman.

Pretpostavimo da imamo novu podatkovnu točku i trebamo je staviti u traženu kategoriju. Razmotrite sliku u nastavku:

koliko je milijuna u milijardi
Algoritam K-najbližeg susjeda (KNN) za strojno učenje
  • Prvo ćemo odabrati broj susjeda, pa ćemo odabrati k=5.
  • Zatim ćemo izračunati Euklidska udaljenost između podatkovnih točaka. Euklidska udaljenost je udaljenost između dviju točaka, koju smo već proučavali u geometriji. Može se izračunati kao:
Algoritam K-najbližeg susjeda (KNN) za strojno učenje
  • Izračunavanjem euklidske udaljenosti dobili smo najbliže susjede, kao tri najbliža susjeda u kategoriji A i dva najbliža susjeda u kategoriji B. Razmotrite sliku ispod:
Algoritam K-najbližeg susjeda (KNN) za strojno učenje
  • Kao što vidimo 3 najbliža susjeda su iz kategorije A, stoga ova nova podatkovna točka mora pripadati kategoriji A.

Kako odabrati vrijednost K u K-NN algoritmu?

Ispod su neke točke koje treba zapamtiti prilikom odabira vrijednosti K u K-NN algoritmu:

  • Ne postoji određeni način za određivanje najbolje vrijednosti za 'K', pa moramo isprobati neke vrijednosti kako bismo iz njih pronašli najbolje. Najpoželjnija vrijednost za K je 5.
  • Vrlo niska vrijednost za K, kao što je K=1 ili K=2, može biti šumna i dovesti do učinaka odstupanja u modelu.
  • Velike vrijednosti za K su dobre, ali mogu naići na poteškoće.

Prednosti KNN algoritma:

  • Jednostavan je za implementaciju.
  • Otporan je na bučne podatke o treningu
  • Može biti učinkovitije ako su podaci o obuci veliki.

Nedostaci KNN algoritma:

  • Uvijek treba odrediti vrijednost K koja neko vrijeme može biti složena.
  • Trošak izračuna je visok zbog izračuna udaljenosti između podatkovnih točaka za sve uzorke obuke.

Python implementacija KNN algoritma

Da bismo izvršili Python implementaciju K-NN algoritma, koristit ćemo isti problem i skup podataka koje smo koristili u Logističkoj regresiji. Ali ovdje ćemo poboljšati performanse modela. Ispod je opis problema:

Problem za K-NN algoritam: Postoji tvrtka proizvođača automobila koja je proizvela novi SUV automobil. Tvrtka želi dati oglase korisnicima koji su zainteresirani za kupnju tog terenca. Dakle, za ovaj problem imamo skup podataka koji sadrži informacije o više korisnika putem društvene mreže. Skup podataka sadrži mnogo informacija, ali Procijenjena plaća i Dob razmotrit ćemo za nezavisnu varijablu i Kupljena varijabla je za zavisnu varijablu. Ispod je skup podataka:

Algoritam K-najbližeg susjeda (KNN) za strojno učenje

Koraci za implementaciju K-NN algoritma:

  • Korak prethodne obrade podataka
  • Prilagođavanje K-NN algoritma skupu za obuku
  • Predviđanje rezultata testa
  • Testirajte točnost rezultata (Stvaranje matrice zabune)
  • Vizualizacija rezultata ispitnog skupa.

Korak prethodne obrade podataka:

Korak prethodne obrade podataka ostat će potpuno isti kao i logistička regresija. Ispod je kod za to:

 # importing libraries import numpy as nm import matplotlib.pyplot as mtp import pandas as pd #importing datasets data_set= pd.read_csv('user_data.csv') #Extracting Independent and dependent Variable x= data_set.iloc[:, [2,3]].values y= data_set.iloc[:, 4].values # Splitting the dataset into training and test set. from sklearn.model_selection import train_test_split x_train, x_test, y_train, y_test= train_test_split(x, y, test_size= 0.25, random_state=0) #feature Scaling from sklearn.preprocessing import StandardScaler st_x= StandardScaler() x_train= st_x.fit_transform(x_train) x_test= st_x.transform(x_test) 

Izvršavanjem gornjeg koda, naš se skup podataka uvozi u naš program i dobro prethodno obrađuje. Nakon skaliranja značajki naš testni skup podataka izgledat će ovako:

Algoritam K-najbližeg susjeda (KNN) za strojno učenje

Iz gornje izlazne slike možemo vidjeti da su naši podaci uspješno skalirani.

    Prilagodba K-NN klasifikatora podacima o obuci:
    Sada ćemo prilagoditi K-NN klasifikator podacima o obuci. Da bismo to učinili, uvest ćemo KNighborsClassifier razred Sklearn susjedi knjižnica. Nakon uvoza klase, kreirat ćemo Klasifikator objekt klase. Parametar ove klase bit će
      n_susjeda:Za definiranje potrebnih susjeda algoritma. Obično je potrebno 5.metric='minkowski':Ovo je zadani parametar i on određuje udaljenost između točaka.p=2:Ekvivalentna je standardnoj euklidskoj metrici.
    Zatim ćemo prilagoditi klasifikator podacima o obuci. Ispod je kod za to:
 #Fitting K-NN classifier to the training set from sklearn.neighbors import KNeighborsClassifier classifier= KNeighborsClassifier(n_neighbors=5, metric='minkowski', p=2 ) classifier.fit(x_train, y_train) 

Izlaz: Izvršavanjem gornjeg koda, dobit ćemo izlaz kao:

freddie mercury
 Out[10]: KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski', metric_params=None, n_jobs=None, n_neighbors=5, p=2, weights='uniform') 
    Predviđanje rezultata testa:Kako bismo predvidjeli rezultat skupa testova, stvorit ćemo a y_pred vektor kao što smo radili u logističkoj regresiji. Ispod je kod za to:
 #Predicting the test set result y_pred= classifier.predict(x_test) 

Izlaz:

Izlaz za gornji kod će biti:

Algoritam K-najbližeg susjeda (KNN) za strojno učenje
    Stvaranje matrice zabune:
    Sada ćemo izraditi matricu zabune za naš K-NN model kako bismo vidjeli točnost klasifikatora. Ispod je kod za to:
 #Creating the Confusion matrix from sklearn.metrics import confusion_matrix cm= confusion_matrix(y_test, y_pred) 

U gornjem kodu smo uvezli funkciju confusion_matrix i pozvali je pomoću varijable cm.

Izlaz: Izvršavanjem gornjeg koda, dobit ćemo matricu kao u nastavku:

Algoritam K-najbližeg susjeda (KNN) za strojno učenje

Na gornjoj slici možemo vidjeti da postoji 64+29= 93 točna predviđanja i 3+4= 7 netočnih predviđanja, dok je u logističkoj regresiji bilo 11 netočnih predviđanja. Stoga možemo reći da je izvedba modela poboljšana korištenjem K-NN algoritma.

    Vizualizacija rezultata skupa treninga:
    Sada ćemo vizualizirati rezultat skupa za obuku za K-NN model. Kod će ostati isti kao u logističkoj regresiji, osim naziva grafikona. Ispod je kod za to:
 #Visulaizing the trianing set result from matplotlib.colors import ListedColormap x_set, y_set = x_train, y_train x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() - 1, stop = x_set[:, 0].max() + 1, step =0.01), nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01)) mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape), alpha = 0.75, cmap = ListedColormap(('red','green' ))) mtp.xlim(x1.min(), x1.max()) mtp.ylim(x2.min(), x2.max()) for i, j in enumerate(nm.unique(y_set)): mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1], c = ListedColormap(('red', 'green'))(i), label = j) mtp.title('K-NN Algorithm (Training set)') mtp.xlabel('Age') mtp.ylabel('Estimated Salary') mtp.legend() mtp.show() 

Izlaz:

Izvršavanjem gornjeg koda dobit ćemo graf ispod:

Algoritam K-najbližeg susjeda (KNN) za strojno učenje

Izlazni graf razlikuje se od grafa koji smo dobili u logističkoj regresiji. Može se razumjeti u sljedećim točkama:

    • Kao što vidimo, grafikon prikazuje crvenu i zelenu točku. Zelene točke su za varijablu Purchased(1), a crvene točke za varijablu Not Purchased(0).
    • Grafikon prikazuje nepravilnu granicu umjesto da prikazuje bilo kakvu ravnu liniju ili krivulju jer je to K-NN algoritam, tj. pronalaženje najbližeg susjeda.
    • Grafikon je klasificirao korisnike u točne kategorije budući da je većina korisnika koji nisu kupili SUV u crvenoj regiji, a korisnici koji su kupili SUV su u zelenoj regiji.
    • Grafikon pokazuje dobre rezultate, ali još uvijek postoje neke zelene točke u crvenom području i crvene točke u zelenom području. Ali to nije veliki problem jer se ovim modelom sprječavaju problemi s prekomjernim opremanjem.
    • Stoga je naš model dobro uvježban.
    Vizualizacija rezultata skupa testova:
    Nakon obuke modela, sada ćemo testirati rezultat stavljanjem novog skupa podataka, tj. Test skupa podataka. Kod ostaje isti osim nekih manjih izmjena: kao npr x_vlak i y_vlak bit će zamijenjen sa x_test i y_test .
    Ispod je kod za to:
 #Visualizing the test set result from matplotlib.colors import ListedColormap x_set, y_set = x_test, y_test x1, x2 = nm.meshgrid(nm.arange(start = x_set[:, 0].min() - 1, stop = x_set[:, 0].max() + 1, step =0.01), nm.arange(start = x_set[:, 1].min() - 1, stop = x_set[:, 1].max() + 1, step = 0.01)) mtp.contourf(x1, x2, classifier.predict(nm.array([x1.ravel(), x2.ravel()]).T).reshape(x1.shape), alpha = 0.75, cmap = ListedColormap(('red','green' ))) mtp.xlim(x1.min(), x1.max()) mtp.ylim(x2.min(), x2.max()) for i, j in enumerate(nm.unique(y_set)): mtp.scatter(x_set[y_set == j, 0], x_set[y_set == j, 1], c = ListedColormap(('red', 'green'))(i), label = j) mtp.title('K-NN algorithm(Test set)') mtp.xlabel('Age') mtp.ylabel('Estimated Salary') mtp.legend() mtp.show() 

Izlaz:

Algoritam K-najbližeg susjeda (KNN) za strojno učenje

Gornji grafikon prikazuje izlaz za skup testnih podataka. Kao što možemo vidjeti na grafikonu, predviđeni rezultat je dobar jer je većina crvenih točaka u crvenom području, a većina zelenih točaka je u zelenom području.

Međutim, postoji nekoliko zelenih točaka u crvenom području i nekoliko crvenih točaka u zelenom području. Dakle, ovo su netočna opažanja koja smo uočili u matrici zabune (7 Netočan izlaz).