9

n次元の点のコレクションがあり、どれが最も近いかを見つけたいと思います。私が2次元で思いつくことができる最高のものは次のとおりです。

from numpy import *
myArr = array( [[1, 2],
                [3, 4],
                [5, 6],
                [7, 8]] )

n = myArr.shape[0]
cross = [[sum( ( myArr[i] - myArr[j] ) ** 2 ), i, j]
         for i in xrange( n )
         for j in xrange( n )
         if i != j
         ]

print min( cross )

これは

[8, 0, 1]

しかし、これは大きなアレイには遅すぎます。どのような最適化を適用できますか？

関連している：

2つの異なるNumpy配列内のポイント間のユークリッド距離（内ではない）

4

7 に答える 7

11

試してみてくださいscipy.spatial.distance.pdist(myArr)。これにより、凝縮された距離行列が得られます。を使用argminして、最小値のインデックスを見つけることができます。これをペア情報に変換できます。

于 2011-02-25T16:38:20.603 に答える
9

この問題に関するウィキペディアのページ全体があります。次を参照してください: http://en.wikipedia.org/wiki/Closest_pair_of_points

エグゼクティブ サマリー: 再帰的な分割統治アルゴリズムを使用して O(n log n) を達成できます (上記の Wiki ページで概説されています)。

于 2011-02-25T16:20:06.200 に答える
6

SciPy（v0.9）のDelaunay三角測量ツールの最新バージョンを利用できます。最も近い2つのポイントは、三角形分割のシンプレックスのエッジになると確信できます。これは、すべての組み合わせを実行するよりもはるかに小さいペアのサブセットです。

コードは次のとおりです（一般的なND用に更新）：

import numpy
from scipy import spatial

def closest_pts(pts):
    # set up the triangluataion
    # let Delaunay do the heavy lifting
    mesh = spatial.Delaunay(pts)

    # TODO: eliminate reduncant edges (numpy.unique?)
    edges = numpy.vstack((mesh.vertices[:,:dim], mesh.vertices[:,-dim:]))

    # the rest is easy
    x = mesh.points[edges[:,0]]
    y = mesh.points[edges[:,1]]

    dists = numpy.sum((x-y)**2, 1)
    idx = numpy.argmin(dists)

    return edges[idx]
    #print 'distance: ', dists[idx]
    #print 'coords:\n', pts[closest_verts]

dim = 3
N = 1000*dim
pts = numpy.random.random(N).reshape(N/dim, dim)

密接にO（n）のようです：

ここに画像の説明を入力してください

于 2011-02-25T21:23:44.877 に答える
2

pdistかなり効率的な方法で配列内のポイント間のペアごとの距離を取得する scipy 関数があります。

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

N*(N-1)/2 個の一意のペアを出力します (r_ij == r_ji であるため)。次に、最小値を検索して、コード内のループ全体の混乱を回避できます。

于 2011-02-25T16:37:34.983 に答える
0

ネストされたループを実行して最短のペアを追跡するのと比較して、どのくらい高速ですか? 巨大なクロス配列を作成することが、あなたを傷つけている可能性があると思います。2 次元の点だけを処理している場合でも、O(n^2) はかなり高速です。

于 2011-02-25T16:24:21.067 に答える
0

受け入れられた答えは小さなデータセットには問題ありませんが、その実行時間はn**2. ただし、@payne が指摘したように、最適なソリューションはn*log(n)計算時間のスケーリングを達成できます。

この最適解は、次のようにsklearn.neighbors.BallTreeを使用して取得できます。

import matplotlib.pyplot as plt
import numpy as np
from sklearn.neighbors import BallTree as tree

n = 10
dim = 2
xy = np.random.uniform(size=[n, dim])

# This solution is optimal when xy is very large
res = tree(xy)
dist, ids = res.query(xy, 2)
mindist = dist[:, 1]  # second nearest neighbour
minid = np.argmin(mindist)

plt.plot(*xy.T, 'o')
plt.plot(*xy[ids[minid]].T, '-o')

この手順は、非常に大きなxy値のセットや大きなディメンションに対しても適切にスケーリングされますdim(ただし、例はケースを示していdim=2ます)。結果の出力は次のようになります

最も近い点のペアはオレンジ色の線で結ばれています

インポートを次の Scipy のものに置き換えることにより、scipy.spatial.cKDTreeを使用して同じソリューションを取得できます。sklearnただしcKDTree、 は とは異なりBallTree、高次元では適切にスケーリングされないことに注意してください。

from scipy.spatial import cKDTree as tree
于 2017-09-07T14:56:00.570 に答える