In informatica, un k-d tree o albero k-d (abbreviazione di albero k-dimensionale) è una struttura dati utilizzata per il partizionamento dello spazio e finalizzata all’organizzazione dei punti in uno spazio k-dimensionale, ossia definito esattamente da k assi ortogonali, un dato numero finito di dimensioni.

Introdotto nel 1975 da Jon Louis Bentley, l'albero k-d è una struttura dati utile in diverse applicazioni, quali:

Ricerche che coinvolgono una chiave di ricerca multidimensionale ad esempio, ricerche per intervallo e ricerche del vicino più prossimo per l'algoritmo k-NN; ricerca di punti di interesse vicini a una coordinata GPS (ad es. "trova il ristorante più vicino") nei Sistemi Informativi Geografici (GIS) Creazione di nuvole di punti: in computer grafica e visione artificiale, viene utilizzato per il ray tracing e per la ricostruzione di nuvole di punti 3D (ad es. dati LiDAR).

Descrizione L'albero k-d è un albero binario in cui ogni nodo è un punto k-dimensionale, un caso particolare di albero binario di partizionamento dello spazio. Ogni nodo non-foglia può essere considerato come generatore implicito di un iperpiano separatore che divide lo spazio in due parti, note come semispazi. I punti a sinistra di questo iperpiano sono rappresentati dal sottoalbero sinistro di quel nodo, mentre quelli a destra dell'iperpiano sono rappresentati dal sottoalbero destro.

Meccanismo di partizione In generale la direzione dell'iperpiano viene scelta nel modo seguente: ogni nodo dell’albero è associato a una delle k dimensioni, con l'iperpiano perpendicolare all’asse di quella dimensione. Quindi, ad esempio, se per una particolare divisione viene scelto l’asse “x”, tutti i punti nel sottoalbero con un valore di “x” inferiore a quello del nodo appariranno nel sottoalbero sinistro e tutti i punti con un valore di “x” maggiore saranno nel sottoalbero destro. In tal caso, l'iperpiano sarebbe determinato dal valore di x del punto e la sua normale sarebbe l’asse x unitario. La scelta dell'asse di divisione e del punto di partizionamento (split) varia a seconda dell'implementazione, ma l'approccio standard (proposto da Bentley) segue queste regole:

Rotazione degli assi: si seleziona l'asse di divisione in base alla profondità del nodo nell'albero. Ad esempio, in uno spazio tridimensionale (k=3), la radice divide lungo l'asse x (profondità 0), il livello successivo lungo l'asse y (profondità 1), quello dopo lungo l'asse z (profondità 2), per poi ricominciare dall'asse x (profondità 3). In generale, l'asse è dato da:

Scelta della mediana: per garantire che l'albero sia bilanciato, il punto di split viene scelto calcolando la mediana delle coordinate dei punti lungo l'asse selezionato.

Operazioni e complessità Le principali operazioni sono relative alla creazione della struttura e alla ricerca all'interno della stessa.

Costruzione (statica)

La costruzione di un albero k-d a partire da un insieme di N punti avviene in modo ricorsivo:

Si seleziona l'asse corrente. Si ordina il set di punti in base alla coordinata dell'asse e si trova la mediana. Il punto mediano diventa il nodo corrente. Si applica la procedura ricorsivamente sui punti a sinistra e a destra della mediana.

Se la mediana viene calcolata in tempo lineare utilizzando un algoritmo come Quickselect, il tempo di costruzione totale è ottimale e pari a .

Ricerca del vicino più prossimo

La ricerca del vicino più prossimo o NNS (Nearest Neighbor Search) mira a trovare il punto nell'albero più vicino a un punto di query Q. L'algoritmo sfrutta le proprietà geometriche dell'albero per eliminare ("potare") interi rami senza doverli esplorare: Discesa: si scende attraverso l'albero come in una normale ricerca binaria per trovare la foglia in cui si troverebbe Q; Salita e Verifica: si calcola la distanza tra Q e il punto corrente. Se è inferiore alla distanza minima attuale, diventa il nuovo "migliore"; Potatura: prima di risalire al nodo padre, l'algoritmo controlla se l'iperpiano di divisione del nodo interseca una sfera ipotetica centrata in Q con raggio pari alla distanza minima corrente; se non c'è intersezione, l'intero sottoalbero opposto viene scartato, garantendo un grande risparmio computazionale.

Complessità

La complessità delle operazioni su un albero k-d dipende fortemente dal bilanciamento dell'albero e dal numero di dimensioni k:

+ Operazione Caso Ottimo / Medio Caso Peggiore Spazio di memoria Costruzione se l'albero è bilanciato Ricerca NNS Query di intervallo dove rappresenta il numero di punti trovati nella query di intervallo

Note

Note

Collegamenti esterni k-d tree nella documentazione di scikit-learn

Categoria:Algoritmi di ricerca Categoria:Algoritmi per l'apprendimento automatico Categoria:Strutture dati Categoria:Visione artificiale