Bollträd

Inom datavetenskap är ett bollträd , ett bollträd eller ett metriskt träd en datastruktur för rymdpartitionering för att organisera punkter i ett flerdimensionellt utrymme. Ett bollträd delar upp datapunkter i en kapslad uppsättning bollar . Den resulterande datastrukturen har egenskaper som gör den användbar för ett antal tillämpningar, framför allt närmaste grannesökning .

Informell beskrivning

Ett bollträd är ett binärt träd där varje nod definierar en D-dimensionell boll som innehåller en delmängd av de punkter som ska sökas. Varje intern nod i trädet delar upp datapunkterna i två disjunkta uppsättningar som är associerade med olika bollar. Medan själva bollarna kan skära varandra, tilldelas varje punkt till den ena eller andra bollen i partitionen enligt dess avstånd från bollens mitt. Varje lövnod i trädet definierar en boll och räknar upp alla datapunkter inuti den bollen.

Varje nod i trädet definierar den minsta bollen som innehåller alla datapunkter i dess underträd. Detta ger upphov till den användbara egenskapen att, för en given testpunkt $t$ utanför bollen, avståndet till valfri punkt i en boll $B$ i trädet är större än eller lika med avståndet från $t$ till bollens yta. Formellt:

D^{B}(t)={\begin{cases}\max(|t-{\textit {B.pivot}}|-{\textit {B.radius} },D^{\textit {B.parent}}),&{\text{if }}B\neq Rot\\\max(|t-{\textit {B.pivot}}|-{\textit { B.radius}},0),&{\text{if }}B=Root\\\end{cases}}

Där $D^{B}(t)$ är det minsta möjliga avståndet från någon punkt i bollen $B$ till någon punkt $t$ .

Kulträd är relaterade till M-trädet , men stöder bara binära delar, medan i M-trädet delar varje nivå sig $m$ till $2m$ gånger, vilket leder till en grundare trädstruktur, behöver därför färre avståndsberäkningar, vilket vanligtvis ger snabbare frågor. Dessutom kan M-trees bättre lagras på disk , som är organiserad i sidor . M-trädet håller också avstånden från föräldernoden förberäknade för att påskynda frågor.

Utsiktspunktsträd är också lika, men de delas binärt upp i en boll, och de återstående data, istället för att använda två bollar.

Konstruktion

Ett antal bollträdkonstruktionsalgoritmer finns tillgängliga. Målet med en sådan algoritm är att producera ett träd som effektivt stöder frågor av önskad typ (t.ex. närmaste granne) effektivt i genomsnittsfallet. De specifika kriterierna för ett idealträd kommer att bero på vilken typ av fråga som besvaras och fördelningen av de underliggande data. Ett allmänt tillämpligt mått på ett effektivt träd är dock ett som minimerar den totala volymen av dess interna noder. Med tanke på de olika fördelningarna av datauppsättningar i den verkliga världen är detta en svår uppgift, men det finns flera heuristik som delar upp data väl i praktiken. I allmänhet finns det en avvägning mellan kostnaden för att bygga ett träd och effektiviteten som uppnås med detta mått.

Detta avsnitt beskriver kortfattat den enklaste av dessa algoritmer. En mer djupgående diskussion om fem algoritmer gavs av Stephen Omohundro.

k -d konstruktionsalgoritm

Den enklaste proceduren kallas " k -d-konstruktionsalgoritmen", i analogi med processen som används för att konstruera k -d-träd . Detta är en offlinealgoritm , det vill säga en algoritm som arbetar på hela datamängden samtidigt. Trädet byggs uppifrån och ner genom att rekursivt dela upp datapunkterna i två uppsättningar. Uppdelningar väljs längs den enskilda dimensionen med den största spridningen av punkter, med uppsättningarna uppdelade med medianvärdet för alla punkter längs den dimensionen. Att hitta uppdelningen för varje intern nod kräver linjär tid i antalet sampel som finns i den noden, vilket ger en algoritm med tidskomplexitet ${\displaystyle O(n\,\log \,n)} ,$ där n är antalet datapunkter.

