Algoritmi k-fqinjët më të afërt (kNN), është një klasifikues mësimi joparametrik, i mbikëqyrur, i cili përdor afërsinë për të bërë klasifikime ose parashikime rreth grupimit të një pike të dhënash individuale. Ndërsa mund të përdoret për problemet e Regresionit ose Klasifikimit, ai zakonisht përdoret si një algoritëm klasifikimi, duke punuar jashtë supozimit se pika të ngjashme mund të gjenden pranë njëra-tjetrës.
Grafika e mësipërme tregon se si funksionon një klasifikues kNN.
Intuitë
Algoritmi kNN është i ndryshëm nga algoritmet e tjera të mësimit të makinerive. Çdo model ML ka formulën e tij specifike që duhet të vlerësohet gjatë trajnimit. Por, formula e algoritmit kNN llogaritet gjatë parashikimit dhe jo gjatë trajnimit. Pse? Për shkak të intuitës së algoritmit kNN, i cili është,
“Kur të arrijë një pikë e re e të dhënave, algoritmi kNN do të fillojë duke gjetur fqinjët më të afërt të kësaj pike të re të të dhënave. Pastaj merr vlerat e veçorive të këtyre fqinjëve dhe i përdor ato si një parashikim për pikën e re të të dhënave”
Nga kjo intuitë mund të themi se, algoritmi kNN është,
Mësimi i bazuar në instancë: Modeli mëson të gjitha instancat e trajnimit dhe më pas përgjithësohet në vlera të reja të të dhënave duke përdorur masën e ngjashmërisë (distanca Euklidiane) për t'i krahasuar ato me shembujt e mësuar. Në këtë blog do të mësojmë se si ndodh kjo.
Të mësuarit dembel: Modelja nuk do të bëjë asgjë në fazën e trajnimit. Ai thjesht memorizon të dhënat e trajnimit. Vetëm gjatë kohës së parashikimit modeli kërkon fqinjët më të afërt nga i gjithë grupi i trajnimit, duke e bërë atë të shtrenjtë.
Jo-parametrik: Do të thotë, që nuk bën ndonjë supozim për të dhënat themelore (Për shembull regresioni linear supozon se të dhënat janë shpërndarë në mënyrë lineare).
kNN për Klasifikimin
Për problemet e klasifikimit, kur duam të parashikojmë klasën e një pike të dhënash, algoritmi kërkon pikat k që janë më afër pikës së të dhënave dhe kthen etiketën e klasës në bazë të votimit të shumicës, d.m.th. etiketa më e përdorur e klasës së tyre do të bëhet etiketa e parashikuar.
Shikoni më poshtë, morëm 7 fqinjët më të afërt (k=7) që i përkasin klasës A dhe klasës B. Shumica e fqinjëve i përkasin klasës B. Prandaj klasa e pikës së të dhënave do të etiketohet si Klasa B.
kNN për regresion
Problemet e regresionit përdorin një koncept të ngjashëm si problemi i klasifikimit, algoritmi kërkon pikat k më të afërta me pikën e të dhënave dhe kthen mesataren e vlerave të tyre si vlerë të parashikuar. Dallimi kryesor këtu është se klasifikimi përdoret për vlera diskrete, ndërsa regresioni përdoret me vlera të vazhdueshme.
Përshkrimi matematikor kNN
Tani, ne dimë të parashikojmë etiketën e klasës së pikës së caktuar të pyetjes që na nevojitet për të identifikuar fqinjët e saj më të afërt. Por, si ta bëjmë këtë? Ju mund ta keni marrë me mend tashmë, ne llogarisim distancën. Ka pak metrikë të distancës që mund t'i përdorim për të llogaritur distancën midis pikës së pyetjes dhe pikave të tjera të të dhënave. Këto metrikë të distancës ndihmojnë në formimin e kufijve të vendimeve, duke ndarë pikat e të dhënave në bazë të etiketave të tyre të klasës.
- Distanca Euklidiane: Kjo është matja e distancës më e përdorur dhe është e kufizuar në vektorë me vlerë reale. Duke përdorur formulën e mëposhtme, ai mat një vijë të drejtë midis pikës së pyetjes dhe pikës tjetër që matet.
Distanca Euklidiane i referohet distancës midis dy pikave. Këto pika mund të jenë në hapësirë të ndryshme dimensionale dhe përfaqësohen nga forma të ndryshme të koordinatave.
Këtu po llogarisim distancën euklidiane midis dy pikave (X21,Y21) dhe (X22,Y22), ju merrni rrënjën katrore të shumës së katrorëve të dy vektorëve të diferencës (Y22-Y21) dhe (X22-X21). Distanca Euklidiane nuk është gjë tjetër veçse gjatësia e vektorit dhe referohet si NormaoseNorma Euklidiane.
- Distanca e Manhatanit: Kjo është një tjetër metrikë e njohur e distancës, e cila mat vlerën absolute midis dy pikave. Formula është,
- Distanca e Minkowskit: Kjo matje e distancës është forma e përgjithësuar e metrikës së distancës Euklidiane dhe Manhatanit. Parametri, p, në formulën e mëposhtme, lejon krijimin e metrikave të tjera të distancës. Distanca Euklidiane përfaqësohet me këtë formulë kur p është e barabartë me dy, dhe distanca e Manhatanit shënohet me p e barabartë me një.
- p=1: Distanca e Manhatanit (l1 normë)
- p=2: Distanca Euklidiane (l2 normë)
Distanca e Hamingut: Kjo teknikë përdoret zakonisht me vektorët Boolean ose vargje (ndryshoret kategorike), duke identifikuar pikat ku vektorët nuk përputhen. Si rezultat, ajo është referuar edhe si metrikë e mbivendosjes. Kjo mund të përfaqësohet me formulën e mëposhtme,
Zgjedhja e vlerës optimale të k
Nuk ka një mënyrë specifike për të përcaktuar vlerën më të mirë k. Ju duhet të eksperimentoni me disa vlera të kpara se të vendosni se me cilën të shkoni përpara. Le të shohim se çfarë mënyrash kemi për të zgjedhur vlerën optimale të k.
- Një nga mënyrat e zakonshme është zgjedhja e vlerës së k duke llogaritur rrënjën katrore të N mostrave në grupin e të dhënave të trajnimit.
- Një mënyrë tjetër është, duke marrë parasysh se një pjesë e mostrave të trajnimit është “e panjohur”. Më pas, ne mund t'i kategorizojmë të dhënat e panjohura në grupin e testit duke përdorur algoritmin kNN dhe të analizojmë se sa i mirë është kategorizimi i ri duke e krahasuar atë me informacionin që kemi tashmë në të dhënat e trajnimit.
- Kur keni të bëni me një problem të klasës binare, përpiquni të zgjidhni një vlerë tek për k. Çfarë do të bëni nëse numri i fqinjëve në secilën klasë është i njëjtë (50–50)? Do të jetë e vështirë të parashikohet etiketa e klasës për pikën tonë të të dhënave. Pra, zgjidhni k si numër çift në raste të tilla.
- kme vlera më të ulëta (k=1 ose k=2), mund të jetë i zhurmshëm dhe i nënshtrohet efekteve të ekstrave. Mundësia për mbivendosje është gjithashtu e lartë në raste të tilla.
- Ndërsa kme vlerë më të madhe, çon në kufij më të qetë të vendimeve, por k nuk duhet të jetë shumë i madh. Përndryshe, grupet me më pak pika të dhënash do të mbivotohen gjithmonë nga grupet e tjera. Për më tepër, kmë e madhe do të jetë llogaritëse e shtrenjtë.
Standardizimi
Një pengesë kryesore në llogaritjen e masave të distancës drejtpërdrejt nga grupi i trajnimit është në rastin kur variablat kanë shkallë të ndryshme matjeje ose ka një përzierje të variablave numerike dhe kategorike. Për shembull, nëse një variabël bazohet në të ardhurat vjetore në dollarë, dhe tjetra bazohet në moshën në vite, atëherë të ardhurat do të kenë një ndikim shumë më të madh në distancën e llogaritur. Një zgjidhje është standardizimi i grupit të trajnimit siç tregohet më poshtë.
Avantazhet dhe disavantazhet e kNN
Përparësitë
- E lehtë për t'u zbatuar: Duke pasur parasysh thjeshtësinë dhe saktësinë e algoritmit, ky është një model i shkëlqyeshëm për shumë raste të përdorimit të mësimit të makinerive që nuk kërkojnë teknika shumë komplekse.
- Përshtatet lehtë: Ndërsa shtohen mostra të reja trajnimi, algoritmi përshtatet për të llogaritur çdo të dhënë të re pasi të gjitha të dhënat e trajnimit ruhen në memorie.
- Pak hiperparametra: KNN kërkon vetëm një vlerëk dhe një metrikë të distancës, prandaj zhvillohet shumë shpejt.
Disavantazhet
- Nuk shkallëzohet mirë: Meqenëse KNN është një algoritëm dembel, ai merr më shumë memorie dhe ruajtje të të dhënave në krahasim me klasifikuesit e tjerë. Kjo mund të jetë e kushtueshme si nga këndvështrimi i kohës ashtu edhe i parasë. Më shumë memorie dhe ruajtje do të rrisin shpenzimet e biznesit dhe më shumë të dhëna mund të kërkojnë më shumë kohë për t'u llogaritur.
- Mallkimi i dimensionalitetit: Algoritmi KNN tenton të bjerë viktimë e mallkimit të dimensionalitetit, që do të thotë se nuk funksionon mirë me hyrjet e të dhënave me dimensione të larta. Kjo nganjëherë quhet edhe "fenomeni i kulmit", ku pasi algoritmi arrin numrin optimal të veçorive, veçoritë shtesë rrisin sasinë e gabimeve të klasifikimit, veçanërisht kur madhësia e kampionit është më e vogël.
- Të prirur ndaj përshtatjes së tepërt: Për shkak të "mallkimit të dimensionalitetit", KNN është gjithashtu më i prirur ndaj përshtatjes së tepërt. Ndërsa teknikat e përzgjedhjes së veçorive dhe të reduktimit të dimensioneve përdoren për të parandaluar që kjo të ndodhë, vlera e k mund të ndikojë gjithashtu në sjelljen e modelit. Vlerat më të ulëta të k mund t'i përshtaten të dhënave, ndërsa vlerat më të larta të k priren të "zbutin" vlerat e parashikimit pasi mesatarizon vlerat në një zonë ose lagje më të madhe. Megjithatë, nëse vlera e k është shumë e lartë, atëherë mund të mos i përshtatet të dhënave.
- Rënia e performancës: kNN ka më pak gjasa të performojë mirë në detyra të avancuara si "Vizioni kompjuterik" dhe "Përpunimi i gjuhës natyrore NLP". Mund të përpiqeni të shtyni performancën e kNN duke shtuar teknika të tjera si bagging, për të përmirësuar performancat parashikuese. Në një pikë të caktuar kompleksiteti, kNN ndoshta do të jetë më pak efektiv se modelet e tjera, pavarësisht nga mënyra se si është akorduar.
Zbatimi me python
- Hapi i parë është importimi i bibliotekave të nevojshme të python dhe leximi i të dhënave.
#importing necessary libraries
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, confusion_matrix
#read dataset
df = pd.read_csv("../dataset.csv")
#size
df.shape
output: (400, 5)
df.head()
Të dhënat tona kanë 400 mostra, 5 veçori
2. Tani le të ndajmë variablat tona të parashikuesit (veçoritë hyrëse X) dhe të përgjigjes (objektivi y). Si parashikues X morëm kolonat nga Gjinia, Mosha, Vlerësuesi dhe si përgjigje y morëm kolonën Blerë.
X = df.iloc[:,2:-1].values y = df.iloc[:,-1].values
Tani, me këtë kod X dhe y do të jenë dy vargje. Pse morëm vargje? Në përshkrimin matematikor të mësipërm, mund të vëreni se pikat tona të të dhënave janë në fakt dy vektorë. Pastaj llogaritet distanca midis pikave të të dhënave.
3. Tani, ne duhet t'i ndajmë të dhënat në grupe treni dhe testimi. Kompleti i trenit ka 80% mostra = 320 ; grupi i testimit ka 20% mostër = 80
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=43) X_train.shape #output: (320, 2) y_train.shape #output: (320,) X_test.shape #output: (80, 2) y_test.shape #output: (80,)
Parapërpunimi i të dhënave - Shkallëzimi i veçorive
4. Vlerat ndryshojnë shumë, veçanërisht vlerat e parashikuara të kolonës së pagave janë vërtet të larta. Distanca Euklidiane do të ndryshojë shumë. Kjo do të ndikojë në performancën duke u dhënë peshë më të madhe këtyre variablave pasi norma (madhësia) e tyre do të jetë më e lartë. Duhet të kryejmë shkallëzimin e veçorive.
Le të shkallëzojmë vlerat duke përdorur StandardScaler() nga bibliotekascikit-learn.
trf = StandardScaler() X_train_trf = trf.fit_transform(X_train) X_test_trf = trf.transform(X_test)
Gjetja e k Fqinjëve më të afërt
5. Le të trajnojmë klasifikuesin kNN dhe të kontrollojmë rezultatin e saktësisë së modelit. Para se të vazhdojmë, duhet të kemi një ide për hiperparametrin n_fqinjët. n_fqinjët është vlera e k, numri i fqinjëve. Ne duhet të vendosim se sa fqinjë më të afërt duam të krahasojmë me vlerën e re të të dhënave.
knn = KNeighborsClassifier(n_neighbors=20) knn.fit(X_train_trf, y_train) y_pred = knn.predict(X_test_trf) print(“Accuracy: “, accuracy_score(y_test, y_pred)) print(confusion_matrix(y_test, y_pred))
Këtu, mora vetëm 20 fqinjë dhe kontrollova saktësinë e modelit tim dhe mora 0.83 (83%), jo keq. Por kjo nuk do të ndodhë në grupe të dhënash më të mëdha, rezultati i saktësisë mund të bjerë vërtet i ulët. "Matrica e konfuzionit" do të na tregojë sa të drejta dhe parashikime bëri modeli ynë. (43 dhe 24 janë parashikime të sakta për 2 klasat. 7 dhe 6 janë parashikime të gabuara për 2 klasa)
Unë mora k = 20, por a e dini se nuk është ideale të merret vlera e k-së si çift, sepse ka shanse për të marrë një barazim gjatë votimit. Po sikur 10 fqinjë i përkasin një klase dhe 10 të tjerë i përkasin klasës tjetër?
Por ne mund ta përmirësojmë këtë rezultat duke zgjedhur vlerën e duhur k. Le të shohim se si ta bëjmë atë.
error_train=[]
error_test=[]
for i in range(1,26):
knn=KNeighborsClassifier(n_neighbors=i)
knn.fit(X_train_trf,y_train)
x=confusion_matrix(y_train,knn.predict(X_train_trf))
y=confusion_matrix(y_test,knn.predict(X_test_trf))
error_train.append((x[0][1]+x[1][0])/x.sum())
error_test.append((y[0][1]+y[1][0])/y.sum())
# plot
plt.plot(range(1,26),error_train,label='training error rate')
plt.plot(range(1,26),error_test,label='test/validation error rate')
plt.xlabel('K Value')
plt.ylabel('Error')
plt.legend()
Këtu kemi gjetur shkallën e gabimit që do të marrim në tren dhe vendosim test për vlera të ndryshme të k. Gjatë vizatimit të prodhimit që morëm,
Duket sikur saktësia ne është e lartë afër k =11
Parashikim
6. Tani për parashikimin tonë përfundimtar, le të përditësojmë vlerën n_neighbors (k=13) në modelin tonë dhe të kontrollojmë edhe një herë pikën e saktësisë dhe matricën e konfuzionit.
knn = KNeighborsClassifier(n_neighbors=11) knn.fit(X_train_trf, y_train) y_pred = knn.predict(X_test_trf) print(“Accuracy: “, accuracy_score(y_test, y_pred)) print(confusion_matrix(y_test, y_pred))
Ja ku shkoni! Ne mund të rrisim rezultatin e saktësisë me 0,02 (2% rritje). Dhe parashikimet e sakta të modelit tonë janë rritur gjithashtu.
konkluzioni
Kjo ishte një qasje bazë për modelin kNN. Duhen disa hapa për të kaluar nga një model bazë kNN në një model plotësisht të akorduar, por rritja e performancës ia vlen plotësisht.
Në këtë tutorial kemi mësuar:
- Kuptoni intuitën dhe themelet matematikore pas algoritmit kNN
- Përdoret scikit-learn për parapërpunimin e të dhënave dhe për të përshtatur kNN.
