Ball tree

In informatica, un ball tree (letteralmente albero a sfere) è una struttura dati spaziale ad albero utilizzata per organizzare punti in uno spazio metrico multidimensionale. Trova la sua principale applicazione nell'ottimizzazione di query geometriche, in particolare nella ricerca dei vicini più prossimi (Nearest Neighbor Search) e nel clustering di dati in spazi a elevata dimensionalità (${\displaystyle d\geq 10}$), dove altre strutture come i k-d tree soffrono della cosiddetta maledizione della dimensionalità.

A differenza dei k-d tree, che dividono lo spazio orientando iperpiani lungo gli assi cartesiani, i ball tree partizionano i dati racchiudendoli in ipersfere (o ball) che possono intersecarsi liberamente, ma il cui volume complessivo viene minimizzato per ottimizzare i tempi di potatura durante la ricerca.

Struttura geometrica e proprietà

Un ball tree è un albero binario in cui ogni nodo definisce una regione ipersferica nello spazio metrico considerato.

Ogni nodo interno ${\displaystyle N}$ dell'albero è caratterizzato da una coppia ${\displaystyle (c,r)}$, dove:

• ${\displaystyle c\in \mathbb {R} ^{d}}$ è il centro dell'ipersfera.
• ${\displaystyle r\in \mathbb {R} _{+}}$è il raggio dell'ipersfera.

Algoritmo di costruzione (top-down)

La costruzione efficiente di un ball tree si basa sulla decomposizione ricorsiva del dataset. L'obiettivo principale è scegliere i centri delle ipersfere in modo da minimizzare il loro raggio (e quindi il volume dello spazio racchiuso), riducendo le sovrapposizioni.

Il metodo euristico standard più utilizzato segue questi passaggi:

• Calcolo del centro: Dato un insieme di punti ${\displaystyle P}$, il centro ${\displaystyle c}$ viene calcolato come il baricentro (media) dei punti:

${\displaystyle c={\frac {1}{|P|}}\sum _{x\in P}x}$

• Calcolo del raggio: il raggio ${\displaystyle r}$ è impostato come la distanza massima tra il centro ${\displaystyle c}$ e il punto più lontano nell'insieme ${\displaystyle P}$:

${\displaystyle r=\max _{x\in P}\|x-c\|}$

• Scelta della linea di proiezione (slipping):
  • si trova il punto ${\displaystyle x_{A}\in P}$ più distante dal centro ${\displaystyle c}$.
  • si trova il punto ${\displaystyle x_{B}\in P}$ più distante da ${\displaystyle x_{A}}$. La retta che unisce ${\displaystyle x_{A}}$ e ${\displaystyle x_{B}}$ rappresenta l'asse di massima variazione (un'approssimazione della prima componente principale).
• Partizionamento (split): tutti i punti in ${\displaystyle P}$ vengono proiettati sulla retta ${\displaystyle {\overline {x_{A}x_{B}}}}$; l'insieme viene diviso in due sottoinsiemi: i punti la cui proiezione è più vicina a ${\displaystyle x_{A}}$ vanno nel figlio sinistro, i restanti nel figlio destro.
• Ricorsione: il processo si ripete ricorsivamente per i due sottoinsiemi finché il numero di punti non scende sotto una soglia prefissata (dimensione della foglia).

Algoritmo di ricerca dei vicini più prossimi

La ricerca del vicino più prossimo con un ball tree sfrutta la disuguaglianza triangolare per implementare una potente strategia branch and bound, che permette di scartare interi rami dell'albero senza doverne esaminare i punti interni.

Dato un punto di query ${\displaystyle q}$ e una distanza di soglia mobile ${\displaystyle d_{\max }}$ (che rappresenta la distanza attuale dal ${\displaystyle k}$-esimo vicino più prossimo trovato fino a quel momento):

1. Calcolo della distanza dal centro (fase iniziale sul nodo ${\displaystyle N}$): si calcola la distanza tra il punto di query q e il centro c del nodo corrente: ${\displaystyle d=\|q-c\|}$.
2. Test di potatura (verifica geometrica): se ${\displaystyle d-r\geq d_{\max }}$, significa che persino il punto più vicino possibile all'interno della sfera di ${\displaystyle N}$ è più lontano del miglior vicino già trovato. Il nodo ${\displaystyle N}$ e tutto il suo sottoalbero vengono scartati immediatamente.
3. Scorrimento condizionato (visita delle foglie): se il nodo è una foglia, si calcola la distanza esatta tra ${\displaystyle q}$ e tutti i punti fisici contenuti nella foglia, aggiornando la lista dei ${\displaystyle k}$ vicini più prossimi e abbassando il valore di ${\displaystyle d_{\max }}$.
4. Esplorazione prioritaria (scelta del ramo ricorsivo): se il nodo è interno, si determina quale dei due figli abbia il centro più vicino a ${\displaystyle q}$. Si visita prima quel figlio (per massimizzare la probabilità di abbassare rapidamente ${\displaystyle d_{\max }}$) e successivamente si valuta l'altro figlio applicando nuovamente il test di potatura.

Confronto con il k-d tree

Mentre i k-d tree dividono lo spazio con iperpiani ortogonali agli assi, creando regioni cubiche o rettangolari, i ball tree usano regioni sferiche. Questo comporta differenze strutturali cruciali:

Al crescere della dimensionalità, gli "angoli" degli iper-rettangoli dei k-d tree tendono a svuotarsi a causa delle proprietà degli spazi iperdimensionali, costringendo l'algoritmo di ricerca a verificare quasi tutti i rami. Le iper-linee curve delle sfere riducono questo volume inutilizzato, rendendo i ball tree decisamente più efficienti in contesti di apprendimento automatico con molte feature (ad es. embedding di immagini o testi).

Note

Collegamenti esterni

• ball tree nella documentazione di scikit-learn

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Classificazione a singola classe · Ranking · Regole di associazione · Apprendimento non supervisionato · Apprendimento semi-supervisionato · Apprendimento supervisionato · Apprendimento debolmente supervisionato · Apprendimento auto-supervisionato · Apprendimento da pochi esempi · Apprendimento gerarchico · Apprendimento per rinforzo · Apprendimento profondo · Apprendimento online · Apprendimento incrementale · Apprendimento trasduttivo · Apprendimento di rappresentazioni · Apprendimento per similarità · Apprendimento per contrasto · Concept drift · Meta-apprendimento · Dati mancanti
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · Clustering spettrale · DBSCAN · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random field CRF · Modello di Markov nascosto · Algoritmo k-nearest neighbors (k-NN) · Ragionamento basato su casi (CBR) · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Modello grafico · Rete bayesiana · Macchine a vettori di supporto (SVM) · Processo gaussiano · Modello ensemble · Boosting · Bagging · Classifier chain · Cascading · Classificatore ECOC · Stacking · Voting
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Analisi della correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Apprendimento di varietà (manifold learning) · Estrazione di caratteristiche · Immersione localmente lineare (LLE) · Isomap · Scaling multidimensionale (MDS) · Selezione delle caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Percettrone basato su kernel · Rete neurale a funzioni base radiali (RBF net) · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Rete neurale grafica · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · PyTorch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico

Portale Informatica

Portale Matematica