الحد الأدنى للمسافة Euclidean بين النقاط في صفيفين مختلفين مختلفين، وليس في الداخل

Question

لدي 2 صفائف من عاشر-Y. الإحداثيات، وأود أن أجد الحد الأدنى لمسافة Euclidean بين كل نقطة في صفيف واحد مع الكل النقاط في الصفيف الآخر. المصفوفات ليست بالضرورة بنفس الحجم. علي سبيل المثال:

xy1=numpy.array(
[[  243,  3173],
[  525,  2997]])

xy2=numpy.array(
[[ 682, 2644],
[ 277, 2651],
[ 396, 2640]])

حلقات الطريقة الحالية من خلال كل تنسيق xy في xy1 وحساب المسافات بين تلك الإحداثيات والإحداثيات الأخرى.

mindist=numpy.zeros(len(xy1))
minid=numpy.zeros(len(xy1))

for i,xy in enumerate(xy1):
    dists=numpy.sqrt(numpy.sum((xy-xy2)**2,axis=1))
    mindist[i],minid[i]=dists.min(),dists.argmin()

هل هناك طريقة للقضاء على حلقة للحلقة وتنظيم حسابات العناصر حسب العناصر بين الصفيفين؟ أنا أتصور توليد مصفوفة المسافة التي يمكنني العثور عليها الحد الأدنى للعنصر في كل صف أو عمود.

طريقة أخرى للنظر في المشكلة. قل أنا uncatenate. xy1 (الطول م) و xy2 (الطول ب) إلى xy (الطول ن)، وأخزن أطوال الصفائف الأصلية. من الناحية النظرية، يجب أن أكون قادرا على توليد nxn. مصفوفة المسافة من تلك الإحداثيات التي يمكنني الاستيلاء عليها MXP. submatrix. هل هناك طريقة لتوليد هذه الخدمات السريعة بكفاءة؟

Answer 1

(بعد شهور عديدة)scipy.spatial.distance.cdist( X, Y )يعطي كل أزواج المسافات، ل x و y 2 dim، 3 ...
كما أنه 22 معايير مختلفة، مفصلةهنا .

# cdist example: (nx,dim) (ny,dim) -> (nx,ny)

from __future__ import division
import sys
import numpy as np
from scipy.spatial.distance import cdist

#...............................................................................
dim = 10
nx = 1000
ny = 100
metric = "euclidean"
seed = 1

    # change these params in sh or ipython: run this.py dim=3 ...
for arg in sys.argv[1:]:
    exec( arg )
np.random.seed(seed)
np.set_printoptions( 2, threshold=100, edgeitems=10, suppress=True )

title = "%s  dim %d  nx %d  ny %d  metric %s" % (
        __file__, dim, nx, ny, metric )
print "\n", title

#...............................................................................
X = np.random.uniform( 0, 1, size=(nx,dim) )
Y = np.random.uniform( 0, 1, size=(ny,dim) )
dist = cdist( X, Y, metric=metric )  # -> (nx, ny) distances
#...............................................................................

print "scipy.spatial.distance.cdist: X %s Y %s -> %s" % (
        X.shape, Y.shape, dist.shape )
print "dist average %.3g +- %.2g" % (dist.mean(), dist.std())
print "check: dist[0,3] %.3g == cdist( [X[0]], [Y[3]] ) %.3g" % (
        dist[0,3], cdist( [X[0]], [Y[3]] ))


# (trivia: how do pairwise distances between uniform-random points in the unit cube
# depend on the metric ? With the right scaling, not much at all:
# L1 / dim      ~ .33 +- .2/sqrt dim
# L2 / sqrt dim ~ .4 +- .2/sqrt dim
# Lmax / 2      ~ .4 +- .2/sqrt dim

Answer 2

لحساب M By P مصفوفة المسافات، وهذا يجب أن يعمل:

>>> def distances(xy1, xy2):
...   d0 = numpy.subtract.outer(xy1[:,0], xy2[:,0])
...   d1 = numpy.subtract.outer(xy1[:,1], xy2[:,1])
...   return numpy.hypot(d0, d1)

ال .outer المكالمات تجعل اثنين من هذه المصفوفات (من الاختلافات العددية على طول المحورين)، .hypot تقوم المكالمات بتحويل تلك الموجودة في مصفوفة الشكل (لمسافات Euclidean العددية).

Answer 3

لماذا تحاول القيام به:

dists = numpy.sqrt((xy1[:, 0, numpy.newaxis] - xy2[:, 0])**2 + (xy1[:, 1, numpy.newaxis - xy2[:, 1])**2)
mindist = numpy.min(dists, axis=1)
minid = numpy.argmin(dists, axis=1)

يحرر: بدلا من الاتصال sqrt, ، القيام المربعات، إلخ، يمكنك استخدام numpy.hypot:

dists = numpy.hypot(xy1[:, 0, numpy.newaxis]-xy2[:, 0], xy1[:, 1, numpy.newaxis]-xy2[:, 1])

Answer 4

الإجابة المقبولة لا تعالج المسألة بالكامل، والتي تطلب العثور على الحد الأدنى المسافة بين مجموعتين من النقاط، وليس المسافة بين كل نقطة في المجموعتين.

Altough الحل المباشر للسؤال الأصلي يتكون بالفعل من الحوسبة المسافة بين كل إخراج الزوج وإيجاد واحد على الأقل، هذا ليس ضروريا إذا كان أحد مهتم فقط في الحد الأدنى المسافات. حل أسرع بكثير يوجد مشكلة الأخيرة.

جميع الحلول المقترحة لها وقت قيد التشغيل m*p = len(xy1)*len(xy2). وبعد هذا جيد لمجموعات البيانات الصغيرة، ولكن يمكن كتابة الحل الأمثل أن المقاييس كما m*log(p), ، إنتاج مدخرات ضخمة كبيرة xy2 مجموعات البيانات.

هذا التنفيذ الأمثل وقت التحجيم يمكن تحقيقه باستخدام scipy.spatial.ckdtree. كالآتي

import numpy as np
from scipy import spatial

xy1 = np.array(
    [[243,  3173],
     [525,  2997]])

xy2 = np.array(
    [[682, 2644],
     [277, 2651],
     [396, 2640]])

# This solution is optimal when xy2 is very large
tree = spatial.cKDTree(xy2)
mindist, minid = tree.query(xy1)
print(mindist)

# This solution by @denis is OK for small xy2
mindist = np.min(spatial.distance.cdist(xy1, xy2), axis=1)
print(mindist)

أين mindist هو الحد الأدنى للمسافة بين كل نقطة في xy1 ومجموعة النقاط في xy2

Answer 5

import numpy as np
P = np.add.outer(np.sum(xy1**2, axis=1), np.sum(xy2**2, axis=1))
N = np.dot(xy1, xy2.T)
dists = np.sqrt(P - 2*N)