Alta dimensione Ricerca prossimità più vicina e Sensibilità localizzazione Hashing

Question

Ecco il problema principale. Ho un database molto grande (25.000 circa) di 48 vettori dimensionali, ognuno popolato con valori compresi tra 0 e 255. Le specifiche non sono così importanti, ma immagino che potrebbe contribuire a dare un contesto.

Non ho bisogno di un vicino più vicino, quindi sono accettabili le ricerche approssimative vicine con un livello di precisione. Sono stato in giro con Locality Sensitivity Hashing ma sono molto perso.

Ho scritto una funzione di hash come descritto nell'articolo in "Distribuzioni stabili" come meglio posso. Ecco il codice.

def lsh(vector, mean, stdev, r = 1.0, a = None, b = None): 
if not a: 
    a = [normalvariate(mean, stdev) for i in range(48)] 
if not b: 
    b = uniform(0, r) 
hashVal = (sum([a[i]*vectorA[i] for i in range(48)]) + b)/r 
return hashVal 

La funzione di hashing è "funzionante" almeno in parte. Se ordino un elenco di punti per il valore hash e la distanza media calcolata tra un punto e il suo vicino nell'elenco, la distanza media è circa 400, rispetto a una distanza media di circa 530 per qualsiasi due punti selezionati casualmente.

Le mie più grandi domande sono queste.

A: Qualsiasi suggerimento su dove posso leggere di più su questo. La mia ricerca non ha prodotto molti risultati.

B: Il metodo suggerisce di generare un valore intero (che il mio non ha). E poi dovresti cercare di trovare le corrispondenze per questo valore intero e una corrispondenza indica un vicino più probabile. Capisco che dovrei calcolare alcune serie di tabelle di valori hash per tutti i miei punti e quindi controllare le tabelle per le hash match, ma i valori che sto restituendo non sembrano abbastanza soddisfacenti da finire con partite a tutti. Sono necessari ulteriori test da parte mia.

C: Istruzioni su come costruire le funzioni di hash basate sugli altri metodi di hashing?

Answer 1

Maby questo è un po 'fuori tema ma è possibile provare a utilizzare PCA http://en.wikipedia.org/wiki/Principal_component_analysis per ridurre la dimensionalità del set di dati. Dovrebbero esserci molti moduli PCA progettati per numPy (ad esempio: http://folk.uio.no/henninri/pca_module/). Il metodo è piuttosto semplice e con moduli pronti all'uso sarà un gioco da ragazzi.

In sostanza, ciò che fa è ridurre il numero di dimensioni (dovresti essere in grado di specificare il numero desiderato) massimizzando la varianza all'interno del numero di dimensioni specificato.

Answer 2

Qui ci sono due risposte:

B: La pagina di Wikipedia indica che math.floor() deve essere utilizzato su hashVal: questo è il modo per ottenere numeri interi.

C: Se si desidera utilizzare il metodo di Hamming, è possibile implementare abbastanza semplice: ogni funzione di Hamming hash viene semplicemente definita da una coordinata (tra 0 e 47) e un numero di bit (tra 0 e 7) . È possibile ottenere il valore di un numero intero in un dato po b con:

bool(i & 2**b)