Menu
I have about 30,000 vectors and each vector has about 300 elements.
For another vector (with same number elements), how can I efficiently find the most (cosine) similar vector?
This following is one implementation using a python loop:
from time import time
import numpy as np
vectors = np.load("np_array_of_about_30000_vectors.npy")
target = np.load("single_vector.npy")
print vectors.shape, vectors.dtype # (35196, 312) float3
print target.shape, target.dtype # (312,) float32
start_time = time()
for i, candidate in enumerate(vectors):
similarity = np.dot(candidate, target)/(np.linalg.norm(candidate)*np.linalg.norm(target))
if similarity > max_similarity:
max_similarity = similarity
max_index = i
print "done with loop in %s seconds" % (time() - start_time) # 0.466356039047 seconds
print "Most similar vector to target is index %s with %s" % (max_index, max_similarity) # index 2399 with 0.772758982696
The following with removed python loop is 44x faster, but isn't the same computation:
print "starting max dot"
start_time = time()
print(np.max(np.dot(vectors, target)))
print "done with max dot in %s seconds" % (time() - start_time) # 0.0105748176575 seconds
Is there a way to get this speedup associated with numpy doing the iterations without loosing the max index logic and the division of the normal product? For optimizing calculations like this, would it make sense to just do the calculations in C?
897
Cosine similarity is related to Euclidean distance by ‖x−y‖2=2(1−cos(θ)). So cos(θ)=1−12‖x−y‖2, assuming x and y have been normalised to be unit vectors. Therefore, if we want to maximise cosine similarity, we can minimise Euclidean distance and then make the conversion.
We use the below formula to compute the cosine similarity. where A and B are vectors: A.B is dot product of A and B: It is computed as sum of element-wise product of A and B. ||A|| is L2 norm of A: It is computed as square root of the sum of squares of elements of the vector A.
Cosine similarity is a measure of similarity between two non-zero vectors of an inner product space that measures the cosine of the angle between them. Similarity = (A.B) / (||A||. ||B||) where A and B are vectors.
However, the Euclidean distance measure will be more effective and it indicates that A' is more closer (similar) to B' than C'. As can be seen from the above output, the Cosine similarity measure was same but the Euclidean distance suggests points A and B are closer to each other and hence similar to each other.
You have the correct idea about avoiding the loop to get performance. You can use argmin to get the minimum distance index.
Though, I would change the distance calculation to scipy cdist as well. This way you can calculate distances to multiple targets and would be able to choose from several distance metrics, if need be.
import numpy as np
from scipy.spatial import distance
distances = distance.cdist([target], vectors, "cosine")[0]
min_index = np.argmin(distances)
min_distance = distances[min_index]
max_similarity = 1 - min_distance
HTH.
130
Edit: Hats off to @Deepak. cdist is the fastest, if you do need the actual computed value.
from scipy.spatial import distance
start_time = time()
distances = distance.cdist([target], vectors, "cosine")[0]
min_index = np.argmin(distances)
min_distance = distances[min_index]
print("done with loop in %s seconds" % (time() - start_time))
max_index = np.argmax(out)
print("Most similar vector to target is index %s with %s" % (max_index, max_similarity))
done with loop in 0.013602018356323242 seconds
Most similar vector to target is index 11001 with 0.2250217098612361
from time import time
import numpy as np
vectors = np.random.normal(0,100,(35196,300))
target = np.random.normal(0,100,(300))
start_time = time()
myvals = np.dot(vectors, target)
max_index = np.argmax(myvals)
max_similarity = myvals[max_index]
print("done with max dot in %s seconds" % (time() - start_time) )
print("Most similar vector to target is index %s with %s" % (max_index, max_similarity))
done with max dot in 0.009701013565063477 seconds
Most similar vector to target is index 12187 with 645549.917200941
max_similarity = 1e-10
start_time = time()
for i, candidate in enumerate(vectors):
similarity = np.dot(candidate, target)/(np.linalg.norm(candidate)*np.linalg.norm(target))
if similarity > max_similarity:
max_similarity = similarity
max_index = i
print("done with loop in %s seconds" % (time() - start_time))
print("Most similar vector to target is index %s with %s" % (max_index, max_similarity))
done with loop in 0.49567198753356934 seconds
Most similar vector to target is index 11001 with 0.2250217098612361
def my_func(candidate,target):
return np.dot(candidate, target)/(np.linalg.norm(candidate)*np.linalg.norm(target))
start_time = time()
out = np.apply_along_axis(my_func, 1, vectors,target)
print("done with loop in %s seconds" % (time() - start_time))
max_index = np.argmax(out)
print("Most similar vector to target is index %s with %s" % (max_index, max_similarity))
done with loop in 0.7495708465576172 seconds
Most similar vector to target is index 11001 with 0.2250217098612361
start_time = time()
vnorm = np.linalg.norm(vectors,axis=1)
tnorm = np.linalg.norm(target)
tnorm = np.ones(vnorm.shape)
out = np.matmul(vectors,target)/(vnorm*tnorm)
print("done with loop in %s seconds" % (time() - start_time))
max_index = np.argmax(out)
print("Most similar vector to target is index %s with %s" % (max_index, max_similarity))
done with loop in 0.04306602478027344 seconds
Most similar vector to target is index 11001 with 0.2250217098612361
42
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
