Tìm hiểu về `leafsize` trong scipy.spatial.KDTree

Question

Báo cáo vấn đề:

Tôi có 150 nghìn điểm trong không gian 3D với tọa độ của chúng được lưu trữ trong ma trận với kích thước [150k, 3] tính bằng mm.

Tôi muốn tìm tất cả các lân cận của một điểm đã pcho nằm trong bán kính r. Và tôi muốn làm điều đó một cách chính xác nhất.

Tôi nên chọn leafsizetham số của mình như thế nào?

from scipy.spatial import KDTree
import numpy as np

pts = np.random.rand(150000,3)

T1 = KDTree(pts, leafsize=20)
T2 = KDTree(pts, leafsize=1)

neighbors1= T1.query_ball_point((0.3,0.2,0.1), r=2.0)
neighbors2= T2.query_ball_point((0.3,0.2,0.1), r=2.0)

np.allclose(sorted(neighbors1), sorted(neighbors2))
True

Answer 1

Hàm query_ball_pointsẽ trả về tập hợp điểm chính xác cho bất kỳ phiên bản nào của cây tìm kiếm. Các leafsizetham số không ảnh hưởng đến kết quả của truy vấn, chỉ việc thực hiện các kết quả.

Hãy tưởng tượng hai cây được hiển thị bên dưới cho cùng một dữ liệu (nhưng các tham số kích thước lá khác nhau) và một truy vấn tìm kiếm tất cả các điểm bên trong vòng tròn màu đỏ.

Trong cả hai trường hợp, mã sẽ chỉ trả về hai điểm nằm bên trong vòng tròn màu đỏ. Điều này được thực hiện bằng cách kiểm tra tất cả các điểm trong tất cả các hộp của cây giao với vòng tròn. Điều này dẫn đến khối lượng công việc khác nhau (tức là hiệu suất khác nhau) trong mỗi trường hợp. Đối với cây bên trái (tương ứng với kích thước lá lớn hơn), thuật toán phải kiểm tra xem 13 điểm có nằm bên trong vòng tròn hay không (6 ở ô giao trên và 7 ở ô giao dưới). Ở cây bên phải (cây có kích thước lá nhỏ hơn), chỉ có ba điểm được xử lý (một ở ô giao nhau phía trên và hai điểm ở ô giao nhau phía dưới).

Theo logic này, bạn có thể nghĩ rằng sẽ hợp lý khi luôn sử dụng kích thước lá nhỏ: điều này sẽ giảm thiểu số lượng so sánh thực tế ở cuối thuật toán (quyết định xem các điểm có thực sự nằm trong vùng truy vấn hay không). Nhưng nó không đơn giản như vậy: kích thước lá nhỏ hơn sẽ tạo ra cây sâu hơn, tăng thêm chi phí cho thời gian xây dựng và thời gian vận chuyển cây. Việc có được sự cân bằng phù hợp giữa hiệu suất truyền qua cây với so sánh cấp độ lá thực sự phụ thuộc vào loại dữ liệu đi vào cây và so sánh cấp độ lá cụ thể mà bạn đang thực hiện. Đó là lý do tại sao scipy cung cấp tham số leafsize như một đối số để bạn có thể điều chỉnh mọi thứ để hoạt động tốt nhất trên một thuật toán cụ thể.