Расстояние от точки до конечного множества точек

Question

У меня есть три numpy массива, скажем, X, Y и Z.

X содержит n массивов измерения m, т.е. [[x11,x12,...,x1m],[x21,x22,...,x2m],...,[xn1,xn2,...,xnm]]

Y содержит k (k> n ) массивы размерности m, т. е. [[y11,y12,...,y1m],[y21,y22,...,y2m],...,[yk1,yk2,...,ykm]]

Z содержит p (p [[z11,z12,...,z1m],[z21,z22,...,z2m],...,[zp1,zp2,...,zpm]]

для каждого элемента Z [i] из массива Z мне нужно вычислить расстояние (евклидово) до каждого элемента массива X и выбрать минимальное расстояние, которое будет обозначено как dist_X [i]. Я должен сделать то же самое, но с массивом Y и обозначить минимальное расстояние через dist_Y [i]. Затем для каждого элемента Z [i] of Z мне нужно вычислить значение dist_Y [i] / (dist_Y [i] + dist_X [i]).

Я попытался сделать что-то вроде этого:

import scipy
from scipy import spatial

def dist_sets(z):
    tree_X = spatial.cKDTree(X)
    tree_Y = spatial.cKDTree(Y)
    dist_X, minid_X=tree_X.query(z)
    dist_Y, minid_Y=tree_Y.query(z)
    return dist_Y/(dist_Y+dist_X)

print(dist_sets(Z))

Однако для больших n, k и p требуется МНОГО вычислительного времени; например (n, m) = (17727, 122), (k, m) = (542273, 122) и (p, m) = (140001, 122).

Есть ли способ оптимизации код в Python, таким образом, чтобы я мог оценить функцию dist_sets (Z) для всех элементов Z?

Answer 1

В документах для KDTree упоминается, что преимущества производительности ухудшаются при больших размерах. С 122 из них вы, вероятно, лучше с наивным векторизованным решением. Вот одна из возможностей:

from sklearn.metrics import pairwise_distances_argmin_min

def dist_sets2(Z):
  iX, dX = pairwise_distances_argmin_min(Z, X)
  iY, dY = pairwise_distances_argmin_min(Z, Y)
  return dY / (dX + dY)

Для k = p = 1000 на моей машине это в 17 раз быстрее, чем при использовании cKDTree.