2011-12-15 28 views
9

Tôi bắt đầu học Python đến từ nền C++. Những gì tôi đang tìm kiếm là một cách nhanh chóng và dễ dàng để tìm gần nhất (láng giềng gần nhất) của một số điểm truy vấn đa chiều trong một mảng 2D (numpy) của các điểm đa chiều (cũng mảng numpy). Tôi biết rằng scipy có một cây k-d, nhưng tôi không nghĩ rằng đây là những gì tôi muốn. Trước hết, tôi sẽ thay đổi giá trị của các điểm đa chiều trong mảng 2D. Thứ hai, vị trí (tọa độ) của mỗi điểm trong mảng 2D quan trọng vì tôi cũng sẽ thay đổi hàng xóm của chúng.Vùng lân cận gần nhất Tìm kiếm bằng Python mà không có cây k-d

Tôi có thể viết chức năng đi qua mảng 2D và đo khoảng cách giữa điểm truy vấn và điểm trong mảng trong khi vẫn theo dõi điểm nhỏ nhất (sử dụng hàm khoảng cách không gian scipy để đo khoảng cách). Có chức năng tích hợp nào không? Tôi đang cố gắng tránh lặp qua mảng trong python càng nhiều càng tốt. Tôi cũng sẽ có nhiều điểm truy vấn vì vậy sẽ có ít nhất hai "cho vòng" - một để lặp qua các điểm truy vấn và cho mỗi truy vấn, một vòng lặp để lặp qua mảng 2D và tìm khoảng cách tối thiểu.

Cảm ơn lời khuyên nào.

Trả lời

1

Bạn có thể tính toán tất cả các khoảng cách scipy.spatial.distance.cdist(X, Y) hoặc sử dụng RTree cho dữ liệu động: .

+0

Tôi thích đề xuất đầu tiên, nhưng tôi thực hiện một truy vấn tại một thời điểm và cập nhật giá trị trong mảng (tương tự như SOM). Tôi có thể sử dụng cdist (X, Y) trong đó X chỉ là một truy vấn và cập nhật mảng và chuyển sang truy vấn tiếp theo. Rtree có vẻ như nó có thể là OK, nhưng tôi là một chút không chắc chắn về cách sử dụng nó trong tình hình của tôi. Tôi tự hỏi liệu có bất kỳ gói đồ thị nào cho phép tìm kiếm lân cận gần nhất với điểm bên ngoài không? Tôi có thể sử dụng một gói đồ thị để tạo ra một mạng lưới nơi mỗi nút là một điểm đa chiều. Một số tính năng khác của gói đồ thị sẽ có ích trong chương trình của tôi – COM

6

Nếu ngắn gọn là mục tiêu của bạn, bạn có thể làm điều này một liner:

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 

Nếu bạn có một vài điểm truy vấn:

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

Broadcasting là rất hữu ích cho loại điều. Tôi không chắc chắn nếu đây là những gì bạn cần, nhưng ở đây tôi sử dụng phát sóng để tìm chuyển giữa p (một điểm trong 3 không gian) và X (một bộ 10 điểm trong không gian 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 
0

Đối với tìm kiếm nhanh hơn và hỗ trợ cho chèn mục động, bạn có thể sử dụng một cây nhị phân cho các hạng mục kỹ thuật 2D, lớn hơn và ít hơn điều hành được xác định bởi khoảng cách đến một điểm tham chiếu (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)