rilevamento rapida similitudine

Question

Ho una vasta collezione di oggetti e ho bisogno di capire le somiglianze tra di loro.

Per essere precisi: dati due oggetti posso calcolare la loro diversità come un numero, un metric - valori più alti significano meno somiglianza e 0 significa che gli oggetti hanno contenuti identici. Il costo di calcolo di questo numero è proporzionale alla dimensione dell'oggetto più piccolo (ogni oggetto ha una determinata dimensione).

Ho bisogno dell'abilità di trovare rapidamente, dato un oggetto, l'insieme di oggetti simili ad esso.

Per essere precisi: ho bisogno di produrre una struttura di dati che mappa qualsiasi oggetto o all'insieme di oggetti non più dissimile da o di d, per qualche valore di dissomiglianza d, tale che l'elencazione degli oggetti nell'insieme non richiede più tempo che se fossero in un array o elenco collegato (e forse lo sono effettivamente). In genere, il set sarà molto più piccolo del numero totale di oggetti, quindi è davvero utile eseguire questo calcolo. È abbastanza buono se la struttura dei dati assume una d fissa, ma se funziona per una d arbitraria, ancora meglio.

Hai già riscontrato questo problema o qualcosa di simile? Qual è una buona soluzione?

Per essere precisi: una soluzione semplice coinvolge calcolare le differenze tra tutte le coppie di oggetti, ma è lento - O (n) dove n è il numero di oggetti. Esiste una soluzione generale con una complessità inferiore?

Answer 1

Senza conoscere più dettagli della metrica, è difficile da dire. Non ho idee per eliminare l'aspetto di O (n^2), ma potrebbe esserci un modo per ridurre alcune delle costanti coinvolte. Per esempio, se tu avessi una metrica euclidea d (p, q) = sqrt ((p_1-q_1)^2 + .. + (p_n-q_n)^2), potresti quadrare la tua distanza d e confrontarla con quella parziale somme di (p_i-q_i)^2 e fermati quando superi d^2.

se questo effettivamente risparmiare tempo dipende da quanto costoso il confronto è quello di calcolare solo gli addendi e quanti calcoli addendo si potrebbe aspettare per evitare in questo modo (ovviamente, il più piccolo d è, meglio è).

Answer 2

Se la misura di similarità è transitiva, non c'è bisogno di calcolare la somiglianza per tutte le coppie di oggetti dal momento che per gli oggetti a, b, c:

similarity(a,c) = similarity(a,b) op similarity(b,c) 

dove op è un operatore binario per esempio moltiplicazione o aggiunta.

Answer 3

Possiamo supporre che la somiglianza sia transitiva, cioè. diff(a,c) == diff(a,b) + diff(b,c)? Se è così, puoi provare quanto segue:

1. Ordinare la raccolta di oggetti. Se la metrica di somiglianza dell'oggetto non ha un valore assoluto decente, puoi arbitrariamente selezionare un oggetto come "zero" e ordinare tutti gli altri oggetti in base alla loro somiglianza con quell'oggetto.
2. Per trovare gli oggetti con somiglianza s a o, trovare o nell'elenco ordinato e cercare a sinistra ea destra fino a quando il differenziale non supera s.

Il vantaggio di questo è che l'ordinamento può essere fatto una sola volta e la successiva costruzione del set è proporzionale al numero di membri che saranno nel set.

Answer 4

Ho bisogno di produrre una struttura di dati che mappa qualsiasi oggetto o all'insieme di oggetti più dissimili o di d, per un valore dissomiglianza d.

Potrebbe essere più veloce abbandonare il calcolo della somiglianza quando il totale parziale diventa maggiore di d. Ad esempio, se le somiglianze sono basate su distanze di coseno o hausdorff, ciò può facilmente essere fatto.

 

PS: se questo non può essere fatto, il problema potrebbe essere correlato al k-nearest problema vicini (o più precisamente un problema vicino più prossimo con un quartiere di soglia). Dovresti cercare algoritmi che trovino i membri più vicini senza calcolare tutte le distanze (magari usando la disuguaglianza triangolare). Wikipedia dovrebbe aiutarti a esplorare algoritmi adatti.

Answer 5

Penso che la soluzione dipenda da molti più dettagli sulla natura del problema.

