Оптимизация расстояния Хэмминга Python

Question

У меня есть около 1M двоичного массива numpy, который мне нужен, чтобы получить Хэмминг. Расстояние между ними, чтобы найти k-ближайших соседей, самый быстрый метод, который я получаю, использует cdist, возвращая матрицу с плавающей точкой с расстоянием.

Поскольку у меня нет памяти достаточно, чтобы получить флоат матрицу 1MX1M так, что я делаю это один элемент, в то время как это:

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

The probles является то, что это взято как 2-3s для каждый Hamming_Distance, до 1 м документа потребовалось целую вечность (и мне нужно использовать его для разных k).

Есть ли самый быстрый способ сделать это?

Я думаю о многопроцессорности или сделать это на C, но у меня есть некоторые проблемы, которые понимают, как это работает многопроцессорство на python, и я не знаю, как смешивать код C с кодом Python.

Answer 1

Если вы хотите вычислить k-ближайших соседей, нет необходимости вычислять все n^2 пары расстояний. Вместо этого вы можете использовать дерево Kd или дерево шаров (обе являются структурами данных для эффективного запроса отношений между множеством точек).

Scipy имеет пакет под названием scipy.spatial.kdtree. Тем не менее, не в настоящее время поддерживает расстояние хамминга как показатель между точками. Тем не менее, замечательные люди в scikit-learn (aka 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 становятся сравнимыми с алгоритмом грубой силы. Я немного неясен в отношении природы ваших векторов, но, надеюсь, приведенный выше фрагмент дает вам некоторые идеи/направление.