U informatici, Lopta stablo, ili Metričko stablo, je struktura podataka za particionisanje memorije u multidimenzionom prostoru.[1] Naziv lopta stablo dolazi iz činjenice da particioniše memoriju u zbijene setove hipersfera znane kao "lopte". Rezultat je da struktura podataka ima karakteristike koje je čine korisnim za veliki broj aplikacija, najpoznatija,pretraživanje najbližeg suseda .

Informacioni opisУреди

Lopta stablo je binarno stablo u kojoj svaki čvor definiše D-dimenzionu hipersferu, ili loptu, koja sadrži podskup tačaka koje treba pretražiti. Svaki čvor stabla particioniše memoriju u disjunktne setove koji su povezani sa različitim loptama. Dok se lopte medusobno mogu ukrstiti, svaki deo memorije je dodeljen jednoj ili drugoj lopti prilikom particionisanja, prema njegovoj udaljenosti od centra lopte. Svaki list u stablu definiše sferu i numeriše sve delove memorije u toj lopti.

Svaki čvor u stablu definiše najmanju loptu koja sadrži sve delove memorije u svom podstablu. Ovo omogućuje da za test tačku t, rastojanje do svake tačke u lopti B u drvetu je veća ili jednaka udaljenosti   od lopte. Formalno: [2]

 

Gde je   minimalno moguće rastojanje od bilo koje tačke u lopti B do neke tačke t.

Lopta stabla su u relaciji sa M-stablom, ali podržavaju samo binarne podele, dok se u M-stablu svaki nivo može deliti od   do   puta, pa dolazi do manje dubine strukture stabla. M-stablo takođe odrzava razdaljinu od roditelja, kako bi ubrzao pozive.

KonstrukcijaУреди

Nekoliko konstruktivnih algoritama lopta stabala su dostupni.[3] Cilj takvih algoritama je da naprave stabla koja će efikasno podržati upite željenih tipova(npr. najbliži sused) u prosečnom slučaju. Specifični kriterijum je idealno drvo koje zavisi od tipa pitanja na koje se odgovara i distribuciju fundamentalnih podataka. Ipak, generalno, efikasno drvo je ono koje minimizuje obim svojih unutrasnjih čvorova. U praksi se pokazuje da je ovo tesko izvesti, ali postoji nekoliko heuristika koje dobro dele podatke. Generalno, treba naci sredinu izmedu cene za pravljenje stabla i efikasnosti koja je ostvarena. [2]

U ovoj sekciji bice opisani najprostiji od ovih algoritama. Detaljniji opis dao je Stephen Omohundro.[3]

k-d Konstrukcioni algoritamУреди

Najjednostavnija procedura je "k-d Konstrukcioni algoritam", analogno sa svim procesima koji se koriste za konstrukciju K-D stabla. Ovo je off-line algoritam, odnosno, algoritam koji operiše na celom skupu podataka odjednom. Stablo je izgradeno odozgo nadole rekurzivno deleći podatke u dva skupa. Delovi su izabrani koristeći jednu dimenziju sa najvećom podelom taćaka, i skupovima podeljenjim srednjom vrednošću svih tacaka. Pretraga svih podela za svaki unutrasnji čvor zahteva linearno vreme po broju uzoraka koji se nalaze u tom čvoru, dajući algoritam sa vremenskom slozenoscu  , gde je n broj podataka.

PseudokodУреди

   function construct_balltree is
       input: 
           D, an array of data points
       output: 
           B, the root of a constructed ball tree
       if a single point remains then
           create a leaf B containing the single point in D
           return B
       else
           let c be the dimension of greatest spread
           let L,R be the sets of points lying to the left and right of the median along dimension c
           create B with two children: 
               B.pivot = c
               B.child1 = construct_balltree(L),
               B.child2 = construct_balltree(R)
           return B
       end if
   end function

Trazenje najbližeg susedaУреди

Bitna stavka koju lopta stabla rade je ubrzavanje traženja najbližeg suseda, u kojem treba naci k tačaka u stablu, koja su najbliža određenoj tacki na određenom rastojanju. Jednostavan algoritam, zvan KNS1 koristi ta rastojanja. Ako algoritam traži strukturu podataka sa test tačkom t i vec ima neku tačku p koja je najbliza tački t, onda ce svako stablo cija je lopta dalja od t nego od p biti ignorisano do kraja pregrage.

OpisУреди

Lopta stablo je algoritam najbližeg suseda koji ispituje čvorove u dubinu, počinjuci iz korena. Prilikom pretrage, algoritam radi na osnovu reda sa prioritetom(koji je često implementiran preko hipa (struktura podataka), označava Q, od k najblizih tacaka koje je do tada prosao. Na svakom cvoru B, moze izvršiti jednu od tri operacije, pre nego što konacno vrati promenjenu verziju prioriteta.

  1. Ako je rastojanje od test tačke t do trenutnog čvora B veca od najdalje tačke u Q, ignorisi B i vrati Q.
  2. Ako je B list stabla, prođi kroz sve tačke numerisane u B , i izmeni redosled najbližeg suseda. I vrati novi redosled.
  1. Ako je B unutrašnji čvor, pozovi algoritam rekurzivno za decu čvora B, tražeci dete čiji je centar bliži tacki t.

Vrati redosled posle svakog od ovih poziva u kojem je promenjen redosled.

PseudocodeУреди

   function knn_search is
       input: 
           t, the target point for the query
           k, the number of nearest neighbors of t to search for
           Q, max-first priority queue containing at most k points
           B, a node, or ball, in the tree
       output: 
           Q, containing the k nearest neighbors from within B
       if distance(t, B.pivot) ? distance(t, Q.first) then
           return Q unchanged
       else if B is a leaf node then
           for each point p in B do
               if distance(t, p) < distance(t, Q.first) then
                   add p to Q
                   if size(Q) > k then
                       remove the furthest neighbor from Q
                   end if
               end if
           repeat
       else
           let child1 be the child node closest to t
           let child2 be the child node furthest from t
           knn_search(t, k, Q, child1)
           knn_search(t, k, Q, child2)
       end if
   end function[2]

PerformanseУреди

U poređenju sa nekoliko drugih struktura podataka, lopta stabla su pokazala dobar rad na problemu najbližeg suseda, posebno kada broj dimenzija raste.[1][4] Ipak, najbolja struktura za određenu aplikaciju zavisi od dimenzije, broja podataka, i strukture podataka.

ReferenceУреди

  1. ^ а б doi:10.1007/978-3-540-74976-9_16
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand
  2. ^ а б в Liu, T.; Moore, A. & Gray, A. (2006). „New Algorithms for Efficient High-Dimensional Nonparametric Classification” (PDF). Journal of Machine Learning Research. 7: 1135—1158. 
  3. ^ а б Omohundro, Stephen M. (1989) "Five Balltree Construction Algorithms"
  4. ^ doi:10.1007/978-3-540-88688-4_27
    This citation will be automatically completed in the next few minutes. You can jump the queue or expand by hand