Pseudokod

      
         
    
             
    
 funktion  construct_balltree  matas  in:  D  , en uppsättning datapunkter.  output:  B  , roten till ett konstruerat bollträd.  om  en enda punkt återstår,  skapa  ett blad  B  som innehåller den enda punkten i  D  return  B  annars  låt  c  vara dimensionen för största spridning låt  p  vara den valda centrala punkten med tanke på c låt  L  ,  R  vara uppsättningarna av punkter som ligger till vänster och höger om medianen längs dimension  c  skapa  B  med två barn:  B  .pivot :=  p  B  .child1 := construct_balltree(L),  B  .child2 := construct_balltree(R), låt  B  .radius vara maximalt avstånd från  p  bland barn  return  B  end if  end funktion

Sök efter närmaste granne

En viktig tillämpning av bollträd är att påskynda sökningar efter närmaste granne , där målet är att hitta de k-punkter i trädet som är närmast en given testpunkt med någon avståndsmetrik (t.ex. Euklidiskt avstånd ). En enkel sökalgoritm, ibland kallad KNS1, utnyttjar avståndsegenskapen för bollträdet. I synnerhet, om algoritmen söker igenom datastrukturen med en testpunkt t och redan har sett någon punkt p som är närmast t bland de punkter som hittills påträffats, då kan varje underträd vars kula är längre från t än p ignoreras för resten av sökningen.

Beskrivning

Algoritmen för bollträdet närmaste granne undersöker noder i djup-första ordning, med början vid roten. Under sökningen upprätthåller algoritmen en kö för max-första prioritet (ofta implementerad med en heap ), betecknad Q här, av de k närmaste punkter som har påträffats hittills. Vid varje nod B kan den utföra en av tre operationer innan den slutligen returnerar en uppdaterad version av prioritetskön:

Om avståndet från testpunkten t till den aktuella noden B är större än den längsta punkten i Q , ignorera B och returnera Q.
Om B är en lövnod, skanna igenom varje punkt som räknas upp i B och uppdatera kön till närmaste granne på lämpligt sätt. Returnera den uppdaterade kön.
Om B är en intern nod, anropa algoritmen rekursivt på B :s två barn, genomsök barnet vars centrum är närmare t först . Returnera kön efter att vart och ett av dessa samtal har uppdaterat den i sin tur.

Genom att utföra den rekursiva sökningen i den ordning som beskrivs i punkt 3 ovan ökar sannolikheten för att det ytterligare barnet kommer att beskäras helt under sökningen.

Pseudokod

    
        
        
            
            
        
    
     funktion  knn_search  matas  in:  t, målpunkten för frågan k, antalet närmaste grannar till t för att söka efter Q, max-förstaprioritetskö som innehåller högst k punkter B, en nod eller boll, i trädets utdata  :  Q, som innehåller de k närmaste grannarna inifrån B  om  avstånd(t, B.pivot) - B.radius ≥ avstånd(t, Q.först)  returnera  sedan  Q oförändrat  annars om  B är en lövnod  då  för varje  punkt p i B  gör  om  avstånd(t, p) < avstånd(t, Q.först) lägg   sedan  till p till Q  om  storlek(Q) > k ta   sedan  bort den längst bort från Q-  änden om  slut om  upprepa  annat  låt barn1 vara den underordnade noden närmast t låt barn2 vara den underordnade noden längst bort t knn_search(t, k, Q, child1) knn_search(t, k, Q, child2)  end if  return  Q  end funktion

Prestanda

Jämfört med flera andra datastrukturer har bollträd visat sig fungera ganska bra på det närmaste grannesökproblemet, särskilt när deras antal dimensioner växer. Den bästa närmaste grannedatastrukturen för en given applikation kommer dock att bero på dimensionaliteten, antalet datapunkter och den underliggande strukturen för datan.