Поиск ближайшего соседа в Python без k-d дерева - PullRequest
Новая
       19

Поиск ближайшего соседа в Python без k-d дерева

9 голосов
/ 16 декабря 2011

Я начинаю изучать Python из C ++. То, что я ищу, - это быстрый и простой способ найти ближайшую (ближайшую соседку) некоторой многомерной точки запроса в двумерном (числовом) массиве многомерных точек (также числовых массивов). Я знаю, что у Сципи есть k-d дерево, но я не думаю, что это то, чего я хочу. Прежде всего, я буду изменять значения многомерных точек в двумерном массиве. Во-вторых, положение (координаты) каждой точки в двумерном массиве имеет значение, так как я также буду менять их соседей.

Я мог бы написать функцию, которая проходит через 2D-массив и измеряет расстояние между точкой запроса и точками в массиве, отслеживая при этом наименьшую (используя функцию пространственного расстояния scipy для измерения расстояния). Есть ли встроенная функция, которая делает это? Я стараюсь избегать перебора массивов в Python, насколько это возможно. У меня также будет множество точек запроса, поэтому будет как минимум две «петли for» - одна для итерации точек запроса и для каждого запроса - цикл для итерации по двумерному массиву и поиска минимального расстояния.

Спасибо за любой совет.

Ответы [ 4 ]

5 голосов
/ 16 декабря 2011

Если ваша цель краткая, вы можете сделать это в одну строку: 

In [14]: X = scipy.randn(10,2)

In [15]: X
Out[15]: 
array([[ 0.85831163,  1.45039761],
       [ 0.91590236, -0.64937523],
       [-1.19610431, -1.07731673],
       [-0.48454195,  1.64276509],
       [ 0.90944798, -0.42998205],
       [-1.17765553,  0.20858178],
       [-0.29433563, -0.8737285 ],
       [ 0.5115424 , -0.50863231],
       [-0.73882547, -0.52016481],
       [-0.14366935, -0.96248649]])

In [16]: q = scipy.array([0.91, -0.43])

In [17]: scipy.argmin([scipy.inner(q-x,q-x) for x in X])
Out[17]: 4

Если у вас несколько точек запроса: 

In [18]: Q = scipy.array([[0.91, -0.43], [-0.14, -0.96]])

In [19]: [scipy.argmin([scipy.inner(q-x,q-x) for x in X]) for q in Q]
Out[19]: [4, 9]
4 голосов
/ 16 декабря 2011

Вещание очень полезно для такого рода вещей. Я не уверен, что это то, что вам нужно, но здесь я использую радиовещание, чтобы найти смещение между p (одна точка в 3-пространстве) и X (набор из 10 точек в 3-пространстве). 

import numpy as np

def closest(X, p):
    disp = X - p
    return np.argmin((disp*disp).sum(1))

X = np.random.random((10, 3))
p = np.random.random(3)

print X
#array([[ 0.68395953,  0.97882991,  0.68826511],
#       [ 0.57938059,  0.24713904,  0.32822283],
#       [ 0.06070267,  0.06561339,  0.62241713],
#       [ 0.93734468,  0.73026772,  0.33755815],
#       [ 0.29370809,  0.76298588,  0.68728743],
#       [ 0.66248449,  0.6023311 ,  0.76704199],
#       [ 0.53490144,  0.96555923,  0.43994738],
#       [ 0.23780428,  0.75525843,  0.46067472],
#       [ 0.84240565,  0.82573202,  0.56029917],
#       [ 0.66751884,  0.31561133,  0.19244683]])
print p
#array([ 0.587416 ,  0.4181857,  0.2539029])
print closest(X, p)
#9
1 голос
/ 16 декабря 2011

Вы можете рассчитать все расстояния scipy.spatial.distance.cdist( X, Y ) или используйте RTree для динамических данных: http://gispython.org/rtree/docs/class.html.

0 голосов
/ 23 декабря 2016

Для более быстрого поиска и поддержки динамической вставки элемента, вы можете использовать бинарное дерево для 2D-элементов, где больше и меньше, чем оператор определяются расстоянием до опорной точки (0,0). 

def dist(x1,x2):
    return np.sqrt( (float(x1[0])-float(x2[0]))**2 +(float(x1[1])-float(x2[1]))**2 )

class Node(object):

    def __init__(self, item=None,):
        self.item = item
        self.left = None
        self.right = None

    def __repr__(self):
        return '{}'.format(self.item)

    def _add(self, value, center):
        new_node = Node(value)
        if not self.item:
            self.item = new_node        
        else:
        vdist = dist(value,center)
        idist = dist(self.item,center)
            if vdist > idist:
                self.right = self.right and self.right._add(value, center) or new_node
            elif vdist < idist:
                self.left = self.left and self.left._add(value, center) or new_node
            else:
                print("BSTs do not support repeated items.")

        return self # this is necessary!!!

    def _isLeaf(self):
        return not self.right and not self.left

class BSTC(object):

    def __init__(self, center=[0.0,0.0]):
        self.root = None
    self.count = 0
    self.center = center

    def add(self, value):
        if not self.root:
            self.root = Node(value)
        else:
            self.root._add(value,self.center)
    self.count += 1

    def __len__(self): return self.count

    def closest(self, target):
            gap = float("inf")
            closest = float("inf")
            curr = self.root
            while curr:
                if dist(curr.item,target) < gap:
                    gap = dist(curr.item, target)
                    closest = curr
                if target == curr.item:
                    break
                elif dist(target,self.center) < dist(curr.item,self.center):
                    curr = curr.left
                else:
                    curr = curr.right
            return closest.item, gap


import util

bst = util.BSTC()
print len(bst)

arr = [(23.2323,34.34535),(23.23,36.34535),(53.23,34.34535),(66.6666,11.11111)]
for i in range(len(arr)): bst.add(arr[i])

f = (11.111,22.2222)
print bst.closest(f)
print map(lambda x: util.dist(f,x), arr)
...