# Locality Sensitive Hash (similar to k-Nearest Neighbor), in Python+Numpy

I've tried implementing Locality Sensitive Hash, the algorithm that helps recommendation engines, and powers apps like Shazzam that can identify songs you heard at restaurants.

LSH is supposed to run far quicker than vanilla Nearest Neighbor, but alas mine is 10x slower. Can I get a hand?

Times:
nearest neighbor:  0.0012996239820495248
lsh             :  0.012921262998133898


I've kept things clean, and marginally documented, and it includes a test for timing as well as to compare the results:

import numpy as np
from scipy.spatial.distance import cosine
import timeit
np.random.seed(0)
np.set_printoptions(precision=3, suppress=True)

# ----------
# vanilla Nearest Neighbor

def nearest_neighbor(X, q, n=1):
'''
Nearest Neighbor, uses euclidean distance
X :: data; ndarray(samples, dimensions)
q :: query point; ndarray(dimensions)
n :: number of neighbors to return
'''
dist = np.sqrt(np.sum((X - q) ** 2, axis=1))
return X[dist.argsort()[:n]]

# ----------
# Cosine similarity of a matrix row-wise compared to a query vector

def cosine_mat1(X, q):
return np.apply_along_axis(lambda x: cosine(x, q), 1, X)

def cosine_mat2(X, q):
out = np.zeros(X.shape)
for ix, x in enumerate(X):
out[ix] = cosine(x, q)
return out

def cosine_mat3(X, q):
Xq = np.sum(X * q, axis=1)
XX = np.sum(X ** 2, axis=1)
qq = np.sum(q ** 2)
return 1.0 - Xq / np.sqrt(XX * qq)

# ----------
# Locality Sensitive Hash

def nearest_neighbor_lsh(X, q, hash_len, n=1):
'''
Locality Sensitive Hashing
X :: data points; ndarray(data point, dimension)
q :: query
'''

hyperslope = np.random.normal(size=(hash_len, X.shape))
hyperbias = np.random.normal(size=hash_len)
hashes = ((np.einsum('hd,nd->nh', hyperslope, X) + hyperbias) > 0)
q_hash = ((np.einsum('hd,d->h', hyperslope, q) + hyperbias)   > 0)
cosine_similarity = cosine_mat3(hashes, q_hash)
return X[cosine_similarity.argsort()[:n]]

# ----------
# Timing

samples = 10000
dims = 5
nearest_k = 10
hash_len = 100

X = np.random.normal(size=(samples, dims)) # 100 5D samples
q = np.ones(dims) * 0

print()
t1 = timeit.Timer('nearest_neighbor(X, q, n=nearest_k)', 'from __main__ import nearest_neighbor, X, q, nearest_k')
print('nearest neighbor: ', t1.timeit(number=1))
t2 = timeit.Timer('nearest_neighbor_lsh(X, q, hash_len=hash_len, n=nearest_k)', 'from __main__ import nearest_neighbor_lsh, X, q, nearest_k, hash_len')
print('lsh             : ', t2.timeit(number=1))

# ----------
# Check accuracy

c1 = nearest_neighbor(X, q, n=nearest_k)
c2 = nearest_neighbor_lsh(X, q, hash_len=hash_len, n=nearest_k)
print()
print('avg distance to neighbors: ', np.mean(np.sqrt(np.sum((c1 - q) ** 2, axis=1))))
print('avg distance using lsh   : ', np.mean(np.sqrt(np.sum((c2 - q) ** 2, axis=1))))
rs = X[np.random.randint(samples, size=nearest_k*100)] # random samples
print('avg distance to random   : ', np.mean(np.sqrt(np.sum((rs - q) ** 2, axis=1))))