«K auzokide hurbilenak»: berrikuspenen arteko aldeak

t
Robota: Aldaketa kosmetikoak
t (Robota: Aldaketa kosmetikoak)
 
{{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.
 
Metodoa sinplea eta intuitiboa da; [[Distantzia|distantzien]] kalkuluan oinarritzen da. Algoritmoaren bertsiorik sinpleenean k auzokide hurbilenen klaseei tratamendu bera ematen zaie, baina badira algoritmoaren aldaera desberdinak auzokideen artean bereizketa egiteko, kasu berrira duten distantziaren arabera garrantzia maila desberdina emateko, adibidez<ref>(gazteleraz) Sierra Araujo, B.{{Erreferentzia|izenburua=Aprendizaje automático : conceptos básicos y avanzados : aspectos prácticos utilizando el software WEKA|argitaletxea=Pearson|data=2006|url=https://www.worldcat.org/oclc/629686982|isbn=84-8322-318-X|pmc=629686982|sartze-data=2019-12-23}}</ref>.
[[Fitxategi:KnnClassification.svg|thumb|206x206px|Adibidea. 11 kasu dituen entrenamendurako datu-basea. k-ren balioaren arabera, k-NN algoritmoa 3-NN, 5-NN... izango da.]]
 
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.
 
Sailkatze- edo test-fasean, <math>x</math> bektorearen bidez deskribatutako kasu berri bat iristen denean, datu-baseko <math>x_i</math> kasu guztietara duen distantzia kalkulatu behar da, distantzia euklidearra normalean, ondoren kasuak distantzia txikienetik handienera ordenatu eta erabiltzaileak definitutako k balioaren arabera hurbilen dauden k kasuak aurkitzeko. Auzokide hurbilenak diren k kasu horien <math>y_i</math> klasea begiratu eta sarrien agertzen den klasea esleitzen zaio <math>x</math> kasu berriari. Eredurik erabili gabe, test-fasean kalkulatutako distantzietan oinarritzen da k-NN algoritmoa kasu berriaren klase-aldagaiaren iragarpena egiteko.
<math>d_E(x_1,x_2)=\sqrt{(x_{11}-x_{21})^2 + (x_{12}-x_{22})^2 + \cdots + (x_{1n}-x_{2n})^2} = \sqrt{\sum_{i=1}^n (x_{1i}-x_{2i})^2}.</math>
 
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.
 
<math>d_E(x_1,x_2)=\sqrt{(x_{11}-x_{21})^2 + (x_{12}-x_{22})^2}</math>
 
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 parametroa ==
 
=== Bermerik gabekoak baztertuz ===
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.
 
Adibidez, izan bedi bi klase ezberdinetan banatutako 100 kasuz osatutako entrenamendurako datu-base bat eta k=5 parametroa. Erabiltzaileak atalase desberdinak finka ditzake, lortu nahi duen bermearen arabera: atalasea 4 balioan finkatzen badu, 5 auzokide hurbilenen artetik gutxienez 4 klase berekoak badira egingo du klasearen iragarpena 5-NN algoritmoak. Atalasea 3 balioan finkatzen badu, lortu beharreko bermearen maila jaitsiko du, nahikoa izango baita 5etik 3 klase berekoak izatea iragarpena egiteko. Bermerik altuena atalasea 5 balioarekin finkatuz lortuko du: auzokide guztien adostasuna.
 
=== Auzokide hurbilenen arteko bereizketa ===
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.
 
k auzokide hurbilenak distantziaren arabera bereizi nahi badira, estrategia desberdinak erabil daitezke:
* Batez besteko distantzia erabiltzea. Auzokideak klaseka multzokatu eta batez bestean kasu berrira zein distantziara dauden kalkulatzen da. k-NN algoritmoak batez bestean distantzia txikienera dagoen klasea esleituko dio kasu berriari.
* 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:
 
<math>w_i=\frac{1}{d_E(x_i,x)}, \quad \quad w_i = \frac{1}{d_E(x_i,x)^2}</math>
 
=== Aldagai iragarleak haztatzea ===
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:
 
<math>\begin{align}
k-NN algoritmoa sailkapen gainbegiraturako metodo bat izateaz gain, aurre-prozesaketa fasean datu-baseko prototipo kopurua murrizteko erabil daiteke. Izan ere, ikasketa automatikorako erabili ohi diren datu-baseak oso handiak izaten dira, horrek dakarren konputazio-kostua altua izanik. Datu-basea arindu nahi izaten da, soberan egon litezkeen kasuak ezabatuz. Noski, ez dira datu-basetik ezabatu nahi klaseen definizioan garrantzitsuak diren kasuak. Horrela, datu-basetik zein prototipo ezabatuko diren erabaki behar da.
 
k-NN algoritmoan oinarritutako bi metodo daude: Hart-en kondentsazioa eta Wilson-en edizioa.
 
=== Hart-en kondentsazioa ===
# Esleitutako klasea eta klase erreala bat ez datozen kasu guztiak datu-basetik ezabatu.
 
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.
 
== Erreferentziak ==
 
== Kanpo estekak ==
* (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)]"