«K auzokide hurbilenak»: berrikuspenen arteko aldeak

Orrazketa eta osatu
No edit summary
(Orrazketa eta osatu)
= k auzokide hurbilenak (k-NN) =
'''K auzokide hurbilenen''' metodoa ({{lang-en|k-nearest neighbors}} edo '''K-NN''') [[Datu-meatzaritza|datu-meatzaritzan]] sailkapen gainbegiraturako 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 auzokide hurbilenen''' metodoa ({{lang-en|k-nearest neighbors}} edo '''K-NN''') [[Datu-meatzaritza|datu-meatzaritzan]] 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.
 
Kk-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 Kk 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>.
 
== Algoritmoa ==
[[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.]]
[[Fitxategi:KnnClassification.svg|thumb|206x206px|K-NN algoritmoaren adibidea. Sailkatu nahi den elementua zirkunferentzia berdea da. K=3 den kasurako zirkunferentzia ''triangelu'' klase bezala sailkatzen da. Karratu bakarra eta bi triangelu daudelako zirkuluan. K=5 den kasurako zirkunferentzia ''karratu'' klase bezala sailkatzen da. Bi triangelu eta hiru karratu daudelako kanpoko zirkuluan.]]
Entrenamendu fasean, [[Datu-base|datubasean]] ukango ditugun kasu guztiak gordeko ditugu, haien aldagai iragarle eta klasearekin.
 
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 fasean, erabiltzaileak K konstantea definitzen du eta sailkatu nahi duen kasu berria aurkezten du. Helburua kasu berri hori klase bat esleitzea denez, hurbilen dauden K elementuen artean gehien agertzen den klasea esleituko diogu, ondoko adibidean ikusten den bezala.
 
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.
Bi elementuen artean “berdinketa” dagoen kasuan, klase bat eukeratzeko aterabide ezberdinak daude, besteak beste, hurbilenaren klasea esleitzea, edo bataz besteko distantzia txikiena duen klasea aukeratzea.
 
Irudian k-NN algoritmoaren adibide bat ikus daiteke. Datu-base horretan <math>N=11</math> kasu daude: horietako 6 "''karratu urdin''" klasekoak dira eta gainerako 5ak "''triangelu gorri''" klasekoak. Kasuak planoan adierazita daude, hau da, kasu bakoitza adierazten duen <math>x_i</math> bektoreak bi osagai ditu. Zirkunferentzia berde batez adierazita dator sailkatu behar den kasu berria, <math>x</math> bektorearen bidez deskribatuta datorrena. Hura "''karratu urdin''" klasekoa edo "''triangelu gorri''" klasekoa den erabakitzeko, datu-baseko 11 kasuetarako distantzia kalkulatu behar da. Irudiko zirkunferentziaren erradioak distantzia hori erakusten du. Erabiltzaileak k=3 balioa aukeratzen badu, 3-NN algoritmoak 3 auzokide hurbilenen klaseak erabiliko ditu iragarpena egiteko; "''karratu urdin''" klaseko bakarra eta "''triangelu gorri''" klaseko bi daudenez, sarrien agertzen den klasea esleituko dio kasu berriari: "''triangelu gorri''" klasea. k=5 balioa aukeratzen badu, "''triangelu gorri''" klaseko 2 eta "''karratu urdin''" klaseko 3 daudenez 5 auzokide hurbilenak biltzen dituen kanpoko zirkuluan, "''karratu urdin''" klasea esleituko zaio kasu berriari.
Gehienetan erabiltzen den distantzia, [[distantzia euklidearra]] da.
 
k-NN algoritmoa erabiltzean, batzuetan "berdinketa" kasuak gertatzen dira: datu-baseko hainbat kasu distantzia berera egotea kasu berritik, hurbileneko auzokideen artean sarrien agertzen diren klaseetan kasu kopuru bera egotea, etab. Halakoak ebazteko estrategia desberdinak proposatu izan dira. Oinarrizko k-NN algoritmoaren aldaerak lortzen dira horrela.
== K aukeratu ==
K-ri baliorik egokiena esleitzea funtsean datuen mendean dago; gehienetan, k-ren balio handiek zarata txikiagotzen dute, baina antzeko klaseen arteko limiteak sortzen dituzte. K on bat erabilera optimizatuz aukera daiteke. Orokorrean, 3 eta 7 balioen artean aukeratzea gomendatzen da. Klasea entrenamenduaren adibidearen klaserik hurbilena izateko iragartzen den kasu berezia (k=1 denean) Nearest Neighbor Algorithm deitzen da, auzokide  gertuenaren Algoritmoa.
 
=== AlgoritmoarenDistantzia aldaerakeuklidearra ===
k-NN algoritmoak prototipoen edo kasuen arteko distantziak kalkulatu behar ditu. Normalean distantzia euklidearra erabiltzen da. ''n''-dimentsioko espazio euklidear batean, <math>x_1=(x_{11},x_{12},\dots,x_{1n})\,</math> eta <math>x_2=(x_{21},x_{22},\dots,x_{2n})\,</math> bi punturen arteko distantzia euklidearra horrela definitzen da:
Oinarrizko algoritmoari aldaera batzuk egiten ahal zaizkio. Horrela batzuetan emaitza hobeak lor daitezke, datu-base batzuetan kasu batzuek ez daukatelako berme asko, edo distantzia kalkulatzeko modu ezberdinak erabiltzen ahal direlako, adibidez.
 
<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>
=== K-NN bermegabeak baztertuz ===
Aurretik hautatutako atalase baten bidez sailkatu nahi diren kasuek berme nahiko duten aukeratzen da, eta haien artean gehiengo absolutuaren bidez kasu berria sailkatzen da.
 
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>.
Adibidez, entrenamendu datu-basean 2 klase ezberdinetan banatutako 10 kasu baldin badaude, atalasea 6koa jartzen da. Hori dela eta, kasu berri batek gutxienez sei bozka izan beharko ditu sailkatu ahal izateko.
 
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:
=== K-NN aukeratutako auzokideen pisaketarekin ===
K-NN algoritmoaren aldaera honetan, kasu guztien arteko distantzia Euklidearrak kalkulatzen da.
 
emateko.
<math>d=\sqrt{(x_b-x_a)^2+(y_b-y_a)^2}</math>
 
<math>d_E(x_1,x_2)=\sqrt{(x_{11}-x_{21})^2 + (x_{12}-x_{22})^2}</math>
non <math>x_a</math> eta <math>y_a</math> A kasuaren X eta Y parametroaren balioa den <math>x_b</math> eta <math>y_b</math>B kasuarenak.
 
Distantziaren definizio hori [[Pitagoras|Pitagorasek]] emandako [[Pitagorasen teorema|teorematik]] eta gerora [[Euklides|Euklidesek]] egindako [[Euklidesen Elementuak|formalizazio lanetik]] eratorriak dira: [[Geometria euklidear|geometria euklidearra]].
Kasu berri bat sartzen denean, klase bat esleitzeko, K elementu hurbilena hartzen da eta haien klasearen arabera banatzen da. Ondoren, kasu bakoitzaren d distantziak kalkulatzen dira. <math>1/d</math> eginez klase bakoitzeko kasuen pisuak kalkulatu ondoren, kasu berriari pisuen batura handiena duen klasea esleituko zaio.
 
== k parametroa ==
=== K-NN batazbesteko distantziarekin ===
k-NN algoritmoa erabiltzeko, k parametroaren balioa finkatu behar da. Oro har, ez dago k-ren baliorik egokiena aukeratzeko metodorik eta ez da egia zenbat eta balio altuagoa aukeratu orduan eta sailkapen hobea lortuko denik. Datu-basearen arabera, k-ren balio desberdinetarako algoritmoaren eraginkortasuna aldatu egiten dela ikusi da. Gehienetan, k-ren balio handiek sailkapenaren zarata txikiagotzen dute, baina klaseen arteko mugak ez dira hain argiak izaten. Hori dela eta, modu esperimentalean aukeratu behar izaten da k-ren balioa. Normalean, 3 eta 7 arteko balio bakoitiak aukeratzea gomendatzen da. k=1 aukeratzen denean, algoritmoak "auzokide hurbilenaren algoritmo" izena hartzen du.
Kasu berritik K elementu hurbilenak kontutan hartuz, klase berdineko elementuen eta kasu berriaren arteko distantzien arteko bataz bestekoak kalkulatzen dira, klase bakoitzeko. Ondoren, bataz besteko distantzia euklidear txikiena duen klasea esleituko zaio kasu berriari.
 
== Algoritmoaren aldaerak ==
=== K-NN distantzia minimoarekin ===
Algoritmoaren oinarrizko ideiatik abiatuz, posible da k-NN algoritmoaren aldaera desberdinak sortzea. Arrazoi desberdinak egon daitezke algoritmoaren hainbat xehetasun aldatuz aldaera desberdinak sortzeko. Atal honetan aldaera horietako batzuk azaltzen dira.
Klase bakoitzari ordezkari bat esleitzen zaio eta kasu berrien sailkapena klaseen ordezkariekin 1-NN egitea izango litzateke, hau da, kasu berriari hurbilen duen ordezkariaren klasea esleituko zaio. Ordezkaria aukeratzeko, gehienetan [[barizentro]]tik (klase berdineko elementu guztien "zentroa") hurbilen dagoen kasua hautatzen da.
 
=== NNBermerik aldagaiengabekoak pisaketarekinbaztertuz ===
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.
Sailkatu beharreko x kasu berriaren eta sailkatutako kasuen arteko distantzia kalkulatzerakoan aldagaiei ez zaie pisu berdina emango. Aldagai bakoitzari dagokion garrantzia eman behar zaio. Honela kalkulatzen da <math>x_{1}</math> kasu berriaren eta <math>x_{2}</math> kasuaren arteko distantzia ponderatua:
 
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.
<math>x_{1}=(x_{a}, x_{b})
 
=== Auzokide hurbilenen arteko bereizketa ===
</math> <math>x_{2}=(x_{a}, x_{b})
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.
</math>
 
k auzokide hurbilenak distantziaren arabera bereizi nahi badira, estrategia desberdinak erabil daitezke:
<math>d(x_1,x_2)=\sqrt{w_1(x_{1}^a-x_{2}^a)^a + w_2(x_{1}^b-x_{2}^b)^2}</math>
* 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>
<math>w_1
 
</math>eta <math>w_2
Auzokide hurbilenak klaseka elkartu eta haien haztapenen batura egiten da. Batura handieneko klasea esleitzen zaio kasu berriari.
</math> pisuak aurretik daude finkaturik. Pisua kalkulatzeko modu bat <math>X_i</math> aldagaiaren eta <math>C</math> klase-aldagaiaren [[Elkarrekiko informazio|elkarrekiko informazioaren]] neurria erabiltzea da, <math>i = 1 . . . , n</math>. Neurria honela definitzen da:
 
=== 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 [[Elkarrekiko informazio|elkarrekiko informazioaren]] neurria erabiltzea da:
 
<math>\begin{align}
\operatorname{I}(XiX,C) & {} = \sum_{xi,ci=1}^n p_\sum_{(Xi,C)j=1}^m p(xix_i,cc_j) \log_2 \frac{p_{p(Xix_i,C)}(xi,cc_j)}{p{Xi}(xix_i)p_{C}p(cc_j)}\\
\end{align},
</math>
 
<math>n</math> izanik <math>X</math> aldagaiaren balio posibleak eta <math>m</math> izanik <math>C</math>-ren etiketa posible guztiak.
== Hasierako datu-baseko datu kopuruaren murriztea ==
Hasierako datu-baseko datu kopurua murrizteko bi metodo nagusi daude: Edizioa eta kondentsazioa. Edizio bat egitean, hasierako kasu guztietatik abiatuz batzuk kentzen zaizkio eta kondentsazio bat egitean aldiz, datu-base huts batetik abiatuz beharrezkoak diren kasuak sartzen zaizkio.
 
Distantzia euklidear haztatuaren kalkulua bi aldagai iragarleren kasurako horrela geratzen da:
=== Harten kondentsazioa ===
X entrenamenduko datu-basea izanik eta U sortuko den datu-base berria (hasieran entrenamenduko datu-baseko lehen elementua sartuko da, hutsa egon ez dadin),  iterazio bakoitzean, Xko elementuak korritu eta x elementu bat bilatu, non bere U-ko elementu hurbilenak klase ezberdin bat duen. x Xtik kendu eta U-ra gehitu eta errepikatu U ez aldatu arte.
 
<math>d_E(x,x_i)=\sqrt{w_1(x_1-x_{i1})^2 + w_2(x_2-x_{i2})^2},</math>
Azpiko irudietan Harten kondentsazioaren emaitzak ikus daitezke. 1.irudian, hasierako datu-basea ikus daiteke, non elementu bakoitzaren koloreak bere klasea adierazten duen. Bigarren irudian, 1.irudiko kasuek 1-NN sailkatzailearekin daukaten predikzioak agertzen dira. 3.irudian, sailkapen berdina egiten da, 1-NN ordez 5-NN erabilita eta zonalde zuriek sailkatu gabeko kasuak erakusten dituzte (bi klaseen arteko berdinketa egon delako, adibidez). 4.irudian, Harten kondentsazioa egin ondorengo datubase berria agertzen da eta 5.ean, datu-base berri horri aplikatutako 1-NNren emaitzak.
 
<br /><gallery>
<math>x=(x_1,x_2)</math> kasu berria izanik eta <math>x_i=(x_{i1},x_{i2})</math> datu-baseko kasuak, <math>i = 1, \ldots, N</math>.
Fitxategi:Data3classes.png|1.Irudia: Entrenamenduko datu-basea
 
Fitxategi:Map1NN.png|2.Irudia: Entrenamenduko datu-basea 1NN aplikatuta
== Datu-baseko kasu kopurua murriztea ==
Fitxategi:Map5NN.png|3.Irudia: Entrenamenduko datu-basea 5NN aplikatuta
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 ===
Hart-ek 1968. urtean argitaratu zuen "''The condensed nearest neighbor rule''"<ref>{{Erreferentzia|izena=P.|abizena=Hart|izenburua=The condensed nearest neighbor rule (Corresp.)|orrialdeak=515–516|hizkuntza=en|data=1968-05|url=http://ieeexplore.ieee.org/document/1054155/|aldizkaria=IEEE Transactions on Information Theory|alea=3|zenbakia=14|issn=0018-9448|doi=10.1109/TIT.1968.1054155|sartze-data=2019-12-26}}</ref> izenburua duen artikulu zientifikoa. Datu-base bat izanik, prototipo batzuk ezabatuz datu-base murriztua lortzea da helburua, jatorrizko datu-baseko kasuek islatutako klaseen banaketa ahalik eta ondoen mantenduz. Proposatzen den algoritmoak bi zerrenda erabiltzen ditu: STORE zerrenda, datu-basean mantenduko diren prototipoak gordeko dituena eta GRABBAG zerrenda, ezabatuak izateko aukeratutako prototipoak dituena. Kasuak ezabatuz arindu nahi den datu-basea entrenamendurako erabiliko dena denez, prototipo guztien klasea ezaguna da.
 
Honakoak dira algoritmoaren urratsak:
 
# Datu-baseko lehenengo kasua STORE zerrendan sartu.
# Datu-baseko bigarren kasuaren klasearen iragarpena egin k-NN erabiliz STOREko kasuetan oinarrituz. Sailkapena zuzena bada, kasua GRABBAG zerrendan sartu, bestela STOREn sartu.
# Modu berean segi datu-baseko kasu guztiekin.
# Datu-baseko kasu guztiak aztertu ondoren, GRABBAG zerrendakoekin prozedura errepikatu behin eta berriz. Prozesuaren amaiera bi modutara lor daiteke:
#* GRABBAG zerrenda hutsa dago, denak STOREn daude.
#* Iterazioren batean GRABBAG zerrendako kasu guztiak aztertu ondoren, bat bera ere ez da STORE zerrendara pasa; zerrendak egonkortu dira.
# GRABBAG zerrendako kasuak datu-basetik ezabatuko dira.
 
Metodo honen arabera, k-NN algoritmoak egindako iragarpena eta kasuaren klase erreala berdinak badira, prototipoa GRABBAG zerrendan sartzen da ezabatua izateko. Izan ere, gertuko bi auzokideak klase berekoak izanik, biak gorde beharrik ez dagoela interpretatzen da. Hart-en kondentsazioarekin klase desberdinekoak diren eta haien artean gertu dauden prototipoak gordetzen dira, horiek daudelako klaseen arteko mugan. STORE zerrendan hasieran prototipo bakarra dago, datu-baseko lehenengoa, eta iterazioak aurrera doazen moduan kasuak sartuko dira bertan. Horregatik errepikatu behar da prozesua behin eta berriz, k-NN algoritmoak STORE zerrenda desberdinetan bilatuko dituelako auzokide hurbilenak eta horien arabera iragarpenak alda daitezkeelako.
 
1.Irudian hasierako datu-basea osatzen duten 180 kasuak ikusten dira, bi aldagai iragarleren bidez deskribatuta datozenak. Prototipoak hiru klasetakoak dira, "''gorri''", "''urdin''" eta "''berde''", eta klase bakoitzetik 60 daude. 2. eta 3 irudietan hasierako datu-basean klaseak nola banatzen diren ikusten da, iragarpenak 1-NN eta 5-NN erabilita egin dira, datu-base osoaren gainean. 4.irudian Hart-en kondentsazioa egin ondoren geratu den datu-base murriztua ikusten da eta 5.irudian adierazten da datu-base murriztuan nola geratu den klaseen banaketa, 1-NN aplikatuta.<gallery>
Fitxategi:Data3classes.png|1.Irudia: Datu-basea
Fitxategi:Map1NN.png|2.Irudia: Klaseen banaketa (1-NN-rekin)
Fitxategi:Map5NN.png|3.Irudia: Klaseen banaketa (5-NN-rekin)
Fitxategi:ReducedDataSet.png|4.Irudia: Datu-base murriztua
Fitxategi:Map1NNReducedDataSet.png|5.Irudia: DatuKlaseen banaketa datu-base murriztuamurriztuan 1NN aplikatuta(1-NN-rekin)
</gallery>
 
Ikus daiteke 2. eta 5.irudien artean ez dagoela ezberdintasun handirik. Hortaz, datu-basea kasuz arintzea lortu da, beti ere klaseen arteko banaketa oso antzekoa mantenduz. Horri esker, gainbegiratutako sailkapeneko test-fasea azkarragoa izango da, datu-basea arindu denez distantzia kopuru txikiagoa kalkulatu beharko delako; asmatze-tasa antzera mantenduko da.
 
=== Wilson-en edizioa ===
Ikus daiteke 2. eta 5.irudien artean ez dagoela ezberdintasun handirik, eta horri esker elementu berri bat sartzerakoan, bere klasea zein den azkarrago erabakitzen ahalko da, asmatze tasa asko apaldu gabe.
Metodo honek Hart-en kondentsazioaren metodoaren helburu bera du: datu-base bat izanik, prototipo batzuk ezabatuz datu-base murriztua lortzea, jatorrizko datu-baseko kasuek islatutako klaseen banaketa ahalik eta ondoen mantenduz. Wilson-ek argitaratu zuen 1972an artikulu zientifiko batean "Asymptotic Properties of Nearest Neighbor Rules Using Edited Data" izenburupean<ref>{{Erreferentzia|izena=Dennis L.|abizena=Wilson|izenburua=Asymptotic Properties of Nearest Neighbor Rules Using Edited Data|orrialdeak=408–421|data=1972-07|url=http://ieeexplore.ieee.org/document/4309137/|aldizkaria=IEEE Transactions on Systems, Man, and Cybernetics|alea=3|zenbakia=SMC-2|issn=0018-9472|doi=10.1109/TSMC.1972.4309137|sartze-data=2019-12-26}}</ref>. Honakoak dira urratsak:
 
# Errepikatu <math>i</math> guztietarako:
=== Wilsonen edizioa ===
#* Datu-baseko <math>x_1,\ldots, x_{i-1}, x_{i+1},\ldots, x_N</math> kasuen artean k auzokide hurbilenak aurkitu.
Datubaseko elementu bakoitzari K-NN algoritmoa aplikatzen zaio (nahi dugun K hartuta), K elementu hurbilenetari sarrien agertzen den klasea esleitzen diogu. Hortik, esleitutako klasea eta klase erreala ezberdinak badira, kasua datu-basetik ezabatzen da eta bestela gordetzen dugu.
#* <math>x_i</math> kasuari bere auzokide hurbilenen artean sarrien agertzen den klasea esleitu.
# 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 ==
<references />
{{erreferentzia_zerrenda}}
== Ikus baita ==
 
* [[Datu-meatzaritza|Datu meatzaritza]]
== Ikus, gainera ==
* [[Datu-meatzaritza]]
* [[Erabaki-zuhaitzen bidezko ikaskuntza|Erabakitze Zuhaitzak]]
* [[Algoritmo genetikoGenetikoak]]ak
* [[Sailkatzaile Bayestarrak]]
* [[Weka]]
 
== 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)]"
 
 
{{autoritate kontrola}}
 
[[Kategoria:Estatistika ez-parametrikoa]]
[[Kategoria:Ikasketa automatikoa]]
[[Kategoria:Informatika]]
[[Kategoria:Datu-meatzaritza]]
[[Kategoria:Adimen artifiziala]]