Xây dựng lưới xấp xỉ đồng nhất từ ​​mẫu ngẫu nhiên (trăn)

Question

Tôi muốn tạo lưới từ dữ liệu được lấy mẫu. Tôi có thể sử dụng thuật toán phân cụm học máy, như k-means, nhưng tôi muốn hạn chế các trung tâm được phân bố đồng đều.

Tôi đã tìm ra cách tiếp cận bằng cách sử dụng tìm kiếm hàng xóm gần nhất để tìm kiếm: chọn một điểm ngẫu nhiên, xóa tất cả các điểm trong bán kính r rồi lặp lại. Điều này hoạt động tốt, nhưng tự hỏi nếu có ai có cách làm tốt hơn (nhanh hơn).

Đáp lại ý kiến ​​Tôi đã thử hai phương pháp thay thế, một hóa ra chậm hơn người kia là như nhau ...

Phương pháp 0 (nỗ lực đầu tiên của tôi):

def get_centers0(X, r): 

    N = X.shape[0] 
    D = X.shape[1] 
    grid = np.zeros([0,D]) 
    nearest = near.NearestNeighbors(radius = r, algorithm = 'auto') 

    while N > 0: 
     nearest.fit(X) 
     x = X[int(random()*N), :] 
     _, del_x = nearest.radius_neighbors(x) 
     X = np.delete(X, del_x[0], axis = 0) 
     grid = np.vstack([grid, x]) 
     N = X.shape[0] 

    return grid 

Phương pháp 1 (sử dụng đồ thị precomputed):

def get_centers1(X, r): 

    N = X.shape[0] 
    D = X.shape[1] 
    grid = np.zeros([0,D]) 
    nearest = near.NearestNeighbors(radius = r, algorithm = 'auto') 
    nearest.fit(X) 
    graph = nearest.radius_neighbors_graph(X) 

    #This method is very slow even before doing any 'pruning' 

Cách 2:

def get_centers2(X, r, k): 

    N = X.shape[0] 
    D = X.shape[1] 
    k = k 
    grid = np.zeros([0,D]) 
    nearest = near.NearestNeighbors(radius = r, algorithm = 'auto') 

    while N > 0: 
     nearest.fit(X) 
     x = X[np.random.randint(0,N,k), :] 

     #min_dist = near.NearestNeighbors().fit(x).kneighbors(x, n_neighbors = 1, return_distance = True) 
     min_dist = dist(x, k, 2, np.ones(k)) # where dist is a cython compiled function 
     x = x[min_dist < 0.1,:] 

     _, del_x = nearest.radius_neighbors(x) 
     X = np.delete(X, del_x[0], axis = 0) 
     grid = np.vstack([grid, x]) 
     N = X.shape[0] 

    return grid 

Chạy những như sau:

N = 50000 
r = 0.1 
x1 = np.random.rand(N) 
x2 = np.random.rand(N) 
X = np.vstack([x1, x2]).T 

tic = time.time() 
grid0 = get_centers0(X, r) 
toc = time.time() 
print 'Method 0: ' + str(toc - tic) 

tic = time.time() 
get_centers1(X, r) 
toc = time.time() 
print 'Method 1: ' + str(toc - tic) 

tic = time.time() 
grid2 = get_centers2(X, r) 
toc = time.time() 
print 'Method 1: ' + str(toc - tic) 

Phương pháp 0 và 2 là như nhau ...

Method 0: 0.840130090714 
Method 1: 2.23365592957 
Method 2: 0.774812936783 

Answer 1

Tôi đã đưa ra một phương pháp rất đơn giản hiệu quả hơn nhiều so với những nỗ lực trước đây của tôi.

Điều này chỉ đơn giản là vòng lặp trên tập dữ liệu và thêm điểm hiện tại vào danh sách các điểm lưới chỉ khi nó lớn hơn khoảng cách r từ tất cả các trung tâm hiện có. Phương pháp này nhanh hơn khoảng 20 lần so với lần thử trước của tôi. Bởi vì không có thư viện bên ngoài liên quan đến tôi có thể chạy tất cả điều này trong cython ...

