최적화 해밍 거리 파이썬

Question

난 주변에서 해밍 거리를 얻을 필요가 바이너리 numpy 배열의 1M 가지고, 가장 빠른 방법은 내가 얻을 수있는 가장 빠른 방법은 거리와 함께 플로트 매트릭스를 반환하는 cdist를 사용하고 있습니다.

나는이 같은 시간에 그것을 하나 개의 요소를하고 있어요 그래서 나는 1Mx1M 플로트 행렬을 얻을 메모리가 충분하지 않기 때문에 :

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

probles 그것을위한 2-3s 같이 촬영하고 있다는 것입니다 각각의 Hamming_Distance를 1m 문서로 만들려면 영원을 필요로했습니다 (그리고 다른 k에 그것을 사용해야합니다).

가장 빠른 방법은 없나요?

멀티 프로세싱을 고려하고 있거나 C로 만들었지 만 파이썬에서 멀티 프로세싱이 어떻게 작동하는지 이해하고 있으며 파이썬 코드와 C 코드를 어떻게 섞어야할지 모르겠다.

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는 무차별 대입 알고리즘과 유사합니다. 나는 벡터의 성격에 대해 조금 불분명하지만 위의 발췌 문장은 당신에게 몇 가지 아이디어/방향을 제시한다.