Tôi phải thực hiện k lân cận gần nhất tìm kiếm dữ liệu 10 chiều trong kd-tree.Là cây k-d hiệu quả cho tìm kiếm kNN. k gần nhất hàng xóm tìm kiếm
Nhưng vấn đề là thuật toán của tôi là rất nhanh cho k = 1, nhưng càng nhiều càng 2000X chậm cho k> 1 (k = 2,5,10,20,100)
Đây có phải là bình thường đối với cây kd, hoặc tôi đang làm gì đó lo lắng?
Vâng, điều này chủ yếu phụ thuộc vào việc triển khai và tập dữ liệu cụ thể của bạn.
Cây kém cân bằng sẽ có nghĩa là bạn phải tìm kiếm nhiều dữ liệu hơn mức cần thiết. Hãy chắc chắn rằng xây dựng cây của bạn là lành mạnh.
Nó cũng có thể phụ thuộc vào cách bạn tìm thấy hàng xóm k. Nếu thuật toán của bạn tìm kiếm cây cho hàng xóm gần nhất và lưu trữ nó, sau đó tìm kiếm thứ hai gần nhất và lưu trữ nó vv, sau đó bạn không thực hiện tìm kiếm rất hiệu quả. Thay vào đó, hãy giữ một danh sách chạy của k lân cận gần nhất và điểm bump trong danh sách khi bạn tìm thấy những người gần gũi hơn đi qua cây. Bằng cách này bạn tìm kiếm một lần, thay vì k lần.
Dù bằng cách nào, có vẻ như bạn đang thực hiện việc này cho một khóa học. Hãy thử nói chuyện với giáo sư, NVHTGV hoặc bạn học của bạn để xem kết quả của bạn có điển hình hay không.
Tôi biết câu hỏi này đã được trả lời, nhưng để biết thêm chi tiết về tìm kiếm KNN với cây k-d, xem Bentley (1975: 514), Truyền thông của ACM 18 (9), tháng 9.
Liên kết tới bài báo này: http://portal.acm.org/citation.cfm?id=361007 – RandomGuy
cây kém cân bằng là lý do. Tôi đã xem xét phương pháp xây dựng cây của mình và nó đã chọn kích thước phân chia sai. Cảm ơn gợi ý :) – Andraz