K auzokide hurbilenak: berrikuspenen arteko aldeak

{{ikasketa automatikoa}}'''k auzokide hurbilenen''' metodoa ({{lang-en|k-nearest neighbors}} edo '''K-NN''') [[Datudatu-meatzaritza|datu-meatzaritzan]]n eta ikasketa automatikoan sailkapen gainbegiratua egiteko metodo bat da. Entrenamendurako kasuen artean, k auzokide hurbilenetan oinarritzen da kasu berrien sailkapena egiteko. Hurbileneko k auzokideen klase-aldagaiaren balioa aztertu eta sarrien agertzen den klasea esleitzen zaio kasu berriari.

k-NN algoritmoak ikasketa nagia edo alferra (''lazy learning'') egiten duela esaten da, ez duelako eredu bat induzitzen ikasketa-fasean; entrenamendurako datu-basetik eredu bat sortu beharrean, datu-base berarekin egiten da kasu berriaren klase-aldagaiaren iragarpena test-fasean.

Gainbegiratutako sailkapenerako algoritmo bat da k-NN<ref>(ingelesez) Dasarathy, Belur V. {{Erreferentzia|izenburua=Nearest neighbor (NN) norms : nn pattern classification techniques|argitaletxea=IEEE Computer Society Press|data=1991|url=https://www.worldcat.org/oclc/22272787|isbn=0-8186-8930-7|pmc=22272787|sartze-data=2019-12-23}}</ref>. Abiapuntua <math>N</math> kasuz osatutako [[datu-base]] bat da, <math>\{(x_1, y_1), ..., (x_N,\; y_N)\}</math> modukoa, non <math>x_i</math> bektoreak <math>i.</math> kasua deskribatzen duen eta <math>y_i</math> den <math>C</math> klase-aldagairako haren etiketa edo balioa. Kasuei erreferentzia egiteko, ''adibide'' edo ''prototipo'' hitzak ere erabiltzen dira. Datu-basetik abiatuz, gainbegiratutako sailkapenerako algoritmoek normalean eredu bat induzitzen badute ere, k-NN algoritmoa berezia da, ez baitu halakorik egiten; horregatik esaten da ikasketa nagia edo alferra egiten duela, ez duelako berezko entrenamendu- edo ikasketa-faserik.

Hortaz, <math>x=(x_{1},x_{2},\dots,x_{n})</math> bektoreak deskribatutako kasu berri bat k-NN algoritmoaren bidez sailkatzeko, haren eta datu-baseko <math>x_i=(x_{i1},x_{i2},\dots,x_{in})\,</math> kasu guztien arteko distantziak kalkulatu behar dira, <math>i = 1, \ldots, N</math>.

Kasuaren deskribapena bi aldagai iragarlez ematen denean, <math>x_1=(x_{11},x_{12})\,</math> eta <math>x_2=(x_{21},x_{22})\,</math> bi puntuan planoan adieraz daitezke, eta distantzia euklidearraren kalkulua horrela geratzen da:

emateko.

Distantziaren definizio hori [[Pitagoras|Pitagorasek]]ek emandako [[Pitagorasen teorema|teorematik]] eta gerora [[Euklides|Euklidesek]]ek egindako [[Euklidesen Elementuak|formalizazio lanetik]] eratorriak dira: [[Geometriageometria euklidear|geometria euklidearra]]ra.

k-NN algoritmo orokorraren arabera, k auzokideen artean sarrien agertzen den klasea esleitzen zaio kasu berriari. Baina sailkatze-problema batzuetan horrek ez du nahikoa berme eskaintzen kasu berriaren iragarpena egiteko. Hori dela eta, atalase bat finka daiteke eta auzokide hurbilenen artean sarrien agertzen den klasea atalaseak adierazitako kopurua adina aldiz agertu beharko da, gutxienez, iragarpena egiteko. Hala ez den kasuetan, kasu berria sailkatu gabe uzten da. Atalaseari k parametroaren balio bera ematen zaionean, hau da, gertuko auzokide guztiak klase berekoak (guztien adostasuna) izatea eskatzen denean, bermearen maila maximoa lortzen da.

k-NN algoritmo orokorraren arabera, k auzokide hurbilenen artean sarrien agertzen den klasea esleitzen zaio kasu berriari, auzokide horien artean inolako bereizketarik egin gabe. Gerta daiteke kasu berritik hurbilen dauden auzokide horien artean sarrien agertzen den klasekoak urrutien daudenak izatea. Irudiko adibidean, k=5 aukeratzen den kasuan argi ikusten da "''triangelu gorri''" klaseko 2 eta "''karratu urdin''" klaseko 3 daudenez 5 auzokide hurbilenen artean, algoritmo orokorrak "''karratu urdin''" klasearen iragarpena egiten duela kasu berriarentzat, nahiz eta "''karratu urdin''" klaseko hiruak "''triangelu gorri''" klasekoak baino urrutiago egon.

* Klaseen ordezkariak erabiltzea. Auzokideak klaseka multzokatu eta klase bakoitzerako ordezkari bat aukeratzen da. Gehienetan klase bakoitzeko barizentrotik (klase bereko kasuen "zentrotik") hurbilen dagoen kasua hautatzen da ordezkari moduan. k-NN algoritmoak distantzia minimora dagoen ordezkariaren klasea esleituko dio kasu berriari.

* Auzokideak haztatzea edo "''Weighted k-NN''"<ref>{{Erreferentzia|izenburua=Weighted K-NN|hizkuntza=en-US|data=2019-06-14|url=https://www.geeksforgeeks.org/weighted-k-nn/|aldizkaria=GeeksforGeeks|sartze-data=2019-12-26}}</ref><ref>{{Erreferentzia|izenburua=Weighted k-nearest neighbors - Nearest Neighbors & Kernel Regression|hizkuntza=en|url=https://www.coursera.org/lecture/ml-regression/weighted-k-nearest-neighbors-778Pn|aldizkaria=Coursera|sartze-data=2019-12-26}}</ref>. <math>x_i=(x_{i1},x_{i2},\dots,x_{in})\,</math>auzokideak distantziaren arabera haztatu egiten dira, <math>i = 1, \ldots, k</math>. Haztapenak garrantzia maila desberdina ematen die kasuei, <math>x=(x_{1},x_{2},\dots,x_{n})</math> kasu berritik gertuen daudenek haztapen altuagoa jasoko dutelarik. Distantziaren araberako <math>w_i</math> haztapena modu desberdinean defini daiteke:

Sailkapen-problemetan, prototipoak <math>n</math> osagaiko <math>x=(x_{1},x_{2},\dots,x_{n})</math> bektoreen bidez deskribatzen dira. Osagai horietako bakoitza ezaugarri bati buruzko informazioa ematen duen <math>X</math> aldagai iragarle baten balioa da. <math>n</math> aldagai iragarle horiek ematen duten informazioa ez da garrantzia maila berekoa izaten, <math>C</math> klase-aldagaiaren iragarpenean.

Adibide bat jartzearren, datu-baseko kasuak osasun-zentro bateko pazienteak badira, <math>x=(x_{1},x_{2},\dots,x_{n})</math> bektoreek pazienteei buruzko informazioa emango dute: adina, egindako probaren baten emaitza, etab. Medikuak gaixotasunei buruz duen ezagutza erabiltzen du <math>x</math> pazientearen sintomak aztertuz diagnostikoa egiteko; <math>C</math> klase-aldagaia da diagnostikoa gordetzen duena. Antzeko egoeran dauden pazienteen (auzokide hurbilenen) diagnostikoan oinarritzen da k-NN algoritmoa <math>C</math>-ren iragarpena egiteko.

Antzeko egoeran dauden pazienteak aurkitzeko, garrantzitsua gertatzen da aldagai iragarle bakoitzak ematen duen informazioa neurtzea. Izan ere, sintoma batzuk oso erlazionatuta baitaude gaixotasunarekin baina datu-baseko beste datu batzuk ez dira esanguratsuak. Aldagai iragarleak haztatzeko beharra sortzen da, klase-aldagaiaren iragarpenean duten garrantziaren arabera.

Ezaugarri edo aldagai iragarle bakoitzaren garrantzia adierazten duen <math>w_j</math> haztapena kalkulatu behar da. Kalkulatzeko modu bat <math>X</math> aldagai iragarlearen eta <math>C</math> klase-aldagaiaren [[Elkarrekikoelkarrekiko informazio|elkarrekiko informazioaren]]aren neurria erabiltzea da:

k-NN algoritmoan oinarritutako bi metodo daude: Hart-en kondentsazioa eta Wilson-en edizioa.

Kasu honetan, Hart-en kondentsazioaren metodoan ez bezala, gertueneko direnen klaseak desberdinak direnean ezabatzen dira kasuak datu-basetik. Horrela lortu nahi da klaseak haien artean ondo bereiztea, hain zuzen ere klaseen arteko mugetan dauden kasuak ezabatuz.

* (ingelesez) "[https://towardsdatascience.com/a-simple-introduction-to-k-nearest-neighbors-algorithm-b3519ed98e A Simple Introduction to K-Nearest Neighbors Algorithm]"

* (ingelesez) "[https://towardsdatascience.com/model-selection-tuning-and-evaluation-in-k-nearest-neighbors-6d3024d78745 Model Selection, Tuning and Evaluation in K-Nearest Neighbors]"

* (ingelesez) "[https://www.analyticsvidhya.com/blog/2018/03/introduction-k-neighbours-algorithm-clustering/ Introduction to k-Nearest Neighbors: A powerful Machine Learning Algorithm (with implementation in Python & R)]"