Ho un database con 500.000 punti in uno spazio di 100 dimensioni e voglio trovare i 2 punti più vicini. Come lo faccio?Come trovare i 2 punti più vicini in uno spazio di 100 dimensioni con 500.000 punti?
Aggiornamento: lo spazio è euclideo, mi dispiace. E grazie per tutte le risposte. BTW questo non è compito a casa.
Si potrebbe provare il ANN library, ma che dà solo risultati affidabili fino a 20 dimensioni.
Grazie. ANN è proprio quello che stavo cercando. Spero che possa contenere tutto nella RAM. – louzer
ANN è facile da usare, ma va notato che si tratta di un'implementazione approssimativa del vicino più prossimo, quindi non è garantito che sia corretto. –
C'è un capitolo dedicato Introduction to Algorithms di trovare due punti più vicini in uno spazio bidimensionale in O (n * log n) tempo. Puoi verificarlo su google books. In effetti, lo consiglio a tutti perché il modo in cui applicano la tecnica divide et impera a questo problema è molto semplice, elegante e impressionante.
Anche se non può essere esteso direttamente al tuo problema (come costante 7 dovrebbe essere sostituito con 2^101 - 1), dovrebbe andare bene per la maggior parte dei set di dati. Quindi, se hai un input ragionevolmente casuale, ti darà la complessità O(n*logn*m) dove n è il numero di punti e m è il numero di dimensioni.
modificare
Questo è tutto a patto di avere spazio euclideo. La lunghezza del vettore v è sqrt(v0^2 + v1^2 + v2^2 + ...). Se è possibile scegliere la metrica, tuttavia, potrebbero esserci altre opzioni per ottimizzare l'algoritmo.
Esegui PCA sui tuoi dati per convertire vettori da 100 dimensioni a dire 20 dimensioni. Quindi crea un albero dei vicini di K (vicino all'albero KD) e ottieni i 2 vicini più vicini in base alla distanza euclidea.
Generalmente se n. di dimensioni sono molto grandi quindi è necessario adottare un approccio di forza bruta (parallelo + distribuito/riduttore di mappa) o un approccio basato sul clustering.
Utilizzare un albero kd. Stai osservando un problema vicino più vicino e ci sono strutture dati altamente ottimizzate per gestire questa esatta classe di problemi.
http://en.wikipedia.org/wiki/Kd-tree
P.S. Problema divertente!
Questa è la risposta corretta. –
Utilizzare la struttura dati nota come KD-TREE. Avrai bisogno di allocare molta memoria, ma potresti scoprire un'ottimizzazione o due sulla base dei tuoi dati.
http://en.wikipedia.org/wiki/Kd-tree.
Il mio amico stava lavorando al suo dottorato anni di tesi fa, quando ha incontrato un problema simile. Il suo lavoro era dell'ordine di 1 milione di punti su 10 dimensioni. Abbiamo costruito una libreria kd-tree per risolverlo. Potremmo essere in grado di scavare il codice se vuoi contattarci offline.
Ecco il suo articolo pubblicato: http://www.elec.qmul.ac.uk/people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf
kdtrees rendono facile trovare un vicino più prossimo ad un dato punto in O (log n) ora, come ricordo. Esiste un'ottimizzazione per trovare la coppia più vicina di punti in meno di O (n log n)? – rampion
-1, anche secondo wikipedia kD-tree è efficiente se N >> 2^k (dove k è dimensioni e N numero di punti, in questo caso 2^100 >> 5e5 e la risposta è completamente fuorviante) – Unreason
10d è non 100d. Anche se i punti dati giacciono approssimativamente su un piano 10-d in 100d, kd-tree non può funzionare (imho): pensa ad un albero di kd profondo 100 s. – denis
È uno spazio metrico? – Seth
Fuori interesse, dove hai preso uno spazio di 100 dimensioni? –
la domanda manca di chiarezza. questa è una domanda matematica? – Sarmaad