Alto nivel vecino más cercano Búsqueda y sensibilidad de localidad Hashing

Question

Aquí está el problema principal. Tengo una base de datos muy grande (25,000 o más) de 48 vectores dimensionales, cada uno poblado con valores que van desde 0 hasta 255. Los detalles no son tan importantes, pero creo que podría ayudar a dar contexto.

No necesito un vecino más cercano, por lo que las búsquedas aproximadas de vecinos que están dentro de un grado de precisión son aceptables. He estado jugando con Locality Sensitivity Hashing pero estoy muy perdido.

He escrito una función hash como se describe en el artículo en "Distribuciones estables" lo mejor que puedo. Aquí está el código.

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 función hash es 'funcional' al menos algunas. Si ordeno una lista de puntos por valor de hash y calculo la distancia promedio entre un punto y su vecino en la lista, la distancia promedio es de aproximadamente 400, en comparación con una distancia promedio de aproximadamente 530 para dos puntos seleccionados al azar.

Mis preguntas más importantes son estas.

A: Cualquier sugerencia sobre dónde puedo leer más acerca de esto. Mi búsqueda no ha producido muchos resultados.

B: El método sugiere que genera un valor entero (que el mío no). Y entonces se supone que debes tratar de encontrar coincidencias para este valor entero y una coincidencia denota un vecino más cercano. Entiendo que se supone que debo calcular un conjunto de tablas de valores hash para todos mis puntos y luego verificar las tablas para las coincidencias hash, pero los valores que estoy devolviendo no parecen ser lo suficientemente buenos como para terminar con coincide en absoluto. Se necesitan más pruebas de mi parte.

C: Instrucciones sobre cómo construir funciones hash basadas en los otros métodos hash?

Answer 1

Maby esto es un poco fuera de tema, pero puede intentar usar PCA http://en.wikipedia.org/wiki/Principal_component_analysis para reducir la dimensionalidad del conjunto de datos. Debe haber muchos módulos de PCA diseñados para numPy (por ejemplo: http://folk.uio.no/henninri/pca_module/). El método es bastante simple y con un módulo listo para usar será muy fácil.

Básicamente, lo que hace es reducir el número de dimensiones (debe poder especificar el número deseado) maximizando la varianza dentro de la cantidad dada de dimensiones.

Answer 2

Aquí hay dos respuestas:

B: La página de Wikipedia indica que math.floor() debe utilizar en hashVal: esta es la forma de obtener números enteros.

C: Si desea utilizar el método de Hamming, puede implementarlo simplemente: cada función de Hamming hash simplemente se define mediante una coordenada (entre 0 y 47) y un número de bit (entre 0 y 7) . Usted puede obtener el valor de un número entero al b un bit determinado con:

bool(i & 2**b)