PODATKOVNE STRUKTURE ZA POSPEŠITEV ISKANJA BLIŽNJIH PRIMEROV

Vsebina naloge:

Nekateri postopki ocenjevanja atributov (Relief) in strojnega učenja (Nearest Neighbour) med delovanjem iščejo primere, ki se nahajajo v bližini podanega primera. Metoda grobe sile (sekvenčno iskanje) ima linearno zahtevnost in postane pri večjem številu primerov in atributov počasna. Namen seminarske naloge je poiskati in implementirati podatkovne strukture (mreže, kd-drevesa) in algoritme za hitrejše iskanje sosednjih primerov ter preučiti, kdaj in kako vplivajo na hitrost izvajanja algoritmov. študent naj dela v okolju ML*. Izdela naj komponente, ki pri podanih parametrih (primeri, metrika, ...) za podani primer vrnejo spisek najbližjih primerov, pri čemer uporabljajo različne metode iskanja (sekvenčno, z mrežami, s kd-drevesi). Komponente naj vključi v algoritma Relief in k-NN ter izmeri hitrost njunega izvajanja. Zključno poročilo o seminarski naj vsebuje:

Literatura in viri:

M. Sedgewick: Algorithms, Addison-Wesley, TN, 1997

Število študentov: 1 do 2

Dodatne zahteve:

Za izdelavo seminarske naloge je potrebno poznavanje jezika C++.

Mentor:

Janez Demšar
Laboratorij za umetno inteligenco
Fakuleta za računalništvo in informatiko
EMail: janez.demsar@fri.uni-lj.si

Govorilne ure: (na FRI) po dogovoru