Phương pháp hiệu quả để tìm KNN của tất cả các nút trong KD-Tree

Question

Tôi hiện đang cố gắng tìm K Lân cận gần nhất của tất cả các nút trong số cân bằng KD-Tree (với K = 2).

Triển khai của tôi là biến thể của mã từ Wikipedia article và nhanh chóng tìm kiếm KNN của bất kỳ nút nào O (nhật ký N).

Vấn đề nằm ở chỗ tôi cần tìm KNN của mỗi nút. Sắp tới với khoảng O (N log N) nếu tôi lặp qua từng nút và thực hiện tìm kiếm.

Có cách nào hiệu quả hơn để thực hiện việc này không?

Answer 1

alt text http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif

Tùy thuộc vào nhu cầu của bạn, bạn có thể muốn thử nghiệm với các kỹ thuật tương đối. Để biết chi tiết, hãy kiểm tra công việc của Arya and Mount về chủ đề này. Một giấy chính là here. Các chi tiết phức tạp của BigO được đặt trong số '98 paper của chúng.

Tôi đã sử dụng thư viện của họ trên các tập dữ liệu chiều rất cao với hàng trăm nghìn phần tử. Nó nhanh hơn bất cứ thứ gì tôi tìm thấy. Thư viện xử lý cả tìm kiếm chính xác và gần đúng. Gói chứa một số tiện ích CLI mà bạn có thể sử dụng để dễ dàng thử nghiệm với tập dữ liệu của mình; và thậm chí hình dung cây kd (xem ở trên).

FWIW: Tôi đã sử dụng R Bindings.

Từ thủ ANN của:

... nó đã được chứng minh bởi Arya và Núi [AM93b] và Arya, et al. [AMN + 98] rằng nếu người dùng sẵn sàng chịu đựng một số lỗi nhỏ trong tìm kiếm (trả lại một điểm có thể không phải là hàng xóm gần nhất, nhưng không phải là cách xa điểm truy vấn hơn chính xác hàng xóm gần nhất) thì có thể đạt được những cải thiện đáng kể trong thời gian chạy là . ANN là hệ thống dành cho trả lời các truy vấn lân cận gần nhất cả chính xác và xấp xỉ.

Answer 2

Nếu chính các nút đó là điểm truy vấn thì thời gian tìm kiếm có thể thấp hơn. Bạn có thể bắt đầu với giai đoạn backtracking và các nút đầu tiên được kiểm tra đã gần điểm truy vấn. Sau đó, các khu vực rộng lớn của cây có thể được cắt tỉa sớm.

Hàng xóm gần nhất là quan hệ đối xứng (nếu n1 là hàng xóm gần nhất của n2, tương tự áp dụng cho n2) vì vậy bạn chỉ cần tìm kiếm một nửa các nút bỏ qua tất cả các nút đã được đánh dấu là hàng xóm gần nhất. Chỉ là một ý tưởng.

Bạn cũng có thể thử tìm kiếm KD-Tree BBF (Best-Bin First), điều này sẽ giúp bạn tìm kiếm các nút gần nhất (thùng) sớm hơn. Tôi đã thực hiện điều này trong C#, vì vậy hãy viết cho tôi nếu bạn quan tâm đến mã nguồn.

Tất nhiên, thời gian chạy thực tế phụ thuộc vào thứ nguyên, cấu trúc KD-Tree và phân phối điểm trong tập dữ liệu của bạn.

Phân cụm các điểm cũng có thể phù hợp.

Answer 3

Tôi đã sử dụng cây che phủ cho vấn đề này. Đây là liên kết: http://hunch.net/~jl/projects/cover_tree/cover_tree.html

Trong tập dữ liệu cho kích thước 50M (Tất cả truy vấn kNN, k = 100), cây bìa mất 5,5 giây để tạo và 120 cho truy vấn. Ann lib mất 3.3s để tạo cây và 138 để truy vấn.

được cập nhật: Hàng xóm gần nhất không phải là mối quan hệ đối xứng. Xem xét điều này: A (0,0) B (1,0) C (3,0). B là gần nhất cho C trong khi C không phải là gần nhất cho C

Answer 4

Cụm từ tìm kiếm là knn tham gia. Chính xác hơn, bạn có thể muốn tự tham gia.

Có lẽ những kết quả tìm kiếm giúp đỡ:

• http://scholar.google.com/scholar?q=k-d-tree+knn+join

Tôi đã chỉ nhìn thấy KNN tham gia các thuật toán cho R * -cây. Tuy nhiên, trong các thí nghiệm của riêng tôi, họ không thể làm tốt hơn một truy vấn lặp lại. Tôi có thể thiếu một số ý tưởng triển khai. Nhưng nói chung, việc nắm giữ dữ liệu một cách thích hợp cho việc tham gia cây là phức tạp hơn nhiều so với một truy vấn knn duy nhất.