@cython.boundscheck(False) 
@cython.wraparound(False) 
@cython.nonecheck(False) 
def get_centers_fast(np.ndarray[DTYPE_t, ndim = 2] x, double radius): 

    cdef int N = x.shape[0] 
    cdef int D = x.shape[1] 
    cdef int m = 1 
    cdef np.ndarray[DTYPE_t, ndim = 2] xc = np.zeros([10000, D]) 
    cdef double r = 0 
    cdef double r_min = 10 
    cdef int i, j, k 

    for k in range(D): 
     xc[0,k] = x[0,k] 

    for i in range(1, N): 
     r_min = 10 
     for j in range(m): 
      r = 0 
      for k in range(D): 
       r += (x[i, k] - xc[j, k])**2 
      r = r**0.5 
      if r < r_min: 
       r_min = r 
     if r_min > radius: 
      m = m + 1 
      for k in range(D): 
       xc[m - 1,k] = x[i,k] 

    nonzero = np.nonzero(xc[:,0])[0] 
    xc = xc[nonzero,:] 

    return xc 

Chạy các phương pháp này như sau:

N = 40000 
r = 0.1 
x1 = np.random.normal(size = N) 
x1 = (x1 - min(x1))/(max(x1)-min(x1)) 
x2 = np.random.normal(size = N) 
x2 = (x2 - min(x2))/(max(x2)-min(x2)) 
X = np.vstack([x1, x2]).T 

tic = time.time() 
grid0 = gt.get_centers0(X, r) 
toc = time.time() 
print 'Method 0: ' + str(toc - tic) 

tic = time.time() 
grid2 = gt.get_centers2(X, r, 10) 
toc = time.time() 
print 'Method 2: ' + str(toc - tic) 

tic = time.time() 
grid3 = gt.get_centers_fast(X, r) 
toc = time.time() 
print 'Method 3: ' + str(toc - tic) 

Phương pháp mới là xung quanh nhanh hơn 20 lần. Nó có thể được thực hiện nhanh hơn nữa, nếu tôi dừng vòng lặp sớm (ví dụ: nếu k lặp liên tục không tạo ra một trung tâm mới).

Method 0: 0.219595909119 
Method 2: 0.191949129105 
Method 3: 0.0127329826355 

Answer 2

Có lẽ bạn chỉ có thể tái phù hợp với những đối tượng nearest mỗi k < < N xóa để đẩy nhanh quá trình. Hầu hết thời gian cấu trúc khu phố không nên thay đổi nhiều.

Answer 3

Tôi không chắc chắn từ câu hỏi chính xác những gì bạn đang cố gắng làm. Bạn đề cập đến việc muốn tạo "lưới gần đúng" hoặc "phân phối đồng đều", trong khi mã bạn cung cấp chọn một tập hợp con các điểm sao cho không có khoảng cách cặp nào lớn hơn r.

Một vài gợi ý có thể:

• nếu những gì bạn muốn là một xấp xỉ lưới, tôi sẽ xây dựng lưới bạn muốn xấp xỉ, và sau đó truy vấn cho hàng xóm gần nhất của mỗi điểm lưới. Tùy thuộc vào ứng dụng của bạn, bạn có thể cắt thêm các kết quả này thành các điểm cắt có khoảng cách từ điểm lưới lớn hơn hữu ích cho bạn.

• nếu những gì bạn muốn là một phân phối xấp xỉ thống nhất rút ra từ một trong những điểm, tôi sẽ làm một ước tính mật độ hạt nhân (sklearn.neighbors.KernelDensity) tại mỗi điểm, và làm một ngẫu nhiên phụ lựa chọn từ các tập dữ liệu trọng bởi nghịch đảo mật độ cục bộ tại mỗi điểm.

• nếu những gì bạn muốn là một tập hợp con điểm như vậy mà không khoảng cách cặp lớn hơnr, tôi sẽ bắt đầu bằng việc xây dựng một radius_neighbors_graph với bán kính r, nhờ đó sẽ chỉ trong một bước, cung cấp cho bạn một danh sách tất cả các điểm quá gần nhau. Sau đó, bạn có thể sử dụng thuật toán cắt tỉa tương tự như thuật toán bạn đã viết ở trên để xóa điểm dựa trên khoảng cách biểu đồ thưa thớt này.

Tôi hy vọng điều đó sẽ hữu ích!

Answer 4

Âm thanh như bạn đang cố gắng tái tạo lại một trong các cách sau:

• tính năng Cluster (xem BIRCH)
• bong bóng dữ liệu (xem "Dữ liệu bong bóng: Chất lượng hoạt động bảo tồn thúc đẩy cho clustering thứ bậc")
• tán phân cụm trước

nghĩa là khái niệm này đã được phát minh ít nhất ba lần với các biến thể nhỏ.

Về mặt kỹ thuật, nó là không phân cụm. K-có nghĩa là không thực sự phân nhóm hoặc.

Nó được mô tả đầy đủ hơn như là lượng tử hóa vector.