Trovare la migliore somiglianza del coseno in un set di vettori

Question

Ho n vettori, ciascuno con m elementi (numero reale). Voglio trovare la coppia in cui la similarità cosine è massima tra tutte le coppie.

La soluzione semplice richiede O (n m).

Esiste una soluzione migliore?

aggiornamento

Cosine similarity/distance and triangle equation mi ispira che avrei potuto sostituire "coseno di similitudine" con "lunghezza della corda", che perde precisione ma aumenta la velocità di un sacco. (Ci sono molte soluzioni esistenti risolvendo vicino nello spazio metrico, come ANN)

Answer 1

coseno di similitudine sim(a,b) è related to Euclidean distance|a - b| da

|a - b|² = 2(1 - sim(a,b)) 

per versori a e b.

Ciò significa che la somiglianza del coseno è maggiore quando la distanza euclidea è la più piccola dopo la normalizzazione secondo la norma L2 e il problema si riduce al closest pair of points problem, che può essere risolto nel tempo O (n lg n).

Answer 2

È possibile verificare con il progetto simbase https://github.com/guokr/simbase, è un database nosql di somiglianza vettoriale.

Simbase usare sotto concetti:

• Vector set: un insieme di vettori
• indicate: la base per vettori, in un insieme di vettore hanno stessa base
• Raccomandazione: una sola direzione binario relazione tra due insiemi di vettori che hanno la stessa base

È possibile utilizzare redis-cli direttamente per le attività di amministrazione oppure è possibile utilizzare i collegamenti del client redis in lingue diverse. in modo corretto in un modo di programmazione. Ecco un esempio di Python

import redis 

    dest = redis.Redis(host='localhost', port=7654) 
    schema = ['a', 'b', 'c'] 
    dest.execute_command('bmk', 'ba', *schema) 
    dest.execute_command('vmk', 'ba', 'va') 
    dest.execute_command('rmk', 'va', 'va', 'cosinesq')