Tôi có cơ sở dữ liệu với 500.000 điểm trong không gian 100 chiều và tôi muốn tìm 2 điểm gần nhất. Tôi phải làm nó như thế nào?Cách tìm 2 điểm gần nhất trong không gian 100 chiều với 500.000 điểm?
Cập nhật: Không gian là Euclide, Xin lỗi. Và cảm ơn tất cả các câu trả lời. BTW đây không phải là bài tập về nhà.
Bạn có thể thử số ANN library, nhưng điều đó chỉ cho kết quả đáng tin cậy tối đa 20 thứ nguyên.
Cảm ơn. ANN chỉ là những gì tôi đang tìm kiếm. Hy vọng rằng nó có thể chứa tất cả mọi thứ trong RAM. – louzer
ANN rất dễ sử dụng, nhưng cần lưu ý rằng nó là một triển khai gần đúng hàng xóm gần nhất, do đó không được đảm bảo là chính xác. –
Có một chương trong Introduction to Algorithms dành cho việc tìm kiếm hai điểm gần nhất trong không gian hai chiều trong thời gian O (n * logn). Bạn có thể xem nó trên google books. Trong thực tế, tôi đề nghị nó cho tất cả mọi người như cách họ áp dụng kỹ thuật phân chia và chinh phục cho vấn đề này là rất đơn giản, thanh lịch và ấn tượng.
Mặc dù nó không thể được mở rộng trực tiếp đến vấn đề của bạn (vì hằng số 7 sẽ được thay thế bằng 2^101 - 1), nó sẽ chỉ tốt cho hầu hết các tập dữ liệu. Vì vậy, nếu bạn có đầu vào ngẫu nhiên hợp lý, nó sẽ cung cấp cho bạn độ phức tạp O(n*logn*m) trong đó n là số điểm và m là số thứ nguyên.
chỉnh sửa
Đó là tất cả giả sử bạn có không gian Euclidian. Tức là, chiều dài của vector v là sqrt(v0^2 + v1^2 + v2^2 + ...). Tuy nhiên, nếu bạn có thể chọn chỉ số, có thể có các tùy chọn khác để tối ưu hóa thuật toán.
Chạy PCA trên dữ liệu của bạn để chuyển đổi vectơ từ 100 thứ nguyên thành 20 kích thước. Sau đó tạo một cây K-lân cận (KD-Tree) và nhận được 2 hàng xóm gần nhất dựa trên khoảng cách euclide.
Nói chung nếu không. kích thước là rất lớn, sau đó bạn phải hoặc là làm một cách tiếp cận vũ phu (song song + phân phối/bản đồ giảm) hoặc một cách tiếp cận dựa trên cụm.
Sử dụng cây kd. Bạn đang xem xét một vấn đề hàng xóm gần nhất và có cấu trúc dữ liệu được tối ưu hóa cao để xử lý loại vấn đề chính xác này.
http://en.wikipedia.org/wiki/Kd-tree
P.S. Vấn đề thú vị!
Đây là câu trả lời đúng. –
Sử dụng cấu trúc dữ liệu được gọi là KD-TREE. Bạn sẽ cần phải phân bổ rất nhiều bộ nhớ, nhưng bạn có thể khám phá một tối ưu hóa hoặc hai trên đường đi dựa trên dữ liệu của bạn.
http://en.wikipedia.org/wiki/Kd-tree.
Bạn tôi đang nghiên cứu Luận án Phd năm trước khi gặp phải vấn đề tương tự. Công việc của anh ta là theo thứ tự 1 triệu điểm trên 10 chiều. Chúng tôi đã xây dựng một thư viện kd-tree để giải quyết nó. Chúng tôi có thể tìm hiểu mã nếu bạn muốn liên hệ với chúng tôi ngoại tuyến.
Đây là giấy được xuất bản của mình: http://www.elec.qmul.ac.uk/people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf
kdtrees giúp bạn dễ dàng tìm thấy một người hàng xóm gần nhất với một điểm nhất định trong thời gian O (log n), như tôi nhớ. Có một tối ưu hóa để tìm cặp điểm gần nhất trong ít hơn O (n log n)? – rampion
-1, cũng theo wikipedia kD-tree có hiệu quả nếu N >> 2^k (trong đó k là kích thước và N số điểm; trong trường hợp này là 2^100 >> 5e5 và câu trả lời là hoàn toàn gây hiểu nhầm) – Unreason
10d là không phải 100d. Ngay cả khi các điểm dữ liệu nằm gần trong một mặt phẳng 10-d trong 100d, kd-tree không thể hoạt động (imho): nghĩ về một cây kd 100 s sâu. – denis
Đây có phải là không gian chỉ số không? – Seth
Không quan tâm, bạn đã nhận được không gian 100 chiều ở đâu? –
câu hỏi thiếu sự rõ ràng. đây có phải là câu hỏi toán học không? – Sarmaad