優化海明距離Python

Question

我有大約1M的二進制numpy數組，我需要讓漢明之間的距離找到de k-nearest-neighbors，我得到的最快速的方法是使用cdist，返回一個具有距離的浮點矩陣。

因爲我沒有足夠的內存來獲得1Mx1M浮點數矩陣所以我做在這樣的時候一個元素：

from scipy.spatial Import distance 
Hamming_Distance = distance.cdist(array1,all_array,'hamming') 

的probles是，它採取類似2-3S爲每個Hamming_Distance，到1m文件，它花了一個永恆（我需要用它來不同的k）。

有沒有最快的方法來做到這一點？

我在想多處理或在C上做它，但我有一些麻煩理解它如何工作python的多處理，我不知道如何混合C代碼與Python代碼。

Answer 1

如果要計算k個最近的鄰居，可能不需要計算所有n^2對距離。相反，您可以使用Kd樹或球樹（兩者都是用於高效查詢一組點之間關係的數據結構）。

Scipy有一個包叫scipy.spatial.kdtree。但是，而不是目前支持漢明距離作爲點之間的度量。然而，scikit-learn（aka sklearn）做的奇妙人做有支持漢明距離的球樹的實現。這是一個使用sklearn球樹的小例子。

from sklearn.neighbors import BallTree 
import numpy as np 

# Generate random binary data. 
data = np.random.random_integers(0, 1, size=(10,10)) 

# Implement BallTree. 
ballt = BallTree(data, leaf_size = 30, metric = 'hamming') 
distances, neighbors = ballt.query(data, k=3) 

print neighbors # Row n has the nth vector's k closest neighbors. 
print distances # Same idea but the hamming distance to neighbors. 

現在的大警告。對於高維矢量，KDTree和BallTree可與蠻力算法相媲美。我對你的載體的性質有點不清楚，但希望上面的片段給你一些想法/方向。