Tính toán mật độ điểm bằng cách sử dụng Python

Question

Tôi có một danh sách các tọa độ X và Y từ địa lý của một phần cụ thể của thế giới. Tôi muốn chỉ định từng tọa độ, trọng số, dựa trên vị trí nằm trong biểu đồ.

Ví dụ: Nếu một điểm nằm ở vị trí có rất nhiều nút khác xung quanh nó, nó nằm trong khu vực có mật độ cao và do đó có trọng số cao hơn.

Phương pháp trực tiếp nhất tôi có thể nghĩ là vẽ vòng tròn bán kính đơn vị xung quanh mỗi điểm và sau đó tính toán nếu các điểm khác nằm trong và sau đó sử dụng hàm, gán trọng số cho điểm đó. Nhưng điều này có vẻ nguyên thủy.

Tôi đã xem xét pySAL và NetworkX nhưng có vẻ như chúng hoạt động với biểu đồ. Tôi không có bất kỳ cạnh nào trong biểu đồ, chỉ là các nút.

Answer 1

Một giải pháp tiêu chuẩn sẽ sử dụng KDE (Kernel Density Estimation).
Tìm kiếm trên web: "Ước tính KDE", bạn sẽ tìm thấy các liên kết khổng lồ. trong loại Google: KDE Ước tính ext: pdf
Ngoài ra, Scipy có KDE, hãy làm theo http://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.gaussian_kde.html này. Có mã mẫu làm việc ở đó;)

Answer 2

Có, bạn có các cạnh và chúng là khoảng cách giữa các nút. Trong trường hợp của bạn, bạn có một đồ thị hoàn chỉnh với các cạnh có trọng số.

Chỉ cần lấy khoảng cách từ mỗi nút đến mỗi nút khác - cung cấp cho bạn O(N^2) về độ phức tạp thời gian - và sử dụng cả hai nút và cạnh làm đầu vào cho một trong các cách tiếp cận bạn tìm thấy.

Xảy ra dù vấn đề của bạn dường như là một vấn đề phân tích ngoài bất kỳ vấn đề nào khác; bạn nên thử chạy một số thuật toán phân cụm trên dữ liệu của mình, như K-means, cụm các nút dựa trên một hàm khoảng cách, trong đó bạn có thể chỉ cần sử dụng khoảng cách euclide.

Kết quả của thuật toán này chính xác là những gì bạn cần, vì bạn sẽ có các phần tử đóng, bạn sẽ biết điều gì và số lượng phần tử được gán cho từng nhóm và bạn sẽ có thể theo các giá trị này, hãy tạo hệ số bạn muốn chỉ định cho mỗi nút.

Mối quan tâm duy nhất đáng chú ý ở đây là bạn sẽ phải xác định số lượng clusters - k-means, k-clusters - bạn muốn tạo.

Answer 3

Nếu bạn có rất nhiều điểm, bạn có thể tính toán các nước láng giềng khu vực gần bằng hiệu quả hơn một KDTree:

import numpy as np 
import scipy.spatial as spatial 
points = np.array([(1, 2), (3, 4), (4, 5), (100,100)]) 
tree = spatial.KDTree(np.array(points)) 
radius = 3.0 

neighbors = tree.query_ball_tree(tree, radius) 
print(neighbors) 
# [[0, 1], [0, 1, 2], [1, 2], [3]] 

tree.query_ball_tree lợi nhuận chỉ số (của points) của những người hàng xóm gần nhất. Ví dụ: [0,1] (tại chỉ số 0) nghĩa là points[0] và points[1] nằm trong khoảng cách radius khoảng cách từ points[0]. [0,1,2] (tại chỉ mục 1) có nghĩa là points[0], points[1] và points[2] nằm trong khoảng cách radius khoảng cách từ points[1].

frequency = np.array(map(len, neighbors)) 
print(frequency) 
# [2 3 2 1] 
density = frequency/radius**2 
print(density) 
# [ 0.22222222 0.33333333 0.22222222 0.11111111] 

Answer 4

Bạn nghiêng ban đầu để vẽ một vòng tròn quanh mỗi điểm và đếm số điểm khác trong vòng tròn đó là một điểm tốt và được đề cập bởi unutbu, một KDTree sẽ là một cách nhanh chóng để giải quyết vấn đề.

Điều này có thể được thực hiện rất dễ dàng với PySAL, sử dụng kdtree của scipy dưới mui xe.

import pysal 
import numpy 
pts = numpy.random.random((100,2)) #generate some random points 
radius = 0.2 #pick an arbitrary radius 

#Build a Spatial Weights Matrix 
W = pysal.threshold_continuousW_from_array(pts, threshold=radius) 
# Note: if your points are in Latitude and Longitude you can increase the accuracy by 
#  passing the radius of earth to this function and it will use arc distances. 
# W = pysal.threshold_continuousW_from_array(pts, threshold=radius, radius=pysal.cg.RADIUS_EARTH_KM) 

print W.cardinalities 
#{0: 10, 1: 15, ..... } 

Nếu dữ liệu của bạn trong một Shapefile, chỉ đơn giản là thay thế threshold_continuousW_from_array với threshold_continuousW_from_shapefile, xem các tài liệu để biết chi tiết.