Come cercare in modo efficiente un set di vettori per un vettore che è la corrispondenza più simile

Question

Come cercare in modo efficiente un set di vettori per un vettore che è la corrispondenza più simile

#1 da (3 voti)
#2 da (1 voti)
#3 da (0 voti)
#4 da (0 voti)

1

Purtroppo, non sono nemmeno sicuro delle parole chiave da utilizzare per questa domanda, quindi se è già stato chiesto per favore indicami la strada giusta.

Dato un set di vettori:

[3, 5, 3]
[10, 23, 5]
[123, 53, 97]

(qui, 'vettore' significa un insieme dimensionale di valori numerici).

Mi piacerebbe conoscere un modo per trovare la corrispondenza più simile a qualsiasi vettore di input. Ad esempio,

[2, 4, 5]

Restituirebbe il primo dalla mia lista come la corrispondenza più vicina. Mi piacerebbe anche conoscere la distanza della partita.

Un modo per visualizzarlo è come un grafico a linee.

Non voglio la ricerca lineare. Potrei avere milioni di vettori. Non mi interessa eseguire il tempo di pre-elaborazione; è il tempo di ricerca che voglio ottimizzare.

Definizione della "corrispondenza più vicina"

In questo caso, supponiamo che i dati siano numerici e che la "corrispondenza più vicina" sia un semplice confronto numerico, fornendo una distanza assoluta. Ad esempio, confrontando [2, 4, 5] potresti fornire le distanze dei dati di test di:

[1, 1, 2]
[8, 19, 0]
[121, 49, 92]

Diversi vettori di dimensioni

Come si gestiscono i vettori di diverse dimensioni? Mi piacerebbe essere in grado di gestire casi come il seguente input:

[120, 99]

Corrispondenza del terzo esempio dai dati del test, in alcuni sensi con "punteggio inferiore". Questo perché i due valori sono simili al primo e all'ultimo valore nei dati del test, ignorando il valore medio e in ordine.

Un altro modo per descriverlo potrebbe essere: l'ordine dei valori nel vettore è importante, ma non la posizione.

Soluzioni di clustering

Ho preso in considerazione una qualche forma di clustering: l'hashing dei vettori in bucket, quindi l'hashing dell'input e il restituzione di tutti i vettori nel bucket corrispondente. Ma ciò che mi disturba è che cosa succede se un dato input è vicino al "limite" di un cluster - non sarebbero restituiti altri valori nei cluster adiacenti, vero?

Dominio applicazione

Voglio utilizzare questo algoritmo per trovare versioni musicali simili per le loro lunghezze di brani costitutive. In quanto tale, le lunghezze possono essere memorizzate come un numero intero in qualche unità di tempo (secondi o millisecondi, ad esempio) e i dati finiscono per apparire come sopra.

Così simile all'algoritmo CDDB (FreeDB), ma più clemenza e la capacità di definire ed esplorare la distanza. E supporto per diversi vettori di lunghezza.

Altre domande che ho esaminato

Come trovare il vettore più vicino a un dato vettore? sembra discutere di punti 2D - mentre questo potrebbe essere considerato in uno spazio 2D, i valori in ogni vettore devono essere considerati insieme.

algorithms

posta Dan Gravell 18.08.2016 - 18:57

fonte

4 risposte

Leggi altre domande sui tag algorithms

Come è utile la struttura dei dati di heap? Qual è il nome di questo tipo di complessità?

score 3 · Answer 1

Questa è una mappa concettuale. Poiché non si sa nulla del dominio dell'applicazione, non è possibile fornire suggerimenti concreti.

In generale, i passaggi per affrontare questo problema sono:

Primo stadio Scopri cos'è una buona similarità o misura di distanza tra due vettori di caratteristiche della stessa lunghezza.
- Ci sono molte scelte. Esempi:
- Norm , ad es. L1, L2, L-infinito
- Coseno
- Distanza del mover terrestre (EMD)
- Hash sensibile alla località
- Proiezione casuale
- Mentre alcune scelte potrebbero funzionare meglio per applicazioni specifiche, in generale una toolbox che implementa tutte quelle note sarà in grado di coprire quasi tutte le applicazioni. La possibilità di dover inventare una nuova misura di similarità per il confronto con vettori di pari lunghezza è bassa.
- Tuttavia, esistono ancora alcune misure di distanza specifiche per l'applicazione:
  - Trasformazione in dominio di frequenza. Questo sarà spiegato successivamente.
  - In altre parole, ci sono alcuni tipi di vettori di caratteristiche (quelli che potrebbero essere chiamati serie temporali o segnali) che trarranno vantaggio da un approccio unificato per il confronto di vettori di lunghezza e lunghezza diversa.
