最適化ハミング距離Python

Question

私は、ハミング距離を得るためにそれらの間の距離を得るために必要なバイナリnumpy配列を持っています。最も近い方法は、私が得る最も速い方法は、距離を持つfloat行列を返すことです。

私はこのような時にそれを一つの要素をやっているので、私は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（別名sklearn）の素敵な人々doは、ハミング距離がサポートされたボールツリーの実装を持っています。ここでは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はブルートフォースアルゴリズムに匹敵するようになります。私はあなたのベクトルの性質について少し不明ですが、うまくいけば上のスニペットはあなたにいくつかのアイデア/方向を与えます。