K auzokide hurbilenak

k auzokide hurbilenen metodoa (ingelesez: k-nearest neighbors edo K-NN) 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.

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; 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.

Algoritmoa

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. Abiapuntua $N$ kasuz osatutako datu-base bat da, $\{(x_{1},y_{1}),...,(x_{N},\;y_{N})\}$ modukoa, non $x_{i}$ bektoreak $i.$ kasua deskribatzen duen eta $y_{i}$ den $C$ 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, $x$ bektorearen bidez deskribatutako kasu berri bat iristen denean, datu-baseko $x_{i}$ 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 $y_{i}$ klasea begiratu eta sarrien agertzen den klasea esleitzen zaio $x$ kasu berriari. Eredurik erabili gabe, test-fasean kalkulatutako distantzietan oinarritzen da k-NN algoritmoa kasu berriaren klase-aldagaiaren iragarpena egiteko.

Irudian k-NN algoritmoaren adibide bat ikus daiteke. Datu-base horretan $N=11$ kasu daude: horietako 6 "karratu urdin" klasekoak dira eta gainerako 5ak "triangelu gorri" klasekoak. Kasuak planoan adierazita daude, hau da, kasu bakoitza adierazten duen $x_{i}$ bektoreak bi osagai ditu. Zirkunferentzia berde batez adierazita dator sailkatu behar den kasu berria, $x$ 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.

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.

Distantzia euklidearra

k-NN algoritmoak prototipoen edo kasuen arteko distantziak kalkulatu behar ditu. Normalean distantzia euklidearra erabiltzen da. n-dimentsioko espazio euklidear batean, $x_{1}=(x_{11},x_{12},\dots ,x_{1n})\,$ eta $x_{2}=(x_{21},x_{22},\dots ,x_{2n})\,$ bi punturen arteko distantzia euklidearra horrela definitzen da:

$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}}}.$

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

Kasuaren deskribapena bi aldagai iragarlez ematen denean, $x_{1}=(x_{11},x_{12})\,$ eta $x_{2}=(x_{21},x_{22})\,$ bi puntuan planoan adieraz daitezke, eta distantzia euklidearraren kalkulua horrela geratzen da:

emateko.

$d_{E}(x_{1},x_{2})={\sqrt {(x_{11}-x_{21})^{2}+(x_{12}-x_{22})^{2}}}$

Distantziaren definizio hori Pitagorasek emandako teorematik eta gerora Euklidesek egindako formalizazio lanetik eratorriak dira: geometria euklidearra.

k parametroa

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.

Algoritmoaren aldaerak

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.

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". $x_{i}=(x_{i1},x_{i2},\dots ,x_{in})\,$auzokideak distantziaren arabera haztatu egiten dira, $i=1,\ldots ,k$. Haztapenak garrantzia maila desberdina ematen die kasuei, $x=(x_{1},x_{2},\dots ,x_{n})$ kasu berritik gertuen daudenek haztapen altuagoa jasoko dutelarik. Distantziaren araberako $w_{i}$ haztapena modu desberdinean defini daiteke:

$w_{i}={\frac {1}{d_{E}(x_{i},x)}},\quad \quad w_{i}={\frac {1}{d_{E}(x_{i},x)^{2}}}$ 

Auzokide hurbilenak klaseka elkartu eta haien haztapenen batura egiten da. Batura handieneko klasea esleitzen zaio kasu berriari.

Aldagai iragarleak haztatzea

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

Adibide bat jartzearren, datu-baseko kasuak osasun-zentro bateko pazienteak badira, $x=(x_{1},x_{2},\dots ,x_{n})$ bektoreek pazienteei buruzko informazioa emango dute: adina, egindako probaren baten emaitza, etab. Medikuak gaixotasunei buruz duen ezagutza erabiltzen du $x$ pazientearen sintomak aztertuz diagnostikoa egiteko; $C$ klase-aldagaia da diagnostikoa gordetzen duena. Antzeko egoeran dauden pazienteen (auzokide hurbilenen) diagnostikoan oinarritzen da k-NN algoritmoa $C$-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 $w_{j}$ haztapena kalkulatu behar da. Kalkulatzeko modu bat $X$ aldagai iragarlearen eta $C$ klase-aldagaiaren elkarrekiko informazioaren neurria erabiltzea da:

${\begin{aligned}\operatorname {I} (X,C)&{}=\sum _{i=1}^{n}\sum _{j=1}^{m}p(x_{i},c_{j})\log _{2}{\frac {p(x_{i},c_{j})}{p(x_{i})p(c_{j})}}\\\end{aligned}},$

$n$ izanik $X$ aldagaiaren balio posibleak eta $m$ izanik $C$-ren etiketa posible guztiak.

Distantzia euklidear haztatuaren kalkulua bi aldagai iragarleren kasurako horrela geratzen da:

$d_{E}(x,x_{i})={\sqrt {w_{1}(x_{1}-x_{i1})^{2}+w_{2}(x_{2}-x_{i2})^{2}}},$

$x=(x_{1},x_{2})$ kasu berria izanik eta $x_{i}=(x_{i1},x_{i2})$ datu-baseko kasuak, $i=1,\ldots ,N$.

Datu-baseko kasu kopurua murriztea

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" 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:

1. Datu-baseko lehenengo kasua STORE zerrendan sartu.
2. Datu-baseko bigarren kasuaren klasearen iragarpena egin k-NN erabiliz STOREko kasuetan oinarrituz. Sailkapena zuzena bada, kasua GRABBAG zerrendan sartu, bestela STOREn sartu.
3. Modu berean segi datu-baseko kasu guztiekin.
4. 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.
5. 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.

• 
  1.Irudia: Datu-basea
• 
  2.Irudia: Klaseen banaketa (1-NN-rekin)
• 
  3.Irudia: Klaseen banaketa (5-NN-rekin)
• 
  4.Irudia: Datu-base murriztua
• 
  5.Irudia: Klaseen banaketa datu-base murriztuan (1-NN-rekin)

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

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. Honakoak dira urratsak:

1. Errepikatu $i$ guztietarako:
   • Datu-baseko $x_{1},\ldots ,x_{i-1},x_{i+1},\ldots ,x_{N}$ kasuen artean k auzokide hurbilenak aurkitu.
   • $x_{i}$ kasuari bere auzokide hurbilenen artean sarrien agertzen den klasea esleitu.
2. 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.

Ikus, gainera

• Datu meatzaritza
• Erabakitze Zuhaitzak
• Algoritmo Genetikoak
• Sailkatzaile Bayestarrak
• Weka

Kanpo estekak

• (ingelesez) "A Simple Introduction to K-Nearest Neighbors Algorithm"
• (ingelesez) "Model Selection, Tuning and Evaluation in K-Nearest Neighbors"
• (ingelesez) "Introduction to k-Nearest Neighbors: A powerful Machine Learning Algorithm (with implementation in Python & R)"

• Datuak: Q1071612