K auzokide hurbilenak

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

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

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

emateko.

${\displaystyle 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-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.

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

${\displaystyle 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.

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

Adibide bat jartzearren, datu-baseko kasuak osasun-zentro bateko pazienteak badira, ${\displaystyle 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 ${\displaystyle x}$ pazientearen sintomak aztertuz diagnostikoa egiteko; ${\displaystyle C}$ klase-aldagaia da diagnostikoa gordetzen duena. Antzeko egoeran dauden pazienteen (auzokide hurbilenen) diagnostikoan oinarritzen da k-NN algoritmoa ${\displaystyle 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 ${\displaystyle w_{j}}$ haztapena kalkulatu behar da. Kalkulatzeko modu bat ${\displaystyle X}$ aldagai iragarlearen eta ${\displaystyle C}$ klase-aldagaiaren elkarrekiko informazioaren neurria erabiltzea da:

${\displaystyle {\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}},}$

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

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

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

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

Hart-ek 1968. urtean argitaratu zuen "The condensed nearest neighbor rule"[5] 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.

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

1. Errepikatu ${\displaystyle i}$ guztietarako:
   • Datu-baseko ${\displaystyle x_{1},\ldots ,x_{i-1},x_{i+1},\ldots ,x_{N}}$ kasuen artean k auzokide hurbilenak aurkitu.
   • ${\displaystyle 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.