rilevamento somiglianza veloce

Question

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

Per essere precisi: dati due oggetti che possono calcolare la loro diversità come un numero, una metrica - valori superiori significano meno somiglianza e 0 indica gli oggetti hanno contenuto identico. Il costo del calcolo di tale numero è proporzionale alla dimensione dell'oggetto più piccolo (ogni oggetto ha una data dimensione).

Ho bisogno della capacità di trovare rapidamente, dato un oggetto, l'insieme degli oggetti simile ad esso.

Per essere precisi: Ho bisogno di produrre una struttura di dati che mappa qualsiasi oggetto o per l'insieme di oggetti non più dissimile o di d, per un valore dissimilarity d, in modo tale che elenca gli oggetti nel set non richiede più tempo che se fossero in una matrice o lista collegata (e forse in realtà sono). Tipicamente, il set sarà molto inferiore al numero totale di oggetti, quindi è veramente utile effettuare questo calcolo. E 'abbastanza buono, se la struttura dei dati assume una d fissa, ma se funziona per un d arbitrario, ancora meglio.

Hai visto questo problema prima, o qualcosa di simile ad esso? Che cosa è 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. C'è una soluzione generale, con complessità inferiori?

Answer 1

Senza conoscere i dettagli della metrica, è difficile da dire. Non ho qualche idea per eliminare la O (n ^ 2) aspetto, ma ci può essere un modo per ridurre alcune delle costanti coinvolti. Ad esempio, se si ha un d metrica euclidea (p, q) = sqrt ((P_1-Q_1) ^ 2 + .. + (p_n-q_n) ^ 2), si potrebbe quadrare la distanza d e confrontarlo con il parziale somme di (p_i-q_i) ^ 2 e fermarsi quando si supera d ^ 2.

Se questo sarà 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

  

Ho bisogno di produrre una struttura di dati   che associa qualsiasi oggetto o alla serie di   oggetti non più dissimili o di   d, per un valore dissimilarity d.

Potrebbe essere più veloce di abbandonare solo il calcolo similitudine, quando il totale parziale diventa più grande d. Ad esempio, se i somiglianze si basano su coseno o distanza di hausdorff questo può essere fatto facilmente.

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). Si dovrebbe cercare di algoritmi che trovano vicino-da membri senza calcolare tutte le distanze (forse qualcosa usando disuguaglianza triangolare). Wikipedia dovrebbe aiutare ad esplorare opportuni algoritmi.

Answer 3

Se la misura di similarità è transitiva, non si dispone 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 esempio moltiplicazione o aggiunta.

Answer 4

Penso che la soluzione dipende da molti più dettagli circa la natura del problema.

1. Avete bisogno di trovare gli oggetti simili per lo stesso oggetto più volte, o solo una volta? Se si tratta di molte volte, quindi la creazione di una struttura di dati in cui si calcola la differenza una volta per ogni coppia, quindi si collega oggetti per oggetti simili in modo da poter recuperare l'elenco rapidamente senza ricalcolo potrebbe essere molto utile miglioramento delle prestazioni.

2. Qual è la natura del calcolo? A un estremo, se la natura della differenza è che è, per esempio, la differenza di altezza tra due persone, quindi mantenendo l'elenco ordinato per altezza sarebbe consentono di trovare gli oggetti simili molto rapidamente. Sto assumendo il vero problema è più complicato di così, ma in seguito a questa logica, se la differenza è la somma di diverse grandezze lineari, è possibile creare un array multi-dimenstional, e quindi concettualmente immaginare l'insieme di oggetti simili a quelli all'interno di una sfera n-dimensionale (ad esempio cerchio, sfera, ipersfera, ecc) centrato intorno all'oggetto di riferimento, e di nuovo trovarli direttamente. In realtà mi viene in mente che, se i calcoli di raggio sono troppo complicato o prendere troppo in fase di esecuzione, una buona approssimazione sarebbe quello di creare un cubo n-dimensionale (cioè quadrato, cubo, Tesseract, ecc) intorno all'oggetto di riferimento, recuperare tutti gli oggetti che si trovano all'interno di tale cubo come "candidati", e poi basta fare il calcolo effettivo sui candidati.

Ad esempio, supponiamo che la "differenza" è la somma dei valori assoluti delle differenze di tre attributi, dire A1, A2 e A3. Si potrebbe creare una matrice 3-dimensionale e impostare il valore di ogni nodo della matrice all'oggetto con quei valori, se presente. 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 per abbinare la complessità delle regole. Il punto è quello di utilizzare la matrice per limitare l'insieme di oggetti che si devono esaminare.

3. Anche in questo caso 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 permette di confrontare rapidamente di questo raggio d'azione. Se si è in campo, fare il pieno confronto. Se no, allora non avrete nemmeno guarda.

Answer 5

Non è possibile utilizzare un k D-albero?

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

Answer 6

Esempio di oggetti: Immagini, documenti. Naturalmente lavorare con la rappresentazione grezzo di questi oggetti non è particolarmente utile. di solito ci si pre-processo la forma grezza e trasformarla in una forma normalizzata (per i documenti, ad esempio un vettore per il quale ogni voce rappresenta il numero / percentuale di volte che una certa parola apparve, per le immagini potrebbe essere una rappresentazione di caratteristiche visive trovato nell'immagine).

se d è fisso ed un n ^ 2 pre-calcolo è possibile, si potrebbe utilizzare una rappresentazione grafico usando una lista concatenata per ciascun oggetto per esempio. Si possono avere soluzioni più efficienti sul scapito della precisione utilizzando algoritmi approssimati vicini più prossimi.

Answer 7

Possiamo supporre che la somiglianza è transitiva, vale a dire. diff(a,c) == diff(a,b) + diff(b,c)? Se è così, si può provare il seguente:

1. Ordina la collezione di oggetti. Se la metrica oggetto somiglianza non ha un valore assoluto decente, è possibile selezionare una arbitrariamente oggetto come "zero" e ordinare tutti gli altri oggetti per la loro somiglianza con l'oggetto.
2. Per trovare gli oggetti con somiglianza s per o, trovare o nella lista ordinata, e di ricerca a sinistra ea destra fino a quando il diff cresce più grande di s.

Il vantaggio di ciò è che l'ordinamento può essere fatta una, e la successiva costruzione set è proporzionale al numero di membri che sarà nel set.

Answer 8

Sembra BK-Tree. href="https://nullwords.wordpress.com/2013/03/13/the-bk-tree-a-data-structure-for-spell-checking/" Ecco un piccolo esempio . 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)