Secondo stadio Scopri come misurare la similarità o la distanza tra due vettori di caratteristiche di diversa lunghezza.
- Questo è altamente specifico per l'applicazione.
- In generale, o cade in elaborazione del segnale , o riconoscimento dei pattern .
- Un tipo di dati che è comune sia all'elaborazione del segnale sia al riconoscimento di pattern è chiamato serie storiche . L'asse non deve corrispondere al tempo, tuttavia - l'asse potrebbe essere ad es. coordinata x o coordinata y su un'immagine 2D, ad esempio.
- Le serie temporali possono essere trasformate in dominio di frequenza , dopo di che è possibile eseguire il confronto.
- Le serie temporali possono anche essere scomposte in spazio di scala .
- Le serie temporali che "deformano" o non si allineano correttamente possono essere confrontate usando dynamic time warping (DTW) che si basa sulla programmazione dinamica. Tuttavia, DTW può essere applicato solo a una coppia di vettori contemporaneamente. A differenza delle trasformazioni discusse in precedenza, DTW non può essere utilizzato per estrarre una rappresentazione da un singolo vettore.
- Un'immagine 2D dovrebbe essere trattata come una serie storica di serie temporali (cioè nidificate). Non provare a rasterizzare due immagini di dimensioni diverse in vettori di lunghezze diverse. Invece, ridimensiona le due immagini nella stessa dimensione 2D, quindi converti in un vettore 1D.
Terzo stadio Scopri come velocizzare le ricerche su larga scala, come ad esempio
- Pre-elaborare un numero elevato di vettori memorizzati in modo che le query che richiedono il vettore più vicino non debbano visitare ogni singolo vettore nel negozio. (Questo obiettivo è analogo alla creazione di un indice per una tabella di database, ma sono necessarie tecniche diverse.)
- Ricerca di cluster da un numero elevato di vettori memorizzati
- Queste conoscenze appartengono generalmente al recupero delle informazioni e in particolare recupero informazioni multimediali .
- È possibile effettuare ricerche su casi estremamente semplici come punti 2D / 3D o rettangoli di delimitazione utilizzando la query spaziale . Tuttavia, è inefficace nella gestione del recupero di informazioni multimediali, che potrebbe dover funzionare con vettori con centinaia o migliaia di dimensioni.

score 1 · Answer 2

C'era una domanda simile su CodeReview. La risposta dovrebbe funzionare anche per il tuo problema: link

In breve:

calcola l'intero spazio (valore min / max per ogni dimensione)
crea un cluster di celle per quello spazio
mappa ogni vettore su una cella del cluster

Il vettore cluster ti offre una sorta di ordinamento che richiede solo la ricerca di un piccolo sottoinsieme. Ad esempio, in 2 dimensioni inizi con 9 celle ... se non ci sono vettori all'interno di quelle celle, continua con 16 celle adiacenti e così via.

Tuttavia, le prestazioni di tale soluzione diminuiscono con il numero delle dimensioni del vettore perché il numero di cluster aumenta esponenziale con il numero di dimensioni ...

Se i vettori non sono equamente distribuiti, è possibile anche migliorare l'algoritmo di clustering utilizzando un clustering dinamico: iniziando con 2 celle in ogni dimensione e dividendo ogni cella se contiene molti vettori.

score 0 · Answer 3

Vorrei davvero avere abbastanza punti per commentare, perché questa è più una richiesta di chiarimento che una risposta, ma vabbè.

Per prima cosa:

+1 per "necessità di definizione di 'match più vicino'" - si potrebbe fare, per esempio, similarità coseno (se si considerano i "vettori" in senso matematico), che sarebbe molto diverso da se si considerasse un " vettore "per essere un punto N-dimensionale e volevo solo la distanza tra due punti. ("Vector" nella programmazione può essere un po 'un termine sovraccarico ...)

Secondo:

I don't want to linear search. I could have millions of vectors.

...

I considered some form of clustering - hashing the vectors into buckets, then hashing the input and returning all vectors in the matching bucket.

A meno che l'elenco dei vettori non sia già stato ordinato in qualche modo significativo per la tua definizione di "corrispondenza più vicina", non penso che tu possa battere il tempo lineare. Il fatto che tu abbia considerato "l'hashing dei vettori" implica anche che sei disposto a eseguire una "pre-elaborazione" lineare?

Una semplice scansione lineare + tenere traccia della "migliore corrispondenza finora" dovrebbe essere veloce, anche per milioni di elementi, assumendo che l'operazione di confronto sia essenzialmente costante (che dovrebbe essere).

Se sei solo timida e hai bisogno di elaborare più vettori di quelli che ti stai lasciando intendere ... allora forse è il momento di accendere alcuni core extra e il multithread che fa schifo.

score 0 · Answer 4

Perché non una semplice ricerca binaria? È possibile ordinare i vettori durante la pre-elaborazione e eseguire semplicemente la ricerca logaritmica in un secondo momento. Se ci sono troppi vettori da inserire nella memoria, è possibile utilizzare un albero B + che funzioni bene con gli HDD. Dovresti quindi costruire l'albero durante la pre-elaborazione e cercare in seguito. Usare un albero ti permetterebbe anche di modificare facilmente il set di vettori.