1. È necessario trovare gli oggetti simili per lo stesso oggetto più volte o solo una volta? Se è molte volte, quindi creare una struttura di dati in cui si calcola la differenza una volta per ogni coppia e quindi connettere gli oggetti a oggetti simili in modo da poter recuperare l'elenco rapidamente senza ricalcolare potrebbe essere un miglioramento delle prestazioni molto utile.

2. Qual è la natura del calcolo? Ad un estremo, se la natura della differenza è che è, ad esempio, la differenza di altezza tra due persone, quindi mantenere l'elenco ordinato per altezza ti consente di trovare gli oggetti simili molto rapidamente. Suppongo che il vero problema sia più complicato di quello, ma seguendo questa logica, se la differenza è la somma di diverse quantità lineari, potresti creare una matrice multi-dimensionale e quindi immaginare concettualmente l'insieme di oggetti simili a quelli all'interno di una sfera n-dimensionale (cioè cerchio, sfera, ipersfera, ecc.) centrata attorno all'oggetto di riferimento, e di nuovo li trova direttamente. In realtà mi sembra che se i calcoli del raggio sono troppo complicati o richiedono troppo tempo di esecuzione, una buona approssimazione sarebbe quella di creare un cubo n-dimensionale (cioè quadrato, cubo, tesseract, ecc.) Attorno all'oggetto di riferimento, recuperare tutto oggetti che si trovano all'interno di quel cubo come "candidati" e quindi eseguono il calcolo effettivo sui candidati.

Ad esempio, supponiamo che la "differenza" è la somma dei valori assoluti delle differenze di tre attributi, dire a1, a2, a3 e. È possibile creare una matrice tridimensionale e impostare il valore di ciascun nodo della matrice sull'oggetto con tali valori, se presenti. Poi, se si desidera trovare tutti gli oggetti con differenze meno di d dall'oggetto o, si potrebbe scrivere:

for (x1=o.a1-d;x1<o.a1+d;++x1) 
{ 
    for (x2=o.a2-d;x1<o.a2+d;++x2) 
    { 
    for (x3=o.a3-d;x1<o.a3+d;++x3) 
    { 
     if (array[x1][x2][x3]!=null 
     && (abs(x1-o.a1)+abs(x2-o.a2)+abs(x3-o.a3)<=d) 
     { 
      ... found a match ... 
     } 
    } 
    } 
} 

ho il sospetto che le regole differenze sono più complicate di quello, ma va bene, basta aggiungere sofisticazione alla alrorithm a abbinare la complessità delle regole. Il punto è usare la matrice per limitare l'insieme di oggetti che devi esaminare.

3. Ancora sulla natura del calcolo: Se uno degli elementi che compongono la differenza, o qualche piccolo sottoinsieme, tende ad essere più importanti di altre, quindi creare una struttura di dati che ti permette di confrontare rapidamente per questo entro il raggio. Se è nell'intervallo, esegui il confronto completo. Se no, allora non lo guardi nemmeno.

Answer 6

Non è possibile utilizzare uno k d-tree?

Può essere necessario (se possibile) per normalizzare le dimensioni. Successivamente, è sufficiente compilare l'albero e utilizzare una ricerca "vicini più vicini a N" e cercare di trovare qualsiasi oggetto all'interno di un intervallo.

Answer 7

Esempio di oggetti: immagini, documenti. Naturalmente lavorare con la rappresentazione grezza di questi oggetti non è per lo più utile. di solito si pre-processa la forma grezza e la si trasforma in una forma normalizzata (per i documenti, ad esempio un vettore per il quale ogni voce rappresenta il numero/percentuale di volte in cui è apparsa una determinata parola, per le immagini potrebbe essere una rappresentazione delle caratteristiche visive trovate nell'immagine).

se d è fisso e un n^2 pre-calcolo è possibile, si potrebbe utilizzare una rappresentazione grafico usando una lista concatenata per ciascun oggetto per esempio. È possibile avere soluzioni più efficienti a scapito della precisione utilizzando algoritmi approssimativamente vicini più vicini.

Answer 8

Suoni come BK-Tree. Here is a small example. Che, fondamentalmente, creare albero e controllare quale ramo deve essere utilizzato per simili ricerca di oggetti e quali no, in modo da evitare O(n2)